1
#include <chrono>
2
#include <vector>
3
#include <iostream>
4

5
// 测试：连续访问 vs 跳跃访问
6
constexpr int SIZE = 1024 * 1024 * 64;  // 64M 个 int = 256MB
7

8
void sequential_access(std::vector<int>& data) {
9
    long long sum = 0;
10
    for (int i = 0; i < SIZE; i++) {
11
        sum += data[i];          // 连续访问 → 每次 Cache Line 装 16 个 int
12
    }
13
}
14

15
void strided_access(std::vector<int>& data, int stride) {
16
    long long sum = 0;
17
    for (int i = 0; i < SIZE; i += stride) {
18
        sum += data[i];          // 跳跃访问 → 每个 Cache Line 只用 1 个 int
19
    }
20
}
21

22
// 结果 (Intel i7)：
23
// 连续访问:   ~10ms   (每个 Cache Line 16 次命中)
24
// stride=16:  ~10ms   (与连续相同——刚好每个 Cache Line 一个 int)
25
// stride=1:   ~10ms   (连续 = stride=1，最佳)
26
// stride=8:   ~20ms   (每 32B 一次访问，命中率 50%)
27
// stride=64:  ~50ms   (每次访问都在不同 Cache Line → 全部 miss)

1
// ❌ 跨 Cache Line 访问——一次读触发两次缓存加载
2
struct Misaligned {
3
    char padding[60];
4
    int64_t value;  // 这个 value 跨了两个 Cache Line！
5
};
6

7
// ✅ 对齐到 Cache Line 边界
8
struct alignas(64) Aligned {
9
    char padding[60];
10
    int64_t value;  // 整个结构在一个 Cache Line 内
11
};
12
static_assert(sizeof(Aligned) % 64 == 0);
13

14
// 对于热路径上频繁访问的数据，对齐到 64 字节可以：
15
// 1. 保证一次加载不跨 Cache Line
16
// 2. 避免伪共享（见 4.3.3）

1
#include <atomic>
2
#include <thread>
3
#include <chrono>
4

5
// ❌ 伪共享版本
6
struct CounterPair_Bad {
7
    std::atomic<int64_t> counter_a{0};  // offset 0
8
    std::atomic<int64_t> counter_b{0};  // offset 8
9
    // counter_a 和 counter_b 在同一个 64B Cache Line 中！
10
    // 线程 A 写 counter_a → 线程 B 的整个 Cache Line 失效
11
    // 线程 B 写 counter_b → 线程 A 的整个 Cache Line 失效
12
};
13

14
// ✅ 避免伪共享版本
15
struct alignas(64) CounterPair_Good {
16
    std::atomic<int64_t> counter_a{0};   // offset 0-7
17
    // padding[56]  →  填充到 64 字节边界
18
    char _pad1[64 - sizeof(int64_t)];    // offset 8-63
19
    std::atomic<int64_t> counter_b{0};   // offset 64-71
20
    char _pad2[64 - sizeof(int64_t)];    // offset 72-127
21
    static_assert(sizeof(CounterPair_Good) == 128);
22
    static_assert(alignof(CounterPair_Good) == 64);
23
};
24

25
// C++17 标准方式
26
struct CounterPair_Modern {
27
    alignas(std::hardware_destructive_interference_size)
28
        std::atomic<int64_t> counter_a{0};
29
    alignas(std::hardware_destructive_interference_size)
30
        std::atomic<int64_t> counter_b{0};
31
};

1
// 测试伪共享的性能影响
2
template<typename CounterPair>
3
void benchmark_false_sharing() {
4
    CounterPair counters;
5
    constexpr int ITER = 100'000'000;
6

7
    auto start = std::chrono::high_resolution_clock::now();
8

9
    std::thread t1([&]() {
10
        for (int i = 0; i < ITER; i++) {
11
            counters.counter_a.fetch_add(1, std::memory_order_relaxed);
12
        }
13
    });
14
    std::thread t2([&]() {
15
        for (int i = 0; i < ITER; i++) {
16
            counters.counter_b.fetch_add(1, std::memory_order_relaxed);
17
        }
18
    });
19

20
    t1.join();
21
    t2.join();
22

23
    auto end = std::chrono::high_resolution_clock::now();
24
    auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
25

26
    // 典型结果 (两核同时写)：
27
    // CounterPair_Bad:    ~3000ms  (伪共享 → MESI 协议来回失效)
28
    // CounterPair_Good:   ~400ms   (各自独立 Cache Line → 无干扰)
29
    // 性能差距 ~7.5x！
30
}

