QuanZhou's Wiki

存储器层次与 cache:为什么按列遍历二维数组会慢

~/ 体系结构#cache#局部性#存储器层次#性能

1. 两个循环,做的事一模一样

复杂度一样,速度却不一样

先猜,再往下读

下面两个函数都把一个 N × N 的 int 矩阵求和。加法次数一样,访问的元素也一样,只是两层循环换了个位置:

#include <cstddef>
#include <vector>

// 矩阵按行优先存放:a[i * n + j] 是第 i 行第 j 列
long long sum_rows(const std::vector<int>& a, std::size_t n) {
    long long s = 0;
    for (std::size_t i = 0; i < n; ++i)
        for (std::size_t j = 0; j < n; ++j)
            s += a[i * n + j];      // 内层沿着一行走
    return s;
}

long long sum_cols(const std::vector<int>& a, std::size_t n) {
    long long s = 0;
    for (std::size_t j = 0; j < n; ++j)
        for (std::size_t i = 0; i < n; ++i)
            s += a[i * n + j];      // 内层沿着一列走
    return s;
}

N 取 4096 时,矩阵是 64 MiB。两个函数哪个快?如果有差距,大概差几倍?

先在纸上写下你的答案。

展开答案

sum_rows 快,而且通常快好几倍。两者都是 O(N2)O(N^2),差距完全来自访问内存的顺序。

具体差几倍取决于机器、编译选项和 N。第 8 节有一份本机实测,建议先自己测一遍再对照。如果你猜两者一样快,说明还缺一个模型:CPU 读内存的成本不是固定的,它取决于数据此刻在存储器层次的哪一层。

本文的位置与阅读方式

这是体系结构系列的第一篇,对应 CS:APP 第 6 章的核心内容。前面的《C++ 对象内存布局》讲的是一个对象在内存里怎么摆放,这一篇再往下一层:CPU 是怎么把这些字节读进来的。

阅读路线是:存储器为什么分层 → 局部性 → cache 的组织与地址划分 → 三类缺失 → 怎样写出 cache 友好的代码 → 动手测量。读完以后,你应该能在不运行程序的情况下,估算一个循环每次迭代大约缺失多少次 cache,并据此决定循环顺序和数据布局。

先交代实验环境

本机的 cache 参数

  • 机器:Apple M5 Pro(arm64),macOS。
  • 编译器:Apple clang 21 和 Homebrew GCC 16.1,-std=c++20。

cache 参数用 sysctl 读取:

sysctl hw.cachelinesize hw.perflevel0.l1dcachesize hw.perflevel0.l2cachesize hw.perflevel0.cpusperl2 hw.perflevel1.l1dcachesize hw.perflevel1.l2cachesize hw.perflevel1.cpusperl2
hw.cachelinesize: 128
hw.perflevel0.l1dcachesize: 131072
hw.perflevel0.l2cachesize: 16777216
hw.perflevel0.cpusperl2: 6
hw.perflevel1.l1dcachesize: 65536
hw.perflevel1.l2cachesize: 8388608
hw.perflevel1.cpusperl2: 6

这台机器有两类核心,sysctl 把 6 个 perflevel0 核心叫作 Super,12 个 perflevel1 核心叫作 Performance。整理一下:

参数perflevel0(6 核)perflevel1(12 核)
cache line128 字节128 字节
L1 数据 cache每核 128 KiB每核 64 KiB
L2 cache16 MiB,6 核共享8 MiB,每 6 核共享一个

两点要记住:

  • line 是 128 字节。很多 x86-64 机器是 64 字节,资料里的例子大多按 64 算,搬到这台机器上要换算。
  • macOS 不通过 sysctl 公开相联度。下文用到相联度时都会注明是假设。

2. 存储器为什么要分层

又大又快又便宜,只能选两个

每一层都是下一层的缓存

理想的存储器又大又快又便宜,但现实中不可兼得:

  • 寄存器和 SRAM 很快,但每个比特占的芯片面积大,做不大。
  • DRAM 便宜、容量大,但访问一次要等很久。
  • SSD 容量更大,延迟还要再高几个数量级。

于是计算机把它们叠成一个层次。越靠近 CPU 的一层越小、越快,每一层都充当下一层的缓存:

层级容量量级访问延迟量级
寄存器几十个不到 1 ns
L1 cache几十到上百 KiB约 1 ns,几个时钟周期
L2 cache几到十几 MiB几 ns 到十几 ns
DRAM几到几十 GiB约 100 ns
SSDTiB几十 µs

