快捷搜索:

浅谈代码的执行效率:编译器的威力

在上一篇文章中,我主要表达了这样一个不雅点:影响法度榜样效率的关键之一是算法,而算法的选择与优化,和是否多一个赋值少一个判断的关系不大年夜。关于算法的选择,我谈到其理论上的繁杂度,并不直接反应出效率。由于在实际运用时,数据的规模,特性等等都邑涉及到算法的实际效果。一个光阴繁杂度低的算法并不代表任何环境下的效率都高。这是“实际”和“理论”的差别之一。现在我盘算来谈一下另一个对照“实际”的器械:编译器对付法度榜样效率的影响。

那么我们先来看这样一段代码,假设有一个保存着整数的单向链表,要求您写一个函数进行乞降,您会怎么写呢?假如我们用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, int, int>

{

public override int Invoke(FSharpList ls, int acc)

{

while (true)

{

FSharpList list = ls;

if (!(list is FSharpList._Cons))

{

return acc;

}

FSharpList._Cons cons = (FSharpList._Cons)list;

FSharpList 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。

至此,我们已经谈了算法和编译器对付机能的影响。那么下次,我们就在“算法同等”且“编译器没有优化”的条件下,继承探究影响代码履行效率的要素之一吧。

您可能还会对下面的文章感兴趣: