🏠 总目录📚 本教程 03 · cache 与数据布局 ← →
📑 本页目录(点开跳转)

03 · cache 与数据布局

实验记录怎么读

本页原有耗时、内存、报错和环境值保留为原文记录;本轮内容审校未逐项复跑这些实验。版本、硬件、数据和测量方法都会影响结果,示例中的倍数也不是保证。需要复现时先核对依赖版本,再在同一输入下比较。

⏱ 92 分钟 | ⭐ 同样的数据、同样的加法、同样的次数,只换遍历顺序 —— 实跑慢 16 倍

🎯 一句话

CPU 缓存通常以 cache line 为单位填充;本章用 64 字节行模型解释局部性,下面打印的标准库常量并非硬件实测。 你所有关于「快慢」的直觉都得从这一条重新长出来 —— 因为你用不用得上那一整块,决定了同一段代码是快还是慢十几倍。

🧩 一、先把那十几倍跑出来

⚠️ 先划一条界,因为这一章和 NumPy 板块隔得很近:

问题 归哪
「一个数组对象怎么描述自己的排布」「切片为什么有时是视图有时是拷贝」「为什么有时要重排一次」 《NumPy 与向量化思维》04
⭐ 「内存是按多大一块搬的」「为什么挨着访问就快」 这一章(硬件层)

这一章从头到尾只有一块裸内存和一个循环,不涉及任何数组对象的描述方式。下面这段就是全章的引子:

// c03_order.cpp
// g++ -O2 -std=c++17 c03_order.cpp -o c03_order
#include <cstdio>
#include <vector>
#include <chrono>

using Clock = std::chrono::steady_clock;
static double ms_since(Clock::time_point t) {
    return std::chrono::duration<double, std::milli>(Clock::now() - t).count();
}

int main() {
    const int N = 4096;                       // 4096 x 4096 个 double = 128 MB
    std::vector<double> m((size_t)N * N, 1.0);

    // ① 一行一行走:内存里挨着的元素,挨着访问
    auto t = Clock::now();
    double s1 = 0;
    for (int r = 0; r < N; ++r)
        for (int c = 0; c < N; ++c)
            s1 += m[(size_t)r * N + c];
    double t_row = ms_since(t);

    // ② 一列一列走:每次跳 N 个 double = 32768 字节
    t = Clock::now();
    double s2 = 0;
    for (int c = 0; c < N; ++c)
        for (int r = 0; r < N; ++r)
            s2 += m[(size_t)r * N + c];
    double t_col = ms_since(t);

    std::printf("矩阵 %d x %d double = %.0f MB\n", N, N, (double)N*N*8/1048576.0);
    std::printf("① 按行走: %8.2f ms   和 = %.0f\n", t_row, s1);
    std::printf("② 按列走: %8.2f ms   和 = %.0f\n", t_col, s2);
    std::printf("   慢了   : %8.2f 倍   (两个和一样吗: %s)\n",
                t_col / t_row, s1 == s2 ? "一样" : "不一样");
    return 0;
}

跑三次的实跑结果(g++ 15.1.0,-O2 -std=c++17):

次 ① 按行走 ② 按列走 慢了
1 13.64 ms 222.46 ms 16.31 倍
2 13.61 ms 223.18 ms 16.40 倍
3 13.60 ms 240.33 ms 17.67 倍

⭐ 两边做的加法一模一样:同样 1677 万次浮点加,同样的 128 MB 数据,两个和都是 16777216,连指令都几乎一样。唯一的差别是访问内存的顺序。

⚠️ 这不是「优化技巧」,这是默认状态下你可能白白损失掉的十几倍。而且注意:写成 ② 那样并不奇怪 —— 「按列求和」是个再自然不过的需求,谁都可能顺手写出来。

🧩 二、CPU 不按元素取数,按「一条」取

选读 · 主存与 CPU 多级缓存,各自在等什么?

主存承载较大的运行中数据,缓存把其中近期或邻近会用到的行留在更快的层级。下面只画常见桌面/服务器 CPU 对普通可缓存内存的定性模型:越靠近核心,通常容量越小、命中延迟越低;向主存走,通常容量更大、访问等待更长。不是固定 KB/ns 表,也不是本机测量。

层级典型职责与容量关系典型访问等待
L1贴近核心的小缓存,常分指令与数据;先满足热点访问命中通常最快
L2通常比本核 L1 大,承接部分 L1 未命中命中通常比 L1 等待长,但比访问主存短
L3 / 末级缓存若实现提供,通常更大,也可能由多个核心共享命中通常再慢一些;共享和互连也会影响等待
主存承载比这些 CPU 缓存更大的工作数据;普通程序按地址读写,并非直接选择某个 L1 槽位通常比缓存命中等待长;不是每次读都实际走到这里

这些缓存的查找、填充与替换通常由硬件管理,程序主要通过访问局部性影响命中;系统软件仍能配置缓存属性等。SRAM 常用于片上 CPU 缓存,DRAM 常用于主存,但这是典型实现,不是角色的定义:也存在 DRAM 充当较大缓存、内存位于封装内等设计。缓存层数、共享关系、位置和实际延迟必须查对应架构。

一次读的最小轨迹:假设数据已在主存、属于普通可缓存区域,没有其他核心持有较新的副本,暂不考虑预取等细节:

  1. 核心读某个元素:若所在行在 L1 有有效可用副本,就是命中,直接满足这次读。
  2. L1 未命中,继续由较低层缓存等寻找;若 L2 或末级缓存命中,就不必访问主存。相关缓存都未能提供时,请求才到主存,取回包含该元素的缓存行,按该实现的策略填充适用缓存,并满足读。
  3. 随后访问同一行内的邻近元素,若行仍有效且未被替换,就可能命中,少一次较远层级的取回。这正是下面连续走访与跨步走访的布局动机;不能据此保证固定加速倍数。

写入另有边界:写回式缓存可以先保留较新的脏行,之后再按实现向较低层/主存写回;直写策略不同。在支持一致性的系统里,其他核心还可能从持有较新数据的缓存取得行,不必先等 DRAM 更新。缓存一致性、写回完成与线程间访问次序是不同问题;C++ 线程仍要用正确的同步,不能靠“等缓存回写”保证普通共享变量安全。这里不展开一致性协议或设备访问规则。

