3 ms·

The paper draws the analogy to continuous root-finding ("Interpolation search is the regula falsi method"), nice. One thing I've been wondering lately is whethe

The paper draws the analogy to continuous root-finding ("Interpolation search is the regula falsi method"), nice. One thing I've been wondering lately is whether the ITP method[0], which is actually more recent than this paper, is a good fit for sorted searching. It's an elegant method that guarantees a maximum number of queries, for example one more than binary search, while taking advantage of interpolation for better-behaved distributions. I wrote a short section about this at [1]. Which is likely to link to the OP soon too. 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 https://en.wikipedia.org/wiki/ITP_Method [1] https://mlochbaum.github.io/BQN/implementation/primitive/sort.html#interpolation-search https://mlochbaum.github.io/BQN/implementation/primitive/sor...

deleted 3y ago
[deleted]
pvansandt 3y ago
Big fan on your presentation on binary search that amortised multiple concurrent searches. 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-Sorted-Arrays/blob/master/src/algorithms/binary_search.h#L18 https://github.com/UWHustle/Efficiently-Searching-In-Memory-...
- mlochbaum 3y ago
  Sounds good on the basic binary search. I jumped through the paper a little too quick and missed the source code link, although thanks for the godbolt confirmation as well. 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. [0] https://news.ycombinator.com/item?id=33648924 https://news.ycombinator.com/item?id=33648924
  - moonchild 3y ago
    > 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 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...

deleted 3y ago

[deleted]

pvansandt 3y ago

Big fan on your presentation on binary search that amortised multiple concurrent searches. 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-Sorted-Arrays/blob/master/src/algorithms/binary_search.h#L18 https://github.com/UWHustle/Efficiently-Searching-In-Memory-...

mlochbaum 3y ago
Sounds good on the basic binary search. I jumped through the paper a little too quick and missed the source code link, although thanks for the godbolt confirmation as well. 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. [0] https://news.ycombinator.com/item?id=33648924 https://news.ycombinator.com/item?id=33648924
- moonchild 3y ago
  > 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 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...