CPU—CPU Cache：如何写出让CPU跑的更快的代码

1. 存储器的层次结构

现代计算机上都用到了CPU Cache、内存和硬盘这些存储设备，其按照上图所示的层次结构组成了计算机存储的层次模型，可以分为如下几个级别：

• 寄存器
• CPU Cache：
  1. L1 Cache
  2. L2 Cache
  3. L3 Cache
• 内存
• SSD/HDD硬盘

寄存器

寄存器是最靠近CPU的控制单元和罗技计算单元的存储器，其使用的材料速度是最快的，一般能在半个时钟周期内完成读写。

伴随最快的速度，其价格自然也是最贵的，所以数量不是很多，一般而言CPU中的寄存器数量大概在几十到几百之间，每个寄存器可以存储一定的字节（byte）的数据，比如：

• 32位CPU中的大多数寄存器可以存储4个字节；
• 64位CPU中的大多数寄存器可以存储8个字节。

CPU Cache

CPU Cache使用的材料是SRAM（随机静态存储器），SRAM之所以叫“静电”存储器，是因为只要有电，数据就可以保持存在，不用像DRAM一样需要每隔一段时间充电刷新一次。但是断电后，其数据还是会丢失，这点和磁盘有本质区别。

在SRAM里面，一个bit的数据，通常需要6个晶体管，所以SRAM的存储密度不高，同样的物理空间下，能存储的数据是有限的，不过也因为其电路简单，所以访问速度非常快，因此用来做CPU Cache再合适不过了。

CPU的高速缓存，通常可以分为L1、L2和L3三级缓存，也称为一级缓存、二级缓存和三级缓存。

L1 Cache

L1高速缓存的访问速度大概只需要2-4个时钟周期，而大小在几十KB到几百KB不等。每个CPU核心都有一块属于自己的L1高速缓存，且指令和数据的缓存是分开的，故而L1高速缓存分为数据缓存和指令缓存。

在Linux系统中，我们查看某个CPU中L1数据缓存的容量大小，可以看到，我的服务器上L1数据缓存大小是32K：

$ cat /sys/devices/system/cpu/cpu0/cache/index0/size

32K

查看某个CPU中L1指令缓存的容量大小：

$ cat /sys/devices/system/cpu/cpu0/cache/index1/size
32K

L2 Cache

L2高速缓存同样是每个CPU核心都有，但是其相对于L1高速缓存距离CPU核心更远，容量更大，通常在几百KB到几MB之间，访问速度则更慢，速度在10-20个时钟周期。

在Linux系统中，我们可以通过以下指令查看L2高速缓存的大小：

$ cat /sys/devices/system/cpu/cpu0/cache/index2/size

256K

L3 Cache

L3高速缓存通常是多个CPU核心共用的，位置比L2高速缓存距离CPU核心更远，大小也会更大，通常在几MB到几十MB不等。访问速度也更慢一些，大概在20-60个时钟周期。

在Linux系统中，我们可以通过以下指令查看L3高速缓存的大小：

$ cat /sys/devices/system/cpu/cpu0/cache/index3/size

25600K

内存

内存一般使用DRAM作为芯片，相比于SRAM，其密度更高，功耗更低，有更大的容量，而且造价比SRAM便宜很多。

DRAM存储一个bit数据，只需要一个晶体管和一个电容就能存储，但是因为数据会被存储在电容里，电容会不断漏电，所以需要「定时刷新」电容，才能保证数据不会被丢失，这就是DRAM之所以被称为「动态」存储器的原因，只有不断刷新，数据才能被存储起来。

DRAM的数据访问电路和刷新电路都比SRAM更复杂，所以访问的速度会更慢，内存速度大概在200~300个 时钟周期之间。

硬盘

SSD（*Solid-state disk*）就是我们常说的固体硬盘，结构和内存类似，但是它相比内存的优点是断电后数据还是存在的，而内存、寄存器、高速缓存断电后数据都会丢失。内存的读写速度比SSD大概快 10~1000 倍。

