编程语言中的堆栈性能

Question

只是为了好玩,我试图比较使用朴素递归算法计算Fibonacci系列的几种编程语言的堆栈性能.代码在所有语言中都是相同的,我将发布一个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:我使用优化编译器ocamlopt更新了ocaml实现的运行时.我还在https://github.com/hoheinzollern/fib-test上发布了测试平台.如果你想要随意添加它:)

Answer 1

您可能希望提高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;
}

这再次缩短了时间,但我怀疑我们在这里达到了收益递减的程度.

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)上.ocamlc另一方面,如果我使用字节码OCaml编译器,我会得到类似于结果的时间(11s).但是当然,对于运行速度比较,没有理由使用字节码编译器,除非你想要编译编译速度本身(ocamlc对于编译速度来说是惊人的).

Answer 3

一种可能性是 C 编译器根据第一个分支 ( n < 2) 是更频繁采用的分支的猜测进行优化。它必须纯粹在编译时执行此操作：进行猜测并坚持下去。

Hotspot 可以运行代码，更频繁地查看实际发生的情况，并根据该数据重新优化。

通过颠倒以下逻辑，您也许if可以看到差异：

public static int fib(int n) {
 if (n >= 2) return fib(n-1) + fib(n-2);
 return 1;
}

无论如何，值得一试：）

与往常一样，还要检查所有平台的优化设置。显然，C 和 Java 的编译器设置，尝试使用 Hotspot 的客户端版本与服务器版本。（请注意，您需要运行超过一秒左右才能真正获得 Hotspot 的全部好处...将外部调用放入循环中以获得一分钟左右的运行可能会很有趣。）