Naggum Nugget
groups.google.com
groups.google.com
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.
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."
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.
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.
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.
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.
I believe the above to be an accurate summary.
The confusion stems from the language you used in your comment, which made it seem like you were claiming a lot more than you actually turned out to be:
"I have yet to see anyone ... actually do the experiment to determine where the actual breakeven point is. Hint: it's less than 5000."
The fact of the matter is that hash tables are faster than ALists in all but the most trivial of cases. Theory predicts it, and an experiment that takes all of two minutes to do confirms it. Everything else is quibbling over angels on the head of a pin.
I'm struggling to think of a non-trolling motivation that explains this behavior.
This is giving me comp.lang.lisp flashbacks.
On Clozure Common Lisp the breakeven point for the average case is 20 items (10 for the worst case).
Your condescending tone would at least not be completely unwarranted if you weren't utterly wrong.
Yes.
> and came up with a universal point
No. I got one data point.
Since there seems to be so much demand for it, I compared ALists and hash tables on Clozure Common Lisp. The breakeven point there was 20 items.
whatever points he's making, it feels like listening to bill o'reilly make them.
For small N, finding something in an association list can be faster than finding the same thing in a hash table.
Naggum also could have run some quick bench marks and figured out at what size N hash tables become a better choice (depending on the nature of the keys, etc. etc.), in less time than he spent berating the intelligence of the questioner.
When I was working through the book (and I still am to some extent), it was basically beat into my brain that some algorithms with worse performance could perform better than faster algorithms for a small enough n.
Only in edge cases like looking up a long string in an alist consisting of one short string he's right.
Is it really that hard to say, "Complex algorithms have higher constant factors, so for small values of N, 'naive' ones can still be faster. When in doubt, measure." without chewing somebody out?
It's easy to deliberately overlook rudeness, but it still unconsciously colors a person's responses and thoughts, which could have a negative impact on the message.
From the wikipedia hash table article (http://en.wikipedia.org/wiki/Hash_table#Separate_chaining_wi...):
Instead of a list, one can use any other data structure that supports the required operations. By using a self-balancing tree, for example, the theoretical worst-case time of a hash table can be brought down to O(log n) rather than O(n). However, this approach is only worth the trouble and extra memory cost if long delays must be avoided at all costs (e.g. in a real-time application), or if one expects to have many entries hashed to the same slot (e.g. if one expects extremely non-uniform or even malicious key distributions).
I miss that guy.