第4章程序员能为缓存做什么

数据局部性优化

章节导读

前三章我们一直在「理解」内存系统：缓存如何工作、虚拟内存如何翻译、NUMA 如何分布。现在到了收获的季节——这一章回答全书最实用的问题：作为一个程序员，我到底能做什么？Drepper 在论文的第 6 章给出了一个振聋发聩的观点：在摩尔定律红利逐渐消退、主频停止增长的时代，软件性能的提升越来越依赖于「让代码适配硬件」，而其中最大的一块红利就藏在缓存里。同一台机器上，缓存友好与缓存敌对的代码之间，性能差距 routinely 达到 10 倍——这相当于免费获得了一台快十倍的机器，唯一的代价是程序员的知识。

优化技术	原理	适用场景	典型加速比	实现难度
AoS→SoA 转换	消除缓存行中的冷数据	批量同字段更新	3-7x	中
热冷数据分离	高频字段紧凑打包	混合访问模式	2-4x	低
循环分块 (Tiling)	工作集适配缓存容量	矩阵运算	2-10x	中
行优先遍历	匹配内存连续布局	多维数组	5-50x	低
伪共享消除	alignas(64) 隔离	多线程计数器	5-10x	低
软件预取	__builtin_prefetch	可预测访问模式	1.5-3x	中
大页 (Huge Pages)	减少 TLB 未命中	大内存应用	1.2-2x	低
链表→数组	消除指针追逐	遍历密集型	10-100x	中

让我们先建立一个正确的心智模型：优化缓存不是零散的技巧堆砌，而是一套有层次的方法论。最底层是数据结构的选择——数组的缓存效率天然碾压链表，这个决策的影响超过之后所有微观优化的总和。中间层是访问模式的组织——行优先还是列优先遍历、循环嵌套的顺序、分块的大小，这些决定了缓存行和 TLB 的利用率。最上层是多线程的数据布局——每个线程的私有数据是否独占缓存行、共享数据的一致性流量有多大，这决定了并行扩展性。伪共享（False Sharing）是最高层问题的典型代表：两个线程各自修改自己的变量，逻辑上毫无共享，却因为变量恰好落在同一个 64 字节缓存行内，导致该行在两个核心的缓存之间被 MESI 协议反复无效化和搬运，性能可能劣化 5-10 倍。这个问题如此隐蔽——代码看起来完全正确，profiler 的 CPU 占用也正常，只有 cache-to-cache 传输计数器能揭露真相——以至于它成为多线程性能调优的「必查项」。

本章还将介绍一些更高级的武器。循环分块（Loop Tiling）通过把大循环切成能装进缓存的小块，同时榨取时间局部性和空间局部性，是矩阵运算优化的基石；缓存无关（Cache-Oblivious）算法用递归分治的方式自动适配所有层级的缓存，无需知道任何硬件参数，Strassen 矩阵乘法和递归矩阵转置是其代表；软件预取指令让程序显式告诉硬件「我马上要用这块数据」，把未命中延迟隐藏在当前计算之后；alignas 和对齐分配则确保关键数据结构不会跨缓存行分裂。最后，我们会系统介绍测量工具链——perf、cachegrind、VTune——因为 Drepper 和所有性能工程师都同意一条铁律：没有测量就没有优化。凭直觉优化缓存几乎总是错的，现代处理器的预取器、乱序执行和缓存层次复杂到超出任何人的直觉。这一章的目标，是让你带着「局部性思维」和「测量习惯」两样工具，回到日常编程中去。

核心概念

空间局部性
时间局部性
伪共享
数据对齐

要点精析

