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

前言

虽然通过指定编译器的优化等级可以对代码进行优化，但其优化具有局限性：

优化行为会受到基本的约束
- 必须保证对程序的行为不产生影响
- 通常会阻止将程序行为引向不利的情况这类优化
某些行为对于开发者来说可能是明确的，但编译器来说可能会受到语言和代码风格的影响
大部分优化分析只是基于执行的步骤
- 在大多数情况下不会对整个程序进行优化分析
- GCC做过程间优化也只是基于单文件进行
大部分优化是基于静态分析进行
在具有不确定行为时，编译器只做保守的优化
因此优化最好的方式依然是进行手动优化，如果编译器没有进行预期的优化那么依然需要从代码出发

方法

别名消除（Memory Aliasing）

内存别名，即同一个地址被多个变量引用，导致编译器会认为这些变量与上下文存在依赖关系从而影响优化。比如 CSAPP 中的例子：

void loop(int* a, int* b, int n) {
  int i, j;
  for (i = 0; i < n; i++) {
    a[i] = 0;
    for (j = 0; j < n; j++) {
      a[i] += b[j] + 10;
    }
  }
}

➡

void loop_better(int* a, int* b, int n) {
  int i, j, val;
  for (i = 0; i < n; i++) {
    val = 0;
    for (j = 0; j < n; j++) {
      val += b[j] + 10;
    }
    a[i] = val;
  }
}

使用 -O1 进行优化：

loop(int*, int*, int):
        push    {r4, r5, lr}
        subs    lr, r2, #0
        ble     .L1
        mov     r4, r1
        mov     ip, r0
        lsl     lr, lr, #2
        add     r1, r0, lr
        add     lr, lr, r4
        movs    r5, #0
.L4:
        str     r5, [ip], #4
        mov     r0, r4
