9.1 数据局部性原理

数据局部性，说白了就是“用过的数据，附近的数据，很快还会再用”。CPU缓存就是基于这个原理工作的。

局部性分两种：

• 时间局部性：刚访问过的数据，很可能很快再次访问。比如循环里的计数器。
• 空间局部性：访问了一个数据，它附近的数据也很快会被访问。比如遍历数组。

我个人习惯，在写代码时总会问自己一句：“这个数据接下来会怎么用？” 如果答案是“连续访问”，那就尽量把它放在连续的内存里。

9.1.1 行优先 vs 列优先

来看一个经典例子。假设我们有一个二维数组，要遍历所有元素。

// 行优先遍历 —— 缓存友好
for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
        sum += matrix[i][j];
    }
}

// 列优先遍历 —— 缓存不友好
for (int j = 0; j < N; ++j) {
    for (int i = 0; i < N; ++i) {
        sum += matrix[i][j];
    }
}

我在项目中遇到过类似情况。有一次优化一个图像处理算法，只是把内层循环的索引顺序换了一下，性能提升了3倍。为什么？因为C++的二维数组在内存中是按行存储的。行优先遍历时，每次访问下一个元素都在同一个缓存行里，几乎不浪费。而列优先遍历，每次跳一行，缓存行利用率极低。

9.2 缓存行对齐

缓存行是CPU缓存和内存之间传输的最小单位。通常是64字节。也就是说，你读一个4字节的int，CPU会把包含它的64字节都加载到缓存里。

这带来了两个问题：

1. 伪共享（False Sharing）：两个线程修改不同变量，但这两个变量恰好在同一个缓存行里。结果每次修改都会导致缓存行失效，性能急剧下降。
2. 对齐访问：如果数据跨缓存行边界，一次读取可能需要两次内存访问。

9.2.1 伪共享的坑

我曾经调试过一个多线程程序，性能始终上不去。8个线程跑，还不如2个线程快。查了很久，发现是伪共享在作祟。

// 伪共享版本
struct Data {
    int a;   // 线程1频繁修改
    int b;   // 线程2频繁修改
    // 实际上a和b很可能在同一个缓存行里
};

// 修复版本 —— 缓存行对齐
struct alignas(64) Data {
    int a;
    char padding[60]; // 填充到64字节
    int b;
};

修复之后，性能直接翻了4倍。嗯，这里要注意：alignas(64) 只是让结构体起始地址对齐到64字节，但成员之间的相对位置不变。如果a和b紧挨着，还是会在同一个缓存行里。所以需要手动填充，或者把a和b放到不同的结构体里。

9.2.2 对齐访问的好处

除了避免伪共享，对齐访问本身也能提升性能。现代CPU对对齐访问有优化，不对齐的访问可能触发异常或降速。

我个人习惯，对于频繁访问的热点结构体，都会加上 alignas(64) 或 alignas(128)。比如这样：

struct alignas(64) HotData {
    double values[8];  // 正好64字节
    // 其他成员...
};

这样能保证整个结构体在一个缓存行内，访问效率最高。

9.3 预取指令（__builtin_prefetch）

预取指令，说白了就是提前告诉CPU：“嘿，这个数据你马上要用，先把它加载到缓存里”。这样等真正用到的时候，数据已经在缓存里了，不用等内存。

GCC和Clang都支持 __builtin_prefetch。它的原型是：

void __builtin_prefetch(const void *addr, int rw, int locality);

• addr：要预取的地址
• rw：0表示读，1表示写
• locality：0~3，表示预取数据的“持久性”。0表示用完就扔，3表示尽量留在各级缓存里

9.3.1 什么时候用预取

预取不是万能的。用得不好反而会降低性能。我总结了几条经验：

• 访问模式可预测：比如遍历链表、树，或者步长固定的数组。
• 数据量大：小数据量没必要，CPU的硬件预取已经够用了。
• 延迟敏感：如果每次访问都等内存，预取能显著减少停顿。

举个例子，遍历一个单向链表：

struct Node {
    int data;
    Node* next;
};

void process_list(Node* head) {
    Node* cur = head;
    Node* prefetch = head ? head->next : nullptr;
    while (cur) {
        // 预取下一个节点
        if (prefetch) {
            __builtin_prefetch(prefetch, 0, 1);
        }
        // 处理当前节点
        process(cur->data);
        // 更新预取指针
        cur = cur->next;
        prefetch = cur ? cur->next : nullptr;
    }
}

我在项目中用过这个技巧。当时处理一个百万节点的链表，加上预取后，遍历时间减少了30%。不过要注意，预取指令本身也有开销，如果节点处理逻辑很轻，预取可能反而拖慢速度。

9.3.2 预取的参数选择

locality 参数很关键。我一般这样选：

嗯，这里要注意：不同CPU对locality的解释可能略有差异。最好在目标平台上做微基准测试。

9.4 知识体系总览

下面这张图总结了缓存优化的核心逻辑。我把它画成了流程图，方便你理解各个知识点之间的关系。

9.5 总结与避坑

好了，我们来收个尾。缓存优化其实就三件事：

1. 利用局部性：数据连续排布，顺序访问。
2. 缓存行对齐：避免伪共享，保证对齐访问。
3. 手动预取：在可预测的访问模式中，提前加载数据。

我曾经在一个高并发服务中，因为忽略了伪共享，导致性能瓶颈。后来用 alignas(64) 加上填充，问题迎刃而解。还有一次，我在遍历一个超大的稀疏矩阵时，用了预取指令，把处理时间从5秒降到了3秒。

但我也要提醒你：不要为了优化而优化。先写正确的代码，再用性能分析工具找瓶颈。缓存优化是锦上添花，不是雪中送炭。如果算法本身复杂度高，缓存优化也救不了。

最后，记住一句话：让数据靠近计算，让访问变得连续。你的CPU会感谢你的。