Hint branch prediction
What is the effect of branch prediction hints.
GCC provides __branch_expect() built in function, so the programmer can give hints to the compiler about branching.
Linux kernel defines two macros using this builtin function.
#define likely(x) __builtin_expect(!!(x), 1) #define unlikely(x) __builtin_expect(!!(x), 0)
Without this hint, it is totally up to compiler to predict branch. With hints, compiler generates code optimized for the hints.
For following conditional statement,
if (condition) do A;
usually compiler generates following codes.
0: TEST condition 1: JUMP to 3 if condition not met 2: do A 3:
With likely() it generates same code. With unlikely()
if (unlikely(condition)) do A;
the compiler generates different codes. It pushes the code that unlikely to happen to the end of the function which has higher chance of cache miss, and the keep the code that is more likely to happen near the TEST.
0: TEST condition 1: JUMP to 10 if condition is met 2: 3: ... 10: do A 11: JUMP to 2
Branch prediction hints may give the unlikely codes more penalty than the codes without hints. Thus if the prediction fails, it may cost higher than the code without hints.
Assume following codes.
if (condA) do A; else do B; if (likely(condB)) do C; else do D; if (unlikely(condC)) do E; else do F; if (condD) do G; else do H; do I do J
For conditional statement without hints, the compiler expects the condition is true. However, it keep the code for the else case near. For condition statements with hints, the compiler keeps the unexpected code far away. For example,
0: TEST condA 1: JUMP 13 if false 2: do A 3: TEST condB 4: JUMP 50 if false 5: do C 6: TEST condC 7: JUMP 52 if true 8: do F 9: TEST condD 10: JUMP 15 if false 11: do G 12: JUMP 17 # for condA 13: do B 14: JUMP 3 # for condD 15: do H 16: jump 6 17: do I 18: do J ..... # for condB 50: do D 51: JUMP 6 # for condC 52: do E 52: JUMP 9 <pre>