第四章：缓存友好型编程——让数据在CPU眼皮底下跑

说到性能优化，很多人第一反应是算法复杂度、编译器优化、多线程并行。但说实话，我见过太多项目，算法选得不错，代码写得也漂亮，可跑起来就是慢。为什么？因为数据没在CPU眼皮底下待着。

CPU缓存，这个离计算单元最近的存储层，才是真正的性能命门。你想想看，CPU主频已经到GHz级别，但内存访问延迟还在几十纳秒级别。这中间的鸿沟，全靠缓存来填。如果代码写得不好，CPU大部分时间都在等数据，那再好的算法也白搭。

4.1 CPU缓存层次结构——三级缓存，一级比一级快

我刚开始做性能调优时，对缓存的理解就是“有个快点的内存”。直到有一次，我在一个图像处理项目里发现，仅仅改变数据访问顺序，性能提升了8倍。从那以后，我才真正开始研究缓存结构。

现代CPU通常有三层缓存：

缓存层级	典型大小	访问延迟	特点
L1	32KB（指令）+ 32KB（数据）	~1ns（3-4个时钟周期）	每个核心独享，速度最快
L2	256KB - 1MB	~3ns（10-12个时钟周期）	每个核心独享，容量适中
L3	8MB - 32MB	~10ns（30-40个时钟周期）	所有核心共享，容量最大

嗯，这里要注意：L1缓存分指令缓存和数据缓存。指令缓存存的是你写的代码，数据缓存存的是你操作的数据。两者分开，互不干扰。我个人习惯在写热点代码时，会刻意让代码体积小一点，尽量塞进L1指令缓存。

4.2 缓存行与局部性原理——64字节的黄金法则

缓存不是按字节存的，而是按“缓存行”存的。现代CPU的缓存行大小通常是64字节。这意味着，你访问一个int变量，CPU会把相邻的64字节全部拉进缓存。

为什么会这样？因为局部性原理。程序访问数据时，往往有规律：

• 时间局部性：刚访问过的数据，很可能马上再访问一次。比如循环里的计数器。
• 空间局部性：刚访问过的数据附近的数据，很可能接下来会被访问。比如数组遍历。

我举个例子你就明白了：

// 缓存友好版本：按行遍历
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];  // 跳跃内存访问
    }
}

按行遍历时，每次访问matrix[i][j]，CPU会把matrix[i][j]到matrix[i][j+15]（假设int是4字节）全部拉进缓存。下一个循环直接命中缓存。按列遍历呢？每次跳N个int，缓存行里的数据全浪费了，每次都要重新从内存拉数据。

4.3 缓存命中与未命中——命中是天堂，未命中是地狱

缓存命中，就是CPU要的数据已经在缓存里了。缓存未命中，就是CPU要去内存里拿。两者的性能差距，大概是一个数量级。

缓存未命中分三种：

• 强制未命中：第一次访问数据，缓存里肯定没有。这是不可避免的。
• 容量未命中：缓存太小，装不下所有数据。比如你处理一个1GB的数组，L3缓存才32MB，肯定装不下。
• 冲突未命中：多个数据映射到同一个缓存行，互相踢来踢去。这是最坑的，往往是因为数据结构设计不合理。

你想想看，如果两个热点数据恰好映射到同一个缓存行，每次访问都会把对方踢出去。这就是所谓的“缓存行颠簸”。

4.4 缓存友好的数据结构设计——从源头解决问题

数据结构设计，是缓存友好编程的起点。我见过太多人用链表存热点数据，结果遍历时缓存未命中率爆表。说白了，链表节点在内存里是散落的，每次访问都要去内存拉数据。

以下是我总结的几个缓存友好设计原则：

4.4.1 用数组代替链表

数组是连续内存，遍历时天然缓存友好。链表呢？每个节点可能分散在内存各处。如果你必须用链表，考虑用“数组池”来管理节点：

// 缓存友好的链表实现：用数组池
struct Node {
    int data;
    int next;  // 用索引代替指针
};

Node pool[1024];  // 连续内存
int head = -1;

// 遍历时，pool是连续内存，缓存友好
for (int i = head; i != -1; i = pool[i].next) {
    process(pool[i].data);
}

4.4.2 结构体对齐与填充

结构体成员顺序会影响缓存利用率。把经常一起访问的成员放在一起：

// 不友好：热点数据分散
struct Entity {
    bool is_alive;    // 1字节
    int health;       // 4字节
    char name[32];    // 32字节
    float position_x; // 4字节
    float position_y; // 4字节
};

// 友好：热点数据集中
struct Entity {
    float position_x; // 4字节
    float position_y; // 4字节
    int health;       // 4字节
    bool is_alive;    // 1字节
    char name[32];    // 32字节
};

嗯，这里要注意：把经常一起访问的成员放在结构体开头，这样它们更可能落在同一个缓存行里。

4.4.3 数据分拆：结构体数组 vs 数组结构体

如果你只访问结构体里的某个字段，考虑用“数组结构体”代替“结构体数组”：

// 结构体数组：访问health时，整个Entity都被拉进缓存
struct Entity entities[1024];
for (int i = 0; i < 1024; ++i) {
    if (entities[i].health < 0) {
        // 只用了health，但position_x/y也被拉进来了
    }
}

// 数组结构体：只拉health数组，缓存利用率更高
struct Entities {
    float position_x[1024];
    float position_y[1024];
    int health[1024];
    bool is_alive[1024];
};

Entities entities;
for (int i = 0; i < 1024; ++i) {
    if (entities.health[i] < 0) {
        // 只访问health数组，缓存行里全是health
    }
}

4.5 实战：缓存友好的矩阵转置

最后，我分享一个实战案例。矩阵转置，看起来简单，但写不好性能差很多：

// 缓存不友好版本
void transpose_bad(int* mat, int N) {
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            int tmp = mat[i * N + j];
            mat[i * N + j] = mat[j * N + i];
            mat[j * N + i] = tmp;
        }
    }
}

// 缓存友好版本：分块转置
void transpose_good(int* mat, int N, int block_size) {
    for (int i = 0; i < N; i += block_size) {
        for (int j = 0; j < N; j += block_size) {
            for (int ii = i; ii < i + block_size && ii < N; ++ii) {
                for (int jj = j; jj < j + block_size && jj < N; ++jj) {
                    int tmp = mat[ii * N + jj];
                    mat[ii * N + jj] = mat[jj * N + ii];
                    mat[jj * N + ii] = tmp;
                }
            }
        }
    }
}

分块转置的核心思想是：让每次操作的数据块都能塞进L1缓存。block_size一般取64字节除以元素大小。比如int是4字节，block_size取16，这样每个块正好是64字节，一个缓存行就能装下。

好了，这一章的内容就到这里。缓存友好编程，说白了就是尊重CPU的工作方式。你让数据在缓存里待着，CPU就给你好脸色。你让数据到处乱跑，CPU就让你等。就这么简单。

---

公众号：蓝海资料掘金营，微信 deep3321