这张表里的延迟是常见的数量级,用来建立直觉,不是本机测量值。重点在比例:从 L1 到 DRAM 差了大约两个数量级。如果每次读内存都要去 DRAM,CPU 大部分时间都在等数据。

读一个 int 时发生了什么

CPU 要读某个地址上的 4 个字节时:

  • 先在 L1 里找。找到了叫命中(hit),几个周期就能拿到。
  • 找不到叫缺失(miss),去 L2 找;L2 也没有,再往下。多等的这段时间叫缺失代价(miss penalty)。
  • 关键在于:从下一层搬上来的不是这 4 个字节,而是包含它的一整块,叫一个 cache line。在本机上是 128 字节。

所以缺失一次,CPU 拿到的其实是 32 个相邻的 int。程序接下来正好要用这 31 个邻居,它们全都会命中;程序只用了这一个就跳到别处,剩下的 124 字节就白搬了。

开头那两个函数的差距,就从这里开始。

命中率 97%,为什么还会慢好几倍?

平均访问时间

衡量一级 cache 的效果,常用平均访问时间:

平均访问时间=命中时间+缺失率×缺失代价\text{平均访问时间} = \text{命中时间} + \text{缺失率} \times \text{缺失代价}

先猜一下:命中时间 1 ns、缺失代价 100 ns,缺失率从 1/32(约 3%)变成 1,平均访问时间差多少倍?

展开答案
  • 缺失率 1/32:1+100/32≈4.11 + 100 / 32 \approx 4.1 ns。
  • 缺失率 1:1+100=1011 + 100 = 101 ns。

差了大约 25 倍。这里的 1 ns 和 100 ns 是示意数字,不是本机测量值。

还有一个更反直觉的地方:即使缺失率只有 3%,平均时间也是命中时间的 4 倍。缺失代价比命中时间大两个数量级,所以缺失率的一点点变化,会被放大成明显的速度差。分析 cache 时盯着缺失率,而不是命中率。

实际程序的差距通常没有公式算的那么大,因为硬件预取会提前搬数据,乱序执行也能让几个缺失同时进行。公式适合估算方向,具体数字要测。

3. 局部性:让搬上来的数据被用上

两种局部性

时间局部性和空间局部性

cache 之所以有用,是因为程序访问内存有规律:

  • 时间局部性:刚访问过的数据,很快还会再访问。
  • 空间局部性:刚访问过某个地址,很快会访问它附近的地址。

看最简单的求和:

long long s = 0;
for (std::size_t i = 0; i < n; ++i)
    s += a[i];
  • s 每次迭代都读写,时间局部性好,通常一直待在寄存器里。
  • a[i] 相邻两次只差 4 字节,空间局部性好。
  • 循环体的指令反复执行同一小段代码,指令 cache 也同时享受两种局部性。

步长:衡量空间局部性的尺子

连续两次访问之间相差的元素个数,叫步长(stride)。设一个 cache line 能装 L 个元素,数据量又远大于 cache:

步长每个 line 用到的元素平均每次访问缺失
1全部 L 个1/L
k(k < L)约 L/k 个约 k/L
≥ L1 个1

本机上 int 的 L = 128 / 4 = 32。步长为 1 时每 32 次访问缺失 1 次;步长达到 32 个 int,也就是 128 字节以后,每次访问都落在新的 line 上。

回到开头的两个循环

行优先意味着什么

C 和 C++ 的二维数组是行优先存放的:同一行的元素相邻,下一行紧跟在上一行后面。a[i * n + j] 的地址是

addr(i,j)=base+(i⋅N+j)⋅4\text{addr}(i, j) = \text{base} + (i \cdot N + j) \cdot 4
  • sum_rows 的内层让 j 加 1,地址加 4 字节,步长为 1,每 32 次访问缺失 1 次。
  • sum_cols 的内层让 i 加 1,地址加 4N 字节。N = 4096 时一次跳 16 KiB,每次访问都落在新的 line 上。等这一列走完、回来读下一列时,前面搬上来的那些 line 早就被挤出去了。

按这个模型,sum_cols 的缺失次数大约是 sum_rows 的 32 倍。但缺失次数之比不等于耗时之比:硬件预取和乱序执行会掩盖一部分延迟,让差距变小;sum_rows 能被编译器向量化,sum_cols 的缺失又可能一路落到 DRAM,这些会让差距变大。实际差多少,第 8 节去测。

