《深入理解计算机系统》之优化程序性能(第五章)笔记

  1. 1. 减少不必要的开销
    1. 1.1. 不必要的函数调用
    2. 1.2. 不必要的内存引用
  2. 2. 让代码可以被编译器优化
    1. 2.1. 可能阻止编译器优化的情况
  3. 3. 利用现代处理器的硬件特性
    1. 3.1. 指令的并行执行
    2. 3.2. 循环展开
      1. 3.2.1. k x 1 循环展开
      2. 3.2.2. k x k 循环展开

高三毕业的暑假就看了这本书,但是当时水平很浅,只能看进去前两章,现在又回来继续往后看。

这本书是了解计算机的一本好书,光是前两章的内容就让我在一段时间学习计算机相关课程的速度飞快。

这本书的第五章主要讲解如何优化程序性能。作者的讲解方式很适合我学习,但是结构上不太适合复习。因此我将其中的知识点重新排列组合,方便我以后复习。

笔记正文:

优化程序性能的方式主要可概括成三种:

  1. 减少不必要的开销 (比如不必要的函数调用、内存引用)
  2. 让代码可以被编译器优化 (比如内存引用可能会阻止编译器优化)
  3. 利用现代处理器的硬件特性 (利用超标量处理器指令并行特性)

减少不必要的开销

这是最简单的优化方式,很多时候只要稍微留意就能注意到可以改善的地方。

不必要的函数调用

比如书里很经典的一个例子,在循环里调用一个返回值固定的函数。

1
2
3
4
for(int i = 0; i < strlen(str); ++i)
{
// do sth...
}

上面的代码,每一次循环,都会调用 strlen(str),计算一次字符串的长度。而计算一次字符串的长度需要遍历整个字符串以寻找字符串末尾的 ‘\0’ 字符。这种情况下效率肯定是很低的。

如果字符串的长度是不会改变的,那么更好的写法是只调用一次 strlen。

1
2
3
4
5
int length = strlen(str);
for(int i = 0; i < length; ++i)
{
// do sth...
}

在我看这本书之前我就听说现代编译器(不知道是哪个语言)能够优化上面的代码。
但是在这本书里指出,C 语言编译器可能会认为 strlen(str) 的返回值是变化的,从而阻止了优化。

在 C++ 中,vector<T> 根据索引访问元素有两种方式,一种是使用 operator[],另一种是使用 at() 成员函数。这两个函数是有区别的,at() 函数会进行越界检查,如果索引越界会触发异常,而 operator[] 则不会。

如果循环中,可以保证逻辑上不会出现越界访问,那么每次都进行越界检查显然是没必要的。

1
2
3
4
5
6
7
8
9
vector<int> vec = {1,2,3,4};
for(int i = 0; i < vec.size(); ++i)
{
// 在这个循环里,通过 i 访问 vec 不会导致越界
// 如果用 at 函数进行越界检查是没必要的
cout << vec[i] << endl; // good
cout << vec.at(i) << endl; // bad

}

C++ 标准库把最常用的 operator[] 设计为不进行越界检查估计就是为了效率。

编译器的内联优化也可以消除不必要的函数调用,C++ 通过 inline 关键词标记一个函数为内联函数,但这不是强制性的约束,是否进行内联优化取决于编译器。

不必要的内存引用

这是我以前很少注意到的细节,这个细节需要结合代码来分析。

比如下面这个 sum1 函数,它对数组进行求和,并把结果存到 result 里。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void sum1(int* array, int length, int* result)
{
*result = 0;
for(int i = 0; i < length; ++i)
{
*result += array[i];
}
}

void sum2(int* array, int length, int* result)
{
int tmp = 0;
for(int i = 0; i < length; ++i)
{
tmp += array[i];
}
*result = tmp;
}

result 是一个 int 指针,它指向一片内存。这个函数的循环,将会多次通过 result 访问这一片内存。

对于函数 sum2,会有更好的效率。因为临时变量 tmp 完全可以存到某个寄存器里,CPU 在循环里只需多次访问一个寄存器。CPU 访问内存的速度和 CPU 访问寄存器的速度是不一样的,CPU 访问寄存器的效率要远远大于访问内存。

我觉得 CPU 会把 array 的数据从内存复制到高速缓存里来提高效率,这本书似乎也有提到,但是我还没看完。

让代码可以被编译器优化

可能阻止编译器优化的情况

下面这两个函数,直觉上看 func2 似乎是 func1 更优雅的实现,所以现代编译器把 func1 优化成 func2 是行得通。函数 func1 有 4 次内存引用。而 func2 只有两次,如果能这么进行优化,那执行效率会有所提升。

