编程语言中的堆栈性能

Question

编程语言中的堆栈性能

8

仅仅出于好玩，我尝试比较了一些编程语言在使用朴素递归算法计算斐波那契数列时的堆栈性能。代码在所有语言中基本相同，我会发布一个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上发布了测试平台。如果您愿意，请随意添加 :)

- hoheinzollern

4

除了应用于基准测试的通常规则外，（1）OCaml本地编译器非常激进，当处理递归等重要的FP概念时不应比C慢六倍。你使用了字节码解释器吗？（2）C的优化设置是什么？ - user395760

11

你执行了多个样本吗？你去除了异常值吗？你对结果取平均了吗？你测量的是时钟时间还是CPU时间？你甚至听说过统计学吗？ :-) - paxdiablo

2

我感到惊讶的是Java运行时。我以前见过这种情况......在C和Java中使用了快速排序算法，每次Java都比C更快。 - Nicholas

4

@paxdiablo：统计数据是紧随谎言和诬蔑之后的那些东西，对吧？;-) - James McNellis

2

@Nicholas：听起来有些可疑。能否让我们看看你的C代码，并了解你使用的编译器和优化设置？ - R.. GitHub STOP HELPING ICE

显示剩余9条评论

8个回答

11

你对你的配置说得太少了（在基准测试中，细节是至关重要的：命令行、使用的计算机等等）。

当我尝试为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的英特尔Xeon 5150(Core 2)上运行的。另一方面，如果我使用OCaml的字节码编译器ocamlc，我会得到与您结果相似的时间（11秒）。但当然，除非您想基准测试编译速度本身（ocamlc在编译速度方面非常出色），否则没有理由使用字节码编译器来运行速度比较。

- Pascal Cuoq

1

很好，我不知道有两个OCaml编译器，我实际上使用的是字节码编译器...感谢您的解释！ - hoheinzollern

2

@hoheinzollern 这里有四个编译器！还有ocamlc.opt，它是使用ocamlopt编译的生成字节码的编译器，以及ocamlopt.opt，它是使用自身编译的本地编译器。当然，这两个编译器生成的代码与它们各自的字节码编译版本相同。 - Pascal Cuoq

1

@hoheinzollern - 你能否使用ocamlopt更新你上面的结果，这样我们可以得到更好的比较？ - aneccodeal

4

一种可能是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的全部好处...将外部调用放入循环中以获取大约一分钟的运行可能会很有趣。）

- Jon Skeet

在 C 代码中更改分支顺序并不会显著改变性能。现在必须有一些其他的优化，我无法想出来。 - hoheinzollern

另外，为什么C#的实现要慢两倍？（我尝试使用.NET得到了相同的结果，这不是Mono的问题） - hoheinzollern

@hoheinzollem：不知道。请注意，这只是一个非常小的测试，很容易出现Java团队做了某种权衡，.NET团队又做了另一种权衡，而在这种特定情况下，Java方法效果很好的情况。 - Jon Skeet

我刚刚在一个玩具基准测试上尝试了你的优化（在IDE之外，发布模式下，多次运行，桌面版本）：C# 1.73秒，Java .95秒，并且通过你的优化：C# 1.35秒，Java .94秒。这是一个包含一些缺陷但还不错的小型基准测试 :) - Lasse Espeholt

@Jon - 这可能是CLR没有解释代码以获取跟踪结果的结果，因此猜测了错误的首选路径吗？我在某个地方读到CLR总是先编译。 - Stephen C

在我的笔记本电脑上，32位.Net 4 CLR上的C#版本对于“classic”版本需要0.77秒，对于“optimized”版本（发布模式，没有调试器）需要0.73秒。不管“优化”如何，64位版本都需要0.70秒。 - Gabe

4

我可以解释一下Python的性能。在递归方面，Python的性能非常糟糕，应该尽量避免使用递归。特别是因为默认情况下，递归深度只有1000就会发生堆栈溢出...

至于Java的性能，那是惊人的。Java打败C是很少见的（即使C端只有非常少的编译器优化）... JIT可能正在进行记忆化或尾递归...

- Rafe Kettler

吹毛求疵：CPython 的递归限制默认为 1000，在常见的桌面架构上至少是这样。否则，没问题。 - user395760

2

是的，递归对Python来说并不好，特别是在这么深的情况下。我决定尝试使用Psyco（JIT编译器）和Cython两种方法。Psyco将时间从75.6秒降至3.36秒。使用Cython，我能够将其降至1.27秒。如果时间与OP中的时间成比例，那么Cython代码在他的机器上运行大约需要1.79秒。按我的标准来看，这相当不错，但也许时间不会如此平稳地缩短。 - Justin Peel

@delnan：这因操作系统和版本而异，但是在我现在使用的机器上，它是1000。 - Rafe Kettler

还有它需要花费的时间来计算每行开头的空格 :) - JeremyP

@JeremyP：如果你真的相信这一点（虽然听起来有点玩笑，但谁也不能确定...）：不是，Python不是解释型语言。它在执行之前会编译成字节码（并且所有被导入的内容都会被缓存/写入磁盘的字节码，因此实际上很少编译）。 - user395760

@delnan：当然这是开玩笑的。这就是为什么我在评论结尾加了一个笑脸。 - JeremyP

2

请注意，如果Java Hotspot虚拟机足够聪明以缓存fib()函数的调用结果，它可以将该算法的指数成本降至接近线性成本。

- user268396

3

我足够聪明，可以将fib函数的调用进行记忆化。我用static const int fib[] = { 1, 1, 2, 3, ... };来替换它们，这比在代码中实现int范围内可能出现的最小值要小。 - R.. GitHub STOP HELPING ICE

但是，如果JVM使用滑动窗口或其他方式来记忆最近N次对fib()的调用，它将优于您的静态查找表。 - user268396

1

@user268396：不需要。R..只需要一个包含47个斐波那契数的数组。第48个会导致32位整数溢出。 - JeremyP

1

使用C语言编程时，您应该声明斐波那契函数为"inline"，或者使用gcc编译器，在编译选项中添加"-finline-functions"参数。这将允许编译器进行递归内联操作。这也是为什么使用"-O3"可以获得更好性能的原因，因为它会激活"-finline-functions"。编辑：您需要至少指定-O / -O1才能进行递归内联，即使函数被声明为inline。实际上，通过测试我发现，声明函数为inline并使用"-O "作为编译标志，或者只使用"-O -finline-functions"，我的递归斐波那契代码比"-O2"或"-O2 -finline-functions"更快。

- steabert

1

我写了一个C版本的朴素斐波那契函数，并在gcc（4.3.2 Linux）中将其编译为汇编语言。然后我使用gcc -O3进行了编译。

未经优化的版本有34行，看起来像是C代码的直接翻译。

经过优化的版本有190行，（很难确定）它似乎至少内联了值为5以下的调用。

- JeremyP

0

你可以尝试的一个 C 技巧是禁用堆栈检查（即内置代码，确保堆栈足够大，以允许当前函数的局部变量进行额外分配）。对于递归函数来说可能会有风险，也可能是 C 时序缓慢的原因之一：执行程序可能已经耗尽了堆栈空间，这迫使堆栈检查在实际运行期间重新分配整个堆栈多次。

尝试近似计算所需的堆栈大小，并强制链接器分配相应的堆栈空间。然后禁用堆栈检查并重新编译程序。

- Olof Forshell

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- paxdiablo · Accepted Answer

你可能需要提高你的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;
}

这再次缩短了时间，但我怀疑我们到达了收益递减的点。