Quiz:只读一个字段

struct Tick {
    long long ts;       // 8 字节
    double    price;    // 8 字节
    int       qty;      // 4 字节
    int       side;     // 4 字节
    char      symbol[8];
};                       // 共 32 字节

double sum_price(const std::vector<Tick>& ticks) {
    double s = 0;
    for (const Tick& t : ticks) s += t.price;
    return s;
}

这个循环按顺序遍历 vector,它的空间局部性好吗?

展开答案

按元素算步长是 1,但按字节算,每次跳 32 字节,真正用到的只有其中 8 字节的 price。一个 128 字节的 line 装 4 个 Tick,搬上来的数据只有 1/4 被用上。

成员布局本身也有讲究,比如 Tick 按对齐值从大到小排列,没有填充,这一点在《C++ 对象内存布局》第 2 节讲过。至于怎么让利用率变成 100%,见第 6 节。

4. cache 怎么组织:S、E、B 三个参数

组、行、块

三个参数描述一个 cache

要理解数据为什么会被挤出去,以及为什么有时 cache 明明没满却频繁缺失,需要看 cache 的内部结构。一个 cache 可以用三个参数描述:

  • B:每个 line 的数据块大小(字节)。本机是 128。
  • E:每一组(set)有几行,叫相联度(associativity)。
  • S:一共有多少组。

每一行除了 B 字节数据,还带一个有效位和一个标记(tag),说明这一行现在装的是哪块内存。总容量是

C=S×E×BC = S \times E \times B

地址拆成三段

查找时,硬件把地址拆成三段。设 B=2bB = 2^b,S=2sS = 2^s:

地址位名字作用
最低 b 位块内偏移(block offset)在 line 里找第几个字节
中间 s 位组索引(set index)决定去哪一组找
剩下的高位标记(tag)和组里每一行的 tag 比较

查找分三步:用组索引选组;在组里找有效且 tag 相同的行;找到就用块内偏移取数据,找不到就是缺失,从下一层搬来这一块,放进这一组。组里满了,就按替换策略踢掉一行,通常是近似的 LRU,也就是最久没用的那一行。

动手拆一个地址

用一个假设的 cache 算一遍

假设一个 L1 数据 cache 是 64 KiB、8 路组相联、line 为 128 字节。容量和 line 大小与本机 perflevel1 核心一致,8 路是假设的:

S=CE×B=655368×128=64S = \frac{C}{E \times B} = \frac{65536}{8 \times 128} = 64

所以 b=7b = 7,s=6s = 6。拿地址 0x12345 来拆,先自己算一下 tag、组索引和偏移。

展开答案
  • 偏移:低 7 位,0x12345 & 0x7F = 69。
  • 组索引:右移 7 位后取低 6 位,(0x12345 >> 7) & 0x3F = 6。
  • tag:右移 13 位,0x12345 >> 13 = 9。

于是硬件去第 6 组,把 8 行的 tag 依次和 9 比较。

让程序替你拆

手算容易出错,后面要拆很多地址,写个小程序。下一张卡片会一直用它:

#include <cstdint>
#include <cstdio>
#include <initializer_list>

// 假设的 cache:64 KiB,8 路组相联,line 128 字节
constexpr std::uint64_t kLine = 128, kWays = 8, kSize = 64 * 1024;
constexpr std::uint64_t kSets = kSize / (kWays * kLine);   // 64

void split(std::uint64_t addr) {
    std::uint64_t offset = addr % kLine;
    std::uint64_t set    = (addr / kLine) % kSets;
    std::uint64_t tag    = addr / (kLine * kSets);
    std::printf("addr=0x%06llx  tag=%llu  set=%2llu  offset=%llu\n",
                (unsigned long long)addr, (unsigned long long)tag,
                (unsigned long long)set, (unsigned long long)offset);
}

int main() {
    split(0x12345);
}
addr=0x012345  tag=9  set= 6  offset=69

和手算一致。

为什么用中间的位做组索引

如果用最高的几位做组索引,一大段连续内存的高位都一样,会全部挤进同一组,顺序遍历数组时只能用到一组。用中间位,相邻的 line 落在相邻的组里,连续的数据能均匀铺满整个 cache。

三种组织方式

