V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
guotie
V2EX  ›  编程

使用递归计算fibonacci测试c,java,go的性能,意外出现了!!!

  •  
  •   guotie · 2012-09-28 12:45:51 +08:00 · 7351 次点击
    这是一个创建于 4437 天前的主题,其中的信息可能已经有所发展或是发生改变。
    测试环境:
    centos liinux 64位
    gcc 4.4.4
    go 1.0.3
    java:
    java version "1.7.0_05-icedtea"
    OpenJDK Runtime Environment (rhel-2.2.1.el6_3-x86_64)
    OpenJDK 64-Bit Server VM (build 23.0-b21, mixed mode)

    计算fibonacci的代码用的这里的代码:
    http://fengmk2.github.com/blog/2011/fibonacci/nodejs-python-php-ruby-lua.html

    c,go,java计算的结果如下:
    java:
    real 0m1.233s
    user 0m1.220s
    sys 0m0.019s

    go:
    real 0m1.719s
    user 0m1.718s
    sys 0m0.001s

    c:
    real 0m1.762s
    user 0m1.760s
    sys 0m0.001s

    运行速度竟然是java > go > c

    c编译的时候,还是用-O2编译的啊!
    26 条回复    1970-01-01 08:00:00 +08:00
    guotie
        1
    guotie  
    OP
       2012-09-28 12:47:11 +08:00
    补充一点,当把c的递归算法改成非递归时,执行时间不到0.001s,为什么c的递归这么慢?!
    hu437
        2
    hu437  
       2012-09-28 13:45:49 +08:00
    java的编译器有优化,一般的情况下java虚拟机优化的代码,性能还是很高的
    Js
        3
    Js  
       2012-09-28 13:57:40 +08:00
    c那个加个inline试试
    fanzeyi
        4
    fanzeyi  
       2012-09-28 14:15:10 +08:00
    这是一个典型的陷阱啊

    非递归的算法大概是 O(n) 的…… 递归的版本大概是 O(n^2) 的. 明显不能这么看.
    clowwindy
        5
    clowwindy  
       2012-09-28 14:26:38 +08:00
    C 加个 inline 之后:

    $ gcc -O2 -s test.c && time ./a.out
    102334155

    real 0m0.679s
    user 0m0.678s
    sys 0m0.001s

    $ gcc -O2 -fno-optimize-sibling-calls -s test.c && time ./a.out
    102334155

    real 0m0.337s
    user 0m0.335s
    sys 0m0.001s

    $ time java test
    102334155

    real 0m0.524s
    user 0m0.535s
    sys 0m0.017s
    bulldozer
        6
    bulldozer  
       2012-09-28 14:31:58 +08:00
    毫秒级别的,估计差异主要是系统如何载入程序,而不是语言跑的速度。
    fanzeyi
        7
    fanzeyi  
       2012-09-28 14:35:37 +08:00
    http://gist.github.com/3798284

    Java 可敢一战?
    fanzeyi
        8
    fanzeyi  
       2012-09-28 14:37:33 +08:00
    算 99999999 次 fibonacci(40) 用了 0.28s ..... PS 一样是递归
    clowwindy
        9
    clowwindy  
       2012-09-28 14:44:56 +08:00
    打开或关闭 -fno-optimize-sibling-calls 开关,两种不同的优化方式,导致速度相差一倍以上,一种比 JVM 快,一种比 JVM 慢。

    https://gist.github.com/3798298
    aligo
        10
    aligo  
       2012-09-28 14:49:16 +08:00
    @fanzeyi 本来从昨天晚上搞那个东西到现在,脑袋涨得很大,你给我发来这个太治愈了

    哈哈哈,太萌了XD
    clowwindy
        11
    clowwindy  
       2012-09-28 14:52:22 +08:00
    @fanzeyi

    连你的错误一起 copy 了……

    http://gist.github.com/3798325
    fanzeyi
        12
    fanzeyi  
       2012-09-28 14:54:01 +08:00
    @clowwindy 郁闷…… 本来是想把 printf 去掉的…… 我改过了
    guotie
        13
    guotie  
    OP
       2012-09-28 14:54:16 +08:00
    @bulldozer 不是
    用一个稍微比40大的数来验证,例如45,结果会更明显。
    guotie
        14
    guotie  
    OP
       2012-09-28 14:58:16 +08:00
    c版本,gcc仅用-O来编译的版本是最快的,计算45 时,快了40%
    keakon
        15
    keakon  
       2012-09-28 15:01:18 +08:00
    这个以前反编译过,GCC -O2直接把函数展开了几层,所以计算量少了很多。JIT估计也会这样作弊。

    说真的这样测性能很不靠谱,学了汇编就知道,函数调用没啥可优化的,CPU指令都一样,再想快点只能不当成函数调用。
    clowwindy
        16
    clowwindy  
       2012-09-28 15:01:58 +08:00
    @fanzeyi

    fibonacci 的 divide and conquer 算法通常是用来演示 divide and conquer 的 bad case 的……我想原文作者拿它作为测试不同语言的一个有趣的方法再合适不过了
    fanzeyi
        17
    fanzeyi  
       2012-09-28 15:05:41 +08:00
    @clowwindy gcc 对于这样的 bad case 优化无力啊…… 所以会导致这个测试的不公平……
    guotie
        18
    guotie  
    OP
       2012-09-28 15:06:07 +08:00
    还有一点,
    go编译出来的文件很大,有1.5M,c编译的版本约6~8k,java的版本700多个字节。
    clowwindy
        19
    clowwindy  
       2012-09-28 15:11:12 +08:00
    @fanzeyi 看我 5 楼的结果,gcc O2 + no-optimize-sibling-calls 比 jvm 快。对这个递归,就相当于是遇到了 optimize-sibling-calls 的 bad case 了……
    lldong
        20
    lldong  
       2012-09-28 17:33:50 +08:00
    用clang编译C看看,clang貌似已经支持尾递归优化了
    air00dd
        21
    air00dd  
       2012-09-28 21:23:04 +08:00
    @fanzeyi 请问0.28s的怎么弄的?本人菜鸟。。。
    fanzeyi
        22
    fanzeyi  
       2012-09-28 22:04:35 +08:00
    @air00dd =.= 那是写错代码了……
    oa414
        23
    oa414  
       2012-09-28 22:06:36 +08:00
    https://gist.github.com/3800046/7fa3a7e96e8aab60ba70c033c00dd219a67fd22d

    数据量大的话Ruby这种解释型的语言好慢……我实在不想等了,用@fanzeyi 1/10的数据量,
    real 1m2.031s
    user 1m1.744s
    sys 0m0.108s
    oa414
        24
    oa414  
       2012-09-28 22:07:36 +08:00
    @fanzeyi 请问怎么贴gist的代码?
    fanzeyi
        25
    fanzeyi  
       2012-09-28 22:10:51 +08:00
    @oa414 https 改成 http, 然后 3800046/ 后面的去掉
    guotie
        26
    guotie  
    OP
       2012-09-29 16:32:12 +08:00
    今天用vs2012测了一下,fibonacci(40)居然要8秒多!
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5323 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 01:29 · PVG 09:29 · LAX 17:29 · JFK 20:29
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.