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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 4439 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

Java

0m1

26 条回复 • 1970-01-01 08:00:00 +08:00

guotie

2012-09-28 12:47:11 +08:00

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

hu437

2012-09-28 13:45:49 +08:00

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

2012-09-28 13:57:40 +08:00

c那个加个inline试试

fanzeyi

2012-09-28 14:15:10 +08:00

这是一个典型的陷阱啊

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

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

2012-09-28 14:31:58 +08:00

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

fanzeyi

2012-09-28 14:35:37 +08:00

http://gist.github.com/3798284

Java 可敢一战？

fanzeyi

2012-09-28 14:37:33 +08:00

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

clowwindy

2012-09-28 14:44:56 +08:00

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

https://gist.github.com/3798298

aligo

2012-09-28 14:49:16 +08:00

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

哈哈哈，太萌了XD

clowwindy

2012-09-28 14:52:22 +08:00

@fanzeyi

连你的错误一起 copy 了……

http://gist.github.com/3798325

fanzeyi

2012-09-28 14:54:01 +08:00

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

guotie

2012-09-28 14:54:16 +08:00

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

guotie

2012-09-28 14:58:16 +08:00

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

keakon

2012-09-28 15:01:18 +08:00

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

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

clowwindy

2012-09-28 15:01:58 +08:00

@fanzeyi

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

fanzeyi

2012-09-28 15:05:41 +08:00

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

guotie

2012-09-28 15:06:07 +08:00

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

clowwindy

2012-09-28 15:11:12 +08:00

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

lldong

2012-09-28 17:33:50 +08:00

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

air00dd

2012-09-28 21:23:04 +08:00

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

fanzeyi

2012-09-28 22:04:35 +08:00

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

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

2012-09-28 22:07:36 +08:00

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

fanzeyi

2012-09-28 22:10:51 +08:00

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

guotie

2012-09-29 16:32:12 +08:00

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