1. 存储器的层次结构
CPU Cache、内存和硬盘这些存储设备，其按照上图所示的层次结构组成了计算机存储的层次模型，可以分为如下几个级别：寄存器
寄存器是最靠近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)所示，高速缓存被设计成：
- 有 S=2sS=2^sS=2s 个组；
- 每个组有 EEE 个高速缓存行；
- 每行包括1位有效位，ttt 位标记位，以及 B=2bB=2^bB=2b 字节的数据块组成。
可以得出，高速缓存的大小 C=S∗E∗BC=S*E*BC=S∗E∗B。
而正常内存地址就如同以上的图 b)中所示，其由 ttt 位的标记位，sss 位的组索引位和 bbb 位的块偏移位组成。当假设CPU是 mmm 位的时候，有 t=m−s−bt=m-s-bt=m−s−b。
CPU Cache的读取本质上就是内存地址和Cache结构之间的映射关系。
直接映射
直接映射是每个组只有一行，即 E=1E=1E=1，其读写数据时执行映射的步骤如下：
- 组选择：从地址中抽出 sss 个组索引位，定位到组；
- 行选择：因为直接映射的每个组只有一行，所以可以明确只有这一行：
- 当此行的有效位被设置（=1），且地址中的 ttt 标记和Cache中的标记相匹配，则缓存命中；
- 否则缓存不命中，需要从下一级缓存或者内存中读取对应的内存数据；
- 字选择：根据最后b位偏移量找出所需内存数据的偏移量。
- 行替换：在缓存不命中的情形下，需要从存储器的下一级中取出块，替代现有的行，由于直接映射每个组只有一个行，所以替换的策略很简单，就是将当前行替换掉。
直接映射的优点是硬件简单，成本低，地址变换简单，而且不涉及替换算法问题，但是这种方式可能会存在对于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∗BC=S*E*BC=S∗E∗B，当 E=1E=1E=1 的时候，是直接映射；而当 1<E<C/B1<E<C/B1<E<C/B 时，即组的数目大于1，且每组都有至少2行的情况时，称为组相联高速缓存。
和直接映射的区别有：
- 组相联高速缓存中的行选择时需要遍历组中所有的行以比较标记 ttt；
- 在缓存不命中时的行替换需要选择某些行进行替换，选择的策略有
最不常使用（Least-Frequently-Used, LFU）策略和最近最少使用（Least-Recently-Used, LRU）策略。但是可以避免直接映射性能抖动的问题。
全相联映射
全相联映射是只含有一个组，这个组包含所有的高速缓存的行，即 E=C/BE=C/BE=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）。
从局部性分析：
- 时间局部性：两个函数对于
sum这个局部变量的反复引用是好的，因为编译器能够将他们缓存在寄存器文件中； - 空间局部性：
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 );
