Where the likely/unlikely statement should be placed for more performance?

Question

Some software (often performance-oriented, e.g. Linux kernel, DPDK) has C helpers for influencing branch prediction.

I have an absolutely simple code snippet (suppose I know the percantage of a > b) to represent the problem of conditions nesting and applying likely/unlikely when some logic is nested:

bool foo()
{
    foo1(1);
    foo2(2);

    /* if (unlikely(a > b)) */
    /* if (a > b)*/
    {
        puts("Ohhh!!! Rare case");
        return true;
    }
    return false;
}

int main(void)
{
    /* if (unlikely(foo())) */
    /* if (foo()) */
    {
        puts("Azaza");
    }
}

So which 2 lines should be uncomented for more performance from a theoretical point of view?

Obviously there are 3 ways to assist compilier with branch prediction:

1. if (unlikely(a > b)) ... if (unlikely(foo()))

2. if (a > b) ... if (unlikely(foo()))

3. if (unlikely(a > b)) ... if (foo())

Which is theoretically the most efficient and why?

Answer 1

To my knowledge, the likely/unlikely statements show the best effect if the conditional variable is not in the cache. Let me explain in more detail.

In your code, the processor has to execute foo anyway. So the likely won't have any strong effect here, since no code path can be skipped during speculative execution. The function must be executed. Let's assume you save the result of foo before in a variable and the code looks like this:

int x = foo();
if (likely(x))
{
    puts("Azaza");
}

In this case the likely(x) will probably only influence the prefetcher/decoder, since the processor just computed x and the value is most likely cached in L1 (except it got interrupted at that point). However, for a precise answer one has to know the microarchitecture extremely well, since it might be possible that current CPUs are so advanced that they can fetch and decode both branches at once.

Now let's assume you have a global variable volatile int c = 15 and we change your code:

if (likely(b == 15))
{
    puts("Azaza");
} else {
    puts("Bzaza");
}

When we execute the code and b is accessed for the first time it won't be in the cache and the processor has to fetch it from memory. This costs multiple hundred CPU-cycles and instead of stalling the CPU starts executing code speculatively without knowing the value of b. In that case, the likely keyword indicates that we should execute the first branch. Note that the executed instructions are not visible to the outside world at that time. Modern x86 processors can execute up to 400 micro-ops speculatively and only commit the result once the prediction turned out to be true.

So to answer your question I would put the likely/unlikely keyword around the a > b.