基于Cache未中的对编程简单优化

我们先来看看这一段代码

for(j = 0; j < 1024; j++)     
for(i = 0; i < 1024; i++)
    A[i][j];
//A[1024][1024]
for(i = 0; i < 1024; i++)     
for(j = 0; j < 1024; j++)
    A[i][j];

Array := [1024][1024]int{}
    // 0,0  0,1  0,2 .....  0,1022  0,1023
    // 1,0  1,1  1,2 .....  1,1022  1,1023
    //.................................
    //1023,0  1023,1 ...... 1023,1022  1023,1023
    fmt.Printf("%p \n",&Array[0][0])
    fmt.Printf("%p \n",&Array[0][1])
    fmt.Printf("%p \n",&Array[1][0])

0xc000100000 
0xc000100008 
0xc000102000 

有没有发现这两种循环的不同，第一循环方式对二维数组的访问跨越了很大的内存地址。而第二种循环则是访问的连续内存。
这样可能产生的最大Cache未中次数可能就是1024*1024次，（如果数组足够大，甚至可能产生缺页中断（可能性很小）)带来频繁的Cache数据换入换出(或者频繁的页面换入换出)

所以一个很简单的优化程序的思想就是尽量让我们的程序满足局部性原理。

相应的方法还有

循环合并

for(i = 0; i < 1024; i++)     
for(j = 0; j < 1024; j++)
    A[i][j]+=  C[i][j];
//A[1024][1024]
for(i = 0; i < 1024; i++)     
for(j = 0; j < 1024; j++)
    B[i][j]+=A[i][j];


for(i = 0; i < 1024; i++)     
for(j = 0; j < 1024; j++)
    A[i][j]
    B[i][j]=A[i][j]-C[i][j];

在不影响正确性的前提下合并循环，让访问数组A,C的放在一起，不然在第二个循环可能已经把上次的AC换出了

数组合并

将具有相同的索引的数组合并成一个数据结构

int val[SIZE],key[SIZE]

strcut Merge{
    int val
    int key
}
struct Merge merge_Strcut[SIZE]

分块

假如我们要计算如下所示的矩阵运算X = YZ

普通的写法如下

for(i = 0; i < N; i++)     
for(j = 0; j < N; j++)
{
  r = 0;
  for(k = 0; k < N; k = k +1)
        r = r +y[i][k]*z[k][j]
x[i][j] = r
  }

就会是这样的计算流程

for(jj = 0; jj < N; jj = jj+B)
    for(kk = 0; kk < N; kk = kk+B)
       for( i = 0; i < N ; i = i + 1)
        for(j = jj ; j < min(jj+B ,N); j = j+1)
        {
                r = 0;
                 for (k  = kk; k < min(jj+B,N); k = k+1)
                            r = r + y[i][k]*z[k][j]
            x[i][j] = x[i][j]+r;
        }

这里使用了分块的思想，正常情况下时一整行乘一整列
这里分块以后将会遍历每一个小块，然后将每个小块的计算结果累加
这里选取步长为3即B为3，以X（0，0）计算为例
X（0，0）=Y（0，0..1..2）Z（0...1...2,0）+Y(0,3...4....5)Z(3....4....5,0)