Hello World
Spiga

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

2010-01-08 00:06 by 老赵, 11846 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。

至此,我们已经谈了算法和编译器对于性能的影响。那么下次,我们就在“算法一致”且“编译器没有优化”的前提下,继续探讨影响代码执行效率的要素之一吧。

相关文章

Creative Commons License

本文基于署名 2.5 中国大陆许可协议发布,欢迎转载,演绎或用于商业目的,但是必须保留本文的署名赵劼(包含链接),具体操作方式可参考此处。如您有任何疑问或者授权方面的协商,请给我留言

Add your comment

36 条回复

  1. 老赵
    admin
    链接

    老赵 2010-01-08 00:07:00

    原本我还想把所有内容放在一篇文章里,结果拆成了分成3-4部分写,而这第二部分写着写着就停不下来了,最后一看居然有3500字……

  2. 麒麟
    *.*.*.*
    链接

    麒麟 2010-01-08 00:09:00

    板凳

  3. 老赵
    admin
    链接

    老赵 2010-01-08 00:11:00

    @麒麟
    写完了,打游戏去了,嘿嘿。

  4. heros
    *.*.*.*
    链接

    heros 2010-01-08 08:10:00

    评论间隔时间只有两秒。有点假。
    lz , 早睡早起,才是好同志!

  5. 温景良(Jason)
    *.*.*.*
    链接

    温景良(Jason) 2010-01-08 08:17:00

    Jeffrey Zhao:
    @麒麟
    写完了,打游戏去了,嘿嘿。


    起得真早啊

  6. 卡通一下
    *.*.*.*
    链接

    卡通一下 2010-01-08 08:29:00

    heros:
    评论间隔时间只有两秒。有点假。
    lz , 早睡早起,才是好同志!


    确实!

    大概是语音录入吧?

  7. 菌哥
    *.*.*.*
    链接

    菌哥 2010-01-08 08:45:00

    老赵的简介中划去了职位,现在在哪高就呢?

  8. 水果阿生
    *.*.*.*
    链接

    水果阿生 2010-01-08 08:47:00

    "BitSet的效率已经打败了g++的编译成果",昨天下午跟某人谈到这件事,我觉得这个同学辩证法学得太好了。

  9. Jerry Qian
    *.*.*.*
    链接

    Jerry Qian 2010-01-08 09:10:00

    顶一下。

  10. 极品拖拉机
    *.*.*.*
    链接

    极品拖拉机 2010-01-08 09:23:00

    昨天还没看见有新博客呢,今天怎么就到中了
    老赵最近好像对推销F#蛮有热度的。
    一般在BS开发应用中,常用的到算法就是循环和递归,对于数据比较小的话,算法的效率我还没感觉出来。
    一般在需要应用算法的地方,如:服务器上缓存,应用hashtable或单链表。
    现在很多时候,算法只是成为一个学校的理论课程,公司面试的题目
    应用的场合(对于大部分人来说),却很少
    个人见解
    最近在复习数据结构和算法
    数据结构蛮有心得,算法还是感觉不着边

  11. 四有青年
    *.*.*.*
    链接

    四有青年 2010-01-08 09:43:00

    楼主近来貌似很推崇Profiling啊,不过的确是个好东西

    另外,问下你玩的什么游戏。。。

  12. DiggingDeeply
    *.*.*.*
    链接

    DiggingDeeply 2010-01-08 09:49:00

    编译器也是人设计的,不可能很智能化,而且优化也是很分场景的。

  13. Mr.d
    *.*.*.*
    链接

    Mr.d 2010-01-08 09:53:00

    极品拖拉机:
    昨天还没看见有新博客呢,今天怎么就到中了
    老赵最近好像对推销F#蛮有热度的。
    一般在BS开发应用中,常用的到算法就是循环和递归,对于数据比较小的话,算法的效率我还没感觉出来。
    一般在需要应用算法的地方,如:服务器上缓存,应用hashtable或单链表。
    现在很多时候,算法只是成为一个学校的理论课程,公司面试的题目
    应用的场合(对于大部分人来说),却很少
    个人见解
    最近在复习数据结构和算法
    数据结构蛮有心得,算法还是感觉不着边



    即使应用不着,个人感觉对思维的拓展、解决问题的能力还是有一定的帮助的。算法这样叫其实很虚,干脆就理解解决某个问题的方法或解决某个问题的有序代码组合吧,那么我们解决某一问题的时候,就在使用算法了。我的愚见,说的不好,大家都来讨论昂。

  14. Jeff Wong
    *.*.*.*
    链接

    Jeff Wong 2010-01-08 10:16:00

    老赵,你确定你是在“浅谈”?我要重新评估自己的能力和智商了。

  15. Kevin Dai
    *.*.*.*
    链接

    Kevin Dai 2010-01-08 11:57:00

    @Jeff Wong
    这些都算是“基础”知识或者说是常识吧。

  16. ubunoon
    *.*.*.*
    链接

    ubunoon 2010-01-08 13:53:00

    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];
    }
    }
    抄的时候也加个 i++或者++j之类的。

    不过这篇文章很受益,对C/C++的了解也更深入一些。


  17. 老赵
    admin
    链接

    老赵 2010-01-08 14:10:00

    @极品拖拉机
    在我看来,算法和经典算法并非一个东西。
    我们学习用的是经典算法,而平时用的时候都是算法。
    而经典算法是影响我们用的算法的,hoho。

  18. 老赵
    admin
    链接

    老赵 2010-01-08 14:11:00

    四有青年:
    楼主近来貌似很推崇Profiling啊,不过的确是个好东西

    另外,问下你玩的什么游戏。。。


    Profiling是一种手段,和哪种确定的东西无关啊,这个概念一定要搞清楚。
    确定的东西就叫做某个Profiler了。

  19. 老赵
    admin
    链接

    老赵 2010-01-08 14:12:00

    Jeff Wong:老赵,你确定你是在“浅谈”?我要重新评估自己的能力和智商了。


    只是涉及了一些可能你平时不太接触的东西,没有一个东西是深入的吧。

  20. 老赵
    admin
    链接

    老赵 2010-01-08 14:13:00

    DiggingDeeply:编译器也是人设计的,不可能很智能化,而且优化也是很分场景的。


    是啊,所以我说某些时候还是需要内嵌汇编的。
    编译器不会很智能化,但是很机械化,所以我们的优化要做智能的那些,而不是机械的那些。
    如果我们亲自来做一些如少一些变量,少一些判断之类的机械优化,就太伤害编译器了,呵呵。

  21. 老赵
    admin
    链接

    老赵 2010-01-08 14:15:00

    heros:
    评论间隔时间只有两秒。有点假。
    lz , 早睡早起,才是好同志!


    0:09和0:11相差是2分钟……

  22. 老赵
    admin
    链接

    老赵 2010-01-08 14:16:00

    菌哥:老赵的简介中划去了职位,现在在哪高就呢?


    失业状态中。

  23. Kevin Dai
    *.*.*.*
    链接

    Kevin Dai 2010-01-08 14:21:00

    老赵对淘宝感兴趣吗?

  24. 老赵
    admin
    链接

    老赵 2010-01-08 14:27:00

    @Kevin Dai
    有啊,可惜淘宝不在上海。

  25. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2010-01-08 15:17:00

    嗯这让我想起Java面试界(嗯,面试专业户?)极爱讨论的“这段代码创建了多少个对象”系列问题。再看看这篇文章:Pulling a Machine Code Rabbit Out of a Java Hat的What can these transforms be used for?那段,“创建了多少个对象”这种事情读Java代码根本是没办法确定的……

  26. Kevin Dai
    *.*.*.*
    链接

    Kevin Dai 2010-01-08 15:28:00

    原来JDK中还有BitSet这个数据类型的,收藏一下。我上次是用布尔数组来做一个问题的。

  27. msyye
    *.*.*.*
    链接

    msyye 2010-01-08 16:13:00

    极力支持!

  28. heros
    *.*.*.*
    链接

    heros 2010-01-08 17:07:00

    @Jeffrey Zhao
    现眼了...

  29. Ivony...
    *.*.*.*
    链接

    Ivony... 2010-01-08 17:11:00

    RFX老大也不接着挖坑。。。。没坑好无聊。。。。

  30. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2010-01-08 18:40:00

    @Ivony...

    Ivony...:RFX老大也不接着挖坑。。。。没坑好无聊。。。。


    没办法,我也想挖坑,但时间不够啊。我都恨不得向老赵学习,回窝修炼了……
    我准备挖大型坑:http://hllvm.group.javaeye.com/
    初步打算先往坑里堆些资料,然后再发点老赵风格的帖。
    资料这种东西我也不可能拿到非公开的,只是资料太分散太零乱,没有考据嗜好的话很多资料明明就在那里也未必会发现得了。我是想至少把零乱的资料整合起来……学习data-as-a-service的精神

  31. 老赵
    admin
    链接

    老赵 2010-01-08 19:09:00

    @RednaxelaFX
    我去跟你学习了。

  32. forhells
    *.*.*.*
    链接

    forhells 2010-01-10 22:25:00

    这本《程序设计语言--实践之路》[美]Michael L.Scott著。还是有意思的,不多说,水平有限,懒散成性。

  33. 幸运猴子
    *.*.*.*
    链接

    幸运猴子 2010-01-11 08:46:00

    @Jeffrey Zhao
    老赵,我如何能向你一样强大?

  34. 极品拖拉机
    *.*.*.*
    链接

    极品拖拉机 2010-01-11 10:25:00

    f#和Erlang比较起来,哪个更占有优势点啊?
    Erlang的语法和IDE太让人难过了。
    F#还没接触过
    老赵对2个不是都有了解吗?
    说说
    FP最近比较流行啊,连我这个老古董都要去学习下了

  35. 蛙蛙王子
    *.*.*.*
    链接

    蛙蛙王子 2010-01-29 23:24:00

    这篇讲的感觉离我的实际开发比较远,平时没留意过编译器的存在都,呵呵。
    也许是没使用C等偏底层语言的经验吧。

  36. 链接

    gaobanana 2010-04-10 11:50:09

    又看完一篇,学到不少知识,优化最多的还是sql语句,对算法优化确实少了点。-

发表回复

登录 / 登录并记住我 ,登陆后便可删除或修改已发表的评论 (请注意保留评论内容)

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

评论内容(大于5个字符):

  1. Your Name yyyy-MM-dd HH:mm:ss

使用Live Messenger联系我