Hint branch prediction

From Software Engineers Wiki
Jump to: navigation, search

What is the effect of branch prediction hints.

Answer

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>
Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox