This is fascinating. Do you have any idea what might cause this? A shot in the dark: Their benchmarking uses a very simple "random" generation to choose the in

This is fascinating. Do you have any idea what might cause this? A shot in the dark: Their benchmarking uses a very simple "random" generation to choose the index to search for, which is actually just a linear scan (modulo the size of the array). Could it be that with the larger array, the generated sequence of test indices happens to work nicely with the CPU's branch prediction - after all, your results show a performance drop-off for the versions that use conditional moves, and the behavior depends suspiciously on the CPU microarchitecture.