Comment by pantalaimon

I had to try it myself but it looks like you are right!

http://codepad.org/tw6EJMr4

i5-2500K:

  naive search
  found: 0, took 1856721 ns
  found: 0, took 1799554 ns
  found: 0, took 1908483 ns
  found: 0, took 1921622 ns
  found: 0, took 1856173 ns
  found: 0, took 1812736 ns
  found: 0, took 1819938 ns
  found: 0, took 1846232 ns
  found: 0, took 1821858 ns
  found: 0, took 1898503 ns
  average: 1854182.00 ns

  knuth search
  found: 0, took 1969758 ns
  found: 0, took 2125165 ns
  found: 0, took 2081280 ns
  found: 0, took 2033002 ns
  found: 0, took 1948852 ns
  found: 0, took 2049150 ns
  found: 0, took 2046759 ns
  found: 0, took 2101704 ns
  found: 0, took 2083800 ns
  found: 0, took 2120793 ns
  average: 2056026.38 ns

edit:

I was wondering how it would look on a simpler CPU, presumably without branch prediction and my router came to mind. Indeed there the picture looks different:

Qualcomm Atheros QCA9558 (MIPS 74Kc V5.0)

  naive search
  found: 0, took 20582795 ns
  found: 0, took 21233303 ns
  found: 0, took 20505486 ns
  found: 0, took 20633735 ns
  found: 0, took 21079799 ns
  found: 0, took 20619782 ns
  found: 0, took 21099067 ns
  found: 0, took 20558769 ns
  found: 0, took 20398468 ns
  found: 0, took 20888357 ns
  average: 20759956.00 ns

  knuth search
  found: 0, took 16323322 ns
  found: 0, took 16530714 ns
  found: 0, took 16255532 ns
  found: 0, took 16416161 ns
  found: 0, took 16577751 ns
  found: 0, took 16488995 ns
  found: 0, took 16417074 ns
  found: 0, took 16466930 ns
  found: 0, took 16295522 ns
  found: 0, took 16277085 ns
  average: 16404909.00 ns