Except that the optimization seem to be quite spectacular.
Compiling pantalaimon's code, there doesn't seem to be any significative difference between the two algorithms with the default compilation parameters of gcc.
However compiling with gcc -O3, Knuth's algorithm is almost twice as fast on an Intel i7-7700HQ, old tricks still work well:
naive search
found: 0, took 597719 ns
found: 0, took 601291 ns
found: 0, took 593332 ns
found: 0, took 592513 ns
found: 0, took 592799 ns
found: 0, took 592409 ns
found: 0, took 592563 ns
found: 0, took 592289 ns
found: 0, took 631602 ns
found: 0, took 592928 ns
average: 597944.50 ns
knuth search
found: 0, took 300860 ns
found: 0, took 318691 ns
found: 0, took 317502 ns
found: 0, took 317348 ns
found: 0, took 351612 ns
found: 0, took 317625 ns
found: 0, took 318217 ns
found: 0, took 312106 ns
found: 0, took 397532 ns
found: 0, took 318284 ns
average: 326977.69 ns
Just for fun, here is the dump of assembler code for function search_knuth:
Compiling pantalaimon's code, there doesn't seem to be any significative difference between the two algorithms with the default compilation parameters of gcc.
However compiling with gcc -O3, Knuth's algorithm is almost twice as fast on an Intel i7-7700HQ, old tricks still work well:
naive search found: 0, took 597719 ns found: 0, took 601291 ns found: 0, took 593332 ns found: 0, took 592513 ns found: 0, took 592799 ns found: 0, took 592409 ns found: 0, took 592563 ns found: 0, took 592289 ns found: 0, took 631602 ns found: 0, took 592928 ns average: 597944.50 ns knuth search found: 0, took 300860 ns found: 0, took 318691 ns found: 0, took 317502 ns found: 0, took 317348 ns found: 0, took 351612 ns found: 0, took 317625 ns found: 0, took 318217 ns found: 0, took 312106 ns found: 0, took 397532 ns found: 0, took 318284 ns average: 326977.69 ns
Just for fun, here is the dump of assembler code for function search_knuth:
And here is the dump of assembler code for function search_naive: