为什么这个Haskell程序会分配如此多的内存？

Question

请注意以下Haskell程序:

-- (^) allocs memory so we define it using the native (**)
pow :: Int -> Int -> Int
pow x y = floor $ fromIntegral x ** fromIntegral y

-- tail recursive, div and mod are native, I believe, so, no alloc
isPalindrome :: Int -> Bool
isPalindrome x = go (pow 10 (floor $ logBase 10 $ fromIntegral x)) x
    where go m x = x <= 0 || div x m == mod x 10 && go (div m 100) (div (x - m * mod x 10) 10)

-- go is tail recursive too... no obvious allocation here
wanderer :: Int -> Int
wanderer n = go 0 (pow 10 n - 1) (pow 10 n - 1) where
    go p x y | p > 0 && div p x >= pow 10 n  = p                
    go p x y | p > 0 && y < div p x || y < x = go p (x-1) (pow 10 n - 1)
    go p x y | isPalindrome (x*y)            = go (x*y) x (y-1) 
    go p x y                                 = go p x (y-1)     

main = print . wanderer $ 8

分析它,我们得到:

Fri May  8 03:36 2015 Time and Allocation Profiling Report  (Final)

       aff +RTS -p -RTS

    total time  =        7.34 secs   (7344 ticks @ 1000 us, 1 processor)
    total alloc = 6,487,919,472 bytes  (excludes profiling overheads)

COST CENTRE     MODULE    %time %alloc

isPalindrome    Main       41.9   18.5
isPalindrome.go Main       22.6    1.4
wanderer.go     Main       20.0   67.8
pow             Main       15.5   12.3


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

MAIN                  MAIN                     47           0    0.0    0.0   100.0  100.0
 main                 Main                     95           0    0.0    0.0     0.0    0.0
 CAF:main1            Main                     92           0    0.0    0.0     0.0    0.0
  main                Main                     94           1    0.0    0.0     0.0    0.0
 CAF:main2            Main                     91           0    0.0    0.0   100.0  100.0
  main                Main                     96           0    0.0    0.0   100.0  100.0
   wanderer           Main                     98           1    0.0    0.0   100.0  100.0
    pow               Main                    101           1    0.0    0.0     0.0    0.0
    wanderer.go       Main                     99    49995002   20.0   67.8   100.0  100.0
     isPalindrome     Main                    102    49985002   41.9   18.5    80.0   32.2
      pow             Main                    104    49985002   15.5   12.3    15.5   12.3
      isPalindrome.go Main                    103    52207117   22.6    1.4    22.6    1.4
     pow              Main                    100           1    0.0    0.0     0.0    0.0
   pow                Main                     97           2    0.0    0.0     0.0    0.0
 CAF                  GHC.Conc.Signal          85           0    0.0    0.0     0.0    0.0
 CAF                  GHC.IO.Encoding          78           0    0.0    0.0     0.0    0.0
 CAF                  GHC.IO.Encoding.Iconv    76           0    0.0    0.0     0.0    0.0
 CAF                  GHC.IO.Handle.FD         69           0    0.0    0.0     0.0    0.0
 CAF                  GHC.Event.Thread         55           0    0.0    0.0     0.0    0.0

据我所知,似乎我的所有函数都是尾递归的,而那些前奏函数都是asm操作.然而,这个简单的程序分配了7GB的内存.所有分配来自哪里？

Answer 1

分配来自go于isPalindrome:

go m x = x <= 0 || div x m == mod x 10 && go (div m 100) (div (x - m * mod x 10) 10)

我们||右边有一个.||通过惰性评估实现短路语义.GHC认为m如果x <= 0求值,则该参数未被使用True,因此它不会取消装箱m,允许它保持未计算.当然,在这种情况下,我们最好m不要拆箱,所以让我们这样做.

{-# LANGUAGE BangPatterns #-}
go !m x = ...

现在用ghc -O2和+RTS -s:

      52,016 bytes allocated in the heap
       3,408 bytes copied during GC
      44,312 bytes maximum residency (1 sample(s))
      17,128 bytes maximum slop
           1 MB total memory in use (0 MB lost due to fragmentation)