5 ms·

True enough in 1999, and all but completely false now. For a competently implemented hash map with integer keys, hash tables start beating linear search somwher

by kmavm 16y ago

True enough in 1999, and all but completely false now. For a competently implemented hash map with integer keys, hash tables start beating linear search somwhere between n = 2 and n = 4. At n = 4, you start needing more than one cacheline to do your linear search. Since a worst-case cache miss is around 300 cycles on a Nehalem, a hash function is very, very cheap price for near-certainty that you'll only probe one line of the structure. All of which makes the table-pounding tone of this post kind of funny from 11 years' hindsight. The crossover point between linear search and hashing is a result of hardware and software parameters, not rhetorical force. He was right when he wrote what he wrote, and is wrong now. Future hardware/software changes might make him right again, but might not. I've indulged in the "real programmers vs. quiche eaters" rhetorical flourish at times, too; this post is a welcome reminder of its risks. It looks better to posterity if you do the experiments, state the results, and walk away.

hvs 16y ago
And based on the way he worded it, he would agree with you now. His point was that you need to apply both theory AND practice and not just blindly cite theory.
- jemfinch 16y ago
  There is an aspect to theory that's comforting, though. I'm sure I would sleep better at night knowing that my application was using an O(1) hash table as its map rather than an O(n) alist, even if the constant factors are higher. More hardware helps out constant factors; it doesn't do anything with quadratic algorithms.
  - deleted 16y ago
    [deleted]
bborud 16y ago
I don't see why this should look funny 11 years in hindsight. the important part is knowing rather than assuming. and you seem to assume quite a lot.
malkia 16y ago
You are ignoring the fact that you have to calculate the hash-key. With association tables, pointer comparison is enough if you are searching for interned symbols.
- jerf 16y ago
  No, he isn't; you entirely missed the point. Cache misses are expensive. Given that he specified integer keys, it's not a bad guess that a hash function will run fewer than 300 cycles on the specified Nehalem. If your association list has to run across three cachelines but your hash implementation runs across only two, the hash wins under these circumstances. Add a couple more cachelines and hashes start winning for more than just integer keys, too. Times have changed. Incidentally, the same may be true of some of the tree alternatives to hashes, too; used to be log n lookups would beat the O(1) lookups of hashes in many real-world scenarios because of the big constant on the O(1), but running across log n cachelines vs. O(1) cachelines (without a big constant) is a different story. The gulf between computation and memory continues to widen.
  - bborud 16y ago
    isn't this making a lot of assumptions with regard to memory locality and the organization of the hash table? for instance: what if the initial capacity isn't set properly for the hash table? what if the hash function isn't perfect and you end up with 16 buckets and 4 elements in one bucket and none in the other 15? (at which point you end up with what is essentially a list with lots of overhead). what if you start off by allocating a hash table that is too small and midway through populating it have to expand it? the more comments I read, the more Erik becomes right.
    - tptacek 16y ago
      Saying "what if your hash table becomes linearized" is not a fair argument when comparing linear search to hash lookup.
    - jerf 16y ago
      "isn't this making a lot of assumptions with regard to memory locality and the organization of the hash table?" Well, yeah. Always. But if you want to talk about how Erik is right, you probably want to go looking for an algorithm specifically designed for storing alists in a cache aware manner. Not sure what such a beast would look like, but something could probably be constructed and probably has been.
nkurz 16y ago
"Completely false" might be an overstatement. Do you have any test results you could point to? Or at least an exact specification of what the test would consist of? Particularly, are you measuring the first run from a luke warm start, guaranteed to be in memory but not in cache? Or might you be reading a page or two from disk, or making multiple passes while it still might be in some level of cache? Because I think the details are going to make a difference as to whether the break even point is n=4 or n=400, or maybe even n=4000. Like the decade-old Erik, my intuition is still that a brute force would be hard to beat for less than 100 integer keys to pointers if one is doing multiple passes through the list. But I'd love to bring my intuition up to date. Do you have one of these new-fangled 'competently implemented hash maps' that you could yield up so I can do some cycle counting? And is it fair if we throw in a few insertions and deletions just to make it realistic? For record, I completely agree on irrelevance of the cycles to compute the hash once one might be hitting main memory. But I also think it's worth noting that the size of your L3 cache may be comparable to the all the RAM that Erik had in his machine. I also think you might be underestimating the power of a modern prefetch unit, whether hinted or automatic. But I'll bow to data. As you said very well: "do the experiments, state the results, and walk away."

