单元二 · 内存墙：机器的时间花在哪

对应教材：[[Optimized C++ Proven Techniques for Heightened Performance.pdf|Optimized C++]] ch2「Computer Behavior Affecting Optimization」
本单元回答：一段代码慢了，时间到底花在哪？为什么多数时候答案都是同一个？
前置：[[单元01-时间的形状：延迟、吞吐与尾延迟]]（分位数、噪声下限、取最小值、环境四元组）
编译说明：示例统一 g++ -std=c++23 -O2 -Wall -Wextra，实跑于 g++ 15.2（Ubuntu），AMD Ryzen 9 7940H（Zen 4，8 核 16 线程，L1d 32KB/核，L2 1MB/核，L3 16MB）。代码在 讲义/code/ 下。

0. 本单元地图

单元一教你量准一个数。单元二回答量完之后最常遇到的那个问题：这个数为什么这么大。

第一讲 一次 miss 值几百条指令 1 ns 和 100 ns 之间那条线
第二讲 缓存阶梯：台阶落在哪 1 → 2 → 3 → 5 → 10 → 34 → 90 → 106 ns
第三讲 搬运量相同，速率差四倍 顺序 45.6 GB/s，随机 11.5 GB/s
第四讲 硬件按行记账 元素从 4 字节长到 64 字节，慢 16 倍
第五讲 改遍历顺序，不改数据结构 列优先慢 20 倍，分块一改就回来了

四条结论依次收紧：

四讲之后，你会拿到一把尺子：看到一段慢代码，先问它碰了多少条 cache line。 这个数字能解释的性能问题，比所有其他单一因素加起来还多。

本单元的测量条件：四个实验都对访存敏感，下面的数字全部用 taskset -c 15 绑核跑出。第一讲会解释为什么必须这么做，以及不绑核会错成什么样。

除计时之外，本单元还会用到两类计数器：perf stat 读硬件事件，valgrind –tool=cachegrind 把 miss 归到函数和源码行。两者各有一次性的准备动作，见 B 线「先说工具」。计数器要配着计时读——它数的是搬运量，不告诉你时间，而这一单元所有的代价最终都要落回时间上。

第一讲 一次 miss 值几百条指令

是什么

CPU 做一次整数加法，在现代 x86 上大约 0.25 纳秒。从主存取一个数，大约 100 纳秒。这两个数字差 400 倍。

把它换成「CPU 能在这段时间里干多少活」，就是内存墙这个说法的来历：一次主存 miss 的时间里，CPU 本来能算完几百条指令。 只要有一条指令在等主存，后面几百条指令的位置就空着。

这条结论把性能优化的第一个问题换掉了。原来的问题是「这段代码执行了多少条指令」，现在的问题是「这段代码碰了多少条不在缓存里的数据」。前者是编译器的事，后者是你的事。

为什么差距会拉开到几百倍

两件事的物理原理不一样。

CPU 里跑的是晶体管开关，开关一次的能量小、距离短、没有机械过程，所以主频能从几兆赫一路推到几吉赫。DRAM 里存的是电容上的电荷，读一次要把电荷引出来比较，写一次要把电容充满。这个过程有确定的物理下限，不是工艺问题。

代价体现在时序上：一次 DRAM 访问要先激活一整行（RAS），再选中列（CAS），等数据读出，然后预充电准备下一次。整个流程走完是几十纳秒，而这段时间 CPU 能跑几百个周期。

缓存的存在就是为了把这条慢路径挡住。CPU 里放几级容量递增、速度递减的存储，让大多数访问在前几级就结束，只有挡不住的那些才落到主存。所以「慢」不是均匀的慢，是分级的慢——分级的结果就是第二讲那条阶梯。

代码逐行

讲义/code/exp06_cache_ladder.cpp。用指针追逐测出四级访存各要多少纳秒。

// 构造覆盖全部 N 个元素的随机单环
std::vector<std::uint32_t> make_cycle(std::size_t n, std::uint32_t seed) {
std::vector<std::uint32_t> perm(n);
std::iota(perm.begin(), perm.end(), 0u);
std::mt19937 rng(seed);
std::shuffle(perm.begin(), perm.end(), rng);

std::vector<std::uint32_t> next(n);
for (std::size_t k = 0; k < n; ++k) next[perm[k]] = perm[(k + 1) % n];
return next;
}

把 0..n-1 打乱得到一个排列，然后让 next[perm[k]] 指向 perm[k+1]。这样从任意一点出发，沿着 next 一直走会不重不漏地经过所有元素，最后回到起点——一个覆盖全数组的单环。

double chase_ns(const std::vector<std::uint32_t>& next, std::size_t steps) {
std::uint32_t cur = 0;
// 预热：把工作集尽量读进缓存，让结果反映稳态而不是冷启动
for (std::size_t i = 0; i < steps / 4; ++i) cur = next[cur];

auto t0 = clk::now();
for (std::size_t i = 0; i < steps; ++i) cur = next[cur];
auto t1 = clk::now();

volatile std::uint32_t sink = cur; // 防止整段被优化掉
(void)sink;
return std::chrono::duration<double, std::nano>(t1 – t0).count() / static_cast<double>(steps);
}

为什么用指针追逐而不是数组遍历。 这一步是整个实验成立的前提。

数组顺序遍历是可以被预取的。CPU 看到你在按 p+1, p+2, p+3 走，就会提前把后面几条 cache line 拉进来。等你走到那一步时数据已经在缓存里了，这一次访问量到的是预取器留下了多少提前量，离访存的真实延迟已经很远。

指针追逐的每一步地址依赖上一步的结果。next[cur] 里的 cur 是上一步读出来的值，硬件在读到之前根本不知道下一个地址在哪，预取器没有可预测的输入。链条上的每一步都必须老老实实等。

预热那一行是为了把工作集先读进缓存，让计时反映稳态。单元一第四讲量过：不预热的话，第一轮的读数被冷启动污染，而工作集越大污染越严重。

为什么除以 steps。 得到的是每步纳秒数，也就是该工作集下的访存延迟。这是全书第一个「摊到单位」的例子——不摊到单位，不同规模的结果没法比。

代码运行结果

$ taskset -c 15 ./exp06_cache_ladder # 跑三轮，每一档取最小值

工作集 元素数 每步延迟 相对 L1
16 KB 4096 1.04 ns 1.00x
64 KB 16384 2.14 ns 2.06x
256 KB 65536 2.94 ns 2.83x
512 KB 131072 3.83 ns 3.68x
1 MB 262144 5.36 ns 5.15x
4 MB 1048576 10.22 ns 9.83x
8 MB 2097152 11.86 ns 11.40x
16 MB 4194304 34.09 ns 32.78x
32 MB 8388608 67.14 ns 64.56x
64 MB 16777216 90.01 ns 86.55x
256 MB 67108864 106.39 ns 102.30x

两端差 102 倍，中间的过渡不平滑——有台阶。

常见坑

坑一：在没绑核、机器又在忙的时候跑。 这是最容易踩的一个，因为它不报错，只是给你一组看起来正常其实错得离谱的数。