依据:Intel SDM Vol.3A 第14章 Memory Cache Control(此处核对 093 版)、Intel 内存层次说明、Intel Technology Journal 2013:内存技术取舍。仅用来核对机制,不把文档示例参数或原库常量输出当作当前机器的缓存规格。

解释上一节差异的一个关键是:缓存通常以一整行填充,而程序可能只用其中一个数,这行叫 cache line(缓存行)。具体事务粒度、缓存层级和预取还取决于硬件,不能把它理解成所有内存访问路径的统一最小单位。

先看标准库给出的建议间距。std::hardware_destructive_interference_size 是实现定义的 constexpr 常量,表示并发访问对象为避免实现引入的争用所建议的最小间距;它不是运行时查询 CPU 缓存行长度的接口。依据:C++17 草案 hardware interference size。原文件名 probe 保留,但其职责只是打印库常量:

// c03_probe.cpp:打印实现建议常量,不探测硬件
// g++ -O2 -std=c++17 c03_probe.cpp -o c03_probe
#include <cstdio>
#include <new>

int main() {
#ifdef __cpp_lib_hardware_interference_size
    std::printf("hardware_destructive_interference_size = %zu\n",
                std::hardware_destructive_interference_size);
#else
    std::printf("(标准库没提供这个常量)\n");
#endif
    return 0;
}

历史编译环境打印的库常量(本轮未作硬件测量):

hardware_destructive_interference_size = 64

⭐ 历史输出是 64 字节的建议值。 这不足以证明本机实际 cache line 长度。本章后续除历史测量表外,所有 64 字节装载、利用率与 padding 推导都以假设缓存行为 64 字节为教学模型;真实平台须查对应架构/缓存层级资料或使用专门硬件查询,并另行验证。按这个模型比较第一节两种走法:

模型:每行 64 字节 用得上几个 double 白搬了
① 按行走 里面 8 个 double 全是接下来马上要用的 8 个 0%
② 按列走 只用第一个,剩下 7 个下次用到时早被挤出去了 1 个 87.5%
可选深入:空间局部性与时间局部性各是哪一笔收益?

靠近的地址,与刚用过的数据

空间局部性是访问一个地址后,又访问附近地址;本章行遍历、连续数组与 SoA 的有效字节比例是例子。时间局部性是近期访问的数据较快再被访问;工作集装得下时,重复复用同一小块数据可能命中较近缓存,工作集放大后效果会改变。它们是访问模式,不是无条件的性能保证。

本章的 CPU 硬件预取与缓存实验不解释操作系统页缓存的预读、回写或污染策略,二者不能互相代替。第二节打印的常量仍只是实现建议间距;64 字节只用于已声明的教学模型,不能因“有空间局部性”就反推实际缓存行大小。

🚦 把这件事直接量出来

如果成本真的挂在「搬了多少条」而不是「取了多少个数」上,那就应该能观察到这样一个现象:取的元素少 16 倍,耗时却不会少 16 倍。

// c03_line.cpp
// g++ -O2 -std=c++17 c03_line.cpp -o c03_line
#include <cstdio>
#include <vector>
#include <chrono>

using Clock = std::chrono::steady_clock;
static double ms_since(Clock::time_point t) {
    return std::chrono::duration<double, std::milli>(Clock::now() - t).count();
}

int main() {
    const size_t BYTES = 128u << 20;             // ⭐ 摸的范围固定 128 MB,比任何一级缓存都大
    const size_t N = BYTES / sizeof(int);
    std::vector<int> a(N, 1);
    const int REP = 5;                           // 每种间隔量 5 遍取最快的一遍

    std::printf("固定摸完同样的 %zu MB,只改「隔几个 int 取一个」\n", BYTES >> 20);
    std::printf("  间隔(字节)      取了多少个   总耗时(ms)\n");

    for (size_t k = 1; k <= 64; k *= 2) {
        double best = 1e18;
        long long s = 0;
        for (int r = 0; r < REP; ++r) {
            auto t = Clock::now();
            s = 0;
            for (size_t i = 0; i < N; i += k) s += a[i];
            double ms = ms_since(t);
            if (ms < best) best = ms;
        }
        std::printf("  %8zu   %12lld   %10.2f\n", k * sizeof(int), s, best);
    }
    return 0;
}

实跑(三次结果几乎一致,这里取第一次):

相邻两次隔多远 取了多少个元素 总耗时
4 字节 33554432 19.21 ms
8 字节 16777216 10.95 ms
16 字节 8388608 8.21 ms
32 字节 4194304 7.24 ms
64 字节 2097152 6.51 ms
128 字节 1048576 5.41 ms
256 字节 524288 3.81 ms

⭐ 看第一行和第五行:元素个数从 3355 万掉到 210 万,少了 16 倍,耗时却只从 19.21 ms 掉到 6.51 ms,只少了不到 3 倍。

在64 字节行、按本例步长访问完整范围的模型下,这两种步长触及的行数基本相同,少取元素不会同比减少行填充。实际耗时还受预取、缓存层级、工作集和循环开销影响,这张曲线不能反过来证明硬件行长。

⚠️ 在该 64 字节模型中,间隔超过一行后才可能整行跳过;表里最后两行的历史耗时下降与这种解释相符,不能单凭耗时归因或测出行长。

⭐ 一句话读法:成本挂在「你碰到了多少条 line」上,不挂在「你用了多少个数」上。

🧩 三、这条 line 从多远的地方来

「搬一条」也不是只有一个价钱 —— 取决于它当时在哪一级。这一层结构可以自己测出来:让指针在一块内存里随机地一跳一跳走下去(随机是关键,否则硬件会提前把下一块取来,测不出真实代价),然后改变这块内存的大小。

// c03_ws.cpp
// g++ -O2 -std=c++17 c03_ws.cpp -o c03_ws
#include <cstdio>
#include <vector>
#include <chrono>
#include <numeric>
#include <random>
#include <algorithm>

using Clock = std::chrono::steady_clock;

