|
|
|
|
|
|
by repsilat
2783 days ago
|
|
|
> This is superior to binary-search: no branches (except for the test when bitfield is 0), and all the comparisons are done in parallel Branchless binary search isn't hard to implement if you know (or can bound) the number of elements statically. You just use the comparison result arithmetically instead of branching on it, and you unroll the loop. Obviously a binary search can't do comparisons in parallel, though. |
|
|
Sure you can, although at reduced efficiency the "deeper" you go.
For example, while searching a range of size N, you know your next probe point will be at N/2. You also know the probe point after that will be at N/4 or 3N/4, and so on. You know up-front all the possible probe points. Of course, only one out of the two probe points N/4 or 3N/4 or will actually be useful, depending on the N/2 result - but that doesn't stop you from comparing all three in parallel.
You can get a reasonable speedup this way: the extra comparisons happen in parallel and for a moderate depth the unnecessary probes are more than compensated by doing comparisons in parallel.