按行与按列遍历二维数组的速度差异

红太狼 2022-05-22 07:37 198阅读 0赞

# 按行与按列遍历二维数组的速度差异 #

### 1.代码（c语言、Linux环境） ###

#include<stdio.h>
    #include<malloc.h>
    #include<sys/time.h>
    #include<sys/resource.h>
    
    // 从进行开始执行到完成所经历的墙上时钟时间（wall clock）时间，
    // 包括其他进程使用的时间片（time slice）和本进程耗费在阻塞（如等待I/O操作完成）上的时间
    
    // CPU时间是指进程占用CPU的时间，进程阻塞的时间则不会计入CPU时间
    void gettime(double *cpu)
    {
        struct rusage ru;
        if(cpu != NULL)
        {
            getrusage(RUSAGE_SELF, &ru);
            *cpu = ru.ru_utime.tv_sec + (double)ru.ru_utime.tv_usec * 1e-6;
        }
    }
    
    int main(int argc,char* argv[])
    {
        if(argc != 2)
            return 0;
    
        int count = atoi(argv[1]);
        double cpu0,cpu1,cpu2;
    
        int *arr = (int*)malloc(sizeof(int) * count * count);
        int i,j;
    
        gettime(&cpu0);
        // 按行遍历二维数组
        for(i=0;i<count;i++)
        {
            for(j=0;j<count;j++)
            {
                arr[i * count + j]=1;
                // printf("%d-%d ",i,j);
            }
        }
        // printf("\n");
    
        gettime(&cpu1);
        // 按列遍历二维数组
        for(i=0;i<count;i++)
        {
            for(j=0;j<count;j++)
            {
                arr[j * count + i]=1;
                // printf("%d-%d ",j,i);
            }
        }
        // printf("\n");
        gettime(&cpu2);
    
        printf("按行遍历二维数组CPU时间差：%lf\n",cpu1-cpu0);
        printf("按列遍历二维数组CPU时间差：%lf\n",cpu2-cpu1);
    
        return 0;
    }

### 2.程序运行结果 ###

![Of7TNvo.png][]

### 3.说明 ###

1.  第一个for循环按行访问二维数组（第一行第一个、第一行第二个……第二行第一个……）,第二个for循环按列访问二维数组（第一行第一个、第二行第一个……第一行第二个……）,分别计算两个for循环的时间差
2.  由实验结果可以看出，随着数组数据量的增大，两种访问二维数组的方式的速度相差越来越大

### 4.原理分析 ###

1.  二维数组的内存地址是连续的，当前行的尾与下一行的头相邻
2.  现代计算机，在CPU与内存之间还有一种存储机制，那就是CPU缓存（cache）。CPU缓存的容量比内存小的多但是交换速度却比内存要快得多。缓存的出现主要是为了解决CPU运算速度与内存读写速度不匹配的矛盾，因为CPU运算速度要比内存读写速度快很多，这样会使CPU花费很长时间等待数据到来或把数据写入内存。
3.  访问数组元素时，CPU不会每次只从内存中读取一个元素，而是读取一个区域的元素。假设二维数组的大小为（10 x 10），访问第一个元素时，CPU也会读取它的相邻元素，因为这个数组比较小，CPU一次就可以把所有元素缓存，因此无论是按行访问数组还是按列访问数组，CPU访问主存的数量都相同。随着数组元素越来越多，CPU缓存一次只能读取数组不到一行的数据，因此按列访问元素时每访问一个元素都要访问内存，因此速度就会慢很多。

[Of7TNvo.png]: https://i.imgur.com/Of7TNvo.png