数据局部性优化有一套清晰的方法论层次，按影响力从大到小排列。第一层是算法与数据结构选择：O(n log n) 的数组算法几乎总是胜过 O(log n) 的链表/树算法，直到 n 大到一定程度——因为数组的顺序访问让每次缓存未命中服务 16 个 int，而树的每次跳转几乎必然未命中；B 树取代二叉树成为数据库索引标准，本质就是缓存优化。第二层是数据布局：结构体字段的排列顺序、数组的存储维度顺序、热冷数据分离（把频繁访问的字段集中到结构体前部，让一个缓存行覆盖更多热数据）。第三层是访问模式：循环顺序、遍历方向、分块大小。第四层是对齐与多线程布局：缓存行对齐、伪共享消除。这个层次的意义在于指导优化顺序：先选对数据结构，再调布局，最后才做微观的访问模式优化——在链表上做缓存行对齐是徒劳的，就像在漏水的船上擦地板。

数组与链表的缓存效率对比是数据结构选择的第一课。考虑遍历 n 个元素：数组的元素连续存放，缓存以 64 字节为单位加载，int 数组每 16 个元素才有一次未命中，未命中率约 6%；链表的节点由 malloc 分散分配，相邻节点在内存中的位置基本随机，每次解引用 next 指针都可能触发一次未命中，未命中率接近 100%。实测数据更有说服力：在 3GHz 处理器上顺序累加 100 万个 int，数组版本约 0.3 毫秒，单链表版本约 3-5 毫秒，差距 10 倍以上——尽管两者的「算法复杂度」相同。这个差距随数据量增大而扩大：数据装进 L2 时数组几乎免费，链表仍在为主存未命中买单。当然链表不是没有价值：O(1) 的中间插入删除、不需要连续内存、迭代器稳定性，这些语义优势在特定场景不可替代。工程上的折中方案是「链表语义、数组实现」：侵入式链表配合对象池、std::vector 加索引模拟、B 树/跳表的数组化变体，游戏引擎和高频交易系统中大量使用这类缓存友好的替代结构。

多维数组的遍历顺序是空间局部性最经典的考题。C/C++ 的二维数组按行优先（Row-major）存储：a[i][j] 和 a[i][j+1] 相邻，a[i][j] 和 a[i+1][j] 相距一整行。因此「外层循环走行、内层循环走列」（即固定 i 遍历 j）是顺序访问，缓存行利用率 100%；反过来「外层走列、内层走行」是步长为 N×sizeof(元素) 的跳跃访问，每个缓存行 64 字节只用了 4 字节，利用率 6%，而且当 N×4 是 2 的幂次时还会引发严重的缓存组冲突（多个访问地址映射到同一组，互相驱逐）。矩阵乘法 C=A×B 的三重循环有六种排列，性能差距可达 10 倍：ijk 顺序对 A 行友好但对 B 列不友好，kij 顺序让 A 和 C 都获得列方向的固定行访问，是朴素循环中的较优选择。Fortran 是列优先存储，同样的代码在 Fortran 里最优顺序恰好相反——这提醒我们：遍历顺序必须匹配存储顺序，跨语言移植数值代码时这是头号性能陷阱。

结构体紧凑化（Struct Compaction）通过减少每个对象占用的字节数，让一个缓存行装下更多对象，直接提升有效带宽。手段有三：第一，字段按大小降序排列消除对齐填充——struct { char a; int b; char c; } 占 12 字节（b 前填充 3 字节，c 后填充 3 字节），重排为 { int b; char a; char c; } 只占 8 字节，节省 33%；第二，用更小的类型——能用 int32_t 不用 int64_t，能用 uint8_t 表示的枚举不用 int，指针能换成数组索引（32 位偏移）就换，这在十亿级对象的系统中是数量级的内存节省；第三，热冷分离——把高频访问的字段（如键、状态位）放进主结构体，低频字段（如统计信息、时间戳）拆到并行的辅助数组，主结构体越小，扫描越快。紧凑化的复利效应：对象从 64 字节减到 32 字节，意味着同样 8MB 的 L3 能容纳的对象数翻倍，同样的内存带宽能扫描的行数翻倍，TLB 覆盖的对象数也翻倍——缓存、带宽、TLB 三重收益叠加。用 pahole 工具（ dwarves 包）可以直接分析编译产物中每个结构体的布局、填充和缓存行占用，是紧凑化的必备助手。

