CPU Caches and Why You Care

本文最后更新于：2023年12月17日下午

前言

最近阅读到几篇有关 CPU caches 和 false sharing 的文章，特别是 CPU Caches and Why You Care ^[1] ，感觉收获颇丰，对 CPU 缓存有了进一步的了解，所以特此记录下来，下面也给出了对应的PPT链接和演讲视频链接，推荐阅读和观看。同时，又再次接触了Cache的关联映射，大学里学习机组时的记忆从脑海里开始浮现，但我好像已经把知识点都还给老师了，所以借此机会，重新回顾温习一番。

PPT 链接、演进视频

CPU Caches and Why You Care

经典问题引入

行遍历 or 列遍历

先来看如下代码（左图），函数功能就是对一个矩阵里的元素进行求和，但有两种不同的遍历方式，行遍历和列遍历，右图展示了在 GCC 和 MSVC 环境下行遍历（RW）和列遍历（CM）的遍历时间，可以看到列遍历是明显快于行遍历的，这也是我们平常在遍历二维数组时最常用的方式。那么背后的原因就在于 CPU Cache，因为 cache line 的存在，CPU 每次都会从内存读取一段连续的数据到缓存中，因此在进行列遍历时，下一个访问的数据已经在缓存中，而不需要去内存读取。

两段 Loop 代码

再来看看下面这个代码示例^[2]，两个循环的差异就在于循环的步长不同，Loop 1步长为1，Loop 2步长为16，不难得到 Loop 2的工作量为 Loop 1 的 6% 左右，但是实际测试中发现，Loop 2 的耗时是 Loop 1 的 70%~80% 左右，这样的结果是反直觉的。

vector<int> arr(64 * 1024 * 1024, 0);
// Loop 1
for (int i = 0; i < arr.size(); i++) arr[i] *= 3;

// Loop 2
for (int i = 0; i < arr.size(); i+=16) arr[i] *= 3;

事实上，上述两段代码的运行耗时主要不在于乘法计算，而在于对数组元素的读取，也就是和内存访问相关。因为 CPU Cache Line 的关系（后面会进一步介绍，这里简单来说，就是 CPU 访问内存不是一个字节为单位，而是一个 chunk 大小为单位，目前一般为 64 字节），而 Loop 2 的步长为 16 * 4（int字节数），恰好每次递增都会跳过一个 Cache Line，所以 Loop 2 和 Loop 1 在内存访问上的耗时是接近的。

指令级并行

下面这段代码示例同样来自 Gallery of Processor Cache Effects ，尽管看上去两个循环做的工作量是一样的，但在上述文章中作者指出，Loop 2的执行速度要比 Loop 1 快了两倍，我在 quick_bench 上做了下类似的测试（需要关闭优化，不然编译器可能直接把整个循环都优化掉了），结果也表明 Loop 2 要比 Loop 1 快1.6倍左右。

int steps = 256 * 1024 * 1024;
int* a = new int[2];

// Loop 1
for (int i=0; i<steps; i++) { a[0]++; a[0]++; }

// Loop 2
for (int i=0; i<steps; i++) { a[0]++; a[1]++; }

测试结果

如何解释这一现象呢？

实际上对于 Loop 1来说，它的工作流如下图所示，两个 a[0]++ 的操作是相互依赖的。

Loop 1 workflow

而对于 Loop 2 来说，它的工作流如下图所示， a[0]++ 与 a[1]++是可以并行的，而 L1 cache 也支持同时去访问不同的内存单元，做并行的优化。感觉这里其实跟指令流水的概念也很相近。

Loop 2 workflow

CPU Caches

上一小节中，列举了几段代码例子，来说明 CPU Caches 的存在以及它的重要性，在该小节中，会进一步介绍 CPU Caches 的缓存结构以及 Cache 的相关知识。

L1,L2,L3 缓存结构

介绍 CPU 缓存结构前，先简单了解下计算机金字塔型的存储结构。现代计算机的体系结构，在性能、成本和制造工艺方面做出取舍，从而达到一个平衡。下图是计算机存储结构的示例图，可以看出，访问速度越快一般容量越小，相应的速度越快，成本也会提高。

计算机存储结构