同一份 exp06，在这台机器桌面空闲但负载约 3 的时候跑，512KB 一档报出 30.44 ns，4MB 一档报出 113.18 ns——分别比绑核后的值高 8 倍和 11 倍。而 16KB、64KB、256MB 三档几乎没受影响。

原因是小工作集本来就待在 L1/L2 里，别的进程抢核只影响调度不影响缓存；256MB 本来就每一档都 miss，多几个也无所谓。受影响的恰好是中间那几档，也就是你最关心的那几档。判断一份阶梯数据可不可信，先看它是否单调、是否平滑。

taskset -c 15 ./exp06_cache_ladder 能把大部分干扰挡掉。

坑二：只跑一轮。 单元一第四讲量到单轮读数抖动约 11%，本机这次的实测更极端：8MB 那一档在三轮里从 11.86 ns 跳到 31.95 ns，差 2.7 倍。绑核也压不住，因为这一档正好压在 L3 容量（16MB）上，缓存里多放一点少放一点，结果就换一个样。

处理办法还是单元一那条：多轮取最小。报数的时候把「取了几轮」一起报上，这是单元一环境四元组的一部分。

坑三：把指针追逐的结论直接套到数组遍历上。 指针追逐量的是延迟——一步等一步，串行。数组遍历通常量的是吞吐——很多次访问同时在飞。这两个数能差 20 倍，第三讲会把这个差别量出来。

教材指引

Guntheroth ch2。这一章给出全书的机器模型，后面每一章的优化手法都能追到这一章的某一条上。

第二讲 缓存阶梯：台阶落在哪

是什么

上一讲那张表有 11 行。把它们按台阶分组，得到四级：

从 L1 到主存，延迟涨了 100 倍。这就是「数据在哪一级」这个问题的全部价值。

为什么台阶落在这些位置

台阶的边界就是每一级的容量。工作集一旦超过某一级的容量，那一级就装不下了，访问开始往下一级掉，延迟跳一档。

三处细节值得拆开。

一、L1 那一档为什么从 1ns 涨到 2ns 就有台阶。 16KB 完全装进 32KB 的 L1，每次访问都是 L1 命中，1.04 ns 约等于四个周期——L1 的访问延迟量级。到 64KB 时已经超出 L1 容量，一部分访问掉到 L2，平均值被拉高到 2.14 ns。这不是「L1 变慢了」，是「一部分访问不再是 L1 了」。阶梯上每一个点都是混合平均值，只不过在台阶附近混合比例变了。

二、L2 到 L3 那一段为什么是渐变的。 1 MB 是 5.36 ns，4 MB 是 10.22 ns，8 MB 是 11.86 ns——涨得不快。因为本机的 L2 是每核 1MB，L3 是 8 核共享 16MB。1MB 的工作集刚超出 L2 时，L3 还能轻松兜住，代价从 L2 的 5 ns 涨到 L3 的 10 ns，只翻一倍。

三、16 MB 到 32 MB 那一步为什么最陡。 16 MB 是 34.09 ns，32 MB 是 67.14 ns，翻一倍。因为 16MB 正好等于 L3 的容量——工作集在 16MB 时 L3 已经放不下全部数据，但还放得下很大一部分；到 32MB 时大半访问都要落到主存。L3 到主存这一步跨的是从三十几纳秒到 90 ns，约三倍。

16MB 那一档的数值本身是全表最不可复现的（见 A 线任务里那张偏差表），但这一步的陡峭不依赖它的精确值：32MB 那一档远超 L3 容量，无论 16MB 取 27 还是 34，落差都是两倍以上。

上面这张表里，每一档的「延迟」都不是单一来源的延迟。它是「这一档里有多少比例的访问落在哪一级」的加权和。 台阶不是在某一级内部量出来的，是在两级的交界处量出来的。

代码逐行

核心循环就是上一讲那段 chase_ns。这里补两点外围代码。

const std::size_t sizes_kb[] = {16, 64, 256, 512, 1024, 4096, 8192, 16384, 32768, 65536, 262144};

for (std::size_t kb : sizes_kb) {
const std::size_t bytes = kb * 1024;
const std::size_t n = bytes / sizeof(std::uint32_t);

auto next = make_cycle(n, 20260911);
const std::size_t steps = n * STEPS_PER_NODE;

// 取多轮最小，避开干扰（单元四的教训）
double best = 1e18;
for (int r = 0; r < 5; ++r) best = std::min(best, chase_ns(next, steps));
//…
}

扫描点按 4 倍递增：16、64、256、1024…… 这个比例是用来看台阶的，不是用来看细节的。要定位一条具体边界，得在台阶附近把间隔加密。

每一步走 n * 3 次——三圈。走一圈的话，环上的每个元素只碰一次，量到的东西受起始位置影响；走三圈能摊掉。这个倍数写在 STEPS_PER_NODE 里，改它要同步改所有对照数据。

每档各建一份 next 数组，不复用。因为不同规模要的是不同的环，换规模就得重建。建数组的时间不计入（在计时循环外面）。

代码运行结果

见上一讲那张表。这里换一个角度读它——把相对倍数按台阶分组：

L1 → L2 2.06x → 2.83x 涨 1.4 倍
L2 → L3 5.15x → 32.78x 涨 6.4 倍
L3 → 主存 32.78x → 102.30x 涨 3.1 倍

从 L2 到 L3 这一段涨幅最大（6.4 倍），因为本机的 L2 每核 1MB 而 L3 共享 16MB，中间跨的容量区间最宽。

常见坑

坑一：把标称容量当成精确边界。 上表写的「L1d 32KB/核」，但台阶出现在 16KB 到 64KB 之间，不在 32KB 这个点上。原因有三：缓存是组相联的，不是全相联；L1 里还要放指令和各种表；工作集的实际占用量比数组本身大。

报边界的时候报区间，别报点。

坑二：拿这台机器的纳秒数去套别的机器。 L1 延迟 1 ns 是这一代 Zen 4 的数值，换成别的架构会变。可以搬走的是台阶的形状——四级、容量递增、延迟递增——具体的纳秒数必须重测。这是单元一环境四元组的直接后果。

坑三：忘了看共享 L3。 本机 L3 是 8 核共享的。实验绑在 15 号核上跑，但如果别的核同时在吃 L3，你能用的 L3 就不到 16MB。这就是为什么 16MB 那一档的抖动最大。

教材指引

Guntheroth ch2。他给的是各类缓存行为的定性描述和量级，具体数字同样要求你在自己机器上重测。

第三讲 搬运量相同，速率差四倍

是什么

上一讲的阶梯是用指针追逐量出来的——那是延迟：一步等一步，串行，没有任何重叠。真实的代码里，访问之间常常没有依赖，可以同时在飞。这时候该看的量换成了吞吐。

exp07_prefetch.cpp 拿同一个 64MB 数组做三件事：

顺序 —— 16M 次访问，每次用满一整行，碰到 1M 行
步长 16 —— 1M 次访问，每次只取 4 字节，但也碰到 1M 行
随机 —— 1M 次访问，同样是 1M 行，只是先后顺序被打乱

三档搬运的字节数完全一样，都是 64MB。差别只在顺序。

为什么顺序访问能把延迟藏起来

先看结果，再解释。