循环融合（Loop Fusion）和循环分块（Loop Tiling/Blocking）是两种方向相反但目标一致的循环变换。融合把多个遍历同一数据的循环合并成一个：先循环一次算 a[i]=f(x[i])，再循环一次算 b[i]=g(a[i])，不如一个循环里同时算完——x 和 a 的数据在合并后只加载一次，缓存流量减半，还消除了中间数组。分块则把一个大循环切成小块，使每个块的工作集能装进目标缓存：矩阵乘法的朴素实现中，计算 C 的一个元素需要 A 的一整行和 B 的一整列，N=4096 时工作集远超 L1；分块成 B×B 的小块后（B 通常取 32-64），每个块内 A、B、C 的子块都能驻留 L1，内层循环全部命中。分块大小的选择是艺术：太小则块间切换开销大且外层访问模式碎片化，太大则装不进缓存，经典公式是让「同时活跃的所有数组块」之和略小于目标缓存容量（对矩阵乘法是 3×B²×sizeof < L1）。分块的现代变体是寄存器分块——把最内层展开成 4×4 或 8×8 的微内核，让数据驻留在寄存器里，这正是 BLAS 库（OpenBLAS、MKL）达到 90% 峰值算力的核心技术。

伪共享（False Sharing）是多线程缓存性能的头号杀手，值得完整拆解。原因：MESI 缓存一致性协议以缓存行为粒度工作，核心 A 写入某行时，必须让所有其他核心中该行的副本失效；如果核心 B 频繁写同一行的不同字节，该行就在 A、B 的 L1 之间来回迁移，每次迁移都要走一致性总线（跨 NUMA 节点时走 UPI），一次写操作从 1 个周期膨胀到几十甚至上百个周期。典型场景：线程各写自己的计数器（数组下标不同但相邻）、多线程更新同一结构体的不同字段、无锁队列的头尾指针相邻。检测方法：perf c2c record/report 是专用工具，能直接定位到伪共享的缓存行和代码行；perf stat -e 观察 cache-misses 异常偏高而算法访存量正常也是信号。解决方法按优先级：字段填充（在竞争字段间插入 padding 使各自独占缓存行）、alignas(64) 对齐、线程私有数据加最终归约（每线程本地累加，结束后合并，彻底消除共享写）、重新设计数据结构（SoA 转 AoS 或反之）。一个真实数据点：8 线程各写相邻 int 计数器的基准，加填充后吞吐量提升 6-8 倍——这是所有性能优化中投入产出比最高的改动之一。

对齐（Alignment）是控制数据与缓存行关系的直接手段。C11/C++11 的 alignas 说明符可以施加在类型和变量上：alignas(64) struct Counter { long v; }; 保证每个 Counter 对象从缓存行边界开始；alignas(64) static char buffer[4096]; 让静态数组对齐。动态分配用 aligned_alloc(64, size)（C11）或 posix_memalign（POSIX），C++17 的 operator new 支持对齐参数。为什么对齐如此重要？未对齐的数据可能跨越两个缓存行：一个 8 字节的 long 若起始地址模 64 等于 60，读写它需要访问两个缓存行，未命中时代价翻倍，在 x86 上还有原子性问题——跨行的 lock cmpxchg 不能保证原子性，会触发总线锁，性能骤降百倍。对齐的实践清单：多线程写入的每个独立变量对齐到 64 字节；DMA 缓冲区按页对齐；性能关键的结构体大小最好是 64 的约数或倍数（16、32、64 字节），使对象数组中每个对象与缓存行的关系一致。注意过度对齐的代价：alignas(64) 一个 8 字节对象意味着内存占用膨胀 8 倍，只在确有竞争或跨行问题时使用。另外，缓存行大小并非永远是 64——Apple Silicon 是 128 字节，用 std::hardware_destructive_interference_size（C++17）或 sysconf(_SC_LEVEL1_DCACHE_LINESIZE) 获取可移植的值。

