rust-lang/rust — pull request #16906 by Gankro (2014-08-31 20:01:08+00:00)
Title: WIP safe and sane B-Tree rewrite

Total minimal rewrite of BTree to not use copy/clone at all, and to generally avoid unnecessary mutations. I have not yet implemented the "miscellaneous" collection things like iterators, Ord, Eq, Hash, etc as I want to nail the core stuff down first.

There is one substantial drawback to my implementation: it doesn't allow configuration of `B`. The benefit of this is that the nodes are made of `[T,..n]`'s instead of Vecs, putting more data contiguously and reducing the amount of indirection. I have done this under @aturon's recommendation that it would be better to write a BTree implementation that would benefit from the future possibility of generic integer arguments being available (I am not saying they will).

One consequence of this is that I currently store the Keys/Values in Options, because it's not clear to me if there's a safe way to work with partially intialized arrays, or to tell Rust to "forget" some or all of the array and not try to run destructors on the elements. I would *love* if someone could show me how to do that.

In addition, right now I do a *lot* of indexing which could probably be replaced with iterators to avoid bounds checks. I'm also not leveraging `copy` instrinsics to bulk shift the elements around. This first draft is emphasizing correctness and safety over performance, but in a way that's easily upgradable. I hope to have the time to start tuning the implementation in the coming days,

The actual code is literally 25% just comments describing the fairly complex logic of a BTree. I've tried to chunk things out into "grokable" functions where possible so that everyone understands what's going on.

Finally, as a quick sanity check, I ran treemap's bench suite on btree (`make check-collections -j8 PLEASE_BENCH=1`):
```
test treemap::bench::find_rand_100 ... bench: 74 ns/iter (+/- 5)
test treemap::bench::find_rand_10_000 ... bench: 164 ns/iter (+/- 3)
test treemap::bench::find_seq_100 ... bench: 76 ns/iter (+/- 2)
test treemap::bench::find_seq_10_000 ... bench: 115 ns/iter (+/- 2)
test treemap::bench::insert_rand_100 ... bench: 126 ns/iter (+/- 2)
test treemap::bench::insert_rand_10_000 ... bench: 1025 ns/iter (+/- 16)
test treemap::bench::insert_seq_100 ... bench: 507 ns/iter (+/- 19)
test treemap::bench::insert_seq_10_000 ... bench: 834 ns/iter (+/- 15)

test btree::bench::find_rand_100 ... bench: 86 ns/iter (+/- 4)
test btree::bench::find_rand_10_000 ... bench: 165 ns/iter (+/- 2)
test btree::bench::find_seq_100 ... bench: 86 ns/iter (+/- 2)
test btree::bench::find_seq_10_000 ... bench: 117 ns/iter (+/- 1)
test btree::bench::insert_rand_100 ... bench: 270 ns/iter (+/- 10)
test btree::bench::insert_rand_10_000 ... bench: 598 ns/iter (+/- 18)
test btree::bench::insert_seq_100 ... bench: 386 ns/iter (+/- 8)
test btree::bench::insert_seq_10_000 ... bench: 459 ns/iter (+/- 4)
```

As you can see, my implementation is generally competitive with treemap, and is substantially faster during large insertion workloads. And as discussed above, I haven't even begun to tune it; my choice of B is largely arbitrary!

If anyone is a low-level optimizing expert, or just knows good BTree design/tuning, I'd love to get any feedback on this work. If anyone has any other ideas or questions, I'm more than happy to discuss this with you!