数据布局优化

原理

存储器各层次中，cache速度快，面积小，当命中率高时可以提高处理器的数据访问速度。数据布局优化通过调整数据在内存中的排列，提升cache和TLB命中率，以及CacheLine利用率，进而提升指令的执行效率，优化程序的时间开销。

常用优化方法如结构体布局优化，数据间重排，伪共享优化（见Cacheline优化）等。

修改方式

• 关于结构体布局优化，下面以结构体数组和数组结构体两种数据组织方式来介绍。
  • 结构体数组定义如下。

    //结构体数组
    struct Array{
            int x;
            int y; 
    };
    struct Array stArray[N];

    此时每一组x和y连续存储的，在内存中的存储格式如下。

    

  • 数组结构体定义如下。

    //数组结构体
    struct Array{
            int x[N];
            int y[N]; 
    };
    struct Array stArray;

    此时x和y是分开存储的，在内存中的存储格式如下。

    

  当业务场景主要针对x进行操作时，数组结构体中x加载到内存和cache中的数据是连续的。相比于结构体数组，提高了cacheline的有效性和cache的命中率，从而提高性能。

• 数据间重排

  以二维数组为例，当二维数组B按列与数组A相加，此时列元素在cache中非连续的，不在一个CacheLine中，性能相对较差。通过对二维数组B重排，改为二维数组A与二维数组B的行元素相加，则可以从cache中连续读取数据。重排前耗时544939us，重排后235722us。

  按列读取：

  for (int i = 0; i < ARRAYLEN; i++) {
      for (int j = 0; j < ARRAYLEN; j++) {
          arrayC[i][j] = arrayA[i][j] + arrayB[j][i];
      }
  }

  改为按行读取：

  for (int i = 0; i < ARRAYLEN; i++) {
      for (int j = 0; j < ARRAYLEN; j++) {
          array[i][j] = arrayA[i][j] + arrayB[i][j];
      }
  }