Create a generic BTreeG for Go 1.18 and beyond.

[gconnell]

With the introduction of generics in Go 1.18, we have the opportunity to use them for our btrees. However, we want to make sure that our API remains compatible with past uses. So, we introduce a new BTreeG which is a generic API. We then utilize it to recreate the original BTree of Item interfaces.

Go compilers <1.18 will compile btree.go, containing just the original BTree of Items. Go compilers >=1.18 instead compile btree_generic.go which creates the BTreeG generic and uses it to make a BTree of Items with the same API as that exposed in btree.go.

One major difference between the APIs of BTree and BTreeG is that, for BTree, we could return a nil Item to connote "nothing was found". For generics, users may often want to store the zero value, so we can't treat the zero value as "missing". For that reason, you'll see these differences in APIs:

  func (t *Btree)     Get(item Item) Item      { ... }
  func (t *BtreeG[T]) Get(item T)    (T, bool) { ... }

Note that we now return a second boolean return value, which is true if the value was found and false otherwise.

Using the generic for base types like int greatly speeds up processing, since it removes the need for the Item interface to be created/malloc'd, and it allows more contiguous storage of values within the BTree's nodes themselves.

As expected, all G (generic) ops are notably faster than their associated Int Item ops, because of the removal of interface overhead. Untested here, but they should also be far less memory-fragmented, since values are stored within the node item arrays rather than pointed to by interfaces within those arrays.

BenchmarkInsertG-4 3014830 355.2 ns/op BenchmarkInsert-4 2296561 639.9 ns/op

BenchmarkSeekG-4 5478997 218.6 ns/op BenchmarkSeek-4 2880756 396.0 ns/op

BenchmarkDeleteInsertG-4 1720306 653.0 ns/op BenchmarkDeleteInsert-4 1304244 1131 ns/op

BenchmarkDeleteInsertCloneOnceG-4 1834026 647.3 ns/op BenchmarkDeleteInsertCloneOnce-4 1293346 932.3 ns/op

BenchmarkDeleteInsertCloneEachTimeG-4 545394 2878 ns/op BenchmarkDeleteInsertCloneEachTime-4 353428 4173 ns/op

BenchmarkDeleteG-4 3223182 366.9 ns/op BenchmarkDelete-4 1979107 600.4 ns/op

BenchmarkGetG-4 4265853 293.2 ns/op BenchmarkGet-4 3091616 431.8 ns/op

BenchmarkGetCloneEachTimeG-4 1990131 693.3 ns/op BenchmarkGetCloneEachTime-4 1705196 610.0 ns/op

BenchmarkAscendG-4 14222 83445 ns/op BenchmarkAscend-4 12345 94486 ns/op

BenchmarkDescendG-4 14335 80779 ns/op BenchmarkDescend-4 11686 98627 ns/op

BenchmarkAscendRangeG-4 8803 134915 ns/op BenchmarkAscendRange-4 5586 209962 ns/op

BenchmarkDescendRangeG-4 6590 182179 ns/op BenchmarkDescendRange-4 3591 323628 ns/op

BenchmarkAscendGreaterOrEqualG-4 12984 92049 ns/op BenchmarkAscendGreaterOrEqual-4 9915 121264 ns/op

BenchmarkDescendLessOrEqualG-4 7876 152083 ns/op BenchmarkDescendLessOrEqual-4 4945 231001 ns/op

BenchmarkDeleteAndRestoreG/CopyBigFreeList-4 100 10167381 ns/op 75390 B/op 15 allocs/op BenchmarkDeleteAndRestore/CopyBigFreeList-4 73 15137467 ns/op 141924 B/op 19 allocs/op

BenchmarkDeleteAndRestoreG/Copy-4 104 12522643 ns/op 235632 B/op 1195 allocs/op BenchmarkDeleteAndRestore/Copy-4 80 16853292 ns/op 433896 B/op 1151 allocs/op

BenchmarkDeleteAndRestoreG/ClearBigFreelist-4 207 5434805 ns/op 670 B/op 4 allocs/op BenchmarkDeleteAndRestore/ClearBigFreelist-4 147 7954534 ns/op 980 B/op 6 allocs/op

BenchmarkDeleteAndRestoreG/Clear-4 198 6781077 ns/op 148424 B/op 1086 allocs/op BenchmarkDeleteAndRestore/Clear-4 134 8639437 ns/op 268872 B/op 1041 allocs/op

[google-cla[bot]]

Thanks for your pull request! It looks like this may be your first contribution to a Google open source project. Before we can look at your pull request, you'll need to sign a Contributor License Agreement (CLA).

View this failed invocation of the CLA check for more information.

For the most up to date status, view the checks section at the bottom of the pull request.

[gconnell]

Alternative fix to #41 that doesn't introduce a /v2/.

[gconnell]

Moving forward with this approach, but let me know if it causes any issues!