3 ms·

With some improvements to pantalaimon's test, and compiling with -O3, Knuth's scheme is 25% faster than the naive search on my 2012 MacBook Pro with latest deve

With some improvements to pantalaimon's test, and compiling with -O3, Knuth's scheme is 25% faster than the naive search on my 2012 MacBook Pro with latest developer tools (Apple LLVM version 10.0.1 (clang-1001.0.46.4)): naive search average: 779106.00 ns knuth search average: 593421.56 ns The sources are in http://codepad.org/G2SBmTnC http://codepad.org/G2SBmTnC and the changes were mostly removing constants here and there to keep the super-smart compiler from unrolling the loop in the naive case (which in the real world, it wouldn't, as the size of the array would not be known at compile-time). Also, searching for a 32-bit integer is way more realistic than searching for a byte! The inner-loops are pretty much as you'd expect (although why it uses two registers for addressing the array is beyond me). Knuth: LBB1_1: cmpl %edi, (%rdx,%rcx) leaq 4(%rcx), %rcx jne LBB1_1 Naive: LBB2_8: cmpl %ebx, (%r12,%rdx) je LBB2_11 addq $4, %rdx cmpq %rdx, %rax jne LBB2_8 Of course, all the comments about not being thread-safe are correct, and you probably only want to do this trick in primitive environments where you can allocate an extra slot at the end of the array when it's first created. But it's a nice trick when circumstances call for it.

lisper 7y ago
What happens when you make the array size larger than your processor cache?
- drfuchs 7y ago
  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
bjourne 7y ago
This is fun! $ clang -mtune=native -march=native -fomit-frame-pointer -O3 -o knuth_search2 knuth_search2.c $ ./knuth_search2 naive search average: 65025704.00 ns knuth search average: 76994680.00 ns and $ gcc -mtune=native -march=native -fomit-frame-pointer -O3 -o knuth_search2 knuth_search2.c $ ./knuth_search2 naive search average: 65636020.00 ns knuth search average: 64689948.00 ns knuth_search2 is your modified code but with 100mb arrays.

lisper 7y ago

What happens when you make the array size larger than your processor cache?

drfuchs 7y ago
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

bjourne 7y ago

This is fun! $ clang -mtune=native -march=native -fomit-frame-pointer -O3 -o knuth_search2 knuth_search2.c $ ./knuth_search2 naive search average: 65025704.00 ns knuth search average: 76994680.00 ns and $ gcc -mtune=native -march=native -fomit-frame-pointer -O3 -o knuth_search2 knuth_search2.c $ ./knuth_search2 naive search average: 65636020.00 ns knuth search average: 64689948.00 ns knuth_search2 is your modified code but with 100mb arrays.