一个简单例子说明为什么C语言在2013年仍很重要

伯乐在线导读:本文作者在开发Dynym项目,这是一个动态语言的通用运行时。在开发时,作者以其他语言的运行速度作为基础比较语言的运行速度,因此发现了一些小秘密。迭代计算斐波那契数列是测试各种语言执行速度的常见方法。作者以不同的语言进行测试,最终发现C语言要比Python编写的计算斐波那契数列快278.5倍。在底层开发,以及专注性能的应用程序中,选择是显而易见的。而为什么会有如此大的运行性能差距呢。作者进一步研究了程序的反汇编代码,发现差别出在内存的访问次数,以及预测的CPU指令的正确性方面。(感谢 乾龙_ICT 的热心翻译。如果其他朋友也有不错的原创或译文,可以尝试提交到伯乐在线。)以下是译文。

原作者注:在本文最开始,我并没说明进行模2^64的计算——我当然明白那些不是“正确的”斐波那契数列,其实我不是想分析大数,我只是想探寻编译器产生的代码和计算机体系结构而已。

最近,我一直在开发Dynvm——一个通用的动态语言运行时。就像其他任何好的语言运行时项目一样,开发是由基准测试程序驱动的。因此,我一直在用基准测试程序测试各种由不同语言编写的算法,以此对其典型的运行速度有一个感觉上的认识。一个经典的测试就是迭代计算斐波那契数列。为简单起见,我以2^64为模,用两种语言编写实现了该算法。

用Python语言实现如下:

用C语言实现如下:

其他语言实现的代码示例,我已放在github上。

Dynvm包含一个基准测试程序框架,该框架可以允许在不同语言之间对比运行速度。在一台Intel i7-3840QM(调频到1.2 GHz)机器上,当 n=1,000,000 时,对比结果如下:

很明显,C语言是这里的老大,但是java的结果有点误导性,因为大部分的时间是由JIT编译器启动(~120ms)占用的。当n=100,000,000时,结果变得更明朗:

在这里,我们探究下为什么C语言在2013年仍然很重要,以及为什么编程世界不会完全“跳槽”到Python或者V8/Node。有时你需要原始性能,但是动态语言仍在这方面艰难挣扎着,即使对以上很简单的例子而言。我个人相信这种情况会克服掉,通过几个项目我们能在这方面看到很大的希望:JVM、V8、PyPy、LuaJIT等等,但在2013年我们还没有到达“目的地”。

然而,我们无法回避这样的问题:为什么差距如此之大?在C语言和Python之间有278.5倍的性能差距!最不可思议的地方是,从语法角度讲,以上例子中的C语言和Python内部循环基本上一模一样。

为了找到问题的答案,我搬出了反汇编器,发现了以下现象:

(译注:

  • 1、不同的编译器版本及不同的优化选项(-Ox)会产生不同的汇编代码。
  • 2、反汇编方法:gcc -g -O2 test.c -o test;objdumb -d test>test.txt  读者可以自己尝试变换优化选项对比反汇编结果)

最主要的部分是计算下一个斐波那契数值的内部循环:

变量在寄存器中的分配情况如下:

262和263行实现了变量交换,264行增加循环计数值,虽然看起来比较奇怪,265行实现了b=a+t。然后做一个简单地比较,最后一个跳转指令跳到循环开始出继续执行。

手动反编译以上代码,代码看起来是这样的:

整个内部循环仅用六条X86-64汇编指令就实现了(很可能内部微指令个数也差不多。译者注:Intel X86-64处理器会把指令进一步翻译成微指令,所以CPU执行的实际指令数要比汇编指令多)。CPython解释模块对每一条高层的指令字节码至少需要六条甚至更多的指令来解释,相比而言,C语言完胜。除此之外,还有一些其他更微妙的地方。

拉低现代处理器执行速度的一个主要原因是对于主存的访问。这个方面的影响十分可怕,在微处理器设计时,无数个工程时(engineering hours)都花费在找到有效地技术来“掩藏”访存延时。通用的策略包括:缓存、推测预取、load-store依赖性预测、乱序执行等等。这些方法确实在使机器更快方面起了很大作用,但是不可能完全不产生访存操作。

在上面的汇编代码中,从没访问过内存,实际上变量完全存储在CPU寄存器中。现在考虑CPython:所有东西都是堆上的对象,而且所有方法都是动态的。动态特性太普遍了,以至于我们没有办法知道,a+b执行integer_add(a, b)、string_concat(a, b)、还是用户自己定义的函数。这也就意味着很多时间花在了在运行时找出到底调用了哪个函数。动态JIT运行时会尝试在运行时获取这个信息,并动态产生x86代码,但是这并不总是非常直接的(我期待V8运行时会表现的更好,但奇怪的是它的速度只是Python的0.5倍)。因为CPython是一个纯粹的翻译器,在每个循环迭代时,很多时间花在了解决动态特性上,这就需要很多不必要的访存操作。

除了以上内存在搞鬼,还有其他因素。现代超标量乱序处理器核一次性可以取好几条指令到处理器中,并且“在最方便时”执行这些指令,也就是说:鉴于结果仍然是正确的,指令执行顺序可以任意。这些处理器也可以在同一个时钟周期并行执行多条指令,只要这些指令是不相关的。Intel Sandy Bridge CPU可以同时将168条指令重排序,并可以在一个周期中发射(即开始执行指令)至多6条指令,同时结束(即指令完成执行)至多4条指令!粗略地以上面斐波那契举例,Intel这个处理器可以大约把28(译者注:28*6=168)个内部循环重排序,并且几乎可以在每一个时钟周期完成一个循环!这听起来很霸气,但是像其他事一样,细节总是非常复杂的。

