rust-lang/rust — pull request #18028 by gereeter (2014-10-14 10:02:23+00:00)
Title: Slimmify BTree by replacing the three Vecs in Node with a manually alloc...

...ated buffer.

Before:

test btree::map::bench::find_rand_100 ... bench: 29 ns/iter (+/- 2)
test btree::map::bench::find_rand_10_000 ... bench: 83 ns/iter (+/- 6)
test btree::map::bench::find_seq_100 ... bench: 30 ns/iter (+/- 1)
test btree::map::bench::find_seq_10_000 ... bench: 50 ns/iter (+/- 3)
test btree::map::bench::insert_rand_100 ... bench: 186 ns/iter (+/- 30)
test btree::map::bench::insert_rand_10_000 ... bench: 377 ns/iter (+/- 8)
test btree::map::bench::insert_seq_100 ... bench: 299 ns/iter (+/- 10)
test btree::map::bench::insert_seq_10_000 ... bench: 368 ns/iter (+/- 12)
test btree::map::bench::iter_1000 ... bench: 20956 ns/iter (+/- 479)
test btree::map::bench::iter_100000 ... bench: 2060899 ns/iter (+/- 44325)
test btree::map::bench::iter_20 ... bench: 560 ns/iter (+/- 63)

After:

test btree::map::bench::find_rand_100 ... bench: 28 ns/iter (+/- 2)
test btree::map::bench::find_rand_10_000 ... bench: 74 ns/iter (+/- 3)
test btree::map::bench::find_seq_100 ... bench: 31 ns/iter (+/- 0)
test btree::map::bench::find_seq_10_000 ... bench: 46 ns/iter (+/- 0)
test btree::map::bench::insert_rand_100 ... bench: 141 ns/iter (+/- 1)
test btree::map::bench::insert_rand_10_000 ... bench: 273 ns/iter (+/- 12)
test btree::map::bench::insert_seq_100 ... bench: 255 ns/iter (+/- 17)
test btree::map::bench::insert_seq_10_000 ... bench: 340 ns/iter (+/- 3)
test btree::map::bench::iter_1000 ... bench: 21193 ns/iter (+/- 1958)
test btree::map::bench::iter_100000 ... bench: 2203599 ns/iter (+/- 100491)
test btree::map::bench::iter_20 ... bench: 614 ns/iter (+/- 110)

This code could probably be a fair bit cleaner, but it works.