连载：编写高效代码 —编写高效代码的意义

winston

编写高效代码(13) 数据对齐访问


          在32位处理器中，一个int型变量占4个byte，假设这个变量i在内存中占据2、3、4、5这4个byte的位置，如下图所示。

数据非对齐存储

        内核在访问这个数据时，会先将从0开始的4个byte读入到寄存器A中，再将从4开始的4个byte读入到寄存器B中，再将有效的数据拼成一个int数据，放在寄存器C中，可见，这种访问效率是多么的低下啊，如果变量i存储在从0开始的4个byte处，那么内核一次就能将i读入到寄存器中，这就是数据对齐与不对齐的访问差别。对于2字节的变量，它的起始地址应该为2的整数倍，对于4字节的变量，它的起始地址应该为4的整数倍，对于8字节的变量，它的起始地址应该为8的整数倍，这样访问效率才高。
       处理器通常都会提供对齐的数据访问指令和非对齐的数据访问指令，对齐的数据访问指令效率要远高于非对齐的数据访问指令。大数据结构时的Cache line对齐
        程序会被Cache到程序Cache中，数据会被Cache到数据Cache中，从前面可知，如果发生Cache miss，会等待大量的时间。
        Intel处理器的Cache line大多为64 byte，在对一个大数据结构（如一个大数组或大结构体）分配内存时，数据结构的起始地址最好为64 byte的整数倍，这样Cache miss的次数最少。例如，一个64 byte的数组，如果起始地址不是64的整数倍，则它会占据两个Cache line，访问时产生两次Cache miss，如果起始地址是64的整数倍，则只会占据1个Cache line，访问时只产生1次Cache miss。
        在Windows平台上，可以使用下面的语句来指定对齐，在这条指令中，将数组指定为64 byte对齐。

__declspec(align(64)) int BigArray[1024];

winston

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

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

二维数组

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

4. for(j=0; j<500; j++)
5. {
6.    for(i=0; i<500; i++)
7.    {
8.        sum += a[i][j];
9.    }
10. }

复制代码

        应该采用如下的写法，Cache的效率才高：

4. for(i=0; i<500; i++)
5. {
6.    for(j=0; j<500; j++)
7.    {
8.        sum += a[i][j];
9.    }
10. }

复制代码

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

4. int a[4], b[4], i;
5. for (i = 0; i < 4; i++)
6. {
7.    b[i] = Func(a[i]);
8. }

复制代码

         如果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的命中效率。

stay

受用！！！