diff options
| -rw-r--r-- | .gitignore | 1 | ||||
| -rw-r--r-- | freelist.go | 15 | ||||
| -rw-r--r-- | freelist_test.go | 27 | ||||
| -rw-r--r-- | page.go | 38 | ||||
| -rw-r--r-- | page_test.go | 43 |
5 files changed, 117 insertions, 7 deletions
@@ -1,3 +1,4 @@ *.prof *.test +*.swp /bin/ diff --git a/freelist.go b/freelist.go index 1346e82..0161948 100644 --- a/freelist.go +++ b/freelist.go @@ -48,15 +48,14 @@ func (f *freelist) pending_count() int { // all returns a list of all free ids and all pending ids in one sorted list. func (f *freelist) all() []pgid { - ids := make([]pgid, len(f.ids)) - copy(ids, f.ids) + m := make(pgids, 0) for _, list := range f.pending { - ids = append(ids, list...) + m = append(m, list...) } - sort.Sort(pgids(ids)) - return ids + sort.Sort(m) + return pgids(f.ids).merge(m) } // allocate returns the starting page id of a contiguous list of pages of a given size. @@ -127,15 +126,17 @@ func (f *freelist) free(txid txid, p *page) { // release moves all page ids for a transaction id (or older) to the freelist. func (f *freelist) release(txid txid) { + m := make(pgids, 0) for tid, ids := range f.pending { if tid <= txid { // Move transaction's pending pages to the available freelist. // Don't remove from the cache since the page is still free. - f.ids = append(f.ids, ids...) + m = append(m, ids...) delete(f.pending, tid) } } - sort.Sort(pgids(f.ids)) + sort.Sort(m) + f.ids = pgids(f.ids).merge(m) } // rollback removes the pages from a given pending tx. diff --git a/freelist_test.go b/freelist_test.go index 792ca92..8caeab2 100644 --- a/freelist_test.go +++ b/freelist_test.go @@ -1,7 +1,9 @@ package bolt import ( + "math/rand" "reflect" + "sort" "testing" "unsafe" ) @@ -127,3 +129,28 @@ func TestFreelist_write(t *testing.T) { t.Fatalf("exp=%v; got=%v", exp, f2.ids) } } + +func Benchmark_FreelistRelease10K(b *testing.B) { benchmark_FreelistRelease(b, 10000) } +func Benchmark_FreelistRelease100K(b *testing.B) { benchmark_FreelistRelease(b, 100000) } +func Benchmark_FreelistRelease1000K(b *testing.B) { benchmark_FreelistRelease(b, 1000000) } +func Benchmark_FreelistRelease10000K(b *testing.B) { benchmark_FreelistRelease(b, 10000000) } + +func benchmark_FreelistRelease(b *testing.B, size int) { + ids := randomPgids(size) + pending := randomPgids(len(ids) / 400) + b.ResetTimer() + for i := 0; i < b.N; i++ { + f := &freelist{ids: ids, pending: map[txid][]pgid{1: pending}} + f.release(1) + } +} + +func randomPgids(n int) []pgid { + rand.Seed(42) + pgids := make(pgids, n) + for i := range pgids { + pgids[i] = pgid(rand.Int63()) + } + sort.Sort(pgids) + return pgids +} @@ -3,6 +3,7 @@ package bolt import ( "fmt" "os" + "sort" "unsafe" ) @@ -132,3 +133,40 @@ type pgids []pgid func (s pgids) Len() int { return len(s) } func (s pgids) Swap(i, j int) { s[i], s[j] = s[j], s[i] } func (s pgids) Less(i, j int) bool { return s[i] < s[j] } + +// merge returns the sorted union of a and b. +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 { + return a + } + + // Create a list to hold all elements from both lists. + merged := make(pgids, 0, len(a)+len(b)) + + // Assign lead to the slice with a lower starting value, follow to the higher value. + lead, follow := a, b + if b[0] < a[0] { + lead, follow = b, a + } + + // Continue while there are elements in the lead. + for len(lead) > 0 { + // Merge largest prefix of lead that is ahead of follow[0]. + n := sort.Search(len(lead), func(i int) bool { return lead[i] > follow[0] }) + merged = append(merged, lead[:n]...) + if n >= len(lead) { + break + } + + // Swap lead and follow. + lead, follow = follow, lead[n:] + } + + // Append what's left in follow. + merged = append(merged, follow...) + + return merged +} diff --git a/page_test.go b/page_test.go index 7a4d327..59f4a30 100644 --- a/page_test.go +++ b/page_test.go @@ -1,7 +1,10 @@ package bolt import ( + "reflect" + "sort" "testing" + "testing/quick" ) // Ensure that the page type can be returned in human readable format. @@ -27,3 +30,43 @@ func TestPage_typ(t *testing.T) { func TestPage_dump(t *testing.T) { (&page{id: 256}).hexdump(16) } + +func TestPgids_merge(t *testing.T) { + a := pgids{4, 5, 6, 10, 11, 12, 13, 27} + b := pgids{1, 3, 8, 9, 25, 30} + c := a.merge(b) + if !reflect.DeepEqual(c, pgids{1, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 25, 27, 30}) { + t.Errorf("mismatch: %v", c) + } + + a = pgids{4, 5, 6, 10, 11, 12, 13, 27, 35, 36} + b = pgids{8, 9, 25, 30} + c = a.merge(b) + if !reflect.DeepEqual(c, pgids{4, 5, 6, 8, 9, 10, 11, 12, 13, 25, 27, 30, 35, 36}) { + t.Errorf("mismatch: %v", c) + } +} + +func TestPgids_merge_quick(t *testing.T) { + if err := quick.Check(func(a, b pgids) bool { + // Sort incoming lists. + sort.Sort(a) + sort.Sort(b) + + // Merge the two lists together. + got := a.merge(b) + + // The expected value should be the two lists combined and sorted. + exp := append(a, b...) + sort.Sort(exp) + + if !reflect.DeepEqual(exp, got) { + t.Errorf("\nexp=%+v\ngot=%+v\n", exp, got) + return false + } + + return true + }, nil); err != nil { + t.Fatal(err) + } +} |