Hacker News Reader

Comment by ot | Hacker News Reader

You'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)

View on HN

It turns out `collections::HashMap` runs about 6~7% faster than BTreeMap. I will update the article to include results of both data structures.

Also seems like you could benefit from the entry() api (available on both BTreeMap and HashMap):

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); }
  }

Good 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...

Reply on news.ycombinator.com