rust-lang/rust — pull request #19796 by cgaebel (2014-12-13 01:15:51+00:00)
Title: Add intrusive iterators to BTree.

Unfortunately, tree structures are intrinsically slower to
iterate over externally than internally. This can be
demonstrated in benchmarks. In fact, it's so bad at external
iteration that calling `.find` on each element in succession
is currently slightly faster.

This patch implements a faster intrusive way to iterate over
BTrees. This is about 5x faster, but you lose all iterator
composition infrastructure. This is a tradeoff that is
acceptable in some applications.

Relevant benchmarks:

```
test btree::map::bench::intrusive_iter_1000 ... bench: 2658 ns/iter (+/- 602)
test btree::map::bench::intrusive_iter_100000 ... bench: 346353 ns/iter (+/- 189565)
test btree::map::bench::intrusive_iter_20 ... bench: 55 ns/iter (+/- 16)
test btree::map::bench::iter_1000 ... bench: 15892 ns/iter (+/- 3717)
test btree::map::bench::iter_100000 ... bench: 1383714 ns/iter (+/- 444706)
test btree::map::bench::iter_20 ... bench: 366 ns/iter (+/- 104)
```

r? @Gankro @huonw

@aturon how does this fit into 1.0 stabilization plans. Is
marking this as #[experimental] enough?