1
#define likely(x)   __builtin_expect(!!(x), 1)
2
#define unlikely(x) __builtin_expect(!!(x), 0)
3

4
// 示例：错误路径标记为 unlikely
5
if (unlikely(ptr == NULL)) {
6
    return -EINVAL;  // 编译器将此路径放在远处
7
}
8

9
// 示例：正常路径标记为 likely
10
if (likely(cpu_online(cpu))) {
11
    // 编译器将此路径紧随 if 之后
12
    schedule_on_cpu(cpu);
13
}

1
if (a > 0) { ... }   // 分支 B1
2
if (b > 0) { ... }   // 分支 B2
3
if (a > 0 && b > 0) { ... }  // 分支 B3
4
// B3 的结果完全由 B1 和 B2 决定！

1
┌──────────┬──────────────┬──────────┐
2
│ 分支 PC  │ 目标地址      │ 预测信息  │
3
├──────────┼──────────────┼──────────┤
4
│ 0x401000 │ 0x401050     │ Taken    │
5
│ 0x401020 │ 0x401100     │ Not Taken│
6
│ 0x401050 │ 0x401200     │ Taken    │
7
│ ...      │ ...          │ ...      │
8
└──────────┴──────────────┴──────────┘

1
int foo() { return bar(); }  // bar() 返回到 foo
2
int baz() { return bar(); }  // bar() 返回到 baz
3
// bar() 中的 ret 指令需要返回到不同地址！

1
#include <stdio.h>
2
#include <stdlib.h>
3
#include <time.h>
4

5
#define SIZE 32768
6

7
int main() {
8
    int *data = malloc(SIZE * sizeof(int));
9
    for (int i = 0; i < SIZE; i++) data[i] = rand() % 256;
10

11
    // 测试 1：未排序数据
12
    clock_t start = clock();
13
    long long sum = 0;
14
    for (int j = 0; j < 10000; j++) {
15
        for (int i = 0; i < SIZE; i++) {
16
            if (data[i] >= 128) sum += data[i];
17
        }
18
    }
19
    clock_t end = clock();
20
    printf("未排序: %.3f 秒\n", (double)(end - start) / CLOCKS_PER_SEC);
21

22
    // 排序
23
    qsort(data, SIZE, sizeof(int), (int(*)(const void*,const void*))strcmp);
24

25
    // 测试 2：排序数据
26
    start = clock();
27
    sum = 0;
28
    for (int j = 0; j < 10000; j++) {
29
        for (int i = 0; i < SIZE; i++) {
30
            if (data[i] >= 128) sum += data[i];
31
        }
32
    }
33
    end = clock();
34
    printf("已排序: %.3f 秒\n", (double)(end - start) / CLOCKS_PER_SEC);
35

36
    free(data);
37
    return 0;
38
}

1
perf stat -e branches,branch-misses ./branch_test
2

3
# 未排序版本：
4
#   327,680,000  branches
5
#   163,840,000  branch-misses          # 50.00% of all branches
6

7
# 排序版本：
8
#   327,680,000  branches
9
#       256,000  branch-misses          # 0.08% of all branches

1
// 分支版本
2
int max_branch(int a, int b) {
3
    if (a > b) return a;
4
    else return b;
5
}
6

7
// 条件传送版本（CMOV）
8
int max_cmov(int a, int b) {
9
    return (a > b) ? a : b;  // 编译器可能生成 CMOV
10
}

1
// 分支版本：计算绝对值
2
int abs_branch(int x) {
3
    if (x < 0) return -x;
4
    return x;
5
}
6

7
// 无分支版本
8
int abs_branchless(int x) {
9
    int mask = x >> 31;  // 0x00000000 或 0xFFFFFFFF
10
    return (x ^ mask) - mask;
11
}
12

13
// 分支版本：clamp
14
int clamp_branch(int x, int lo, int hi) {
15
    if (x < lo) return lo;
16
    if (x > hi) return hi;
17
    return x;
18
}
19

20
// 无分支版本
21
int clamp_branchless(int x, int lo, int hi) {
22
    // 利用无符号比较的溢出特性
23
    return x < lo ? lo : (x > hi ? hi : x);
24
    // 更优的位运算版本省略
25
}

1
// 普通循环：每次迭代都有循环分支
2
for (int i = 0; i < n; i++) {
3
    sum += arr[i];
4
}
5

6
// 展开后：循环分支减少 4 倍
7
for (int i = 0; i < n; i += 4) {
8
    sum += arr[i];
9
    sum += arr[i+1];
10
    sum += arr[i+2];
11
    sum += arr[i+3];
12
}
13
// 处理剩余元素...

1
// 原始版本：在热循环中有分支
2
for (int i = 0; i < n; i++) {
3
    if (data[i].type == TYPE_A) {
4
        process_a(&data[i]);
5
    } else {
6
        process_b(&data[i]);
7
    }
8
}
9

10
// 优化：先按类型分组，再分别处理
11
// 分组后每组内部无分支
12
int count_a = 0, count_b = 0;
13
for (int i = 0; i < n; i++) {
14
    if (data[i].type == TYPE_A) group_a[count_a++] = data[i];
15
    else group_b[count_b++] = data[i];
16
}
17
for (int i = 0; i < count_a; i++) process_a(&group_a[i]);
18
for (int i = 0; i < count_b; i++) process_b(&group_b[i]);

1
# 编译并运行排序实验
2
gcc -O2 -o branch_test branch_test.c
3
perf stat -e branches,branch-misses ./branch_test
4

5
# 对比排序前后的 branch-misses 比例

1
#include <stdio.h>
2
#include <time.h>
3

4
#define N 1000000000
5

6
int main() {
7
    int sum = 0;
8

9
    // likely 版本（99% 走 if 分支）
10
    clock_t start = clock();
11
    for (long i = 0; i < N; i++) {
12
        if (__builtin_expect(i >= 0, 1)) {  // 几乎总是 true
13
            sum += i;
14
        }
15
    }
16
    clock_t end = clock();
17
    printf("likely: %.3f 秒\n", (double)(end - start) / CLOCKS_PER_SEC);
18

19
    // unlikely 版本（99% 走 if 分支，但标记为 unlikely）
20
    sum = 0;
21
    start = clock();
22
    for (long i = 0; i < N; i++) {
23
        if (__builtin_expect(i >= 0, 0)) {  // 标记为 unlikely（实际几乎总是 true）
24
            sum += i;
25
        }
26
    }
27
    end = clock();
28
    printf("unlikely: %.3f 秒\n", (double)(end - start) / CLOCKS_PER_SEC);
29

30
    return 0;
31
}

1
#include <stdio.h>
2
#include <time.h>
3

4
// 测试不同数量的分支对预测准确率的影响
5
#define BRANCH_COUNT 4096
6

7
int main() {
8
    // 创建一个包含大量分支的跳转表
9
    void *targets[BRANCH_COUNT];
10
    for (int i = 0; i < BRANCH_COUNT; i++) {
11
        targets[i] = &&label + i;  // 简化示意
12
    }
13

14
    // 测量间接跳转的预测准确率
15
    // 当跳转表大小超过 BTB 容量时，准确率会骤降
16
    // ...
17
    return 0;
18
}