3 ms·
"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 consi
by 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."