commit bd9baa174297fbdb0fa1168baa43b1a14fe8e2c5
author Graeme Connell <gsconnell@gmail.com> Sat May 28 18:24:39 2022 -0600
committer Graeme Connell <gsconnell@gmail.com> Sun May 29 15:47:30 2022 -0600
tree 01d090d91cb9db1a971ef5d825a4693bf6c98c4d
parent ac7cc57f11e692c57831c3d9bcffb4b7a649b738

Create a generic BTreeG for Go 1.18 and beyond.

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