优化程序性能

在这部分仍然涉及了不少汇编的底层内容，需要仔细多读几遍，后续还是要重新阅读CSAPP这本书，前面的计算机基础只是在浅显的翻过。

编写高效的程序的建议

选择合适的算法和数据结构

编译器的能力和局限性

探索并行化

表示程序的性能

引入每元素的周期数（CPI）作为表示程序的性能，执行每条指令需要的时钟周期。

系统有“4GHz”处理器，表示处理器时钟的运行频率为每秒4×10⁹个周期。

代码移动

如果一个表达式总是得到同样的结果，最好把它移动到循环外面，这样只需要计算一次。编译器有时候可以自动完成，比如说使用 -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;

小心过程调用

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

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)，而这个函数本身需要通过遍历字符串来取得长度，因此时间复杂度就成了二次方。

编译器出于安全的原因，不会主动优化，比如如果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');
}

数据流图

了解处理器的算数处理性能，便于更好的优化。

根据数据流图来找到程序的关键路径，然后找到优化路径。

循环展开

通过增加每次迭代计算的元素的数量，减少循环的迭代次数，同时需要注意循环边界的更改。