类型参数特点
直接映射E = 1每块内存只有一个位置可放,硬件最简单,但映射到同一组的两块会互相踢
组相联1 < E < C/B每组 E 个位置,现代 CPU 的 L1、L2 都是这种
全相联S = 1放哪都行,冲突最少,但每次要比较所有行,只适合很小的结构,比如一些 TLB

E 越大冲突越少,但每次查找要同时比较更多 tag,电路更复杂、功耗更高,命中延迟也可能变长。这是一个工程取舍。

三类缺失

按原因分类,才知道怎么优化

  • 冷缺失(compulsory miss):第一次访问某块数据,cache 里必然没有。只能靠预取缓解。
  • 容量缺失(capacity miss):程序反复使用的数据,也就是工作集,比 cache 大,装不下。解法是缩小工作集,比如分块计算。
  • 冲突缺失(conflict miss):cache 整体没满,但好几块数据恰好映射到同一组,超过了 E 行,互相踢。解法是改变数据的地址分布,比如在每行末尾加填充。

冲突缺失最反直觉,下一张卡片用开头的矩阵算一遍。

N = 4096 时,一整列挤进了同一组

先猜

还是用上面假设的 cache。N = 4096 时,同一列相邻两行的地址相差 4096 × 4 = 16 KiB。这一列的元素会分布在哪些组里?

展开答案

把 main 改成依次拆前 4 行同一列的地址:

for (int i = 0; i < 4; ++i) split(std::uint64_t(i) * 4096 * 4);
addr=0x000000  tag=0  set= 0  offset=0
addr=0x004000  tag=2  set= 0  offset=0
addr=0x008000  tag=4  set= 0  offset=0
addr=0x00c000  tag=6  set= 0  offset=0

全在第 0 组。原因是 S×B=64×128=8S \times B = 64 \times 128 = 8 KiB,地址每增加 8 KiB,组索引就绕回原值;16 KiB 是 8 KiB 的整数倍,所以一整列的 4096 个元素全部落在同一组。

这一组只有 8 行,按列访问到第 9 个元素就会踢掉第 1 个。整个 64 KiB 的 cache,按列遍历时只用上了 8 行,也就是 1 KiB。

那就把 N 改成 4100?

每行多 4 个 int,也就是多 16 字节。直觉上,这样相邻两行就会错开到不同的组。先别急着下结论,跑一下看看:

for (int i : {0, 1, 7, 8, 9}) split(std::uint64_t(i) * 4100 * 4);
addr=0x000000  tag=0  set= 0  offset=0
addr=0x004010  tag=2  set= 0  offset=16
addr=0x01c070  tag=14  set= 0  offset=112
addr=0x020080  tag=16  set= 1  offset=0
addr=0x024090  tag=18  set= 1  offset=16

直觉只对了一半。每行多出的 16 字节先体现在块内偏移上,要累积 8 行凑满 128 字节,组索引才加 1。所以是每 8 行换一组:第 0–7 行在第 0 组,第 8–15 行在第 1 组,以此类推。

这已经比 N = 4096 好得多:一整列现在均匀分布在全部 64 组里,能用上整个 cache,不再只有 8 行。如果想让相邻两行直接落在相邻的组里,每行要多出一整个 line,也就是 32 个 int,N = 4128:

addr=0x000000  tag=0  set= 0  offset=0
addr=0x004080  tag=2  set= 1  offset=0
addr=0x008100  tag=4  set= 2  offset=0

这个推理的边界

这只是对一个假设的 L1 的推理。N 很大时,一整列有 4096 个 line、共 512 KiB,本来就装不进 L1,就算错开了组,容量缺失也在。真正受影响的是 L2:512 KiB 本来装得进 16 MiB 的 L2,如果因为 2 的幂步长挤在少数几组里,就装不下了。

能装下多少,可以不依赖相联度算出来。组索引每隔 S×B=C/ES \times B = C / E 字节绕回一次,设步长 dd 是 2 的幂,且 B≤d≤C/EB \le d \le C / E,那么一串步长为 dd 的访问只能用到 (C/E)/d(C / E) / d 个组,每组 EE 行:

可容纳的 line 数=C/Ed×E=Cd\text{可容纳的 line 数} = \frac{C / E}{d} \times E = \frac{C}{d}

EE 被约掉了。N = 4096 时 d=16d = 16 KiB,16 MiB 的 L2 只能容纳 16 MiB/16 KiB=102416\ \text{MiB} / 16\ \text{KiB} = 1024 个 line,远少于一列的 4096 个;8 MiB 的 L2 只有 512 个。这个推导假设组索引直接取地址的中间位,如果硬件对索引做了哈希,具体数字会不同。

