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

秒速五厘米 2022-12-24 11:50 129阅读 0赞

[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时钟周期的数量

例如：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nZmVpXzM1OA_size_16_color_FFFFFF_t_70]  
该图中：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定律的思想**：当我们对系统的某个部分加速时，其对系统整体性能的影响取决于该部分的重要性和加速程度。

## 消除性能瓶颈 ##

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

[961]: https://blog.csdn.net/zhaohongfei_358/article/details/111414370
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nZmVpXzM1OA_size_16_color_FFFFFF_t_70]: /images/20221120/c357027a82b94bbaa4a802e41d8f6b0c.png