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

  • Z时代
  • 2024-01-10
  • 分类：综合

编程

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 <stdio.h>
#include <stdlib.h>
#define M 10000
#define N 20000
int 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 <stdio.h>
#include <stdlib.h>
#define M 10000
#define N 20000
int 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.二维数组两种遍历的比较

http://blog.sina.com.cn/s/blog_707d31f50101j2e7.html
[2]  哆啦A熊.二维数组按行和按列遍历的效率

https://blog.csdn.net/shuffle_ts/article/details/89420651

以上是 由二维数组遍历引发的内存访问空间局部性理解 的全部内容， 来源链接： utcz.com/z/516419.html

回到顶部