4 ms·

If you have perf critical branches in your code, you should try and make them as predictable as possible. Sometimes that means using a different approach that i

If you have perf critical branches in your code, you should try and make them as predictable as possible. Sometimes that means using a different approach that is algorithmically worse, but has much more predictable branches. Classic example is linear search is faster than binary search for “small” lists. The item == myItem branch is only taken once at the end. Meanwhile binary search will take the branches of it’s comparison (item < myItem, item > myItem) in equal proportion to each other, so the branch predictor is stuck at a 50% guess for that branch. There is a great talk on this but I can’t remember what it’s called...

sischoel 5y ago
Although it is possible to create branchless binary search. Here is one article: https://schani.wordpress.com/2010/04/30/linear-vs-binary-search/ https://schani.wordpress.com/2010/04/30/linear-vs-binary-sea..., there are probably other ways to do that. Another interesting question where one could sink a lot of time is how do to binary search on GPU's using multiple threads. There branching in multiple threads at the same time is also bad, but for slightly different reasons.
- singron 5y ago
  On a GPU you could do a parallel n-ary search. I.e. instead of making 1 test in the center, make n tests. E.g. 1 round of 32-ary search should be equivalent of 5 rounds of binary search. Not only do you avoid the branch predictor, but the memory access is also parallel, which isn't true in branchless binary search. If the width of the search is larger than a warp/wavefront (32/64), then you need to add synchronization and it might not be faster anymore. GPUs aren't really built for latency though and this will waste a lot of accesses on speculation. You are probably better off with a good btree.
acidbaseextract 5y ago
As you point out, the exact properties that make binary search algorithmically fast can slow it down on real computer hardware. Branch predictors like low entropy (unsurprising) branches, but binary search is algorithmically fast because it maximizes the entropy (information gained) from the few branch checks that it does make.

sischoel 5y ago

Although it is possible to create branchless binary search. Here is one article: https://schani.wordpress.com/2010/04/30/linear-vs-binary-search/ https://schani.wordpress.com/2010/04/30/linear-vs-binary-sea..., there are probably other ways to do that. Another interesting question where one could sink a lot of time is how do to binary search on GPU's using multiple threads. There branching in multiple threads at the same time is also bad, but for slightly different reasons.

singron 5y ago
On a GPU you could do a parallel n-ary search. I.e. instead of making 1 test in the center, make n tests. E.g. 1 round of 32-ary search should be equivalent of 5 rounds of binary search. Not only do you avoid the branch predictor, but the memory access is also parallel, which isn't true in branchless binary search. If the width of the search is larger than a warp/wavefront (32/64), then you need to add synchronization and it might not be faster anymore. GPUs aren't really built for latency though and this will waste a lot of accesses on speculation. You are probably better off with a good btree.

acidbaseextract 5y ago

As you point out, the exact properties that make binary search algorithmically fast can slow it down on real computer hardware. Branch predictors like low entropy (unsurprising) branches, but binary search is algorithmically fast because it maximizes the entropy (information gained) from the few branch checks that it does make.