2 ms·
Wow, that is so weird. I would have expected this to be entirely dominated by memory latency. I'm also scratching my head trying to figure out why this only s
by lisper 8y ago
Wow, that is so weird. I would have expected this to be entirely dominated by memory latency.
I'm also scratching my head trying to figure out why this only shows up with -O3. I would have expected the exact opposite, i.e. a bigger difference on lower optimization settings.
- pantalaimon 8y agoFirst I thought this was because in drfuchs' version both the array and the key are completely random, so it's not likely the key is found before the end of the array is reached. This is of course the more realistic scenario, whereas my test was only testing the worst case where they key is not part of the array. However, when I modify it to not include they key in the search array (`myarray[i] = random() & 0x7fffffff;`, `key = 0xffffffff;`) I see the same behavior: -O0, i5-2500K naive search average: 1773653.88 ns knuth search average: 1865263.62 ns -O3, i5-2500K naive search average: 590244.25 ns knuth search average: 345119.06 ns
- drfuchs 8y agoYeah, I was careless on not preserving the nice feature of your code that kept there from ever being a match, figuring that the chances were low of a hit; but of course that assumption went out the window when the array got way bigger. After posting, I noticed the issue, so I made a similar change to yours, and the results didn't change. I do suggest that you change the line that sets 'key' to not make it known at compile-time, to avoid unrealistic optimizations, thus: const int key = random() | 0x80000000; // ensure no match