1
CPU 用分支预测器来猜测分支结果，提前填充流水线：
2

3
1. 静态预测 (Static Prediction)
4
   - 向后跳转（循环）→ 预测跳转
5
   - 向前跳转（if/else）→ 预测不跳转
6
   - 简单但准确率低
7

8
2. 动态预测 (Dynamic Prediction)
9
   - BTB (Branch Target Buffer)：缓存分支目标地址
10
   - BHB (Branch History Buffer)：记录分支历史
11
   - 两级自适应预测器：根据过去 N 次的结果模式来预测
12

13
3. 现代 CPU 的预测器
14
   - 使用神经网络/感知器预测器
15
   - 预测准确率 > 95%
16

17
分支预测失败 (Branch Misprediction) 的代价：
18
→ 流水线中所有已取指但未完成执行的指令全部作废
19
→ 从正确路径重新取指
20
→ 典型代价：15-20 cycles
21
→ 最坏情况（如间接跳转，虚函数调用）：30+ cycles

1
// ❌ 不可预测的分支——预测器无能为力
2
std::vector<int> data = generateRandomData();
3
int sum = 0;
4
for (int x : data) {
5
    if (x > 0) {           // 随机数据 → 分支结果随机
6
        sum += x;           // → 预测准确率 ~50%
7
    }                       // → 大量流水线冲刷
8
}
9

10
// ✅ 排序后——预测器可以学到规律
11
std::sort(data.begin(), data.end());
12
for (int x : data) {
13
    if (x > 0) {           // 先全是 false，然后全是 true
14
        sum += x;           // → 预测准确率 ~100%
15
    }                       // → 几乎没有冲刷
16
}
17

18
// 典型结果（100MB 数据）：
19
// 随机:  ~80ms  (50% mispredict → 大量冲刷)
20
// 排序:  ~30ms  (几乎 0 mispredict)
21
// 差距 ~2.5x——分支预测失败是真实的性能杀手

1
// C++20 给编译器的分支提示
2
if (__builtin_expect(ptr != nullptr, 1)) {   // GCC/Clang
3
    // 大概率走这里
4
}
5

6
// C++20 属性
7
if (ptr != nullptr) [[likely]] {    // 大概率走这里
8
    process(ptr);
9
} else [[unlikely]] {               // 极少走这里
10
    handle_error();
11
}
12

13
// 编译器的优化：
14
// - [[likely]] 路径的代码放在紧邻位置（减少跳转）
15
// - [[unlikely]] 路径的代码放在函数的冷区域（不影响指令缓存）

1
指令级并行 (Instruction-Level Parallelism)：
2
CPU 同时在流水线中执行多条指令——前提是这些指令之间没有依赖。
3

4
超标量 (Superscalar)：
5
同一时钟周期发射多条指令到不同的执行单元。
6
例：Intel Core 可以同时执行 4 条整数指令 + 2 条浮点指令 + 2 条访存指令。
7

8
乱序执行 (Out-of-Order Execution)：
9
CPU 按顺序取指令，但不按顺序执行。
10
→ 遇到依赖时，后面的独立指令可以先执行
11
→ 通过寄存器重命名消除「假依赖」（WAR/WAW）
12
→ 重排序缓冲区 (ROB) 保证「看起来」是按顺序执行的
13

14
数据依赖的类型：
15
- RAW (Read After Write)：真依赖 → 必须等待
16
- WAR (Write After Read)：假依赖 → 寄存器重命名消除
17
- WAW (Write After Write)：假依赖 → 寄存器重命名消除

1
// 依赖链 → 限制 ILP
2
float sum = 0;
3
for (int i = 0; i < N; i++) {
4
    sum += data[i];      // 每次加法都依赖前一次的结果
5
}                        // → 循环携带依赖 (Loop-Carried Dependence)
6
                         // → 无法并行，每周期最多完成一次加法
7

8
// 打破依赖链 → 利用 ILP
9
float sum1 = 0, sum2 = 0, sum3 = 0, sum4 = 0;
10
for (int i = 0; i < N; i += 4) {
11
    sum1 += data[i];     // 四条独立的加法链
12
    sum2 += data[i+1];   // 每条链之间没有依赖
13
    sum3 += data[i+2];   // → CPU 可以同时执行
14
    sum4 += data[i+3];   // → 接近 4x 吞吐量
15
}
16
float sum = sum1 + sum2 + sum3 + sum4;  // 最后合并
17

