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

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.程序运行结果

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缓存一次只能读取数组不到一行的数据，因此按列访问元素时每访问一个元素都要访问内存，因此速度就会慢很多。