int main() {
    std::printf("  数据量      每次跳一步的平均耗时(ns)\n");
    for (size_t kb = 8; kb <= 65536; kb *= 4) {
        size_t n = kb * 1024 / sizeof(int);          // 这么多个 int
        std::vector<int> next(n);
        // 造一条走遍所有格子的随机环:next[i] 是下一个要去的格子
        std::vector<int> perm(n);
        std::iota(perm.begin(), perm.end(), 0);
        std::mt19937 rng(12345);
        std::shuffle(perm.begin(), perm.end(), rng);
        for (size_t i = 0; i + 1 < n; ++i) next[perm[i]] = perm[i + 1];
        next[perm[n - 1]] = perm[0];

        const long long STEPS = 20'000'000;
        int p = 0;
        for (long long i = 0; i < (long long)n; ++i) p = next[p];   // 预热
        auto t = Clock::now();
        for (long long i = 0; i < STEPS; ++i) p = next[p];          // ⭐ 一步都不能提前预测
        double ns = std::chrono::duration<double, std::nano>(Clock::now() - t).count() / STEPS;
        std::printf("  %6zu KB    %8.2f     (p=%d)\n", kb, ns, p);
    }
    return 0;
}

跑两次的实跑结果:

数据总量 随机跳一步(第一次) (第二次)
8 KB 3.00 ns 4.05 ns
32 KB 5.10 ns 5.04 ns
128 KB 15.42 ns 11.76 ns
512 KB 38.53 ns 31.35 ns
2048 KB 150.49 ns 155.03 ns
8192 KB 315.75 ns 303.19 ns
32768 KB 344.19 ns 354.69 ns

⭐ 同一行代码,数据从 8 KB 长到 32 MB,一步的代价涨了大约 100 倍(3 ns → 344 ns)。台阶的位置就是各级缓存装不下的地方。

⚠️ 三条诚实声明: - 这些数字不是纯粹的缓存延迟,里面还含地址翻译等其它开销;它们回答的是「随机跳一步实际要等多久」,不是硬件手册上的延迟指标。 - 绝对值只对这台机器有效,你的一定不同。要看的是形状:平的一段、抬起来的台阶、最后的高原。 - 表里没有任何一个数字来自资料,全部是上面那段代码跑出来的。

📋 由此得到一条很实用的判据:

⭐ 「数据量刚好越过某一级缓存」是性能悬崖最常见的位置。 一个 batch size 从 32 调到 64、一个中间张量从 480 KB 长到 520 KB,代码一个字没改,耗时可能翻几倍。 这也是为什么「调大一点点反而慢了」这种现象经常不是玄学。

⚠️ 上面全是 CPU 这一侧。GPU 那边有自己的一套层次(寄存器 / Shared Memory / L2 / HBM)和自己的比值,AI 基础设施 03 第一节有一张完整的表,本章不重画那张表。

可选深入:读布局实验前,别把 int 和 long 都当成 64 位

sizeof 的结果依赖目标数据模型

把四种类型的下界列清楚。下面按 C++20 起的补码规则说明,并已对照当前公开工作草案;固定版本参考 N4868。N 是包含符号位的整数值表示宽度,实际可以更大;表中的范围是该最小宽度下必须能容纳的范围,不是所有实现的完整范围。

有符号类型最小 N(位)至少包含的范围(两端含)
short int16−215 … 215−1
int16−215 … 215−1
long int32−231 … 231−1
long long int64−263 … 263−1

存储大小还满足 sizeof(short) ≤ sizeof(int) ≤ sizeof(long) ≤ sizeof(long long),相邻类型可以一样大,仍是不同类型。sizeof 的单位是 C++ 字节,sizeof(char)==1;一个字节有 CHAR_BIT 位。sizeof(T)×CHAR_BIT 是对象表示所占位数,可能包括填充位,不能直接等同上表 N。不能从最低位宽反推出跨平台固定的 2/4/8 字节。

前文与下方程序保留 C++17 基线。若讨论 C++17 的最低保证,它还允许其他有符号表示形式,不能把上表额外的最负值通用化:short/int 的共同保底负端为 −32767,long 为 −2147483647,long long 为 −9223372036854775807;各自正端至少是对应正数。具体实现的完整范围可查 numeric_limits 的 lowest()/max(),对象大小则查 sizeof。

在常见 CHAR_BIT=8 的 ABI 中,按 short/int/long/long long/指针的顺序,典型 LP64 是 16/32/64/64/64 位,Windows x64 的典型 LLP64 是 16/32/32/64/64 位。这是常见实现安排;LP64/LLP64 的名称本身不约束所有类型,标准也不要求每个平台选其中一种。这里没有新增平台、GPU、扩展或缓存行测量。

依据:当前公开草案 basic.fundamental、实现限值接口、固定对照 N4868、微软类型范围与前文 Windows 数据模型文档。

标准给整数最小范围与相对大小,不保证 int、long 在所有机器上同宽。常见 LP64 平台是 int 32、long/指针 64 位;64 位 Windows 的 LLP64 则 int/long 32、指针 64 位。size_t 是 sizeof 的无符号结果类型,不是“固定等于 long”;固定宽度 int32_t/uint32_t 等只在实现提供相应精确类型时存在。字节的位数用 CHAR_BIT,不能仅凭 sizeof(char)==1 推出所有平台的字节必为 8 位。

#include <cassert>
#include <climits>
#include <cstddef>
#include <cstdint>
#include <iostream>
#include <limits>
int main() {
    static_assert(sizeof(char)==1);
    static_assert(std::numeric_limits<int>::max()>=32767);
    static_assert(std::numeric_limits<long>::max()>=2147483647L);
    std::size_t count=3;
    std::uint32_t exact=42; // this implementation provides exact 32-bit type
    assert(count==3 && exact==42);
    std::cout << "bits: int=" << sizeof(int)*CHAR_BIT
              << " long=" << sizeof(long)*CHAR_BIT
              << " pointer=" << sizeof(void*)*CHAR_BIT
              << " size_t=" << sizeof(std::size_t)*CHAR_BIT << '\n';
}

这里打印的是当前编译目标的对象表示宽度,不是给别的 ABI 作承诺。结构体 padding、printf 格式和溢出上限仍要按实际类型核对;输出大小不能证明内存访问已对齐到缓存行。依据:C++17 基本类型、Windows LLP64。

🧩 四、结构体为什么会莫名变胖

前面讲的是「怎么访问」。这一节开始讲「怎么摆」,第一件事是:你写的字段顺序,直接决定这个结构体占多少字节。

原因是对齐:硬件要求一个 8 字节的数必须放在 8 的倍数地址上,编译器只好在字段之间插空洞来满足它。