18
// 编译器优化标志：-funroll-loops 自动做循环展开

1
// ===== AoS (Array of Structures) =====
2
struct Entity_AoS {
3
    float pos_x, pos_y, pos_z;     // 12B
4
    float vel_x, vel_y, vel_z;     // 12B
5
    float health;                   // 4B
6
    char name[32];                  // 32B
7
    int flags;                      // 4B
8
    // sizeof = 64B —— 刚好一个 Cache Line 一个 Entity
9
};
10

11
std::vector<Entity_AoS> entities(10000);
12

13
// 遍历所有实体的位置（如相机裁剪）
14
for (auto& e : entities) {
15
    e.pos_x += e.vel_x * dt;   // 访问 pos_x → 加载整个 64B Entity
16
    e.pos_y += e.vel_y * dt;   // 但 name[32]、flags 也被加载了——浪费！
17
    e.pos_z += e.vel_z * dt;   // 一个 Cache Line 只更新 12B 有效数据
18
}
19
// 缓存利用率 ~12/64 = 18.75%
20

21
// ===== SoA (Structure of Arrays) =====
22
struct MovementSystem {
23
    std::vector<float> pos_x;   // 每个数组独立、连续
24
    std::vector<float> pos_y;
25
    std::vector<float> pos_z;
26
    std::vector<float> vel_x;
27
    std::vector<float> vel_y;
28
    std::vector<float> vel_z;
29
} movement;
30

31
// 遍历所有位置
32
for (int i = 0; i < N; i++) {
33
    movement.pos_x[i] += movement.vel_x[i] * dt;  // pos_x 连续
34
}   // 一个 Cache Line (64B) 装 16 个 float！
35
    // → 16 次操作 1 次 cache miss
36

37
// 缓存利用率 ~100%
38
// 性能差距：遍历 100 万个实体时，SoA 比 AoS 快 ~4-6 倍

1
// 进一步优化：批处理 + SIMD
2
#include <xmmintrin.h>  // SSE
3

4
void update_positions_sse(std::vector<float>& px,
5
                          const std::vector<float>& vx,
6
                          float dt, int count) {
7
    __m128 dt4 = _mm_set1_ps(dt);
8

9
    for (int i = 0; i < count; i += 4) {
10
        // 一次加载 4 个 float (16B = 128bit SSE 寄存器)
11
        __m128 pos = _mm_loadu_ps(&px[i]);
12
        __m128 vel = _mm_loadu_ps(&vx[i]);
13

14
        // 一次完成 4 个 pos += vel * dt
15
        pos = _mm_add_ps(pos, _mm_mul_ps(vel, dt4));
16

17
        _mm_storeu_ps(&px[i], pos);
18
    }
19
    // SoA 布局让 SIMD 可以直接使用——数据已连续排列
20
    // AoS 布局需要先 gather → 完全无法 SIMD 化
21
}

1
// 行为树节点——传统 OOP 实现
2
class BTNode {
3
public:
4
    virtual Status tick(Entity& e) = 0;  // 虚函数 → 间接跳转
5
};
6

7
// 行为树遍历
8
Status run_behavior_tree(Entity& entities[], int count) {
9
    for (int i = 0; i < count; i++) {
10
        // 每个 Entity 的行为树可能在不同节点
11
        // → tick() 是虚函数调用 → 间接跳转 → BTB 难以预测
12
        // → 每个 Entity 的分支预测都不同 → 大量 mispredict
13
        root->tick(entities[i]);
14
    }
15
}
16

17
// 优化方案：按行为状态对 Entity 分组 (Grouping by State)
18
enum class AIState { IDLE, PATROL, CHASE, ATTACK, FLEE };
19

20
struct AISystem_SoA {
21
    std::vector<Entity*> entities_by_state[5];  // 每种状态一个数组
22

23
    void update() {
24
        // 同状态的 Entity 在一起处理
25
        for (auto* e : entities_by_state[AIState::IDLE]) {
26
            updateIdle(e);    // 所有 IDLE 实体 → 分支预测 100% 命中
27
        }
28
        for (auto* e : entities_by_state[AIState::CHASE]) {
29
            updateChase(e);   // 所有 CHASE 实体 → 分支预测 100% 命中
30
        }
31
        // 而不是：for each entity → switch(state) → 预测率 ~20%
32
    }
33
};
34

35
// 效果：从 ~60% 分支预测准确率提升到 ~98%
36
// 游戏 AI 中 ~30% 的性能提升来自这种批处理分组