深入理解计算机系统第 9 课 Program Optimization

这一讲可谓是全书最实用的部分，介绍如何基于代码执行的机制，去优化我们的代码。

通用代码优化技巧

即使是常数项系数的操作，同样可能影响性能。性能的优化是一个多层级的过程：算法、数据表示、过程和循环，都是需要考虑的层次。于是，这就要求我们需要对系统有一定的了解，例如：

程序是如何编译和执行的
现代处理器和内存是如何工作的
如何衡量程序的性能以及找出瓶颈
如何保持代码模块化的前提下，提高程序性能

最根源的优化是对编译器的优化，比方说再寄存器分配、代码排序和选择、死代码消除、效率提升等方面，都可以由编译器做一定的辅助工作。

但是因为这毕竟是一个自动的过程，而代码本身可以非常多样，在不能改变程序行为的前提下，很多时候编译器的优化策略是趋于保守的。并且大部分用来优化的信息来自于过程和静态信息，很难充分进行动态优化。

接下来会介绍一些我们自己需要注意的地方，而不是依赖处理器或者编译器来解决

代码移动

如果一个表达式总是得到同样的结果，最好把它移动到循环外面，这样只需要计算一次。编译器有时候可以自动完成，比如说使用 -O1 优化。一个例子：

void set_row(double *a, double *b, long i, long n){
    long j;
    for (j = 0; j < n; j++){
        a[n*i + j] = b[j];
    }
}

这里 n*i 是重复被计算的，可以放到循环外面

long j;
int ni = n * i;
for (j = 0; j < n; j++){
    a[ni + j] = b[j];
}

减少计算强度

用更简单的表达式来完成用时较久的操作，例如 16*x 就可以用 x << 4 代替，一个比较明显的例子是，可以把乘积转化位一系列的加法，如下：

for (i = 0; i < n; i++){
    int ni = n * i;
    for (j = 0; j < n; j++)
        a[ni + j] = b[j];
}

可以把 n*i 用加法代替，比如：

int ni = 0;
for (i = 0; i < n; i++){
    for (j = 0; j < n; j++)
        a[ni + j] = b[j];
    ni += n;
}

公共子表达式

可以重用部分表达式的计算结果，例如：

/* Sum neighbors of i, j */
up =    val[(i-1)*n + j  ];
down =  val[(i+1)*n + j  ];
left =  val[i*n     + j-1];
right = val[i*n     + j+1];
sum = up + down + left + right;

可以优化为

long inj = i*n + j;
up =    val[inj - n];
down =  val[inj + n];
left =  val[inj - 1];
right = val[inj + 1];
sum = up + down + left + right;

虽然说，现代处理器对乘法也有很好的优化，但是从 3 次乘法优化到 1 次，总是不错的主意

阻碍代码优化的因素

过程调用

我们先来看一段代码，找找有什么问题：

void lower1(char *s){
    size_t i;
    for (i = 0; i < strlen(s); i++)
        if (s[i] >= 'A' && s[i] <= 'Z')
            s[i] -= ('A' - 'a');
}

问题在于，在字符串长度增加的时候，时间复杂度是二次方的！

问题就在于，每次循环中都会调用一次 strlen(s)，而这个函数本身需要通过遍历字符串来取得长度，因此时间复杂度就成了二次方。

可以怎么优化呢？简单，那么只计算一次就好了：

void lower2(char *s){
    size_t i;
    size_t len = strlen(s);
    for (i = 0; i < len; i++)
        if (s[i] >= 'A' && s[i] <= 'Z')
            s[i] -= ('A' - 'a');
}