缓存、栈、堆与性能剖析

你在一家国内头部私募 quant 桌上,周末把一段单线程的沪深300成分股信号聚合器用 C++17 重写。重写"显然更快"——更少的分配、更紧的循环、通篇现代 C++17。周一集成测试都过,墙钟时间却慢了百分之四十。PM 问你为什么。你盯着 diff 看不出名堂,因为你写代码时感到的"更快",住在 C++ 标准之下的一层里:住在缓存层级里、住在一次栈指针挪动与一次 ptmalloc2 上的 arena 分配之间的差异里、住在你那个内循环交给硬件预取器的访存模式里。本课存在的理由,就是 3.4.2 把你留在了熟练写现代 C++17——std::unique_ptr、移动语义、std::optional、std::string_view——却答不出 PM 那个问题的位置。本课结束时你能答了。你脑子里会装上 L1d / L2 / L3 / DRAM 的延迟表;你能在十纳秒以内说出一次 new 在 glibc 默认分配器上的代价;并且你会在同一个二进制上用 perf stat、perf record、cachegrind、Google Benchmark 复现那个经典的行优先 vs 列优先矩阵求和减速。

把内存层级背成一组数字

国内 quant 桌(幻方 / 鸣熙 / 九坤 / 明汯 / 灵均)部署的硬件,典型是 Intel Xeon Gold 6342 / 6354(Ice Lake-SP)或更早一代 Xeon Gold 6248R,操作系统多为 Rocky Linux 9 或 Ubuntu 22.04 LTS。在这类 x86_64 上,你需要按延迟而不是按架构记住六层存储。CPU ​寄存器​​(register)是当前指令的工作集,访问大约 0.3 纳秒。​​L1 数据缓存​​(L1d)每核 32 KiB、64 字节一根缓存行(cache line)、约 1 纳秒。​​L2 缓存​ 每核 256 KiB 到 1 MiB、约 4 纳秒。​​L3 缓存​​(亦称 LLC, last-level cache)是 socket 上所有核共享的几十 MiB,约 15 纳秒。​​DRAM​ 是几 GiB 容量、随机访问约 100 纳秒——顺序访问下硬件预取器(hardware prefetcher)会把大部分延迟隐藏掉。再往下,持久化存储——NVMe 约 10 微秒、网络往返 100 微秒起——又远比 DRAM 慢四个数量级。

值得背的四个数字是 ​1 / 4 / 15 / 100 ns​​,对应 L1d / L2 / L3 / DRAM。每往下一层大约慢 3 到 7 倍,压成一句口号驱动本模块剩下的内容:​​让热工作集装进你能装进的最高那一层缓存​​。一个对 10 MiB 数组的循环踩 L3;一个对 1 GiB 数组的循环大部分访问落在 DRAM;一个 100 KiB 的内循环只要周围代码安静就能留在 L2,小心点能留在 L1。DRAM 比 L1d 慢大约一百倍——所以优化这件事不是"少跑几条指令",而是"把缓存焐热"。

整个画面下面那块承重的概念,是​​缓存行​​(cache line)。CPU 从来不会从 DRAM 取单个字节,它一次取 64 字节的一根缓存行。两个结果由此而来。第一,顺序访问便宜:读 arr[0] 付一次 DRAM 取数的钱,然后 arr[1] 到 arr[7](如果是 double)从缓存里免费拿——一根 64 字节的行装得下八个 double。第二,硬件预取器会识别顺序步长(sequential access),提前把后面几根行预取进来,在流式负载上把 DRAM 延迟基本藏住。随机访问(random access)同时打掉这两件事:每一次取数都是一根新缓存行,预取器也没法预测你下一步往哪跳。这正是下面工作例子里同样的字节量,列优先(column-major)会输给行优先(row-major)一个数量级的全部原因。

栈与堆,从布局层面看

new 和 delete 你在 3.4.1 第 3 课见过,std::unique_ptr 你在 3.4.2 第 1 课见过。你还没见的是它们的代价。​​调用栈​​(call stack)是一段连续内存——1 到 8 MiB,由 ulimit -s 决定,Linux 默认 8 MiB——一次函数调用在进入时用一条 sub rsp, N 指令挪动栈指针(stack pointer)rsp,在退出时用 add rsp, N 还回去。栈分配因此一周期完成、并且本质上是绑作用域的:函数返回时存储就消失。​​堆​​(heap)是进程地址空间剩下的部分,由 malloc / free 管理,C++ 的 new / delete 默认在底下调它们。在 glibc Linux 上,malloc 由 ptmalloc2 实现——每线程 arena、按大小分箱的 free-list——非竞争快路径每次 malloc 或 new 大约 20 到 30 纳秒。最坏情况则包含线程间锁竞争、碎片、为扩堆而发的系统调用(brk / mmap),以及把新分配页落实回物理页带来的 page fault——这些都不在那个快路径数字里。

