由二维数组遍历引发的内存访问空间局部性理解

1. CPU⾼速缓存：在计算机系统中，CPU⾼速缓存（英语：CPU Cache）是⽤于减少处理器访问内存所需平均时间的部件。在⾦字塔式存储体系中它位于⾃顶向下的第⼆层，仅次于CPU寄存器。其容量远⼩于内存，但速度却可以接近处理器的频率。当处理器发出内存访问请求时，会先查看缓存内是否有请求数据。如果存在（命中），则不经访问内存直接返回该数据；如果不存在（失效），则要先把内存中的相应数据载⼊缓存，再将其返回处理器。缓存之所以有效，主要是因为程序运⾏时对内存的访问呈现局部性（Locality）特征。这种局部性既包括空间局部性（Spatial Locality），也包括时间局部性（Temporal Locality）。有效利⽤这种局部性，缓存可以达到极⾼的命中率。（百度百科解释）。

2.⼆维数组有两种遍历⽅式，⼀种是先⾏后列，⼀种是先列后⾏，代码实现也很简单，⽤两个for循环嵌套即可，表⾯上看来，⼆者时间复杂度都是O(mn),但实际上，效率的是通过内存页⾯交换次数和Cache命中率的⾼低来判断的。

3.先⾏后列的效率要⾼的多，这个与⼆维数组的存储⽅式有关(内存中，上⼀⾏的尾部地址和下⼀⾏的头部地址连续)。

情况⼀：如果申请的空间在内存之中，也就是说读取只需要看cache是否命中，未命中再到内存中读取。⽽cache从内存中抓取⼀般都是整个数据块，所以它的物理内存是连续的，对于较⼤的数组⽽⾔，⼏乎读取的数据都是同⾏不同列的（因为cache很⼩，所以对于较⼤的数组⼀般只会拿⼀⾏内的数据），⽽如果内循环以列的⽅式进⾏遍历的话，将会使整个缓存块⽆法被利⽤，⽽不得不从内存中读取数据，⽽从内存读取速度是远远⼩于从缓存中读取数据的。随着数组元素越来越多，按列读取速度也会越来越慢。

情况⼆：申请的为虚拟内存（当然程序认为还是连续的物理内存，是操作系统在磁盘另开辟的空间），虚拟内存到物理内存需要经过地址映射，如果虚拟内存采⽤页式地址映射（不讨论快表技术，仅分析页表在内存中），最好的情况是每次映射的页内数据都可以被使⽤，这样可以减少页⾯调度的次数,从⽽提升效率。

例如：对于int a[128][1024];假设内存页⼤⼩为4096字节(⼀个int 占4个字节)，该数组每⾏正好占据⼀个内存页的空间，若按先⾏后列遍历，外层循环每⾛⼀⾏，内层⾛过1024个元素正好⼀页，没发⽣页⾯调度，遍历完整个数组页⾯调度次数最多为128次；若按先列后⾏，则每遍历⼀个元素，都发⽣⼀次页⾯调度，因为列上每个元素位于同⾏内（不同页），遍历整个数组页⾯调度次数可能达到1024*128次；实际中由于物理内存⾜够（内存页较⼤，分配给进程的页框数多等因素），调度次数会减少很多。

4.总结：对于⼆维数组的遍历效率优化，其实就是更好的利⽤程序申请内存⽽产⽣的空间局部性，这种局部性在很多地⽅都有体现，⼆维数组只是简单的⼀个例⼦，⼀个好的程序可以合理减少缺页发⽣的次数，提⾼程序的空间局部性，从⽽提⾼运⾏效率。

简易代码（实际结果很可能因为申请内存位置不同或内存⼤⼩⽽产⽣偏差）：#include #include #define M 10000#define N 20000int main(){

int MyArray[M][N]; int i,j;

//先⾏后列⽅式遍历 for( i = 0;i < M;i++){ for(j = 0;j < N;j++){ MyArray[i][j] = 0; } }}

#include #include #define M 10000#define N 20000int main(){

int MyArray[M][N]; int i,j;

//先列后⾏⽅式遍历 for( i = 0;i < N;i++){ for(j = 0;j < M;j++){ MyArray[j][i] = 0; } }}

参考⽂章

[1] ⼩⽩xiaoxiao.⼆维数组两种遍历的⽐较