An unlikely experiment

In the world of programming, there are many resources available to learn from, and one of the most prominent is the Linux Kernel. Within its extensive codebase, you may come across an intriguing pattern: an if statement with an unlikely macro. This statement, unlikely (condition_that_does_not_happen_much), plays a crucial role in optimizing program performance.

But what exactly is unlikely, and how does it impact the efficiency of our programs? Let's delve into this topic and uncover the secrets behind this seemingly simple construct.

The unlikely macro, defined as #define unlikely(e) __builtin_expect(!!(e), 0), is a straightforward macro that takes an operand e and passes it to the __builtin_expect function along with 0 as the second argument. The __builtin_expect function is a special tool that informs the compiler about the anticipated outcome of an expression.

By annotating an expression with __builtin_expect, we provide the compiler with prior knowledge about which branch of the program is more likely or unlikely to be executed. This valuable information allows the compiler to optimize the code by priming the CPU with the appropriate branch prediction probabilities, ultimately leading to improved performance.

To illustrate the concept, let's consider a simple example. We have two identical loops, one using the unlikely macro and the other using the likely macro. In these loops, we perform an if statement that checks if the value of i is divisible by 1000. In the unlikely loop, this condition occurs 0.1% of the time, while the else branch happens 99.9% of the time.

Conversely, in the likely loop, the else branch is the more common scenario. By employing different macros, we can trick the compiler into thinking the opposite branch is more likely to occur.

When we measure the performance of these two loops, we observe that as the percentage of values taking the first branch decreases, the accuracy of the likely_simple compiler hint diminishes. This is because the compiler optimizes the code based on the expected branch outcomes. When the actual execution deviates from these expectations, performance suffers.

The assembly code generated for both loops reveals the key difference: in the unlikely loop, the code directly follows the if condition with the total += i + 1 assembly, followed by a branch to the total += 2 assembly. In contrast, the likely loop has the total += 2 assembly followed by the total += i + 1 assembly. This ordering matters because modern CPUs employ a technique called instruction pipelining, where they prefetch and pre-emptively execute several instructions after the currently executing one.

By arranging the instructions in the most efficient order, the CPU can optimize its processing pipeline, resulting in better performance.

In summary, the unlikely macro and the __builtin_expect function are powerful tools in a programmer's arsenal. By providing the compiler with information about the likelihood of branch outcomes, we can guide the compiler in optimizing our code for better performance. The example we explored demonstrates how the order of instructions and the compiler's ability to anticipate branch outcomes can significantly impact the execution speed of our programs.

So, the next time you come across an unlikely macro in the Linux Kernel or your own codebase, remember its importance in fine-tuning performance and unlocking the full potential of your programs.