C 高速缓存
在古代，是没有高速缓存的说法的，cpu直接和内存通信。后来cpu越来越快，内存却跟不上cpu的速度了，于是人们设计了高速缓存。高速缓存离cpu更近，也就有了比内存更快的速度，然而高速缓存比较昂贵，因此空间非常有限。
现代的cpu一般有多级缓存，一级缓存比二级缓存快但比二级缓存小，二级缓存比三级缓存快但比三级缓存小，这样。这里按照最简单和原始的情况，也就是只有一级缓存的情况来描述缓存的性质。
对于程序来说，缓存是“透明”的，也就是说程序是感受不到缓存的存在的，所有的内存访问看起来都像是直接访问了内存。这种特性使得编程变得很容易，但是如果要针对缓存使用进行优化则变得比较困难。
C.1 局部性原理
局部性原理有两种形式：时间局部性和空间局部性。
时间局部性：一个程序具有良好的时间局部性的话，被引用过一次的存储器位置很有可能在不久的将来再次被引用。
空间局部性：一个程序具有良好的空间局部性的话，被引用过一次的存储器位置附近的位置很有可能在不久的将来被引用。
具有良好局部性的程序可以最大程度地利用缓存的特性。局部性原理和高速缓存好像有点像鸡和蛋的关系。
C.2 缓存的组态
缓存是分成许多组的，每一组又包含一些行，每一个行有一个由若干字节组成的块。每个行里还包含一个标记。
假设我们的缓存一共有\(S=2^s\)组（组的数目一定是2的某次方），每个组有\(E\)行，每一行包含\(B=2^b\)字节（B也一定是2的某次方）。然后设计算机的所能给出的地址共M位（比如在32位系统里\(M=32\)），一条地址就按照下图分成三部分
图 C.1: 内存地址和缓存的对应
每次访问一个地址的时候，cpu会根据地址的组索引部分去找缓存中相应的组，然后将标记部分和组里每一行的标记做对比，如果一致那么将直接读取缓存中的数据，避免访问内存。如果这一组所有的行的标记都与地址的标记不同，将会从这一组中消去一行，然后把目标内存缓存进来。（每次会缓存\(2^b\)字节。也就是这一组标志和索引对应的所有内存内容）。
注意到偏移量是\(b\)，而缓存的每一行中有\(2^b\)个字节，cpu会根据这个偏移量去缓存中找对应的字节。
关于缓存不命中的时候到底要消去缓存组中的哪一行，有各种不同的设计，比如随机消去一行，或者把最后一次使用时间最远的消去，或者把访问量最小的一行消去等等。
C.3 缓存优化
举个例子，在操作比较大的矩阵的时候，假设矩阵是按照行存储的（\(address = col + row \times max\_col\)），那么按照先行后列的方式访问可能会获得更快的速度。
在某些情况下，如果更加精细地设计一些，也许可以在每一行后面增加一些无意义的字节，来提高缓存命中的概率（比如需要交替访问多行，使得访问后面的行的时候不要消除前面行的缓存内容）。
C.4 如何查看cpu的缓存组态
- 查看L1缓存有多少组：
上面cpu0表示第一个cpu，服务器上/sys/devices/system/cpu/下会有96个cpu。不要担心，它们的缓存参数是一致的。index0表示该cpu里面的第一个缓存。经实验，index0和index1是一级缓存，分别是数据和指令缓存；index2是二级缓存；index3是三级缓存。二级和三级缓存都是部分数据/指令的。
- 查看每一组有多少行：
- 查看每一行有多少字节：
- 查看缓存的大小
其实也可以算出来。上面每一行字节数乘以每一组行数再乘以组数即可。
- 其他信息也都在同意目录下，可以自行探索一下。
C.5 感受一下缓存不命中
还是请回我们的muladd程序。据查，我们的cpu的一级数据缓存每一行有64个字节。已知每个double占8个字节，也就是说我们的一行缓存最多可以缓存8个双精度浮点数（如果它们在内存里是对齐到8字节的话（一般来说的确是这么对齐的））。这回我们每次跳跃地进行计算，每次加8，来尝试使得缓存无法命中：
__attribute__ ((noinline))
void muladd(double* a, double* b, double* c, double* d,
unsigned long long N){
unsigned long long i,j;
for(i = 0; i < 8; i++){
for(j = i; j < N; j+=8){
d[j] = a[j] * b[j] + c[j];
}
}
}根据上一节的命令，我们查到CPU的一级缓存是32kB，也就是说最多可以存储4096个double，所以无论如何，这些数字是不可能全部缓存起来的。（这也是最开始为什么选择了8192作为数组维度）。
显然，这个函数也是一样对每组a[i]，b[i]，c[i]进行一次计算。编译并运行，可以发现原来耗时约20s的程序，现在需要30s。
二级缓存和三级缓存相对空间要大一些，而且是数据和指令共用的，一般就不对它们进行优化了（吧？）。