Cache 友好的代码

Cache 友好的代码

图书馆有几千万本书，但你的书桌只能放 10 本。聪明的做法是：一次去书架取一批主题相关的书放到桌上，接下来几个小时都在这堆书里翻。每次需要一本书就跑一趟书架，那效率会低到崩溃。

CPU 面临同样的问题：内存巨大而缓存极小。Cache 友好的代码，就是尽量"把相关的书放在一起"——每次从内存取来一整个 cache line（64 字节）时，都能被充分利用。写 Cache 友好的代码，有时候比切换到更快的算法还有效。

Level 1：建立直觉

Cache 的基本原理

CPU 访问内存时，不是一个字节一个字节取，而是一次取一整个 cache line（64 字节）。

内存中的数组：
[0][1][2][3][4][5][6][7][8][9][10][11][12][13][14][15]...
└────────────────┘ └────────────────┘
     cache line 0        cache line 1

访问 arr[0] → 加载 cache line 0（[0]-[15] 全部进缓存）
访问 arr[1] → 命中！（已在缓存中）
访问 arr[2] → 命中！
...
访问 arr[17] → 未命中，加载新的 cache line

访问顺序决定了缓存效率：

顺序访问：arr[0], arr[1], arr[2], ...
→ 每 16 个元素（int32）才有 1 次 cache miss
→ cache 命中率约 93.75%

随机访问：arr[500], arr[32000], arr[100], ...  
→ 每次访问几乎都是 cache miss
→ cache 命中率接近 0%

性能差距：可以超过 100 倍！

行优先 vs 列优先访问

矩阵（二维数组）在内存中按**行优先（Row-Major）**存储（C/C++/Java）：

int matrix[3][3]:
内存中的存储顺序：
[00][01][02][10][11][12][20][21][22]
├── 第0行 ──┤├── 第1行 ──┤├── 第2行 ──┤

行优先访问（好）：

// 按行遍历：顺序访问内存
for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        sum += matrix[i][j];  // 按内存顺序访问：cache友好
    }
}

列优先访问（差）：

// 按列遍历：跳跃访问内存
for (int j = 0; j < N; j++) {
    for (int i = 0; i < N; i++) {
        sum += matrix[i][j];  // 每次跳 N 个元素：cache 不友好
    }
}

N=1000 的矩阵（4MB），在 L3 cache 容量 8MB 的 CPU 上：
行优先：约 2ms
列优先：约 80ms  ← 40倍差距！

局部性原理

Cache 友好的核心概念是局部性（Locality）：

时间局部性：刚用过的数据很快还会用（如循环变量 i）。 空间局部性：访问了某个地址，附近的地址也可能被访问（如数组顺序访问）。

硬件预取器（Prefetcher）就是利用空间局部性：它检测到你在顺序访问一个数组，就在你访问之前提前把下一批 cache line 加载好。

硬件预取的工作原理：
t=0: 访问 arr[0]  → 加载 cache line 0
     预取器检测到顺序访问 → 后台偷偷加载 cache line 1, 2, 3...
t=1: 访问 arr[1]  → 命中（预取好了）
t=2: 访问 arr[16] → 命中（预取好了）
...

如果访问模式随机（链表、树遍历）→ 预取器失效 → 每次都等

Level 2：原理剖析

数据结构布局

数组的结构（Array of Structures，AoS）：

struct Point {
    float x, y, z;
    int color;
    int id;
    // 总共 20 字节
};

Point points[1000000];  // 数组的结构

// 计算所有点的 x 坐标之和
float sum_x = 0;
for (int i = 0; i < N; i++) {
    sum_x += points[i].x;   // 每次访问 20 字节的 Point，只用了 4 字节的 x
    // 64 字节 cache line 里有 3 个 Point，但只用了 3 个 x
}
// 有效数据利用率：4/20 = 20%（每次加载 20 字节，只用 4 字节）

结构的数组（Structure of Arrays，SoA）：

struct Points {
    float x[1000000];   // 所有 x 连续存储
    float y[1000000];
    float z[1000000];
    int   color[1000000];
    int   id[1000000];
};

Points points;

// 计算所有点的 x 坐标之和
float sum_x = 0;
for (int i = 0; i < N; i++) {
    sum_x += points.x[i];   // 顺序访问 x 数组
    // 64 字节 cache line 里有 16 个 x 值，全部被使用！
}
// 有效数据利用率：16/16 = 100%

