]> git.lizzy.rs Git - rust.git/commit
auto merge of #11497 : huonw/rust/trie-internal-iter, r=alexcrichton
authorbors <bors@rust-lang.org>
Sat, 18 Jan 2014 01:56:41 +0000 (17:56 -0800)
committerbors <bors@rust-lang.org>
Sat, 18 Jan 2014 01:56:41 +0000 (17:56 -0800)
commitf4498c71e21308f6657d0150d5f473835e4b436f
tree056558abc445547eae39e2aa143a92f131138f03
parent2ff358c062e9f4c31e0e34d0cd9179a9af363867
parent0148055a56953a747362acb78efc8f0865fccc54
auto merge of #11497 : huonw/rust/trie-internal-iter, r=alexcrichton

This stores the stack of iterators inline (we have a maximum depth with
`uint` keys), and then uses direct pointer offsetting to manipulate it,
in a blazing fast way:

Before:

    bench_iter_large          ... bench:     43187 ns/iter (+/- 3082)
    bench_iter_small          ... bench:       618 ns/iter (+/- 288)

After:

    bench_iter_large          ... bench:     13497 ns/iter (+/- 1575)
    bench_iter_small          ... bench:       220 ns/iter (+/- 91)

Also, removes `.each_{key,value}_reverse` as an offering to
placate the gods of external iterators for my heinous sin of
attempting to add new internal ones (in a previous version of this
PR).