阅读经典——《深入理解计算机系统》08
本文将介绍存储器层次结构以及局部性对程序性能的影响。
- 什么是存储器层次结构？
- 局部性
什么是存储器层次结构
这个词大家也许并不陌生，计算机中的存储器从寄存器、缓存到内存、硬盘，形成了一个层次结构。为什么不用单一的一种存储设备，比如只用硬盘呢？因为每一种存储设备都有它的优缺点，硬盘虽然存储空间大，但传输速率太慢，完全跟不上CPU的节奏，直接与CPU交换数据的话会严重拉低CPU的执行效率。而内存虽然容量小一些，但速度比硬盘快的多，因此介于CPU和硬盘之间。随着CPU主频越来越高，CPU与内存的交换效率也变得越来越低，因此现代计算机系统在CPU和内存之间插入多级缓存，以缩小CPU与内存之间的频率差距。
下图为完整的存储器层次结构，从最顶层的寄存器，到最底层的远程存储器（包括分布式文件系统、Web服务器），越往下容量越大、传输速率越慢、单位容量价格越低。
在存储器层次结构中，每一层都作为其下一层的缓存。比如说，当我们想要从L1 cache中读取数据的时候，先检查寄存器中有没有我们需要的数据，如果有，直接从寄存器中读取，如果没有，再从L1 cache中读取。再比如说，当我们想要从硬盘中读取数据的时候，先检查内存中有没有我们需要的数据，如果有，直接从内存中读取，如果没有，再从硬盘中读取。
存储器层次结构的优点在于，作为一个整体，它的容量相当于最底层的存储设备的容量，而它的速度却相当于最顶层存储设备的速度。也就是说，它可以在速度和容量这两个看似矛盾的方面同时达到极限。
为什么？为什么如此神奇？
这是因为程序具有局部性。
局部性
理解局部性对程序开发人员有极大的帮助。一般来讲，有良好局部性的程序比局部性差的程序运行得更快。
局部性有两种：时间局部性和空间局部性。让我们举几个例子来说明吧。
下面的数组元素求和函数就具有良好的时间局部性和空间局部性。
int sumvec(int v[N])
{
int i, sum = 0;
for (i = 0; i < n; i++)
{
sum += v[i];
}
return sum;
}
在该程序中，变量sum在每次循环迭代中被引用一次。如果同一个存储单元在短时间内多次被引用，我们就说该存储单元具有时间局部性。向量v中的元素在循环中按照存储顺序依次被读取，这些被访问的存储单元在空间上离的很近，我们就说它们有良好的空间局部性。
有局部性良好的程序，就有局部性不好的程序。下面的二维数组按列求和就是一个典型的例子。
int sumarraycols(int a[M][N])
{
int i, j, sum = 0;
for (j = 0; j < N; j++)
for (i = 0; i < M; i++)
sum += a[i][j];
return sum;
}
由于二维数组在内存中的存放顺序是按行排放的，因此该程序相当于以N个元素的间隔访问数据，这些存储位置在空间上的距离变大，空间局部性不好。正确的做法应该是外层循环行遍历，内层循环列遍历。
上面举的两个例子都是数据的局部性，除此之外，还有取指令的局部性。因为指令存放在存储器中，CPU读取这些指令也需要考虑局部性。for循环就具有良好的局部性，由于循环体内的指令在存储器中是连续放置的，因此具有良好的空间局部性；又由于循环会执行多次，因此也具有良好的时间局部性。
关注作者或文集《深入理解计算机系统》，第一时间获取最新发布文章。
