我的一位朋友向我解释了他为什么认为他的程序运行不够快。“你分析过它的性能吗？”我问。“没有，但我很确定我知道瓶颈在哪里，”他回答道——真是著名的遗言。“好吧，我们试试性能分析器，”我说。性能分析很快揭示，98% 的 CPU 时间都花在了我朋友程序的一个子例程中，而 86% 的 CPU 时间都花在了一行代码上，而且他搞错了瓶颈的位置。

性能分析器是无价的工具，它可以让你知道程序的大部分时间都花在哪里。这些信息非常宝贵，因为它告诉你应该把时间花在哪里才能使你的程序更有效率，以及你在哪里浪费时间。典型的程序不像上面故事中那样一边倒。“80-20”法则表明，一个程序大约 80% 的时间会花在约 20% 的代码中。

如果一个程序的总运行时间是 n，那么我们可以将运行时间分解成几部分

total-time = a1*n + a2*n + a3*n + ...

其中 “a” 代表你的程序在特定代码段中花费的总时间的比例。“a” 的总和必须为 1。“80-20” 法则表明，其中一个 “a” 会非常大。例如，假设 a1 是 8/10，a2 是 2/10。这些数字对应于一个程序，它 80% 的时间用于执行 a1，20% 的时间用于执行其他所有内容。

total-time = .8*n + .2*n

在我朋友的例子中，我们能够稍微优化那一行代码。真正的优化发生在两天后，他告诉我，他已经删除了整个相关的子例程，仅仅是通过改变他对数据的思考方式。

在 Linux 下最容易使用的性能分析器是 gprof 性能分析器。gprof 是 GNU 开发工具的标准组成部分。如果你安装了 gcc，你可能也安装了 gprof。要使用 gprof，只需使用 -pg 开关，用 gcc 重新编译你的程序。这个选项会导致 gcc 在你的程序中每个子例程的开头插入一小段额外的代码。当你链接你的程序时，也必须使用 -pg 开关，因为必须存在另一段代码才能将各个部分连接在一起。

重新编译后，运行你的程序。由于分析代码所需的工作，它的执行速度会稍微慢一些，但不应该太慢。程序结束后，当前目录中会有一个名为 gmon.out 的文件。这个文件包含程序运行期间收集的性能分析信息。gprof 用于以人类可读的形式打印这些信息。

gprof 以两种方式输出信息：平面配置文件和调用图。平面配置文件告诉你程序在所有子例程中花费了多少时间，而调用图告诉你哪些子例程调用了哪些子例程。

平面配置文件的第一部分如列表 1所示。“自身秒数”列显示了每个子例程占用的时间。“调用”列显示了每个子例程被调用的次数。“自身 ms/调用”列给出了在给定子例程中花费的平均时间（以毫秒为单位），而 “总 ms/调用” 还包括该子例程调用的子例程中花费的时间。由于 gprof 文档中解释的原因，最后一列实际上只是一个猜测，不应依赖。

在这个例子中，需要注意的一个重要事项是，mcount 子例程是 gcc 使用 -pg 开关编译代码时插入的实际性能分析子例程调用。程序近 20% 的时间都花在这里这一事实表明，正在发生大量的调用和返回，而加速代码的一种方法是消除一些子例程调用。哪些子例程呢？rnd 和 uni 子例程很可能是候选对象，因为它们在 900 秒内被调用了 1.42 亿次。

Linux 上常用的另一个性能分析器是 bprof。bprof 和 gprof 之间的主要区别在于，bprof 提供源代码行级别的计时，而 gprof 只有子例程级别的分辨率，并且还包括诸如调用计数之类的信息。要使用 bprof，请将对象文件 bprof.o 链接到你的程序中。运行你的程序后，一个名为 bmon.out 的文件包含计时信息。在这个数据文件上运行 bprof，它会复制你的源文件，并在每行前面加上计时数字。

Linux 下的性能分析器的工作原理是定期检查程序计数器，以查看程序实际在代码的哪个位置工作。虽然易于实现，但此过程具有一定的随机性，导致测量中存在一定的噪声。在 “长” 时间间隔内，良好的数据量会淹没噪声。当我们只对查找瓶颈感兴趣时，这通常在实践中已经足够好了。

gprof 和 bprof 都使用仅在你的程序实际运行时才运行的计时器。内核代表你的程序占用大量时间的一种方式是通过读取或写入大量数据。这些时间不会累积到性能分析中。内核可能会占用大量时间的另一种更微妙的方式是，如果你的程序使用了太多内存，以至于内核必须将你程序的一部分换入和换出内存。这种情况称为页面抖动，因为你通常可以听到你的磁盘在剧烈地响。

检查系统时间的一种简单方法是使用以下命令运行你的程序

time <

