[williamkuszmaul]

One thing I'm confused about: Did the author try vectorizing the linear search implementation? (Of course, it is possible that even if they did not, the compiler did.) I would imagine that vectorization is behind the advice to use linear searches on small arrays.

[dkersten]

> I would imagine that vectorization is behind the advice to use linear searches on small arrays.

I always thought a core part is that searching linearly is simply very cache efficient due to easy prefetching of linear data and that this is simply faster when you don’t have to search too much. Of course, that and vectorisation together is even better.

[orlp]

The benchmarking code is available, I did not: https://github.com/orlp/bitwise-binary-search. The compiler also did not appear to have autovectorized it.

That said, I would expect the overhead of vectorization to dominate at smaller sizes, and the fact that linear search is... well... linear to dominate at larger sizes. There might be a sweet spot for a few dozen elements where it would be the best, but I think it'd be rather niche (and strictly limited to floats/integers).

Regarding cache effects of linear search, this entire article is under the assumption your data is in-cache, if not your results will vary (wildly).