缓存无关（Cache-Oblivious）算法是 1999 年 Frigo 等人提出的优雅思想：通过递归分治编写的算法，无需知道任何缓存参数（容量、行大小、层次数），就能在所有层级的缓存上自动达到接近最优的性能。原理是递归的自相似性：一个把问题对半分解的算法，在某个递归层级上子问题恰好装进 L1，在更浅的层级恰好装进 L2、L3——同一份代码自动适配整个存储层次，甚至适配未来硬件。经典例子是递归矩阵转置：把 N×N 矩阵分成四个象限，递归转置每个象限并交换反对角象限，递归到 16×16 左右时切换为朴素循环；实测其性能与精心调优的固定分块版本相当，但完全不需要选择分块参数。另一个例子是 Strassen 矩阵乘法：把复杂度从 O(n³) 降到 O(n^2.807) 的同时，其递归结构天然缓存友好，在实际 n 达到几千时就能胜过朴素三重循环。van Emde Boas 布局的数组则展示了缓存无关的数据结构设计。对程序员的启示：当分块参数难以确定或目标硬件多样（库代码）时，递归分治是更稳健的选择——编译器不能替你选择分块大小，但递归会自动「找到」每一级缓存。

性能分析工具是缓存优化的眼睛，三大主力各有分工。perf 是 Linux 原生工具，直接读取 CPU 的硬件性能计数器（PMU）：perf stat -e cache-references,cache-misses 给出总体未命中率；perf record -e cache-misses -g 加 perf report 把未命中归因到函数和源代码行；perf c2c 专门猎杀伪共享；perf mem 记录每次未命中的数据来源层级（L1/L2/L3/远程节点）。优点是开销极低（采样式）、测的是真实硬件事件；缺点是事件名因 CPU 型号而异，需要查 perf list。Valgrind 的 cachegrind 走模拟路线：它不读硬件计数器，而是用软件模拟一个可配置参数的缓存，逐条指令追踪每次访存的命中情况，cg_annotate 输出精确到每一行源代码的未命中统计。优点是结果确定、可重复、能模拟任意缓存配置（比如「如果 L1 只有 16KB 会怎样」）；缺点是慢 20-100 倍，且模拟的是单线程。Intel VTune 是商业工具中的标杆，提供内存访问图形化分析、跨 NUMA 流量统计和微架构探索（Top-Down 方法），适合深度调优。实践建议：日常用 perf stat 快速体检，定位用 perf record，伪共享用 perf c2c，精细归因用 cachegrind，重大优化项目上 VTune。

矩阵转置是缓存优化的「果蝇实验」——问题足够简单，优化空间足够深，是 CSAPP Cache Lab 的经典题目。朴素实现 for i, for j: B[j][i]=A[i][j] 的问题：读 A 是行优先顺序（友好），写 B 是列优先跳跃（每个缓存行只用 4 字节就被丢弃），未命中率约 50%。第一级优化是分块：以 32×32 的块为单位转置，块内数据装进 L1，读写都变成块内的小跳跃，未命中率降到 10% 以下；块大小的选择要避开 2 的幂次导致的组冲突（32×32 的 int 块每行 128 字节，恰好是缓存行的 2 倍，可能引发冲突，实践中 30×30 或加 padding 的 32×33 反而更快——这是「冲突未命中」的活教材）。第二级是处理对角线块：i==j 的块转置时读写同一区域，需要特殊处理避免自我驱逐。第三级是递归分治的缓存无关版本，性能与最优分块相当但免调参。第四级考虑 SIMD：用 SSE/AVX 的转置指令（_mm256_permute 系列）一次转置 4×4 或 8×8 的小块。这个例子浓缩了本章所有主题：访问模式、分块、冲突、对齐、递归——把它做透，缓存优化的直觉就建立了。

