3 ms·
The Rust BTreeMap implementation is an example of this as well. It does a linear scan through the nodes instead of a binary search because it's actually faster
by chlorion 3y ago
The Rust BTreeMap implementation is an example of this as well. It does a linear scan through the nodes instead of a binary search because it's actually faster in this case!
https://doc.rust-lang.org/std/collections/struct.BTreeMap.html https://doc.rust-lang.org/std/collections/struct.BTreeMap.ht...
- fulafel 3y agoInteresting. But the doc doesn't go as far as to say it's faster, just fast - any measurements for eg string keys?
- chlorion 3y agoI can't seem to find any benchmarks for this but Gankra did a long write up about Rust's btree implementation! I did not read this entire thing so it's very possible it contains a benchmark somewhere but I couldn't find any when doing a quick skim. https://faultlore.com/blah/rust-btree-case/ https://faultlore.com/blah/rust-btree-case/
- pkulak 3y agoDid we both just watch the latest Crust of Rust, or did you just know that? If the latter, I’m impressed!
- chlorion 3y ago>Did we both just watch the latest Crust of Rust Yes that's exactly how I knew about this!