Data.MemoCombinators;意想不到的運行時間

import qualified Data.MemoCombinators as Memo 
import System.Environment 

single = fib' 80000 
    where fib' = Memo.integral fib'' 
     fib'' 0 = 0 
     fib'' 1 = 1 
     fib'' x = fib' (x-1) + fib' (x-2) 

doubleFast = fib' 80000 + fib' 80000 
    where fib' = Memo.integral fib'' 
     fib'' 0 = 0 
     fib'' 1 = 1 
     fib'' x = fib' (x-1) + fib' (x-2) 

doubleSlow = g 80000 + g 80000 
    where g x = fib' x 
      where fib' = Memo.integral fib'' 
       fib'' 0 = 0 
       fib'' 1 = 1 
       fib'' x = fib' (x-1) + fib' (x-2)    

main = do 
    args <- getArgs 
    case args of 
    ["single"]  -> print single 
    ["doubleFast"] -> print doubleFast 
    ["doubleSlow"] -> print doubleSlow

./file單個+ RTS -sData.MemoCombinators;意想不到的運行時間

產量

1,085,072,320 bytes allocated in the heap 
387,297,448 bytes copied during GC 
265,811,512 bytes maximum residency (10 sample(s)) 
99,107,440 bytes maximum slop 
433 MB total memory in use (0 MB lost due to fragmentation) 

Total time 2.78s ( 2.78s elapsed)

./file doubleFast + RTS -s

產生了相同的結果。這對我有意義：由於fib'在doubleFast的範圍內，所以在計算第一個fib' 80000後不會丟棄fib'，並且可以用來直接給出第二個fib' 80000。

什麼我不明白的是：

./file doubleSlow + RTS -s

2,166,532,752 bytes allocated in the heap 
551,826,896 bytes copied during GC 
263,793,848 bytes maximum residency (11 sample(s)) 
204,460,968 bytes maximum slop 
818 MB total memory in use (0 MB lost due to fragmentation) 

Total time 14.22s (14.24s elapsed)

請糾正我，如果我錯了：fib'被用來計算第一個g 80000 = fib' 80000。函數g被留下，並且因爲g不被記憶，所以它不能被直接用於計算第二個g 80000。此外，在離開g 80000的第一個呼叫之後，由於fib'的查找表不在doubleSlow的範圍內而被丟棄。

800 MB對我有意義，因爲查找表必須被構建兩次。然而，爲什麼它需要14.22s而不是2.78s？我預計大約兩倍，約。 5.8S。

來源

2013-06-20 efie

在GC中花費了多少時間？你用-O2編譯過嗎？ – augustss

當使用的優化編譯，我得到了所有的三種方式幾乎相同的人物 - fib'和fib''然後被提升到最高級別也爲doubleSlow，因爲他們是兩個人，即使沒有優化，使不同的是剛一個查找，兩個大數的加法，以及doubleX與single的加法結果。

在沒有優化的情況下編譯時，doubleSlow需要大約4.5倍的時間，並且分配大約是其他兩個的兩倍。差異的大部分是由於較長GC，

MUT  time 1.64s ( 1.64s elapsed) 
GC  time 7.09s ( 7.10s elapsed) 

MUT  time 0.75s ( 0.75s elapsed) 
GC  time 1.07s ( 1.07s elapsed)

和計算時間（MUT）約爲兩倍長，這符合事實查找數據結構是建立兩次（你的推理是更或更少正確，則查找表是g的本地，然後調用g 80000兩次）。

我對GHC的垃圾回收器不夠熟悉，無法解釋爲什麼收集第一個查找表需要很長的時間和默認設置，但所花費的時間非常依賴於分配區域的大小，我得到了最好的結果它設置爲3MB，

$ ./memfib +RTS -s -A3M -RTS doubleSlow > /dev/null 
    2,166,534,656 bytes allocated in the heap 
    599,670,152 bytes copied during GC 
    161,411,104 bytes maximum residency (13 sample(s)) 
     99,163,664 bytes maximum slop 
      414 MB total memory in use (0 MB lost due to fragmentation) 

            Tot time (elapsed) Avg pause Max pause 
    Gen 0  562 colls,  0 par 0.49s 0.49s  0.0009s 0.0041s 
    Gen 1  13 colls,  0 par 0.62s 0.62s  0.0477s 0.0841s 

    INIT time 0.00s ( 0.00s elapsed) 
    MUT  time 1.61s ( 1.62s elapsed) 
    GC  time 1.11s ( 1.11s elapsed) 
    EXIT time 0.03s ( 0.03s elapsed) 
    Total time 2.76s ( 2.76s elapsed) 

    %GC  time  40.2% (40.2% elapsed) 

    Alloc rate 1,343,022,682 bytes per MUT second 

    Productivity 59.8% of total user, 59.7% of total elapsed

相比

$ ./memfib +RTS -s -A3M -RTS doubleFast > /dev/null 
    1,085,085,832 bytes allocated in the heap 
    311,633,528 bytes copied during GC 
    165,830,256 bytes maximum residency (9 sample(s)) 
     99,121,736 bytes maximum slop 
      389 MB total memory in use (0 MB lost due to fragmentation) 

            Tot time (elapsed) Avg pause Max pause 
    Gen 0  280 colls,  0 par 0.22s 0.22s  0.0008s 0.0042s 
    Gen 1   9 colls,  0 par 0.34s 0.34s  0.0376s 0.0792s 

    INIT time 0.00s ( 0.00s elapsed) 
    MUT  time 0.79s ( 0.79s elapsed) 
    GC  time 0.55s ( 0.56s elapsed) 
    EXIT time 0.03s ( 0.03s elapsed) 
    Total time 1.38s ( 1.38s elapsed) 

    %GC  time  40.3% (40.3% elapsed) 

    Alloc rate 1,378,141,985 bytes per MUT second 

    Productivity 59.7% of total user, 59.7% of total elapsed

這幾乎是一兩個因素。

來源

2013-06-20 21:10:16

Data.MemoCombinators;意想不到的運行時間

回答

相關問題