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

[guotie]

测试环境：
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编译的啊！

[guotie]

补充一点，当把c的递归算法改成非递归时，执行时间不到0.001s，为什么c的递归这么慢？！

[hu437]

java的编译器有优化，一般的情况下java虚拟机优化的代码，性能还是很高的

[Js]

c那个加个inline试试

[fanzeyi]

这是一个典型的陷阱啊

非递归的算法大概是 O(n) 的…… 递归的版本大概是 O(n^2) 的. 明显不能这么看.

[clowwindy]

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]

毫秒级别的，估计差异主要是系统如何载入程序，而不是语言跑的速度。

[fanzeyi]

http://gist.github.com/3798284

Java 可敢一战？

[fanzeyi]

算 99999999 次 fibonacci(40) 用了 0.28s ..... PS 一样是递归

[clowwindy]

打开或关闭 -fno-optimize-sibling-calls 开关，两种不同的优化方式，导致速度相差一倍以上，一种比 JVM 快，一种比 JVM 慢。

https://gist.github.com/3798298

[aligo]

@fanzeyi 本来从昨天晚上搞那个东西到现在，脑袋涨得很大，你给我发来这个太治愈了

哈哈哈，太萌了XD

[clowwindy]

@fanzeyi

连你的错误一起 copy 了……

http://gist.github.com/3798325

[fanzeyi]

@clowwindy 郁闷…… 本来是想把 printf 去掉的…… 我改过了

[guotie]

@bulldozer 不是
用一个稍微比40大的数来验证，例如45，结果会更明显。

[guotie]

c版本，gcc仅用-O来编译的版本是最快的，计算45 时，快了40%

[keakon]

这个以前反编译过，GCC -O2直接把函数展开了几层，所以计算量少了很多。JIT估计也会这样作弊。

说真的这样测性能很不靠谱，学了汇编就知道，函数调用没啥可优化的，CPU指令都一样，再想快点只能不当成函数调用。

[clowwindy]

@fanzeyi

fibonacci 的 divide and conquer 算法通常是用来演示 divide and conquer 的 bad case 的……我想原文作者拿它作为测试不同语言的一个有趣的方法再合适不过了

[fanzeyi]

@clowwindy gcc 对于这样的 bad case 优化无力啊…… 所以会导致这个测试的不公平……

[guotie]

还有一点，
go编译出来的文件很大，有1.5M，c编译的版本约6～8k，java的版本700多个字节。

[clowwindy]

@fanzeyi 看我 5 楼的结果，gcc O2 + no-optimize-sibling-calls 比 jvm 快。对这个递归，就相当于是遇到了 optimize-sibling-calls 的 bad case 了……

[lldong]

用clang编译C看看，clang貌似已经支持尾递归优化了

[air00dd]

@fanzeyi 请问0.28s的怎么弄的？本人菜鸟。。。

[fanzeyi]

@air00dd =.= 那是写错代码了……

[oa414]

https://gist.github.com/3800046/7fa3a7e96e8aab60ba70c033c00dd219a67fd22d

数据量大的话Ruby这种解释型的语言好慢……我实在不想等了，用@fanzeyi 1／10的数据量，
real 1m2.031s
user 1m1.744s
sys 0m0.108s

[oa414]

@fanzeyi 请问怎么贴gist的代码？

[fanzeyi]

@oa414 https 改成 http, 然后 3800046/ 后面的去掉

[guotie]

今天用vs2012测了一下，fibonacci(40)居然要8秒多！