That should explain it. I’ve removed the line as it’s no more mysterious...
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); }
}