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

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.

Although it is possible to create branchless binary search. Here is one article: 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.

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.

Rule of thumb #1: don't. The compiler is probably smarter than you, it can handle things itself most of the time.

Rule of thumb #2: always test low-level performance improvements on real data. This is very similar to rule #1 - the compiler might already be implementing the optimisation you're changing to, so you might be making the code less readable for no benefit.

Rule of thumb #3: sort your arrays. Sorting algorithms are one of the most aggressively-optimised functions in modern computer science, it's a very small overhead compared to regular branch prediction failures. Make sure to keep rules #1 and #2 in mind, but this is probably the most common significant performance improvement to be gleaned from branch prediction.

Famous SO for #3 https://stackoverflow.com/questions/11227809/why-is-processi...

I might be off base here, but you would probably do best to not overthink this and let the compiler do its job. Attempting to pre-optimize if statements relative to a branch predictor (a very hardware-specific thing) is probably a massive fool's errand.

The compiler doesn't know how the CPU branch predictor works either. It's not especially good at optimizing this, or guessing if a branch is predictable or not, so you might as well do it yourself.

You can use the __builtin_expect keyword on GCC and clang.

It does make a difference (HPC code uses it quite a bit because of this), but as it's done manually, results obviously vary depending on processor, and there's a limit to how far you can take it. Trying not to branch (not always possible) is best...

Basically, it's like manually doing profile-guided optimisation - you look at perf or vtune, and add the above to branches which have a high penalty and which are rarely or often taken, and see if it makes a difference.

Note that this is not targeted to branch prediction, but compiler optimizations. It should be done carefully, because it tends to have a larger downside than its upside, and the changes the compiler makes based on it can be unpredictable, and unstable.

> Trying not to branch (not always possible) is best...

Branches are often faster than branch-free methods, since they can speculate certain data dependencies away.

> Branches are often faster than branch-free methods, since they can speculate certain data dependencies away.

And often they're slower, since predicting some branches is often impossible due to the data :) So the processor ends up miss-predicting most of the time, thinking it knows what happened last time.

It all depends on what you're doing.

You can hint the compiler: https://en.cppreference.com/w/cpp/language/attributes/likely

Or you can use profile directed optimization, as others mentioned.

In my test recently it reduced branches as a whole by 30%, according to perf stat ./a.out

Branch prediction works predictably well when the branch is heavily biased towards one outcome, typically follows a repeating pattern of a short length (eg. taken once every three iterations), or is strongly correlated with another preceding (not necessarily local) branch. Conversely, branch prediction works badly when they are data dependent on irregular data.

My rule of thumb is to partition my data sets, to make sure the conditional has the same result in as long a row as possible.