2 ms·

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 confirmat

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...
- mlochbaum 3y ago
  There are some possibilities with uneven searches for sure. The major issue is that a search is so fast it doesn't leave a lot of room for overhead. For interpolation search, scheduling out bad cases sounds fine until you have a lot of them: then you have to search them one at a time, and the length's unpredictable, right? Grouping by search length doesn't really sound feasible: you'd have to store element index and value, as well as current search index, for each element that goes the long way.
  - moonchild 3y ago
    > length's unpredictable, right? Grouping by search length doesn't really sound feasible 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.)

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...

mlochbaum 3y ago
There are some possibilities with uneven searches for sure. The major issue is that a search is so fast it doesn't leave a lot of room for overhead. For interpolation search, scheduling out bad cases sounds fine until you have a lot of them: then you have to search them one at a time, and the length's unpredictable, right? Grouping by search length doesn't really sound feasible: you'd have to store element index and value, as well as current search index, for each element that goes the long way.
- moonchild 3y ago
  > length's unpredictable, right? Grouping by search length doesn't really sound feasible 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.)