同样是把一个 4096×4096 的整数矩阵全部加起来,代码只改了一个循环的嵌套顺序,耗时差出十倍。本机实测:按行遍历 26 毫秒,按列遍历 283 毫秒,比值 10.88。算法复杂度完全一样,加法次数一个不少,慢的那版甚至没有多做什么。

原因不在算法,在内存访问顺序。按行走,下一个元素就在刚才读进来的那一小片数据里;按列走,每走一步都跳到 16KB 之外,缓存里没有现成的,只能去更远的地方取。CPU 的执行速度比内存快太多,等数据的时间就成了主角。

这篇就讲这件事:缓存到底分几层、一次 miss 要等多久、为什么访问顺序能决定快慢,以及怎么在自己机器上把这些数字测出来。

缓存在哪:从寄存器到内存

CPU 不是直接从内存拿数据的。它内部有一串容量越来越小、速度越来越快的存储,离执行单元越近越快也越贵。数据被一层层往上搬,用完再往下写。

CPU 侧的存储层级
寄存器几十到几百个,延迟约一个周期。编译器分配,程序员只能间接影响。
L1 缓存每个核私有,通常几十 KB,分成指令和数据两部分,延迟几个周期。
L2 缓存每个核私有,通常几百 KB 到几 MB,延迟十几个周期。
L3 缓存多核共享,常见十几到几十 MB,延迟几十个周期。
内存容量以 GB 计,延迟上百个周期,还要经过内存控制器和总线。

容量和延迟的数字是公开架构资料的典型范围,不是每颗芯片都一样。本机的固件报告里 L2 和 L3 的数值按簇统计,读出来不直观,所以下面不引用具体容量,直接用实测的拐点说话。

这一层结构的目的只有一个:让常用数据待在离 CPU 近的地方。程序访问内存有很强的规律,刚刚用过的数据很可能马上再用,相邻的数据很可能接着用。缓存就是靠这两个规律把命中率做上去的。

缓存行:搬运的单位是 64 字节

缓存和内存之间不是按变量搬,而是按块搬。这个块叫缓存行,cache line,x86 上通常是 64 字节。你读一个 4 字节的整数,硬件会把包含它的 64 字节整块取进来,因为这 64 字节里的其他数据很可能马上被用到。

缓存行解释了很多「看起来不合理」的性能现象。两个相邻的变量被两个线程分别改写,逻辑上毫不相干,但只要它们落在同一行里,硬件就要在两个核之间反复同步这一整行,速度掉得厉害。这就是伪共享,后面单独讲。

它也解释了为什么按列遍历会慢。矩阵按行存储,一行是连续的;按列走时,每一步跨过一整行,64 字节的缓存行里只用到了一个元素,其余 60 字节被白白搬进来。下一次再走这一列,已经是几千行之后,那一行早就被挤出去了。

还有一个细节:缓存行有对齐要求。一个跨两行的数据访问可能要拆成两次,甚至触发两次总线事务。编译器通常会把大结构按 64 字节对齐,但自己分配的内存不一定,写高性能代码时要留意。缓存行也不能无限加大:行越大,顺序访问越划算,随机访问浪费越多,一致性维护的粒度也越粗。64 字节是多年权衡的结果,不同架构可能不同,按 64 字节估算通常够用。

命中、未命中和延迟量级

CPU 要的数据在缓存里,叫命中,hit;不在,叫未命中,miss。命中时按层级取,L1 最快,L2 次之,L3 再次。未命中时要往下走到内存,甚至走到更慢的地方,期间执行单元可能无事可做。

延迟量级可以这样记:L1 几个周期,L2 十几个周期,L3 几十个周期,内存上百个周期。按常见的 4GHz 量级折算,一个周期约 0.25 纳秒,L1 大概是 1 纳秒级,内存是几十到上百纳秒。这些是公开资料的经验值,具体到某颗芯片会有出入,本机实测的数字在后面。