.L3:
        ldr     r2, [r0], #4
        adds    r2, r2, #10
        ldr     r3, [ip, #-4]
        add     r3, r3, r2
        str     r3, [ip, #-4]
        cmp     r0, lr
        bne     .L3
        cmp     ip, r1
        bne     .L4
.L1:
        pop     {r4, r5, pc}

➡

loop_better(int*, int*, int):
        subs    ip, r2, #0
        ble     .L7
        push    {r4, lr}
        mov     r4, r1
        mov     lr, r0
        lsl     ip, ip, #2
        add     r1, r0, ip
        add     ip, ip, r4
.L3:
        mov     r2, r4
        movs    r0, #0
.L4:
        ldr     r3, [r2], #4
        adds    r3, r3, #10
        add     r0, r0, r3
        cmp     r2, ip
        bne     .L4
        str     r0, [lr], #4
        cmp     lr, r1
        bne     .L3
        pop     {r4, pc}
.L7:
        bx      lr

和预期一样，loop_better() 取得了更好的效果，LOAD 与 STORE 操作由原来的 2n 减少到了 n 次。如果采用更高的优化等级会怎么样？使用 -O2，*-O3* 分别进行优化：

# -O2 -O3
loop(int*, int*, int):
        push    {r4, r5, lr}
        subs    lr, r2, #0
        ble     .L1
        lsl     lr, lr, #2
        movs    r4, #0
        add     r5, r0, lr
        add     lr, lr, r1
.L4:
        mov     ip, r1
        movs    r2, #0
        str     r4, [r0], #4
.L3:
        ldr     r3, [ip], #4
        adds    r3, r3, #10
        cmp     lr, ip
        add     r2, r2, r3
        str     r2, [r0, #-4]
        bne     .L3
        cmp     r0, r5
        bne     .L4
.L1:
        pop     {r4, r5, pc}

# -O2
loop_better(int*, int*, int):
        subs    ip, r2, #0
        ble     .L7
        push    {r4, lr}
        mov     r4, r1
        mov     lr, r0
        lsl     ip, ip, #2
        add     r1, r0, ip
        add     ip, ip, r4
.L3:
        mov     r2, r4
        movs    r0, #0
.L4:
        ldr     r3, [r2], #4
        adds    r3, r3, #10
        add     r0, r0, r3
        cmp     r2, ip
        bne     .L4
        str     r0, [lr], #4
        cmp     lr, r1
        bne     .L3
        pop     {r4, pc}
.L7:
        bx      lr

# -O3
loop_better(int*, int*, int):
        push    {r4, r5, r6, r7, r8, r9, r10, lr}
        mov     r4, r1
        subs    r1, r2, #0
        ble     .L1
        lsrs    r2, r1, #2
        mov     ip, r0
        vmov.i32        q10, #10  @ v4si
        add     r7, r0, r1, lsl #2
        add     r10, r1, #-1
        add     r2, r4, r2, lsl #4
        bic     r5, r1, #3
.L3:
        cmp     r10, #2
        bls     .L8
        vmov.i32        q9, #0  @ v4si
        mov     r3, r4
.L5:
        vld1.32 {q8}, [r3]!
        vadd.i32        q8, q8, q10
        cmp     r2, r3
        vadd.i32        q9, q9, q8
        bne     .L5
        vadd.i32        d18, d18, d19
        cmp     r5, r1
        it      ne
        movne   r0, r5
        vpadd.i32       d18, d18, d18
        vmov.32 r3, d18[0]
        beq     .L4
.L7:
        ldr     r6, [r4, r0, lsl #2]
        add     r8, r0, #1
        lsl     lr, r0, #2
        cmp     r1, r8
        add     r9, r6, #10
        add     r3, r3, r9
        ble     .L4
        add     lr, lr, r4
        adds    r0, r0, #2
        cmp     r1, r0
        ldr     r6, [lr, #4]
        add     r8, r6, #10
        add     r3, r3, r8
        ble     .L4
        ldr     r0, [lr, #8]
        adds    r0, r0, #10
        add     r3, r3, r0
.L4:
        str     r3, [ip], #4
        cmp     ip, r7
        bne     .L3
.L1:
        pop     {r4, r5, r6, r7, r8, r9, r10, pc}
.L8:
        movs    r3, #0
        mov     r0, r3
        b       .L7

loop() 采用 -O2，*-O3* 优化后汇编结果相同，而 loop_better() 则会进一步采用并行操作对循环进行向量化优化。同时 loop() 中并没有得到很好的优化，它通过使用 R2 存储计算结果，最后将寄存器的值更新到对应的内存上，看起来减少了 LOAD 操作，但实际上 STORE 操作依然存在 2n 次，并未达到最优。因此仍然需要从代码上出发进行修改来达到最优
C 中存在 restrict 关键字来让编译器避免别名问题，但 C++ 中没有该关键字，所以考虑的修改方式最好是通过临时变量来进行更好的优化

常数传播

常数传播是指替代表达式中已知常数的过程。这项事情一般在编译期时进行，但在某些时候编译器面对复杂的控制流程可能不能将所有的情况识别出来，从而导致进行一些不必要的计算。因此，手动进行传播优化是很有必要的
C++ 中可以使用 constexpr 让编译器在编译器进行对应的处理，C 自从 constexpr specifier (since C23) - cppreference.com 后才引入该关键字，所以 C 需要开发在一定情况下进行手动优化

传参优化

函数的参数传递是通过寄存器与栈进行传递，参数数量如果超出可使用寄存器的数量后会将多余的参数通过压栈的方式进行传递。因此，将大量的参数组合成对应的结构体往往能够进行更高效的访问处理
对于不同的架构，可供使用传参的寄存器数量是不一样的，比如 ArmV7，R0-R3 一般作为参数传递：

int func(int a, int b, int c, int d, int e) {
  return a + b + c + d + e;
}

void func_caller() {
  func(1, 2, 3, 4, 5);
}

汇编结果：

func(int, int, int, int, int):
        push    {r7}
        sub     sp, sp, #20
        add     r7, sp, #0
        str     r0, [r7, #12]
        str     r1, [r7, #8]
        str     r2, [r7, #4]
        str     r3, [r7]
        ldr     r2, [r7, #12]
        ldr     r3, [r7, #8]
        add     r2, r2, r3
        ldr     r3, [r7, #4]
        add     r2, r2, r3
        ldr     r3, [r7]
        add     r2, r2, r3
        ldr     r3, [r7, #24]
        add     r3, r3, r2
        mov     r0, r3
        adds    r7, r7, #20
        mov     sp, r7
        ldr     r7, [sp], #4
        bx      lr
func_caller():
        push    {r7, lr}
        sub     sp, sp, #8
        add     r7, sp, #8
        movs    r3, #5
        str     r3, [sp]
        movs    r3, #4
        movs    r2, #3
        movs    r1, #2
        movs    r0, #1
        bl      func(int, int, int, int, int)
        nop
        mov     sp, r7
        pop     {r7, pc}

可以看出，当超出 R0-R3 后，5 会被压入到栈底，进入到 func() 中寄存器的值会被临时保存到栈中然后再进行后续的操作。因此使用结构体将参数进行组合，会是一个更好的优化方式，毕竟访问寄存器的速度远远高于访问内存的速度

内联替换

函数的跳转切换需要对上下文的状态进行保存，这其中就会存在如下这四个步骤：

flowchart LR
    saveCtx(保存上下文) --> jmp(跳转执行)
    jmp --> return(返回调用处)
    return --> recoveryCtx(恢复上下文)

因此函数的调用过程就会产生开销，可以通过宏和 inline 关键字进行优化处理，但并不是所有的函数都可以通过内联的方式来进行处理，大体量的函数如果被内联进去反而会导致较差的效果

全局变量

在多个文件间共享的全局变量对于编译器来说进行优化分析是十分不利的，对于这种情况，编译器的优化通常是十分保守的，所以在一定的情况下应尽量避免使用全局变量，而且在并行编程中，对全局变量的修改也需要考虑如何协调其他消费者的状态同步
如果需要通过使用全局变量的方式来进行处理，按照 Linux 的 API 风格是最好的做法

语句级优化

1. 删除冗余语句

代码中可能存在一些死代码，这也会导致编译器无法进行合适的优化。通常情况下编译器会以 unused-xx 相关的警告来进行提示并在编译器将其丢弃

2. 代数变换

进一步简化计算语句也有利于编译优化的进行，编译器对于代数变换并不敏感，尤其是含有控制依赖的情况。所以如果有代数变换的表达式应该尽量对代数运算进行优化

3. 去除相关性

去除相关性是为了让编译器进行更好的优化，何为依赖关系？若操作A必须先于B发生，那么就称B依赖于A，那么A与B就存在依赖关系
依赖关系的存在不利于编译器进行语句移动以及向量化等优化方式的展开，因此需要开发人员对依赖关系进行破除，帮助编译器进行更好的优化
依赖关系分为数据依赖和控制依赖两种类型
数据依赖是指两个操作访问同一个变量，且这两个操作中有一个写操作，大概分为三种：

依赖关系	示例	说明
真依赖	`a = 1; b = a;`	对 `a` 进行先写后读
输出依赖	`a = 1; a = 2;`	对 `a` 进行先写后写
反依赖	`a = b; b = 1;`	对 `b` 进行先读后写

书上将这三种依赖又分为真依赖和伪依赖（输出依赖，反依赖），不过这里分为强依赖和弱依赖感觉更加合适：

强依赖（真依赖）：语句间出现了先后的数据值传递，不容易消除
弱依赖（输出依赖，反依赖）：语句间没有引发数据值的传递，比较容易消除

控制依赖是由程序的控制结构所引起，比如：

void func(int a, int b) {
  if (a > b)                // S1
    printf("%d\n", a);      // S2
  ...
}

这里的 S2 是否执行完全依赖于 S1 的判断结果
有一些常用方法

1. 标量扩展

在 C/C++ 中常见的变量类型均属于标量，标量扩展则是将循环中的标量引用转换成临时数组进行替换，这样有利于编译器对循环进一步向量化：

void func() {
  int A[10] = 
    { 1, 22, 333, 4444, 55555, 413, 2333, 122, 1999, 10 };
  int N = sizeof(A) / sizeof(int);
  int T;
  int B[10] = { 0 };
  for (int i = 0; i < N; i++) {
    T = A[i];
    A[i] = B[i];
    B[i] = T;
  }
  // 阻止编译器优化掉上面的逻辑
  for (int i = 0; i < N; i++) {
    printf("%d %d\n", A[i], B[i]);
  }
}

➡

void func_vec() {
  int A[10] = 
    { 1, 22, 333, 4444, 55555, 413, 2333, 122, 1999, 10 };
  int N = sizeof(A) / sizeof(int);
  int T[N];
  int B[10] = { 0 };
  for (int i = 0; i < N; i++) {
    T[i] = A[i];
    A[i] = B[i];
    B[i] = T[i];
  }
  // 阻止编译器优化掉上面的逻辑
  for (int i = 0; i < N; i++) {
    printf("%d %d\n", A[i], B[i]);
  }
}

这个书上的例子有一定的问题，采用 GCC 不同等优化编译得到汇编后发现，func_vec() 中的 T[N] 在循环中会被优化成寄存器取代：

# -O1
.L2:
        ldr     r1, [r3]
        ldr     r0, [r2]
        str     r0, [r3], #4
        str     r1, [r2], #4
        cmp     r3, r6
        bne     .L2
        movw    r7, #:lower16:.LC1
        movt    r7, #:upper16:.LC1

# -O2
.L7:
        ldr     r7, [lr]
.L3:
        ldr     r3, [ip]
        str     r7, [ip], #4
        str     r3, [lr], #4
        cmp     ip, r5
        bne     .L7
        movw    r7, #:lower16:.LC1
        movt    r7, #:upper16:.LC1

循环中的行为和不采用向量化的函数一致，所以其实并没有得到书上预期中的优化效果，不过 GCC 优化策略也是合理的，访问寄存器远比写到内存要快

2. 标量重命名

这属于语句之间存在强依赖，比如：

void func() {
  int a = 3, b = 0, y, z, T;
  T = 2;        // S1
  y = T + T;    // S2
  T = a - b;    // S3
  z = T * T;    // S4
  // ...
}

这里可以看出，S1 - S4 之间出现了强依赖，导致了需要按照 4 条语句间顺序进行执行，对于编译器优化与指令重排来说并不是十分友好。其实不难看出可以将总体语句划分出 S1&S2 与 S3&S4 两块，那么 T 的作用其实局限在了两块内，并不需要上下块进行依靠，因此改进如下：

void func() {
  int a = 3, b = 0, y, z, T, T1;
  T = 2;          // S1
  y = T + T;      // S2
  T1 = a - b;     // S3
  z = T1 * T1;    // S4
  // ...
}

编译器在一定可能的情况下会对其进行优化？

公共子表达式优化

当程序中存在多个相同的表达式，使用临时变量进行归纳即可，避免重复计算

分支语句优化

处理器运用流水线机制来提高性能，而流水线机制需要填充指令来进行依次的执行，那么遇到分支语句与条件跳转时，会导致后续的指令失效并重新填充流水线，这将导致性能的损失。所以这里有一些方法来进行优化

1. 合并判断条件

简化判断条件语句，有利于流水线性能的提升

2. 生成选择指令

三目运算符即选择指令

只有一些平台支持选择指令

3. 运用条件编译

按照不同的条件来控制是否选择编译这段代码。实际上是针对不同的平台进行对应的实现，同样避免全量编译

4. 移除分支语句

运用查表法能够有利于分支跳转优化，如果分支的结果可以通过计算得出那么可以将结果转换成数组进行存储，这样有利于减少分支跳转

5. 平衡分支跳转

switch 是很常用的一种语法方式，对于过多的分支可以采取平衡的策略来做更好的跳转，比如：

switch (CASE) {
  case 1: func_1();
  case 2: func_2();
  case 4: func_4();
  case 6: func_6();
  case 8: func_9();
  case 10: func_10();
}

流程如下：

flowchart LR
    CASE_1(CASE == 1)
    CASE_2(CASE == 2)
    CASE_4(CASE == 4)
    CASE_6(CASE == 6)
    CASE_8(CASE == 8)
    CASE_10(CASE == 10)

    CASE_1 --> CASE_2 --> CASE_4
    CASE_4 --> CASE_6 --> CASE_8 --> CASE_10

可以将分支进行平衡：

flowchart TD
    CASE_0(CASE < 5)
    CASE_1(CASE < 3)
    CASE_2(CASE < 7)
    CASE_3(CASE < 2)
    CASE_4(CASE = 4)
    CASE_5(CASE = 6)
    CASE_6(CASE < 9)
    CASE_7(CASE = 1)
    CASE_8(CASE = 2)
    CASE_9(CASE = 8)
    CASE_10(CASE = 10)

    CASE_0 --> CASE_1
    CASE_0 --> CASE_2
    CASE_1 --> CASE_3
    CASE_1 --> CASE_4
    CASE_3 --> CASE_7
    CASE_3 --> CASE_8

    CASE_2 --> CASE_5
    CASE_2 --> CASE_6
    CASE_6 --> CASE_9
    CASE_6 --> CASE_10

总结

不难看出过程优化其实算得上编程上的一些细节与习惯，平常编写的时候多留意反而会取得更好的效果

ZYXeeker`s blog

程序性能优化 —— 过程优化

前言

方法