N = 4096、4100、4128 三种情况下 sum_cols 的速度差多少,第 8 节的实验里测一下。

写操作怎么处理

两个问题,四种策略

  • 写命中时,要不要立即写下一层?
    • 写直达(write-through):每次写都同时写下一层,简单但流量大。
    • 写回(write-back):只改 cache 里的这一行,标记为脏(dirty),被替换时才写回。现代 CPU 的数据 cache 基本都这样做。
  • 写缺失时,要不要先把这一块搬上来?
    • 写分配(write-allocate):先把块搬进 cache,再在 cache 里写,通常和写回搭配。
    • 非写分配(no-write-allocate):直接写到下一层,不进 cache。

写分配意味着,即使你只写不读,写一个数组也会先把它读进 cache。第 6 节的 false sharing 会用到这一点:写一个变量,也要先把它所在的整个 line 拿到手。

5. 矩阵乘法:同样的乘法,不同的循环顺序

6 种循环顺序,缺失次数差 16 倍

用步长规律来估算

计算 C=A×BC = A \times B,三个矩阵都是 n × n 的 double,按行优先存放。i、j、k 三重循环有 6 种排列,结果完全相同,缺失次数却差很多。

用第 3 节的步长规律估算:本机一个 line 装 L = 128 / 8 = 16 个 double,并假设 n 很大,一整列装不进 cache。只看最内层循环,每次迭代平均缺失多少次?先自己填一下,再展开对照。

展开答案
循环顺序内层循环访问每次迭代的缺失L = 16 时
ijk、jikA 按行(1/L),B 按列(1)1 + 1/L约 1.06
jki、kjiA 按列(1),C 按列(1)22
kij、ikjB 按行(1/L),C 按行(1/L)2/L0.125

最好和最差差了 16 倍。这是模型估算,没有考虑预取和多级 cache,但足以说明方向。

ikj 的写法

// C 先清零;内层沿着 B 和 C 的同一行走,步长都是 1
for (std::size_t i = 0; i < n; ++i)
    for (std::size_t k = 0; k < n; ++k) {
        const double r = A[i * n + k];          // 内层循环里不变,放进寄存器
        for (std::size_t j = 0; j < n; ++j)
            C[i * n + j] += r * B[k * n + j];
    }

只是换了循环顺序,内层每次迭代的缺失就从约 1 次降到 0.125 次。再进一步是分块(blocking):把矩阵切成能装进 cache 的小块,在一块上算完再换下一块,让时间局部性也用足。分块留到后续文章。

6. 数据布局与 false sharing

AoS 还是 SoA:跟着热点循环走

把 price 单独存一列

第 3 节 Quiz 里的 std::vector<Tick> 叫 AoS(array of structs),一个对象的所有字段挨在一起。如果热点循环只读 price,可以改成 SoA(struct of arrays):

struct Ticks {
    std::vector<long long> ts;
    std::vector<double>    price;
    std::vector<int>       qty;
    // ...
};

double sum_price(const Ticks& t) {
    double s = 0;
    for (double p : t.price) s += p;   // 每个 line 里的 16 个 double 全部用上
    return s;
}

现在搬上来的每个 line 全是 price,利用率从 1/4 变成 100%,连续的 double 也更容易被编译器向量化。

没有哪种布局永远更好

反过来,如果每次处理一个 tick 都要用到大部分字段,AoS 更好,因为一次缺失就把需要的字段都搬上来了。看热点循环实际读哪些字段,再决定布局。

false sharing:两个线程没共享数据,却互相拖慢

一致性以 line 为单位

多线程时还有一个陷阱。cache 一致性协议以 line 为单位跟踪数据:一个核要写某个 line,必须先让其他核里这个 line 的副本失效。

struct Counters {
    std::atomic<long long> a;   // 线程 1 一直在加
    std::atomic<long long> b;   // 线程 2 一直在加
};

a 和 b 逻辑上没有任何共享,但它们挨在一起,落在同一个 line 里。两个核会不停地让对方的副本失效,这个 line 在两个核之间来回搬。这就是 false sharing,可能让本该并行的代码比单线程还慢。

让它们落在不同的 line 上

struct Counters {
    alignas(128) std::atomic<long long> a;
    alignas(128) std::atomic<long long> b;
};