访问顺序 访问次数 耗时 搬运速率 每次访问
顺序 16777216 1.37 ms 45.6 GB/s 0.08 ns
步长 16 1048576 1.30 ms 48.1 GB/s 1.24 ns
随机 1048576 5.42 ms 11.5 GB/s 5.17 ns

顺序那一档访问的元素个数是另外两档的 16 倍，耗时反而最短。而随机那一档和步长 16 访问的元素个数一模一样、碰的 cache line 条数一模一样、搬运的字节数一模一样，耗时是它的 4.2 倍。

搬运量相同，速率差 4.2 倍。 先用计数器把「搬运量相同」这句话确认下来，再解释差在哪。

计数器说：三档碰的 line 一样多

exp07_prefetch 也有单档入口，同样配一个 none 档，减掉建 64MB 数组和打乱下标的流量：

$ taskset -c 15 perf stat -e L1-dcache-load-misses,cache-misses \\
-e l2_pf_hit_l2.all,l2_pf_miss_l2_l3.all ./exp07_prefetch <seq|stride|gather|none>

每档跑 20 遍，减掉基线：

三档每档都碰 1M 条 line、跑 20 遍，共 20M 条。

第一列的三档几乎相同，这就是「搬运量相同」的直接证据。 2100 万这个数就是 20M 条 line 的首触次数——第四讲那条「硬件按行记账」在这里第二次出现。

差在第三、四列。顺序和步长两档，预取器分别发出 2087 万和 1570 万次取数请求，这些请求在 L2 里都没有命中，于是下沉到 L3 去取。等 CPU 真的来要这条数据，它已经在 L2 里了，需求 miss 因此只有 9.7 万和 20.6 万。随机那一档预取器只发出 115 万次，剩下两千万条全要当场去 L3 或主存取。

耗时跟着第四列走，不跟着第一列。

中间那两列不能相加。顺序那一档，预取请求「命中 L2」和「下沉 L3」都是两千多万，加起来超过了它碰到的 line 数——同一条 line 被预取器重复请求过。这两个计数不是把同一批请求分成互斥的两类。判断预取器有没有在干活，看第三列的量级。

差在哪：预取器与内存并行度

一、预取器。 它盯着 CPU 发出的地址流，找规律。看到地址按 +64 字节 稳定前进，就提前把后面几条 line 拉进来；看到稳定的 +4096 字节 步长，一样能识别——步长 16 那一档走的正是这个模式，所以它和顺序打平（48.1 对 45.6 GB/s）。

随机的地址流里没有规律可找。上表第三列里它只有 115 万，其余两档是 1570 万和 2087 万，差 14 到 18 倍——这就是「预取器认不出」在计数器上的样子。

预取量差十几倍，落到需求 miss 上是 105 到 224 倍。中间多出来的那一段，是「预取请求发出去了」和「要用的时候数据在不在」之间的差。

二、乱序执行与内存并行度。 顺序那一档，s0 += d[i] 和 s1 += d[i+1] 之间没有依赖，CPU 可以同时发出很多条访存指令。单次 miss 要等 90 ns，但同时有十几条 miss 在飞，摊到每一次就只剩几纳秒。

算一下摊薄的比例。随机那一档每遍 104.8576 万次访问，耗时 5.42 ms，一共约 108 万次 L2 需求 miss——每次 miss 摊到 5.02 ns。 而单次访存延迟是 90 ns（第一讲）。两者差 18 倍，也就是说平均有十几个 miss 同时在飞。

随机那一档还留着这个能力，所以它是 5.17 ns 而不是 90 ns。把两件事都掐掉的是带上数据依赖的指针追逐，那才是上一讲的 90~106 ns。

三档的分工：顺序那档已经顶到内存带宽上限（45.6 GB/s，和第四讲量到的 50 GB/s 是同一个数），随机那档只跑到 11.5 GB/s，离上限还远。所以随机那档不是被带宽卡住的，是被延迟卡住的——带宽不是瓶颈，延迟才是。

代码逐行

// 步长 16 个 int = 64 字节，正好隔一条 line。每条 line 只用 4 字节。
inline std::uint64_t sum_stride(const std::vector<std::uint32_t>& d) {
std::uint64_t s0 = 0, s1 = 0;
std::size_t i = 0;
for (; i + 32 < d.size(); i += 32) { s0 += d[i]; s1 += d[i + 16]; }
return s0 + s1;
}

一次循环处理两个元素，中间隔 16 个 int。这样两档的循环次数是元素数的一半，方便和顺序版对照。

// 按下标序列取。下标是预打乱的，硬件猜不出下一个是谁。
inline std::uint64_t sum_gather(const std::vector<std::uint32_t>& d,
const std::vector<std::uint32_t>& idx) {
std::uint64_t s0 = 0, s1 = 0;
std::size_t i = 0;
for (; i + 2 <= idx.size(); i += 2) { s0 += d[idx[i]]; s1 += d[idx[i + 1]]; }
for (; i < idx.size(); ++i) s0 += d[idx[i]];
return s0 + s1;
}

下标数组预先打乱好，里面存的是已经乘过 16 的位置，直接拿来做数组下标。多读一个 4MB 的下标数组是这笔测量的成本——它是顺序读的，速率接近带宽上限，相比 64MB 的主数据流可以忽略。

std::vector<std::uint32_t> idx(SPARSE_N);
std::iota(idx.begin(), idx.end(), 0u);
std::mt19937 rng(20260912);
std::shuffle(idx.begin(), idx.end(), rng);
for (auto& v : idx) v *= 16; // 摊到整块内存上

种子写死，任何人重跑都得到同一个排列。这一步不能省——换成随机种子，两次运行的结论就没法比了。

三条独立的累加链（s0、s1）是这个实验的另一个前提。如果只用一个累加变量，两个加法之间就带上了依赖，循环本身会成为瓶颈，把访存的差别盖住。这个坑在单元一的 exp02 里已经踩过一次。

代码运行结果

见上表。这里补一段程序自己的归因：

三档搬运的字节数完全一样，都是 64 MB
搬运量相同，速率差了 4.2 倍。顺序和步长 16 都跑在 46 GB/s 附近，
随机那一档只有 11.5 GB/s，离上限还差得远——它不是被带宽卡住的，
是被延迟卡住的。

常见坑

坑一：只看访问次数，不看搬运量。 「步长 16 只取了 1/16 的元素，怎么没快 16 倍？」——因为加法次数少了 16 倍，搬运的字节数一个没少。取多少元素决定加法次数，碰多少行才决定耗时。这两笔账从这一讲起要分开算。

坑二：把随机访问的 5 ns 当成「随机访问的成本」。 5.17 ns 是大批独立访问重叠之后的摊薄值。单次随机访存延迟是 90~106 ns（第一讲）。写代码时该用哪个数，取决于这段访问有没有依赖链：遍历一个 vector<int> 用 5 ns，跟着 next 指针走用 100 ns。

坑三：以为预取器只认「连续」。 本机的预取器认步长，步长 16 那一档和顺序打平就是证据。所以「把数据打散就能避免预取器干扰」这个想法不成立——要打断预取，得让地址不可预测。

教材指引

