From 4d8824b05d255bcad03f6a777c34bcdfb9bb5cfb Mon Sep 17 00:00:00 2001 From: Josh Bleecher Snyder Date: Tue, 20 Dec 2016 14:04:46 -0800 Subject: Don't allocate huge slices to merge pgids in freelist.write MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit 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) --- page.go | 31 +++++++++++++++++++++++++------ 1 file changed, 25 insertions(+), 6 deletions(-) (limited to 'page.go') 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...) } -- cgit v1.2.3