关于改进Has​​kell在Fibonacci微基准测试中与C相比的性能

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

哈斯克尔:

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在这个微基准测试中做的事情变得更慢的方式吗？(我不是要求渐近更快的算法来计算纤维.)

非常感谢你.

[编辑]

事实证明,这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成一个在堆栈上运行soleley的函数.只需查看配置文件...只分配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的情况的代码.返回值在寄存器中传递.

一句话:一切似乎都在发挥作用,你不可能通过改变程序来挤出更多.自定义堆栈检查是一个明显的减速源,但不确定它是否可以归咎于全时差异.

Answer 2

这些似乎是一个非常虚弱的"基准" barsoap.假设我比较以下几乎同样天真的程序:

module Main where
import System.Environment (getArgs)

fib ::  Int ->  Int
fib 0 = 1
fib 1 = 1
fib 2 = 2 
fib n = (\x y -> x + y + y )  (fib (n-3))  (fib (n-2) )

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

......在另一个角落......

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

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

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

然后,光荣的ghc粉碎gcc,不是太令人惊讶,真的:

$ ghc --make -fforce-recomp fib.hs -o fibh
[1 of 1] Compiling Main             ( fib.hs, fib.o )
Linking fibh ...
$ time ./fibh 40
165580141

real    0m0.013s
user    0m0.007s
sys 0m0.003s

$ gcc fib.c -o fibc
$ time ./fibc 40
165580141

real    0m1.495s
user    0m1.483s
sys 0m0.003s

现在开启优化,ghc加快速度:

$ ghc --make -fforce-recomp fib.hs -O3 -o fibhO
$ time ./fibhO 40
165580141

real    0m0.007s
user    0m0.002s
sys 0m0.004s

但gcc终于得到了一个线索.

$ gcc fib.c -O3 -o fibcO
$ time ./fibcO 40
165580141

real    0m0.007s
user    0m0.004s
sys 0m0.002s

我认为解释是ghc对共同子表达式消除的谨慎态度:在(几乎)一切都是表达式的情况下它是危险的,它表明程序员知道如何使用lambda.

Answer 3

GHC 编译这个很好。下一步是对 GHC 后端的输出进行微观优化。在这里使用各种 LLVM 标志会有所帮助。

为此，请使用 ghc-core 检查程序集，并尝试 LLVM 的其他标志以查看得到的结果。

另一种方法是添加少量并行性。