Guntheroth ch2 讲缓存行为时把预取和乱序执行放在一起说。他给的判断是：硬件能自动处理的模式比多数人以为的多，所以先量再改。

第四讲 硬件按行记账

是什么

上一讲已经暗示了一件事：决定成本的不是「取了多少字节」，是「碰了多少条 cache line」。这一讲把它量成一条可以直接用的换算。

exp08_linecost.cpp 用元素尺寸从 4 字节扫到 128 字节，每次只读元素开头的 4 字节：

// 每个元素只取开头那个 int。alignas 把元素尺寸钉死成 Sz。
template <std::size_t Sz>
void sum_aligned(const void* base, std::size_t n) {
struct alignas(Sz) E { int v; };
static_assert(sizeof(E) == Sz, "对齐没有把尺寸钉住");
const E* p = static_cast<const E*>(base);
std::uint64_t s0 = 0, s1 = 0;
std::size_t i = 0;
for (; i + 2 <= n; i += 2) { s0 += std::uint32_t(p[i].v); s1 += std::uint32_t(p[i + 1].v); }
for (; i < n; ++i) s0 += std::uint32_t(p[i].v);
g_sink = s0 + s1;
}

alignas(Sz) 把元素尺寸钉成 Sz，不用手写 padding 数组。static_assert 保证对齐确实生效了——少了它，alignas(16) 到底有没有把 sizeof 顶到 16 只能靠猜。

为什么「读 4 字节」和「搬 64 字节」是两笔账

先看结果。

元素尺寸 一行装 搬运量 耗时 每次访问 搬运速率 相对 4B
(字节) 几个 (MB) (ms) (ns) (GB/s)
4 16 16 0.31 ms 0.07 ns 50.3 1.00x
8 8 32 0.55 ms 0.13 ns 56.8 1.77x
16 4 64 1.17 ms 0.28 ns 53.3 3.77x
32 2 128 2.48 ms 0.59 ns 50.3 8.00x
64 1 256 5.07 ms 1.21 ns 49.3 16.31x
128 跨两行 512 18.26 ms 4.35 ns 27.4 58.77x

六档的有用数据一共 16 MB，访问次数都是 4194304。两样都没变。

元素从 4 字节长到 64 字节，搬运量涨 16 倍，耗时涨 16.31 倍。

读到的有用数据一个字节没变，多出来的钱全花在「顺带搬进来的那些字节」上。

为什么顺带搬进来的是 64 字节。 DRAM 的存储阵列一次突发传输就是 64 字节（8 次 64 位传输），这是接口宽度定死的。所以从主存往缓存搬数据的最小单位就是 64 字节，缓存行也是 64 字节。你读 4 字节，硬件搬 64 字节，剩下 60 字节是搭车的。

看搬运速率那一列。 4 到 64 字节五档都落在 49~57 GB/s，彼此差不到 15%。同一条速率出现在搬运量差 16 倍的五段代码里，说明卡住它们的是同一件事——内存带宽，不是访问次数也不是指令数。于是有了一条换算：

耗时 ≈ 搬运量 ÷ 带宽，搬运量按 64 字节的行算。

最后一档 128 字节掉到 27.4 GB/s。 比按比例外推的还慢。元素跨在两行上，硬件要凑齐两次行填充才能给出一个元素——这笔代价在排版结构体的时候会反复遇到，单元三会专门讲。

代码逐行

template <std::size_t Sz>
void sample_ms(const void* base, std::size_t n, int rounds, double& best, double& median) {
std::vector<double> v;
v.reserve(static_cast<std::size_t>(rounds));
for (int r = 0; r < rounds; ++r) {
auto t0 = clk::now();
sum_aligned<Sz>(base, n);
v.push_back(std::chrono::duration<double, std::milli>(clk::now() – t0).count());
}
std::sort(v.begin(), v.end());
best = v.front();
median = v[v.size() / 2];
}

除了最小值，这里还把中位数一起报出来。两者差得多，说明这一档的读数不稳，结论就不能只靠最小值撑着。

// 小尺寸那几档更快、读数也更飘，多跑几轮才看得清
const int rounds = (sz <= 16) ? 21 : 7;

轮数随尺寸变。这一行是被一次错误逼出来的：4 字节那一档跑 5 轮时报 19.1 GB/s，跑到 21 轮才稳定在 48~50 GB/s。前面几轮是在等内存子系统和频率进稳态。

报读数的时候连轮数一起报，这样别人重跑时知道该跑多少轮。

代码运行结果

见上表。程序自己给出的三条结论：

元素尺寸从 4 涨到 64，搬运量涨 16 倍，耗时涨 16.31 倍。

再看搬运速率那一列：4 到 64 字节五档都落在 48 GB/s 上下，
说明卡住它们的是同一件事——内存带宽。

最后一档 128 字节掉到 27 GB/s，元素跨在两行上。

常见坑

坑一：轮数不够，把「还没热身」当成「这一档更快」。 上面那一行 rounds 就是为此写的。四个字节的元素访问最快，受频率爬升的影响也最大。

坑二：以为元素小就一定快。 元素小只在「一行装得下多个」时划算。表里 4 字节和 8 字节都是 8~16 个一行，速率只差 13%。跳变发生在 64 字节那一档——一行只装得下一个元素，从这一档起，每取一个元素就实打实搬一整行。

坑三：把这条换算用到容量受限的场景上。 「耗时 ≈ 搬运量 ÷ 带宽」成立的前提是数据装不进缓存、必须从主存流过来。如果工作集只有几 MB，全部待在 L3 里，这条式子给的是上限而不是实际值——那时候的瓶颈在 L3 带宽和 L1 组冲突上，第五讲量这个。

教材指引

Guntheroth ch2。cache line 是 64 字节这一条他在讲缓存行为时给出，后面 ch10「Optimize Data Structures」整章都在用它——结构体怎么排、AoS 还是 SoA，判据都落回这一条。

第五讲 改遍历顺序，不改数据结构

是什么

前四讲把成本推到了「碰多少条 cache line」。这一讲给出一个常常不用改一个字节数据就能把条数降下来的办法：换遍历顺序。

exp09_locality.cpp 处理一个 N×N 的 int 矩阵，行优先存放，求全部元素的和。三段代码做同一件事，只有顺序不同：

template <std::size_t N>
void sum_rowmajor(const int* m) { // 一行一行地加
std::uint64_t s[CHAINS] = {};
for (std::size_t i = 0; i < N; ++i)
for (std::size_t j = 0; j < N; ++j)
s[j % CHAINS] += std::uint32_t(m[i * N + j]);
g_sink = fold(s);
}

template <std::size_t N>
void sum_colmajor(const int* m) { // 一列一列地加
std::uint64_t s[CHAINS] = {};
for (std::size_t j = 0; j < N; ++j)
for (std::size_t i = 0; i < N; ++i)
s[i % CHAINS] += std::uint32_t(m[i * N + j]);
g_sink = fold(s);
}

第三段 sum_blocked 把矩阵切成 16×16 的小方块，块内按行加，块之间按列走。

为什么 4 MB 装得进 L3，还是慢 12.7 倍

N 取三档，工作集分别是 16KB、4MB、64MB：

