📚 课程目录第3章缓存友好型算法设计

缓存友好型算法设计：空间局部性与时间局部性、循环分块、数据预取、避免缓存抖动

大家好，我是你们的老朋友。今天咱们聊一个特别实在的话题——缓存友好型算法设计。

说实话，我见过太多工程师，代码写得飞起，算法复杂度分析得头头是道，结果一跑性能测试，直接被打回原形。为什么？因为现代 CPU 和内存之间有个巨大的鸿沟——缓存。你写的代码如果不尊重缓存，那再好的算法也是白搭。

这一章，我就把压箱底的经验掏出来，跟你聊聊怎么让代码“喂饱”缓存。

1. 空间局部性与时间局部性：缓存的两个基本法则

先问个问题：为什么连续访问数组比随机访问快那么多？

答案就俩字——局部性。

空间局部性：你访问了一个内存地址，接下来很可能访问它附近的地址。比如遍历数组，CPU 会把一整块数据都拉到缓存里。
时间局部性：你访问了一个数据，过一会儿很可能再次访问它。比如循环里的累加变量，它一直待在寄存器或 L1 缓存里。

我有个习惯：写代码前先画个内存访问轨迹图。你想想看，如果每次访问都跳来跳去，缓存根本来不及预取，那性能能好吗？

核心原则：让数据访问模式尽量连续、尽量重复。这就是缓存友好的本质。

2. 循环分块（Loop Tiling）：把大问题切成小方块

循环分块，说白了就是把大循环拆成小循环，让每次处理的数据块刚好能塞进缓存。

我记得有一次优化矩阵乘法，原始代码长这样：

// 原始版本：大循环，缓存完全不友好
for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
        for (int k = 0; k < N; k++)
            C[i][j] += A[i][k] * B[k][j];

这个版本的问题在哪？B 矩阵是按列访问的，每次访问 B[k][j] 都会跳一大段内存。当 N 很大时，缓存根本装不下，频繁发生缓存缺失。

改成循环分块后：

// 分块版本：每次处理 BLOCK_SIZE 大小的子矩阵
#define BLOCK_SIZE 64

for (int i = 0; i < N; i += BLOCK_SIZE)
    for (int j = 0; j < N; j += BLOCK_SIZE)
        for (int k = 0; k < N; k += BLOCK_SIZE)
            for (int ii = i; ii < i + BLOCK_SIZE; ii++)
                for (int jj = j; jj < j + BLOCK_SIZE; jj++)
                    for (int kk = k; kk < k + BLOCK_SIZE; kk++)
                        C[ii][jj] += A[ii][kk] * B[kk][jj];

你看，现在每次处理的是一个 64×64 的小方块。A 和 B 的子块都能放进 L2 缓存，数据复用率大幅提升。

我的经验：BLOCK_SIZE 不是越大越好。我一般先查 CPU 的 L1/L2 缓存大小，然后让每个分块的数据量不超过缓存的一半。比如 L1 是 32KB，那分块大小就控制在 16KB 以内。

3. 数据预取（Prefetching）：让数据提前到位

预取，就是提前告诉 CPU 你接下来要访问哪些数据，让它先把数据拉到缓存里。

现代 CPU 有硬件预取器，但有时候它猜不准。这时候就需要我们手动干预。

举个例子，遍历链表时，每个节点在内存里是分散的，硬件预取根本没法工作。我曾经在项目中遇到一个链表遍历的性能瓶颈，后来加了预取指令：

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

void process_list(struct Node* head) {
    struct Node* curr = head;
    struct Node* prefetch = head ? head->next : NULL;

    while (curr) {
        // 手动预取下一个节点
        __builtin_prefetch(prefetch, 0, 1);

        // 处理当前节点
        process(curr->data);

        // 更新指针
        curr = prefetch;
        prefetch = prefetch ? prefetch->next : NULL;
    }
}

这里用了 GCC 的 __builtin_prefetch，第二个参数 0 表示读操作，第三个参数 1 表示中等时间局部性。效果很明显，性能提升了将近 30%。

注意：预取不是万能的。预取太早，数据可能被踢出缓存；预取太晚，来不及。我一般让预取指令比实际访问提前 10-20 个 CPU 周期。

4. 避免缓存抖动（Cache Thrashing）：别让缓存“打架”

缓存抖动，就是多个数据块争抢同一个缓存行，导致频繁换入换出。最典型的场景是二维数组按列访问。

来看一个反面教材：

// 按列访问：每次访问都跨越多个缓存行
for (int j = 0; j < N; j++)
    for (int i = 0; i < N; i++)
        sum += matrix[i][j];

这个循环里，每次访问 matrix[i][j] 都会跳到不同的缓存行。当 N 很大时，缓存行被反复替换，性能惨不忍睹。

改成按行访问就好了：

// 按行访问：连续内存，缓存友好
for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
        sum += matrix[i][j];

就这么简单的一改，性能能差出 10 倍以上。

还有一种情况是伪共享。多线程环境下，两个线程修改不同变量，但这两个变量恰好在同一个缓存行里。结果每次修改都会导致缓存行失效，性能急剧下降。

我曾经在一个高并发服务里遇到过这个问题。两个线程分别更新一个结构体的两个字段，结果吞吐量死活上不去。后来我把这两个字段用 __attribute__((aligned(64))) 分开到不同缓存行，问题就解决了。

避坑指南：多线程共享数据时，尽量让每个线程的数据独占一个缓存行。可以用 alignas(64) 或填充字节来隔离。

5. 知识体系总览

下面这张图总结了本章的核心知识点和它们之间的关系：

6. 总结与实战建议

好了，这一章的内容就这些。我最后给你几个实战建议：

先分析，再优化：用 perf 或 valgrind 的 cachegrind 工具看看缓存缺失率。别瞎猜。
从数据布局入手：结构体字段按访问频率排列，热数据放前面。数组优先按行遍历。
分块大小要测试：不同 CPU 的缓存大小不一样。我一般写个脚本自动测试最优分块。
预取要适度：加太多预取指令反而会占用指令缓存，得不偿失。
多线程注意伪共享：用 __attribute__((aligned(64))) 或 padding 隔离热数据。

记住，缓存优化不是玄学，是科学。你只要理解了局部性原理，再配合工具分析，就能写出又快又省内存的代码。