1 
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

./ファイル 単一 +RTS -s

収量

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'、最初の計算後に破棄fib' 80000されず、2 番目の を直接与えるために使用できます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 80000fib'doubleSlow

ルックアップ テーブルを 2 回作成する必要があるため、800 MB は理にかなっています。しかし、なぜ 2.78 秒に比べて 14.22 秒かかるのでしょうか? 私は約2倍、約を期待していました。5.8秒。

4

1 に答える 1

3

fib'最適化を使用してコンパイルすると、3 つの方法すべてでほぼ同じ数値が得られます。最適化を行わなくても、他の 2 つの場合と同様fib''に、 の場合もトップレベルに引き上げられますdoubleSlow。したがって、違いはルックアップであり、2 の加算です。大きな数、およびdoubleX対のその追加の結果single。

最適化なしでコンパイルすると、doubleSlow約 4.5 倍の時間がかかり、他の 2 つよりも約 2 倍多く割り当てられます。違いの大部分は、より長い 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) は約 2 倍の長さです。これは、ルックアップ データ構造が 2 回構築されるという事実に適合します (あなたの推論は多かれ少なかれ正しいです。ルックアップ テーブルはローカルでgあり、その後、g 800002 回呼び出されます)。

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

ほぼ正確に 2 倍です。

于 2013-06-20T21:10:16.960 に答える