// c03_pad.cpp
// g++ -O2 -std=c++17 c03_pad.cpp -o c03_pad
#include <cstdio>
#include <cstdint>
#include <cstddef>

struct Bad  { char  flag; double value; char  tag; int32_t id; };   // 随手写的顺序
struct Good { double value; int32_t id; char  flag; char  tag; };   // 从大到小排

int main() {
    std::printf("字段本身加起来: 1 + 8 + 1 + 4 = %d 字节\n\n",
                (int)(sizeof(char) + sizeof(double) + sizeof(char) + sizeof(int32_t)));

    std::printf("Bad  实际占 %zu 字节  (对齐要求 %zu)\n", sizeof(Bad),  alignof(Bad));
    std::printf("  flag  在偏移 %zu\n", offsetof(Bad, flag));
    std::printf("  value 在偏移 %zu   <- 前面被塞了 7 字节空洞\n", offsetof(Bad, value));
    std::printf("  tag   在偏移 %zu\n", offsetof(Bad, tag));
    std::printf("  id    在偏移 %zu   <- 又塞了 3 字节\n\n", offsetof(Bad, id));

    std::printf("Good 实际占 %zu 字节  (对齐要求 %zu)\n", sizeof(Good), alignof(Good));
    std::printf("  value 在偏移 %zu\n", offsetof(Good, value));
    std::printf("  id    在偏移 %zu\n", offsetof(Good, id));
    std::printf("  flag  在偏移 %zu\n", offsetof(Good, flag));
    std::printf("  tag   在偏移 %zu\n\n", offsetof(Good, tag));

    std::printf("⭐ 同样四个字段,只换了声明顺序: %zu -> %zu 字节,省了 %.0f%%\n",
                sizeof(Bad), sizeof(Good),
                100.0 * (sizeof(Bad) - sizeof(Good)) / sizeof(Bad));
    std::printf("   一条 64 字节的 cache line 能装几个: Bad %zu 个 / Good %zu 个\n",
                64 / sizeof(Bad), 64 / sizeof(Good));
    return 0;
}

实跑输出:

算一算

字段本身加起来: 1 + 8 + 1 + 4 = 14 字节

Bad 实际占 24 字节 (对齐要求 8)

flag 在偏移 0

value 在偏移 8 <- 前面被塞了 7 字节空洞

tag 在偏移 16

id 在偏移 20 <- 又塞了 3 字节

Good 实际占 16 字节 (对齐要求 8)

value 在偏移 0

id 在偏移 8

flag 在偏移 12

tag 在偏移 13

⭐ 同样四个字段,只换了声明顺序: 24 -> 16 字节,省了 33%

一条 64 字节的 cache line 能装几个: Bad 2 个 / Good 4 个

⭐ 字段加起来只有 14 字节,Bad 却占 24 字节 —— 有 10 字节是空洞。 换个顺序变成 16 字节,一行逻辑都没改,省了 33%。

先读准最后一行的 2 / 4:它是 64 / sizeof 的整数除法,表示从一条 64 字节行的起点起,能完整容纳几个这样的对象。不能把紧凑数组想成每行只摆 2 个 Bad、再空着 16 字节。C++ 数组元素连续排列,元素大小已包含 ABI 所需 padding;沿用上例 Bad=24、Good=16 的 ABI,第三个 Bad 位于相对字节地址 [48,72),会跨过 64 字节边界,下一行继续放它的剩余部分。

只算地址跨度:明确假设两种数组起点都按 64 B 行边界对齐,N=1024。Bad 的 24N=24576 B 跨度覆盖 384 个不同 line ID;Good 的 16N=16384 B 覆盖 256 个,比值为 384/256=1.5,不是两倍。这里统计完整数组字节区间覆盖的行,未模拟某段程序具体读取哪些字段。

起始偏移和有限 N 会改变边缘计数;上述大小与约 33% 空间节省沿用原 ABI 示例,不是跨平台 sizeof 保证。不同 line ID 数不等于实测缓存缺失、行填充或 DRAM 事务数,更不能推出 1.5 倍速度。实际还取决于访问字段、缓存驻留、预取与执行开销。依据:C++17 数组连续排列、sizeof 与数组总大小;本轮只核对有限地址模型,没有新增编译或硬件测量。

📋 两条能直接用的规矩:

规矩 说明
⭐ 字段按大小从大到小声明 最省事的做法,多数情况下自动最优
⚠️ 别自作聪明加 #pragma pack 它能去掉空洞,但会让某些字段落在没对齐的地址上 —— 在有些平台上性能更差甚至直接出错

⭐ 读源码时的用处:看到一个结构体的字段顺序「奇怪地按大小排列」,或者中间插着 char _pad[N] 这种看似没用的成员,那不是风格问题,是有人在控制布局。


🧩 五、AoS 还是 SoA:同一批数据的两种摆法

现在把「怎么摆」放大到一整个数组。假设有 800 万个粒子,每个粒子有 8 个属性。有两种摆法:

摆法 长什么样 内存里的顺序
AoS(结构体数组) 一个数组,每个元素是一个完整的粒子 x y z vx vy vz m q x y z vx vy vz m q …
SoA(数组的结构) 8 个数组,每个数组装一个属性 x x x x … 然后 y y y y … 然后 …

⭐ 如果你的循环只用其中一个属性,这两种摆法的差别是巨大的。

// c03_aos.cpp
// g++ -O2 -std=c++17 c03_aos.cpp -o c03_aos
#include <cstdio>
#include <vector>
#include <chrono>

using Clock = std::chrono::steady_clock;
static double ms_since(Clock::time_point t) {
    return std::chrono::duration<double, std::milli>(Clock::now() - t).count();
}

struct Particle {                 // 一个粒子的全部属性摆在一起
    float x, y, z;
    float vx, vy, vz;
    float mass, charge;
};                                // 8 个 float = 32 字节

