「程序性能优化理论与方法」一些笔记
由于作者是使用的 X86 平台进行的测试，考虑到手上实际的设备和环境，这些更偏向于理论
硬件 & 版本依据：ARM A53，ARM GCC 11.1.0

前言

代码中其实很多逻辑均为循环，虽然在大多数情况下编译器能够进行很好的优化，但遇到复杂逻辑结构时会造成不确定性优化。因此，通过手动优化循环结构是更加好的选择，这里总结一些常用的方法

方法

循环不变量外提

将循环中的不变量外提是一种很常见的优化方式，同时也是编译器常见的优化手段

循环合并

循环合并是指将具有相同迭代空间的多个循环合并成一个循环的一种优化手段，合并的目的是为了提供并行化优化。虽然书上提到了即使也会导致优化不成功的例子，但经过尝试似乎并没有出现对应的情况，这里推测可能复杂度不高的代码对于具有多发射特性的处理器来说影响不是很大

循环展开

循环展开通过将循环体内的代码复制多次操作，进而减少循环分支指令执行的次数，提升处理器指令调度的空间，以此获得更多的指令级并行。在循环展开后的循环体内可以发掘更多的数据级并行以此来获得更高的性能，修改书上的例子：

#include <sys/time.h>

#include <stdio.h>

#define N       512

#ifdef ENABLE_INT
#define ELEM_T  int
#else
#define ELEM_T  double
#endif

void func_loop_1(ELEM_T A[][N], ELEM_T B[][N], ELEM_T C[][N]) {
  int i, j;
  for (i = 0; i < N; i++) {
    for (j = 0; j < N; j++) {
      A[i][j] = A[i][j] + B[i][j] * C[i][j];
	  }
  }
}

void func_loop_2(ELEM_T A[][N], ELEM_T B[][N], ELEM_T C[][N]) {
  int i, j;
  for (i = 0; i < N; i++) {
    for (j = 0; j < N; j+=4) {
      A[i][j] = A[i][j] + B[i][j] * C[i][j];
      A[i][j + 1] = A[i][j + 1] + B[i][j + 1] * C[i][j + 1];
      A[i][j + 2] = A[i][j + 2] + B[i][j + 2] * C[i][j + 2];
      A[i][j + 3] = A[i][j + 3] + B[i][j + 3] * C[i][j + 3];
	  }
  }
}

int main(int argv, char* args[]) {
  ELEM_T A[N][N], B[N][N], C[N][N];
  struct timespec time_start, time_end;
  int i, j;

  for (i = 0; i < N; i++) {
    for (j = 0; j < N; j++) {
      A[i][j] = 1.f;
      B[i][j] = 2.f;
      C[i][j] = 3.f;
	  }
  }

  clock_gettime(CLOCK_BOOTTIME, &time_start);
  if (argv < 2) {
    func_loop_1(A, B, C);
  } else {
    func_loop_2(A, B, C);
  }
  clock_gettime(CLOCK_BOOTTIME, &time_end);
  printf("%s spent: %ld us\n", argv < 2 ? "func_loop_1" : "func_loop_2", (time_end.tv_nsec - time_start.tv_nsec) / 1000);

  return 0;
}

使用不同的类型和编译优化等级进行测试：

int & -O0 ：

# ./test && ./test 1
func_loop_1 spent: 11804 us
func_loop_2 spent: 12206 us

int & -O2 ：

# ./test 10 && ./test 1
func_loop_1 spent: 3101 us
func_loop_2 spent: 2932 us

double & -O0 ：

# ./test && ./test 1
func_loop_1 spent: 15437 us
func_loop_2 spent: 14987 us

double & -O2 ：

# ./test && ./test 1
func_loop_1 spent: 5655 us
func_loop_2 spent: 5523 us

不难看出，通过手动循环展开的代码会比通过 -O2 的向量化优化后的结果更好，所以其实最好的优化方式依然是从源代码上出发。这是依靠编译器对代码向量化优化，手工向量化循环会取得更好的结果
同时选择展开次数也是十分的重要，修改上述代码：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N       1000
#define ELEM_T  double

void func_loop_1(ELEM_T A[][N], ELEM_T B[][N], ELEM_T C[][N]) {
  int i, j;
  for (i = 0; i < N; i++) {
    for (j = 0; j < N; j++) {
      A[i][j] = A[i][j] + B[i][j] * C[i][j];
	  }
  }
}

void func_loop_2(ELEM_T A[][N], ELEM_T B[][N], ELEM_T C[][N]) {
  int i, j;
  for (i = 0; i < N; i++) {
    for (j = 0; j < N; j+=2) {
      A[i][j] = A[i][j] + B[i][j] * C[i][j];
      A[i][j + 1] = A[i][j + 1] + B[i][j + 1] * C[i][j + 1];
	  }
  }
}