AoS 适合需要同时访问一个对象所有字段的场景（如"处理一个 Point"）。SoA 适合需要对某个字段大批量处理的场景（如"对所有点的 x 坐标做计算"——GPU、SIMD 向量化的标准方式）。

实测性能差距（N=10^7，Intel i7-12700K）：

仅访问 x 字段：
  AoS：约 85ms（cache 利用率低）
  SoA：约 22ms（cache 利用率满）
  差距：3.9 倍

矩阵乘法优化：Tiling/Blocking

N×N 矩阵乘法 C = A × B：

// 朴素实现（cache 不友好）
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 按列访问！cache 极差
        }
    }
}

N=1000，矩阵大小 4MB 各：
朴素实现：~5秒
优化实现：~0.3秒（17倍提升）

优化方案1：交换循环顺序（ikj 代替 ijk）：

// ikj 顺序：B 按行访问（cache 友好）
for (int i = 0; i < N; i++) {
    for (int k = 0; k < N; k++) {
        float a_ik = A[i][k];
        for (int j = 0; j < N; j++) {
            C[i][j] += a_ik * B[k][j];  // B[k][j] 顺序访问！
        }
    }
}
// 与朴素 ijk 相比：3-5倍提升（仅靠改循环顺序）

优化方案2：分块（Tiling）——让工作集适配 cache：

#define TILE 64   // 选 tile 大小，使 3 个 tile 的数据能装入 L2 cache

// 分块矩阵乘法
for (int i = 0; i < N; i += TILE) {
    for (int j = 0; j < N; j += TILE) {
        for (int k = 0; k < N; k += TILE) {
            // 对 TILE×TILE 的子块做乘法，全部数据在 cache 中
            for (int ii = i; ii < min(i+TILE, N); ii++) {
                for (int jj = j; jj < min(j+TILE, N); jj++) {
                    float sum = 0;
                    for (int kk = k; kk < min(k+TILE, N); kk++) {
                        sum += A[ii][kk] * B[kk][jj];
                    }
                    C[ii][jj] += sum;
                }
            }
        }
    }
}

分块确保 TILE×TILE 的子矩阵（64×64 = 16KB）能完全装入 L1 或 L2 cache，整个乘法过程不出现 L3 miss。

TILE 大小的选择策略：

L1 cache = 32KB，需要装 3 个 TILE（A、B、C 各一块）：
3 × TILE² × 4 bytes ≤ 32KB
TILE² ≤ 2730
TILE ≤ 52

实践中常用 TILE = 32 或 64（兼顾 cache 和对齐）
不同 CPU 最优 TILE 不同，需要实测

预取（Prefetching）

硬件预取器会自动检测顺序访问模式并提前加载。对于非规律的访问，可以显式告诉 CPU 提前加载：

#include <immintrin.h>

for (int i = 0; i < N; i++) {
    // 提前预取 20 个元素后的 cache line
    __builtin_prefetch(&arr[i + 20], 0, 1);
    // 参数：地址，读=0/写=1，时间局部性（0=不再需要，3=高度复用）
    
    process(arr[i]);  // 处理当前元素时，20个元素后的已经在缓存中了
}

实际效果：当处理时间 > 内存延迟（约 100ns），预取可以完全隐藏内存延迟。

预取距离的选择：

预取太近：来不及加载（预取距离 < 内存延迟/处理时间）
预取太远：缓存被占满，驱逐了其他有用数据

经验公式：
  预取距离 ≈ 内存延迟 / 每元素处理时间
  内存延迟 ≈ 200 周期（约 100ns @ 2GHz）
  如果每个元素处理需要 10 周期：预取 200/10 = 20 个元素前

缓存对齐

结构体的成员有时会因为对齐而产生意外的"填充"（padding），导致数据变稀疏：

// 糟糕的结构布局（总大小 24 字节，有 7 字节填充）
struct Bad {
    char   a;    // 1字节
    // 7字节填充！（为了让 double 对齐到 8 字节边界）
    double b;    // 8字节
    int    c;    // 4字节
    // 4字节填充（为了让 struct 大小是 8 的倍数）
};
// sizeof(Bad) = 24，1个 cache line 只能装 2 个这样的结构

// 优化后（总大小 16 字节，无填充）
struct Good {
    double b;    // 8字节（最大对齐字段放前面）
    int    c;    // 4字节
    char   a;    // 1字节
    // 3字节填充（sizeof = 16）
};
// sizeof(Good) = 16，1个 cache line 装 4 个！

规则：将字段按大小降序排列，大字段在前，小字段在后——减少填充，提高 cache 密度。

