缓存友好与数据布局——本机分层延迟拐点、2.77 倍的 AoS/SoA 与测不出来的跨行惩罚
环境：Windows 11 x64（build 26200），GCC 13.1.0（MinGW-w64，全路径
D:/Qt/Tools/mingw1310_64/bin/gcc.exe；PATH 上那个是 Strawberry 4.9.2 32 位），gcc -std=gnu11 -O2，对照构建一律加-fno-tree-vectorize（两个 exe 并排跑，凡是比值随构建档位变化的地方都写了两套）。计时QueryPerformanceCounter，本机频率 10,000,000 Hz ⇒ 分辨率 100ns，两次连续调用差 0 个 tick（第 9 节实测过），所以本文的 ns/元素全部是 16 万到 1,600 万次累计摊出来的。耗时取 3–5 次的中位数（区间），AoS/SoA 那组因为进程内重复 5 次而是最小值（下面表里标明）。QueryWorkingSetEx一类只有 OS 专栏有、本节用不上。同期机器上还有 3 个 agent 在跑，所以绝对纳秒只当区间看，比值比绝对值可靠；校验和（同一算法两种布局必须得同一个数）每次都核。缓存几何信息没读到（第二节末说明原因），所以文中”行 = 64 字节”是按主流 x86 假设 + 用实测拐点反推的，不是从系统信息里读出来的。探针在%TEMP%/agents/dbg2/（d1.c–d3.c与o2_*.out/nv_*.out）。
一、先量尺子：本机分层延迟的三个拐点
方法只有一条：造一条随机环，每个节点是一条 64 字节记录，next 写在记录内部（不在旁表里，避免旁表自己把被测数据挤出去）。每次顺着环跳一步，就是”必然未命中的一个缓存行的延迟”。跨度从小到大扫 16 档：
跨度(KB) 行数 ns/次 落在哪
8/16/32/48 128–768 1.38 平台一（最里层）
64/128/256 1024–4096 3.66/3.38/3.71 平台二
512/1024 8192–16384 4.21/5.59
2048 32768 19.59 ← 拐点
4096 65536 99.34 平台三（最外层）
8192…131072 … 90.46–109.15 平台三，平坦三条读数：
- 最里层平台是 1.38 ns，而且平到 48 KB 才开始动（64 KB 就跳到 3.66）。这条拐点位置就是”最里层缓存装不下 48 KB 之后的东西”的直接证据。1.38 ns ÷（约 4 GHz）≈ 5–6 个周期，是典型 L1 命中延迟量级——但本机 L1 的标称容量我没读到（见本节末），所以这句话只能按”拐点在 48→64 KB 之间”来用。
- 中间平台不平整，是 3.38 → 5.59 缓慢爬升（64 KB–1 MB），到 2 MB 突然 19.59，4 MB 起就是 90–109 ns 的地板。“多一级缓存”在延迟上的表现不是台阶而是斜坡——真正断崖式的是最后那一级（约 18 倍于 1 MB 处）。
- 最外层 90–109 ns 是平坦的：一旦每步都要出到最外层，跨度再大一倍也不会更慢（行数从 65,536 到 2,097,152，ns/次只从 99.34 到 99.34 之间晃）。所以”内存墙”的成本是每次未命中的单价，不是”数据多大”本身。
顺序对照（同一块 buffer，按行号顺序读，测的是能被预取器吃到的那一面）：
顺序 64 KB 2.34 ns/次 顺序 1 MB 2.39 ns/次
顺序 16 MB 2.99 ns/次 顺序 128 MB 3.68 ns/次
随机 16 MB 93.65 ns/次 → 31.3 倍
随机 128 MB 99.34 ns/次 → 27.0 倍同一块内存、同样的记录条数，只是把访问顺序从”随机”改成”顺序”，单价从 99.34 掉到 3.68 纳秒。 这就是本节所有其它实验的物理学基础：硬件能预测的东西根本不去最外层。
顺带一条失败的取证也要留：GetLogicalProcessorInformationEx(RelationAll, …) 在本机一条 RelationCache 都没枚举出来（循环按 e->Size 步进，输出 0 行；改成 GetLogicalProcessorInformation 老接口没做）。所以”L1=32KB / L2=?KB / L3=12MB”这类标称数字本节未实测，文中凡是用到行大小 64 字节的地方，依据是第四节实测的比值恰好等于字节比（15.8 vs 16）以及第三节步长 8（8×8 字节 = 64 字节）处触碰成本明显跃升，是反推，不是读回来的。
二、步长与预取：贵的不是”跨行”，是”每行只用到一点点”
8 MB 的 int64 数组（1,048,576 个元素，一行装 8 个），从第 0 个开始按步长 s 取元素求和。5 次取中位数：
| 步长(元素) | 每次触碰 ns，O2（区间） | 关掉向量化 | 一行里有用的字节 | 有用字节 / ns |
|---|---|---|---|---|
| 1 | 0.51（0.49–0.54） | 0.53 | 64 | 15.6 |
| 2 | 0.84（0.69–0.96） | 0.53 | 32 | 9.4 |
| 4 | 0.90（0.82–1.16） | 0.76 | 16 | 8.9 |
| 8 | 1.38（1.22–2.11） | 1.31 | 8 | 5.8 |
| 16 | 2.12（1.96–3.94） | 3.41 | 8 | 3.8 |
| 64 | 4.65（3.47–7.28） | — | 8 | 1.7 |
| 256 / 1024 | 2.54 / 2.54 | — | 8 | 3.1 |
最后一列是换算出来的（= 有用字节 ÷ 单次触碰成本），它是这张表真正想给的量：步长 1 时每纳秒拿到 15.6 字节有用数据，步长 8（正好一行一个）只剩 5.8，步长 64 剩 1.7。 单看”每次触碰多少钱”反而会误判——步长 8 的 1.38 ns 比步长 1 的 0.51 ns 更便宜，但它一行只搬回 8 字节。
两个细节值得记住：
- 步长 2/4 的差距远小于 8/16：0.51 → 0.84 → 0.90 是”同一行里多取几个”的边际成本（约 0.3 ns/次，是 load+add 的量级），1.38 之后每次触碰都要新行，成本立刻换档。拐点正好在 8 = 64÷8 处，这是”行 = 64 字节”的第二条反推证据。
- 步长 64 的 4.65 ns 是整张表里最差的，比 256/1024（2.54）还差一倍。合理解释是 s=64（512 字节）时步长仍在硬件预取器的跟踪范围内但每行只取一个，于是预取器把带宽花在永远用不到的相邻行上；s=256（2 KB）超出跟踪能力，预取器干脆放弃，剩下的只是纯未命中。这一条是解释，不是结论——它需要带宽侧计数器才能钉死，本机没有
perf，第 6 节（还没展开）才谈采样式工具能不能给出。
手工预取呢？同一份代码，把 __builtin_prefetch(&a[i+d]) 放进循环，d 从 0 到 256：
d=-1(不发) 0.413 d=0 0.435 d=8 0.442 d=16 2.076(区间 0.476–2.511)
d=32 1.759 d=64 1.146 d=128 0.860 d=256 0.917 （O2）
d=-1 0.468 d=0 0.523 d=8 0.556 d=16 2.012 （关向量化，同一结论）没有任何一档快过”不发预取”，最差的一档慢 5.0 倍。 两个构建档位都一样，所以不是向量化被搞坏的副产物。合理解释同样在本机的数字里：第一节已经量到顺序扫描的单价是 3.68 ns/行，而这里每元素 0.413 ns/8 字节 = 3.3 ns/行——顺序流本来就一直在预取之前，硬件已经把行拿到了，软件再加一条指令只有成本没有收益。工程判据因此很硬：只有在”访问模式硬件预测不到、而你自己能算出下一个地址”的地方才值得手工预取（第一节 31 倍差距的随机跳就是这类，但它需要的是一条链而不是一个标量加法，本探针没做那个版本，这一处属于推断）。
三、AoS 与 SoA：2.77 倍是真的，2.31 倍有一半不是缓存
100 万条 {float a,b,c,d;}（sizeof=16，一行 4 条），两种摆法各存一份同样的数据。为了不把结论压在”加法依赖链”上，两种摆法都用 4 个累加器打散依赖（不加这层的版本测出来是 1.07 vs 0.96 ns/元素、比值 1.11，那是累加器延迟封顶，不是内存——第 9 节”负载要挑循环携带依赖的”在这里反着咬了我一口）。5 次取最小值：
| 用法 | AoS | SoA | 比值 O2 | 比值 关向量化 |
|---|---|---|---|---|
只用 1 个字段（x.a） | 0.73 ns/元素，770 µs | 0.26 ns/元素，278 µs | 2.77 | 2.13 |
| 用全部 4 个字段 | 1.45 ns/元素，1524 µs | 0.63 ns/元素，658 µs | 2.31 | 1.64 |
这两行的成因不一样，混起来讲就成了 folklore：
- 第一行是缓存。AoS 为了拿 4 字节的
a必须把整条 16 字节都拉进来 → 触碰 16 MB；SoA 只碰 4 MB 那个数组。字节比是 4，实测比值只有 2.77——差额说明 AoS 那条 16 MB 的顺序流并没有每次都付最外层的单价（第一节：顺序扫 16 MB 是 2.99 ns/行，而随机跳同一跨度要 93.65 ns/行，预取器把顺序这一半买断了）。别把 2.77 说成 4，那是抄笔记不是测量。 - 第二行不全是缓存：两种摆法触碰的字节完全相同（都是 16 MB，都要读全部字段）。可是 SoA 还快 2.31 倍。把向量化关掉，比值掉到 1.64。所以这 2.31 里大约有 0.67 倍是**“每条记录内部要做 4 路横向求和”的算术/向量化代价**，不是局部性代价。
objdump/-S层面的对照没做（本节未实测这一点的具体指令构成），但”换构建档位比值就变”本身已经足够排除”纯粹是缓存”的说法。
可操作的结论只有一句：AoS 变 SoA 的收益上限，等于”少触碰了多少字节”；如果字段本来就要全用，收益主要来自编译器友好，得实测才知道还在不在。
四、把热字段和冷字段挤在同一行里：15.8 倍，而且几乎正好是字节比
typedef struct { int hot; char cold[60]; } —— 一只对象正好 64 字节，热字段只有 4 字节，遍历只读 hot。对照是同样 262,144 只对象的纯热数组（int[]，1 MB）：
只读 hot：HC=3.39/3.18/3.09 ns/只 分离=0.21/0.20/0.20 ns/只 比值=15.80/15.83/15.82 字节比=64/4=16三次重复的比值都在 15.8，字节比是 16。 这是全文最干净的一条线性关系：代价 ≈ 被触碰的字节数，别的因素（对齐、行内位置、预取器状态）在这一项里合计不到 2%。换算成行也对得上：分离版 0.20 ns/元素 = 每 64 字节行 3.2 ns，与第一节顺序扫描在 64 KB–1 MB 档的 2.34–2.39 ns/行同量级；混排版 3.18 ns/元素 = 每行 3.18 ns（每行只用 4 字节），它跑在 16.8 MB 的跨度上，顺序流已被预取器吃下，但多触碰了 16 倍的行。
这条和第三节第一行是同一个物理量的两个刻度：AoS 的字段比是 16/4 = 4（16 字节里只用 4 字节），这里是 64/4 = 16。
它同时也是”对齐填充”的账单。 第五节要讲的伪共享解法是 alignas(64)，而这一节刚测完：把一只 4 字节的对象填满到 64 字节，单线程遍历时付 15.8 倍。同一件事，在有两个核分别碰它的时候是救命的，在只有一个线程扫描它的时候是纯税。 所以”要不要填充”不能问”64 字节对不对”，只能问”这行会被几个核碰、被扫描多少次”。
五、伪共享：本节不重测，接两个已发布的数字，然后把”填充的账”算清
同一段计数器代码，共享 vs 独占，本专栏已经有两份实测，本文不重复取数：
- 本栏第 2 节（日志与可定位性）：全局共享原子计数器 12.4 ns/次，改成每线程独占一条缓存行 2.1 ns/次（5.9 倍）；并且把共享变量本身对齐到 64 字节毫无改善（12.3 vs 12.4）——“对齐”不解决伪共享，“独占”才解决，这条经常被读反。
- 并发专栏第 8 节（原子操作与内存序）：8 个计数器挤同一行 vs 各占一行，快慢比 1.38–3.21 倍（4 轮：1.46/0.45、1.24/0.47、1.32/0.50、1.40/1.02 ms），而且两种写法结果完全正确，只有计时能发现。
本文补的是那半边账：填充付出的空间，什么时候会被读回来。 第四节的 15.8 倍就是答案的下界——如果一个 alignas(64) 的槽位数组后来要被单线程整表扫描（回收、压缩、序列化、诊断转储），那这笔空间债会以遍历时长的形式一次还清，而且扫描次数越多越亏。三档判据：
- 多个核高频写同一行 → 必须独占（5.9 倍在这里）。
- 每核写一次、之后主要读（例如收尾时汇总的 per-thread 统计） → 不必填 64 字节，让它紧凑，因为伪共享只在”写”的时候收钱。并发第 8 节还留了一条更锋利的对照：分片在”写者多且不需要即时全局值”时才划算，需要全局值时合并的那次读写反而比单点累加更慢——本文引用的那 1.38–3.21 倍就是同一次实验里”挤同一行 vs 各占一行”的那一半。
- 填了之后还要整表扫描 → 先看第四节那条 15.8 倍，再决定；折中办法是冷热分离：把可写的计数器放紧凑数组（各占一行），把只读的元数据放另一个数组，两边都不吃亏。
本节没有自己造多线程探针（同期机器上还有 3 个 agent，跑不出可信的并发比值），这一点算作本节的边界而不是缺陷。
六、跨缓存行的读：本机测不出惩罚
教科书说”结构别跨行”。探针：同一份 uint64_t[1,048,576]，一组起点 8 字节对齐（每 8 条才可能跨一次 64B 行），另一组起点偏移 4 字节（4,12,20,…,60,68，每第 8 条必然跨行）。校验和两边完全相同（549,755,289,600）。
第1次 aligned 0.678 ns/元素 offset4 0.660 比值 0.973
第2次 aligned 0.554 offset4 0.546 比值 0.986
第3次 aligned 0.785 offset4 0.555 比值 0.707比值 0.707–0.986，全部 ≤1，即”跨行”版本没有一次更慢，第三次还”快了 30%“——而同一组里 aligned 自己三次就散布在 0.554–0.785（1.42 倍），所以这一档的读数基本被噪声主导，能说的只有”没测到惩罚”。结论：在这台 x86 上，自然长度的读跨不跨行不是成本项。真正有成本的是触碰更多行——这才是第三节和第四节的主题。所以”跨行惩罚”这条经验要改成：“别为了对齐把结构撑大（第四节：撑到 64 字节就付 15.8 倍），跨不跨行本身在单线程扫描里量不出来。”
非 2 的幂的记录尺寸另有小幅差别，方向和”每行装几条”一致：
记录 20 B（每行 3.20 条） 0.918 ns/元素 vs 记录 24 B（每行 2.67 条） 1.010 ns/元素
比值 0.909，字节比 1.2024/20 = 1.20 的字节差，换来 1.10 的时间差（比值 0.909 表示 20B 版更快 10%）——这一项落在”字节数主导、但不完全成正比”的区间，因为 1 MB×20 与 24 MB 都还在层里。写紧凑结构划不划算，取决于它有没有把你推出那一档。
七、分支预测与数据依赖：7.81 倍，以及它消失的条件
经典实验（32,768 个 uint8_t = 32 KB，正好落在第一节那个 1.38 ns 平台里，重复 300 遍，共 9,830,400 次判定）：
| 写法 | 随机数据 | 有序数据 | 随机/有序 |
|---|---|---|---|
if (v < 128) sum += v; | 2.899 ns/元素 | 0.371 | 7.81 倍 |
sum += (v < 128) ? v : 0; | 0.486 | 0.482 | 1.01 倍 |
两条路径都写 sum（挡住 if-conversion） | 3.090 | 0.489 | 6.32 倍 |
全命中数据（v = i & 0x7f），if 版 | 0.402 | — | — |
关掉向量化重跑，三行比值是 7.38 / 1.02 / 6.72 —— 同一量级，结论不依赖构建档位。
三条要分开读的结论：
-
误预测确实贵：2.899 vs 0.371，7.81 倍；而且”全命中”只有 0.402，说明贵的不是那条比较，是分支方向猜不准时那条流水线冲刷（第一节的 L1 命中单价是 1.38 ns，一次误预测的冲刷量级正好和它同一档，这不是巧合但也不是证明）。
-
无分支写法把 7.81 倍抹平成 1.01 倍：0.486/0.482 与数据分布无关。代价是它比”有序 + if”（0.371）慢 31%——分支不是要消灭的敌人，不可预测才是；数据有序时留着分支更快。第 7 节（读汇编）已经实测过
int leaf(int x){return x>0?x:-x;}在-O2下编成mov/cltd/xor/sub四条无分支指令、连栈帧都没有，那是编译器替你做这个选择的现成例子。 -
“编译器会不会 if-convert”要自己查，不能猜：
-S输出里 variant0 的内层循环是cmpl $127, %r12d jbe .L6 ... ja .L25真分支（
jbe/ja）还在，所以那 7.81 倍不是我自己造出来的假象；而 variant1（三目）在计时上表现为”与分布无关的 1.01 倍”，与它被折成无分支的行为一致。这里必须诚实标一句：我没有逐条比对 variant1 循环体里的指令（第 9 节那条”交付前用objdump -d数指令”在这一项上我只做了一半），所以第 2 条里的”无分支”是从计时特征推的，不是从反汇编读出来的。
数据依赖的另一个方向也在这张表里：variant2 之所以必须写出来，是因为 if (v<128) sum+=v; 这种形状太容易被折成 cmov/掩码加，一旦折掉，“分支预测”这个实验对象就消失了——这正是第 9 节说的”保活成功 ≠ 测到你想测的东西”在数据布局上的版本。
八、小结
- 本机分层延迟实测：1.38 ns（≤48 KB）→ 3.38–5.59 ns（64 KB–1 MB）→ 19.59 ns（2 MB）→ 90–109 ns（≥4 MB 平坦）；同一块 128 MB，顺序 3.68 vs 随机 99.34 ns = 27.0 倍，16 MB 是 2.99 vs 93.65 = 31.3 倍。缓存几何（L1/L2/L3 标称容量、行大小）没从系统信息读到，文中 64 字节行是从步长 8 处的跃升和 15.8≈16 的字节比反推的。
- 步长的正确指标是”有用字节/纳秒”：15.6（s=1）→ 5.8（s=8，正好一行一个）→ 1.7（s=64）。单看每次触碰多少钱会判反（s=8 的 1.38 ns 比 s=1 的 0.51 ns “便宜”，但一行只搬回 8 字节）。
- 手工
__builtin_prefetch在顺序扫描上全线无效甚至有害（0.413 → 最差 2.076，慢 5.0 倍；两个构建档位同结论）。硬件预取已经把顺序流买断了，软件预取只在”模式可算出但硬件预测不到”的地方才有位置。 - AoS→SoA 的收益要拆成两笔：只读 1/4 字段是 2.77 倍（字节比 4，因为一部分还留在层里，别抄成 4 倍）；读全部字段字节数相同却还有 2.31 倍，关掉向量化缩成 1.64，所以那部分是编译器友好不是局部性。测之前先把累加器拆成 4 路，否则依赖链封顶，实测只剩 1.11 倍（我第一版就栽在这上面）。
- 热冷字段挤在一行 = 15.8 倍遍历税，且比值几乎正好等于字节比 16 → 代价基本等于被触碰的字节数。同一件事反过来读就是
alignas(64)的账单。 - 伪共享本节不重测：本栏第 2 节 12.4→2.1 ns（5.9 倍，对齐共享变量没用、独占才有用），并发第 8 节 1.38–3.21 倍且结果永远正确。要补的是账：多个核高频写同一行才值得填 64 字节；填完还要整表扫描的话，第四节那 15.8 倍会一次还清。
- 跨缓存行的 8 字节读在本机测不出惩罚（比值 0.707–0.986，校验和一致），所以别为对齐把结构撑大；非 2 的幂记录尺寸的影响（20 B vs 24 B，比值 0.909）方向和字节数一致但被”还在不在同一档”打折。
- 分支：随机 2.899 vs 有序 0.371 ns/元素（7.81 倍），三目版 1.01 倍；无分支并不总赢——有序数据下留着分支反而快 31%。做这类实验要先确认分支没被折掉（
-S里的jbe/ja），这一条我在一项上没做完，已在文中标明。