而由于CPU与内存之间存在较大的性能差距，因此引入了 CPU Cache。CPU Cache 通常分为大小不等的三级缓存，分别是 L1 Cache，L2 Cache，L3 Cache，其中 L1 Cache 通常分为数据缓存和指令缓存，即数据和指令时分开存储的；L1 Cache 和 L2 Cache 都是每个 CPU core 独有的，而 L3 Cache 是多个 CPU core 共享的，其层级关系如下图所示：

CPU Cache 层级关系（来自小林coding）

以 Intel Core i7-9xx 处理器为例，该 CPU 每个 core 有32KB的 L1 I-cache 和 32KB的 L1 D-cache，256KB 的 L2 cache，4 个 cores 共享一个 8MB 的 L3 cache。

Cache line

引入CPU cache之后，CPU访问某块地址时，会首先检查L1 Cache，如果不存在，则会检查L2 cache，然后是L3 Cache、内存。如果CPU直接命中cache，则不需要再去访问内存，如果没有命中cache，则需要找到之后会把内存中的数据映射到cache中，内存映射到到cache的传输的最小单位就是 cache line。现代CPU cache line大小一般是64或者128字节，也就是说就算CPU只读取一个字节，也会把这个字节所在的内存段里64字节全部映射到cache中。这主要是根据局部性原理，访问到一个地址时，这个地址附近的内容近期也很大概率被访问到。^[3]

Cache Coherence

现代 CPU 都是多核的，由于 L1/L2 Cache 是多个核心各自独有的，那么会带来多核心的缓存一致性（Cache Coherence） 的问题，如果不能保证缓存一致性的问题，就可能造成结果错误^[4]。

有关CPU 缓存一致性的有关问题，小林coding - CPU 缓存一致性这篇文章解释得很详细了，大家可以直接移步阅读，这里不再做进一步展开。

设想一下，两个不同的变量被两个线程（运行在不同的 core 上）使用，看起来这完全是可以并行的，因为两个线程之间用的是互相独立的数据。然后，如果这两个变量落在同一个 cache line 上的话，并且至少有一个线程进行写操作，那么就会存在 cache line 的竞争（Cache coherence 缓存一致性），这个现象被称作是 false sharing。

之所以称作是 false sharing，是因为尽管不同线程之间没有共享数据，但是无意中共享了 cache line。

接下来用两段代码来进一步说明 false sharing。

下方的左图代码，其含义是为了实现对一个矩阵元素求和的功能，使用线程池来并发求和，对应线程数量大小为P，每个线程都会分配一定数量的行，各个线程都会把求和结果放在 result 数组中，最终进行一个求和。

右图则展示了线程数量与单线程执行效率对比关系，可以看到当线程数小于15时，虽然线程数增加了但程序的执行效率反而低于单线程，线程数在20-25区间也是有一个递减的趋势，且效率远低于预期。

导致上述现象的根因就是 false sharing：对于数组 `result[P]`，它的多个 int 数组元素都处在同一个 cache line 上，而在上述代码中，线程池里遍历矩阵元素求和时，都是在对`result[P]`中元素进行修改写入，从而导致多个线程之间对同一个 cache line 产生竞争关系，当一个线程在写入时，其他线程 cache 里的变量已经失效了，必须要重新从内存中读取，因此写线程也需要将写入cache 的值再写回内存。这样一来，由于缓存一致性的问题，导致原先能够并行的多个线程反而像是串行执行，再加上线程切换的开销，因此执行效率自然是大大下降。

知道根因后，也就自然想到对应的解决办法，如下左图代码所示，在每个线程中引入一个局部变量 count，在遍历矩阵时都先累加在该变量上，求和完之后再一次地赋值给 result[P]，因此每个线程的局部变量都在不同的线程栈上，是不会处于同一个 cache line 上，因此也就没有缓存一致性和 false sharing 的问题了。最后程序的性能表现如下右图所示，可以看到，达到了一个预期的线性增长的效果。

关于 False Sharing ，还可以再看看这篇文章 Concurrency Hazards: False Sharing ^[5]，其中也给出了一个详细具体的例子来解释 false sharing。

总结与建议

最后也是翻译下PPT里的总结和建议。

总结

