efficient, extremely-unlikely conditionals?

Question

I have some performance-critical code that will crash and burn in extremely unlikely situations (e.g. when an intermediate double equals 0.0, when it is no more likely for that double to be zero than any other value).

One option of course is to whistle and ignore the corner case, and pray it never comes up. But I'd like to catch it if possible; on the other hand I'm not too enthusiastic about adding conditionals into performance-critical code. Are there any tricks to adding a check of the form

if(val == 0.0)
{
    // extremely unlikely code path
}

in a way that will minimize the performance penalty? On some compilers it's possible to pass the CPU branch-prediction hints, but I've heard that these no longer have any effect on modern processors?

Answer 1

use likely , unlikely

In the Linux kernel, they are defined as

#define likely(x)       __builtin_expect(!!(x), 1)
#define unlikely(x)     __builtin_expect(!!(x), 0)

The __builtin_expect macros are GCC specific macros that use the branch prediction; they tell the processor whether a condition is likely to be true, so that the processor can prefetch instructions on the correct "side" of the branch.

You should wrap the defines in an ifdef to ensure compilation on other compilers:

#ifdef __GNUC__
#define likely(x)       __builtin_expect(!!(x), 1)
#define unlikely(x)     __builtin_expect(!!(x), 0)
#else
#define likely(x)       (x)
#define unlikely(x)     (x)
#endif

Answer 2

You might want to look at the answers to this question. If you have any notion of ever running on Windows, you might want to look at this as well.

It's almost certainly worth your while to look at the explanations of branch predictions in the answers to this question. (Note that the behavior observed in that question was common not just across compilers but across languages, illustrated by examples in Java and C++.)

As far as I understand this, the problem with

if (val == 0.0)
{
  // extremely unlikely code path
}

is that the branch predictor will initially assume that the condition will be true, that is, it will start to execute your extremely unlikely code path as soon as it encounters this condition for the first time. The cost of the branch isn't so much the evaluation of val == 0.0 but the cost of backing out of the unlikely branch when val == 0.0 turns out to be false. After it has encountered the branch statement a few times, however, the branch predictor will guess that the condition is false, and execution will proceed just as if you had told the compiler that the "false" branch was the likely one to take.

Running in such an environment, you don't need to optimize the branch in general, because it will be optimized for you. The only optimization you can make to the branching is to optimize the first time when it is called (and maybe a couple of other times, depending on exactly what the branch prediction algorithm looks for). If your application is so performance-critical that you can't afford that cost for even the first one or two times a function is run, should you be programming in C++?

In order to encourage the branch predictor to take the right path the first time, however, you could write

if (val != 0.0)
{
  // stuff you want to do almost every time
}
else
{
  // extremely unlikely code path
}

This has two advantages: first, it's portable, and second, it gets the extremely unlikely code out of the way so you can more easily see what the code is usually supposed to do. The disadvantage is that it adds another level of indentation to // stuff you want to do almost every time.

I'll admit to having used this technique myself.

Answer 3

You need to know if having that conditional in there is actually hurting performance in a significant way. This is the method I use.

I would tend to assume if there's a performance issue in the time-critical code, one should go after what that issue actually is. Don't assume the conditional hurts until the diagnostic proves it.