Hacker News Reader

Comment by nice_byte | Hacker News Reader

Small question, I don't really see how switching to unordered_map solves the locality problem that the author mentioned... unordered_map most likely uses chaining, and even if we were allocate a continuous block of memory for each bucket (as opposed to having a linked list), we'd still have a locality issue.

View on HN

I think C++'s built in unordered_map has to use chaining due to restrictions on iterators mandated for standard library containers, which is a drag. You've still got to roll your own open addressed container. :( This comes up in one of Chandler Carruth's talks [1].

[1] https://www.youtube.com/watch?v=fHNmRkzxHWs

Yep, that's exactly what I did (because of the same concerns) in one of my projects, which is why I was initially surprised to see them recommend unordered_map. But, as the other commenter pointed out, unordered_map has way less "hops" and thus provides a significant improvement over a search tree in terms of locality.

Collisions should not be common enough to have chains (or skip patterns) of 20 elements, in an (unordered) hash map. It should be more like, one jump to the hashed index, and then maybe another jump or two if there is a collision. That's significantly fewer jumps in memory than for a balanced ordered binary tree.

Thanks, that makes sense.

Well I think you're overthinking that right now, I think this is "traversing a tree" O(log n) vs a "hash table lookup" O(1)

But the main thing is that the hash table lookup mostly is in the same memory area until you try to get the actual value out of it. Also the author mentions as a side note the problem with them "(though they do have their drawbacks in the worst-case scenarios, so you need to be careful)"

A tree access is ~log n memory lookups and every one of them can miss cache. A hash map access is ~1 memory lookup, which can miss cache. Even when you have cache collisions and need to do a linear search in a bucket it's not going to cause additional cache misses if the bucket is allocated as an array.

Reply on news.ycombinator.com