复旦大学961-计算机系统基础-第二章-优化程序性能

961全部内容链接

文章目录

• 优化程序性能
• 优化编译器的能力
• 编译器优化的局限性
• 表示程序性能
• 特定体系结构或应用特性的性能优化
• 限制因素
• 确认和消除性能瓶颈
• • 确定性能瓶颈
  • 消除性能瓶颈

优化程序性能

《CSAPP》P341

1. 选择合适的算法和数据结构
2. 编写出编译器能够有效优化以转换成高效可执行代码的源代码
3. 消除不必要的功能，让代码尽可能有效地执行所期望的任务。如不必要的函数调用，条件测试和内存引用。

《CSAPP》P387 5.13 应用：性能提高技术

1. 高级设计：选择合适的算法和数据结构
2. 基本编码原则：避免限制优化的因素，这样编译器就能产生高效的代码，例如：消除连续的函数调用，消除不必要的内存引用。
3. 低级优化：结构化代码以利用硬件功能。如：①展开循环，降低开销，并且使得进一步的优化成为可能； ②通过使用例如多个累积变量和重新结合等技术，找到方法提高指令级并行；③用功能性的风格重写条件操作，使得编译采用条件数据传送。

优化编译器的能力

《CSAPP》P342

优化编译器的能力：现代编译器运用复杂精细的算法来确定一个程序中计算的是什么值，以及他们是被如何使用的。然后利用一些机会来简化表达式，在几个不同的地方使用同一个计算，以及降低一个给定的计算必须被执行的次数。大多编译器，包括GCC，会向用户提供一些优化级别参数，优化级别越高，程序性能越高，但也可能增加程序的规模，也可能使标准的调试工具很难对程序进行调试。

编译器优化的局限性

《CSAPP》P342

编译器优化的局限性：编译器只会对程序使用安全的优化。也就是说编译器在简化语句时，会考虑到所有情况，如果可能会出问题，就不会对其进行优化。这种情况下，就需要开发人员自行优化。 例如下面代码：

void twiddle1(long *xp, long *yp) {
	*xp += *yp;
	*xp += *yp;
} // 该语句效率低，需要六次访存（2次读*xp，2次写*xp，2次读*yp）

void twiddle2(long *xp, long *yp) {
	*xp += 2* *yp;
} // 该语句效率高，仅需要3次访存（读*xp，读*yp，写*xp）
           

该例子中，若xp和yp指向的是不同的地址，则1,2的结果是一样的，但如果他们指向的是同一地址，则他们的结果会不一致（1的xp会变为原来的4倍，2的xp会变为原来的3倍）。编译器考虑到可能会出现不一致，所以编译器并不会将twiddle1优化成twiddle2。

这种妨碍编译器优化的因素称为妨碍优化的因素（optimization blocker）。上述这种两个指针可能指向同一个内存位置的情况称为内存别名使用（memory aliasing） 。

表示程序性能

《CSAPP》P345

我们引入度量标准每元素的周期数（Cycles Per Element, CPE） 作为一种表示程序性能并指导我们改进代码的方法。CPE这种度量标准帮助我们在更细节的级别上理解迭代程序的循环性能。这样的度量标准对执行重复计算的程序来说是很适当的，例如图像处理中的像素，或是计算矩阵乘积中的元素。

每元素的周期数：

1. 周期：指的是CPU的时钟周期
2. 元素：指要处理的集合的一个元素

每元素的周期数就是指处理一个元素要消耗的CPU时钟周期的数量

例如：

该图中：psum1和psum2指的是两个程序函数。slope是斜率（这个斜率就是CPE的值），横坐标是集合元素的数量，纵坐标是时钟周期数。

也就是说，当集合元素数为0时，它们消耗的时钟周期数为400，当集合元素数为200时，psum1消耗的时钟期周期数为2200。所以psum1的CPE的值为9，也就是 (2200-400)/200 = 9。 psum2的算法一样。显然，psum2函数的性能更好。

CPE的计算公式：

C P E = f ( n ) − f ( 0 ) n       其 中 f ( n ) 表 示 n 个 元 素 时 消 耗 的 时 钟 周 期 数 CPE = \frac{f(n) - f(0)}{n} ~~~~~其中f(n)表示n个元素时消耗的时钟周期数 CPE=nf(n)−f(0)​     其中f(n)表示n个元素时消耗的时钟周期数

特定体系结构或应用特性的性能优化

《CSAPP》P350-P377

1. 消除循环的低效率：就是把循环里面的代码效率写的高一点。因为非循环部分影响较小，可以忽略不计。但是循环里面的代码要执行多次，影响比较大
2. 减少过程调用：过程调用就是函数调用。过程调用会带来开销，而且会妨碍大多数形式的程序优化。
3. 消除不必要的内存引用：不要频繁直接操作指针。可以申请一个局部变量，对局部变量进行操作。比如， for(;; ) *p+=1; 可以改成 a=*p; for(;; ) a+=1; *p=a;
4. 理解现代处理器：理解现代处理器可以帮助优化程序性能。现代处理器支持指令集并行，即看似代码是一条一条执行的，但实际上在CPU中，可以多条指令一起执行。若一系列操作必须按照严格顺序执行时，就会遇到延迟界限（latency bound） ，因为在下一条指令开始之前，这条指令必须结束。这个界限是程序性能的终极限制。
5. 循环展开：循环展开是一种程序变换，通过增加每次迭代计算的元素的数量，减少循环的迭代次数。它减少了不直接有助于程序结果的操作的数量，第二，它提供了一些方法，可以进一步变化代码，减少整个计算中关键路径上的操作数量。
6. 提高并行性：由4知，现代CPU是可以并行执行的。但不是所有代码都会并行，改造代码让其可以并行执行就可以提高程序性能。 如 for(;;i++) a = arr[i]; 可以改造为 for(;;i+=2) {a = arr[i]; b= arr[i+1] }; a += b 前者for循环中只有一行代码，所以整个for循环都是串行执行的。而改造后的后者，循环次数降低了一倍，而且for循环中的两行代码可以并行执行，所以整体提高了性能。

限制因素

《CSAPP》P378

1. 寄存器溢出，当采用提高循环并行性的优化时，若我们的并行度p超过了可用的寄存器数量，那么编译器就会借助于（resort to）溢出（spilling） ，将某些临时值存放到内存中，通常是在运行时堆栈上分配空间。这样我们优化的优势就很可能消失。
2. 分支预测和预测错误处罚：当分支预测逻辑不能正确预测一个分支是否要跳转的时候，条件分支可能会招致很大的预测错误处罚。若CPU支持投机执行（speculative execution），处理器会开始执行预测的分支目标处的指令。若预测正确，就“提交”投机执行的指令的结果，若预测错误，则丢弃。

确认和消除性能瓶颈

《CSAPP》P388

确定性能瓶颈

对于很大的程序，我们很难知道应该优化什么地方。所以需要借助代码剖析程序（code profiler） ，这是在程序执行时收集性能数据的分析工具。

程序剖析（profiling） 运行程序的一个版本，其中插入了工具代码，以确定程序的各个部分需要多少时间。这样就可以知道哪一块消耗的时间最长，然后针对消耗最长的这块代码进行优化了。

Unix提供了一个剖析程序GPROF。它确定程序中每个函数花费了多少CPU时间。其次，它计算了每个函数被调用的次数，以执行调用的函数来分类。

Amdahl定律的思想：当我们对系统的某个部分加速时，其对系统整体性能的影响取决于该部分的重要性和加速程度。

消除性能瓶颈

使用剖析程序来指导优化，一步一步消除性能瓶颈。