存储器的层次结构

编写程序的时候，性能优化的瓶颈不是往往不是在与计算量，而是I/O时间的开销。要能够更好的优化程序，就必须得了解一些存储器层次知识。

我们编写程序，直接打交道的存储器就是寄存器和内存，有时还会加上硬盘。但其实，在计算机内部，缓存的作用也是不容小视的。内部计算机中的存储器容量越大，单位成本越便宜，但是相应的速度也就越慢，一台现代计算机拥有的存储器从CPU访问的速度由快到慢排序大致有以下几个部分：寄存器、CPU中的L1L2L3缓存（SRAM）、内存（DRAM）、固态硬盘、机械硬盘。在硬盘内部为了提升速度，也带有一定大小的缓存。可见，缓存无处不在，我们只有利用好缓存，才能够有效缩短I/O时间。

考虑这两个不同计算二维数组元素和的函数：

long long sum1(int m, int n, int array[m][n])
{
  long long ret = 0;
  for (int i = 0;i < m;i++)
  {
    for (int j = 0;j < n;j++)
    {
      ret += array[i][j];
    }
  }
  return ret;
}
long long sum2(int m, int n, int array[m][n])
{
  long long ret = 0;
  for (int j = 0;j < n;j++)
  {
    for (int i = 0;i < m;i++)
    {
      ret += array[i][j];
    }
  }
  return ret;
}

乍一看，这两个函数似乎没有什么区别，但其实，在m和n足够大的情况下，sum1的运行速度要比sum2要快很多。这就是缓存的作用，在sum1中，我们对array的访问基本上顺序的，由于array在内存中是顺序存储的，所以我们访问内存的时候，也是顺序访问。而内存访问一次需要花费不少时钟周期，所以缓存会一次读取内存中接下来的部分，在下面的访问中，省去了每次都要访问内存的时间。然而，由于我们的缓存不是无限大的，后面加载的值会覆盖掉前面的值，在sum2里，因为我们不是顺序的访问内存，所以在m和n够大的情况下，我们基本上无法从缓存里拿到我们想要的值。这就导致了sum1和sum2的运行效率有着决定性的差距。在编写程序时，我们也要利用这一点，写出带有所谓“空间局部性”的程序，尽量顺序访问内存，可以使运行速度提升不少。

除了“空间局部性”以外，还有一个对于程序运行速度关系很大的性质——“时间局部性”，所谓时间局部性，就是把对于同一块内存的访问，尽量集中到一个时间内，这样可以有效的利用这块内存被预读到缓存的性质，提高I/O效率。具体的举例由于需要针对不同类型的缓存才能看出效果，在这里就不做展开了。