现在的位置: 首页 > 综合 > 正文

连载:编写高效代码(14) 程序、数据访问符合Cache的时间、空间局部性

2018年01月25日 ⁄ 综合 ⁄ 共 841字 ⁄ 字号 评论关闭

        Cache正是利用了程序、数据访问时的时间局部性和空间局部性,为了使Cache的访问效率最高,程序和数据的组织,也应该要符合这两个特性。最典型的例子就是二维数组的访问,下面就是一个二维数组:

二维数组

        如果a[i][j]在Cache中,那么a[i][j+1]就很可能也在Cache中,但是a[i+1][j]则不一定。于是代码这样写就不太好:

 

for(j=0; j<500; j++)

{

   for(i=0; i<500; i++)

   {

       sum += a[i][j];

   }

}

 

        应该采用如下的写法,Cache的效率才高:

 

for(i=0; i<500; i++)

{

   for(j=0; j<500; j++)

   {

       sum += a[i][j];

   }

}

 

       再来看另一个例子,在下面的这段代码中:

 

int a[4], b[4], i;

for (i = 0; i < 4; i++)

{

   b[i] = Func(a[i]);

}

 

         如果a和b数组存放在不同的Cache line中,一开始访问a会产生一次Cache miss,一开始访问b也会产生一次Cache miss,如果a和b数组存放在一个Cache line之中,则只会产生一次Cache miss。

       在一起使用的数据放在一起能减少数据的Cache miss,在一起使用的函数放在一起能减少程序的Cache miss。

        程序的组织也要符合Cache局部性原则。例如,一个程序大小为40K Bytes,经常使用的代码占据30K,很少使用的代码(如初始化、异常处理等)占据10K,指令Cache为32K Bytes,这段程序是无法完全放在Cache中的,我们可以将经常执行的代码放在一起,将很少使用的代码放在一起。这样经常使用的代码就能完全进入Cache中,减少了Cache miss。

         有些较好的编译器能分析函数的调用关系,并合理的安排函数的存储位置,以提高指令Cache的命中效率。

 

抱歉!评论已关闭.