Merge pull request #636 from josharian/perf

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

1 files changed, 21 insertions, 13 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