关键不是单个数字,而是比例。一次内存访问的延迟,足够 CPU 执行几百条算术指令。如果代码每隔几条指令就 miss 一次,执行单元大部分时间在等,主频再高也没用。反过来,如果数据都在 L1 里,CPU 的发射宽度和乱序能力才能发挥出来。

缓存未命中还有不同的处理方式。顺序访问时,硬件预取器会提前把后面的行取进来,miss 的代价被掩盖;随机访问时,预取器猜不中,只能老老实实等。这就是为什么链表遍历通常比数组遍历慢,哪怕算法复杂度一样。

局部性:空间和时间

缓存能起作用,靠的是两类局部性。空间局部性指「用了一个地址,附近的地址很可能马上被用」,数组、结构体、连续的图像像素都符合。时间局部性指「刚用过的地址,很快会再用」,循环里的累加变量、反复访问的配置表都符合。

写代码时能做的,大多是把访问模式往这两条上靠。把二维数组按行遍历,是空间局部性;把循环里反复用到的值提到外层,是时间局部性;把链表的节点改成数组下标,是把随机访问变成顺序访问。这些改动不改变算法,但能改变缓存命中率。

反过来,有些写法天然反局部性。按列遍历二维数组、在很大的数组里做随机跳转、每个元素都新建一个对象、把热数据和冷数据混在一个结构体里,都会让缓存行里的大部分字节被浪费。知道原因,才有改的方向。矩阵分块是这两种局部性的典型用法:把大矩阵切成能装进缓存的小块,块内按行访问,算完一块再换下一块。块大小要按缓存容量估,太大装不下,太小则循环开销上升。

局部性不是理论概念,它可以直接测。固定总访问次数,只改工作集大小或步长,耗时曲线会在缓存容量附近出现明显的拐点。下面就用这个方法。

预取:帮忙还是添乱

硬件预取器会观察访问模式,提前把可能用到的缓存行取进来。顺序扫描时它工作得很好,因为下一步的地址几乎可以确定。跨步访问也能被识别,只要步长固定。随机访问就没办法,预取器没有可靠的方向。

预取也有代价。取进来的数据如果没被用到,就白占缓存空间,还可能把有用的行挤出去;预取本身要占总线带宽,数据量大时反而拖慢其他访问。软件预取指令也一样,插得太多、太早或太晚,都可能起反效果。

所以优化口诀不是「多加预取」,而是「先让访问模式可预测」。顺序化、分块、把随机索引改成连续索引,这些做法让硬件预取器有活干,比手动插指令稳。确实需要手动预取时,一次只提前几行,并且用实测确认收益。顺序扫描的预取收益最稳定,值得优先考虑。

本机实测:工作集多大就开始变慢

方法是指针追逐:把一块内存按下标串成一条覆盖全部元素的单向链,然后反复执行「读下一个下标」,每次访问都依赖上一次的结果,乱序执行没法提前。工作集从小到大,耗时曲线会告诉你哪一级缓存装不下了。

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <time.h>

static volatile uint64_t sink;

static double ms(clock_t a, clock_t b) {
    return (double)(b - a) * 1000.0 / CLOCKS_PER_SEC;
}

static uint32_t rng_state = 88172645u;
static uint32_t rnd(void) {
    rng_state ^= rng_state << 13;
    rng_state ^= rng_state >> 17;
    rng_state ^= rng_state << 5;
    return rng_state;
}