小就是快，快就是小，在硬件层面上没有时间/空间的权衡；
关注 locality 局部性
可预测的访问模式，构建对缓存预取友好的程序

建议

对于数据
- 在实际中，尽可能使用数组遍历
- 充分利用 cache line，提高利用率
  - 当看到数据结构中有布尔值时，这可能是存在问题的，对于 64位的 cache line 可能就只使用了其中 1 位
- 警惕 false sharing
对于 代码/指令
- 适合缓存的工作集：避免在异构序列上进行迭代调用虚函数
  - 例如从一个基类派生出三个子类 A,B,C，然后有程序了有一个基类指针容器，指向不同类型的子类，当遍历这个容器取调用虚函数 Process 时，第一个对象类型为A，假如此时A对应的Process函数指令不在缓存中，那么就从主存里读取到缓存，然后执行；接着第二个对象类型为B，同样又需要把B的Process函数指令从主存读取到缓存；接着第三个对象类型为C，也需要把C的Process函数指令读取到缓存中，当时如果此时缓存已经满了，那么就会发生替换，很可能就把A之前的缓存的指令替换了。那么以此类推，以A，B，C的顺序访问，那么就会一直发生从主存读取到缓存的操作。一个可行的解决思路就是，按对象类型排好序，先遍历所有 A 对象，再是B，最后是C。
- 构造 “fast paths”，无分支序列：提前检查所有通常不常见的奇怪情况
- 谨慎使用内联函数
  - 好处在于可以减少分支（函数调用算是分支，可能会产生缓存miss），对编译器来说也便于产生其他类型的优化，来产生更小的代码
  - 坏处在于缓存中可能会有多份相同代码指令的拷贝，会减小有效缓存的大小
- 利用好一些工具 PGO 和 WPO
  - PGO（profile guided optimization）工具在编译过程中收集程序运行时的数据,然后利用这些数据对程序进行针对性的优化
  - WPO（whole program optimization）全局程序优化

机组知识回顾：Cache映射

Cache映射图解

上图来自B站视频帮你把Cache映射梳理清楚! | 图解cache映射 ^[6]，感觉讲得比较清晰透彻，可以移步观看，这里再做简单地文字版介绍，提炼下关键点。

引入 Cache 的原因主要为了减小 CPU 和主存之间的性能差距，这在前面计算机的存储结构部分也有提及。
Cache 和主存间的数据交换以 cache行（cache line / cache 块）为单位，一个cache line里包含有多个地址（暂且用物理地址表示），而这里一个地址的长度（一个地址对应的数据大小，几个bits），如果是按字节编址，则一个地址代表一字节，如果按字编址，字的大小为4字节的话，则一个地址代表4字节。
Cache 中每个 cache 行还对应有标记项，包括有效位、脏位、tag （跟地址映射相关）。
Cache 和主存之间有三种地址映射方式，且聚焦的是两边块号的对应关系（而不是一个地址到另一个地址）。
对于一个主存物理地址，可以划分成两部分来看，块号和块内地址，块内地址可通过一个块多大和按什么编址来确定
- 全相联映射：多对多映射，主存中的任意一块都可以映射到 Cache 中的任意一行。因此物理地址中除了块内地址部分，其余位都作为 tag 放入 Cache 的标记项，查询 Cache 时需要遍历所有的 cache 行来确定是否在缓存中^[7]
  - 优点：机制灵活，命中率高
  - 缺点：比较电路难于设计和实现，只适合小容量的 Cache
- 直接映射：一对一映射，主存的某一块一定映射到 Cache 中的某一行
  - 优点：映射方式简单，易实现
  - 缺点：机制不灵活，Cache 命中率低（多个内存块会映射到 Cache 的同一行，容易发生冲突，替换）
- 组相联映射：结合全相联映射和直接映射的方式，对 Cache 里的 cache line 进行分组，每组有 2^r 个 cache line（r=1,2,3 即2路，4路，8路），即主存中的每个 cache 块都会映射到 Cache 的固定的一个组中，但在组内又可以随机映射到其中一个 cache line。
  - 这样设计，增加了映射的灵活性，主存中的一块可以映射到Cache中的2^r 块，提供命中率，而每次比较时也只需要进行2^r 路比较，硬件开销小。