Efficiently Searching In-Memory Sorted Arrays: Revenge of Interpolation Search? [pdf]
pages.cs.wisc.edu
pages.cs.wisc.edu
I might suggest, slightly pushing back on this article's PDF, binary search is not the de-facto in-memory search algorithm. Cache consciousness btrees, and various optimizations of tries, or radix trees are better. Eytzinger arrays are a good BST option if data is pre-sorted and/or requires rare resort passes. Which brings us back to btrees: keeping data sorted is usually 51% of the problem. Search is the other 49%.
OK, if you don't need range search, which needs sorted keys, then hashmaps are darn hard to beat.
The PDF author however makes a strong point: if FLOPS is going up way faster than memory BW, the obvious thing to do is spend a little more code looking into memory smartly. And the PDF even gives algos to do it. So my that's why I say BST as de-facto algorithm, while I don't think that's true, is only small push back. The paper goes way further.
However, the inner loop of indexes usually is some other kind of search algorithm. Graefe mentions in BTree techniques that interpolation search is sometimes applicable to inner nodes in btrees. One of the SIP evaluations was using SIP as part of the inner loop in LevelDB, which doesn't displace the use of an LSM for managing the larger data set.
If you don't need a lot of range queries, eytzinger, or cache-line optimized btrees do get a lot more interesting, but the iteration logic gets a lot worse. SIP returns an element if it's present and a sentinel if absent, which is an odd choice since the index is usually what's needed. No clue, but hopefully you'll have some sympathy for revisiting your old code and wondering who wrote it. :)
I do think that optimizing search algorithms is still worthwhile in an indexed setting for two reasons: 1. The size of a node within an index like a btree depends on the efficiency with which that node can be searched, so if you are able to decrease the cost of searching a given node in the index, that might motivate larger node sizes. I know that a common heuristic is to use a multiple of a page size, but that is based on the assumption that the whole node will be used as part of the search. 2. Pushing algorithmic decisions to just in time can be more costly than the time saved from choosing a better algorithm. You lose icache efficiency, stall on the decision, etc. I think it's still good to steel man, as best you can, that your index is actually buying you improved performance for additional complexity or update overhead.
It's intriguing that Interpolation Search, despite its historically lackluster performance, is being given a second life through SIP and TIP. I love the fact that they're leveraging hardware trends and advanced calculations to optimize search performance.
The fact that SIP shows up to 4x faster performance on uniformly distributed data and TIP is 2-3x faster on non-uniformly distributed data is quite promising. It seems these approaches could be really useful in practice, given that real-world data often follows non-uniform distributions.
The introduction of a meta-algorithm to dynamically select the optimal search algorithm based on the data distribution is a clever touch. It helps to enhance the overall search performance by not sticking to a one-size-fits-all approach.
I'd love to read more about these techniques and their practical implementations. Do they have any benchmarks or plans to test these new methods in large-scale, real-world systems?
But the parts of the comment you're highlighting are specific and opinionated. And I don't find them particularly hyperbolic.
SIP is very sensitive to quality of implementation. I did my best to steel man binary search, but if either is not implemented carefully, then you can easily get inverted results. I tried several different axes of variation for implementation of binary search and probably spent more time optimizing binary search than SIP or TIP, but binary search is very sensitive to cache misses and how that relates to branch prediction and conflict misses. Quality of linear search is also critical and relies heavily on array padding. SIMD was actually a major pessimization since for SIP, it's only worth using if linear search is < 100 elements or so.
I spent a lot of effort trying to model the performance of SIP to predict from statistics of the data to how it would perform. You can consider the cost of each interpolation as a random access cache miss, and the cost of a linear search based on its distance, but the cost of a linear search has decreasing marginal cost with more distance before you reach steady state, which is exactly where you are using it in SIP. So, that basically led nowhere, but it does point out that an L2 norm is the wrong metric for identifying if interpolation would be useful on your data.
I think the bigger insight of TIP is around its use of efficient approximations for hyperbolic interpolations. There's a lot of research around polynomial interpolation, but I think that hyperbolas are also worth examining. I don't expect TIP to be used in a database engine, and while data might be commonly zipf distributed, I'm not sure that people are putting that kind of data into an array and doing lookups on them where the values at the bottom of the array have a lot of duplicate values.
SIP, I think, is more about increasing amounts of spatial cache locality, and making the most of out-of-order processors. It is more a variation on interpolation-sequential search, so it might be more practically used in a SIP-2 or SIP-3 variation which a hard-coded, unrolled number of iterations. (SIP-1 would just be interpolation sequential.) The downside of an interpolation method is that pairs of sequential interpolations don't surround the target, which leaves the search unbounded. I don't find hybrid approaches very interesting because I don't expect an implementation to be able to pipeline useful work which has a time per iteration that is sufficiently fast. For perspective, on billion element arrays, I think typical number of interpolations was around 3. We would expect number of interpolations to not increase to 4 until you hit a quintillion elements which suggests that the gap in efficiency between log N and log log N grows slowly enough that algorithmic gains have a nearby, practical upper bound to potential improvement.
One of my favorite related papers is RadixSpline by Kipf et al. The amount of additional memory across a number of scenarios would be tiny, you could write a very efficient inner loop, and it would have basically been tailor fit to work perfectly on the FB dataset (one of the real world distributions).
Since the author's here: the "Optimized binary search" algorithm looks good, in that it has an obvious branchless implementation. But it'll depend on how the code's written and compiled, and clang in particular will turn it into a branch without -mllvm --x86-cmov-converter=0. Making it branchless was the intention, right? Was the output code checked to make sure it uses cmov?
[0] https://en.wikipedia.org/wiki/ITP_Method
[1] https://mlochbaum.github.io/BQN/implementation/primitive/sor...
I did several variations on binary search and always compared against the best one. [0] From what I remember, some variations were compiled to a branchless implementation and some were compiled to implementations that used a branch. I had many passes of analysis by pasting into godbolt with identical compilers and flags. Power of 2 binary search did better on small arrays iirc, but are the first to hit conflict misses. For larger arrays, I believe the branchy search algorithms start to do better since half their branches get predicted correctly.
I haven't previously looked at ITP, and I would need to study further to get a more clear idea on what its aiming for. Some hybrid methods, unlike ITP require additional memory accesses, but I don't think this does, just compute. On the other hand, since at a billion elements you're looking at roughly 3 interpolations or 30 bisections, there's a pretty narrow window of opportunity here, and in the batch case, there are indices to contend with. I'm on the BQN discord if you wanted a different form of communication.
[0] https://github.com/UWHustle/Efficiently-Searching-In-Memory-...
Yeah, the big deal about ITP is not really the interpolation but the graceful fallback to binary search. With of course that nasty division overhead. I'll have to study your paper to see which ideas there could be used.
Glad you liked the talk! And a small world, huh? I've been wanting to get an implementation of the vector binary search into CBQN for a while, so that an open source version of it exists at least. Always some other thing to do. Multiple searches are really a different world. Elijah Stone pointed out recently[0] that with searches that all have the same iteration count (sadly, not interpolation search!), several of them can be run at once just by copying the loop body. That was new to me at least. And for searches that don't fit in cache it's possible to partition the sought values, which does the accesses in a perfectly cache-friendly order for some extra compute. That's described in the page I linked before.
They don't need to have the same iteration count; it suffices to mask out searches as they finish (like gpus) or ensure that repeated search iterations are idempotent, and just wait until all finish. My first implementation actually did this, and the iteration count could vary by as much as 1 when the search space size was not a power of two. I changed that after henry pointed out that it can cause mispredicts.
In the case of interpolation search, a naive application might be a bad idea (since a single pathological lane slows down all the other concurrent searches). But an alternative might be to detect and 'schedule out' pathological lanes; use binary search instead of interpolation search for them, and now you have nice worst-case asymptotics again.
(Fun anecdote: I asked an nvidia employee why they don't use this strategy for gpu branches in general. The response: mumble mumble not sure, probably tradeoffs—just isn't worth it. Fair enough. Not six months later, they release new gpus which do that for sparse threadgroups. I maintain they stole the idea from me :)
Alternately, it might be possible to swap out completed lanes as soon as they finish—superscalar cpu is a mimd, after all—getting this branch free might be too much overhead, but maybe if you do the check every k iterations or something...
You just have to group by ceillog2, so there aren't many buckets. Can even discretise further (say, one bucket for every two exponents) with likely not too much penalty. Alternately, perhaps restart the search entirely for pathological elements (so don't try to keep around the information gained by the cursory iterations of interpolation search), but if there are too many pathological elements, just do binary search up front for all elements. I expect this would work pretty well in practice. (Maybe with exponential backoff or something, so you don't lose to changes in the distribution of elements being searched for.)
(This reminds me, I have a similar problem with adaptive sorting. Having identified a number of presorted runs, it's necessary to merge them in the right order, because if I merge them in the wrong order I get quadratic. Plan is similarly to sort them by lzcnt or some such, which is a curious recursive problem.)
(not sure if this is what you meant by "conflict misses") I believe the reason branchy binary search algorithms do better on large arrays is that the CPU's speculative execution will cause it to prefetch data to the caches. That means that, for around half of the steps, the data needed for the comparisons will not need to be fetched from memory.
You can get the best of both world by using a branchless implementation and manually prefetching data as in [^0].
[0^]: https://en.algorithmica.org/hpc/data-structures/binary-searc...
Much faster than the SIP and TIP nonsense in the tight loop. Also faster than Eytzinger in most cases. They use only a linear equation to model the data, quadratic or logarithmic fit would be much better. And it's much smaller than a full db index, just 3-4 numbers, the type of the curve (linear, quadratic, logarithmic) and the curve parameters.
Without ranges a hashtable is still the best, esp. if constant then use a CMPH. I use that in unicode table searches, where the data varies every year.
How do you start a binary search at a single point exactly, search in the right direction doubling the interval size until you bracket it? The paper mentions what they call Interpolation-Sequential which does a sequential search instead and they claim this is faster if you get close enough. In any case, it doesn't seem right to call this "branchless" given that the number of steps is variable.
TIP uses rational functions, not linear. Still, I'm a bit skeptical that a global quadratic or logarithmic fit solves all problems: isn't piecewise data with one or two big gaps fairly common? With a distribution that's uniform only after taking a log, I see how a logarithmic fit would have some theoretical motivation; quadratic seems unmotivated.
If your data is non-linear, then polynomials will require a lot of terms to have low enough error, eg. on zipf. You also need to be able to fit the curve efficiently, so hyperbolic interpolation was a viable option.
With respect to finding the pivot beforehand, by choosing the end points, you can have confidence that you won't need to saturate at the end points in the first step. You might get better error by finding a better slope, but that is accepting a much higher cost to choosing the parameters.
I'd be curious to learn about related approaches which you've measured to be a big improvement, although I didn't understand all the terms you used.
Multidimensional curves, ie lots of holes in the data, do make no sense to model for the initial pivot calc. Binary search finds them much better then. The cost is similar to a hash table, almost constant with 2-4 branches, and mostly into cached data.
I agree because for datasets that fit into memory, the scope for improvement is pretty limited. From a billion elements to 128 billion, that's only around 23% (37/30) more comparisons for binary search, and keeping that constant at the expense of more linear search isn't necessarily all that interesting for cheap comparisons. LogN grows so slowly that log-logN is frequently not that practically interesting.
This paper seems to imply that previous approaches didn't use piecewise-linear approximations??
Can someone clear up if I got my history wrong? Did I just assume piecewise-linear is well-known when it isn't?
The Google paper is "The Case for Learned Index Structures" I think? This paper discusses index structures to be stored along with the data, so it's not directly comparable to the OP, which starts with the sorted data alone. Google's use case is so dominated by lookups that as far as I can tell they don't even report on the time to construct the index. I'm not sure the same priorities hold in every domain.
Building and maintaining indices is also not free, so it's interesting to try to do your best with much less index maintenance.