织梦CMS - 轻松建站从此开始!

罗索

高效编程之cache命中对于程序性能的影响

jackyhwei 发布于 2019-03-14 14:19 点击:次 
下面这个代码用两个双层循环遍历了一个二维数组里所有的元素,以我自己机器的测试 上面那个循环耗时基本为下面的一半,两个循环的时间复杂度相同,为什么会有这么大的差别?
TAG: 优化  cache  命中率  

下面这个代码用两个双层循环遍历了一个二维数组里所有的元素,以我自己机器的测试 上面那个循环耗时基本为下面的一半,两个循环的时间复杂度相同,为什么会有这么大的差别?

首先要明白的是不管是几维数组,他们都是用一块地址连续的内存来存储所有的元素,而内存布局的顺序是一整行接着下一个整行排列,第一个循环是一行一行访问,所以从内存上看是顺序的遍历了这块内存,每次读取的位置都在上一次的附近,所以cache命中率高。第二个循环是一列一列访问,可以说访问的元素都不是连续的内存访问(相隔了一行的大小),从而降低了cache的命中率。

cache的命中率对多层循环的影响是最明显的,因此在设计循环逻辑的时候,如果有某个数据结构需要多次访问,尽量让其全部在最里层中完成访问,提高cache对其的命中率。

#include <stdio.h>
#include <stdlib.h>
int main()
{
     int hang = 1024*8;
     int lie = 1024*8;
     int c = 0;
     int **arr = (int **)malloc(sizeof(int*) * lie);
     for(c = 0; c < lie; c++)
     {
          arr[c] = (int*)malloc(sizeof(int) * hang);
     }
 
     struct timeval time1, time2;
     int i, j;
 
     gettimeofday(&time1, 0);
     for(j = 0; j < lie; j++)
     {
          for(i = 0; i < hang; i++)
          {
               arr[j][i] ++;
          }
 
     }
     gettimeofday(&time2, 0);
     printf("time %f\n", (double)(time2.tv_sec-time1.tv_sec) + (double)(time2.tv_usec-time1.tv_usec) /1000000);
 
 
     gettimeofday(&time1, 0);
     for(i = 0; i < hang; i++)
     {
          for(j = 0; j < lie; j++)
          {
               arr[j][i] ++;
          }
 
     }
     gettimeofday(&time2, 0);
     printf("time %f\n", (double)(time2.tv_sec-time1.tv_sec) + (double)(time2.tv_usec-time1.tv_usec) /1000000);
 
 
     return 0;
}

(hdflzh)
本站文章除注明转载外,均为本站原创或编译欢迎任何形式的转载,但请务必注明出处,尊重他人劳动,同学习共成长。转载请注明:文章转载自:罗索实验室 [http://www.rosoo.net/a/201903/17557.html]
本文出处:cnblogs 作者:hdflzh 原文
顶一下
(0)
0%
踩一下
(0)
0%
------分隔线----------------------------
发表评论
请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。
评价:
表情:
用户名: 验证码:点击我更换图片
栏目列表
将本文分享到微信
织梦二维码生成器
推荐内容