Repository navigation
Generic approach #41
Description
With support for generics, we can replace interfaces with generic types.
The use of generics avoids variables escaping to heap when calling the B-tree functions yielding 20-30% improvement.
Below are some comparisons between benchmarks (taken from original repository) done with benchstat:
name old time/op new time/op delta
Insert-8 121ns ± 1% 89ns ± 1% -27.04% (p=0.008 n=5+5)
Seek-8 115ns ± 1% 78ns ± 0% -31.56% (p=0.008 n=5+5)
DeleteInsert-8 248ns ± 0% 185ns ± 1% -25.51% (p=0.008 n=5+5)
DeleteInsertCloneEachTime-8 1.10µs ± 5% 0.61µs ± 1% -44.45% (p=0.008 n=5+5)
Delete-8 138ns ± 1% 101ns ± 1% -26.62% (p=0.008 n=5+5)
Get-8 102ns ± 1% 71ns ± 0% -30.46% (p=0.008 n=5+5)
Ascend-8 40.2µs ± 1% 31.7µs ± 0% -21.18% (p=0.008 n=5+5)
Descend-8 39.3µs ± 1% 30.7µs ± 1% -21.91% (p=0.008 n=5+5)
AscendRange-8 72.3µs ± 1% 57.6µs ± 1% -20.39% (p=0.008 n=5+5)
DescendRange-8 92.9µs ± 1% 77.6µs ± 1% -16.45% (p=0.008 n=5+5)
name old alloc/op new alloc/op delta
Insert-8 35.6B ± 4% 18.4B ± 3% -48.31% (p=0.008 n=5+5)
Seek-8 7.00B ± 0% 0.00B -100.00% (p=0.008 n=5+5)
DeleteInsert-8 0.00B 0.00B ~ (all equal)
DeleteInsertCloneEachTime-8 2.98kB ± 5% 1.91kB ± 1% -36.16% (p=0.008 n=5+5)
Delete-8 0.00B 0.00B ~ (all equal)
Get-8 0.00B 0.00B ~ (all equal)
Ascend-8 0.00B 0.00B ~ (all equal)
Descend-8 0.00B 0.00B ~ (all equal)
AscendRange-8 0.00B 0.00B ~ (all equal)
DescendRange-8 0.00B 0.00B ~ (all equal)
name old allocs/op new allocs/op delta
Insert-8 0.00 0.00 ~ (all equal)
Seek-8 0.00 0.00 ~ (all equal)
DeleteInsert-8 0.00 0.00 ~ (all equal)
DeleteInsertCloneEachTime-8 11.0 ± 0% 11.0 ± 0% ~ (all equal)
Delete-8 0.00 0.00 ~ (all equal)
Get-8 0.00 0.00 ~ (all equal)
Ascend-8 0.00 0.00 ~ (all equal)
Descend-8 0.00 0.00 ~ (all equal)
AscendRange-8 0.00 0.00 ~ (all equal)
DescendRange-8 0.00 0.00 ~ (all equal)
In case of plain Insert Benchmark, the results are even better:
name old time/op new time/op delta
Insert-8 200ns ± 2% 137ns ± 1% -31.20% (p=0.008 n=5+5)
name old alloc/op new alloc/op delta
Insert-8 60.0B ± 0% 27.0B ± 0% -55.00% (p=0.008 n=5+5)
name old allocs/op new allocs/op delta
Insert-8 1.00 ± 0% 0.00 -100.00% (p=0.008 n=5+5)
func BenchmarkInsert(b *testing.B) {
b.StopTimer()
tr := btree.New(32)
b.StartTimer()
for i := 0; i < b.N; i++ {
tr.ReplaceOrInsert(btree.Int(i))
}
}Unfortunately the functions that return nil do not work ex. func (t *BTree) Delete(item Item) Item.
We can't simply return zero value for generic type, because it's still a valid value, so I decided to change the API, so that:
func (t *BTree[T]) Delete(item T) (T, bool) { ... }we also return bool which indicates whether anything was really deleted.
Of course, we can implement B-tree on pointers to generic types, but it harms performance in many cases (like having B-tree for numeric types).
Changes of API destroy backward compatibility, but because of reasons mentioned above, I believe that this approach is justified.
Here is link to forked repository with generic B-tree:
https://github.com/Michal-Leszczynski/btree
How do you suggest we further proceed with this effort.
Activity
SaveTheRbtz commentedon Apr 16, 2022
Came here with exactly the same proposal (and similar benchmarks). Maybe it is time to create a
v2release?mmatczuk commentedon Apr 27, 2022
Perf analysis https://www.scylladb.com/2022/04/27/shaving-40-off-googles-b-tree-implementation-with-go-generics/
mmatczuk commentedon Apr 29, 2022
@Michal-Leszczynski please send a PR. Merging this would require go mod v2.
In the context of performance you can consider sending a followup PR that replaces slice with array in
nodeitems.gconnell commentedon Jun 4, 2022
Fixed by #45