预取（Prefetching）分硬件和软件两路。硬件预取器内置于现代 CPU：L1 的流预取器检测同一缓存行内的顺序访问并提前加载相邻行，L2 的跨页流预取器追踪步长固定的访问模式（stride prefetcher），能跨越页边界预取——这就是为什么顺序访问数组的实际性能常常好于静态计算的理论值。但硬件预取器有盲区：指针追逐（链表、树）无法预测，不规则步长会失效，预取过猛还会污染缓存挤掉有用数据。软件预取让程序员显式补位：x86 的 prefetcht0/t1/t2 指令（GCC/Clang 内建函数 __builtin_prefetch(addr, rw, locality)）把指定地址提前拉进对应层级的缓存。使用模式是「计算与预取重叠」：在循环中处理第 i 个元素时，预取第 i+D 个元素（D 是预取距离，取「未命中延迟 ÷ 每元素处理时间」，通常 4-32），当处理推进到 i+D 时数据已在缓存中，延迟被完全隐藏。软件预取的适用场景：已知模式的间接访问（如遍历索引数组再取数据 data[index[i]]，可以预取 data[index[i+D]]）、硬件预取器失效的大步长扫描。注意事项：预取指令本身有发射开销，过度预取（距离太近或太多）反而降低性能；预取只解决延迟不解决带宽，带宽饱和的负载预取无效。

代码示例

这段代码是矩阵转置的三个版本对比，浓缩了分块优化的全部要点。版本一 transpose_naive 按定义逐元素转置，写 B 时是列方向跳跃，缓存行利用率极低。版本二 transpose_blocked 以 B×B 块为单位处理：外层双重循环枚举块，内层双重循环处理块内元素——块内访问的跨度只有 B×4 字节，当 B=32 时 A、B 两个块共 8KB，稳稳装进 32KB 的 L1，未命中率骤降。版本三在分块基础上给临时块加了一列 padding（buf[B][B+1]），破坏 B×4 字节恰好是缓存行整数倍导致的组冲突——这个 +1 的技巧能让某些尺寸下性能再提升 20%。用 perf stat -e L1-dcache-load-misses 分别测量三个版本（N=2048），典型结果是：naive 约 400 万次未命中，blocked 约 30 万次，blocked+padding 约 25 万次，运行时间比例大致相同。动手改 B 的值（8/16/32/64/128）画出性能曲线，你会亲眼看到「工作集与缓存容量的关系」如何决定最优分块。
#define N 2048
#define B 32
static int A[N][N], C[N][N];

void transpose_naive(void) {
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            C[j][i] = A[i][j];
}

void transpose_blocked(void) {
    for (int i0 = 0; i0 < N; i0 += B)
        for (int j0 = 0; j0 < N; j0 += B)
            for (int i = i0; i < i0 + B && i < N; i++)
                for (int j = j0; j < j0 + B && j < N; j++)
                    C[j][i] = A[i][j];
}

这段代码完整演示伪共享的产生与消除，是多线程缓存优化的必修课。SharedCounters 结构中 8 个 long 计数器连续排列，总共 64 字节——恰好一个缓存行。8 个线程各自疯狂递增自己的计数器，逻辑上零共享，但每次递增都让整行在其他 7 个核心的缓存中失效，该行以极高频率在核心间弹跳。PaddedCounters 给每个计数器配 56 字节填充，使其独占一个缓存行，写操作完全本地化。两个版本的循环体一模一样，唯一区别是结构体布局。实测（8 核，每线程 1 亿次递增）：伪共享版本约 8-12 秒，填充版本约 1.2-1.5 秒，差距 6-8 倍，而且伪共享版本的性能随线程数增加不升反降（更多核心争抢同一行）。验证手段：perf c2c record ./a.out 然后 perf c2c report，报告中 HITM（Hit Modified，读到其他核心的脏行）事件会精确指向 SharedCounters 所在缓存行和偏移。生产代码中的对应实践：每线程统计用 thread_local 变量最后归约，队列头尾指针分别 alignas(64)，环形缓冲区的读写游标隔离到不同行。
#include <thread>
#include <chrono>
#include <cstdio>
#define ITERS 100000000L

struct SharedCounters {
    long c[8];
};

