Haskell - for循环的有效等价物？

Question

我一直在做一些实验,这是我找到的东西.考虑以下C程序:

int main()
{
   for(int i = 0;
       i < 1000000;
       ++i)
   {}
}

和以下Haskell程序:

import System.IO

loop :: Int -> IO ()
loop n = if 0 == n then return () else loop (n-1)

main = loop 1000000

以下是time上述C程序的输出:

real    0m0.003s
user    0m0.000s
sys 0m0.000s

......以及Haskell计划:

real    0m0.028s
user    0m0.027s
sys 0m0.000s

起初我认为gcc检测到一个空循环并对其进行优化,但在增加迭代次数后,程序的运行时间也增加了.以下是time两个程序的输出,迭代次数设置为10000000:

C版

real    0m0.024s
user    0m0.023s
sys 0m0.000s

Haskell版本

real    0m0.245s
user    0m0.247s
sys 0m0.000s

如您所见,Haskell程序慢了10倍.

问题是:forHaskell中循环的有效替代方法是什么？正如我们刚刚看到的那样,简单的递归会使程序减慢大约10倍(这可能是尾递归优化完成的).

Answer 1

首先,你要将你的C代码翻译成这个,

main = go 0
    where
        go :: Int -> IO ()
        go i | i < 1000000 = go (i+1)
             | otherwise   = return ()

哪个ghc优化到空程序.它将最终值移动到寄存器中,与之进行比较,然后返回():

Main_zdwa_info: 
    cmpq    $1000000, %r14          # imm = 0xF4240
    movl    $1000000, %eax          # imm = 0xF4240
    cmovlq  %rax, %r14
    movq    (%rbp), %rax
    movl    $ghczmprim_GHCziUnit_Z0T_closure+1, %ebx
    jmpq    *%rax  # TAILCALL

运行时:

$ time ./A
./A  0.00s user 0.00s system 88% cpu 0.004 total

不花时间.

但是,一般而言,GHC 为尾递归函数发出等效的循环,例如GCC.特别是,您需要编译数字基准测试以ghc -O2 -fllvm获得最佳结果.如果您不希望您的程序被优化,那么ghc将很乐意执行您指定的程序,在这种情况下,这将涉及大量冗余工作,这些工作将在更高的优化级别上被删除.

有关分析Haskell程序的低级性能的更多信息,请查看RWH ch25.

Answer 2

对于循环结构,您通常必须使用Worker/Wrapper样式来帮助GHC点优化,而不是在外部函数级别重复.

Grigory Javadyan在评论中说,原始版本在-O3处得到优化,我希望在-O2检测到这个版本:

import System.IO

loop :: Int -> IO ()
loop n = go n
  where
    go n | n <= 0 = return ()
    go n          = go (n-1)

main = loop 1000000