CSAPP 5 - 优化程序性能

1. 概述

1. 首当其冲的，还是要编写出好的算法和数据结构，优化内部结构
2. 其次才是编写出能让编译器 易优化的，高效的可执行代码。这点在特定的机器上可能有着特定的不同的优化，但有一些基本的优化仍然是相同的。
   1. 消除不必要的工作，让代码消耗时间在期望执行的任务上。包括消除或减少函数调用、条件测试、内存引用；同时熟悉处理器如何工作，利用反汇编知道它究竟如何执行操作，从而调整程序获得最大的速度。
   2. 利用好处理器的指令级并行能力，同时执行多条指令

2. 利用好编译器自身优化

gcc 就提供了不同优化级别的执行操作，利用 -O1 -O2 -O3 对程序进行不同级别的编译器优化代码。gcc 也在不断的更新迭代，编译器自身也在越来越强大。

基本编码规范：（避免限制优化的因素，产生更高效的代码）

消除连续的函数调用；避免不必要的内存引用

3. 消除循环的低效率，内存调用等

• 展开循环，降低开销

• 实现指令级并行

• 用功能性代码重写条件操作，使得编译采用条件传送

for (i=0; i<len; i++)
    if (s[i] >= 'A' && s[i]<= 'Z')
        s[i] -= ('A' - 'a');

函数调用不断使用，极其低效

4. 理解现代处理器

现代处理器采用分支预测的技术，处理器会猜测是否会选择分支，同时还预测分支的目标地址。这就让true/false 很痛苦，因为一旦预测失败就会产生很大的代价。所以我们会尽可能的采用条件传送（conditional move），而不是条件控制转移。

条件控制转移：等待代码的条件结果，选择合适的路径

for (i=0;i<n;i++)
    if(a[i]>b[i]){
        long t = a[i];
        a[i] = b[i];
        b[i]=t;
    }

条件传送：先将结果运行，再根据结果选择最终的结果值

for (i=0;i<n;i++)
    if(a[i]>b[i]){
        long min =a[i] < b[i] ? a[i] : b[i];
        long max =a[i] < b[i] ? b[i] : a[i];
        a[i] = min;
        b[i] = max;
    }

防止寄存器溢出

当并行度 p 超过可用寄存器的数量，编译器就会溢出，将一些临时变量放在内存中，会降低运行速度

5. 利用代码剖析程序，进行分析

Unix提供剖析程序GPROF可以进行代码剖析分析

代码剖析（Code profiling）
程序员在优化软件性能时要注意应尽量优化软件中被频繁调用的部分，这样才能对程序进行有效优化。使用真实的数据，精确的分析应用程序在时间上的花费的行为就成为_代码剖析_。现在几乎所有的开发平台都支持代码剖析，本文要介绍的是linux下针对c/c++的GNU的gprof代码剖析工具。

PS：gprof不只能对c/c++，还可对Pascal和Fortran 77进行代码剖析。

gprof
GNU gprof 是一款linux平台上的程序分析软件（unix也有prof)。借助gprof可以获得C/C++程序运行期间的统计数据，例如每个函数耗费的时间，函数被调用的次数以及各个函数相互之间的调用关系。gprof可以帮助我们找到程序运行的瓶颈，对占据大量CPU时间的函数进行调优。

PS：gprof统计的只是用户态CPU的占用时间，不包括内核态的CPU时间。gprof对I/O瓶颈无能为力，耗时甚久的I/O操作很可能只占据极少的CPU时间。

如何使用gprof
gprof的使用很简单，遵循以下步骤即可：

参考文档：

https://sourceware.org/binutils/docs/gprof/index.html#Top

6. 小结

没有一个编译器能用好的算法代替低效率的算法，因此程序设计的内容才是仍然是程序员主要关心的。我们应当养成良好的代码风格，给后续的工作带来便捷。