void func_loop_4(ELEM_T A[][N], ELEM_T B[][N], ELEM_T C[][N]) {
  int i, j;
  for (i = 0; i < N; i++) {
    for (j = 0; j < N; j+=4) {
      A[i][j] = A[i][j] + B[i][j] * C[i][j];
      A[i][j + 1] = A[i][j + 1] + B[i][j + 1] * C[i][j + 1];
      A[i][j + 2] = A[i][j + 2] + B[i][j + 2] * C[i][j + 2];
      A[i][j + 3] = A[i][j + 3] + B[i][j + 3] * C[i][j + 3];
	  }
  }
}

void func_loop_8(ELEM_T A[][N], ELEM_T B[][N], ELEM_T C[][N]) {
  int i, j;
  for (i = 0; i < N; i++) {
    for (j = 0; j < N; j+=8) {
      A[i][j] = A[i][j] + B[i][j] * C[i][j];
      A[i][j + 1] = A[i][j + 1] + B[i][j + 1] * C[i][j + 1];
      A[i][j + 2] = A[i][j + 2] + B[i][j + 2] * C[i][j + 2];
      A[i][j + 3] = A[i][j + 3] + B[i][j + 3] * C[i][j + 3];
      A[i][j + 4] = A[i][j + 4] + B[i][j + 4] * C[i][j + 4];
      A[i][j + 5] = A[i][j + 5] + B[i][j + 5] * C[i][j + 5];
      A[i][j + 6] = A[i][j + 6] + B[i][j + 6] * C[i][j + 6];
      A[i][j + 7] = A[i][j + 7] + B[i][j + 7] * C[i][j + 7];
	  }
  }
}

void func_loop_10(ELEM_T A[][N], ELEM_T B[][N], ELEM_T C[][N]) {
  int i, j;
  for (i = 0; i < N; i++) {
    for (j = 0; j < N; j+=10) {
      A[i][j] = A[i][j] + B[i][j] * C[i][j];
      A[i][j + 1] = A[i][j + 1] + B[i][j + 1] * C[i][j + 1];
      A[i][j + 2] = A[i][j + 2] + B[i][j + 2] * C[i][j + 2];
      A[i][j + 3] = A[i][j + 3] + B[i][j + 3] * C[i][j + 3];
      A[i][j + 4] = A[i][j + 4] + B[i][j + 4] * C[i][j + 4];
      A[i][j + 5] = A[i][j + 5] + B[i][j + 5] * C[i][j + 5];
      A[i][j + 6] = A[i][j + 6] + B[i][j + 6] * C[i][j + 6];
      A[i][j + 7] = A[i][j + 7] + B[i][j + 7] * C[i][j + 7];
      A[i][j + 8] = A[i][j + 8] + B[i][j + 8] * C[i][j + 8];
      A[i][j + 9] = A[i][j + 9] + B[i][j + 9] * C[i][j + 9];
	  }
  }
}

int main() {
  auto A = new ELEM_T[N][N];
  auto B = new ELEM_T[N][N];
  auto C = new ELEM_T[N][N];
  struct timespec time_start, time_end;
  int i, j;

  for (i = 0; i < N; i++) {
    for (j = 0; j < N; j++) {
      A[i][j] = 1.f;
      B[i][j] = 2.f;
      C[i][j] = 3.f;
	  }
  }

  clock_gettime(CLOCK_BOOTTIME, &time_start);
  func_loop_1(A, B, C);
  clock_gettime(CLOCK_BOOTTIME, &time_end);
  printf("func_loop_1 %ld us\n", (time_end.tv_nsec - time_start.tv_nsec) / 1000);

  clock_gettime(CLOCK_BOOTTIME, &time_start);
  func_loop_2(A, B, C);
  clock_gettime(CLOCK_BOOTTIME, &time_end);
  printf("func_loop_2 %ld us\n", (time_end.tv_nsec - time_start.tv_nsec) / 1000);

  clock_gettime(CLOCK_BOOTTIME, &time_start);
  func_loop_4(A, B, C);
  clock_gettime(CLOCK_BOOTTIME, &time_end);
  printf("func_loop_4 %ld us\n", (time_end.tv_nsec - time_start.tv_nsec) / 1000);

  clock_gettime(CLOCK_BOOTTIME, &time_start);
  func_loop_8(A, B, C);
  clock_gettime(CLOCK_BOOTTIME, &time_end);
  printf("func_loop_8 %ld us\n", (time_end.tv_nsec - time_start.tv_nsec) / 1000);


  clock_gettime(CLOCK_BOOTTIME, &time_start);
  func_loop_10(A, B, C);
  clock_gettime(CLOCK_BOOTTIME, &time_end);
  printf("func_loop_10 %ld us\n", (time_end.tv_nsec - time_start.tv_nsec) / 1000);

  delete[] A;
  delete[] B;
  delete[] C;

  return 0;
}

通过 -O0 和 -O2 得到的不同的结果：

-O0

# ./test
func_loop_1 56799 us
func_loop_2 55125 us
func_loop_4 54264 us
func_loop_8 53811 us
func_loop_10 53870 us

-O2

# ./test
func_loop_1 18926 us
func_loop_2 18515 us
func_loop_4 18809 us
func_loop_8 19068 us
func_loop_10 18635 us

