Haskell:为什么Int的性能比Word64差,为什么我的程序远比C慢？

Question

我正在阅读一篇关于Haskell在使用Collat​​z猜想时有多缓慢的文章,它基本上表明如果你将三个加一个乘以一个奇数,或者将一个偶数除以一个,你最终会得到一个.例如,3 - > 10 - > 5 - > 16 - > 8 - > 4 - > 2 - > 1.

本文中给出的程序是计算给定范围内最长的Collat​​z序列.C版本是:

#include <stdio.h>

int main(int argc, char **argv) {
   int max_a0 = atoi(argv[1]); 
   int longest = 0, max_len = 0;
   int a0, len;
   unsigned long a;

   for (a0 = 1; a0 <= max_a0; a0++) {
      a = a0;
      len = 0;

      while (a != 1) {
         len++;
         a = ((a%2==0)? a : 3*a+1)/2;
      }

      if (len > max_len) {
         max_len = len;
         longest = a0;
      }
   }
   printf("(%d, %d)\n", max_len, longest);
   return 0;
}

使用Clang O2进行编译,它在我的计算机上运行0.2秒.

该文章中给出的Haskell版本明确地将整个序列生成为列表,然后计算中间列表的长度.它比C版慢10倍.但是,由于作者使用LLVM作为后端,我没有安装,我无法重现这一点.使用GHC 7.8和默认后端,它在我的Mac上运行10秒,比C版本慢50倍.

然后,我使用尾递归编写一个版本,而不是生成一个中间列表:

collatzNext :: Int -> Int
collatzNext a
  | even a    = a `div` 2
  | otherwise = (3 * a + 1) `div` 2

collatzLen :: Int -> Int
collatzLen n = collatzIter n 0
  where
    collatzIter 1 len = len
    collatzIter n len = collatzIter (collatzNext n) (len + 1)

main = do
  print $ maximum $ [collatzLen x | x <- [1..1000000]]

使用GHC 7.8和O2编译,它运行2秒,比C版本慢10倍.

有趣的是,当我Int在类型注释中更改为时Word,它只花了1秒,快了2倍!

我已经尝试过BangPatterns进行明确的严格评估,但是没有明显的性能提升可以被注意到 - 我猜GHC的严格分析足够智能来处理这样一个简单的场景.

我的问题是:

1. 为什么Word版本比那个版本快得多Int？
2. 为什么这个Haskell程序与C相比这么慢？

Answer 1

该计划的表现取决于几个因素.如果我们所有这些都正确,那么性能将与C程序的性能相同.经历这些因素:

1.使用和比较正确的单词大小

发布的C代码段并不完全正确; 它在所有架构上使用32位整数,而Haskell Int-s在64位机器上是64位.除此之外,我们应该确保在两个程序中使用相同的字大小.

此外,我们应该始终在Haskell代码中使用本机大小的整数类型.因此,如果我们使用的是64位系统,我们应该使用64位数字,并避开Int32-s和Word32-s,除非特别需要它们.这是因为对非本机整数的操作主要是作为外部调用而不是primops实现的,因此它们的速度要慢得多.

2.分部 collatzNext

div是慢quot的Int,因为div处理负数不同.如果我们使用div并切换到Word,程序会变得更快,因为div它与quotfor 相同Word.quot与Int作品一样精致.然而,这仍然没有C那么快.我们可以通过向右移位来除以2.出于某种原因,在这个例子中,甚至连LLVM都没有这种特殊的强度降低,所以我们最好手工完成,取而代之的quot n 2是shiftR n 1.

3.检查均匀度

检查这一点的最快方法是检查最低有效位.LLVM可以even对此进行优化,而本机代码则不能.因此,如果我们使用本机codegen,even n可以替换为n .&. 1 == 0,这可以提高性能.

但是,我发现GHC 7.10存在一些性能问题.在这里,我们没有得到一个内联even的Word,其击毁性能(调用带有堆分配的功能Word框代码中做到这一点的最热的部分).所以在这里我们应该使用rem n 2 == 0或n .&. 1 == 0代替even.尽管如此,evenfor for Int内存很好.

4.融合列表 collatzLen

这是一个至关重要的因素.链接的博客文章对此有点过时了.GHC 7.8不能在这里做融合,但7.10可以.这意味着使用GHC 7.10和LLVM,我们可以方便地获得类似C的性能,而无需显着修改原始代码.

collatzNext a = (if even a then a else 3*a+1) `quot` 2
collatzLen a0 = length $ takeWhile (/= 1) $ iterate collatzNext a0
maxColLen n   = maximum $ map collatzLen [1..n]

main = do
    [n] <- getArgs
    print $ maxColLen (read n :: Int) 

使用ghc-7.10.1 -O2 -fllvm和n = 10000000,上述程序在2.8秒内运行,而等效的C程序在2.4秒内运行.如果我在没有LLVM的情况下编译相同的代码,那么我将获得12.4秒的运行时间.这种放缓完全是因为缺乏优化even.如果我们使用a .&. 1 == 0,那么减速就会消失.

5.计算最大长度时融合列表

即使GHC 7.10也不能这样做,所以我们不得不求助于手动循环写入.

collatzNext a = (if a .&. 1 == 0 then a else 3*a+1) `shiftR` 1
collatzLen    = length . takeWhile (/= 1) . iterate collatzNext

maxCol :: Int -> Int
maxCol = go 1 1 where
  go ml i n | i > n = ml
  go ml i n = go (max ml (collatzLen i)) (i + 1) n

main = do
  [n] <- getArgs
  print $ maxCol (read n :: Int)

现在,for ghc-7.10.1 -O2 -fllvm和n = 10000000,上面的代码在2.1秒内运行,而C程序在2.4秒内运行.如果我们想在没有LLVM和GHC 7.10的情况下实现类似的性能,我们只需手动应用重要的缺失优化:

collatzLen :: Int -> Int
collatzLen = go 0 where
  go l 1 = l
  go l n | n .&. 1 == 0 = go (l + 1) (shiftR n 1)
         | otherwise    = go (l + 1) (shiftR (3 * n + 1) 1)

maxCol :: Int -> Int
maxCol = go 1 1 where
  go ml i n | i > n = ml
  go ml i n = go (max ml (collatzLen i)) (i + 1) n

main = do
  [n] <- getArgs
  print $ maxCol (read n :: Int)

现在,使用ghc-7.8.4 -O2和n = 10000000,我们的代码运行2.6秒.