cache命中率对效率的影响

趁着去买菜的空档, 突然间想起来cache命中率失败的代价从来还没测过, 随后又想到网上很多人争论如果两个for循环嵌套, 到底是大循环放在外面效率高还是小循环放在外面效率高. 虽然有大牛说不同情况不同分析, 但到底为什么却没有分析.

于是就for循环与cache命中率写了一段测试代码访问1G的数据来测了一下性能, 竟然有1倍之多.

代码如下:

#include <Windows.h>
#include "assist.h"

//cache line 64 byte
//cache size 4Mbyte
typedef unsigned char cache_line_t[64];

cache_line_t cache_line [1024 * 1024 * 1024 / sizeof(cache_line_t)];

#define FAST 0

int _tmain(int argc, _TCHAR* argv[])
{
int times;
int i, j;
int tmp;

CACL_TAKES_TIME_BEGIN(aa);

#if FAST
for (j = 0; j < ARRAY_SIZE(cache_line); j++) { for (i = 0; i < 64; i++) { tmp = cache_line[j][i]; } } #else for (i = 0; i < 64; i++) { for (j = 0; j < ARRAY_SIZE(cache_line); j++) { tmp = cache_line[j][i]; } } #endif printf("takes:%dmsn", CACL_TAKES_TIME_END(aa)); return 0; }

具体原因可以参考这篇文章. OK买菜去.

------------------------------------------------------------
<<代码大全>>p623中讲到把最忙循环放在最内层, 是因为for循环第一次是需要初始化变量的, 如果最多层越少, 那么i变量被初始为0的次数就越少. 但是从上面的例子表明并非是这样, 这说明当数据量到达一定程度之后, 就要权衡是i被初始化的次数花的代价高还是cache命中率降低的代价更高.

这再次说明了一个道理, 这个世界上没有银弹, 同样说明不加思索的拿来主义在一定程度上是程序效率的拦路虎.



发表评论