这里写 128,是因为本机的 line 是 128 字节。《C++ 对象内存布局》的 alignas 一节已经提到过:写死 64 在这台机器上不够;std::hardware_destructive_interference_size 是编译期常量,在本机的 Apple clang 21 和 GCC 16 下都是 256,比实际的 128 大,能保证隔开,代价是多占空间。

false sharing 在低延迟系统里很常见,比如各线程分别更新的统计计数器、SPSC 队列的 head 和 tail。后面讲缓存一致性协议时,会专门做实验测它的代价。

7. 存储器山:把局部性画成一张图

工作集和步长,两个维度一起看

实验怎么设计

反复读一个数组,改变两个变量,测读取吞吐量:

  • 工作集大小:数组有多大,决定数据能待在哪一级 cache 里,对应时间局部性。
  • 步长:每次跳多少个元素,对应空间局部性。

把吞吐量画成这两个变量的曲面,就得到存储器山(memory mountain)。

先推测它的形状

不用测量,从前面的知识就能推出大致形状:

  • 沿工作集方向会看到几级台阶:装得进 L1 时最高,超过 L1 掉一级,超过 L2 再掉一级,最后落到 DRAM 的水平。台阶的位置大致对应各级 cache 的容量。
  • 沿步长方向,吞吐量随步长增大而下降,步长达到一个 line 之后每次都缺失,曲线变平。
  • 步长为 1 时,即使工作集远大于 cache,吞吐量也比大步长高不少。这是硬件预取的功劳:它发现你在顺序读,就提前把后面的 line 搬上来。

这台机器上的台阶具体在哪里,是不是对得上 sysctl 报出的 128 KiB 和 16 MiB,要测了才知道。它是第 8 节实验的扩展题。

8. 动手测量:按行与按列

先写预测,再写代码

实验要求

代码自己写,下面只给要求。新建一个目录,写 rowcol.cpp:

  • 用 std::vector<int> 存 N × N 矩阵,下标用 i * N + j。N 从第一个命令行参数读入,可选的第二个参数是重复次数,默认 1。
  • 实现第 1 节的 sum_rows 和 sum_cols。
  • 用 std::chrono::steady_clock 分别计时,每个函数跑 5 次取最小值。
  • 把求和结果打印出来,否则编译器发现结果没用,可能把循环整个删掉。但打印要放在计时区间之外:在终端里每次 printf 都是一次系统调用,要花几微秒。
  • N 小时一次求和只要几微秒,计时噪声和函数本身一样大。先不计时地预热若干次,再在计时区间内连续调用“重复次数”那么多次取平均。每次调用前加一道编译器屏障,比如 asm volatile("" : : "r"(a.data()) : "memory");,防止编译器发现输入没变,把多次调用合并成一次。
  • 输出两者的耗时和比值。
clang++ -std=c++20 -O2 rowcol.cpp -o rowcol
./rowcol 4096 && ./rowcol 4100 && ./rowcol 4128 && ./rowcol 256 1000

运行前先填这张表

问题我的预测实测
N = 4096 时,sum_cols 比 sum_rows 慢几倍?
N 改成 4100,sum_rows 的耗时会变吗?
N 改成 4100 和 4128,sum_cols 会变快多少?
N = 256(矩阵 256 KiB),差距变大还是变小?
-O2 换成 -O0,差距变大还是变小?

测完把实测填进去。和预测对不上的格子最有价值:回到对应的小节,找出是哪一步推理漏了东西,再把更正写在旁边。

我的一次实测

  • 机器:Apple M5 Pro,参数见第 1 节;页大小 16 KiB(sysctl hw.pagesize)。
  • 编译:Apple clang 21.0.0,-std=c++20 -O2,最后一行改为 -O0。
  • 计时:每次运行取 5 次中的最小值,每个配置运行 3 次,表中取中位数,单位 ms。N = 256 先预热 1000 次,再连续调用 1000 次取平均,运行 5 次取中位数。
问题我的预测实测对照
N = 4096 时,sum_cols 比 sum_rows 慢几倍?32 倍cols 54.043 / rows 0.912,约 59 倍量级对,实测更大
N 改成 4100,sum_rows 的耗时会变吗?不变0.912 → 0.827对,差别在噪声范围内
N 改成 4100 和 4128,sum_cols 会变快多少?不变,cache 都被用到了54.043 → 20.726 和 22.359,耗时降到约 40%错
N = 256(矩阵 256 KiB),差距变大还是变小?变小,sum_cols 也能放进 cachecols 0.0387 / rows 0.0030,约 13 倍对
-O2 换成 -O0,差距变大还是变小?变大,编译器的优化变少了cols 65.439 / rows 19.311,约 3.4 倍错