当然，还有一款传统的硬盘，也就是机械硬盘（Hard Disk Drive, HDD），它是通过物理读写的方式来访问数据的，因此它访问速度是非常慢的，它的速度比内存慢 10W 倍左右。

2. CPU Cache的数据结构和读取

我们先了解一下CPU Cache的结构，其由很多个Cache Line组成，Cache Line是CPU从内存中读取数据的基本单位，一次读取大小即为Cache Line的大小。在Linux系统中，我们可以使用如下命令查看L1 Cache Line的大小，即L1 Cache一次载入数据的大小是64字节。

$ cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size
64

通用的高速缓存存储器的组织结构

高速缓存的存储器如下图 a)所示，高速缓存被设计成：

1. 有 $S=2^s$ 个组；
2. 每个组有 $E$ 个高速缓存行；
3. 每行包括1位有效位，$t$ 位标记位，以及 $B=2^b$ 字节的数据块组成。

可以得出，高速缓存的大小 $C=S*E*B$。

而正常内存地址就如同以上的图 b)中所示，其由 $t$ 位的标记位，$s$ 位的组索引位和 $b$ 位的块偏移位组成。当假设CPU是 $m$ 位的时候，有 $t=m-s-b$。

CPU Cache的读取本质上就是内存地址和Cache结构之间的映射关系。

直接映射

直接映射是每个组只有一行，即 $E=1$，其读写数据时执行映射的步骤如下：

1. 组选择：从地址中抽出 $s$ 个组索引位，定位到组；
2. 行选择：因为直接映射的每个组只有一行，所以可以明确只有这一行：
   1. 当此行的有效位被设置（=1），且地址中的 $t$ 标记和Cache中的标记相匹配，则缓存命中；
   2. 否则缓存不命中，需要从下一级缓存或者内存中读取对应的内存数据；
3. 字选择：根据最后b位偏移量找出所需内存数据的偏移量。
4. 行替换：在缓存不命中的情形下，需要从存储器的下一级中取出块，替代现有的行，由于直接映射每个组只有一个行，所以替换的策略很简单，就是将当前行替换掉。

直接映射的优点是硬件简单，成本低，地址变换简单，而且不涉及替换算法问题，但是这种方式可能会存在对于Cache空间利用不充分而带来的性能抖动的问题，在《CSAPP》这本书中就有一个很好的例子来阐述这个问题。

如下的一个函数：

float dotprod(float x[8], float y[8])
{
    float sum = 0.0;
    int i;
    for(i=0; i<8; i++){
        sum += x[i] * y[i];
    }
    return sum;
}

我们假设浮点数是4个字节大小，x被夹在到从地址0-32字节连续内存中，y紧随其后，从32-64字节。假设一个Cache块是16字节，足够容纳4个浮点数，那么就会出现如下的缓存组对应：

元素	地址	组索引	元素	地址	组索引
x[0]	0	0	y[0]	32	0
x[1]	4	0	y[1]	36	0
x[2]	8	0	y[2]	40	0
x[3]	12	0	y[3]	44	0
x[4]	16	1	y[4]	48	1
x[5]	20	1	y[5]	52	1
x[6]	24	1	y[6]	56	1
x[7]	28	1	y[7]	60	1

在运行时：

• 循环第一次引用x[0]，缓存不命中，导致x[0]-x[3]被加载到Cache组0；
• 接下来对y[0]的引用，再次缓存不命中，导致y[0]-y[3]被加载到Cache组0，覆盖了前一次的x[0]-x[3]；
• 下一次迭代中，再次缓存不命中，加载x[0]-x[3]，如此往复，导致性能极低。

组相联映射

前面我们说过，高速缓存的大小 $C=S*E*B$，当 $E=1$ 的时候，是直接映射；而当 $1<E<C/B$ 时，即组的数目大于1，且每组都有至少2行的情况时，称为组相联高速缓存。

和直接映射的区别有：

