1
guotie OP 补充一点,当把c的递归算法改成非递归时,执行时间不到0.001s,为什么c的递归这么慢?!
|
2
hu437 2012-09-28 13:45:49 +08:00
java的编译器有优化,一般的情况下java虚拟机优化的代码,性能还是很高的
|
3
Js 2012-09-28 13:57:40 +08:00
c那个加个inline试试
|
4
fanzeyi 2012-09-28 14:15:10 +08:00
这是一个典型的陷阱啊
非递归的算法大概是 O(n) 的…… 递归的版本大概是 O(n^2) 的. 明显不能这么看. |
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 |
6
bulldozer 2012-09-28 14:31:58 +08:00
毫秒级别的,估计差异主要是系统如何载入程序,而不是语言跑的速度。
|
7
fanzeyi 2012-09-28 14:35:37 +08:00
|
8
fanzeyi 2012-09-28 14:37:33 +08:00
算 99999999 次 fibonacci(40) 用了 0.28s ..... PS 一样是递归
|
9
clowwindy 2012-09-28 14:44:56 +08:00
打开或关闭 -fno-optimize-sibling-calls 开关,两种不同的优化方式,导致速度相差一倍以上,一种比 JVM 快,一种比 JVM 慢。
https://gist.github.com/3798298 |
11
clowwindy 2012-09-28 14:52:22 +08:00
|
14
guotie OP c版本,gcc仅用-O来编译的版本是最快的,计算45 时,快了40%
|
15
keakon 2012-09-28 15:01:18 +08:00
这个以前反编译过,GCC -O2直接把函数展开了几层,所以计算量少了很多。JIT估计也会这样作弊。
说真的这样测性能很不靠谱,学了汇编就知道,函数调用没啥可优化的,CPU指令都一样,再想快点只能不当成函数调用。 |
16
clowwindy 2012-09-28 15:01:58 +08:00
@fanzeyi
fibonacci 的 divide and conquer 算法通常是用来演示 divide and conquer 的 bad case 的……我想原文作者拿它作为测试不同语言的一个有趣的方法再合适不过了 |
18
guotie OP 还有一点,
go编译出来的文件很大,有1.5M,c编译的版本约6~8k,java的版本700多个字节。 |
19
clowwindy 2012-09-28 15:11:12 +08:00
@fanzeyi 看我 5 楼的结果,gcc O2 + no-optimize-sibling-calls 比 jvm 快。对这个递归,就相当于是遇到了 optimize-sibling-calls 的 bad case 了……
|
20
lldong 2012-09-28 17:33:50 +08:00
用clang编译C看看,clang貌似已经支持尾递归优化了
|
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 |
26
guotie OP 今天用vs2012测了一下,fibonacci(40)居然要8秒多!
|