performance - 与斐波那契微基准测试中的 C 相比提高 Haskell 的性能

Question

我遇到了this question ，它比较了各种编译器在计算斐波那契数时的性能，以天真的方式。

我尝试用 Haskell 来做这件事，看看它与 C 相比如何。

C代码:

#include <stdio.h>
#include <stdlib.h>

int fib (int n) {
  if (n < 2) return 1;
  return fib (n-1) + fib (n-2);
}

int main (int argc, char* argv[]) {
  printf ("%i\n", fib (atoi(argv[1])));
  return 0;
}

结果:

> gcc -O3 main.c -o fib
> time ./fib 40
165580141
real    0m0.421s
user    0m0.420s
sys 0m0.000s

haskell :

module Main where
import System.Environment (getArgs)

fib :: Int -> Int
fib n | n < 2 = 1
      | otherwise = fib (n-1) + fib (n-2)

main = getArgs >>= print . fib . read . head

结果:

> ghc -O3 -fllvm -optlo-O3 Main.hs -o fib
> time ./fib 40
165580141
real    0m1.476s
user    0m1.476s
sys 0m0.000s

分析与

> ghc -O3 -fllvm -optlo-O3 -prof -auto-all -caf-all -rtsopts Main.hs -fforce-recomp -o fib
> ./fib 40 +RTS -prof

显示 fib需要 100% 的时间和分配，这不足为奇。我对堆进行了一些配置，但不知道它们意味着什么:

> ./fib 40 +RTS -hc

> ./fib 40 +RTS -hd

所以我的问题是:我能做些什么来让这个 Haskell 程序的性能更接近 C，或者这只是 GHC 在这个微基准测试中碰巧让它变慢的方式吗？ (我不是在要求一种渐近更快的算法来计算 fibs。)

非常感谢。

[编辑]

原来 ghc -O3比 ghc -O3 -fllvm -optlo-O3 快在这种情况下。但是 optlo-block-placement为 LLVM 后端带来了明显的不同:

> ghc -O3 Main.hs -o fib -fforce-recomp
> time ./fib 40
165580141
real    0m1.283s
user    0m1.284s
sys 0m0.000s

> ghc -O3 -fllvm -optlo-O3 -o fib -fforce-recomp
> time ./fib 40
165580141
real    0m1.449s
user    0m1.448s
sys 0m0.000s

> ghc -O3 -fllvm -optlo-O3 -optlo-block-placement -o fib -fforce-recomp
> time ./fib 40
165580141
real    0m1.112s
user    0m1.096s
sys 0m0.016s

我想研究这个的原因是因为对于这个程序，C 和 OCaml 都比 Haskell 快得多。我有点不能接受，想了解更多，以确保我已经做了我能做的一切:D

> ocamlopt main.ml -o fib
> time ./fib 40
165580141
real    0m0.668s
user    0m0.660s
sys 0m0.008s

Answer 1

堆配置文件在这里不是很有趣，因为 GHC 编译 fib进入一个在堆栈上单独操作的函数。只需查看配置文件...仅分配了 800 个字节，main 的小开销执行。

就 GHC 的核心级别而言，这实际上得到了尽可能优化。不过，低级代码生成是另一回事。让我们快速深入了解 GHC 生成的代码:

_Main_zdwfib_info:
.Lc1RK:
    leal -8(%ebp),%eax
    cmpl 84(%ebx),%eax
    jb .Lc1RM

这是对堆栈空间的检查。可能是 C 不需要的东西，因为它可以让操作系统处理堆栈空间分配。 Haskell 有用户级线程，所以栈空间是手动管理的。

    cmpl $2,0(%ebp)
    jl .Lc1RO

与您的代码中的 2 进行比较。

    movl 0(%ebp),%eax
    decl %eax

参数从堆栈中重新加载并递减以获取递归调用的参数。重新加载可能是不必要的 - 但不确定它是否有所作为。

    movl %eax,-8(%ebp)
    movl $_s1Qp_info,-4(%ebp)
    addl $-8,%ebp
    jmp _Main_zdwfib_info

参数和返回地址被压入栈顶，我们直接跳转到标签处进行递归。

.Lc1RO:
    movl $1,%esi
    addl $4,%ebp
    jmp *0(%ebp)

参数小于2的情况的代码。返回值在寄存器中传递。

底线:一切似乎都在按应有的方式工作，您不太可能通过更改程序来从中榨取更多。自定义堆栈检查是一个明显的减速源，但不确定它是否可以归咎于完整的时间差异。