An unlikely experiment

There are so many great places to learn about out there on the internet, and one of those great places is the legendary Linux Kernel. If you stumble around some of that codebase (even if you don't understand much) you might see an interesting pattern littered throughout:

if (unlikely(condition_that_does_not_happen_much)) {
    // do thing
} else {
    // do more common thing
}

What is this mysterious unlikely? Why do we need to tell the computer that something is unlikely, and what does that even do?

It turns out that this simple statement can end up having a huge benefit to performance (or detriment, if used improperly). Let's see if we can understand this a bit, so that we can in turn improve our own programs :)

What is unlikely?

The definition of unlikely is actually a simple macro:

#define unlikely(e) __builtin_expect(!!(e), 0)

It takes in an operand e which is passed to __builtin_expect along with 0. __builtin_expect is a special function that just annotates an expression to tell the compiler that it should "expect" the value of the expression to be equal to the second value which in this case is zero.

What we are effectively doing here is giving the compiler some apriori information about what branch of the program is likely or unlikely to be taken. With this information it can prime the CPU to start with the correct probabilities for branch prediction and improve performance.

Okay that was a lot, can you give an example?

Sure I can! Let's great a simple example where we have two identical loops, except one will use the unlikely macro and the other uses the opposing likely macro:

long unlikely_simple(long num_runs) {
    long total = 0;
    for (long i = 0; i < num_runs; i++) {
        if (unlikely(i % 1000 == 0)) {
            total += 2;
        } else {
            total += i + 1;
        }
    }

    return total;
}

long likely_simple(long num_runs) {
    long total = 0;
    for (long i = 0; i < num_runs; i++) {
        if (likely(i % 1000 == 0)) {
            total += 2;
        } else {
            total += i + 1;
        }
    }

    return total;
}

In these simple loops, we take the if branch 0.1% of the time and the else branch 99.9% of the time. Naturally the actually more "likely" path here is the else branch, but we can trick the compiler to thinking the opposite with our choice of macro.

Let's observe the performance of these two loops, and also modify that 1000 to be different values so we can see the effect of different percentages on the likely and unlikely loops:

From the data we can see that as we decrease the percent of values that will take the first branch, the likely_simple compiler hint becomes less and less accurate. We hinted to the compiler that we should optimize towards the first branch, but real execution often goes to the second branch - leading to worse performance.

Okay so we've seen some data that shows our hint is having an effect on how the loop is processed. But why is that? The answer is in the assembly:

Assembly generated using the command: gcc -O2 unlikely.c -o bin/unlikely

Likely loop Assembly

0000000100000460 <_likely_simple>:
... 
# start of the loop
100000488: d343fd2d     lsr     x13, x9, #3
10000048c: 9bcb7dad     umulh   x13, x13, x11
100000490: d344fdad     lsr     x13, x13, #4
100000494: 9b0c29ad     madd    x13, x13, x12, x10
100000498: f10005bf     cmp     x13, #0x1

# branching check. if it's equal, go to else at "4b8"
10000049c: 540000e0     b.eq    0x1000004b8 <_likely_simple+0x58>

# the if branch. perform total += 2
1000004a0: 91000908     add     x8, x8, #0x2

# loop condition
1000004a4: 9100054a     add     x10, x10, #0x1
1000004a8: 91000529     add     x9, x9, #0x1
1000004ac: f1000400     subs    x0, x0, #0x1

# loop re-enter and loop exit checks here
1000004b0: 54fffec1     b.ne    0x100000488 <_likely_simple+0x28>
1000004b4: 14000004     b       0x1000004c4 <_likely_simple+0x64>

# the else branch. perform total += i
1000004b8: 8b0a0108     add     x8, x8, x10

# loop exit
1000004bc: 17fffffa     b       0x1000004a4 <_likely_simple+0x44>
1000004c0: d2800008     mov     x8, #0x0                ; =0
1000004c4: aa0803e0     mov     x0, x8
1000004c8: d65f03c0     ret

Unlikely loop Assembly

00000001000004cc <_unlikely_simple>:
...
# start of the loop
1000004f4: d343fd2d     lsr     x13, x9, #3
1000004f8: 9bcb7dad     umulh   x13, x13, x11
1000004fc: d344fdad     lsr     x13, x13, #4
100000500: 9b0c29ad     madd    x13, x13, x12, x10
100000504: f10005bf     cmp     x13, #0x1

# branching check. if it's NOT equal, go to if at "524"
100000508: 540000e1     b.ne    0x100000524 <_unlikely_simple+0x58>

# the else branch. perform total += i
10000050c: 8b0a0108     add     x8, x8, x10

# loop condition
100000510: 9100054a     add     x10, x10, #0x1
100000514: 91000529     add     x9, x9, #0x1
100000518: f1000400     subs    x0, x0, #0x1

# loop re-enter and loop exit checks here
10000051c: 54fffec1     b.ne    0x1000004f4 <_unlikely_simple+0x28>
100000520: 14000004     b       0x100000530 <_unlikely_simple+0x64>

# the if branch. perform total += 2
100000524: 91000908     add     x8, x8, #0x2
100000528: 17fffffa     b       0x100000510 <_unlikely_simple+0x44>
10000052c: d2800008     mov     x8, #0x0                ; =0
100000530: aa0803e0     mov     x0, x8
100000534: d65f03c0     ret

Lots of assembly, but the key part is the order of the branches in the likely loop versus the unlikely loop. In the unlikely loop, we have the total += i + 1 assembly immediately following the if condition check and a branch to the total += 2 assembly. The compiler uses the opposite ordering and branching in the likely loop, favoring to have the total += 2 assembly first and and the total += i + 1 second.

This ordering is important to the execution of the loop because the CPU will generally pipeline instructions, meaning that it will prefetch and pre-emptively execute several instructions after the currently executing one. The pre-fetch happens in the order of the instructions in memory, hence why the order matters. This explains why in our experiment we would see varying performance for the two functions. One of them would go against that pipelining and cause the CPU work to be wasted, and the other was aligned with it and lead to better performance.

Conclusion

There are lots of little gems like this in open source repos that we can all learn from. While unlikely and likely touch upon several low level concepts that likely won't matter for the average program, it is always good to have this knowledge in your backpocket. You never know when this type of code might 2X your performance!