浅谈代码的执行效率（2）：编译器的威力
2010-01-08 00:06 by 老赵, 11780 visits在上一篇文章中，我主要表达了这样一个观点：影响程序效率的关键之一是算法，而算法的选择与优化，和是否多一个赋值少一个判断的关系不大。关于算法的选择，我谈到其理论上的复杂度，并不直接反映出效率。因为在实际运用时，数据的规模，特征等等都会涉及到算法的实际效果。一个时间复杂度低的算法并不代表任何情况下的效率都高。这是“实际”和“理论”的区别之一。现在我打算来谈一下另一个比较“实际”的东西：编译器对于程序效率的影响。
那么我们先来看这样一段代码，假设有一个保存着整数的单向链表，要求您写一个函数进行求和，您会怎么写呢？如果我们用F#，那么最容易实现的自然是递归方式：
let rec sum ls = match ls with | [] -> 0 | x :: xs -> x + (sum xs)
这段F#代码使用了模式匹配：如果是一个空链表，那么其结果自然等于零，否则就把它第一个元素加上剩余元素之和。这段代码显然非常简单，通过声明式的方法“表达”了函数的逻辑，没有任何一句多余的代码。不过您一定发现了，这个函数的实现中使用了递归，因此对于长度为n的链表来说，这个函数的时间复杂度为O(n)，空间复杂度也是O(n)——空间的开销在函数的调用栈上。一般来说，递归总是难逃调用栈的累积，因此它的空间复杂度总是难以做到O(1)的常数级别。调用栈的堆积，使得程序在执行访问的内存地址跨度不断增大，容易导致程序的局部性（Locality）不佳，性能较差——关于代码局部性的影响，我们下篇文章中再进行讨论。
当然，有些朋友可能会说，为什么要用递归呢？用普通的一个for或while循环，然后不断累加不也可以吗？当然可以，而且这么做的话空间复杂度便是O(1)了，时间复杂度虽然还是O(n)，但是经过上面的描述，我们可以知道它的实际执行效率会比递归的方式要好。不过，for/while都是命令式编程的方式，不适合函数式编程的“声明”风格，因此在实际应用中我们往往会写这样的sum函数：
let sum ls = let rec sum' ls acc = match ls with | [] -> acc | x :: xs -> sum' xs (acc + x) sum' ls 0
这个sum函数中定义了一个辅助函数sum'，这个辅助函数会多一个参数作为“累加器”，其中依旧使用了模式匹配的语法，在遇到空数组时直接返回累加器的值，否则就把链表的第一个元素加至累加器中，再递归调用sum'辅助函数。没错，这里还是用了递归。这样看起来，它的执行效果应该和前一种实现没有多大差别？
那么实际结果又是如何呢？如果您有条件不妨可以自己尝试一下——我这里贴一下由.NET Reflector反编译为C#后的sum'函数代码：
[Serializable] internal class sum'@9 : OptimizedClosures.FSharpFunc<FSharpList<int>, int, int> { public override int Invoke(FSharpList<int> ls, int acc) { while (true) { FSharpList<int> list = ls; if (!(list is FSharpList<int>._Cons)) { return acc; } FSharpList<int>._Cons cons = (FSharpList<int>._Cons)list; FSharpList<int> xs = cons.get_Tail(); int x = cons.get_Head(); acc += x; ls = xs; } } }
您不用彻底理解这段代码的结果如何，但您可以轻易察觉到，这并不是一段递归代码——这是一段“循环”，它的效果和我们自己的循环实现相同。为什么会这样？因为现在的sum'函数已经实现了尾递归，它能够被F#编译器优化为循环（并不是所有的尾递归都能优化为循环）。因此，虽然从高级语言的代码上，第二种实现方式比第一种要略微复杂一些，而且同样是递归，但最终的执行效果有较大差距。尾递归示例可能有些过分典型了，但这正说明了一个问题，我们使用的算法（广义的算法，即程序的实现方法）会在很多方便影响程序效率，例如体系结构方面（如递归性能较低）或是编译器的优化方面。一个好的算法，在这些方面都要考虑——例如，它可能需要在一定程度上去“迎合”编译器的优化，个中复杂程度并非“简短”二字就能概括的。
这便是编译器的威力所在了，它能把一段有特定模式的代码进行优化成更高效的形式。因此，您所看到的代码执行方式，并不一定是计算机的真正运行方式。换句话说，高级代码中表现出的高性能的代码，并不能把它直接视为机器执行时效果。这句话可能有些过于“理论”，如果您还一时无法立即接受的话，可能它的另一个“变体”会更加现实一些：一段看上去性能较差的代码，经过编译器优化之后其性能可能并不比“高效”的代码要差。而事实上，编译器最适合优化的一类内容便是所谓“少一些变量”，“少一些判断”等人工的、机械的优化方式了。
编译技术发展了几十年，早已形成了许多模式，高级语言的编译器也早已熟知一些机械的优化方式。例如，C#编译器会直接帮我们计算出一些常量表达式（包括数值计算和字符串连接），而JIT也会帮我们做一些循环展开、内联调用等常见优化手段。要比一些传统的优化，又有谁比的过机械而严谨的计算机来的完整呢？编译器甚至可以在多种可能产生冲突的优化方式中做出选择最有效的选择，而这个让人来完成就很麻烦了，如果在项目中这么做的话，可能会随着代码的修改之前的优化都没有效果了。对于大部分人来说，进行手动的细节优化，即便使用的是C语言，其最后的结果也很难超过编译器——更何况，C语言的确贴近CPU，但这表示它一定最为高效吗？
在目前的CPU面前，调整两条指令的顺序可能就会在效率方面产生非常显著的区别（这也是为什么在某些极端性能敏感的地方还是需要直接内嵌汇编代码），因为它迎合了CPU在执行指令过程中的预测及并行等优化方式。例如，处理器中只有一个乘法元件，那么编译器可以将两个乘法操作的依赖性降低，这样CPU便可以并发执行多条指令——关于这些我们会在以后的文章中进行讨论。试想，作为一个普通人类，我们进行此类优化的难度是多少呢？所以，我们应该把精力投入最有效的优化方式上，而程序字面上的“简短”几乎不会产生任何效果。
编译器的优化并非在空谈。例如Core Java 2中阐述了这样一个现象，便是JDK中的BitSet集合效率比C++的性能高。当然，文章里承认，这是由于Borland C++编译器的BitSet模板实现不佳导致的性能底下。不过这篇文章的数据也已经旧了，据某大牛的可靠消息，Core Java 7中表示，BitSet的效率已经打败了g++的编译成果，感兴趣的朋友们可以翻阅一下，如果我找到了网上的引用资料也会及时更新。这也是编译器的优化效果，因为对于BitSet这种纯算术操作，Java比C/C++这种静态编译的语言快很正常，因为JIT可以找到更多在运行时期可以做的特殊优化方式。
最后再举一个例子，便是Google工程师Mark Chu-Carroll在3年多前写的一篇文章《The “C is Efficient” Language Fallacy》，其中表示C/C++只是“最贴近CPU的语言”，但并非是进行科学计算时最高效的语言——甚至它们几乎不可能成为最高效的语言。这也是编译器的缘故，且看Mark列举了一小段代码：
for (int i=0; i < 20000) {
for (int j=0; j < 20000) {
x[i][j] = y[i-2][j+1] * y[i+1][j-2];
}
}
这段代码进行的是两个数组的计算。此时C++编译器便会遇到一个叫做“别名检测（alias detection）”的问题，那就是C++编译器无法得知x和y两个数组的关系（试想如果它们是一个函数的两个参数，也就是说没有任何其他上下文信息），例如它们是不是同一个数组？是不是有重叠？要知道C++的数组访问只是基于下标地址配合偏移量的计算，因此x和y的内容完全可能出现重叠现象。于是C++编译器只能老老实实地按照高级代码的写法生成机器码，优化的余地并不大——这里由于语言特性而导致编译器无法进行更高级的优化，可谓是一个“硬伤”。
Mark表示，Fortran-77可以区分x和y两者是否相同，Fortran-98可以由程序员指名两者并无重叠（如果我没有理解错原文的话），而一个由Lawrence Livermore实验室发明实验性语言Sisal比Fortran更有20%的性能提高。此外Mark还提出了他经历过的一个实际案例：几年前他要写一个复杂的算法来求出两个数组中“最长相同子串”，当时他不知道哪种语言合适，便使用多种语言各实现了一遍。最后他使用两个长为2000的数组进行测试的结果为：
- C：0.8秒。
- C++：2.3秒。
- OCaml：解释执行花费0.6秒，完全编译后执行耗费0.3秒。
- Java：1分20秒。
- Python：超过5分钟。
一年以后它使用最新的Java运行时，改进后的JIT只用了0.7秒便执行完了——当然还有额外的1秒用于启动JVM。在评论中Mark补充到，他是个严肃的C/C++程序员，并且已经尽他最大的努力来对C代码进行了优化。而当时他从来没有用过OCaml写过程序，更别说对OCaml代码进行一些取巧的优化方式了。至于OCaml高效的原因，他只是简单的提了一句，我也没有完全理解，便直接引用，不作翻译了：
The results were extremely surprising to me, and I did spend some time profiling to try to figure out just why the OCaml was so much faster. The specific reason was that the Caml code did some really clever stuff - it basically did something like local constant propagation that were based on be able to identify relations between subscripts used to access different arrays, and having done that, it could do some dramatic code rewriting that made it possible to merge loops, and hoist some local constants out of the restructured merged loop.
事实上，OCaml似乎的确是门了不起的语言，您可以在搜索引擎上使用“C++ OCaml Performance”作为关键字进行查找，可以找到很多性能比较的结果，以及OCaml编译优化方面的资料。自然，这些是题外话，您可以把它们作为扩展阅读用于“开阔视野”。我列举这个例子也不是为了说明C/C++的性能不够好，我这里谈的一切都是想说明一个问题：代码的执行效率并非能从字面上得出结论，更不是“简短”两个字能说明问题的。少一些赋值，少一些判断并非提高性能的正确做法，甚至您的手动优化会让编译器无法理解您的意图，进而无法进行有效的优化。如果您真想在细节上进行优化，还是进行Profiling之后，针对热点进行有效地优化吧。
Profiling，Profiling，Profiling。
至此，我们已经谈了算法和编译器对于性能的影响。那么下次，我们就在“算法一致”且“编译器没有优化”的前提下，继续探讨影响代码执行效率的要素之一吧。
相关文章
- 浅谈代码的执行效率（1）：算法是关键
- 浅谈代码的执行效率（2）：编译器的威力
- 浅谈代码的执行效率（3）：缓存与局部性
- 浅谈代码的执行效率（4）：汇编优化
原本我还想把所有内容放在一篇文章里，结果拆成了分成3-4部分写，而这第二部分写着写着就停不下来了，最后一看居然有3500字……