5 ms·
> It’s mysterious that Rust’s release version with -i ran slightly faster, though. That's actually not surprising: a large fraction of time is spent in the map
by ot 12y ago
> It’s mysterious that Rust’s release version with -i ran slightly faster, though.
That's actually not surprising: a large fraction of time is spent in the map lookup, which in Rust is implemented as a B-tree, thus lookup time is (mildly) dependent on the map size. If keys are lowercased before inserting them, the map ends up having fewer elements.
The Nim version uses instead hash tables, whose lookup time is near-constant (that is, excluding memory hierarchy effects).
- arthurtw 12y agoThat should explain it. I’ve removed the line as it’s no more mysterious...
- ot 12y agoYou're still comparing two different data structures. Is there a good hash table in Rust? If you use that instead of the B-tree, I would expect it to be at least as fast as Nim. B-trees are especially bad for string keys, because comparisons are expensive. EDIT: From Rust docs: "Currently, our implementation simply performs naive linear search. This provides excellent performance on small nodes of elements which are cheap to compare". (emphasis mine)
- arthurtw 12y agoIt turns out `collections::HashMap` runs about 6~7% faster than BTreeMap. I will update the article to include results of both data structures.
- tikue_ 12y agoAlso seems like you could benefit from the entry() api (available on both BTreeMap and HashMap): http://doc.rust-lang.org/std/collections/struct.BTreeMap.html#method.entry http://doc.rust-lang.org/std/collections/struct.BTreeMap.htm... I think the example used in the docs is your exact use case. This bit: let found = match map.get_mut(..) { .. } if !found { .. } can be replaced with match map.entry(word) { Occupied(mut view) => { *view.get_mut() += 1; } Vacant(view) => { view.insert(1); } }
- arthurtw 12y agoGood point! I’ve updated the article accordingly. I learned the Entry thing a few months ago, but Rust’s BTreeMap did not support the entry API at that time, so my code did not use it. Then I totally forgot about it when writing this blog...
- AYBABTME 12y agoThis seems an odd choice to me (default to B-Tree instead of hash map). I'd expect a sorted map to be a special case, not a general one. Do you happen to know the rationale? Not criticizing, just curious.
- euid 12y agoIt's a poor choice on the author's part http://doc.rust-lang.org/std/collections/ http://doc.rust-lang.org/std/collections/ Use a HashMap when: - You want to associate arbitrary keys with an arbitrary value. - You want a cache. - You want a map, with no extra functionality. Use a BTreeMap when: - You're interested in what the smallest or largest key-value pair is. - You want to find the largest or smallest key that is smaller or larger than something - You want to be able to get all of the entries in order on-demand. - You want a sorted map.
- arthurtw 12y agoI chose it because I wanted to learn Rust by implementing my own BTreeMap struct. I admit it’s not a good choice performance-wise, and made the comparison with Nim less meaningful. I’ve updated the code and article with HashMap. It runs about 6~7% faster than BTreeMap.
- dbaupp 12y agoSlightly confusingly, the authors BTreeMap just appears to be a binary tree, while the standard library BTreeMap is a B-tree: http://en.wikipedia.org/wiki/B-tree http://en.wikipedia.org/wiki/B-tree
- dbaupp 12y ago> That's actually not surprising: a large fraction of time is spent in the map lookup This was not the case in my benchmarks: the Rust spent 60% of its time doing regex matches, 25% allocating strings and less than 6% manipulating the map.