在编程语言堆栈性能 [英] Stack performance in programming languages

问题描述

只是为了好玩，我试图比较一对夫妇的编程语言使用的计算天真递归算法斐波那契数列中的堆栈性能。在code主要是在所有的语言一样，我会发布的Java版本：

Just for fun, I tried to compare the stack performance of a couple of programming languages calculating the Fibonacci series using the naive recursive algorithm. The code is mainly the same in all languages, i'll post a java version:

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我得到了这些时间：

Ok so the point is that using this algorithm with input 40 I got these timings:

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

他们都采取了在使用每种语言的官方仓库可用的版本Ubuntu的10.04箱，双核英特尔​​机器上。

They are taken in a Ubuntu 10.04 box using the versions of each language available in the official repositories, on a dual core intel machine.

我知道，像OCaml的功能性语言有来自处理函数一阶公民放缓，都没有问题解释，因为这一事实，即它在本次测试中唯一跨preTED语言的CPython的运行时间，但我是由Java运行时间pssed IM $ p $这是C为相同算法的一半！你认为这对JIT编译？

I know that functional languages like ocaml have the slowdown that comes from treating functions as first order citizens and have no problem to explain CPython's running time because of the fact that it's the only interpreted language in this test, but I was impressed by the java running time which is half of the c for the same algorithm! Would you attribute this to the JIT compilation?

你会如何解释这些结果？

How would you explain these results?

编辑：谢谢你的回复有趣！我承认，这不是一个适当的基准（从来没有说过它是：P），也许我可以做一个更好的，并邮寄到你下一次，在我们讨论一下光：）

thank you for the interesting replies! I recognize that this is not a proper benchmark (never said it was :P) and maybe I can make a better one and post it to you next time, in the light of what we've discussed :)

编辑2：我更新了OCaml的执行运行时，使用优化编译器ocamlopt。此外，我发表了 https://github.com/hoheinzollern/fib-test 的测试平台。如果你想随意作出补充吧：）

EDIT 2: I updated the runtime of the ocaml implementation, using the optimizing compiler ocamlopt. Also I published the testbed at https://github.com/hoheinzollern/fib-test. Feel free to make additions to it if you want :)

推荐答案

您可能要杀青你的C编译器的优化级别。随着的gcc -O3 ，使一个很大的区别，从2.015秒到0.766秒下降，降幅约62％。

You might want to crank up the optimisation level of your C compiler. With gcc -O3, that makes a big difference, a drop from 2.015 seconds to 0.766 seconds, a reduction of about 62%.

除此之外，你需要确保你已经正确测试。您应该运行的每个程序的十倍，去掉异常值（最快和最慢），那么平均其他八。

Beyond that, you need to ensure you've tested correctly. You should run each program ten times, remove the outliers (fastest and slowest), then average the other eight.

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

In addition, make sure you're measuring CPU time rather than clock time.

任何低于这一点，我不会考虑一个体面的统计分析，它很可能会受到噪音，使您的结果无效。

Anything less than that, I would not consider a decent statistical analysis and it may well be subject to noise, rendering your results useless.

有关它的价值，以上与C时序分别为七奔跑的异常值平均之前取出。

For what it's worth, those C timings above were for seven runs with the outliers taken out before averaging.

其实，这个问题给出算法的选择是多么的重要瞄准了高性能的时候。虽然递归解决方案通常是优雅的，这一个从您复制的很多故障遭受的计算。迭代版本：

In fact, this question shows how important algorithm selection is when aiming for high performance. Although recursive solutions are usually elegant, this one suffers from the fault that you duplicate a lot of calculations. The iterative version:

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％进一步降低和一个高达的从原始code折减的96％。

further drops the time taken, from 0.766 seconds to 0.078 seconds, a further reduction of 89% and a whopping reduction of 96% from the original code.

和作为最后的尝试，你应该尝试下，结合一个查找表超过一定点的计算：

And, as a final attempt, you should try out the following, which combines a lookup table with calculations beyond a certain point:

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;
}

这减少了一次又一次，但我怀疑我们在这里打收益递减点。

That reduces the time yet again but I suspect we're hitting the point of diminishing returns here.

这篇关于在编程语言堆栈性能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！