16 KB（整块装得进 L1）
遍历顺序 耗时 每次访问 相对行优先
行优先 0.0014 ms 0.34 ns 1.0x
列优先 0.0016 ms 0.38 ns 1.1x
分块 16 0.0021 ms 0.51 ns 1.5x
行优先 / 列优先 = 1.1 倍

4 MB（L1 装不下，L3 装得下）
行优先 0.3981 ms 0.38 ns 1.0x
列优先 5.0396 ms 4.81 ns 12.7x
分块 16 0.4015 ms 0.38 ns 1.0x
行优先 / 列优先 = 12.7 倍

64 MB（L3 也装不下）
行优先 5.8857 ms 0.35 ns 1.0x
列优先 117.9601 ms 7.03 ns 20.0x
分块 16 8.0741 ms 0.48 ns 1.4x
行优先 / 列优先 = 20.0 倍

倍率这样走：1.1 → 12.7 → 20.0。

我跑之前猜的是第二档应该没事——4MB 整块都在 16MB 的 L3 里待着。实测 12.7 倍。

先算清楚为什么。三个缓存各有多少个组，决定步长会不会撞车。本机的几何（从 sysfs 读，不是背的）：

组数全是 2 的幂。 这一条是整件事的来源。

N=1024 时列优先的步长是 1024 个 int = 4096 字节 = 64 条 cache line。地址落在哪个组，看的是行号对组数取模。所以同一列上相邻两次访问，组号相差 64。

对三级分别算：

L1 64 mod 64 = 0 → 1024 次访问全落 1 个组， 8 路装 1024 条 → 全塌
L2 64 mod 2048 = 64 → 落在 32 个组，每组 32 条， 8 路装 32 条 → 塌
L3 64 mod 16384 = 64 → 落在 256 个组，每组 4 条， 16 路装 4 条 → 装得下

L3 装得下，L1 和 L2 都塌。4MB 的数据在 L3 里放得好好的，而 L1 每次去看都是空的——这不是容量不够，是组冲突。

N=64 时步长是 256 字节 = 4 条 line，对 64 取模等于 4，64 次访问依次落在 16 个组上，每组 4 条，8 路装得下。所以第一档只有 1.1 倍。

N=4096 时步长是 16384 字节 = 256 条 line：

L1 256 mod 64 = 0 → 1 个组，4096 条 → 塌
L2 256 mod 2048 = 256 → 8 个组，每组 512 条 → 塌
L3 256 mod 16384 = 256 → 64 个组，每组 64 条，16 路装 64 条 → 也塌了

这一档三级全塌，所以倍率从 12.7 涨到 20.0。

用 perf 把这件事量出来

上面全是算术。硬件计数器能给出独立的证据。exp09_locality 有一个单档入口，专供外部工具计数：

$ taskset -c 15 perf stat -e L1-dcache-load-misses,cache-misses ./exp09_locality 1024 none
$ taskset -c 15 perf stat -e L1-dcache-load-misses,cache-misses ./exp09_locality 1024 row
$ taskset -c 15 perf stat -e L1-dcache-load-misses,cache-misses ./exp09_locality 1024 col
$ taskset -c 15 perf stat -e L1-dcache-load-misses,cache-misses ./exp09_locality 1024 blk

none 档只建矩阵不遍历。它存在的理由是：计数器数的是进程做过的全部事情。 建那个 4MB 矩阵本身就有内存流量，不打掉的话会稀释掉三档之间的差别。两条命令相减，是这类工具的通用套路。

N=1024，每档 30 遍，一共 31,457,280 次访问。减掉 none 基线后：

行优先的 L1 miss 数，正好等于它碰到的 cache line 条数。 4MB 矩阵是 65536 条 line，跑 30 遍就是 1,966,080 次首触。多次运行实测在 1,971,190 到 1,993,090 之间，比理论值高 0.26% 到 1.4%。第四讲那条「硬件按行记账」，在这里被直接量到了。

列优先碰的是同一批 line，却报了 33,442,254 次——同一块数据多搬了 16.8 倍。 多出来的部分全是塌掉之后反复取回。

L2 那一列差得更远：32,094 对 16,227,239，两个数量级。这和上面那张几何表对得上——L3 装得下，L1 和 L2 都装不下。

行优先那格的 L2 数要打个折看。它是两个小数字相减得来的（row 的 95,572 减 none 的 63,478），而 L2 正是三档里最不稳的一列，跑几次能在几万这个量级上晃一倍。稳的是列优先那一格——一千六百万这个数落在两个数量级的差距上，怎么晃都不会反过来。报数时按稳定性分开对待，不是所有格子都配得上同样的位数。

分块是怎么把这件事按回去的。 块内 16 个 int 正好占满一行；块只有 16 行，一整个块的工作集是 16×64 = 1KB，装得下 L1。块内按行加，每次访问用满一行；换到下一个块时，前面的块已经用完了，被挤出去也无所谓。

三档里分块分别只比行优先贵 1.50、1.01、1.37 倍。数据布局一个字节都没动，改的只是遍历顺序。

代码逐行

// 每条累加链只带 1 次加法。多开几条，让内层不被加法延迟卡住，
// 这样量到的差别才归因到访存上。
constexpr int CHAINS = 4;

inline std::uint64_t fold(const std::uint64_t (&s)[CHAINS]) {
return s[0] + s[1] + s[2] + s[3];
}

CHAINS = 4 的作用和上一讲的 s0/s1 一样，只是这里用数组统一处理。按 j % CHAINS 轮流累加，四 条链互相独立。

// 矩阵越小越快，越要跑够轮数把热身摊掉；大矩阵的列优先是秒级，少跑几轮
const int rounds = (N <= 128) ? 21 : (N <= 1024 ? 9 : 3);
const int repeat = (N <= 128) ? 300 : 1;

repeat 是把同一段跑 repeat 遍再除以 repeat。N=64 时整段只有 5 微秒，直接量会被时钟精度吃掉——单次 steady_clock::now() 要 16~18 ns（单元一 exp04）。跑 300 遍把总时长撑到毫秒级。

这是单元一第四讲那条规则的直接应用：要量一段比尺子还短的代码，就把它包进一批再摊薄。

sample([&] { sum_rowmajor<N>(m.data()); }, rounds, repeat, r_best, r_med);
sample([&] { sum_colmajor<N>(m.data()); }, rounds, repeat, c_best, c_med);
sample([&] { sum_blocked<N>(m.data(), 16); }, rounds, repeat, b_best, b_med);

三段各跑各的，取各自的最小值再比。不要在同一轮里混着跑三段再比总和，那样前一段会把缓存状态留给后一段，比的是跑的顺序。

代码运行结果

见上表。程序在结尾给了一条关于自己结论适用范围的提示：

倍率不是一个能背下来的常数。同一段代码，矩阵从 4 MB 长到 64 MB，
倍率就从 12.7 走到 20.0。报一个数字的时候，把规模一起报上。

常见坑

坑一：把「慢 20 倍」当成一个可以背的常数。 倍率随规模变。同一份源码，16KB 时是 1.1 倍，64MB 时是 20 倍。离开规模谈倍数没有意义。

