从缓存来看程序局部性提高程序运行效率的原因
一、什么是程序局部性
一个写的优美的程序往往具有一个良好的局部性，那么什么是程序局部性呢？
程序局部性是指程序在运行的一段时间内，它们更加倾向于引用的数据靠近最近引用过的数据。因此，整个程序的执行会限制于程序中的某一部分，对应的执行代码的时候访问的存储空间也局限于某一个内存区域。现在不论是操作系统还是应用程序，都参考了局部性的原理，例如：缓存机制、CPU指令执行顺序等。在硬件层，局部性原理允许计算机设计者通过引入称为高速缓存存储器的小而快速的存储器来保存最近被引用的指令和数据项，从而提高对主存的访问速度。在操作系统级，局部性原理允许系统使用主存作为虚拟地址空间最近被引用块的高速缓存。
而从程序局部性来分类，主要有两个种类，一个是时间局部性，一个是空间局部性。
PS：算法局部性
1.1 时间局部性
时间局部性通常运用在循环当中，一条指令一旦被执行，那么不久以后该指令可能再次被执行，被访问过的存储器位置也肯能会在不久之后会被再次访问，它强调的是数据的重复访问。
而利用时间局部性的原理缓存可以极大的提高数据重复访问的性能。
int sum( int *array, int n){
int sum = 0;
for ( int i = 0; i < n; i++ ){
sum += array[i];
}
return sum;
}
如上代码中的sum变量就是存在于循环当中，这个变量在此循环中被多次访问，因此sum就具有良好的时间局部性。
1.2 空间局部性
程序访问了某一个存储器的位置，那么不久之后，它附近的存储单元也肯能会被访问，空间局部性更多的是强调它附近的位置会被经常引用。
int sum( int *array, int n){
int sum = 0;
for ( int i = 0; i < n; i++ ){
sum += array[i];
}
return sum;
}
我们知道一个数组，在内存中存放的向下图一样连续存放的。
因此上面的程序变量array则具有良好的空间局部性，每次访问其中的array[ i ]的时候，array[ i+1 ]总是在它的下一个位置。步数越长，空间局部性就会越差。
需要注意的是，变量array没有时间局部性，因为在循环体中，每个元素只会被访问一次。sum并不具备空间局部性，因为sum是标量，我们只能通过它得到一个值。
1.3 局部性对程序执行效率的影响
我们知道二维数组在计算机中存取的方式是以行来存取的，因此我们写一个程序，分别采用不同的存取方式。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int a[3000][3000];
//先访问行
void fun_1()
{
int i,j;
int sum = 0;
for(i=0; i<3000; i++)
{
for(j=0; j<3000; j++)
{
sum += a[i][j];
}
}
}
//先访问列
void fun_2()
{
int i,j;
int sum = 0;
for(j=0; j<3000; j++)
{
for(i=0; i<3000; i++)
{
sum += a[i][j];
}
}
}
int main()
{
clock_t start, finish;
double duration;
start = clock();
fun_1();
finish = clock();
duration = (double)(finish - start) / CLOCKS_PER_SEC;
printf( "fun_1: %f seconds\n", duration);
start = clock();
fun_2();
finish = clock();
duration = (double)(finish - start) / CLOCKS_PER_SEC;
printf( "fun_2: %f seconds\n", duration) ;
return 0;
}
此时经过编译运行的出来的结果如下：
fun_1: 0.037495 seconds
fun_2: 0.077399 seconds
但是一旦当数据量变小的时候，例如数组为a[400][400]，运行结果却相反。
fun_1: 0.001839 seconds
fun_2: 0.001127 seconds
这是因为在测试数据量小的情况下，对于CPU这么高的主频，缓存不命中所损失的时间是很少的。当K变得很大的时候，基本不能命中，那么每次访问一个对象都要从读取周期长的存储器中读取数据，那么这样就会比数据量小的情况花费更多的时钟周期，所以一旦当数据量变大，那么差距就会更加明显。
根据如上结果进行分析，在对数组的访问中，如果访问数组的顺序和存取顺序是一致的，并且是连续访问，那么这种访问就具有良好的空间局部性。
二、存储器系统
计算机存储器从下至上分别有硬盘，主存、高速缓冲存储器、寄存器。越往上速度越快，成本越高。
在最早的时候，计算机存储器层次只有三层：CPU寄存器、DRAM主存、磁盘存储，后来因为CPU和主存之间存在巨大的速度差异，所以系统的设计者在CPU和主存之间插入了一个小型的SRAM高速缓冲存储器L1缓存，大概在2-4个时钟周期内访问。后来发现这个高速缓冲存储和主存还是有很大的速度差异，因此在这两个存储器之间又增加了一个L2高速缓冲存储器，大约可以在10个时钟周期内访问，由此计算机通过不断的演变，变成了现在的存储体系。
那么它们是如何协调工作来提高运行效率呢。
三、什么是缓存
存储器的主要思想是上一级的存储器作为下一级的存储器的高速缓冲存储，因此如上图所示，L1是L2的高速缓存，主存是磁盘的高速缓存。
换句话来说，对于每一个K，位于K层的更快更小的存储器设备作为第K+1层的更大的慢的存储器设备的缓存。也就是说，第K层存储了K+1层中经常被访问的数据。在缓存之间，数据是按照块为单位进行传输的。当然不同层次的缓存，块的大小会不相同，一般情况来说，是越向上块越小。
如下图所示：
K是K+1层的缓存，数据的传输是按照块大小为单位的，如上图K层缓存了K+1层中块编号为4、9、14、3号的数据。当程序需要这些块中的数据时。可以直接从缓存k中得到，这样的话会比从K+1层中去读取数据要块的多。
四、缓存命中和缓存失效
缓存命中
当程序需要第K+1层中的某一个数据m的时候，他首先会去K层缓存中进行寻找，如果数据刚好在K层中，那么称此次缓存命中，如上图中访问K+1层中的数据块14，此时首先在缓存层K层中去寻找，而14正好在K层中，此时发生了缓存命中。
缓存失效
缓存失效也叫作缓存不命中。当需要的数据对象M不在缓存K层中，此时称之为缓存不命中，当发生缓存不命中时，CPU会直接从K+1层中取出包含数据对象M的数据块，然后将其缓存到K层，如果此时K层的缓存已经放满的话，就会覆盖其中的一块，覆盖的时候会根据缓存中的替换策略决定的（例如LRU）。在K层从K+1层中取出数据对象M后，程序就可以在缓存中取出数据对象M了。
五、程序局部性如何影响程序性能
这里我们来说一说为什么局部性好的程序能有更好的性能。
利用空间局部性：由于空间局部性，假设缓存K能存取n个数据块，在对数组进行访问的时候，由于数据才内存中是连续存放的，对第一个元素进行访问的时候，会把第一个元素后面的一共n个元素（缓存k有n个数据块）拷贝到缓存k中，这样在对第二个元素到第n个元素的访问时就可以直接存缓存中获取，从而提高性能。
利用时间局部性：由于时间局部性，对同一个数据对象可能会被多次使用。一旦一个数据对象从K+1层中进入到第K层的缓存中，就希望它被多次引用，这样可以节省很多访问锁造成的时间开销。
同理，访问第n个元素的时候 ，n不在缓存中，缓存管理器会把从n到2n的元素拷贝到缓存中，对它们的访问就可以直接在缓存中进行。
通过空间局部性，我们希望对后面对缓存中其他对象的访问能补偿不命中后拷贝这些块的时间花费。
下面我们在思考一下之前的题，上面两道题的区别是一个是按照行进行访问的，一个是按照列进行访问的，正式这些不同导致了性能上的差别。
我们先来看看按行访问，发生了什么，为了分析方便，我们假设：缓存每次只能缓存一块，一块大小只能存放3个int类型数据，假设对于一个两行三列的int[2][3]的数组访问。
按行访问时，访问a[0][0]，时直接从内存读取，然后将a[0][0]以及其后的两个数缓存到其缓存中，这样再访问a[0][1],a[0][2]时直接从缓存中读取，对于第二行的访问也是如此。因此对于整个数组6个元素的访问，只访问了2次内存，缓存命中了4次。
再来看看按列访问，当访问a[0][0]，时直接从内存读取，然后将a[0][0]以及其后的两个数缓存到其缓存中，看起来和按行访问没什么区别，那好，再看下一步，按列访问的话接下来应该是访问a[1][0]了，先去缓存中找，肯定找不到了，没办法，只能再次访问内存。对于第2、3列情况一样，这样，同样一个数组，按列访问访问了6次内存，效率当然比按行访问低了。
ps：在JAVA中也有一个伪共享可以看一下