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

Using a large (50gb) database with a read-write-delete heavy load,
nearly 100% of allocated space came from freelists.
1/3 came from freelist.release, 1/3 from freelist.write,
and 1/3 came from tx.allocate to make space for freelist.write.
In the case of freelist.write, the newly allocated giant slice gets
copied to the space prepared by tx.allocate and then discarded.

To avoid this, add func mergepgids that accepts a destination slice,
and use it in freelist.write.

This has a mild negative impact on the existing benchmarks,
but cuts allocated space in my real world db by over 30%.

name                      old time/op    new time/op    delta
_FreelistRelease10K-8       18.7µs ±10%    18.2µs ± 4%    ~             (p=0.548 n=5+5)
_FreelistRelease100K-8       233µs ± 5%     258µs ±20%    ~             (p=0.151 n=5+5)
_FreelistRelease1000K-8     3.34ms ± 8%    3.13ms ± 8%    ~             (p=0.151 n=5+5)
_FreelistRelease10000K-8    32.3ms ± 1%    32.2ms ± 7%    ~             (p=0.690 n=5+5)
DBBatchAutomatic-8          2.18ms ± 3%    2.19ms ± 4%    ~             (p=0.421 n=5+5)
DBBatchSingle-8              140ms ± 6%     140ms ± 4%    ~             (p=0.841 n=5+5)
DBBatchManual10x100-8       4.41ms ± 2%    4.37ms ± 3%    ~             (p=0.548 n=5+5)

name                      old alloc/op   new alloc/op   delta
_FreelistRelease10K-8       82.5kB ± 0%    82.5kB ± 0%    ~     (all samples are equal)
_FreelistRelease100K-8       805kB ± 0%     805kB ± 0%    ~     (all samples are equal)
_FreelistRelease1000K-8     8.05MB ± 0%    8.05MB ± 0%    ~     (all samples are equal)
_FreelistRelease10000K-8    80.4MB ± 0%    80.4MB ± 0%    ~             (p=1.000 n=5+5)
DBBatchAutomatic-8           384kB ± 0%     384kB ± 0%    ~             (p=0.095 n=5+5)
DBBatchSingle-8             17.2MB ± 1%    17.2MB ± 1%    ~             (p=0.310 n=5+5)
DBBatchManual10x100-8        908kB ± 0%     902kB ± 1%    ~             (p=0.730 n=4+5)

name                      old allocs/op  new allocs/op  delta
_FreelistRelease10K-8         5.00 ± 0%      5.00 ± 0%    ~     (all samples are equal)
_FreelistRelease100K-8        5.00 ± 0%      5.00 ± 0%    ~     (all samples are equal)
_FreelistRelease1000K-8       5.00 ± 0%      5.00 ± 0%    ~     (all samples are equal)
_FreelistRelease10000K-8      5.00 ± 0%      5.00 ± 0%    ~     (all samples are equal)
DBBatchAutomatic-8           10.2k ± 0%     10.2k ± 0%  +0.07%          (p=0.032 n=5+5)
DBBatchSingle-8              58.6k ± 0%     59.6k ± 0%  +1.70%          (p=0.008 n=5+5)
DBBatchManual10x100-8        6.02k ± 0%     6.03k ± 0%  +0.17%          (p=0.029 n=4+4)

1 files changed, 25 insertions, 6 deletions

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...)
 }