本文，我们主要关心的是cache miss事件，那么我们只需要统计程序cache miss的次数即可。
使用perf 来检测程序执行期间由此造成的cache miss的命令是perf stat -e cache-misses ./exefilename，另外，检测cache miss事件需要取消内核指针的禁用（/proc/sys/kernel/kptr_restrict设置为0）。

1、数据合并

有两个数据A和B，访问的时候经常是一起访问的，总是会先访问A再访问B。
这样A[i]和B[i]就距离很远，如果A、B是两个长度很大的数组，那么可能A[i]和B[i]无法同时存在cache之中。
为了增加程序访问的局部性，需要将A[i]和B[i]尽量存放在一起。为此，我们可以定义一个结构体，包含A和B的元素各一个。这样的两个程序对比如下：

test.c

  1. #define NUM 393216  
  2.   int main(){  
  3.     float a[NUM],b[NUM];  
  4.     int i;  
  5.     for(i=0;i<1000;i++)  
  6.         add(a,b,NUM);  
  7. }  
  9. int add(int *a,int *b,int num){  
  10.     int i=0;  
  11.     for(i=0;i<num;i++){  
  12.         *a=*a+*b;  
  13.         a++;  
  14.         b++;  
  15.     }     
  16. }

test2.c

  1. #define NUM 393216  
  2. typedef struct{  
  3.     float a;  
  4.     float b;  
  5. }Array;  
  7. int main(){  
  8.     Array myarray[NUM];  
  9.     int j=0;  
  10.     for(j=0;j<1000;j++)  
  11.         add(myarray,NUM);  
  12. }  
  14. int add(Array *myarray,int num){  
  15.     int i=0;  
  16.     for(i=0;i<num;i++){  
  17.         myarray->a=myarray->a+myarray->b;  
  18.         myarray++;  
  19.     }     
  20. }

注：我们设置数组大小NUM为393216，因为cache大小是3072KB，这样设定可以让A数组填满cache，方便对比。 对比二者的cache miss数量：
为了对比，之后测试了大小都为39216的情况，证明确实越大越好

NUM=393216图片.pngNUM=39216图片.png
可以看到，后者的cache miss数量相对前者有一定的下降，大致优化性能20%。
进一步，可以查看触发cach-miss的函数：
test程序的结果（含-g查看函数调用）：
NUM=393216
test1图片.pngtest2图片.pngperf stat:
图片.png
可见，page-faults次数不变， 但misses和耗时比例却上升，说明add函数的cache-misses和耗时有一定下降

2、循环交换

C语言中，对于二维数组，同一行的数据是相邻的，同一列的数据是不相邻的。
如果在循环中，让依次访问的数据尽量处在内存中相邻的位置，那么程序的局部性将会得到很大的提高。
观察下面矩阵相乘的几个函数：

test_ijk:

  1. void Muti( double A[][NUM],double B[][NUM],double C[][NUM],int n){   
  2.     int i,j,k;  
  3.     double sum=0;  
  4.     for (i=0;i<n;i++)  
  5.         for(j=0;j<n;j++){  
  6.             sum=0.0;  
  7.             for(k=0;k<n;k++)  
  8.                 sum+=A[i][k]*B[k][j];  
  9.             C[i][j]+=sum;  
  10.         }

test_jki:

  1. void Muti( double A[][NUM],double B[][NUM],double C[][NUM],int n){   
  2.     int i,j,k;  
  3.     double sum=0;  
  4.     for (j=0;j<n;j++)  
  5.         for(k=0;k<n;k++){  
  6.             sum=B[k][j];  
  7.             for(i=0;i<n;i++)  
  8.                 C[i][j]+=A[i][k]*sum;  
  9.         }         
  10. }

test_kij:

  1. void Muti( double A[][NUM],double B[][NUM],double C[][NUM],int n){   
  2.     int i,j,k;  
  3.     double sum=0;  
  4.     for (k=0;k<n;k++)  
  5.         for(i=0;i<n;i++){  
  6.             sum=A[i][k];  
  7.             for(j=0;j<n;j++)  
  8.                 C[i][j]+=B[k][j]*sum;  
  9.         }         
  10. }

考察内层循环，可以发现，不同的循环模式，导致的cache失效比例依次是kij、ijk、jki递增。

3、循环合并

在很多情况下，我们可能使用两个独立的循环来访问数组a和c。
由于数组很大，在第二个循环访问数组中元素的时候，第一个循环取进cache中的数据已经被替换出去，从而导致cache失效。
如此情况下，可以将两个循环合并在一起。
合并以后，每个数组元组在同一个循环体中被访问了两次，从而提高了程序的局部性。

实际情况下，一个程序的cache失效比例往往并不像我们从理论上预测的那么简单。
影响cache失效比例的因素主要有：数组大小，cache映射策略，二级cache大小，Victim Cache等，
同时由于cache的不同写回策略，我们也很难从理论上预估一个程序由于cache miss而导致的时间耗费。
真正在进行程序设计的时候，我们在进行理论上的分析之后，只有使用perf等性能调优工具，
才能更真实地观察到程序对cache的利用情况。

参考资料：
https://blog.csdn.net/sunshineywz/article/details/109044155