编程语言中的栈性能

Question

为了好玩，我尝试比较几种编程语言在使用简单递归算法计算斐波那契数列时的性能。代码在不同语言中基本相同，我会贴出一个Java版本：

public class Fib {
 public static int fib(int n) {
  if (n < 2) return 1;
  return fib(n-1) + fib(n-2);
 }

 public static void main(String[] args) {
  System.out.println(fib(Integer.valueOf(args[0])));
 }
}

所以重点是，当我用这个算法输入40时，得到了这些时间：

C: 2.796s
Ocaml: 2.372s
Python: 106.407s
Java: 1.336s
C#(mono): 2.956s

这些数据是在一台运行Ubuntu 10.04的电脑上获取的，使用的是每种语言在官方库中可用的版本，电脑是双核英特尔处理器。

我知道像ocaml这样的函数式语言在处理函数时会有一些性能下降，而且我也能解释CPython的运行时间，因为它是这次测试中唯一的解释型语言，但我对Java的运行时间感到惊讶，它的速度是C语言的一半！你认为这和JIT编译有关吗？

你会如何解释这些结果呢？

编辑：感谢大家有趣的回复！我承认这不是一个正式的基准测试（我从来没说过这是 :P），也许下次我可以做一个更好的测试并分享给你们，基于我们讨论的内容 :)

编辑2：我更新了ocaml实现的运行时间，使用了优化编译器ocamlopt。同时我把测试代码发布在了 https://github.com/hoheinzollern/fib-test。如果你想的话，欢迎进行补充 :)

Answer 1

我来给你讲讲Python的性能。Python在递归方面的表现非常糟糕，最好是尽量避免在代码中使用递归。尤其是因为在递归深度达到1000的时候，就会默认出现栈溢出的问题……

至于Java的性能，那就厉害了。Java很少能超过C语言（即使C语言的编译优化很少）……Java的即时编译（JIT）可能在做一些记忆化处理或者尾递归优化……

Answer 2

你对你的配置说得很少（在基准测试中，细节非常重要：命令行、使用的电脑等等）。

当我尝试在OCaml上复现时，我得到了：

let rec f n = if n < 2 then 1 else (f (n-1)) + (f (n-2))

let () = Format.printf "%d@." (f 40)


$ ocamlopt fib.ml
$ time ./a.out 
165580141

real    0m1.643s

这是在一台2.66GHz的Intel Xeon 5150（Core 2）上。如果我使用字节码OCaml编译器ocamlc，我得到的时间和你的结果差不多（11秒）。不过，当然了，如果要进行速度比较，使用字节码编译器就没必要了，除非你想测试编译本身的速度（ocamlc在编译速度上非常出色）。

Answer 3

你可能想要提高你C语言编译器的优化级别。使用 gcc -O3 后，效果会很明显，运行时间从2.015秒降到0.766秒，减少了大约62%。

除此之外，你还需要确保测试的方式是正确的。你应该运行每个程序十次，去掉最快和最慢的结果，然后对其他八次的结果取平均。

另外，确保你测量的是CPU时间，而不是时钟时间。

如果不做到这些，我就不认为这是一个合格的统计分析，结果可能会受到干扰，导致你的结果没有意义。

顺便提一下，上面提到的C语言运行时间是经过七次运行，去掉了异常值后再取的平均。

---

实际上，这个问题显示了选择算法在追求高性能时的重要性。虽然递归解决方案通常很优雅，但这个方法的问题在于你重复计算了很多次。迭代版本：

int fib(unsigned int n) {
    int t, a, b;
    if (n < 2) return 1;
    a = b = 1;
    while (n-- >= 2) {
        t = a + b;
        a = b;
        b = t;
    }
    return b;
}

进一步将运行时间从0.766秒降到0.078秒，减少了89%，相比原始代码减少了惊人的96%。

---

最后，你应该尝试以下方法，它结合了查找表和某个点之后的计算：

static int fib(unsigned int n) {
    static int lookup[] = {
        1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,
        610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657,
        46368, 75025, 121393, 196418, 317811, 514229, 832040,
        1346269, 2178309, 3524578, 5702887, 9227465, 14930352,
        24157817, 39088169, 63245986, 102334155, 165580141 };
    int t, a, b;

    if (n < sizeof(lookup)/sizeof(*lookup))
        return lookup[n];
    a = lookup[sizeof(lookup)/sizeof(*lookup)-2];
    b = lookup[sizeof(lookup)/sizeof(*lookup)-1];
    while (n-- >= sizeof(lookup)/sizeof(*lookup)) {
        t = a + b;
        a = b;
        b = t;
    }

    return b;
}

这又一次减少了时间，但我怀疑我们可能已经到了收益递减的阶段。