对得上的格子,也要能说清楚数字为什么是这样:

  • 59 倍比估算的 32 倍还大。 32 倍只数了缺失次数。sum_rows 被向量化,又有预取帮忙,64 MiB 只用 0.912 ms,约 74 GB/s;sum_cols 在 N = 4096 时撞上了下面要说的冲突缺失,下一列要回 DRAM 取,而且步长 16 KiB 正好是一页,每次访问都换一页,TLB 的压力也很大。
  • N = 256 装得进 L2,仍差 13 倍。 矩阵 256 KiB 装不进 128 KiB 的 L1。按列走时步长是 1 KiB,用第 4 节的公式,L1 只能容纳 128 KiB/1 KiB=128128\ \text{KiB} / 1\ \text{KiB} = 128 个 line,少于一列的 256 个,所以 sum_cols 每次访问都要去 L2;sum_rows 顺序读,一个 line 只缺失一次,还有预取提前搬数据。差距变小,是因为缺失代价从 DRAM 的量级降到了 L2 的量级。

两处预测错误的更正:

  • N = 4100 让 sum_cols 快了 2.5 倍左右。 我只想了容量,没有逐级考虑映射。两种 N 下一列都是 512 KiB,都装不进 L1,所以差别不在 L1,而在下一列(j + 1,和这一列共用 line)还能不能在 L2 命中。N = 4096 时,按第 4 节的公式,L2 只能容纳 1024 个 line,少于一列的 4096 个,下一列只能回 DRAM 取,这是冲突缺失。N = 4100 时每行错开 16 字节,这一列分散到 L2 的许多组里,下一列多数在 L2 命中。冲突缺失要逐级看:容量够,不等于映射得开。
  • -O0 反而让差距变小。 sum_rows 从 0.9 ms 变成 19.3 ms,慢了约 20 倍:失去了向量化,s、i、j 每次迭代都要读写栈,瓶颈从内存带宽变成了指令数。sum_cols 只从 54 ms 变成 65 ms,因为它本来就在等内存,多出来的指令被延迟盖住了。两边加上一块相近的计算开销,比值就被稀释了。反过来,-O2 下的 59 倍也不全是 cache 的功劳,其中一部分来自 sum_rows 被向量化。

扩展

  • 步长实验:对一个 64 MiB 的数组,分别以步长 1、2、4、8、16、32、64 求和,画出每个元素的平均耗时,看看曲线在哪里变平,是否和 128 字节的 line 对得上。
  • 工作集实验:步长固定为 1,数组从 16 KiB 增大到 256 MiB,看耗时的台阶出现在哪里。
  • 矩阵乘法:n = 1024,比较 ijk 和 ikj 的耗时,看是否符合第 5 节的估算方向。

记录实验时交代清楚机器、编译器版本和编译选项,性能结论离开这些信息就没有意义。

9. 检验:合上文章答一遍

每题先自己回答,再展开对照

Quiz 1:一次 cache 缺失,从下一层搬上来多少数据?这对顺序遍历意味着什么?

搬上来一整个 cache line,本机是 128 字节。顺序遍历时,一次缺失之后同一个 line 里剩下的数据全部命中,int 数组每 32 次访问才缺失 1 次。

Quiz 2:命中率从 97% 提高到 99%,听起来只提高了 2 个百分点,为什么可能快很多?

平均访问时间 = 命中时间 + 缺失率 × 缺失代价。缺失代价比命中时间大两个数量级,所以要看缺失率:从 3% 降到 1%,缺失项变成原来的三分之一。按命中 1 ns、缺失代价 100 ns 的示意数字,平均时间从 4 ns 降到 2 ns。

Quiz 3:已知容量 C、相联度 E、line 大小 B,怎么算组数?地址的三段分别做什么?

S=C/(E×B)S = C / (E \times B)。最低 log⁡2B\log_2 B 位是块内偏移,中间 log⁡2S\log_2 S 位是组索引,剩下的高位是 tag。组索引选组,tag 判断是否命中,偏移在 line 里取数据。

Quiz 4:为什么用地址的中间位做组索引,而不是最高位?