1
2
3
4
5
6
7
8
9
10
void func1(int* a, int* b)
{
*a += *b;
*a += *b;
}

void func2(int* a, int* b)
{
*a += 2 * (*b);
}

但是实际上,编译器可能不会做出这样的优化。这是因为当参数 a 和 参数 b 的指针是同一个指针时,两个函数的计算结果是不同的。

比如:

1
2
3
int v = 1;
func1(&v, &v); // return: 4
func2(&v, &v); // return: 3

编译器的优化必须保证优化前后的一致性,所以编译器不会把 func1 优化成 func2

这里我觉得可以总结出一条结论:相同的内存引用,可能会阻止编译器优化。

利用现代处理器的硬件特性

不了解现代 CPU 的工作细节,我看完也还是一知半解啊。所以以下内容很可能有错误,请批评指正。

X86 中一条汇编指令可能要多个时钟周期才能完成。而且这些指令是有可能乱序执行的。线代处理器使用一种分支预测技术,在遇到分支(if语句可能产生分支)的时候,处理器不会等待条件检测完成再去选择分支,而是先猜测一条分支是成立的,执行这条分支的指令。如果分支预测错误,那么代价是很大的:之前执行的结果只能全部丢弃,要重新执行正确分支的指令。

这些现代处理器的特性,也会对程序性能有影响。

指令的并行执行

上面提到的 sum2 函数,它循环部分的汇编代码如下(Clang 12.0 使用 O1 优化):

1
2
3
4
5
.LBB1_4:    # =>This Inner Loop Header: Depth=1
add ecx, dword ptr [rdi + 4*rsi]
add rsi, 1
cmp rax, rsi
jne .LBB1_4

这一段汇编代码中,实际上并不只有 addaddcmpjne 四个操作,比如还涉及从内存中加载数据的操作( dword ptr [rdi + 4*rsi] )。在加载数据之后,比较关键的一个点是,两个 add 指令是可以同时运行的。

这是因为两个 add 指令直接并不存在数据依赖。第二个 add 和 cmp 指令就不能同时进行,因为 cmp 使用了 rsi 寄存器的值,必须要等第二个 add 指令完成之后,cmp 计算的值才是正确的。

第一个 add 指令和第二个 add 指令虽然也都用到了 rsi 寄存器,但是第一个 add 指令用到的 rsi 寄存器,发生在加载数据的时候。真正进行 add 计算时,已经不再使用 rsi 寄存器的值了。

BUT! 如果我理解没问题的话,我这里就有个疑惑了:人可以分析出来这些,但是 CPU 怎么知道这些指令没有数据上的依赖呢?

循环展开

这是我觉得最有意思的部分,循环展开优化是我以前就了解过的编译器优化技术,这本书让我知道了循环展开优化里的各种细节。

k x 1 循环展开

前文提到的 sum2 函数的循环要执行 n 次加法和 n 次判断(判断 i 和 length 的大小)。循环展开优化,将每次循环做 1 次加法改成做 k 次加法。这样优化最终还是要做 n 次加法,但是循环的次数以及判断的次数都减少了。(减少了 cmp 指令和 jmp 指令的执行)

这种循环展开称为 k x 1 循环展开,一次循环计算 k 个元素而累计值存到 1 个变量中。

比如当 k = 2 时,函数 sum2 可以展开成:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void sum2(int* array, int length, int* result)
{
int tmp = 0;
int i;
// 1 次循环加 2 个元素
for(i = 0; i < length - 1; i += 2)
{
tmp = (tmp + array[i]) + array[i + 1];
}
// 把剩余的元素都加上
for(; i < length; ++i)
{
tmp = tmp + array[i];
}
*result = tmp;
}

k x k 循环展开

k x 1 次循环展开的计算结果都存到 1 个变量中,这导致第 t 次运算都要等第 t - 1 次运算结束后才能进行。如果有多个结果变量,那么这 k 次运算就可以并行执行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void sum2(int* array, int length, int* result)
{
int tmp1 = 0;
int tmp2 = 0;
int i;
// 1 次循环加 2 个元素
for(i = 0; i < length - 1; i += 2)
{
// 现在,这两个加法运算没有关联了,可以并行执行
tmp1 = tmp1 + array[i];
tmp2 = tmp2 + array[i + 1];
}
// 把剩余的元素都加上
for(; i < length; ++i)
{
tmp1 = tmp1 + array[i];
}
*result = tmp1 + tmp2;
}

最后,循环展开的代码不需要自己写,编译器优化会自动完成的。