软件性能工程-优化技巧

1. Data Structures

1.1 Packing and Encoding

如果一个数据需要多个部分表示，比如日期需要由年月日三部分组成，一般可能考虑定义三个整数来表示。我们还可以考虑，将三个部分压缩到一个整数中：

c
1
2
3
4
5
typedef struct {
    int year: 13;
    int month: 4;
    int day: 5;
} date_t;

其中我们假设 year 的值域大小为 $2^{13}$、month 值域大小为 $2^4$（足以表示 12 个月），day 值域大小为 $2^5$（足以表示 31 天）。这个被称为位域语法，编译器将会自动选择一个足够大的整型存储。在访问具体的字段时，编译器将会自动进行位运算，将字段取出。

将数据放入尽可能少的量中可以减少内存访问次数，从而提高性能。

1.2 Augmentation

我们可以在数据结构中多记录一些东西来使得操作变快。例如我们有一个链表，现在想在末尾添加一个元素。如果之前已有的元素数量很多，我们要花费很多的时间从前往后一直寻找到最后一个元素，然后再添加元素。

我们可以考虑再记录一个 tail 指针，指向最后一个元素，这样直接 $O(1)$ 添加元素了：

1.3 Precomputing

预处理在算竞中用烂了，不用多说。

除了在运行时预处理，还可以直接打表，生成代码，例如：

除此之外我还想到了之前在程序设计课上分享的 constexpr 来预处理：

1.4 Caching

如果一个函数值的计算比较耗费时间，那么我们可以把这个函数值缓存：

c
1
2
3
inline double hypo(double A, double B) {
    return sqrt(A*A + B*B);
}

写成：

当然这个例子不适用，在其他的情况中多缓存几个值应该会好些。

1.5 Sparsity

对于如图所示的矩阵乘法，如果我们直接计算，时间复杂度就是 $O(n^2)$ 的。但我们发现左边这个矩阵有很多地方都是 $0$，$0$ 乘上任何数都是 $0$，我们很多时间都浪费在对 $0$ 进行运算上。

我们可以将这种矩阵表示成一种 Compressed Sparsity Row (CSR) 的形式：

对于每一行，cols 数组表示哪一列是非 0 的，vals 数组表示这个非 0 的值是多少。然后我们把每一行的 cols 和 vals 都放在一起，并用 rows[i] 表示第 $i$ 行所对应的 cols 和 vals 的起始位置。

我们可以在 $O(n^2)$ 的时间内得到一个 $O(n+nnz)$ 的数据结构。其中 $nnz$ 为非 0 元素的个数。

然后使用下面的算法进行矩阵乘法：

时间复杂度为 $O(nnz)$

对于图，也有对应的手法：

edges 数组存放一个点连出去的边。我个人觉得和直接用 vector 建图的差距不大。

这种图的表示方式还可以再进行压缩，首先每个点对应 edges 元素从小到大排序。然后每个点对应的第一个 edges 元素减去该点的编号，即 edges[offsets[v]]-=v，然后 edges 中剩余的元素做差分，即 edges[offsets[v]+i]-=edges[offsets[v]+i-1]。这么做的原因是让 edges 中元素的绝对值尽可能小，从而使得能用尽可能少的位/字节表示：

然后就有两种方案：

k-bit codes

每个 edges 元素的值用若干个 k 位数据表示，其中低 k-1 位用于编码数据，第 k 位为 continue bit，如果其为 1 就说明还没编码完，需要继续往后读 k 位。这样的话每个元素所使用的位的数量可能是不一样的。

这样做有一个问题，我们需要判断第 k 位，而这个分支判断是不可预测的，分支预测的开销会比较大。

另一个方法

这篇论文 介绍了不用 continue bit 的方法。首先用一个字节来表示一个 header，header 的高 2 位表示后续每个整数所使用的字节的大小（1 到 4 个字节），然后低 6 位表示后面有几个整数：

2. Logic

2.1 Constant Folding and Propagation

就是直接传播常量，把能在编译期算出来的东西算出来，没什么好说的。应该是编译器自己能搞定的。

2.2 Common-Subexpression Elimination

如果有表达式多次出现，那么我们可以只计算一个，不用重复计算。