by kmavm 16y ago

hvs 16y ago

And based on the way he worded it, he would agree with you now. His point was that you need to apply both theory AND practice and not just blindly cite theory.

jemfinch 16y ago
There is an aspect to theory that's comforting, though. I'm sure I would sleep better at night knowing that my application was using an O(1) hash table as its map rather than an O(n) alist, even if the constant factors are higher. More hardware helps out constant factors; it doesn't do anything with quadratic algorithms.
- deleted 16y ago
  [deleted]

bborud 16y ago

I don't see why this should look funny 11 years in hindsight. the important part is knowing rather than assuming. and you seem to assume quite a lot.

malkia 16y ago

You are ignoring the fact that you have to calculate the hash-key. With association tables, pointer comparison is enough if you are searching for interned symbols.

jerf 16y ago
No, he isn't; you entirely missed the point. Cache misses are expensive. Given that he specified integer keys, it's not a bad guess that a hash function will run fewer than 300 cycles on the specified Nehalem. If your association list has to run across three cachelines but your hash implementation runs across only two, the hash wins under these circumstances. Add a couple more cachelines and hashes start winning for more than just integer keys, too. Times have changed. Incidentally, the same may be true of some of the tree alternatives to hashes, too; used to be log n lookups would beat the O(1) lookups of hashes in many real-world scenarios because of the big constant on the O(1), but running across log n cachelines vs. O(1) cachelines (without a big constant) is a different story. The gulf between computation and memory continues to widen.
- bborud 16y ago
  isn't this making a lot of assumptions with regard to memory locality and the organization of the hash table? for instance: what if the initial capacity isn't set properly for the hash table? what if the hash function isn't perfect and you end up with 16 buckets and 4 elements in one bucket and none in the other 15? (at which point you end up with what is essentially a list with lots of overhead). what if you start off by allocating a hash table that is too small and midway through populating it have to expand it? the more comments I read, the more Erik becomes right.
  - tptacek 16y ago
    Saying "what if your hash table becomes linearized" is not a fair argument when comparing linear search to hash lookup.
  - jerf 16y ago
    "isn't this making a lot of assumptions with regard to memory locality and the organization of the hash table?" Well, yeah. Always. But if you want to talk about how Erik is right, you probably want to go looking for an algorithm specifically designed for storing alists in a cache aware manner. Not sure what such a beast would look like, but something could probably be constructed and probably has been.

nkurz 16y ago

"Completely false" might be an overstatement. Do you have any test results you could point to? Or at least an exact specification of what the test would consist of? Particularly, are you measuring the first run from a luke warm start, guaranteed to be in memory but not in cache? Or might you be reading a page or two from disk, or making multiple passes while it still might be in some level of cache? Because I think the details are going to make a difference as to whether the break even point is n=4 or n=400, or maybe even n=4000. Like the decade-old Erik, my intuition is still that a brute force would be hard to beat for less than 100 integer keys to pointers if one is doing multiple passes through the list. But I'd love to bring my intuition up to date. Do you have one of these new-fangled 'competently implemented hash maps' that you could yield up so I can do some cycle counting? And is it fair if we throw in a few insertions and deletions just to make it realistic? For record, I completely agree on irrelevance of the cycles to compute the hash once one might be hitting main memory. But I also think it's worth noting that the size of your L3 cache may be comparable to the all the RAM that Erik had in his machine. I also think you might be underestimating the power of a modern prefetch unit, whether hinted or automatic. But I'll bow to data. As you said very well: "do the experiments, state the results, and walk away."