我们假定8条指令是不相关的,这样处理器就可以取得足够的指令来利用指令重排序带来的好处。对于包含分支指令的指令流进行重排序是非常复杂的,也就是对if-else和循环(译者注:if-else需要判断后跳转,所以必然包含分支指令)产生的汇编代码。典型的方法就是对于分支指令进行预测。CPU会动态的利用以前分支执行结果来猜测将来要执行的分支指令的执行结果,并且取得那些它“认为”将要执行的指令。然而,这个推测有可能是不正确的,如果确实不正确,CPU就会进入复位模式(译者注:这里的复位不是指处理器reset,而是CPU流水线的复位),即丢弃已经取得的指令并且重新开始取指。这种复位操作有可能对性能产生很大影响。因此,对于分支指令的正确预测是另一个需要花费很多工程时的领域。

现在,不是所有分支指令都是一样的,有些可以很完美的预测,但是另一些几乎不可能进行预测。前面例子中的循环中的分支指令——就像反汇编代码中267行——是最容易预测的其中一种,这个分支指令会连续向后跳转100,000,000次。

以下是一个非常难预测的分支指令实例:

如果random()是真正随机的(事实上在C语言中远非如此),那么对于if-else的预测还不如随便猜来的准确。幸运的是,大部分的分支指令没有这么顽皮,但是也有很少一部分和上面例子中的循环分支指令一样变态。

回到我们的例子上:C代码实现的斐波那契数列,只产生一个非常容易预测的分支指令。相反地,CPython代码就非常糟糕。首先,所有纯粹的翻译器有一个“分配”循环,就像下面的例子:

编译器无论如何处理以上代码,至少有一个间接跳转指令是必须的,而这种间接跳转指令是比较难预测的。

接下来回忆一下,动态语言必须在运行时确定如“ADD指令的意思是什么”这样基本的问题,这当然会产生——你猜对了——更加变态的分支指令。

以上所有因素加起来,最后导致一个278.5倍的性能差距!现在,这当然是一个很简单的例子,但是其他的只会比这更变态。这个简单例子足以凸显低级静态语言(例如C语言)在现代软件中的重要地位。我当然不是2013年里C语言最大的粉丝,但是C语言仍然主导着低级控制领域及对性能要求高的应用程序领域。

收藏 12 评论

关于作者:乾龙

匆匆啊 匆匆啊 擦身而过的人呐 一朵浪花一刹那 不过如此啊 (新浪微博:@乾龙_ICT | 个人博客:乾龙) 个人主页 · 我的文章 · 2

相关文章

可能感兴趣的话题



直接登录
最新评论
  • 小白   2013/09/02

    数列那个, 快慢和2^64幂取余数有关系吧.
    而这在C语言里靠自动截断,0开销.

  • 王二   2013/09/02

    用不带JIT编译器的解释型语言跟C比较,这个例子不够典型。

  • cpp_mengtong   2013/09/02

    优化一下,把递归给用栈实现,试试速度!

  • Hongbao Chen   2013/09/02

    这种比较简直傻逼。解释执行和编译执行效率能一样?
    不要跟我说你看某某书籍或者什么JIT,都是扯。

  • 死掉的海   2013/09/03

    额 我想吐槽 while 并不是 python里最快的 优先选择for 。而且 拿python 跟c 比 真的有意思吗?

  • thoupin   2013/09/03

    别执着于某种语言如何犀利,如何的快,如果真的要追求速度,何不用汇编呢, 甚至直接敲1010也行额。
    但是以前以机器为中心的时代不会再来了, 现在想的应该是以人为中心,不是运行效率,而是开发效率。
    为什么? 就是因为现在的硬件水平和数据规模,人要向前看,C语言确实很优秀,我也没说他不好,只不过
    对于现在的时代,应该思变,去寻求更好的。

  • 模数不具有代表性。
    为什么要用2^64做模?C语言里直接截断,Python里按大数存储。两者根本没有可比性,甚至可以算是Python的优点。
    或者说C代码里连取模%都没有出现,怎么和有%的Python代码比较?

  • js里面不会溢出么?。。

  • nic   2013/10/18

    就一个简单的fib怎么会要四五十秒?!一看就知道作者的程序有问题。比如JavaScript版本的n是一个字符串,每次比较都要转换类型,程序修改后就只要和java差不多的时间了。python支持无限精度的整数,&运算也不能解决问题。如果在现实世界中要算第1亿个fib数,用C语言也不会有多快,这种比较也没有什么实际意义吧

  • FreeBird   2014/02/09

    为什么我亲测的情况和博文中的差别很大呢?我用python3来跑fib(1,000,000),几乎是瞬间就出结果了,跑fib(100,000,000),16s就出结果了。不过我稍微改写了一下python版的程序(后来我试了一下,用while的版本也差不多时间出结果):
    def fib(n):
    SZ = 2 ** 64
    a, b = 1, 0
    for i in range(n):
    t = b
    b = (a + b) % SZ
    a = t
    return b

  • 也就是内存延迟及相应地动态语言的分支浪费了许多时间

  • 在下小菜一个,请问那个C语言的fib程序在Visual Studio2013中为什么无法运行呢?(代码保证一致)是不是数值太大了?

跳到底部
返回顶部