struct PaddedCounters {
    struct alignas(64) Slot { long v; };
    Slot c[8];
};

template <typename T>
double bench(T &ctrs) {
    auto t0 = std::chrono::steady_clock::now();
    std::thread ts[8];
    for (int i = 0; i < 8; i++)
        ts[i] = std::thread([&ctrs, i] {
            for (long k = 0; k < ITERS; k++)
                if constexpr (std::is_same_v<T, SharedCounters>)
                    ctrs.c[i]++;
                else
                    ctrs.c[i].v++;
        });
    for (auto &t : ts) t.join();
    auto t1 = std::chrono::steady_clock::now();
    return std::chrono::duration<double>(t1 - t0).count();
}

这段代码演示结构体布局对扫描性能的影响，以及热冷分离（SoA 变换）的威力。场景：遍历 100 万个粒子，累加所有 x 坐标。版本一用 AoS（Array of Structs）：Particle 含 8 个字段共 64 字节，但我们只需要 x——每个缓存行 64 字节中只有 4 字节有用，有效带宽利用率 6.25%。版本二用 SoA（Struct of Arrays）：把所有 x 拆到独立数组 xs 中，扫描 xs 时每个缓存行的 64 字节全部是有用数据，利用率 100%。实测版本二比版本一快 8-12 倍（还受益于编译器对连续 float 数组的自动向量化——SoA 是 SIMD 友好的布局，AoS 则难以向量化）。这个权衡在图形学（ECS 架构的核心动机）、数据库（列式存储击败行式存储做分析查询的原因）、科学计算（Fortran 传统）中反复出现。决策规则：整体读写对象（如遍历后渲染每个粒子的全部属性）用 AoS；按字段批量处理（分析、过滤、聚合）用 SoA；混合负载考虑「热字段 AoS + 冷字段 SoA」的折中。用 pahole 查看结构体布局、用 perf stat 对比 LLC-load-misses 是验证手段。
struct Particle {
    float x, y, z;
    float vx, vy, vz;
    float mass;
    int id;
};

Particle particles[1000000];
float xs[1000000];

float sum_aos() {
    float s = 0;
    for (int i = 0; i < 1000000; i++)
        s += particles[i].x;
    return s;
}

float sum_soa() {
    float s = 0;
    for (int i = 0; i < 1000000; i++)
        s += xs[i];
    return s;
}

这段代码演示软件预取隐藏间接访问延迟的经典模式。场景：根据索引数组随机访问大表——sum += table[index[i]]，这是哈希探测、图遍历、连接操作的共同内核，硬件预取器对这种间接模式完全无能为力，因为下一个地址藏在数据里。解法是「预取流水线」：处理第 i 个元素时，先发出对 table[index[i+D]] 的预取请求（D 是预取距离），然后安心处理当前元素；等循环推进到 i+D 时，数据已经在 L1 里了。预取距离 D 的估算：主存未命中延迟约 200 周期，每次迭代的其他工作约 10-20 周期，所以 D 取 8-16 比较合适；D 太小则预取来不及完成，太大则预取的数据在到达使用点前可能被驱逐，且 index[i+D] 本身的访问也提前了（好在 index 是顺序访问，硬件预取器能覆盖）。__builtin_prefetch(addr, 0, 3) 的三个参数：地址、读写意图（0 读 1 写）、时间局部性提示（3 表示保留在所有层级缓存，0 表示用完即弃的非临时数据）。实测在 100 万条随机索引的场景下，预取版本比朴素版本快 1.5-2.5 倍。同样的模式适用于链表遍历（处理当前节点时预取 node->next->next）和 B 树下降。
#include <stdio.h>
#define TABLE_SIZE (64 * 1024 * 1024)
#define N_INDEX 1000000
#define DIST 12

static char table[TABLE_SIZE];
static int index_arr[N_INDEX];

long sum_with_prefetch(void) {
    long s = 0;
    for (int i = 0; i < N_INDEX; i++) {
        if (i + DIST < N_INDEX)
            __builtin_prefetch(&table[index_arr[i + DIST]], 0, 3);
        s += table[index_arr[i]];
    }
    return s;
}

