Merge pull request #636 from josharian/perf

Don't allocate huge slices to merge pgids in freelist.write

3 files changed, 49 insertions, 20 deletions

diff --git a/freelist.go b/freelist.go
index d32f6cd..53efa8f 100644
--- a/freelist.go
+++ b/freelist.go
@@ -46,16 +46,24 @@ func (f *freelist) pending_count() int {
 	return count
 }
 
-// all returns a list of all free ids and all pending ids in one sorted list.
-func (f *freelist) all() []pgid {
-	m := make(pgids, 0)
+// lenall returns the combined number of all free ids and all pending ids.
+func (f *freelist) lenall() int {
+	n := len(f.ids)
+	for _, list := range f.pending {
+		n += len(list)
+	}
+	return n
+}
 
+// all copies into dst a list of all free ids and all pending ids in one sorted list.
+// f.lenall returns the minimum length required for dst.
+func (f *freelist) copyall(dst []pgid) {
+	m := make(pgids, 0, len(f.pending)) // len(f.pending) undercounts, but it is a start
 	for _, list := range f.pending {
 		m = append(m, list...)
 	}
-
 	sort.Sort(m)
-	return pgids(f.ids).merge(m)
+	mergepgids(dst, f.ids, m)
 }
 
 // allocate returns the starting page id of a contiguous list of pages of a given size.
@@ -186,22 +194,22 @@ func (f *freelist) read(p *page) {
 // become free.
 func (f *freelist) write(p *page) error {
 	// Combine the old free pgids and pgids waiting on an open transaction.
-	ids := f.all()
 
 	// Update the header flag.
 	p.flags |= freelistPageFlag
 
 	// The page.count can only hold up to 64k elements so if we overflow that
 	// number then we handle it by putting the size in the first element.
-	if len(ids) == 0 {
-		p.count = uint16(len(ids))
-	} else if len(ids) < 0xFFFF {
-		p.count = uint16(len(ids))
-		copy(((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[:], ids)
+	lenids := f.lenall()
+	if lenids == 0 {
+		p.count = uint16(lenids)
+	} else if lenids < 0xFFFF {
+		p.count = uint16(lenids)
+		f.copyall(((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[:])
 	} else {
 		p.count = 0xFFFF
-		((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[0] = pgid(len(ids))
-		copy(((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[1:], ids)
+		((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[0] = pgid(lenids)
+		f.copyall(((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[1:])
 	}
 
 	return nil
diff --git a/page.go b/page.go
index 7651a6b..ccc6666 100644
--- a/page.go
+++ b/page.go
@@ -145,12 +145,33 @@ func (a pgids) merge(b pgids) pgids {
 	// Return the opposite slice if one is nil.
 	if len(a) == 0 {
 		return b
-	} else if len(b) == 0 {
+	}
+	if len(b) == 0 {
 		return a
 	}
+	merged := make(pgids, len(a)+len(b))
+	mergepgids(merged, a, b)
+	return merged
+}
+
+// merge copies the sorted union of a and b into dst.
+// If dst is too small, it panics.
+func mergepgids(dst, a, b pgids) {
+	if len(dst) < len(a)+len(b) {
+		panic(fmt.Errorf("mergepgids bad len %d < %d + %d", len(dst), len(a), len(b)))
+	}
+	// Copy in the opposite slice if one is nil.
+	if len(a) == 0 {
+		copy(dst, b)
+		return
+	}
+	if len(b) == 0 {
+		copy(dst, a)
+		return
+	}
 
-	// Create a list to hold all elements from both lists.
-	merged := make(pgids, 0, len(a)+len(b))
+	// Merged will hold all elements from both lists.
+	merged := dst[:0]
 
 	// Assign lead to the slice with a lower starting value, follow to the higher value.
 	lead, follow := a, b
@@ -172,7 +193,5 @@ func (a pgids) merge(b pgids) pgids {
 	}
 
 	// Append what's left in follow.
-	merged = append(merged, follow...)
-
-	return merged
+	_ = append(merged, follow...)
 }
diff --git a/tx.go b/tx.go
index 1cfb4cd..37a8ca1 100644
--- a/tx.go
+++ b/tx.go
@@ -381,7 +381,9 @@ func (tx *Tx) Check() <-chan error {
 func (tx *Tx) check(ch chan error) {
 	// Check if any pages are double freed.
 	freed := make(map[pgid]bool)
-	for _, id := range tx.db.freelist.all() {
+	all := make([]pgid, tx.db.freelist.lenall())
+	tx.db.freelist.copyall(all)
+	for _, id := range all {
 		if freed[id] {
 			ch <- fmt.Errorf("page %d: already freed", id)
 		}