程序优化

• 编译器优化
  • 原理和要求
    • 变换程序结构，使其运行更快，占用内存更少。
    • 不改变程序运行的输出，一般不改变程序的复杂度。
  • 局部优化
    • 一般只在一个语句块中进行。
    • 常量折叠：编译期计算常量表达式的值，并用结果代替。
    • 强度削弱：把开销大的计算用更小的方式替代，如用移位和加法运算代替常数乘法。
    • 死代码删除：删除无用变量和不会被运行的函数、分支等。
    • 公共表达式提取：把多个表达式的重复部分提取出来，只计算一次。
  • 全局优化
    • 内联：把被调用函数的代码展开到调用处。内联后可能可以进行更多局部优化。
    • 代码外提：把重复计算的表达式提取到控制结构外。
    • 循环转换：如交换嵌套循环的顺序、循环体融合、把嵌套循环等效变换为单层循环、循环展开。
  • 优化的障碍
    • 内存别名：存在对同一内存区域的多个可变引用时，存在正确性问题，难以优化。
    • 函数调用：函数可能存在副作用，难以对函数的行为做出判断。
    • 非可结合运算：如浮点运算，改变运算顺序可能改变结果。
• 机器相关优化
  • 分支预测
    • 现代处理器流水线多，分支预测错误的惩罚较大，分支预测需要很高的准确率。
    • 简单启发式分支预测：
      • 如果跳转目标地址比当前更小，大概率是循环，则选择跳转。
      • 如果跳转目标地址比当前更大，大概率是条件选择，则选择不跳转。
    • 避免分支：
      • 转换循环。
      • 循环展开。
      • 使用 cmov* 指令。
      • 避免间接访问，如函数指针调用、虚函数。
  • 循环展开
    • 2x1
      • 在一次循环中，同时累加两个元素，计算顺序都是左结合。

      • int i = 0, x = 0, limit = length - 1;
        for (; i < limit; i += 2) {
            x = (x + d[i]) + d[i + 1];
        }
        for (; i < length; i++) {
            x = x + d[i];
        }
    • 2x1a
      • 在一次循环中，同时累加两个元素，计算顺序是先右结合再左结合。
      • 比 2x1 更好一点，减少了数据依赖，下一次循环处理器流水线可以等待更少的阶段。

      • int i = 0, x = 0, limit = length - 1;
        for (; i < limit; i += 2) {
            x = x + (d[i] + d[i + 1]);
        }
        for (; i < length; i++) {
            x = x + d[i];
        }
    • 2x2
      • 在一次循环中，同时累加两个元素，使用两个累加变量，最后相加。
      • 比 2x1a 更好，两个数据流相互独立处理。

      • int i = 0, x0 = 0, x1 = 0, limit = length - 1;
        for (; i < limit; i += 2) {
            x0 = x0 + d[i];
            x1 = x1 + d[i + 1];
        }
        for (; i < length; i++) {
            x0 = x0 + d[i];
        }
        int x = x0 + x1;