C语言深度解剖之——for循环优化

2/10/2017来源:ASP.NET技巧人气:908

转载:点击打开链接 作者:chen825919148

1.8.2,循环语句的注意点

【建议1-27】在多重循环中,如果有可能,应当将最长的循环放在最内层,最短的循环放在最外层,以减少CPU跨切循环层的次数。

例如:

************************************以上是原文************************************

其实,右边的循环之所以比左边的效率高,本质原因并非是循环长短的问题,而是与程序访问的局部性和Cache命中率有关。计算机专业毕业的学生应该很清楚这个问题,在《操作系统》和《体系结构》课程中一般都会探讨此问题。我们知道,数组在计算机中是行优先存储的(即本行的最后一个元素与下一行的第一个元素地址相邻),左边的循环中,依次访问的是变量a[0][0],a[1][0],a[2][0],……,a[99][0],a[0][1],a[1][1],a[2][1],……,a[99][1],……这实际上是按照列优先的原则在访问数组元素。如果Cache容量相对于数组容量而言不够大,考虑一个极端情况,假设Cache只有一个块,只能存储一行数据,则每访问一个元素就会发生一次Cache失效,就需要访问一次主存,读入一块数据,导致存储系统效率低下,明显影响操作延迟。而右边的循环采用的是行优先访问原则,与元素存储顺序一致。基于同样的假设,此时只有访问新一行的第一个数据时才发生Cache失效,通过访问主存读入一块连续的数据(恰为数组的一行),此后访问同行数据便可直接使用Cache中缓存的数据,直到访问下一行的第一个数据。Cache失效率降低了,整个存储系统的平均访问延迟降低了,显然程序执行效率较高。

内外循环交换是优化程序性能的重要手段之一,右边程序的存储访问局部性较好,建议如此编程。