坑二：以为分块要调很多参数。 本机的分块边长 16 不是调出来的，是算出来的：一行 64 字节，int 是 4 字节，16 个一行。换 double 就是 8 个一行。分块边长先取「一行装几个」，再看整个块装不装得下 L1，通常一次就中。

坑三：只盯着 L3 看。 组冲突发生在 L1，而 L1 只有 32KB。所有以 2 的幂为步长的访问都要检查一遍会不会全落进同一个组——这是布局问题的常见来源，单元三会再遇到。

教材指引

Guntheroth ch2 给了局部性的定性描述和「按行还是按列」的例子。分块在 ch10 讲数据结构优化时作为手法出现。

A 线任务 · probe v0.2：拐点扫描器

单元一造了 probe 的四个零件：分位数、样本集、计时器、对数直方图。这一版加第五个——拐点扫描器，把本单元手写的那套「扫一圈规模、算倍数、标台阶」收成一个函数。

struct SweepPoint {
std::size_t bytes = 0; // 工作集大小
std::size_t items = 0; // 计数单位个数
double ns_per_item = 0;
double ratio = 1.0; // 相对最小规模那一点的倍数
bool knee = false; // 相对上一点跳了 1.8 倍以上
};

template <typename Make, typename Body, typename ItemsOf>
std::vector<SweepPoint> sweep(const std::vector<std::size_t>& sizes, int rounds,
Make make, Body body, ItemsOf items_of);

三个设计决定，每一个都是被前面几讲的坑逼出来的。

一、make 和 body 分开，make 不计时。 造数据本身可能要几百毫秒（比如给 64MB 数组建一个随机环），混进计时结果会把结论带偏。分开之后，计时区间里只剩你要量的那段。

二、items_of 必传。 工作集的单位是字节，但你关心的单位可能是元素。少了这个换算，报出来的「每元素耗时」会跟着元素大小变，两种元素的代码就没法比。默认按字节算，要按元素算就传 bytes / 4。

三、台阶判据写死成常量，并且打印出来。

constexpr double KNEE_RATIO = 1.8;
const double base = pts.empty() ? 1.0 : pts.front().ns_per_item;
for (std::size_t i = 0; i < pts.size(); ++i) {
pts[i].ratio = base > 0 ? pts[i].ns_per_item / base : 1.0;
pts[i].knee = (i > 0) && (pts[i].ns_per_item > pts[i – 1].ns_per_item * KNEE_RATIO);
}

1.8 是经验值：缓存边界上通常跳 2 倍以上，噪声则远低于这个门槛。选 1.8 而不是「看着像台阶就算」，是为了让判据可以被别人复算。把判据写进代码、打印在输出里，别人才能不同意你的判据并且指出来。

验收：新工具不能改掉测法

probe_sweep_demo.cpp 用 probe::sweep 重做 exp06 的缓存阶梯，和手写版逐个对照。

$ g++ -std=c++23 -O2 -Wall -Wextra -o probe_sweep_demo probe_sweep_demo.cpp
$ taskset -c 15 ./probe_sweep_demo

工作集 计数单位 每单位耗时 相对最小
16 KB 12288 1.04 ns 1.00x
64 KB 49152 2.08 ns 2.00x ◀ 拐点
256 KB 196608 2.74 ns 2.64x
1 MB 786432 4.13 ns 3.98x
4 MB 3145728 9.89 ns 9.52x ◀ 拐点
16 MB 12582912 28.27 ns 27.22x ◀ 拐点
64 MB 50331648 84.95 ns 81.78x ◀ 拐点

和 exp06 手写版对照（每步延迟，取三轮最小值）：
工作集 exp06 手写 本 demo 偏差
16 KB 1.04 ns 1.04 ns -0.1%
1024 KB 5.36 ns 4.13 ns -23.0%
16384 KB 34.09 ns 28.27 ns -17.1%
65536 KB 90.01 ns 84.95 ns -5.6%

这次试验第一次跑出来的是错的，而且错得不明显。

第一版的 body 里有个热身循环（走 3/4 圈）加计时循环（走 3 圈），一共 3.75 圈；而 items_of 按元素个数算，等于声称只走了 1 圈。结果整条曲线整体偏了 3.75 倍——16KB 报 3.67 ns 而不是 0.98 ns。

每一档都偏高同一个倍数，曲线的形状一点没变。 台阶还在原来的位置，倍数关系也对（2.05x、2.76x、5.27x 全对）。单看那份输出，它像一份完全正常的阶梯数据。只有拿去和 exp06 对照，才看得出绝对值全错。

这就是 items_of 这个参数存在的理由，也是它的用法：它必须等于 body 里那件事实际发生了几次。 一次指针追逐算一次。sweep 用它来摊薄总时间，写错不会报错，只会让整条曲线整体缩放。

修法是把热身循环去掉——sweep 对每一档跑 5 轮取最小，第一轮的冷启动本来就会被后面几轮挤掉，exp06 手写版里那个热身循环在取最小的框架下是多余的。改完重跑，16KB、64KB、256KB、4MB、64MB 五档都落进了 8% 以内。

1MB 和 16MB 对不上，而这次不该改代码

剩下两档差得远。多跑几轮，看这两个数各自的分布：

1MB 在上面这轮读 4.13，另一轮读 5.91——它自己是散的，不是 demo 和 exp06 谁对谁错。

16MB 更极端：57 倍的范围。它压在 L3 容量（16MB）上，其他核多占一点 L3，这一档就换一个数。

关键的一步是：本次 exp06 重跑给的是 27.68 ns，和 demo 的 27.03~28.27 一致。 两边在 16MB 上其实是对得上的，对不上的是我那张标称表里的 34.09——它是当初采集时撞上干扰的一个偏高值。没有第二个来源对照，这个错会一直留在表里。

判断这类偏差有个比数值更快的办法：看形状。 曲线在 16MB 处鼓起来、导致 16MB 比 64MB 还慢，这是环境在说话——访存延迟不会这么走。看到非单调，先怀疑环境，别改代码。

A 线工具的输出里，规模和偏差都要跟着走。 只报一个绝对值，读者没法判断它是不是可信的。demo 把偏差算出来打在屏幕上，而不是在收尾文字里断言「对得上」——机器忙的时候它就该难看。

交付要求

B 线任务 · MiniQuote v0.2：第一次 profiling

先说工具

单元一要求你用分位数而不是平均值汇报性能。这一讲要的是另一件事：你的直觉指出的热点，和工具指出的热点，是不是同一批。

这一讲手上有四个工具，能力互补：

准备：

sudo sysctl kernel.perf_event_paranoid=-1 # perf 需要，valgrind 不需要
sudo apt install valgrind # gprof 随 binutils，本来就有

编译时记得带 -g。 不带的话 cachegrind 照样跑，但 cg_annotate 的函数表是空的——
它手上有计数器，没有符号，不知道那些数该挂到谁头上。

基线：v0.1 的分阶段读数

mini_quote_v01.cpp 是 B 线的起点。它按单元一的要求写成最直白的样子，故意留了两处浪费：

// v0.1 的浪费点之一：每条记录的每个字段各占一个 std::string。
// 5 个 string 就是 160 字节，而原始记录只有 24 字节。
struct StrTick {
std::string ts;
std::string order_id;
std::string price;
std::string qty;
std::string side;
};

