面试题——内外大小循环耗时的底层分析
经常遇到这样的面试题：比较
for (i = 0; i < A; i++)
{
for (j = 0; j < B; j++)
{
/////
}
}
和
for (i = 0; i < B; i++)
{
for (j = 0; j < A; j++)
{
/////
}
}
两段代码哪一个耗时更少(假设A>>B)？ 网上没有这类问题的底层分析，仔细思考之后打算写一篇博客，所用代码在gcc下测试。
首先定义两个数组用于程序测试：
#define A 1000000 #define B 200 int p[A][B],q[A][B];
定义大循环在外面，小循环在里面的测试代码，让数组p实现加一功能：
void demo1()
{
int i,j;
for (i = 0; i < A; i++)
{
for (j = 0; j < B; j++)
{
p[i][j]++;
}
}
}
定义大循环在里面，小循环在外面的测试代码，让数组q实现加一功能：
void demo2()
{
int i,j;
for (j = 0; j < B; j++)
{
for (i = 0; i < A; i++)
{
q[i][j]++;
}
}
}
比较demo1和demo2的耗时，计时程序如下，形参是函数指针：
void shijian(void(*func)())
{
time_t start, end;
time(&start);
func();
time(&end);
printf("%fs ", difftime(end, start));
}
为了保证程序的准确性，计时比较10次：
for (i = 0; i < 10; i++)
{
shijian(&demo1);
shijian(&demo2);
printf("\n");
}
运行结果见下图：
结果还是比较明显的，大循环在外面，小循环在里面的速度远远快于
大循环在里面，小循环在外面的速度，原因分析见下。
计算机的存储层次结构见下图：
CPU访存时，会先访问Cache，如果访问Cache失效，Cache中没有要读取的数据，就到内存中查找所需数据，再传送给Cache，CPU再读Cache，如果内存中也没有，继续到外存中寻找。因为
CPU访问Cache速度 > CPU
访问内存速度 >>
CPU
访问外存速度，当程序运行时，缓存命中率越高，所用时间就越少，缓存失效次数越多，所用时间越多。为了分析方便，假设Cache容量大小为16B，内存分块大小为16B，采用全相联映像。
数组p,q在内存中的存储情况：
分析demo1的Cache失效次数：
当第一次执行循环，CPU读取p[0][0]的时候，此时Cache为空，访问缓存失效，需要将一个内存块拷贝到Cache中，拷贝后Cache中的数据分布为：
当第二次执行循环体，CPU读取p[0][1],p[0][1]已经在缓存中，缓存命中；
当第三次执行循环体，CPU读取p[0][2],p[0][2]已经在缓存中，缓存命中；
当第四次执行循环体，CPU读取p[0][3],p[0][3]已经在缓存中，缓存命中；
当第五次执行循环体，CPU读取p[0][4],p[0][4]不在缓存中，访问缓存失效,此时继续将一个内存块拷贝到Cache中，覆盖原先数据：
当第六次执行循环体，CPU读取p[0][5],p[0][5]已经在缓存中，缓存命中；
当第七次执行循环体，CPU读取p[0][6],p[0][6]已经在缓存中，缓存命中；
当第八次执行循环体，CPU读取p[0][7],p[0][7]已经在缓存中，缓存命中；
当第九次执行循环体，CPU读取p[0][8],p[0][8]不在缓存中，访问缓存失效,此时继续将一个内存块拷贝到Cache中，覆盖原先数据。
.........
........
当i=0的时候，内循环共执行200次，其中缓存命中150次，缓存失效50次；
当i=1的时候，内循环共执行200次，其中缓存命中150次，缓存失效50次；
当i=i的时候，内循环共执行200次，其中缓存命中150次，缓存失效50次；
当i=999999的时候，内循环共执行200次，其中缓存命中150次，缓存失效50次；
所以，对于demo1，缓存命中次数为 150*A，缓存失效次数为 50*A，缓存命中率为75%。
分析demo2的Cache失效次数：
当第一次执行循环，CPU读取q[0][0]的时候，此时Cache为空，访问缓存失效，要将一个内存块拷贝到Cache中：
当第二次执行循环，CPU读取q[1][0]的时候，q[1][0]并不在Cache中，访问缓存失效;
当第三次次执行循环，CPU读取q[2][0]的时候，q[2][0]并不在Cache中，访问缓存失效;
当第四次执行循环，CPU读取q[3][0]的时候，q[3][0]并不在Cache中，访问缓存失效;
当第五次执行循环，CPU读取q[4][0]的时候，q[4][0]并不在Cache中，访问缓存失效;
.........
........
当j=0的时候，内循环共执行1000000次，其中缓存命中0次，缓存失效A次；
当j=1的时候，内循环共执行1000000次，其中缓存命中0次，缓存失效A次；
当j=i的时候，内循环共执行1000000次，其中缓存命中0次，缓存失效A次；
当j=199的时候，内循环共执行1000000次，其中缓存命中0次，缓存失效A次；
所以，对于demo2，缓存命中次数为 0，缓存失效次数为 B*A，缓存命中率为 0%。
综上分析可知，当大循环在外侧，小循环在里侧的时候，缓存命中率远大于 大循环在里侧，小循环在外侧的时候，所以demo1的耗时更少。
注：满足内层循环中操作数据在内存连续的就可以提高访问Cache命中率，就本题例子而言大循环在外侧，小循环在里侧速度快，但是如果本题所给数组列数多于行数，结果就相反
完整测试代码：
#include "stdio.h"
#include<time.h>
#define A 1000000
#define B 200
int p[A][B],q[A][B];
void demo1()
{
int i,j;
for (i = 0; i < A; i++)
{
for (j = 0; j < B; j++)
{
p[i][j]++;
}
}
}
void demo2()
{
int i,j;
for (j = 0; j < B; j++)
{
for (i = 0; i < A; i++)
{
q[i][j]++;
}
}
}
void shijian(void(*func)())
{
time_t start, end;
time(&start);
func();
time(&end);
printf("%fs ", difftime(end, start));
}
int main()
{
int i;
for (i = 0; i < 10; i++)
{
shijian(&demo1);
shijian(&demo2);
printf("\n");
}
return 0;
}
投递腾讯等公司6个岗位 >