• 组相联高速缓存中的行选择时需要遍历组中所有的行以比较标记 $t$；
• 在缓存不命中时的行替换需要选择某些行进行替换，选择的策略有最不常使用（Least-Frequently-Used, LFU）策略和最近最少使用（Least-Recently-Used, LRU）策略。但是可以避免直接映射性能抖动的问题。

全相联映射

全相联映射是只含有一个组，这个组包含所有的高速缓存的行，即 $E=C/B$。因为只有一个组，所以地址中不包含组索引位。

因为全相联映射必须并行的搜索许多相匹配的标记，构建一个又大又快的相联高速缓存很困难，而且很昂贵。因此，全相联高速缓存只适合做小的高速缓存，比如虚拟内存系统中的翻译备用缓冲器（TLB）。

实际应用

使用以下命令可以查看Linux机器上的Cache的映射方式：

L1 数据缓存，可以看到，该机器的CPU的L1数据Cache是8路相联的高速缓存：

$ cat /sys/devices/system/cpu/cpu0/cache/index0/size

32K # 缓存大小，即上述的 C
$ cat /sys/devices/system/cpu/cpu0/cache/index0/number_of_sets
64  # 缓存的组数，即上述的 S
$ cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size
64  # 缓存的行大小，即上述的 B
$ cat /sys/devices/system/cpu/cpu0/cache/index0/ways_of_associativity
8   # 组的行数，即上述的 E

L2，也是个8路相联的高速缓存：

$ cat /sys/devices/system/cpu/cpu0/cache/index2/size

256K

$ cat /sys/devices/system/cpu/cpu0/cache/index2/number_of_sets
512
$ cat /sys/devices/system/cpu/cpu0/cache/index2/coherency_line_size
64

$ cat /sys/devices/system/cpu/cpu0/cache/index2/ways_of_associativity
8

L3，是一个20路相联的高速缓存：

$ cat /sys/devices/system/cpu/cpu0/cache/index3/size

25600K

$ cat /sys/devices/system/cpu/cpu0/cache/index3/number_of_sets
20480
$ cat /sys/devices/system/cpu/cpu0/cache/index3/coherency_line_size
64

$ cat /sys/devices/system/cpu/cpu0/cache/index3/ways_of_associativity
20

Tip

Q：为什么用中间位作为高速缓存的组索引？

如果用最高位做索引

情况如上图中的中间所示，连续的块都别映射到了同一个组中（特别的，如果是直接映射高速缓存，连续的块被映射到同一行中）这样的确也能利用缓 存，如上图所示，当引用第一个元素的时候，会把第1、2、3、4个拷贝到缓存的组0中，以后对2、3、4的引用就能直接在缓存中提取。引用第5个元素的时 候，把第5、6、7、8个拷贝到缓存的组1中，同样的，对4、5、6的引用能直接在缓存中提取。后面的情况类似就不再叙述。 

通过上面的叙述，你可能已经发现一个问题：当对缓存的组1进行操作的时候，缓存中的其它组是没有被利用的，这和缓存中只有一个组其实效果是一样的。对缓存中的其他组没有很好的利用，也就是说，虽然也有缓存的利用，但有最大化。

改用中间位做索引，如上图中的右图所示，同一组中的块不再是连续的，这样可以保证缓存中的所有组都能被有效的利用。

引用第1个元素的时候，将把第1、5、9、13放入缓存组1中

引用第2个元素的时候， 把第2、6、10、14放入缓存

引用第3个，把3、7、11、15放入缓存

引用第4个，把4、8、12、16放入缓存

这样对前四个元素的引用都不会命中，而而对后面的引用都能命中。这种过程也就是所谓的缓存预热。

3. 如何写出让CPU跑的更快的代码

3.1 局部性原理

一个编写良好的计算机程序常常具有良好的局部性(locality)，即，它们倾向于引用邻近于其他引用过的数据项的数据项，或者最近引用过的数据项本身，这种倾向性，被称为局部性原理。一般而言，有良好局部性的程序比局部性差的程序运行的更快。

局部性通常有两种不同的形式：

