循环优化

原理

循环优化是对程序中使用到的循环部分进行代码优化，合理的优化可以充分利用处理器的计算单元，提升指令流水线的调度效率，也可以提升cache命中率。循环优化的方法有很多，如循环展开，循环融合，循环分离，循环交换，循环平铺等，根据具体业务代码选择使用。

修改方式

• 循环展开

  循环展开是将循环体重复多次来减少循环，通常使用在小循环中。可以利用鲲鹏处理器具有多个指令执行单元的特点，增加计算密度，提升指令流水线的调度效率。如下是循环展开前后的代码对比。

  修改前：

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

  修改后：

  int i;
  for (i = 0; i < ARRAYLEN - (ARRAYLEN % 4); i+=4) {
      arrayC[i] = arrayA[i] * arrayB[i];
      arrayC[i + 1] = arrayA[i + 1] * arrayB[i + 1];
      arrayC[i + 2] = arrayA[i + 2] * arrayB[i + 2];
      arrayC[i + 3] = arrayA[i + 3] * arrayB[i + 3];
  }
  for (; i < ARRAYLEN; i++) {
      arrayC[i] = arrayA[i] * arrayB[i];
  }

• 循环融合

  循环融合是将相邻或紧密间隔的循环融合在一起，减少对循环变量的操作。迭代变量在循环体内被使用，可以提高cache的使用率。合并小循环后也有利于增加鲲鹏处理器乱序执行的机会，提升指令流水线的调度效率。

  修改前：

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

  修改后：

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

• 循环分离

  循环分离主要针对较为复杂或计算密集的循环，将大循环拆分至多个小循环内执行，提升寄存器的利用率。

  修改前：

  for (int i = 1; i < ARRAYLEN; i++) {
      arrayA[i] = arrayA[i-1] + 2;
      arrayC[i] = arrayB[i] + 6;
  }

  修改后：

  for (int i = 1; i < ARRAYLEN; i++) {
      arrayA[i] = arrayA[i-1] + 2;
  }
  for (int i = 1; i < ARRAYLEN; i++) {
      arrayC[i] = arrayB[i] + 6;
  }

• 循环交换

  循环交换是指交换循环的嵌套顺序，让内存访问尽可能满足局部性规则，提高cache命中率。

  修改前：

  for (int j = 0; j < ARRAYLEN; j++) {
      for (int i = 0; i < ARRAYLEN; i++) {
          matrixC[i][j] = matrixA[i][j] + 3;
      }
  }

  修改后：

  for (int i = 0; i < ARRAYLEN; i++) {
      for (int j = 0; j < ARRAYLEN; j++) {
          matrixC[i][j] = matrixA[i][j] + 3;
      }
  }

• 循环平铺

  循环平铺是指将一个循环拆分成一组嵌套循环，每个内部循环负责一个小数据块，以便最大化利用cache中的现有数据，提高cache命中率。通常针对比较大的数据集。

  修改前：

  for (int i = 0; i < n * ARRAYLEN; i++) {
      for (int j = 0; j < n * ARRAYLEN; j++) {
          matrixA[i][j] = matrixA[i][j] + matrixB[i][j];
      }
  }

  修改后：

  // 假设定义一个合适的平铺块大小，这里取名为TILE_SIZE，可以根据实际缓存大小等因素调整
  #define TILE_SIZE 16 
  for (int ii = 0; ii < n * ARRAYLEN; ii += TILE_SIZE) {
      for (int jj = 0; jj < n * ARRAYLEN; jj += TILE_SIZE) {
          for (int i = ii; i < ii + TILE_SIZE && i < n * ARRAYLEN; i++) {
              for (int j = jj; j < jj + TILE_SIZE && j < n * ARRAYLEN; j++) {
                  matrixA[i][j] = matrixA[i][j] + matrixB[i][j];
              }
          }
      }
  }