编程语言中的堆栈性能
只是为了好玩，我试图比较使用朴素递归算法计算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上发布了测试平台。 如果你想要随意添加它:)
您可能希望提高C编译器的优化级别。 使用gcc -O3 ，这会产生很大的影响，从2.015秒降至0.766秒，减少约62％。
除此之外，您需要确保已经正确测试。 你应该运行每个程序十次，删除exception值（最快和最慢），然后平均其他八个。
此外，确保测量CPU时间而不是时钟时间。
除此之外，我不会考虑一个不错的统计分析，它可能会受到噪音的影响，使你的结果无用。
对于它的价值，上面的那些C时间是七次运行，并且在平均之前取出exception值。
实际上，这个问题表明了在针对高性能时算法选择的重要性。 虽然递归解决方案通常很优雅，但是这个解决方案会遇到复制大量计算的错误。 迭代版本：
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; }
这再次减少了时间，但我怀疑我们在这里达到了收益递减的程度。
你对配置说的很少（在基准测试中，细节就是一切：命令行，计算机使用，……）
当我尝试为OCaml重现时，我得到：
let rec fn = 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 ，我会得到类似于你的结果的时间（11s）。 但是，当然，对于运行速度比较，没有理由使用字节码编译器，除非您想要对编译本身的速度进行基准测试（ ocamlc对于编译速度ocamlc是惊人的）。
一种可能性是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的全部好处...将外部调用放在一个循环中以获得一分钟左右的运行可能会很有趣。）
我可以解释一下Python的性能。 Python的递归性能充其量是非常糟糕的，并且应该像编码中的瘟疫一样避免它。 特别是因为默认情况下堆栈溢出只发生在1000的递归深度…
至于Java的表现，这太棒了。 Java胜过C很少见（即使在C端只有很少的编译器优化）…… JIT可能做的是memoization或tail recursion ……
请注意，如果Java Hotspot VM足够智能以记忆fib（）调用，它可以将算法的指数成本降低到更接近线性成本的值。
我写了一个天真的Fibonacci函数的C版本，并在gcc（4.3.2 Linux）中将其编译为汇编程序。 然后我用gcc -O3编译它。
未经优化的版本长34行，看起来像是C代码的直接翻译。
优化的版本是190行长（并且很难说但是）它似乎至少要求最多约5个值的调用。
使用C，您应该声明fibonacci函数“inline”，或者使用gcc将-finline-functions参数添加到编译选项中。 这将允许编译器执行递归内联。 这也是为什么使用-O3可以获得更好的性能，它会激活-finline-functions 。
编辑您需要至少指定-O / -O1来进行递归内联，如果函数是内联声明的话。 实际上，测试自己我发现声明函数内联并使用-O作为编译标志，或者只使用-O -finline-functions ，我的递归fibonacci代码比使用-O2或-O2 -finline-functions更快。
您可以尝试的一个C技巧是禁用堆栈检查（即内置代码，确保堆栈足够大，以允许额外分配当前函数的局部变量）。 这对于递归函数来说可能是冒险的，实际上可能是C次缓慢的原因：执行程序可能已经耗尽了堆栈空间，这迫使堆栈检查在实际运行期间多次重新分配整个堆栈。
尝试近似所需的堆栈大小，并强制链接器分配那么多的堆栈空间。 然后禁用堆栈检查并重新生成程序。