static void chase(size_t bytes, uint32_t steps) {
    size_t n = bytes / sizeof(uint64_t);
    uint64_t *a = (uint64_t *)malloc(n * sizeof(uint64_t));
    for (size_t i = 0; i < n; i++) a[i] = i;

    for (size_t i = n - 1; i > 0; i--) {
        size_t j = rnd() % (i + 1);
        uint64_t t = a[i]; a[i] = a[j]; a[j] = t;
    }

    /* 把打乱后的下标串成一条覆盖全部元素的链 */
    uint64_t *next = (uint64_t *)malloc(n * sizeof(uint64_t));
    for (size_t i = 0; i < n; i++) next[a[i]] = a[(i + 1) % n];
    for (size_t i = 0; i < n; i++) a[i] = next[i];
    free(next);

    uint64_t idx = 0;
    clock_t t0 = clock();
    for (uint32_t i = 0; i < steps; i++) idx = a[idx];
    clock_t t1 = clock();
    sink = idx;

    double total = ms(t0, t1);
    printf("chase %7zu KB  %8.3f ms  %6.2f ns/access\n",
           bytes / 1024, total, total * 1000000.0 / steps);
    free(a);
}

int main(void) {
    chase(4 * 1024, 8000000u);
    chase(32 * 1024, 8000000u);
    chase(256 * 1024, 8000000u);
    chase(4 * 1024 * 1024, 8000000u);
    chase(64 * 1024 * 1024, 8000000u);
    printf("sink=%llu\n", (unsigned long long)sink);
    return 0;
}

编译并运行,本机实际输出(同一档位重复多次,取其中一次):

gcc -O2 hw_chase.c -o hw_chase.exe
.\hw_chase.exe

chase       4 KB    11.000 ms    1.38 ns/access
chase      32 KB     9.000 ms    1.12 ns/access
chase     256 KB    26.000 ms    3.25 ns/access
chase    4096 KB   574.000 ms   71.75 ns/access
chase   65536 KB  1047.000 ms  130.88 ns/access
sink=1099402252490

4KB 和 32KB 都在 1 纳秒出头,说明工作集还在最快的私有缓存里;256KB 涨到 3.25 纳秒,大约是三倍,对应下一级缓存;4MB 直接跳到 71.75 纳秒,64MB 是 130.88 纳秒,已经是内存的延迟量级。拐点非常清楚:不是逐渐变慢,而是跨过某条线后突然变慢。

同一档位的重复测量也有波动,4KB 那组在不同次运行里出现过接近两倍的差异,这是频率调整和后台进程造成的。看趋势要看多次结果,不要拿单次数字下结论。

另一个实验是二维数组的遍历顺序。4096×4096 个整数,正好 64MB,按行加起来 26 毫秒,按列加起来 283 毫秒。两者都读了 1600 万次,区别只是下一次访问的地址是「下一个」还是「下一行」。按列走时,每次访问几乎都要重新取一个 64 字节的缓存行,实际带宽利用率只有六十四分之一。

顺序访问

用满缓存行,硬件预取器能提前取数据,延迟被掩盖。数组、连续的结构体、按行遍历的矩阵都属于这类。代价是数据布局要配合访问顺序。

随机访问

每次只用一个元素,缓存行其余部分浪费,预取器猜不中,延迟直接暴露。链表、哈希表、按列遍历的大矩阵都属于这类。代价是访问次数乘以 miss 延迟。

伪共享:两个线程写同一行

伪共享是缓存行带来的经典问题。两个线程各自更新一个计数器,两个计数器在内存里相邻,正好落在同一行。线程 A 改了第一个,线程 B 改了第二个,硬件为了保证一致性,要把整行在两个核之间来回传递。两个线程没有共享数据,却在共享缓存行,性能比单线程还差。

修法有两种。一是填充,给每个线程的变量后面补上几十字节,把两个变量推到不同的缓存行;二是分区,每个线程只处理自己那块数据,最后再汇总。第一种费内存,第二种改结构。哪种划算要看变量数量和线程数。

判断伪共享不能只看代码有没有共享变量,要看地址。两个变量地址差多少、是否落在同一行,才决定会不会互相干扰。没有多线程测试条件时,可以用「单线程跑得快、多线程反而更慢」这个现象做初筛,再用性能计数器确认。本机没有做线程对照实验,这一条属于原理说明,未在本机实测。

实际项目里,伪共享往往藏在计数器、统计结构和任务队列里。先用单线程和多线程的耗时对比做初筛,再看地址分布。不要一上来就给所有共享变量填充,先确认是不是它,否则只是徒增内存占用。