对短生命期的小对象,规则是​​默认放栈;只在有生命期或大小理由时才伸手去堆​​。这条规则印证了 3.4.1 第 4 课的建议:优先写 Buffer b(10000);(Buffer 对象在栈上、内部 data_ 成员指向一段堆上的 10000 个 double),而不是 Buffer* b = new Buffer(10000);(Buffer 对象本身就在堆上,每次成员访问都多走一次指针间接、可能在缓存里 miss)。前者付一次栈挪动给 Buffer、加一次 malloc 给数据。后者付两次 malloc,并且每次访问都多一次间接。

关于 ​TLB​​(translation lookaside buffer)一段话:CPU 缓存少量虚拟地址到物理地址的翻译——视处理器而定大约 64 到 1024 条。在多个 4 KiB 页之间随机追指针——比如遍历一张散落在 4 GiB arena 上的哈希表——即便数据还在缓存里,也可能在 TLB 里 miss,每次页表行走(page-table walk)大约一百周期。解法是​​大页​​(huge pages,2 MiB 而非 4 KiB),把所需 TLB 条目数压到原来的 1/512。这是 3.4.5 部署层负责的开关,这里点名让你认识这个词,不动手配置。

Linux quant 开发者每天会碰的剖析工具链

第一个伸手去拿的工具是 perf stat。规范调用把二进制锁在单核上以保证测量可重复,并要那五个解释百分之九十单线程性能问题的计数器:

taskset -c 2 perf stat -e cycles,instructions,cache-references,cache-misses,branch-misses ./matrix_bench --benchmark_filter=BM_RowMajor

taskset -c 2 perf stat -e cycles,instructions,cache-references,cache-misses,branch-misses ./matrix_bench --benchmark_filter=BM_ColMajor

它给你一页摘要:总周期、总指令、​​每周期指令数​​(IPC, instructions per cycle = instructions / cycles)、缓存引用与缓存未命中(cache miss)的计数(LLC 未命中率 = cache-misses / cache-references),以及分支预测失败计数。一段健康的计算密集型 C++ 程序在现代 x86 上跑出 IPC 大约 2 到 4;低于 1 意味着 CPU 因为缓存未命中或分支预测失败在原地等。缓存未命中率超过几个百分点,意味着工作集没装进缓存。

第二个工具是 perf record。它以 999 Hz 采样程序计数器,产出一份你用 perf report 交互式读的剖析;或者把它管道到 Brendan Gregg 的 flamegraph 脚本里得到那张经典的横向条形​​火焰图​​(flame graph):

taskset -c 2 perf record -F 999 --call-graph=dwarf -- ./matrix_bench --benchmark_filter=BM_ColMajor
perf report

# or as a flame graph SVG via Brendan Gregg's scripts:
perf script | stackcollapse-perf.pl | flamegraph.pl > flame.svg

火焰图里每个矩形的宽度正比于它的包含时间。规则是​​先优化栈顶最宽的那块;比它窄的都是噪声​​。在一个只占百分之三运行时间的函数上花一下午,即便把它快一倍,也是浪费。

cachegrind(valgrind --tool=cachegrind ./your_binary)是精确工具。它模拟宿主机的缓存层级(默认是 L1 与 LL),并按源代码行给出准确的 L1 与 LL 未命中计数,用 cg_annotate 看。它比真实运行慢 20 到 100 倍,所以你要外科手术式地用:先从 perf report 挑出热函数,再用 cachegrind 看是哪几行 load 真的在 miss。Compiler Explorer(godbolt.org,国内可正常访问)是回答"编译器到底为这个函数发了什么"的日常工具——粘函数进去、选 x86-64 gcc 12.2 -O2 -mavx2、读汇编。本模块第 4 课会重度依赖它;这里先把它引入。

微基准库(micro-benchmark)用 ​Google Benchmark​​。模板代码不多,框架替你处理预热、迭代次数、方差估计与每次迭代的计时:

#include <benchmark/benchmark.h>

static void BM_RowMajor(benchmark::State& state) {
    std::vector<double> m(N * N);
    for (std::size_t k = 0; k < m.size(); ++k) m[k] = static_cast<double>(k) * 1e-9;
    for (auto _ : state) {
        benchmark::DoNotOptimize(sum_row_major(m));
    }
}
BENCHMARK(BM_RowMajor);