所以选择以 4 为步进不一定是个很好的选择，要根据不同的平台做出合适的选择

循环分段

可以将单层循环拆成两层嵌套循环，分段的段长可以根据需要选取。如果原循环是可并行化循环，那么即使分段后依然可以实施并行化变化。分段后的外层循环可以采用多线程等并行化技术来发掘任务级并行，而内层循环可以使用向量化技术来做到数据级并行，比如采用数据和任务并行的矩阵计算：

任务数的划分根据处理器个数来计算：

其中，N 为迭代次数，P 为处理器个数，K 为每个处理器上分到的迭代次数

循环分块

循环分块是对多重循环的迭代空间进行重新划分，其目的是为了提高缓存命中率以及解决大于设备内存容量数组的情况。简化书上的例子：

// N = 256, A[N][N], B[N][N], C[N][N]
for (j = 0; j < N; j++) {
  for (k = 0; k < N; k++) {
    for (i = 0; i < N; i++) {
      C[i][j] = C[i][j] + A[i][k] * B[k][j];
    }
  }
}

在对 k 层的循环中，这个范围的数据会被用到，但当出现 Cache 不足以容纳这个范围的数据时，则会出现缓存未命中的情况增加循环时间。因此，可以将 i 层循环进行分块，倘若分成 M 块，那么所使用的数据范围将会变成，同时将 i 层循环提到最外层，改变迭代的顺序：

// N = 256, A[N][N], B[N][N], C[N][N]
// M = 4
for (i = 0; i < N; i+=M) {
  for (j = 0; j < N; j++) {
    for (k = 0; k < N; k++) {
      for (I = i; I < i + M; I++) {
	    C[I][j] = C[I][j] + A[I][k] * B[k][j];
      }
    }
  }
}

也不难看出 k 和 j 的循环也是可以进行同样的优化处理。最关键的点在于选择分块的数量，太少不能充分利用性能，太多收益可能不如不优化
-O3 一般会启用编译器的分块优化方案，但是通常情况下不会用到这个等级，而且分块的好坏也取决于编译器内置的算法如何，所以需要根据硬件情况手动进行分块是最好的方案

循环交换

循环交换对原有的循环并没有做出修改，而是调整了迭代的顺序。一般可以从寄存器重用和内存连续性两方面出发，简化书上代码：

// N = 256, A[N][N], B[N][N], C[N][N]
for (j = 0; j < N; j++) {
  for (k = 0; k < N; k++) {
	for (i = 0; i < N; i++) {
	  A[i][j] = A[i][j] + B[i][k] * C[k][j];
	}
  }
}

寄存器重用
可以将 i 循环提至外层，这样 C[i][j] 在内部就可以作为不变量，利于编译器将其优化成寄存器进行运算，减少 LOAD 和 STORE 的次数：

// N = 256, A[N][N], B[N][N], C[N][N]
for (j = 0; j < N; j++) {
  for (i = 0; i < N; i++) {
    for (k = 0; k < N; k++) {
      A[i][j] = A[i][j] + B[i][k] * C[k][j];
    }
  }
}

内存连续性
不难看出内循环中的矩阵 A 和矩阵 C 在 j 的索引下具有内存连续性的特性，因此可以做这样的修改促使编译器进行向量化优化：

// N = 256, A[N][N], B[N][N], C[N][N]
for (i = 0; i < N; i++) {
  for (k = 0; k < N; k++) {
    for (j = 0; j < N; j++) {
      A[i][j] = A[i][j] + B[i][k] * C[k][j];
    }
  }
}

循环分布

循环分布是将一个循环分解成多个循环，每个循环都和原循环具有相同的迭代空间，但只包含原循环语句的语句子集。比如：

// N = 256, A[N], B[N]
for (j = 0; j < N; j++) {
  A[i + 1] = A[i] + 10;   // S1
  B[i] = B[i] + 20;       // S2
}

可以将 S1 与 S2 拆开，S2 可以通过 SIMD 进行实现，这样有利于编译器进行更好的优化

循环分裂

这个和循环分布不同，分裂开来的循环不具有相同的迭代空间，这也是一种很常见的做法。比如将一个大循环中的不同阶段进行分裂，然后正确实现每部分的代码促进编译器进行优化

循环倾斜

用于改变迭代空间，发掘循环中的并行性。书上例子：

// N 8 A[N][N]
for (i = 1; i < N; i++) {
  for (j = 1; j < N; j++) {
    A[i][j] = A[i - 1][j] + A[i][j - 1];
  }
}

按照上述编写的逻辑，不难看出循环的次序：

其实可以看出整体的依赖计算顺序是这样的：

如果需要计算和两者的值，按照上面的写法需要读取两次然后进行计算，那么为什么不可以在访问到它的同时计算出两者的值呢？于是经过倾斜后，循环迭代的逻辑就可以变换成这样：

ZYXeeker`s blog

程序性能优化 —— 循环优化

前言

方法