# 用 pahole 工具分析结构体填充
pahole ./program | grep -A 20 "struct Bad"
# 输出：
# struct Bad {
#     char               a;      /*  0     1 */
#     /* XXX 7 bytes hole, try to pack */
#     double             b;      /*  8     8 */
#     int                c;      /* 16     4 */
#     /* size: 24, cachelines: 1, members: 3 */
#     /* sum members: 13, holes: 1, sum holes: 7 */
# };

Level 3 · 规范怎么定义的（资深）

缓存行为的形式化分析

Cache 行为的理论分析基于 三类未命中模型（3C Model），由 Mark Hill 在 1987 年的博士论文中提出：强制未命中（Compulsory/Cold Miss，第一次访问某数据）、容量未命中（Capacity Miss，工作集超过 Cache 总大小）和冲突未命中（Conflict Miss，多个地址映射到同一组，即使 Cache 总容量足够）。这个模型为分析和优化 Cache 性能提供了系统化的框架。

矩阵分块（Tiling/Blocking）优化的理论基础来自 Monica Lam 1991 年的论文 "The Cache Performance and Optimizations of Blocked Algorithms"。该论文证明了对于 N×N 矩阵乘法，当分块大小 B 满足 3B² ≤ Cache 容量时，Cache Miss 数从 O(N³) 降至 O(N³/B)——这意味着 Cache 大一倍，Miss 数减少一倍。GCC 和 LLVM 的循环优化 pass（如 -floop-nest-optimize、Polly）会自动进行分块变换，其分块大小的选择基于目标 CPU 的 Cache 参数。

硬件预取的行为由 CPU 微架构决定，不在 ISA 规范中定义。但 软件预取指令有明确的 ISA 定义：x86 的 PREFETCHT0/T1/T2/NTA（分别预取到 L1/L2/L3/非时序缓冲区）、ARM 的 PRFM 指令。Intel 的优化手册详细描述了何时使用软件预取有益（通常是在硬件预取器无法识别的不规则访问模式下），以及预取距离的推荐值（提前 100-300 个周期发出预取，对应提前遍历 2-8 个缓存行）。

Level 4 · 边界与陷阱（所有人）

陷阱 1：AoS vs SoA——数据布局决定缓存效率

"Array of Structures"（AoS）和 "Structure of Arrays"（SoA）是两种常见的数据布局。假设你有一百万个粒子，每个粒子有 x、y、z 坐标和质量。AoS 布局是 [{x,y,z,mass}, {x,y,z,mass}, ...]，SoA 布局是 {[x,x,...], [y,y,...], [z,z,...], [mass,mass,...]}。如果你的计算只需要 x 坐标，AoS 布局每加载一条缓存行（64 字节）只有 1/4 的数据是有用的（其余是 y、z、mass），而 SoA 布局每条缓存行 100% 是有用的 x 坐标。在 SIMD（如 AVX-512）计算中，SoA 的优势更加明显——连续的 x 坐标可以直接加载到向量寄存器中。游戏引擎（如 Unity 的 DOTS/ECS 框架）和科学计算库广泛使用 SoA 布局。

陷阱 2：链表是 Cache 的天敌

链表的每个节点通过指针连接，节点在内存中的位置取决于 malloc() 的分配策略——通常是散布在堆的各个位置。遍历链表时，每次跟随指针（pointer chasing）几乎都是 Cache Miss（约 50-100ns），而遍历数组时，连续的元素位于同一条或相邻的缓存行中（约 1ns/元素）。在 1000 万个元素的遍历中，链表可能比数组慢 50-100 倍。这就是为什么 Bjarne Stroustrup（C++ 之父）多次公开建议"除非有特殊原因，否则使用 vector 而不是 list"。如果确实需要频繁的中间插入/删除，可以考虑使用"展开链表"（unrolled linked list），每个节点存储一个小数组而非单个元素。

陷阱 3：多线程遍历共享数据时的 Cache Thrashing

多个线程同时读取同一个大数组的不同部分，直觉上应该是完全并行的。但如果线程数 × L1 Cache 大小 < 数组大小，每个线程频繁加载自己需要的数据会驱逐其他线程已缓存的数据（尤其在共享 L3 Cache 层面）。更隐蔽的是，即使线程只是读取数据，如果数据恰好与其他线程的写入位于同一缓存行，MESI 协议仍会触发缓存行无效化。解决方案包括：对数据进行分区使每个线程的工作集独立、使用线程本地副本（thread-local copy）、或调整线程数使总工作集不超过 L3 Cache 容量。