优化程序性能方法概览

本文为CSAPP的第五章的笔记。CSAPP作为入门超算优化的读物，不出意外的话，会有第六章的笔记，这篇笔记不会成为一个系列。但CSAPP是一本不可多得的好书，非常推荐大家读英文原版！

本章如果不太懂指针也没有太大关系，尽力写了一些讲解，希望大家都能看懂，并且都能动手试试，如有错误欢迎指正。

绪论

要想了解优化计算，我们首先要了解处理器的运作， 我们需要一个目标机器的模型，指明如何处理指令，以及各个操作的时序特性。学过汇编语言的我们都知道，编译器必须知道时序信息，才能够确定是用一条乘法指令还是用移位和加法的组合，对嵌入式技术人员来说，这就是类似于时钟的概念。

然后，我们利用处理器提供的指令级并行能力，同时执行多条指令。

代码剖析程序是我们的好帮手，它是测量程序各个部分性能的工具，帮助找到代码中低效率的地方，确定程序中我们应该着重优化的部分。

代码优化远不是将本书给出的代码视作一个框架那么简单，实际上是存在相当多的试错试验的。看上去很小的变化会导致性能上很大的变化，一些被寄予厚望的技术也可能是无效的。我们很难确切解释为什么某段代码序列具有特定的执行时间，性能可能依赖于处理器设计的许多细节特性。

研究一个内循环的代码是研究优化计算的良好开端，这样可以识别出降低性能的属性。例如，过多的内存引用和寄存器使用不当。从汇编代码开始，我们还可以预测什么操作会并行执行，以及它们会如何使用处理器资源。确认关键路径（循环的反复执行过程中形成的数据相关链）可以决定执行一个循环所需要的时间。

不断修改源代码，试图欺骗编译器产生有效的代码，确实是编写很多高性能程序的方式。

你可以撰写“编译器友好型”以及“缓存友好型”的程序。针对不同的目标硬件平台，做出特定的优化。但这一切都是基于对于系统充分的理解，以及程序功能正确，回归测试到位。

1. 优化编译器的能力和局限性

现代编译器运用复杂精细的算法来确定一个程序计算的是什么值，以及如何被使用，然后利用一些机会来简化表达式。在几个不同的地方使用同一个计算，以及降低一个给定的计算必须被执行的次数。

命令行选项“-Og”调用gcc是让gcc使用一组基本的优化。-O0是传统的选项，因为是最适合调试的。-O1，-O2或更高则是让gcc使用更大量的优化。

gcc -Og xxx.c # 有优化
gcc -O0 xxx.c # 无优化

我在命令行试了一下： 然后使用Windows Powershell自带的命令Measure-command查看有优化和无优化的运行时间对比：

对比还是比较明显的，有8millis左右的差异！

在这个程序里，我只是使用了printf("hello world")这样的语句，在一些非常大且复杂的程序中，优化的效率会更加明显。

大多数gcc参与编译的项目中，优化级别-O2已经成为了被接受的标准。本书主要考虑以优化级别-O1编译出的代码，重点还是放在C语言函数的不同写法，以此优化性能。

编译器必须对程序使用安全的优化，必须考虑所有会遇到的情况。但是程序的功能不应该变化。当然，这是两边共同努力的结果，程序员也应该思考如何将程序写的更容易转化为机器代码。

内存别名使用

以下两个过程，可以帮助我们理解决定一种程序转换是否安全有多难：

void twiddle1(long *xp, long *yp)
{
	*xp += *yp;
	*xp += *yp;
}

void twiddle2(long *xp, long *yp)
{
	*xp += 2 * *yp; 
}

两个过程似乎是做了相同的事情，都是把“指针yp指示的位置的值加到xp指示的位置的值”这件事做了两次。

但内存引用次数不一样，这就导致了效率的不同。

twiddle2效率更高，它只需要引用3次内存(读xp，读yp，写xp)；twiddle1有两句，所以有23=6次内存引用。

但还需要注意，我们要考虑xp等于yp的情况：

void twiddle1(long *xp, long *yp)
{
	*xp += *xp;
	*xp += *xp;
}

void twiddle2(long *xp, long *yp)
{
	*xp += 2 * *xp; 
}

twiddle1的情况下，*xp增加4倍，2的情况下，增加了3倍。编译器不知道twiddle1会如何被调用，因此它必须假设xp和yp可能会相等。因此，它不能产生twiddle2风格的代码作为twiddle1的优化版本。