static void BM_ColMajor(benchmark::State& state) {
    std::vector<double> m(N * N);
    for (std::size_t k = 0; k < m.size(); ++k) m[k] = static_cast<double>(k) * 1e-9;
    for (auto _ : state) {
        benchmark::DoNotOptimize(sum_col_major(m));
    }
}
BENCHMARK(BM_ColMajor);

BENCHMARK_MAIN();

benchmark::DoNotOptimize(x) 是关键一句。少了它,如果结果没人观察,编译器就有权把整个 benchmark 循环当作死代码消掉——你那个"每次迭代 1 纳秒"的测量,量的其实是空循环。框架打印每次迭代的纳秒、CPU 时间,以及它自动调到的迭代数;方差列让你能拒掉噪声大的运行。

经典工作例:行优先 vs 列优先

分配一个 std::vector<double>,大小 N * N,取 N = 10000——大约 800 MiB,远超任何 L3 缓存。用两种方式求和,触碰的字节数完全相同、次数相同,只有循环顺序不同:

static constexpr std::size_t N = 10000;

double sum_row_major(const std::vector<double>& m) {
    double s = 0.0;
    for (std::size_t i = 0; i < N; ++i) {
        for (std::size_t j = 0; j < N; ++j) {
            s += m[i * N + j];
        }
    }
    return s;
}

double sum_col_major(const std::vector<double>& m) {
    double s = 0.0;
    for (std::size_t j = 0; j < N; ++j) {
        for (std::size_t i = 0; i < N; ++i) {
            s += m[i * N + j];
        }
    }
    return s;
}

两个函数触碰相同的 800 MiB、相同次数。数值上的和按字节相同。只有访存模式不同:sum_row_major 在一行内走相邻的 double(一根 64 字节的缓存行装八个 double,预取器顺着往前推);sum_col_major 每次迭代跳 N * sizeof(double) = 80000 字节,同时打掉缓存行和预取器。

每个都跑一次 perf stat(下面的数字来自 2.8 GHz 的单核 Ice Lake Xeon,绝对值会因宿主机不同而漂移,但​​比例​​在所有现代 x86 上稳定):

# BM_RowMajor (taskset -c 2 perf stat -e cycles,instructions,cache-references,cache-misses,branch-misses ...)
          1,400,000,000      cycles
          5,200,000,000      instructions              #    3.71  insn per cycle
             12,500,000      cache-references
                145,000      cache-misses              #    1.16 % of all cache refs
                340,000      branch-misses

# BM_ColMajor (same command, different filter)
         18,300,000,000      cycles
          5,200,000,000      instructions              #    0.28  insn per cycle
            105,000,000      cache-references
             82,500,000      cache-misses              #   78.57 % of all cache refs
                360,000      branch-misses

从 IPC 那行开始读。行优先退役 3.71 条指令每周期,接近前端上限。列优先退役 0.28——CPU 十四个周期里有十三个在等缓存。缓存未命中率印证这件事:同样的指令数,1.16% vs 78.57%。指令数相同,因为两个函数发的 load 和加法完全一样;只有顺序变了,只有缓存行为对此有响应。分支未命中数两边一样——循环分支不管哪种顺序都完全可预测。原因纯粹是访存模式,而剖析器是你能看见这件事的唯一地方。

纪律

三句话管住本模块剩下的内容。​​优化之前先测量。​ ​测量不能复现,优化就不存在。​ ​剖析器永远对,你的直觉通常错。​ 第 2、3、4 课都会把这套工具链——perf stat、perf record、cachegrind、Google Benchmark、godbolt——作为它们的加速是真材实料而非民间传说的依据。第 4 课声称某个 AVX2 内循环比标量版快 3.8 倍,这个声明有 perf stat 撑——IPC 从 2.1 涨到 3.6——并且二进制里的 __m256d 指令在 godbolt 上得到确认。你给自己的改动拿不出这种证据时,你就还没把活干完。

第 2 课往下走一步。你刚看到访存模式决定绝对速度;第 2 课给你看决定"访存模式"到底是什么的​​布局​​决策——用 alignas 做缓存行对齐、padding 与伪共享(只先讲名词,线程材料还不动),以及结构体数组(AoS, array of structures)与数组结构体(SoA, structure of arrays)之间的取舍——这个取舍决定一段对一百万条交易记录的热循环到底是每条记录一次缓存行 load,还是每八条记录才一次。

练习