5 ms·

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 chaini

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.

ploxiln 10y ago
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.
- nice_byte 10y ago
  Thanks, that makes sense.
santaclaus 10y ago
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 https://www.youtube.com/watch?v=fHNmRkzxHWs
- nice_byte 10y ago
  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.
recentdarkness 10y ago
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)"
pandaman 10y ago
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.

ploxiln 10y ago

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.

nice_byte 10y ago
Thanks, that makes sense.

santaclaus 10y ago

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 https://www.youtube.com/watch?v=fHNmRkzxHWs

nice_byte 10y ago
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.

recentdarkness 10y ago

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)"

pandaman 10y ago

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.