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

本贴最后更新于 4129 天前,其中的信息可能已经事过景迁

翻译自 Anthony J Bonkoski


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

用Python语言实现如下:

def fib(n):
    SZ = 2**64
    i = 0
    a, b = 1, 0
    while i < n:
        t = b
        b = (b+a) % SZ
        a = t
        i = i + 1
    return b

用C语言实现如下:

 

#include <stdio.h>
#include <stdlib.h>
typedef unsigned long ulong;

int main(int argc, char *argv[])
{
ulong n = atoi(argv[1]);
ulong a = 1;
ulong b = 0;
ulong t;

for(ulong i = 0; i &lt; n; i++) {
    t = b;
    b = a+b;
    a = t;
}

printf(&quot;%lu\n&quot;, b);
return 0;

}

 

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

 

=======================================================
  语言                               时间 (秒)
=======================================================
  Java                               0.133
  C Language                         0.006
  CPython                            0.534
  Javascript V8                      0.284

 

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

 

=======================================================
  语言                              时间(秒)
=======================================================
  Java                               0.300
  C Language                         0.172
  CPython                            47.909
  Javascript V8                      24.179

 

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

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

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

0000000000400480 <main>:
247   400480:       48 83 ec 08             sub    $0x8,%rsp
248   400484:       48 8b 7e 08             mov    0x8(%rsi),%rdi
249   400488:       ba 0a 00 00 00          mov    $0xa,%edx
250   40048d:       31 f6                   xor    %esi,%esi
251   40048f:       e8 cc ff ff ff          callq  400460 <strtol@plt>
252   400494:       48 98                   cltq
253   400496:       31 d2                   xor    %edx,%edx
254   400498:       48 85 c0                test   %rax,%rax
255   40049b:       74 26                   je     4004c3 <main+0x43>
256   40049d:       31 c9                   xor    %ecx,%ecx
257   40049f:       31 f6                   xor    %esi,%esi
258   4004a1:       bf 01 00 00 00          mov    $0x1,%edi
259   4004a6:       eb 0e                   jmp    4004b6 <main+0x36>
260   4004a8:       0f 1f 84 00 00 00 00    nopl   0x0(%rax,%rax,1)
261   4004af:       00
262   4004b0:       48 89 f7                mov    %rsi,%rdi
263   4004b3:       48 89 d6                mov    %rdx,%rsi
264   4004b6:       48 83 c1 01             add    $0x1,%rcx
265   4004ba:       48 8d 14 3e             lea    (%rsi,%rdi,1),%rdx
266   4004be:       48 39 c8                cmp    %rcx,%rax
267   4004c1:       77 ed                   ja     4004b0 <main+0x30>
268   4004c3:       be ac 06 40 00          mov    $0x4006ac,%esi
269   4004c8:       bf 01 00 00 00          mov    $0x1,%edi
270   4004cd:       31 c0                   xor    %eax,%eax
271   4004cf:       e8 9c ff ff ff          callq  400470 <__printf_chk@plt>
272   4004d4:       31 c0                   xor    %eax,%eax
273   4004d6:       48 83 c4 08             add    $0x8,%rsp
274   4004da:       c3                      retq
275   4004db:       90                      nop

 

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

262   4004b0:       48 89 f7                mov    %rsi,%rdi
263   4004b3:       48 89 d6                mov    %rdx,%rsi
264   4004b6:       48 83 c1 01             add    $0x1,%rcx
265   4004ba:       48 8d 14 3e             lea    (%rsi,%rdi,1),%rdx
266   4004be:       48 39 c8                cmp    %rcx,%rax
267   4004c1:       77 ed                   ja     4004b0 <main+0x30>

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

a:  %rsi
b:  %rdx
t:  %rdi
i:  %rcx
n:  %rax

 

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

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

loop:   t = a
        a = b
        i = i+1
        b = a+t
        if(n > i) goto loop

整个内部循环仅用六条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次。

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

void main(void)
{
    for(int i = 0; i < 1000000; i++) {
         int n = random();
         if(n >= 0) {
            printf("positive!\n");
        } else {
            printf("negative!\n");
        }
    }
}

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

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

