4 ms·

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

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

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