c
1
2
3
4
a = b + c;
b = a - d;
c = b + c;
d = a - d;

可以写为：

c
1
2
3
4
a = b + c;
b = a - d;
c = b + c;
d = b;

由于第三行和第一行的 b 发生了改变，所以我们不消掉第三行的表达式。

2.3 Algebraic Identities

我们可以使用一些代数上的变化来使程序变快：

collides 中计算 d 的时候需要使用 sqrt 函数，而这个函数的计算并非是常数的时间，使得 d 计算比较慢。但 d 后面只是去跟 b->r + b2->r 比较，那么我们可以两边平方，不用再使用 sqrt 了：

2.4 Short-Circuiting

有时候我们可能算到一半就知道结果了，后面的计算就没必要了。

比如判断一个非负数序列之和是否大于某个 limit，那么如果在循环累加的时候已经超过 limit 就可以直接返回了。

除此之外，&& 和 || 有短路特性。在判断的时候，可以把容易成立的条件，或是耗费比较低的条件放在前面：

一般来说空格和换行符会比较常见，所以后者选择将这两个的判断提前。

2.5 Creating a Fast Path

在进行比较复杂耗时的判断之前可以先看一下有没有一些简单且耗时短的特殊情况。

比如判断两球是否相交，一个特殊情况是，如果包裹两个球的正方形没有相交的话那么这两个球就不会相交，而判断正方形相交是简单的。

当然上述代码中的 b1-> r + b2->r 还可以用到 2.2 所说的优化，把他们提出来。

2.6 Combining Tests

比如我们想将下面这个真值表变成函数的话，直接写的话需要各种 if 判断，可能会出现分支预测错误带来的严重的性能下降：

我们可以把 a 、b 、c 三个参数压成一个整数，然后使用 switch 判断：

3. Loops

3.1 Hoisting

循环内每次循环计算结果都一样的代码可以提出来，不要重复计算：

3.2 Sentinels

Sentinels 是一种特殊值，放在数据结构中，简化条件判断。比如：

A 数组最后的 INT64_MAX 和 1 可以保证后面的 while 循环一定可以退出。后面再判断循环退出的位置，就可以消去新加入的值所带来的影响。并且，前者每次循环需要进行两次判断，而后者只需要进行一次，速度更快。

3.3 Loop Unrolling

在 CSAPP 中见过且用过，不多说。

不过这里还有一点值得讨论。如果循环展开过多，会使得循环体内的指令数很多，这样就会使得指令的空间局部性比较差，反而降低性能。

3.4 Loop Fusion

将能合并在一起的循环合并到一起：

3.5 Eliminating Wasted Iterations

我们可以通过调整循环边界来减少不必要的循环：

4. Functions

4.1 Inlining

函数内联大家都很熟悉了，不多说。

不过在 C 语言中，有如下的说法：

如果一个包含函数体的函数定义只有 inline 修饰是过不了编译的，因为 inline 是建议编译器进行内联优化，编译器不会生成函数的符号。此时，对于一个函数调用，编译器可以选择内联，但如果编译器不考虑内联的话，会出现链接错误。所以一种方案是写一个带 inline 不带函数体的定义和一个不带 inline 带函数体的定义：

c
1
2
3
4
inline int func();
int func() {
    ....
}

另一个解决方案是写 static inline int func() {...}，多加一个 static 修饰，使得即使没内联，每个 .c 文件也都生成一个局部的符号，不会有链接冲突。

为了更严格地控制编译器内联优化的行为，我们有：

• __attribute__((always_inline))：强制编译器去内联函数
• __attribute__((no_inline))：强制编译器不去内联函数

4.2 Tail-Recursion Elimination

这个优化说的是，如果一个递归函数，最后的行为是进行递归（也就是尾递归），那么我们起始可以不去递归，而是复用当前的函数（更改下参数再从头开始跑一遍），这样可以减少函数调用的开销：

4.3 Coarsening Recursion

众所周知，一些时间复杂度较低的算法，只是在数据量较大时才显出优势。而在低数据量时，时间复杂度高的算法未必比复杂度低的算法更慢。于是我们设置一个临界，在临界以下考虑使用别的算法：