int main() {
    const size_t N = 8'000'000;
    const int    REP = 5;

    // ① AoS:一个装着「结构体」的数组
    std::vector<Particle> aos(N);
    for (size_t i = 0; i < N; ++i) { aos[i].x = 1.0f; aos[i].mass = 2.0f; }

    // ② SoA:每个属性一个自己的数组
    std::vector<float> sx(N, 1.0f), sy(N), sz(N),
                       svx(N), svy(N), svz(N),
                       smass(N, 2.0f), scharge(N);

    double best_aos = 1e18, best_soa = 1e18;
    float r1 = 0, r2 = 0;

    for (int r = 0; r < REP; ++r) {                 // 只用 x 这一个字段
        auto t = Clock::now();
        float s = 0;
        for (size_t i = 0; i < N; ++i) s += aos[i].x;
        double ms = ms_since(t);
        if (ms < best_aos) { best_aos = ms; r1 = s; }
    }
    for (int r = 0; r < REP; ++r) {
        auto t = Clock::now();
        float s = 0;
        for (size_t i = 0; i < N; ++i) s += sx[i];
        double ms = ms_since(t);
        if (ms < best_soa) { best_soa = ms; r2 = s; }
    }

    std::printf("sizeof(Particle) = %zu 字节,%zu 个粒子共 %.0f MB\n",
                sizeof(Particle), N, (double)N * sizeof(Particle) / 1048576.0);
    std::printf("只求和 x 这一个字段(%zu MB 的有效数据):\n",
                (size_t)(N * sizeof(float) / 1048576));
    std::printf("  ① AoS  结构体数组: %8.2f ms   (和 %.0f)\n", best_aos, r1);
    std::printf("  ② SoA  数组的结构: %8.2f ms   (和 %.0f)\n", best_soa, r2);
    std::printf("  AoS / SoA        : %8.2f 倍\n", best_aos / best_soa);
    std::printf("⭐ AoS 每搬一条 64 字节的 cache line,只用得上其中 %zu 字节\n",
                64 / sizeof(Particle) * sizeof(float));
    return 0;
}

跑三次的实跑结果:

次 ① AoS ② SoA AoS / SoA
1 14.27 ms 6.03 ms 2.37 倍
2 15.92 ms 6.53 ms 2.44 倍
3 13.29 ms 6.36 ms 2.09 倍

⭐ sizeof(Particle) = 32 字节,一条 line 装 2 个粒子,而你只要 x —— 每搬 64 字节只用得上 8 字节,87.5% 的带宽是白花的。SoA 那边则是搬来的 64 字节里 16 个 float 全都要用。

📋 该选哪个:

你的循环 选
一次只碰一两个属性,但要碰所有元素(大部分数值计算) ⭐ SoA
一次要碰某个元素的全部属性(比如「找到这个粒子,把它整个打印出来」) AoS
两种都有 按最热的那个循环选,或者拆成两份

⭐ 这解释了一件你天天在用的事:为什么框架里的一批数据是「一个 x 张量 + 一个 y 张量」,而不是「一个装着样本对象的列表」。那就是 SoA。 深度学习的每个算子都是「对所有元素做同一件事」,正好落在 SoA 那一行。

⚠️ GPU 上这件事的名字不一样但道理一样:AI 基础设施 02 讲的「非合并访存」说的是「warp 里 32 个线程访问连续地址就合并成 1 次内存事务,否则可能变成 32 次、有效带宽掉到 1/32」—— ⭐ 那一章讲的是后果和怎么避开,这一章讲的是为什么内存非得按固定大小的块搬。 两边是同一个机制在两种硬件上的样子。

🧩 六、💀 false sharing:两个变量互不相干,却互相拖累

这一节兑现 02 章第六节留下的那句话 —— 那里说 shared_ptr 的引用计数是原子操作、「多线程下会真的争抢缓存行」。代价有多大,现在量出来。

⚠️ 前提:cache line 是缓存的最小单位,也是多核之间保持一致的最小单位。一个核改了某条 line 里的任何一个字节,其它核手上那条 line 的副本就整条作废。

于是就有了这个荒谬的场景:四个线程各改各的变量,谁也不碰别人的,但因为这四个变量挤在同一条 line 里,它们互相把对方的缓存打掉。

// c03_false.cpp
// g++ -O2 -std=c++17 -pthread c03_false.cpp -o c03_false
#include <cstdio>
#include <thread>
#include <vector>
#include <chrono>
#include <atomic>

using Clock = std::chrono::steady_clock;
static double ms_since(Clock::time_point t) {
    return std::chrono::duration<double, std::milli>(Clock::now() - t).count();
}

struct Packed  { std::atomic<long long> v; };              // 4 个挤在一起
struct Spread  { std::atomic<long long> v; char pad[56]; };// ⭐ 历史64字节间距模型;不是硬件行长探测或普适对齐保证

template <class Slot>
double run(int nthreads, long long iters) {
    std::vector<Slot> slots(nthreads);
    for (auto& s : slots) s.v.store(0, std::memory_order_relaxed);
    std::vector<std::thread> ts;
    auto t = Clock::now();
    for (int k = 0; k < nthreads; ++k)
        ts.emplace_back([&slots, k, iters] {
            for (long long i = 0; i < iters; ++i)
                slots[k].v.fetch_add(1, std::memory_order_relaxed);
        });
    for (auto& th : ts) th.join();
    return ms_since(t);
}

int main() {
    const int  T = 4;
    const long long ITER = 20'000'000;
    std::printf("硬件线程数: %u\n", std::thread::hardware_concurrency());
    std::printf("sizeof(Packed)=%zu  sizeof(Spread)=%zu\n\n",
                sizeof(Packed), sizeof(Spread));
    std::printf("%d 个线程,各自给【自己的】计数器加 %lld 次(互不相干的变量)\n", T, ITER);

    for (int r = 0; r < 3; ++r) {
        double a = run<Packed>(T, ITER);
        double b = run<Spread>(T, ITER);
        std::printf("  第%d次:  挤在一起 %8.2f ms   隔开 %8.2f ms   慢 %.2f 倍\n",
                    r + 1, a, b, a / b);
    }
    return 0;
}

实跑输出:

硬件线程数: 8

sizeof(Packed)=8 sizeof(Spread)=64

4 个线程,各自给【自己的】计数器加 20000000 次(互不相干的变量)

同样工作量,比较两种内存布局
实测轮次挤在一起隔开相对耗时
第1次1577.45 ms211.50 ms7.46 倍
第2次1824.92 ms175.98 ms10.37 倍
第3次1176.16 ms201.48 ms5.84 倍

💀💀 5.84 到 10.37 倍,而这四个线程之间没有任何逻辑上的共享。 这里改变的是 char pad[56] 带来的布局;历史输出记录 sizeof(Spread)=64,但没有给出每个对象的行对齐测量。64 字节间距不是跨平台隔离保证,复用时应核对类型大小、对齐与实际缓存一致性粒度;标准库建议值可用于布局设计,不能当作测量结论。