• 时间局部性：被引用一次的内存位置很可能在不远的将来再被多次引用；
• 空间局部性：一个内存位置被引用了一次，那么程序很可能在不远的将来引用附近一个内存位置。

3.1 如何写出让CPU跑得更快的代码

由于CPU访问Cache的速度比访问内存的速度要快100多倍，所以编写缓存命中率更高的程序可以有效提升程序性能，同时这也是代码局部性良好的体现。

所以，如何让CPU跑得更快，本质上是让代码的缓存命中率更好，即有良好的局部性。

3.2 提升数据缓存命中率

const int N = 64;

int sum1(int a[N][N]) {
    int i, j, sum = 0;


    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++)
            sum += a[i][j];

    return sum;
}

int sum2(int a[N][N]) {
    int i, j, sum = 0;

    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++)
            sum += a[j][i];

    return sum;
}

如上的代码，sum1和sum2函数的效果是一致的，但是因为二维数组所占用的内存是连续的，所以sum1的局部性比sum2要好，其缓存命中率也更高（当然在现在的大存储器上可能体现不出差距，可以增大N）。

从局部性分析：

1. 时间局部性：两个函数对于sum这个局部变量的反复引用是好的，因为编译器能够将他们缓存在寄存器文件中；
2. 空间局部性：sum1函数内循环对于内存的每次引用是步长为1的引用，这在空间上的局部性是好的。

其实可以总结如下：

• 将注意力集中在内循环上，大部分计算和内存访问都发生在这里；特别地，以步长为1来读数据，从而使程序的空间局部性最大；
• 一旦从存储器中读入了一个数据对象，尽可能多地使用它，从而使得程序中的时间局部性最大。

3.3 提升指令缓存的命中率

void foo() {
    int i, array[N];
    for (i = 0; i < N; i++)
        array[i] = rand() % 100;


    // 操作一：数组遍历
    for (i = 0; i < N; i++)
        if (array[i] < 50)
            handle(array[i]);
    
    // 操作二：排序
    sort(array, array+N)
}

比如以上函数，主要是对一个随机数组进行两种操作，第一种是数组遍历，第二种是排序，假设二者没有什么相关性，那么操作一和操作二的先后顺序对代码运行速度有影响么？

在回答这个问题之前，我们先了解 CPU 的分支预测器。对于 if 条件语句，意味着此时至少可以选择跳转到两段不同的指令执行，也就是 if 还是 else 中的指令。那么，如果分支预测可以预测到接下来要执行 if 里的指令，还是 else 指令的话，就可以「提前」把这些指令放在指令缓存中，这样 CPU 可以直接从 Cache 读取到指令，于是执行速度就会很快。

当数组中的元素是随机的，分支预测就无法有效工作，而当数组元素都是是顺序的，分支预测器会动态地根据历史命中数据对未来进行预测，这样命中率就会很高。

因此，先排序再遍历的速度会更快！

比如，C/C++的编译器就提供了likely和unlikely的两种宏，如果true的概率比较大，那么使用likely，反之使用unlikely。

#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)

if (likely(array[i] < 50)) {
    // do something
} else {
    // do something
}

实际上，CPU自身的动态分支预测已经比较准了，只有当确信CPU预测不准时才会使用这两个宏。那么作为码农，我们最重要的就是在循环体中写出有规律的分支判断语句，帮助CPU预测正确，提升代码性能。

3.4 提升多核CPU的缓存命中率

多核CPU上，线程可能在不同线程之间来回切换执行，这对CPU Cache是不利的，虽然L3 Cache是多核共享的，但是L1和L2却是核心独有的，线程的切换必然会降低缓存的命中率。

所以Linux提供了sched_setaffinity方法，实现将线程绑定到某个CPU核心这一功能，从而提升缓存的命中率。

int sched_setaffinity(pid_t pid , size_t cpusetsize ,
                             const cpu_set_t * mask ); 

4. 参考文献

《CSAPP》

对缓存的思考【续】——编写高速缓存友好代码

2.3 如何写出让 CPU 跑得更快的代码？

CSAPP 第六章 存储器层次结构（二）局部性和缓存系统