为什么这个简单的haskell算法这么慢？

Question

扰流警报:这与Project Euler的问题14有关.

以下代码需要大约15秒才能运行.我有一个在1s内运行的非递归Java解决方案.我想我应该能够更接近这个代码.

import Data.List

collatz a 1  = a
collatz a x
  | even x    = collatz (a + 1) (x `div` 2)
  | otherwise = collatz (a + 1) (3 * x + 1)

main = do
  print ((foldl1' max) . map (collatz 1) $ [1..1000000])

我已经分析过,+RHS -p并注意到分配的内存很大,并随着输入的增长而增长.对于n = 100,0001gb分配(!),分配n = 1,000,00013gb(!!).

然后再次-sstderr表明,尽管分配了大量字节,但总内存使用量为1mb,生产率为95%+,因此13gb可能是红鲱鱼.

我可以想到几个可能性:

1. 有些事情并不像它需要的那么严格.我已经发现了 foldl1',但也许我需要做更多的事情？是否有可能标记collatz 为严格(甚至有意义吗？

2. collatz不是尾部调用优化.我认为它应该是但不知道确认的方法.

3. 编译器没有做我认为应该进行的一些优化 - 例如collatz,任何一次只需要在内存中的两个结果(最大值和当前值)

有什么建议？

这几乎是一个重复的为什么这个Haskell表达式如此之慢？虽然我会注意到快速Java解决方案不必执行任何memoization.有什么办法可以加快速度而不必诉诸它吗？

作为参考,这是我的分析输出:

  Wed Dec 28 09:33 2011 Time and Allocation Profiling Report  (Final)

     scratch +RTS -p -hc -RTS

  total time  =        5.12 secs   (256 ticks @ 20 ms)
  total alloc = 13,229,705,716 bytes  (excludes profiling overheads)

COST CENTRE                    MODULE               %time %alloc

collatz                        Main                  99.6   99.4


                                                                                               individual    inherited
COST CENTRE              MODULE                                               no.    entries  %time %alloc   %time %alloc

MAIN                     MAIN                                                   1           0   0.0    0.0   100.0  100.0
 CAF                     Main                                                 208          10   0.0    0.0   100.0  100.0
  collatz                Main                                                 215           1   0.0    0.0     0.0    0.0
  main                   Main                                                 214           1   0.4    0.6   100.0  100.0
   collatz               Main                                                 216           0  99.6   99.4    99.6   99.4
 CAF                     GHC.IO.Handle.FD                                     145           2   0.0    0.0     0.0    0.0
 CAF                     System.Posix.Internals                               144           1   0.0    0.0     0.0    0.0
 CAF                     GHC.Conc                                             128           1   0.0    0.0     0.0    0.0
 CAF                     GHC.IO.Handle.Internals                              119           1   0.0    0.0     0.0    0.0
 CAF                     GHC.IO.Encoding.Iconv                                113           5   0.0    0.0     0.0    0.0

并且-sstderr:

./scratch +RTS -sstderr 
525
  21,085,474,908 bytes allocated in the heap
      87,799,504 bytes copied during GC
           9,420 bytes maximum residency (1 sample(s))          
          12,824 bytes maximum slop               
               1 MB total memory in use (0 MB lost due to fragmentation)  

  Generation 0: 40219 collections,     0 parallel,  0.40s,  0.51s elapsed
  Generation 1:     1 collections,     0 parallel,  0.00s,  0.00s elapsed

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time   35.38s  ( 36.37s elapsed)
  GC    time    0.40s  (  0.51s elapsed)
  RP    time    0.00s  (  0.00s elapsed)  PROF  time    0.00s  (  0.00s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time   35.79s  ( 36.88s elapsed)  %GC time       1.1%  (1.4% elapsed)  Alloc rate    595,897,095 bytes per MUT second

  Productivity  98.9% of total user, 95.9% of total elapsed

和Java解决方案(不是我的,取自Project Euler论坛并删除了memoization):

public class Collatz {
  public int getChainLength( int n )
  {
    long num = n;
    int count = 1;
    while( num > 1 )
    {
      num = ( num%2 == 0 ) ? num >> 1 : 3*num+1;
      count++;
    }
    return count;
  }

  public static void main(String[] args) {
    Collatz obj = new Collatz();
    long tic = System.currentTimeMillis();
    int max = 0, len = 0, index = 0;
    for( int i = 3; i < 1000000; i++ )
    {
      len = obj.getChainLength(i);
      if( len > max )
      {
        max = len;
        index = i;
      }
    }
    long toc = System.currentTimeMillis();
    System.out.println(toc-tic);
    System.out.println( "Index: " + index + ", length = " + max );
  }
}

Answer 1

起初,我以为你应该尝试把一个感叹号前一个在collatz:

collatz !a 1  = a
collatz !a x
  | even x    = collatz (a + 1) (x `div` 2)
  | otherwise = collatz (a + 1) (3 * x + 1)

(您需要放在{-# LANGUAGE BangPatterns #-}源文件的顶部才能使其正常工作.)

我的推理如下:问题是你在第一个争论中建立了一个巨大的thunk:它开始了1,然后变成1 + 1,然后变成(1 + 1) + 1,......所有都没有被强迫.这种爆炸模式collatz会强制每次调用时强制第一个参数,因此它从1开始,然后变为2,依此类推,而不会构建一个大的未评估的thunk:它只是保持整数.

请注意,爆炸模式只是使用的简写seq; 在这种情况下,我们可以重写collatz如下:

collatz a _ | seq a False = undefined
collatz a 1  = a
collatz a x
  | even x    = collatz (a + 1) (x `div` 2)
  | otherwise = collatz (a + 1) (3 * x + 1)

这里的诀窍是强制一个守卫,然后总是评估为False(所以身体是无关紧要的).然后评估继续下一情况下,一个已经已经被评估.然而,爆炸模式更清晰.

不幸的是,当编译时-O2,这不会比原来运行得快!我们还能尝试什么？好吧,我们可以做的一件事是假设这两个数字永远不会溢出机器大小的整数,并给出collatz这种类型的注释:

collatz :: Int -> Int -> Int

我们将把爆炸模式留在那里,因为即使它们不是性能问题的根源,我们仍然应该避免积累thunk.这使我的(慢)计算机上的时间减少到8.5秒.

下一步是尝试将其更接近Java解决方案.首先要意识到的是,在Haskell中,div相对于负整数,它的行为方式更为数学上正确,但比Haskell中的"正常"C除法要慢quot.替换div为quot将运行时间降低到5.2秒,并替换x `quot` 2为x `shiftR` 1(导入Data.Bits)以匹配Java解决方案,使其降至4.9秒.

这个差不多我现在可以得到它,但我认为这是一个非常好的结果; 因为你的计算机比我的快,所以它应该更接近Java解决方案.

这是最终的代码(我在路上做了一些清理工作):

{-# LANGUAGE BangPatterns #-}

import Data.Bits
import Data.List

collatz :: Int -> Int
collatz = collatz' 1
  where collatz' :: Int -> Int -> Int
        collatz' !a 1 = a
        collatz' !a x
          | even x    = collatz' (a + 1) (x `shiftR` 1)
          | otherwise = collatz' (a + 1) (3 * x + 1)

main :: IO ()
main = print . foldl1' max . map collatz $ [1..1000000]

看一下这个项目的GHC核心(有ghc-core),我认为这可能和它一样好; 在collatz循环使用未装箱的整数,程序的其他部分看起来OK.我能想到的唯一改进就是从map collatz [1..1000000]迭代中消除拳击.

顺便说一句,不要担心"总分配"数字; 它是在程序生命周期内分配的总内存,即使GC回收内存也不会减少.多TB的数字很常见.