跑 100 万条：

$ ./gen_quote 1000000 && ./mini_quote_v01

输入 ticks.bin，1000000 条，22.9 MB
StrTick 内存 152.6 MB（每条 160 字节，原始记录只有 24 字节）

分阶段耗时
读文件 13.5 ms 6.7%
建 StrTick 数组 65.5 ms 32.5%
逐条转字符串 74.7 ms 37.1%
建 map 并汇总 46.7 ms 23.2%
算汇总数字 0.9 ms 0.4%
合计 201.3 ms

跑之前先写下你猜的热点。 不是走过场——Guntheroth 说他凭直觉找到的热点列表和 profiler 给出的基本是同一批，但他依然认为直觉路线不可取，理由是他自己给的：直觉准不准是一回事，别人没法验证你的直觉是另一回事，后者在工程里更致命。

对照下面这张表，看两件事：你的猜测和实测差在哪，以及这个差距能不能靠「经验」消除。

一个容易忽略的读法：StrTick 数组占 152.6 MB，是原始数据 22.9 MB 的 6.7 倍。 单元一的 baseline 里 24MB 就已经超出本机 L3 了，到 152MB 时每一次访问都必然落到主存。这一版慢的根源不是「字符串转换慢」，是它把工作集撑大了 6.7 倍。这正是本单元前四讲要教的归因方式：先问搬运量，再问指令数。

逐条计时在这一层没有用

v0.1 里按单元一的要求记了单条处理延迟：

单条处理延迟（第 2 阶段内部，逐条计时）
p50 50.0 ns p90 51.0 ns p99 70.0 ns max 13786.0 ns n=1000000

先别看这几个数。 单元一量过一次 steady_clock::now() 要 16~18 ns，而这里每条记录只做 5 次 to_string，真实耗时在 15 ns 上下。也就是说这几个分位数里，有一大半是尺子自己的重量。

要量这一层，得用分块计时——把 4096 条包成一批，读一次时钟，再除以批大小。这是单元一 exp04 的结论在这里的第二次应用。

分阶段计时到这里就给到头了：它能告诉你「建 StrTick 数组占 32.5%」，答不出这 32.5% 是花在分配、拷贝还是构造上。前面几讲反复用的那两个问题，在这里要交给计数器：

perf stat 看到的：整个进程

$ taskset -c 15 perf stat -e L1-dcache-load-misses,cache-misses,cache-references \\
./mini_quote_v01

23,191,183 L1-dcache-load-misses
1,797,244 cache-misses
43,826,849 cache-references
0.246360417 seconds time elapsed

处理一次 24MB 输入，L1 读 miss 两千三百万次，L2 需求 miss 一百八十万次。

这两个数回答不了这一讲的问题——它们属于整个进程，不属于某个阶段。
要归到函数上，得换工具。

这两个数本身的稳定性也值得记一笔。同一份输入连跑五次：

L1 那个数稳，L2 那个晃两倍。理由在第三讲量过：L2 的容量余量小，
边界上那部分数据留不留得住，取决于这一轮跑的时候 L3 里还压着谁。
余量大的那一级可以只报一个数，贴着容量上限的那一级要带范围。
这条判断不是这一处特有的，后面每一级都这么看。

cachegrind 看到的：归到函数

$ g++ -std=c++23 -O2 -g -o mini_quote_v01_g mini_quote_v01.cpp
$ valgrind –tool=cachegrind –cache-sim=yes \\
–I1=32768,8,64 –D1=32768,8,64 –LL=1048576,8,64 \\
–cachegrind-out-file=cg.out ./mini_quote_v01_g
$ cg_annotate –show=Dr,D1mr,DLmr –threshold=0.5 cg.out

–LL 传的是 L2 的几何（1MB / 8 路）。cachegrind 只模拟两级，要让它的
「LL」对应本机的哪一级，就得把这个数传对。传成本机 L3 的 16MB 是另一个问题——
那时候 LL miss 指的是「连 L3 都没命中」。两者都会生效，输出头部会写明用的是哪一套。

–threshold=0.5 是必须的。默认阈值会把所有低于 1% 的行藏起来，
而这里正要看的就是那几行小条目——它们单独都不大，加起来才是大头。

关键列是 DLmr（last-level miss，读）：

Dr D1mr DLmr file:function
39,000,000 3,500,002 3,500,002 bits/basic_string.h
└ main 1,000,002 / ~vector<StrTick> 2,500,000
39,006,194 1,000,005 1,000,005 strtol_l.c:____strtoul_l_internal
40,741,642 337,809 52,358 bits/stl_tree.h

这一次运行里，D1 读 miss 共 709 万，LLd 读 miss 共 612 万。按份额排：

读 miss 里近四分之三落在三处，其中一处是字符串操作，一处是把字符串解析回数字。

strtoul 那 100 万次是 v0.1 里「把字符串解析回数字」那一步的账单，
分阶段计时把它记在「建 map 并汇总」名下，看不出它具体贵在解析上。
~vector<StrTick> 那 250 万次更隐蔽——销毁一百万个 StrTick 要读每个 string
的控制块，这笔开销在分阶段计时里根本没有单独一行。

这两条正好回答了「先说工具」里那个问题：分阶段计时给出的热点和计数器给出的热点，
在函数这一层对不上。 对不上的地方，就是 v0.2 要动的地方。

cachegrind 也要先说清它自己晃不晃。同一份二进制连跑四次：

写侧的 miss 逐位可复现，读侧会晃两个百分点。原因是它模拟的缓存按地址索引，
而堆上那些节点的地址每次运行都在变（ASLR 加分配器行为），
谁和谁撞在同一个组里随之改变。写侧多是大块顺序写，受地址摆放影响小。

这条值得单独记：「模拟器可复现」是个常见的默认假设，而它并不总成立。
一个工具跑出两个数时，先确认是工具在晃，还是被测对象在晃。这里两者都在晃，
而且晃的幅度比后面要用的那个 8 倍差距小一个数量级，结论不受影响。

两份计数对不上，而这一次也不该改代码

拿两个工具各自多次运行的范围去比：

两者相差 6 到 12 倍，远远超出它们各自的晃动幅度。 这个差距是真的。

两个数都没错，量的不是同一件事：

所以这里没有「谁更准」，只有分工：perf 告诉你真实机器上有多糟，
cachegrind 告诉你那些 miss 是哪几行代码产生的。 用错的工具问错的问题，
拿到的数再精确也没用。

用 gprof 对一遍

先按正常方式编：

$ g++ -std=c++23 -O2 -pg -Wall -Wextra -o mini_quote_v01_prof mini_quote_v01.cpp
$ ./mini_quote_v01_prof && gprof ./mini_quote_v01_prof gmon.out | head -8

Flat profile:

Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls ms/call ms/call name
87.50 0.14 0.14 main
12.50 0.16 0.02 7 2.86 2.86 (anonymous namespace)::Dist::p(double) const

这份平表没有用。两处问题：

把数据量加到 500 万条、档位降到 -O0（关掉内联），gprof 才给出像样的平表：

