I had to try it myself but it looks like you are right! http://codepad.org/tw6EJMr4 http://codepad.org/tw6EJMr4 i5-2500K: naive search found: 0, took 185

I had to try it myself but it looks like you are right! http://codepad.org/tw6EJMr4 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