两个指针可能指向同一个内存位置的情况即为内存别名使用。

只执行安全的优化中，编译器必须假设不同的指针可能会指向内存中同一个位置。对于一个使用指针变量p和q的程序，考虑下面的代码序列：

x = 1000;
y = 3000;
*q = y;
*p = x;
t1 = *q;

t1的计算值依赖于指针p和q是否指向内存中同一个位置。如果不是，t1等于3000，如果是，t1等于1000。这提示我们，编译器必须能够确定两个指针是否指向同一个位置。

让我们再回顾一下指针的取值过程，带*号的是指针p所指向的位置，p当然就是指针本身。指针自己的内容是0x00400000一类的地址，*p则是这个地址存储的值。

这个地址可以看作是快递箱，箱子里存储了数值1000或者是3000等。在这里，* q=y意思是把q指向的地址存储的值拿出来赋为y的3000，* p=x的意思是把* p存储的值拿出来赋为1000。那么，t1 = * q 当然就是把* q里的值拿出来赋给t1。

有趣的是，地址可不同于值，因为地址是唯一的，地址里的值也只能同时存在一个。再明确点说，快递柜——我们的内存空间里所有的地址都是编号好了的，每一个快递箱——我们的每个地址，一次只能放一件快递（现实生活中一般是这样吧）——也就是一个数值，一个地址只能存放一个值。我们可以把指针看作是取件码，假设情况非常简单，没有任何保密措施——我们的取件码就等于快递箱地址（假设快递小哥凭拿到的取件码放快递）。那么靠这个取件码就能找到这个快递箱里存放的快递了，也就是我们的数值！这就是取值的过程。

所以，我们可以解释为什么t1的计算值依赖于指针p和q是否指向内存中同一个位置：这就是撞车！如果指向了内存同一个位置，那么，用上面取快递的比喻，这很好理解，因为取件码怎么能一样呢？！

我们来看看如果不是同一个位置：现在假设快递柜有两个箱子，地址分别是0x00400000和0x00400001，p是0x00400000，q是0x00400001。有两件快递，x = 1000; y = 3000;

那么，*q = y; 快递小哥把3000放进0x00400000，*p = x; 把1000放进0x00400001。我们的t1去找取件码q所指代的地址所存放的数值，当然非常轻松，那就是3000，没有什么异议可言。看起来非常有秩序，这是因为在这种情况下，箱子里的快递没有被换过。

如果是同一个位置呢？那就说明p和q这两个取件码居然是一样的，但是快递小哥也很无奈，他只能先放进去y，再用x替代y。这样，我们的t1最后拿到的就会是1000。

这是一个主要的妨碍优化的因素，也可能会严重限制编译器产生优化代码机会的程序。所以，要想优化，我们必须全方面的考虑这个问题。

书中也给了一道练习题以供思考：

void Swap(long *xp, long *yp)
{
	*xp = *xp + *yp;
	*yp = *xp - *yp;
	*xp = *xp - *yp;
}

在这种情况下，xp如果等于yp，我们假设一开始* yp = 2；那么首先第一行代码过去，*xp就会变成4；第二行代码过去，* yp 就是0；第三行过去，* xp还是0。所以* yp肯定也是0。

很明显，假设xp和yp不同，但装的都是2的话，那么，第一行代码过去，*xp变成4，*yp不变还是2；第二行过去，*yp变成2，*xp不变还是4,；第三行代码过去，*xp变成了2，*yp也是2。这和xp，yp指向同一个位置的情况简直是大相径庭！

函数调用

还有一个妨碍优化的因素是函数调用。请看下面这个过程：

long f();
long func1(){
	return f()+f()+f()+f();
}
long func2(){
	return 4*f();
}

func2和func1的区别就是调用次数的不同，fun2只调用了一次f()。

考虑这种情况：

long counter = 0;
long f(){
	return counter ++ ;
}

这个函数使用的是全局变量counter，修改了全局程序状态的一部分，改变调用它的次数会改变程序的行为。

特别地，假设一开始counter设置为0，对func1的调用会返回0+1+2+3=6，但对func2的调用会返回4·0=0。这个结果非常的截然不同，从程序意图上看，func1似乎又比func2好，因为它老老实实地做了加和的操作。