⭐ 为什么它特别难查:

表现
代码看起来 完全正确,四个线程各写各的,没有锁、没有竞态、结果也对
加线程之后 ⚠️ 越加越慢,看起来像「这活并行不起来」
用一般的方法查 查不到 —— 没有锁竞争、没有系统调用、CPU 占用还很高
改法 按目标平台核对对齐与足够的隔离间距,或者干脆各自在局部变量里累加,最后合并一次

⚠️ 回到 02 章那句话:shared_ptr 每次拷贝和析构都要原子地改一次引用计数。如果多个线程频繁拷贝同一个 shared_ptr,它们改的就是同一条 line 上的同一个计数器 —— 这已经不只是 false sharing,是真的在抢同一个数。⭐ 这就是「默认用 unique_ptr,说不清谁最后走才用 shared_ptr」那条建议在性能上的理由。


可选深入:计数器实验的线程何时结束,借用活到哪一步?

先保证收尾,再比较布局

原实验把所有 worker join 完才离开局部计数器的作用域。join 等待关联线程完成,成功后不再 joinable;线程函数已返回但尚未 join/detach,thread 对象仍可能 joinable。析构一个 joinable 的 std::thread 会调用 terminate。异常路径也要收尾,不能靠正常路径末尾的一次 join 兜所有失败。

#include <cassert>
#include <atomic>
#include <thread>
int main() {
    std::atomic<int> count{0};
    std::thread first([&] { for(int i=0;i<500;++i) ++count; });
    try {
        std::thread second([&] { for(int i=0;i<500;++i) ++count; });
        second.join();
    } catch (...) { // if second cannot be created, still join first
        if(first.joinable()) first.join();
        throw;
    }
    assert(first.joinable());
    first.join();
    assert(!first.joinable() && count.load()==1000);
}

这个小例特意在第二个线程创建失败时 join 第一个;它不是完整线程组封装。detach 只解除句柄关联,不等待工作结束、不延长 lambda 捕获引用的寿命;把原实验改成 detach 然后返回,会让 worker 可能访问已销毁的局部数据,禁止这样复现。线程函数中未捕获异常也会 terminate,不能假定由启动者的 catch 自动接住。

独立计数器 ++ 可以选 atomic,让每次读改写成为原子操作;atomic 不保证无锁,也不会把多个字段的业务不变量合成一个事务。比如“余额减少与转出记录增加”需要一个整体临界区,不能用两个互不相关的 atomic 就声称一致。下面只补这些 worker 的接口、状态与收尾读法,不实现完整并发库。

把上面的“余额+转出记录”封装成类,边界也必须一起封装;const 方法不会自动线程安全。一个最小接口契约可以这样读,锁管理沿用 02 章,不另写一份 guard 实验:

余额与记录的接口草图(伪代码,非可编译 C++ 程序)

Ledger:
  私有:mutable mutex m、balance、records
  apply(amount):持 m 检查并一起更新余额/记录;失败也须保持不变量
  snapshot() const:持同一 m 复制状态,返回快照

不导出可变内部引用,所有相关读写都遵守同一锁协议;否则封装就漏了。单个方法安全不等于调用者连续调用多个方法成为原子事务,对象销毁前也必须已无并发访问;草图只提出接口与失败路径约束,不是一份已经验证的类实现。

若要每线程一份计数,可读函数体内的块作用域声明 thread_local unsigned count = 0;:同一声明在各线程对应独立实体。这个块作用域例若需要动态初始化,在该线程首次经过声明时初始化,已构造对象在线程退出时销毁;池中它随 worker 生存,不会每个任务自动重置。thread_local 指针所指对象仍可能共享,TLS 也不是跨线程发布协议;不由此承诺无开销或固定实现偏移。

原实验的 relaxed 还需要一句读法:它只让该 atomic 的访问保持原子性,不用它发布其他普通数据。本章固定 C++17,六种内存序按用途区分:

例如先写普通数据,再向 flag 作 release store;另一线程的 acquire load 读到该 store(或其释放序列)写入的值,才建立这里所说的发布/获取关系,不能只凭时间先后断言。load 不能用 release/acq_rel,store 不能用 consume/acquire/acq_rel;更复杂的 RMW、失败序与生命周期另有约束,不靠一次运行证明正确。依据:C++17 内存序与atomic 操作。

若要复用 worker 而不是每次新建,线程池的大体流程是:任务队列由 mutex/CV 保护;worker 等“有任务或停止”,锁内取任务,解锁后执行,在线程入口处理任务失败,不让异常逃出。关闭时先拒收新任务,再明确选择排空待办或取消尚未开始的任务,通知等待者,最后不持队列锁地 join;否则 join 可能挡住需要该锁的 worker。队列容量是需选择的约束,不能承诺取消任意正在运行的任务;所有者及被捕获对象须活到 worker 终止。02 章的谓词等待可复用,这里不交付通用池或吞吐结论。

C++20 可选对照:协作停止不是强杀

下面是独立 C++20 例,不可放进原 C++17 编译命令。jthread 在可 join 的析构路径请求停止并 join;stop_token 要由工作代码主动检查,阻塞或忽略请求的 worker 仍可能让析构等待。它也不自动修复捕获对象的寿命顺序。

#include <cassert>
#include <atomic>
#include <thread>
#include <stop_token>
int main() { // C++20 only
    std::atomic<bool> observed{false};
    {
        std::jthread worker([&](std::stop_token token) {
            while(!token.stop_requested()) std::this_thread::yield();
            observed=true;
        });
        assert(worker.request_stop()); // request; worker must cooperate
    } // joinable destructor requests stop and joins
    assert(observed.load()); // observed outlives worker
}

依据:C++17 thread 析构、C++20 后续草案 N4868 的 jthread。本轮只跑这些短标准库例,没有重跑原页的硬件计时,更没有硬件行长测量。

🧩 七、Python 侧也逃不掉

前面全是 C++。但这件事不是 C++ 的特性,是硬件的特性 —— 用纯 Python 也能把它跑出来。

01 章第二节说过「那 1000 个对象散落在堆的各处,遍历它们等于 1000 次指针跳转」,当时留了一句「这一条会在 03 章变成一个更大的数字」。就是下面这个:

# c03_pyscatter.py
import random, time, array

N = 2_000_000

# ① 一次性造出来的对象,地址大体是挨着的
objs = [float(i) for i in range(N)]
gaps = [abs(id(objs[i + 1]) - id(objs[i])) for i in range(1000)]
print("① 顺序造出来的 float 对象,相邻两个的地址差(前 1000 个的中位数):",
      sorted(gaps)[len(gaps) // 2], "字节")

# ② 把列表打乱:对象本身没动,但「访问顺序」和「内存顺序」错开了
shuffled = objs[:]
random.seed(0)
random.shuffle(shuffled)
gaps2 = [abs(id(shuffled[i + 1]) - id(shuffled[i])) for i in range(1000)]
print("② 打乱之后,相邻两个的地址差(中位数):",
      sorted(gaps2)[len(gaps2) // 2], "字节")

def timed(f, rep=5):
    best = 1e18
    for _ in range(rep):
        t = time.perf_counter()
        r = f()
        best = min(best, (time.perf_counter() - t) * 1000)
    return best, r

t1, s1 = timed(lambda: sum(objs))
t2, s2 = timed(lambda: sum(shuffled))
arr = array.array('d', objs)
t3, s3 = timed(lambda: sum(arr))

print(f"③ 顺序列表求和  : {t1:8.1f} ms")
print(f"   打乱列表求和  : {t2:8.1f} ms   (慢 {t2/t1:.2f} 倍)")
print(f"   array('d') 求和: {t3:8.1f} ms   (对顺序列表 {t1/t3:.2f} 倍)")
print("   三个和一样吗:", s1 == s2 == s3)

实跑输出(CPython 3.13.14,跑两次):

操作步骤

  1. 顺序造出来的 float 对象,相邻两个的地址差(前 1000 个的中位数): 32 字节
  2. 打乱之后,相邻两个的地址差(中位数): 20633632 字节
  3. 顺序列表求和 : 15.0 ms
  4. 打乱列表求和 : 41.5 ms (慢 2.77 倍)
  5. array('d') 求和: 11.7 ms (对顺序列表 1.29 倍)
  6. 三个和一样吗: True

第二次跑的打乱地址差是 29225504 字节,倍数 2.85。

⭐ 注意 shuffled 和 objs 装的是【同一批对象】 —— 同样 200 万个 float,同样的和(True),一个字节的数据都没多也没少。唯一变的是访问它们的顺序,慢了 2.77 / 2.85 倍。

⚠️ 而地址差那两行是证据:顺序造出来的对象相邻地址差 32 字节(挨着),打乱之后中位数是 2000 万字节 级别 —— 每一步都跳到一条全新的 line 上。

📋 顺手能用的三条:

现象 解释
⭐ 同一批数据,打乱顺序访问就是慢 和语言无关,第二节那条判据在起作用
array('d') 比顺序列表还快一点(1.21–1.29 倍) 它是一块连续的裸内存,不是 200 万个对象加 200 万个指针
⚠️ 但 array 的优势在这里没有第一节那么夸张 因为 sum() 每取一个还要造一个 Python float 对象,那笔开销盖过了布局的差别 —— ⭐ 瓶颈换了地方,布局的收益就被摊薄了

⚠️ 反过来说,在纯 Python 里追求 cache 友好基本不划算 —— 解释器开销(01 章那三笔)通常比布局的差别大得多。这一节的意义是让你认得这个现象,真要吃到这份收益,得让数据以连续裸内存的形式交给下面那一层。

🔗 这一章连到哪里

相关的地方 为什么
《NumPy 与向量化思维》04 「一个数组对象怎么描述自己的排布」「切片是视图还是拷贝」全在那边。⭐ 本章只讲硬件层:用 64 字节行模型解释局部性
01 章 那一章第二节说「1000 个对象散落在堆的各处,这一条会在 03 章变成一个更大的数字」—— 第七节的 2.77 / 2.85 倍就是它
02 章 那一章第六节说 shared_ptr 的原子计数「多线程下会真的争抢缓存行」—— 第六节把这句话量成了 5.84–10.37 倍
AI 基础设施 02 它讲「非合并访存」:warp 里 32 个线程访问连续地址合并成 1 次事务,否则有效带宽掉到 1/32。⭐ 那是后果和避法,本章是它背后的机制;warp / SM / GPU 侧的一切归它讲
AI 基础设施 03 它第一节有 GPU 侧完整的内存层次表(寄存器 / Shared Memory / L2 / HBM 及其带宽),⭐ 本章不重画那张表,只测了 CPU 这一侧
AI 基础设施 07 「少搬一次内存」正是算子融合的全部动机 —— 本章解释了为什么搬内存这么贵,那一章算能省多少
04 章 结构体的布局(第四节)不只是性能问题:两边对同一个结构体的布局理解不一致,程序会直接读错数据 —— 那是下一章的正题

✅ 检查点

  1. 4096×4096 的 double 矩阵,按行走和按列走实跑各多少毫秒?慢了几倍?两种走法有什么不同、有什么完全相同?
  2. 打印出的 hardware_destructive_interference_size 是什么?能否据此称“本机 cache line 实测 64 字节”?
  3. 固定摸完 128 MB,间隔从 4 字节改成 64 字节:取的元素少了几倍?耗时少了几倍?为什么不成比例?
  4. 那条「成本挂在什么上」的判据怎么说?
  5. 随机跳一步的耗时,从 8 KB 涨到 32 MB 大约变了多少倍?为什么正文强调「要看形状不看绝对值」,还说了哪一条诚实声明?
  6. Bad 和 Good 两个结构体在原 ABI 示例中各占多少字节、字段合计多少?历史 64/sizeof 的 2 / 4 表示什么?若 1024 个元素的数组起点都按 64 B 对齐,各自完整字节跨度覆盖多少个不同 line ID,能否据此推出搬运次数或速度?
  7. 字段该怎么声明?为什么不推荐用 #pragma pack 去掉空洞?
  8. AoS 和 SoA 分别是什么摆法?只求和 x 一个字段时实跑差几倍?sizeof(Particle) 是多少,一条 line 里有多少字节是白搬的?
  9. 为什么框架里是「一个 x 张量 + 一个 y 张量」而不是「一个样本对象列表」?
  10. false sharing 是什么?实跑慢了几倍?改法是什么?为什么它特别难查?
  11. 纯 Python 那个实验里,objs 和 shuffled 有什么不同、有什么相同?慢了几倍?地址差分别是多少?
  12. 为什么正文说「在纯 Python 里追求 cache 友好基本不划算」?
👀 答案
  1. 按行 13.64 / 13.61 / 13.60 ms,按列 222.46 / 223.18 / 240.33 ms,慢 16.31 / 16.40 / 17.67 倍。不同的只有访问内存的顺序;相同的是数据(同一个 128 MB 矩阵)、运算(1677 万次浮点加)、结果(两个和都是 16777216),连指令都几乎一样。
  2. 历史打印值为 64 字节;它是标准库实现定义的 constexpr 建议间距,不是运行时硬件探测值。不能由此证明本机 cache line 长度;正文的 64 字节计算是教学假设。
  3. 元素从 33554432 个降到 2097152 个,少了 16 倍;耗时从 19.21 ms 降到 6.51 ms,只少了不到 3 倍。在本例的 64 字节行模型中,两种步长触及的行数基本相同;实际耗时还受预取、缓存层级和循环开销影响,不能据此反推行长。
  4. 成本挂在「你碰到了多少条 cache line」上,不挂在「你用了多少个数」上。
  5. 从 3.00 ns(8 KB)涨到 344.19 ns(32 MB),大约 100 倍。三条诚实声明:① 这些数不是纯粹的缓存延迟,含地址翻译等其它开销;② 绝对值只对这台机器有效,要看的是形状(平的一段、台阶、高原);③ 表里没有任何一个数字来自资料,全部实跑。
  6. 原 ABI 示例中,字段合计 14 字节;Bad 为 24 字节(有 10 字节空洞),Good 为 16 字节,省约 33%。历史 2 / 4 是单行从边界起能完整容纳的对象数,不代表紧凑数组每行尾部都空置;第三个 24 字节对象可跨行。按两数组起点均 64 B 对齐、N=1024 的完整字节跨度模型,分别覆盖 384 / 256 个不同 line ID,比值 1.5;改变偏移或有限 N 有边缘差异。这不是实测 miss、DRAM 事务或吞吐,不能推出两倍搬运,也不保证 1.5 倍加速。
  7. 按大小从大到小声明。不推荐 #pragma pack:它能去掉空洞,但会让某些字段落在没对齐的地址上,在有些平台上性能更差甚至直接出错。
  8. AoS = 结构体数组(一个粒子的属性挨在一起);SoA = 数组的结构(每个属性一个数组)。只求和 x 时实跑 2.37 / 2.44 / 2.09 倍。sizeof(Particle) = 32 字节,一条 line 装 2 个粒子而只用得上 2 个 float = 8 字节,87.5% 白搬。
  9. 因为那就是 SoA。深度学习的每个算子都是「对所有元素做同一件事」,一次只碰一两个属性但要碰所有元素 —— 正好落在该选 SoA 的那一行。
  10. 多个线程各改各自的变量,但这些变量挤在同一条 cache line 里;一个核改了 line 里任何一个字节,其它核的整条副本作废。实跑 5.84–10.37 倍(挤在一起 1176–1825 ms,隔开 176–212 ms)。改法:核对目标平台对齐与隔离间距(历史 pad[56] 仅是本例布局),或各自在局部变量里累加最后合并一次。难查是因为:代码完全正确、没有锁竞争和系统调用、CPU 占用还很高,症状只是「加线程越加越慢」。
  11. 装的是同一批对象,同样 200 万个 float,和相同(True),数据一个字节没变;只有访问顺序不同。慢 2.77 / 2.85 倍。地址差:顺序的中位数 32 字节,打乱后 20633632 / 29225504 字节。
  12. 因为解释器开销通常比布局的差别大得多(01 章那三笔)。实验里 array('d') 只比顺序列表快 1.21–1.29 倍,就是因为 sum() 每取一个还要造一个 Python float 对象,那笔开销盖过了布局差别 —— 瓶颈换了地方,布局的收益就被摊薄了。

本节回顾

⚡ 走神救援

🏁 全章一句话:CPU 不按元素取数,按固定大小的一整块取——本章按 64 字节行作教学推导,⭐ 标准库打印的是实现建议间距,不能当作硬件实测行长。引子是同一个矩阵按行走和按列走:同样的数据量、同样的加法次数、同样的结果,只有访问顺序不同,慢了十几倍。

📏 ⭐⭐ 判据:成本挂在「碰到了多少条 line」上,不挂在「用了多少个数」上。 证据是固定摸完同样大的内存、只改间隔——取的数少了十几倍,耗时只少不到三倍,在 64 字节行模型下可用触及行数相近来解释,但曲线不能证明硬件行长。

⭐ 搬一条的价钱取决于它在哪一级,最近和最远差约两个数量级。由此得到 ⭐ 「数据量刚好越过某一级缓存」是性能悬崖最常见的位置——「调大一点点反而慢了」经常不是玄学。 ⚠️ 这些数绝对值只对本机有效,而且没有一个来自资料。

📦 怎么摆同样要紧:对齐会插空洞,只把字段从大到小重排就能省掉三分之一——历史 2 / 4 是单行完整件数的取整视图;紧凑数组允许对象跨行,不能由此推出两倍搬运。按上述 64 B 对齐、1024 元素的完整地址跨度模型,不同行数为 384 / 256,比值 1.5,也不是性能保证。⚠️ 别用 #pragma pack 硬去空洞。放大到数组就是 AoS 与 SoA 之别,⭐ 框架里「一个 x 张量加一个 y 张量」就是 SoA。

💀 false sharing 兑现了上一章的欠账:几个线程各加各自的计数器、毫无逻辑共享,只因挤在同一条 line 里就慢了将近一个数量级。⭐ 难查是因为代码完全正确、没有锁竞争、CPU 占用还高——症状只是「加线程越加越慢」。

🐍 Python 也逃不掉:同一批对象只打乱访问顺序就慢了两倍多。⚠️ 但换成紧凑数组只快了两成——每取一个还要造一个对象,瓶颈换了地方,布局收益就被摊薄。⭐ 所以纯 Python 里追求 cache 友好基本不划算。

下一节 👉 04-ABI与二进制兼容.md

打卡记录保存在你的浏览器里,首页能看到总进度