4 ms·

Making the array a thousand times bigger (~5Gigabytes): #define ARRAY_SIZE 1234567890 #define ITERATIONS 10 still results in a 20% speed advantage for Knu

Making the array a thousand times bigger (~5Gigabytes): #define ARRAY_SIZE 1234567890 #define ITERATIONS 10 still results in a 20% speed advantage for Knuth: naive search average: 790441856.00 ns knuth search average: 627306112.00 ns It would be great to see if these results hold up on the most recent CPUs (compiled with -O3, of course). By the way, the results varied a bit between runs, but always had about the same ratio.

lisper 7y 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 7y ago
  First 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 7y ago
    Yeah, 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
pantalaimon 7y ago
> It would be great to see if these results hold up on the most recent CPUs (compiled with -O3, of course). On a Xeon Gold 6146: -O0 naive search average: 1289837.88 ns knuth search average: 1304139.38 ns -O3 naive search average: 272361.28 ns knuth search average: 270700.78 ns

lisper 7y 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 7y ago
First 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 7y ago
  Yeah, 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

pantalaimon 7y ago

> It would be great to see if these results hold up on the most recent CPUs (compiled with -O3, of course). On a Xeon Gold 6146: -O0 naive search average: 1289837.88 ns knuth search average: 1304139.38 ns -O3 naive search average: 272361.28 ns knuth search average: 270700.78 ns