连续内存的高位相同,用高位做索引会让一大段连续数据挤进同一组。用中间位,相邻的 line 落在相邻的组里,顺序访问能铺满整个 cache。

Quiz 5:冷缺失、容量缺失、冲突缺失分别怎么缓解?

冷缺失靠预取;容量缺失靠缩小工作集,比如分块;冲突缺失靠改变地址分布,比如给每行加填充,避免 2 的幂步长。

Quiz 6:N = 4096 的 int 矩阵按列遍历,为什么会出现严重的冲突缺失?N 改成 4100 解决了多少?

在 S × B = 8 KiB 的假设下,行长 16 KiB 是 8 KiB 的整数倍,一整列全落在同一组,只能用上 E 行。N = 4100 时每行多 16 字节,要 8 行才让组索引加 1,一列均匀分布到全部组里,不再只用一组;N = 4128 每行多一整个 line,相邻行直接落在相邻的组。

在本机上,一列 512 KiB 怎样都装不进 L1,真正起作用的是 L2:步长 16 KiB 时 L2 只能容纳 C/16 KiB=1024C / 16\ \text{KiB} = 1024 个 line,少于 4096,下一列要回 DRAM。N 改成 4100 后下一列能在 L2 命中,实测 sum_cols 耗时降到约 40%。

Quiz 7(面试题):矩阵乘法的 6 种循环顺序里哪类最好?为什么?

ikj 和 kij 最好。内层循环沿着 B 和 C 的同一行走,两者步长都是 1,每次迭代约缺失 2/L 次;ijk 有一个按列访问,约 1 + 1/L 次;jki 两个都按列,约 2 次。

Quiz 8(面试题):什么是 false sharing?怎样避免?

两个线程写的是不同变量,但变量落在同一个 cache line 上,一致性协议以 line 为单位失效,导致这个 line 在核之间来回搬。用 alignas 把它们隔到不同的 line 上,间隔按目标机器的 line 大小确定;std::hardware_destructive_interference_size 是保守的编译期常量,不一定等于实际值。

Quiz 9:同一份代码从 -O2 换成 -O0,按行和按列的耗时比从 59 倍降到 3.4 倍。为什么关掉优化反而缩小了差距?

两者的瓶颈不同。sum_rows 在 -O2 下是向量化的顺序读,受内存带宽限制;到了 -O0,每次迭代都要读写栈上的变量,变成受指令数限制,慢了约 20 倍。sum_cols 本来就在等内存,多出来的指令被缺失延迟盖住,只慢了约 1.2 倍。两边加上一块相近的固定开销,比值就被稀释了。这也说明 -O2 下的倍数里,有一部分来自向量化,不全是 cache。

10. 一套可以复用的判断方法

拿到一个循环,按顺序问这几个问题

从步长到线程

要回答的问题怎么判断
内层循环的步长是多少?步长为 1 时每 L 次访问缺失约 1 次,达到一个 line 后每次都缺失
工作集装得进哪一级 cache?和 sysctl 报出的 L1、L2 容量比较,装不下就考虑分块
步长是不是 2 的较大次幂?是的话警惕冲突缺失,用填充错开
热点循环读了结构体的哪些字段?只读少数字段考虑 SoA,读大部分字段保持 AoS
有没有多个线程各自写相邻的变量?有就检查 false sharing,按 line 大小对齐隔开

几个值得留下的判断

  • 复杂度相同的两段代码,访问顺序不同就可能差好几倍。分析性能时,先看访问模式,再看指令数。
  • 讨论 cache 时先说清楚机器参数:本机 line 是 128 字节,不是很多资料默认的 64。
  • 估算可以指明方向,但实际差距要测:预取、乱序执行和多级 cache 都会改变结果。
  • 冲突缺失要逐级看。步长 d 是 2 的幂时,一级 cache 只能容纳 C / d 个 line,L1 装不下的时候,再看 L2 装不装得下。
  • 测微秒级的代码,先预热,再重复上千次取平均;打印放在计时区间外,并防止编译器合并重复调用。

延伸阅读

需要更多细节时,从这里查

下一步可以沿三个方向继续:一是分块矩阵乘法,把时间局部性也用足;二是虚拟内存和 TLB,本机的页大小是 16 KiB(sysctl hw.pagesize),大步长访问还会引发 TLB 缺失;三是缓存一致性协议 MESI,它解释了 false sharing 背后 line 是怎样在核之间传递的。