《深入理解计算机系统》Part1 06：存储器层次结构

摘要：这一章主要介绍了存储器的层次结构，以及如何写出存储器友好的代码。
关键词：局部性；存储器体层次结构；高速缓存
目录：
  1. 什么是程序的时间局部性和空间局部性
  2. 存储器层次结构
  3. 编写高速缓存友好的代码

1. 什么是程序的时间局部性和空间局部性

时间局部性只指，对于某个数据，他被使用的时间在时间轴上的分布是集中的而不是分散的，也就意味着，程序对他的调用是集中在某个时间段内的。程序的空间局部性则是指，对于某个时段，程序调用的数据在地址空间内的分布是集中的而不是分散的，也就意味着，程序该段时间内，程序调用的数据分布比较集中。

后面我们将看到编写高速缓存友好的代码就是编写局部性好的代码

2.存储器层次结构

存储器在计算机内是有层次，就像一个金字塔，塔顶的存储器速度极高，但容量很小，越往下，速度越慢，但容量越大。为什么要使用这种层次结构呢？因为这一种方案既经济又能达到不错性能的方案。

存储器层次结构 读的过程就是底层的数据向上传递的过程，而写的过程就是上层的数据向下传递的过程。读数据的时候，上层的存储器向下层的存储器要，如果下层的有，那么就命中了，没有的话下层再向下层要，这样不断的进行下去，命中率越高效率肯定就越高，因为下层就不要再不断的递归往下取数据了。写数据的时候稍微复杂，比如从一层写到下一层的时候，他不是立刻写到一下层的，他是当该层有新的数据要从下一层进来的时候，他正好把要写的数据写到下层空出位置给新的数据进来，这就是写回。

3.编写缓存友好的代码

什么是缓存友好的代码，就是缓存命中率高的代码，那么怎么使缓存命中率高呢？增强代码的局部性。为什么？
数据在存储器中的传递是以块进行的，只不过每个相邻的存储器之间块的大小可能不一样。当你的代码局部性好的时候，你在某一段时间内，频繁的访问同一个变量那肯定命中率很高，如果你某一时段，频繁的访问一些空间上很近的数据，那命中率也很高，因为那些数据随着块都一起运到了缓存中。其实之间操作系统对数据类型的对齐就是操作系统所做的缓存友好的措施。

编写缓存友好的代码，看起来好像很麻烦，需要你理解底层的缓存是如何存储数据的等一些底层的知识。但其实有个简单方法，就是你只要确保你代码的局部性就好了。时间局部性好说，空间局部性也好说，你只要保证你最近使用的这些数据都在空间内都是连续分布的。比如一个循环中使用的这些数据都是连续的。比如两个矩阵相乘，你知道矩阵可以用二维数组表示，他们是按照列存储的，那么如果你是按照列的顺序去计算，肯定就是局部性好了。因为第一行的元素在存储器中是分散的，但第一列的元素是连续的。你矩阵的第一个元素时，缓存里已经顺带把第一列的前几个元素都取来了，因为都在一个块里，如果你第二元素用的同一行的，那又得重新去取，所以这样的代码就不具有空间局部性。

总结这两章来说，在底层做优化时，主要是要充分利用指令流水线和缓存友好。