When the region is large it just doesn't cut the search space down almost at all: it's a rounding error.

Now you might think it's basically free, but clogging up the OOOE structures with instructions can hurt MLP because fewer memory accesses fit in the window, even if the instructions always completely execute in the shadow of existing misses.

There is a similar trick with pages: you might try to favor not touching more pages than necessary, so it might be worth moving probe points slightly to avoid touching a new page. For example, if you just probed at bytes 0 and 8200, the middle is 4100, but that's a new 4k page (bytes 4096 thru 8191), so maybe you adjust it slightly to probe at 4090 since you already hit that page with your 0 probe.

Making all of these calculations dynamically is a bit annoying and maybe slow, so it's best if the whole search is unrolled so the probe points according to whatever rules can be calculated at compile time and embedded into the code.

Much more important than either of these things is avoiding overloading the cache sets. Some implementations have this habit of choosing their probe points such that only a very small number of sets in the L1, L2 are used so the caching behavior is terrible. Paul Khuong talks about this in detail on pvk.ca.

Doing a linear walk at the end definitely helps a bit though: SIMD is fastest for this part.

For example the first access in a binary search will be the middle element, followed by the lower quartile or upper quartile. If you store all of those together in memory, a single cache line fetch can serve all those requests.

Edit: Oops, TIL the eytzinger layout other comments have mentioned _is_ a levelwise traversal. Anywho, it's usually a good starting point for this kind of thing.

If you store the middle element together with its first two quartiles, you're making a B-tree. You will need indirection (pointers) to locate the other chunks that are not stored together and so it goes.

"Binary search" usually refers to the sorted array algorithm, though of course in the abstract sense of subdivision, any subdivision-by-two search is binary and in that sense we have the term "binary search tree".

On a GPU for example, if you have an array with 100.000 elements and want to find the index of one value, you are probably best of by using 100.000 threads to find that value.

So that's 100.000-ary search.

On a CPU, using an Eytzinger layout will probably also give you better performance than any of the N-ary approaches.

Very readable blog post on how it helps with binary search: https://algorithmica.org/en/eytzinger

With follow up post on N-ary approaches: https://algorithmica.org/en/b-tree

Bonus if this library also detected/leveraged specialized hardware (GPU, AVX, etc) and then leveraged it appropriately.

Obviously, these parameters would need optional per-app-invocation overrides, e.g. so random apps didn't hog shared resources, e.g. for benchmarking, etc.

(I'm guessing this exists but not widely deployed...?)

[1] https://en.wikipedia.org/wiki/Automatically_Tuned_Linear_Alg...