编译器一般不会试图判断一个函数是否没有副作用，如果没有，就可能被优化成func2中的样子。相反，编译器会假设最糟的情况，保持所有函数调用不变。

书中给了我们一个措施：内联函数替换(inline substitution)，将函数调用替换为函数体。

long funclin(){
	long t = counter ++ ;
	t = counter ++ ;
	t = counter ++ ;
	t = counter ++ ;
	return t;
}
// 编译器还可以做一些统一操作：统一funclin中对全局变量的更新，产生一个优化版本：
long funcopt(){
	long t = 4 * counter + 6 ;
	counter += 4;
	return t;
}

gcc不会做一些非常激进的优化，这也就意味着，如果你想要更好地使用gcc编写代码，你应该具备这种从程序上优化的能力。

2. 表示程序性能（CPE）

在开始这一小节之前，让我们认识一下CPE。

CPE(每元素的周期数，Cycles Per Element)，是一种表示程序性能的度量标准，类似于时钟周期。这种度量值能够表示执行了多少条指令，反映的是给定向量长度下程序的执行效率。

函数psum1每次迭代计算结果向量的一个元素。

第二个函数使用循环展开的技术，每次迭代计算两个元素。

这样的一个过程所需要的时间，可以用一个常数加上一个被处理元素个数成正比的因子来描述。也就是基于最小二乘的拟合函数：

两个函数的运行时间（代码计时、初始化过程、准备循环以及完成过程的时间开销）分别近似于368+9.0n和368+6.0n。当式子有较大的n，此时运行时间主要由n来决定，每项的系数n就是CPE的有效值。此时，psum1的CPE是9，psum2的CPE是6，那么psum2优于psum1。

这道题很简单，你只需要画图，和我们解不等式一样。

3. 程序示例

data_t表示基本元素的数据类型。

为了度量代码对于整数和浮点数数据的性能，我们分别为不同的类型声明编译和运行程序。

如：

typedef long data_t;

并分配一个len个data_t类型对象的数组来存放实际的向量元素。

书中给出了以下优化示例：

有一些变换组合是编写快速代码的“魔术(black art)”，但是作者仍然建议我们实验加上分析，反复尝试不同的方法，进行测量，并检查汇编代码表示，确定底层的性能瓶颈。

以下是combine1的CPE度量值：

4. 消除循环的低效率

每次循环迭代时都必须对测试条件求值，向量的长度不会随着循环的进行而改变，所以，我们在测试条件中都使用这个值。

这样的优化称为代码移动(code motion)。这类优化包括识别要执行多次但是计算结果不会改变的计算，因而可以将计算移动到代码前不会被多次求值的部分。在上例中，对vec_length的调用从循环内部移动到循环的前面。

优化编译器会试着进行代码移动，但对于在哪里调用函数或调用多少次的变换，编译器通常会非常小心，它们不能可靠地发现一个函数是否会有副作用，因此，我们假设函数会有副作用。

如果vec_length有某种副作用，combine1和combine2可能会有不同的行为。

程序员必须经常帮助编译器显式地完成代码的移动。

对库函数strlen的调用是Lower1的循环测试的一部分。在时间复杂度上，对于一个长度为n的字符串，strlen所用的时间与n成正比，因为对lower1的n次迭代的每一次都会调用strlen，所以Lower1的整体运行时间是字符串长度的二次项，正比于$n^2$。

除了将对strlen的调用移出了循环，Lower1和lower2是一样的，性能明显对比提升了。

理想的情况下，编译器会认出循环测试中对strlen的每次调用会返回相同的结果，因此能够把这个调用移出循环。但是这非常难，因为strlen会检查字符串的元素，而随着Lower1的进行，这些值会改变。编译器需要探查。

一个看上去无足轻重的代码片段，有隐藏的渐近低效率（asymptotic inefficiency）。在数据量变得比较庞大的时候，这些代码的问题就会浮出水面。

5. 减少过程调用

过程调用会带来开销，妨碍优化。从combine2的代码可以看出，每次循环迭代都会调用get_vec_element来获取下一个向量元素，对于每个向量引用，这个函数要把向量索引i和循环便捷作比较，明显会造成低效率。在处理任意的数组访问时，边界检查可能是个很有用的特性，但是对combine2代码的简单分析表明所有的引用都是合法的。