void exec_instruction(instruction_t *inst)
{
    switch(inst->opcode) {
        case ADD:    // do add
        case LOAD:   // do load
        case STORE:  // do store
        case GOTO:   // do goto
    }
}

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

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

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

 

  • C

    C 语言是一门通用计算机编程语言,应用广泛。C 语言的设计目标是提供一种能以简易的方式编译、处理低级存储器、产生少量的机器码以及不需要任何运行环境支持便能运行的编程语言。

    85 引用 • 165 回帖 • 2 关注

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...

推荐标签 标签

  • Maven

    Maven 是基于项目对象模型(POM)、通过一小段描述信息来管理项目的构建、报告和文档的软件项目管理工具。

    186 引用 • 318 回帖 • 282 关注
  • Firefox

    Mozilla Firefox 中文俗称“火狐”(正式缩写为 Fx 或 fx,非正式缩写为 FF),是一个开源的网页浏览器,使用 Gecko 排版引擎,支持多种操作系统,如 Windows、OSX 及 Linux 等。

    8 引用 • 30 回帖 • 409 关注
  • 程序员

    程序员是从事程序开发、程序维护的专业人员。

    574 引用 • 3533 回帖
  • wolai

    我来 wolai:不仅仅是未来的云端笔记!

    2 引用 • 14 回帖 • 1 关注
  • 工具

    子曰:“工欲善其事,必先利其器。”

    288 引用 • 734 回帖 • 1 关注
  • C

    C 语言是一门通用计算机编程语言,应用广泛。C 语言的设计目标是提供一种能以简易的方式编译、处理低级存储器、产生少量的机器码以及不需要任何运行环境支持便能运行的编程语言。

    85 引用 • 165 回帖 • 2 关注
  • 游戏

    沉迷游戏伤身,强撸灰飞烟灭。

    177 引用 • 816 回帖
  • 链书

    链书(Chainbook)是 B3log 开源社区提供的区块链纸质书交易平台,通过 B3T 实现共享激励与价值链。可将你的闲置书籍上架到链书,我们共同构建这个全新的交易平台,让闲置书籍继续发挥它的价值。

    链书社

    链书目前已经下线,也许以后还有计划重制上线。

    14 引用 • 257 回帖
  • 数据库

    据说 99% 的性能瓶颈都在数据库。

    343 引用 • 723 回帖
  • 996
    13 引用 • 200 回帖 • 10 关注
  • VirtualBox

    VirtualBox 是一款开源虚拟机软件,最早由德国 Innotek 公司开发,由 Sun Microsystems 公司出品的软件,使用 Qt 编写,在 Sun 被 Oracle 收购后正式更名成 Oracle VM VirtualBox。

    10 引用 • 2 回帖
  • 阿里巴巴

    阿里巴巴网络技术有限公司(简称:阿里巴巴集团)是以曾担任英语教师的马云为首的 18 人,于 1999 年在中国杭州创立,他们相信互联网能够创造公平的竞争环境,让小企业通过创新与科技扩展业务,并在参与国内或全球市场竞争时处于更有利的位置。

    43 引用 • 221 回帖 • 106 关注
  • SpaceVim

    SpaceVim 是一个社区驱动的模块化 vim/neovim 配置集合,以模块的方式组织管理插件以
    及相关配置,为不同的语言开发量身定制了相关的开发模块,该模块提供代码自动补全,
    语法检查、格式化、调试、REPL 等特性。用户仅需载入相关语言的模块即可得到一个开箱
    即用的 Vim-IDE。

    3 引用 • 31 回帖 • 105 关注
  • 又拍云

    又拍云是国内领先的 CDN 服务提供商,国家工信部认证通过的“可信云”,乌云众测平台认证的“安全云”,为移动时代的创业者提供新一代的 CDN 加速服务。

    21 引用 • 37 回帖 • 548 关注
  • WiFiDog

    WiFiDog 是一套开源的无线热点认证管理工具,主要功能包括:位置相关的内容递送;用户认证和授权;集中式网络监控。

    1 引用 • 7 回帖 • 591 关注
  • 小说

    小说是以刻画人物形象为中心,通过完整的故事情节和环境描写来反映社会生活的文学体裁。

    28 引用 • 108 回帖
  • MyBatis

    MyBatis 本是 Apache 软件基金会 的一个开源项目 iBatis,2010 年这个项目由 Apache 软件基金会迁移到了 google code,并且改名为 MyBatis ,2013 年 11 月再次迁移到了 GitHub。

    170 引用 • 414 回帖 • 387 关注
  • 前端

    前端技术一般分为前端设计和前端开发,前端设计可以理解为网站的视觉设计,前端开发则是网站的前台代码实现,包括 HTML、CSS 以及 JavaScript 等。

    247 引用 • 1348 回帖 • 1 关注
  • PWL

    组织简介

    用爱发电 (Programming With Love) 是一个以开源精神为核心的民间开源爱好者技术组织,“用爱发电”象征开源与贡献精神,加入组织,代表你将遵守组织的“个人开源爱好者”的各项条款。申请加入:用爱发电组织邀请帖
    用爱发电组织官网:https://programmingwithlove.stackoverflow.wiki/

    用爱发电组织的核心驱动力:

    • 遵守开源守则,体现开源&贡献精神:以分享为目的,拒绝非法牟利。
    • 自我保护:使用适当的 License 保护自己的原创作品。
    • 尊重他人:不以各种理由、各种漏洞进行未经允许的抄袭、散播、洩露;以礼相待,尊重所有对社区做出贡献的开发者;通过他人的分享习得知识,要留下足迹,表示感谢。
    • 热爱编程、热爱学习:加入组织,热爱编程是首当其要的。我们欢迎热爱讨论、分享、提问的朋友,也同样欢迎默默成就的朋友。
    • 倾听:正确并恳切对待、处理问题与建议,及时修复开源项目的 Bug ,及时与反馈者沟通。不抬杠、不无视、不辱骂。
    • 平视:不诋毁、轻视、嘲讽其他开发者,主动提出建议、施以帮助,以和谐为本。只要他人肯努力,你也可能会被昔日小看的人所超越,所以请保持谦虚。
    • 乐观且活跃:你的努力决定了你的高度。不要放弃,多年后回头俯瞰,才会发现自己已经成就往日所仰望的水平。积极地将项目开源,帮助他人学习、改进,自己也会获得相应的提升、成就与成就感。
    1 引用 • 487 回帖 • 2 关注
  • JVM

    JVM(Java Virtual Machine)Java 虚拟机是一个微型操作系统,有自己的硬件构架体系,还有相应的指令系统。能够识别 Java 独特的 .class 文件(字节码),能够将这些文件中的信息读取出来,使得 Java 程序只需要生成 Java 虚拟机上的字节码后就能在不同操作系统平台上进行运行。

    180 引用 • 120 回帖 • 3 关注
  • IBM

    IBM(国际商业机器公司)或万国商业机器公司,简称 IBM(International Business Machines Corporation),总公司在纽约州阿蒙克市。1911 年托马斯·沃森创立于美国,是全球最大的信息技术和业务解决方案公司,拥有全球雇员 30 多万人,业务遍及 160 多个国家和地区。

    17 引用 • 53 回帖 • 140 关注
  • 阿里云

    阿里云是阿里巴巴集团旗下公司,是全球领先的云计算及人工智能科技公司。提供云服务器、云数据库、云安全等云计算服务,以及大数据、人工智能服务、精准定制基于场景的行业解决方案。

    89 引用 • 345 回帖
  • SendCloud

    SendCloud 由搜狐武汉研发中心孵化的项目,是致力于为开发者提供高质量的触发邮件服务的云端邮件发送平台,为开发者提供便利的 API 接口来调用服务,让邮件准确迅速到达用户收件箱并获得强大的追踪数据。

    2 引用 • 8 回帖 • 486 关注
  • Rust

    Rust 是一门赋予每个人构建可靠且高效软件能力的语言。Rust 由 Mozilla 开发,最早发布于 2014 年 9 月。

    58 引用 • 22 回帖
  • RabbitMQ

    RabbitMQ 是一个开源的 AMQP 实现,服务器端用 Erlang 语言编写,支持多种语言客户端,如:Python、Ruby、.NET、Java、C、PHP、ActionScript 等。用于在分布式系统中存储转发消息,在易用性、扩展性、高可用性等方面表现不俗。

    49 引用 • 60 回帖 • 361 关注
  • Postman

    Postman 是一款简单好用的 HTTP API 调试工具。

    4 引用 • 3 回帖 • 7 关注
  • 笔记

    好记性不如烂笔头。

    308 引用 • 793 回帖