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).
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.
Not criticizing, just curious.
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.I’ve updated the code and article with HashMap. It runs about 6~7% faster than BTreeMap.
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)
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 {
..
}
match map.entry(word) {
Occupied(mut view) => { *view.get_mut() += 1; }
Vacant(view) => { view.insert(1); }
}