From b6edc59413f79016a1063c2ec6bc05516bc99cb6 Mon Sep 17 00:00:00 2001 From: Alexis Beingessner Date: Tue, 16 Sep 2014 10:49:26 -0400 Subject: complete btree rewrite Replaces BTree with BTreeMap and BTreeSet, which are completely new implementations. BTreeMap's internal Node representation is particularly inefficient at the moment to make this first implementation easy to reason about and fairly safe. Both collections are also currently missing some of the tooling specific to sorted collections, which is planned as future work pending reform of these APIs. General implementation issues are discussed with TODOs internally Perf results on x86_64 Linux: test treemap::bench::find_rand_100 ... bench: 76 ns/iter (+/- 4) test treemap::bench::find_rand_10_000 ... bench: 163 ns/iter (+/- 6) test treemap::bench::find_seq_100 ... bench: 77 ns/iter (+/- 3) test treemap::bench::find_seq_10_000 ... bench: 115 ns/iter (+/- 1) test treemap::bench::insert_rand_100 ... bench: 111 ns/iter (+/- 1) test treemap::bench::insert_rand_10_000 ... bench: 996 ns/iter (+/- 18) test treemap::bench::insert_seq_100 ... bench: 486 ns/iter (+/- 20) test treemap::bench::insert_seq_10_000 ... bench: 800 ns/iter (+/- 15) test btree::map::bench::find_rand_100 ... bench: 74 ns/iter (+/- 4) test btree::map::bench::find_rand_10_000 ... bench: 153 ns/iter (+/- 5) test btree::map::bench::find_seq_100 ... bench: 82 ns/iter (+/- 1) test btree::map::bench::find_seq_10_000 ... bench: 108 ns/iter (+/- 0) test btree::map::bench::insert_rand_100 ... bench: 220 ns/iter (+/- 1) test btree::map::bench::insert_rand_10_000 ... bench: 620 ns/iter (+/- 16) test btree::map::bench::insert_seq_100 ... bench: 411 ns/iter (+/- 12) test btree::map::bench::insert_seq_10_000 ... bench: 534 ns/iter (+/- 14) BTreeMap still has a lot of room for optimization, but it's already beating out TreeMap on most access patterns. [breaking-change] --- src/libstd/collections/mod.rs | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/libstd') diff --git a/src/libstd/collections/mod.rs b/src/libstd/collections/mod.rs index d98d490a84b..324c0295971 100644 --- a/src/libstd/collections/mod.rs +++ b/src/libstd/collections/mod.rs @@ -16,7 +16,7 @@ pub use core_collections::{Collection, Mutable, Map, MutableMap}; pub use core_collections::{Set, MutableSet, Deque, MutableSeq}; -pub use core_collections::{Bitv, BitvSet, BTree, DList, EnumSet}; +pub use core_collections::{Bitv, BitvSet, BTreeMap, BTreeSet, DList, EnumSet}; pub use core_collections::{PriorityQueue, RingBuf, SmallIntMap}; pub use core_collections::{TreeMap, TreeSet, TrieMap, TrieSet}; pub use core_collections::{bitv, btree, dlist, enum_set}; -- cgit 1.4.1-3-g733a5