rust-lang/rust — pull request #17801 by Gankro (2014-10-05 17:49:28+00:00)
Title: Doc BTree better, #[inline] everything, and add some iteration benches

I previously avoided `#[inline]`ing anything assuming someone would come in and explain to me where this would be appropriate. Apparently no one *really* knows, so I'll just go the opposite way an inline everything assuming someone will come in and yell at me that such-and-such shouldn't be `#[inline]`.

==================

For posterity, iteration comparisons:

```
test btree::map::bench::iter_20 ... bench: 971 ns/iter (+/- 30)
test btree::map::bench::iter_1000 ... bench: 29445 ns/iter (+/- 480)
test btree::map::bench::iter_100000 ... bench: 2929035 ns/iter (+/- 21551)

test treemap::bench::iter_20 ... bench: 530 ns/iter (+/- 66)
test treemap::bench::iter_1000 ... bench: 26287 ns/iter (+/- 825)
test treemap::bench::iter_100000 ... bench: 7650084 ns/iter (+/- 356711)

test trie::bench_map::iter_20 ... bench: 646 ns/iter (+/- 265)
test trie::bench_map::iter_1000 ... bench: 43556 ns/iter (+/- 5014)
test trie::bench_map::iter_100000 ... bench: 12988002 ns/iter (+/- 139676)
```

As you can see `btree` "scales" much better than `treemap`. `triemap` scales quite poorly.

Note that *completely* different results are given if the elements are inserted in order from the range [0, size]. In particular, TrieMap *completely* dominates in the sorted case. This suggests adding benches for both might be worthwhile. However unsorted is *probably* the more "normal" case, so I consider this "good enough" for now.

===========

Effects of inlining (no iter numbers because of changed bench after taking baseline results):

test treemap::bench::find_rand_100 ... bench: 76 ns/iter (+/- 4)
test treemap::bench::find_rand_10_000 ... bench: 163 ns/iter (+/- 5)
test treemap::bench::find_seq_100 ... bench: 76 ns/iter (+/- 2)
test treemap::bench::find_seq_10_000 ... bench: 115 ns/iter (+/- 1)
test treemap::bench::insert_rand_100 ... bench: 113 ns/iter (+/- 7)
test treemap::bench::insert_rand_10_000 ... bench: 987 ns/iter (+/- 22)
test treemap::bench::insert_seq_100 ... bench: 511 ns/iter (+/- 23)
test treemap::bench::insert_seq_10_000 ... bench: 851 ns/iter (+/- 20)

## Before
test btree::map::bench::find_rand_100 ... bench: 71 ns/iter (+/- 5)
test btree::map::bench::find_rand_10_000 ... bench: 152 ns/iter (+/- 4)
test btree::map::bench::find_seq_100 ... bench: 80 ns/iter (+/- 2)
test btree::map::bench::find_seq_10_000 ... bench: 104 ns/iter (+/- 1)
test btree::map::bench::insert_rand_100 ... bench: 250 ns/iter (+/- 1)
test btree::map::bench::insert_rand_10_000 ... bench: 667 ns/iter (+/- 5)
test btree::map::bench::insert_seq_100 ... bench: 455 ns/iter (+/- 4)
test btree::map::bench::insert_seq_10_000 ... bench: 600 ns/iter (+/- 11)

## After
test btree::map::bench::find_rand_100 ... bench: 74 ns/iter (+/- 4)
test btree::map::bench::find_rand_10_000 ... bench: 154 ns/iter (+/- 5)
test btree::map::bench::find_seq_100 ... bench: 83 ns/iter (+/- 2)
test btree::map::bench::find_seq_10_000 ... bench: 108 ns/iter (+/- 1)
test btree::map::bench::insert_rand_100 ... bench: 245 ns/iter (+/- 4)
test btree::map::bench::insert_rand_10_000 ... bench: 624 ns/iter (+/- 13)
test btree::map::bench::insert_seq_100 ... bench: 419 ns/iter (+/- 10)
test btree::map::bench::insert_seq_10_000 ... bench: 542 ns/iter (+/- 4)

Significant insertion gains, no significant search change. Actual users should see huge benefits due to cross-crate effects of `#[inline]`.