程序结束后，将打印三个时间：用户时间（CPU 运行你的程序所花费的时间）、系统时间（CPU 在内核中为你的程序服务所花费的时间）和经过时间（实际时间，有时称为 “挂钟” 时间）。通过比较这些时间，你可以大致了解内核必须为你做多少工作。

我最喜欢的性能分析器是一个名为 pixie 的程序，但不幸的是，它在 Linux 上不可用。Pixie 的工作原理是实际读取可执行文件，将计数代码插入到只能在开始时进入并在结束时退出的代码 “基本块” 中。如今，gcc 中存在用于计算这些基本块执行次数的支持（-a 选项），但尚不支持获取每个块的实际时间。

现在你已经知道程序中瓶颈的位置了。有一些简单的技术可以使事情运行得更快。最简单的方法当然是使用 gcc 的 -O 标志来优化代码。但请注意，优化器以生成错误代码而臭名昭著。

通常可以通过增加空间来减少运行时间。请考虑列表 2中的以下 (FORTRAN) 代码片段。

性能分析表明，程序超过四分之一的时间都花在了这个循环中，这不仅是因为它速度慢，还因为它被频繁调用。由于它被频繁调用，因此在每次循环迭代中都会重新计算变量 cx、cy 和 cz。如果我们预先将这些值计算到 tcentr() 数组中，则四个数组引用、三个浮点加法和一个乘法将替换为单个数组引用。从而消除了关键循环中的大量代码。

锦上添花的是将乘以 0.25 的运算（乘以 0.25 比除以 4.0 快）完全移出循环；因此，我们不是将总和的每个元素乘以 0.25，而是将整个总和乘以 0.25。由于循环恰好执行了大约 100,000 次左右，因此我们消除了 99,999 次浮点乘法。新代码如列表 3所示。

此时，再次对程序进行性能分析，此子例程的运行时间已降至总时间的 15%，其中 10% 由平方根计算占用。由于现在另一个子例程占据了运行时间的主要部分，因此优化工作的重点从这个子例程转移开了。

对于这段代码，还有一件半容易的事情可以做。碰巧的是，已知平方根只需要在非常有限的值范围内使用。因此，我们可以用一个函数替换平方根函数，该函数通过查找预先计算好的表格中的值并返回在表格条目之间出现的值的插值来输出相同的值。同样，我们用空间换取了时间。

加速程序的另一种常见方法是用指针替换数组引用。在本文开头的示例中，占我朋友程序 98% 的代码行看起来像

int i, array[1000000];
...
 i = 0;
 while(array[i] == 0) i++;

此行搜索数组的下一个非零元素。引用数组的操作包括将 i 乘以一个比例因子（实现为二进制左移），将此值添加到 array[] 的开头，然后从该位置获取。用以下代码替换此代码

int *p, i, array[1000000];
...
 p = array;
 while(*p == 0) p++;
 i = p - array;

我们在此案例中尝试的另一个更改是展开循环。代码被替换为

int *p, i, array[1000000];
...
 p = array;
 for(;;) {
 if (*p++ != 0) break;
 if (*p++ != 0) break;
 if (*p++ != 0) break;
 if (*p++ != 0) break;
 }

这里的想法是，在某些类型的机器上，执行分支的成本很高，而拒绝分支的成本很低。在一个非常紧凑的循环中，循环的开销最终可能成为总时间的重要组成部分。第二个示例中的代码已被重写，以便大多数分支不被执行，并且在循环体的每次迭代中完成更多的工作。

事实证明，这种 “优化” 并未在我们使用的机器上提高任何速度。一个好的编译器在用 -O 编译时会为你展开短循环。重要的是在优化前后进行性能分析，以查看你所做的事情是否有帮助或有害。

优化代码的另一个主要选择包括简单地寻找更好的算法。例如，假设我们要在一个数组中搜索特定的条目。如果数组非常小，我们可以简单地依次检查每个元素。当元素数量变多时，哈希表是一种快速简便的方法，可以减少必须搜索的元素数量。对于无法哈希的数据，树搜索提供了另一种选择。哈希和树超出了本文的范围，但应该是任何程序员的技巧锦囊的一部分。任何关于数据结构的好书都可以向你展示它们的工作原理。

特定于机器的优化通常最好留给编译器。编译器在最简单的优化方面正变得越来越好，而 gcc 是最好的编译器之一。一旦性能分析器找到程序中速度较慢的部分，优化它的最佳方法就是简单地想象必须手动计算所有内容。希望你能注意到编译器会遗漏的改进之处。

毕竟，永远不会编写出完美的编译器。有一个老笑话，一旦制造出能够像人一样编写代码的计算机，那台计算机就会期望获得报酬来换取它的工作。嘿，这是工作保障。