Sorry, my phrasing was poor. The searched for elements are indeed random, but the first few (and last few) accesses will hit cache. Depending on the size of t

Sorry, my phrasing was poor. The searched for elements are indeed random, but the first few (and last few) accesses will hit cache. Depending on the size of the total array, the relative importance of the different access times vary. We were actually comparing some different memory layouts besides the standard "sorted" (http://cglab.ca/~morin/misc/arraylayout/ http://cglab.ca/~morin/misc/arraylayout/). Our conclusion was essentially that with proper implementation, there wasn't much if any advantage to alternative layouts. But there certainly were some subtle things about testing. In particular, there is a significant difference between preparing a list of random searches in advance (and loading them from memory), versus calculating a random number on the fly. Since the performance advantage of the branching approach depended on how far ahead the speculative execution would get, the additional µops for making the number sometimes slowed down enough to remove the speculative advantage. But to clarify my earlier answer: I think the author is seeing real effect, and the difference has to do with prefetching due to speculative execution of the branching approach. This doesn't mean that branching is the best approach, though, only that a "naive" approach can indeed beat branchless at certain sizes. Both the branching and branchless approaches can be improved significantly with either batching or explicit prefetching.