关于c++:C二维数组按行遍历与按列遍历的速度比较

1. 程序：

#include<cstdio>
#include<cstdlib>
#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[])
{
    int count = 20000;
    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;
}

测试机器：
处理器：Apple M1
内存：8g

2. 后果：

count=1000

count=5000

count=10000

count=20000

3. 阐明

第一个 for 循环按行拜访二维数组（第一行第一个、第一行第二个……第二行第一个……）, 第二个 for 循环按列拜访二维数组（第一行第一个、第二行第一个……第一行第二个……）, 别离计算两个 for 循环的时间差
由试验后果能够看出，随着数组数据量的增大，两种拜访二维数组的形式的速度相差越来越大

4. 原理剖析

二维数组的内存地址是间断的，以后行的尾与下一行的头相邻
古代计算机，在 CPU 与内存之间还有一种存储机制，那就是 CPU 缓存（cache）。CPU 缓存的容量比内存小的多然而替换速度却比内存要快得多。缓存的呈现次要是为了解决 CPU 运算速度与内存读写速度不匹配的矛盾，因为 CPU 运算速度要比内存读写速度快很多，这样会使 CPU 破费很长时间期待数据到来或把数据写入内存。
拜访数组元素时，CPU 不会每次只从内存中读取一个元素，而是读取一个区域的元素。假如二维数组的大小为（10 x 10），拜访第一个元素时，CPU 也会读取它的相邻元素，因为这个 数组比拟小，CPU 一次就能够把所有元素缓存，因而无论是按行拜访数组还是按列拜访数组，CPU 拜访主存的数量都雷同。随着数组元素越来越多，CPU 缓存一次只能读取数组不到一行的数据，因而按列拜访元素时每拜访一个元素都要拜访内存，因而速度就会慢很多。