$ g++ -std=c++23 -O0 -pg -Wall -Wextra -o mq_prof_o0 mini_quote_v01.cpp
$ ./gen_quote 5000000 && ./mq_prof_o0 && gprof ./mq_prof_o0 gmon.out | head -14

现在平表有内容了，但顶上那条只占 10.94%（std::_Construct<StrTick>，就是建数组时的构造）。它答不出「三分之一的时间在建 StrTick 数组」——那条结论被摊碎在三百多个 std:: 条目里。

更麻烦的是 -O0 和 -O2 给出的热点排序不一样。 同一份源码、同一个 500 万条输入：

两件事同时发生：

还有第三件事：gprof 采样到的总时长只有 4.17 秒，而程序实际跑了 14.92 秒。三分之二的时间花在 gprof 看不见的地方——std::to_string、std::string::operator=、std::map 的实现都在 libstdc++ 动态库里，而 gprof 的采样直方图只覆盖主程序自己的代码段。

三条合起来指向同一个结论：gprof 答不了这一讲的问题，而它答不了的原因可以事先说清。
它的调用次数是准的（那部分它数得清楚），时间归因要给 -O0 打折，而且要知道打多少折。

四个工具放到一起，各自该问什么问题是分好的：

四个里只有 cachegrind 会直接指到源码行，代价是慢 50 倍、且不模拟预取器。
报它的数字时，这两件事要一起报出去。

v0.2 要交付的东西

Guntheroth 在书里讲过一个反例：他曾在调试器里测出 deque 比预期「慢一千倍」。这个数字让他花了大量时间去查 deque 的实现，最后发现是在调试器里测量导致的——调试器关掉了优化、改变了内存布局，量到的完全不是发布版本的行为。

上面那个 -O0 比 -O2 慢 15.2 倍的数，是同一类陷阱的另一种形态。数字本身没错，错的是把它当成发布版本的数字用。

本单元引用与数字速查卡

本机环境：g++ 15.2（Ubuntu），-std=c++23 -O2，AMD Ryzen 9 7940H（8 核 16 线程，L1d 32KB/核，L2 1MB/核，L3 16MB）。所有访存实验都用 taskset -c 15 绑核，取多轮最小值。

阶梯（exp06，三轮最小值）

16 MB 那一档最不稳。同一台机器在另一些时刻给出过 27.56 和 177.43 ns，而本次 exp06 重跑给的是 27.68 ns。表里的 34.09 是采集当时的一个偏高读数，不是这一档的真实值。 报这一档的数时，把范围一起报上。

三档访问顺序（exp07）

同一次运行配的计数器（每档 20 遍，已减 none 基线）：

L1 那一列三档相同（搬运量相同），L2 需求 miss 差两个数量级（预取器认不认得出）。
中间两列不能相加，理由见第三讲。

元素尺寸扫描（exp08，有用数据恒为 16 MB，访问次数恒为 4194304）

遍历顺序（exp09）

N=1024 的计数器（每档 30 遍 = 31,457,280 次访问，已减 none 基线）：

行优先的 L1 列是理论值 1,966,080（65536 条 line × 30 遍）加 1% 上下。
⚠ 这一格是两个小数字相减得到的，几次运行能差一倍；列优先那格差两个数量级，怎么晃都不翻。

MiniQuote v0.1（1M 条，-O2）

StrTick 内存 152.6 MB（每条 160 B，原始记录 24 B）。

两套计数器读数（MiniQuote v0.1，1M 条）

两个工具各跑一次，不是同一次运行：

L1 差 1.8 倍，下一级差 6.5 倍，都远大于两个工具各自的晃动。来源见 B 线：
cachegrind 不模拟预取器，而 perf 的 cache-misses 只数需求 miss。
两套数不能互相验证，只能互相补充。

cg_annotate –show=Dr,D1mr,DLmr –threshold=0.5 的前几行
（-O2 -g 构建；不带 -g 表是空的，不带 –threshold 小条目会被藏起来）：

工具折损（5M 条）

干扰量级

出自教材

练习与参考答案

练习 1（必做）：把 exp06 的扫描点加密到 2 倍递增（16、32、64、128……），在 16KB~64KB 和 512KB~1MB 两段各补几个点。重跑，回答：L1 的边界更接近 32KB 还是 64KB？和标称的 32KB 差多少？

参考答案：边界会落在一个区间里，不会落在 32KB 这个点上。原因有三个：L1 是 8 路组相联而非全相联，实际可用的利用率低于 100%；L1 里还要放指令、TLB 表项等；随机环本身的元数据也占空间。报边界时报区间。 这道题的收获是「标称容量」和「实测边界」不是一回事。

练习 2：拿 exp07 改一个参数——把随机那一档的 idx 改成排好序的（不再是随机顺序），其他不动，重跑。三档现在各是什么速率？

参考答案：排好序之后它就是顺序访问的一个稀疏版本，速率会回到 45 GB/s 上下，和「步长 16」那一档几乎一样。这道题想说明的是：决定成本的是「地址流能不能被预测」，取了多少元素只在其次。 稀疏本身不贵，乱才贵。

练习 3：用 exp08 的思路，设计一个实验回答这个问题：std::vector<int> 和 std::vector<char>，求和一遍，哪个快？为什么？

参考答案：要先把「一共多少个元素」固定住，否则两个数组的总字节数不同，比的是容量不是元素尺寸。固定元素数 N 之后，vector<int> 搬 4N 字节，vector<char> 搬 N 字节——但两者都可能落到「一行装得下多个」的区间里，实际速率会很接近，差异主要在每周期能发射的访存指令数和向量化宽度上。这道题的价值是暴露一个常见错误：比较两种元素尺寸时，不固定元素数就得不出干净结论。

练习 4：exp09 的列优先在 N=1024 时慢 12.7 倍，原因是步长 4096 字节对 L1 的 64 个组取模等于 0。请算出 N 取多少时列优先的步长会不和 L1 组数冲突，并验证。

参考答案：步长 = N × 4 字节，除以 64 字节得到相隔的 line 数 = N/16。要让 (N/16) mod 64 ≠ 0，N 不能是 1024 的倍数。取 N = 1040（步长 4160 字节 = 65 条 line，65 mod 64 = 1），组冲突消失，列优先应该接近行优先。跑一下就能验证——exp09_locality.cpp 里把 N 从 1024 换成 1040 即可。这道题说明「2 的幂」在布局问题里是个需要主动怀疑的数字。

练习 5：B 线的 v0.1 里，StrTick 数组占 152.6 MB 而原始记录只有 22.9 MB。用本单元第四讲的换算估一下：如果去掉 StrTick 这一层，只保留 vector<Tick>，第二阶段的时间大概能降到多少？实际改一版验证。

参考答案：预估的思路是「耗时 ≈ 搬运量 ÷ 带宽」。StrTick 那一层要搬 152.6 MB（构造一次）+ 152.6 MB（填字段），Tick 那一层只要搬 22.9 MB + 22.9 MB。粗略估计能降到原来的 15% 上下。实际改完可能对不上——因为「转字符串」那一步的代价不只是搬运，还有 to_string 本身的指令数。对不上的部分就是这个模型的边界，把它记下来。

验收自测（含答案）