出问题时先看哪里

现象真实原因第一步查什么
数组变大后突然变慢工作集超过某一级缓存,命中率断崖式下降固定访问次数,扫描不同工作集大小,找拐点
行列遍历差出好几倍按列走时每步跨一行,缓存行利用率极低确认数组的存储顺序和循环嵌套顺序是否一致
两个线程互相拖慢伪共享,两个变量落在同一缓存行打印变量地址,算地址差是否小于 64 字节
加了预取反而更慢预取的数据没用上,挤占缓存和带宽去掉预取做对照,比较命中率和总耗时
结构体访问比数组慢结构体太大,一个缓存行装不下几个元素看结构体大小和字段顺序,把热字段放前面
同样的数据偶尔快偶尔慢数据跨缓存行,访问被拆成两次或触发两次事务检查结构体大小和对齐,按 64 字节边界分配
miss 后整段代码停顿依赖加载,后续指令都在等这个值看依赖链长度,能否提前加载或改成批量访问
多线程加速比上不去内存带宽或一致性流量成为瓶颈比较单线程和多线程的字节吞吐,不只看耗时
换一种语言后同样的算法变慢对象布局和分配方式破坏了局部性看数据是连续存放还是散落在堆上

边界与代价

缓存不是越大越好。容量增加会带来更大的面积、更高的访问延迟和更多的功耗,命中率提升却未必线性。芯片设计要在容量、延迟、功耗和成本之间取平衡,所以真实产品是分层结构,不是一块巨大的缓存。

预取会浪费带宽。取进来的数据如果没被用上,占总线的份额就是纯损失。在多核共享内存带宽的场景里,一个核的激进预取可能拖慢其他核,这种干扰很难从单线程测试里看出来。

修伪共享要付空间代价。填充几十字节看起来不多,但变量多了、线程多了,内存占用会明显上升;分区则要改数据结构和汇总逻辑,代码复杂度上升。优化之前先确认瓶颈真的是伪共享。

测量受频率和调度影响。同样的代码在不同负载、不同电源策略下结果不同;线程被调度到不同核心,缓存状态也不一样。要把测量做稳,至少固定线程数、重复多次、记录环境。

这篇只讲 CPU 侧的缓存和 miss 代价,不展开 DRAM 的刷新、行缓冲,也不讲 SSD 的页和块。完整的存储层级会在存储方向单独展开,这里先把「离 CPU 越远越慢」这条主线立住。

今天就能验证的五个练习

  1. 把上面的指针追逐程序编译运行,记录五档工作集的纳秒数,找到你自己机器上的拐点。
  2. 把工作集固定为 4MB,把步长从 1 改成 2、4、8、16,观察每次访问耗时怎么变化。
  3. 写一个两线程程序,让两个线程各自累加一个全局变量,先让变量相邻,再在中间填充 64 字节,比较两种版本的耗时。
  4. 在顺序遍历的循环里加一次 __builtin_prefetch,提前几行预取,比较加与不加的耗时。
  5. 查自己 CPU 的缓存规格,把 L1、L2、L3 的容量和文章里的拐点对上,想想为什么 4MB 那档会突然变慢。

五个练习都能在一台普通电脑上完成,不需要特殊硬件。做完你会对「数据放在哪」这件事敏感很多。

小结

缓存按行搬运,x86 上一行 64 字节。命中时快,未命中时要等几十到上百个周期,比例悬殊。空间局部性和时间局部性决定命中率,访问顺序和数据结构决定局部性。伪共享让不相干的变量互相拖累,预取用错了会帮倒忙。

下一篇换一个方向:CPU 一次只能照顾几十个数据流,GPU 一次能照顾几千个。它为什么能同时算几千个像素,又为什么在小任务上反而更慢,下一篇拆开讲。

下一篇:GPU 为什么能同时算几千个像素,从一次矩阵乘法和一百个小任务说起。