这段代码展示循环融合与分块在真实计算中的组合应用：图像模糊（3×3 卷积）。未优化版本分两趟：第一趟把灰度图转成浮点存入临时数组 tmp，第二趟对 tmp 做卷积——tmp 被完整写一遍再完整读一遍，对大图（远超 L3）意味着两轮完整的主存往返。融合版本把转换和卷积合并进同一个分块循环：以行为条带处理，每个条带的转换结果还在 L1/L2 里就被立即用于卷积，临时数组缩小到条带大小（几 KB），主存流量减半以上。分块的维度选择也有讲究：卷积的窗口是 3×3，按行分条带（每次处理若干完整行）比按二维块分割更简单且足够——条带宽度等于图像宽度保证行内顺序访问，条带高度取 8-16 行使工作集驻留 L2。这类「融合消除中间数组」的模式适用于一切流水线式的数据处理：ETL 的多趟转换、机器学习的前处理链、信号处理的级联滤波。判断标准很简单：如果两个循环遍历同一份数据且第一个的输出是第二个的输入，融合几乎总是正确的——除非融合后寄存器压力过大导致溢出，这时用分块把融合限制在块内。
#define W 4096
#define H 4096
#define STRIP 16
static unsigned char gray[H][W];
static float tmp[STRIP + 2][W];
static float out[H][W];

void blur_fused_tiled(void) {
    for (int y0 = 1; y0 < H - 1; y0 += STRIP) {
        int y1 = y0 + STRIP < H - 1 ? y0 + STRIP : H - 1;
        for (int y = y0 - 1; y <= y1 + 1; y++)
            for (int x = 0; x < W; x++)
                tmp[y - (y0 - 1)][x] = gray[y][x] * (1.0f / 255.0f);
        for (int y = y0; y < y1; y++)
            for (int x = 1; x < W - 1; x++) {
                float s = 0;
                for (int dy = -1; dy <= 1; dy++)
                    for (int dx = -1; dx <= 1; dx++)
                        s += tmp[y - y0 + 1 + dy][x + dx];
                out[y][x] = s / 9.0f;
            }
    }
}

实验笔记

本章实验是全书的收官之战，要求综合运用前三章知识完成一个完整的优化项目。实验一「AoS vs SoA 对决」：实现一个粒子系统基准，100 万个粒子各含位置、速度、质量、ID 共 32 字节，分别用 AoS 和 SoA 布局实现三种操作——只读 x 坐标求和、更新全部位置（pos += vel × dt）、按 ID 过滤，用 perf stat 测量每种组合的 LLC 未命中和运行时间，绘制 2×3 的性能矩阵，并解释为什么「更新全部位置」操作中两种布局的差距远小于「只读 x」。实验二「伪共享猎杀」：编写一个 8 线程的无锁计数器基准，依次实现四个版本——共享数组相邻元素、共享数组加 alignas(64) 填充、thread_local 计数器加最终归约、原子 fetch_add 共享计数器，测量各版本吞吐量，用 perf c2c 生成伪共享报告，解释为什么 thread_local 版本最快而原子版本最慢。实验三「矩阵乘法进阶」（可选加分）：从朴素三重循环出发，依次应用循环重排（选出六种排列中最优的两种）、一维分块、二维分块加寄存器分块（4×4 微内核），每一步用 perf 测量 GFLOPS 并计算达到峰值算力的百分比，最终对比 OpenBLAS 的 cblas_sgemm，理解工业级实现还做了哪些你没做的事（预取、SIMD、多级分块）。实验报告要求：每个结论附测量数据，每个优化解释「改善了哪种未命中（强制/容量/冲突）」，并回答一个开放问题——如果目标机器的 L1 从 32KB 变成 48KB、缓存行从 64 字节变成 128 字节，你的哪些参数需要调整，哪些代码结构可以不变（提示：缓存无关算法）。

第4章 程序员能为缓存做什么