3

このページで読んだスペースリークの例について疑問に思っています（残念ながら、そこでは説明されていませんでした）： https://en.wikibooks.org/wiki/Haskell/Graph_reduction

トリッキーなスペースリークの例:

(\xs -> 先頭の xs + 最後の xs) [1..n]

(\xs -> 最後の xs + 先頭の xs) [1..n]

最初のバージョンは O(1) 空間で実行されます。O(n) の 2 番目。

私が正しく理解しているかどうかはわかりません（助けていただければ幸いです）。私の知る限り、遅延評価は左端の最も外側の評価を意味します。したがって、これらの例では、これらの redex を次のように減らします。

(\xs -> 先頭の xs + 最後の xs) [1..200]

=> ([1..200] -> 先頭の x + 最後の x)

=> 先頭 [1..200] + 末尾 [1..200]

=> 1 + 最後 [1..200]

=> 1 + 最後 [2..200]

=> ... ...

=> 1 + 最後 [199..200]

=> 1 + 最後 [200]

=> 1 + 200

=> 201

と

(\xs -> 最後の xs + 先頭の xs) [1..200]

([1..200] -> 最後の xs + 先頭の xs)

ラスト [1..200] + ヘッド [1..200]

ラスト [2..200] + ヘッド [1..200]

... ... ...

ラスト [199..200] + ヘッド [1..200]

ラスト [200] + ヘッド [1..200]

200 + ヘッド [1..200]

200 + 1

201

間違った方法で縮小したのかもしれませんが (間違っている場合は訂正してください)、ここではスペースリークの可能性は見られません。そこで、最初に ghci でランタイム (スペースではない) をテストしました。

1>> (\xs -> head xs + last xs) [1..50000000]
50000001
(10.05 secs, 4,003,086,632 bytes)
2>> (\xs -> last xs + head xs) [1..50000000]
50000001
(2.26 secs, 3,927,748,176 bytes)

ウィキブックによると、2 番目のバージョンではスペース リークが発生するはずですが、ランタイムははるかに高速です (可能かもしれませんが、ここでは何もおかしくありません)。

次のソースコードがあります。

module Main where

main = do
--  let a = (\xs -> head xs + last xs) [1..20000000]    -- space leak
let b = (\xs -> last xs + head xs) [1..20000000]    -- no space leak
--  putStrLn ("result for a - (\\xs -> head xs + last xs): " ++ show a)
putStrLn ("result for b - (\\xs -> last xs + head xs): " ++ show b)

...そして、最適化なしでコンパイルしてから、プログラムを呼び出しました：

$ ghc -O0 --make -rtsopts -fforce-recomp Main.hs
[1 of 1] Compiling Main             ( Main.hs, Main.o )
Linking Main ...

$ ./Main +RTS -sstderr
result for b - (\xs -> last xs + head xs): 20000001
   1,600,057,352 bytes allocated in the heap
         211,000 bytes copied during GC
          44,312 bytes maximum residency (2 sample(s))
          21,224 bytes maximum slop
               1 MB total memory in use (0 MB lost due to fragmentation)

                                     Tot time (elapsed)  Avg pause  Max pause
  Gen  0      3062 colls,     0 par    0.012s   0.012s     0.0000s    0.0001s
  Gen  1         2 colls,     0 par    0.000s   0.000s     0.0002s    0.0002s

  INIT    time    0.000s  (  0.000s elapsed)
  MUT     time    0.518s  (  0.519s elapsed)
  GC      time    0.012s  (  0.012s elapsed)
  EXIT    time    0.000s  (  0.000s elapsed)
  Total   time    0.534s  (  0.532s elapsed)

  %GC     time       2.3%  (2.3% elapsed)

  Alloc rate    3,088,101,743 bytes per MUT second

  Productivity  97.6% of total user, 98.0% of total elapsed

これは良い結果です。2.3% のガベージ コレクションがあり、使用メモリは約 1 MB です。次に、最適化なしで他のケースをコンパイルしたところ、次の結果が得られました。

module Main where

main = do
  let a = (\xs -> head xs + last xs) [1..20000000]    -- space leak
--  let b = (\xs -> last xs + head xs) [1..20000000]    -- no space leak
  putStrLn ("result for a - (\\xs -> head xs + last xs): " ++ show a)
--  putStrLn ("result for b - (\\xs -> last xs + head xs): " ++ show b)

$ ghc -O0 --make -rtsopts -fforce-recomp Main.hs
[1 of 1] Compiling Main             ( Main.hs, Main.o )
Linking Main ...

$ ./Main +RTS -sstderr
result for a - (\xs -> head xs + last xs): 20000001
   1,600,057,352 bytes allocated in the heap
   2,088,615,552 bytes copied during GC
     540,017,504 bytes maximum residency (13 sample(s))
     135,620,768 bytes maximum slop
            1225 MB total memory in use (0 MB lost due to fragmentation)

                                     Tot time (elapsed)  Avg pause  Max pause
  Gen  0      3051 colls,     0 par    0.911s   0.915s     0.0003s    0.0016s
  Gen  1        13 colls,     0 par    2.357s   2.375s     0.1827s    0.9545s

  INIT    time    0.000s  (  0.000s elapsed)
  MUT     time    0.434s  (  0.430s elapsed)
  GC      time    3.268s  (  3.290s elapsed)
  EXIT    time    0.094s  (  0.099s elapsed)
  Total   time    3.799s  (  3.820s elapsed)

  %GC     time      86.0%  (86.1% elapsed)

  Alloc rate    3,687,222,801 bytes per MUT second

  Productivity  14.0% of total user, 13.9% of total elapsed

これはさらに悪いことです。大量のガベージ コレクションが行われ、メモリ使用量がはるかに高くなります。

ここで実際に何が起こっているのですか？スペースリークが発生する理由がわかりません。

PS 両方のケースを完全最適化 (O2) でコンパイルすると、両方のプログラムの効率はほぼ同じになります。

4

1 に答える 1

4

xs同じです。2回書き出すと[1..200]、混乱します。式の評価の過程で存在するすべての中間エンティティに明示的に名前を付ける方がよい:

(\xs -> head xs + last xs) [1,2,3]
head xs + last xs        { xs = [1,2,3] }
(+) (head xs) (last xs)
(+) 1         (last xs)  { xs = 1:xs1 ; xs1 = [2,3] }
              (last xs1) { xs1 = 2:xs2 ; xs2 = [3] }
              (last xs2)
              3
4

ここで、xs(and xs1) のバインディングは、先に進むにつれて安全に忘れられることがわかります。これは、xsどこにも参照がないためです。

[1..200]したがって、2 番目が最初のものと同じであることを除いて、正しく削減したため、last最初に (2 番目のバリアントで) を見つけている間、それを保持する必要があったため、リークが発生しました。

もちろん、コンパイラはこれを最適化し、参照透過性の原則のために equals を equals に置き換え、列挙を[1..200] 2 回実行することが許可されているため、2 番目のバリアントでもO(1)空間で実行されます。

つまり、最終的にはコンパイラの問題です。スペースリークが発生する可能性があります (すべきではありません)。

于 2016-06-09T13:51:58.683 に答える