If you know about the distribution of keys you can do even better by factoring that knowledge into where you split.

See also: Static search trees: 40x faster than binary search

- https://curiouscoding.nl/slides/p99-text/

- https://curiouscoding.nl/posts/static-search-tree/

- https://news.ycombinator.com/item?id=42562847 (656 points; 232 comments)

So is the SIMD the magic piece here, or is it the interpolation search? If the data is evenly distributed, that is pretty optimal for the interpolation search..

TL;DR the author developed an algorithm to solve this specific problem:

> The popular Roaring Bitmap format uses arrays of 16-bit integers of size ranging from 1 to 4096. We sometimes have to check whether a value is present.

There's no claim that this algorithm is universal and performs equally well for other problems.

In fact, note how the compare operation on the data types involved (16-bit integers) is quite cheap for modern CPUs. A similar problem with strings instead of integers would get no benefits from the author's ideas and would actually fare worse, due to useless comparisons per cycle.

This was the entry level project we did in a hardware optimization course I took maybe 15 years ago, using SIMD instructions. Lots of things can be naively optimized by unrolling any loops like this. Compilers do some of this themselves.

I always wondered if we could get any faster than O(log n). Glad we're making progress!

you know things are bad when lemire.me feels he needs to post an AI slop image :(

What about non-binary search?

And here I thought this was going to be related to quaternions

You can improve interpolated search by monitoring progress and if it's not converging fast enough, alternate with bisection steps. (and, as clear from the article, switch to linear/vector scanning when the range is small emough).

Often when an interpolated search is wrong the interpolation will tend to nail you against one side or the other of the range-- so the worst case is linear. By allowing only a finite number of failed probes (meaning they only move the same boundary as last time, an optimally working search will on average alternate hi/lo) you can maintain the log guarantee of bisection.