Welcome to Rooeye's blog

内外大小循环耗时的底层分析

c/c++ rooeye 584℃ 0评论

cxy

经常遇到这样的面试题:比较
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命中率,就本题例子而言大循环在外侧,小循环在里侧速度快,但是如果本题所给数组列数多于行数,结果就相反






转载请注明:寻梦人博客 » 内外大小循环耗时的底层分析

喜欢 (3)
发表我的评论
取消评论

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址