4 ms·

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 symbo

• 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.
  • malkia 16y ago
    Cache misses are expensive yes. And when you have an interned string to be searched on - you always have to calculate it's hash-sum as key before looking for it in a hash-table, and you don't have to do that for a linear search (it's an interned symbol that's why). This means you might have to read one, two or more cache lines (if the cache line is 64, then it's strlen(yourstring)/8) You can't use the pointer itself as a key - either the distribution is not good, or the language would not allow you (you can't do it in Common Lisp which Erik Naggum was talking about). That calculation of the key might read one two or more cache lines - depending on how big the string is. Off course it would be better for the hash-table the smaller key is, and worse if not. And then, there are still CPUs without cache still in popular use - for example PS3's CELL SPE (spu). And one more thing - in the linear search you always read the same cache lines, while in the hash-table you have to read everytime different memory (the strings to be searched upon). But in both cases, there are instructions to prefetch, but again - you would be wasting less cache with the assoc table if you are looking a lot (e.g. you'll warm always from the begining and keep that in the L1), while for hash-table you would warm all the keys. It's really hard to compare, but I hope you get the picture.