haskell - STUArraysie-i == Intの場合にのみスペースリーク？

Question

私は次の切り取られた動作に混乱しています：

import Data.Int
import Data.Array.ST
import Control.Monad.ST

{-# INLINE fib #-}
fib _ 0 = return 0
fib _ 1 = return 1
fib c n = do
  f1 <- memo c (fib c) (n-1)
  f2 <- memo c (fib c) (n-2)
  return (f1+f2)

newtype C a = C a

{-# INLINE memo #-}
memo (C a) f k = do
  e <- readArray a k
  if e == (-1)
     then do
       v <- f k
       writeArray a k v
       return v
     else return e

evalFib :: Int -> Int
evalFib n = runST $ do
  a <- newArray (0,n) (-1) :: ST s (STUArray s Int Int)
  fib (C a) n

main = print $ evalFib 120000

それを使用してコンパイルすると-O2、スタックオーバーフローが発生します（20Mのメモリが使用されていることを示しています）。紛らわしいのは、次のいずれかの変更が行われた場合、実際には期待どおりに機能することです（スタックオーバーフローがなく、9Mのメモリが使用されています）。

Int64Int:(与えるevalFib :: Int64 -> Intと）の代わりに使用されSTUArray s Int64 Intます。実際、Int*（Int32、、など）は、または;Int16と同様にトリックを実行します。WordWord*
newtype C a画像から削除されます。
data C a = C !aの代わりに使用されますnewtype

私はこの振る舞いに頭を悩ませようとしています：それはGHC /アレイモジュールのバグですか（とで同じ振る舞いを示します7.4.2）7.6.2、それともそのように動作するはずですか？

PS面白いことに、コアの違いを確認するためにコンパイルしようとすると、ghc array.hs -O2 -fext-core両方のGHCバージョンが「ghc：panic！（「不可能」が発生した）」で失敗します。ここでも運がない。

score 11 · Accepted Answer

あなたが言うように、あなたの最初のプログラムはスタックオーバーフローです：

$ ghc -O2 A.hs --make -rtsopts
$ ./A +RTS -s
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.
      21,213,928 bytes allocated in the heap
       3,121,864 bytes copied during GC
       5,400,592 bytes maximum residency (4 sample(s))
          20,464 bytes maximum slop
              20 MB total memory in use (0 MB lost due to fragmentation)

Int64 に変更すると、正常に動作します。

$ time ./A
-2092835058118682368
./A  0.03s user 0.01s system 92% cpu 0.050 total

じゃあ漏れはどこ？

コードを視覚的に検査するだけで、明らかな問題があります。

fib はその配列引数で遅延しています

これは、見た動作からも推測できます。

newtype C a is removed from the picture;

data C a = C !a is used instead of newtype

厳密性アナライザーに配列を公開するすべてのサーバー。

配列で fib を厳密にする場合:

{-# LANGUAGE BangPatterns #-}

{-# INLINE fib #-}
fib !_ 0 = return 0
fib !_ 1 = return 1
fib !c n = do
  f1 <- memo c (fib c) (n-1)
  f2 <- memo c (fib c) (n-2)
  return (f1+f2)

その後、それは機能します：

$ time ./A
-2092835058118682368
./A  0.03s user 0.01s system 89% cpu 0.052 total

では、なぜあるタイプでは漏れるのに、別のタイプでは漏れないのでしょうか? Int64 で運が良かっただけだと思います。しかし、私はこれを「バグ」と考えています。おそらく、さまざまな num 型の書き換えルールにあります。

simplifier の出力を見ると、Int64 の場合と Int の場合では、まったく異なる書き換えルールの実行が得られます。基になる関数は Int によってインデックス付けされることが多いため、共通の Int 型を使用してさまざまな最適化を実行することになります。この場合、厳密性アナライザーを混乱させるのに十分です。

いつものように、一般的なルールが適用されます: コンパイラにより多くのヒントを与えると、より良いコードが得られます。

score 5 · Accepted Answer

7.6.1 のコアを見ると、作業を行う関数である-O2andは、 orをインデックスタイプとして使用するかどうかにかかわらず、構造的に (ほぼ) 同じです。コアは長くて複雑なので、出力は次のようになります。-dsuppress-uniquesMain.main_$spoly_$waintInt64diff

$ diff Int_core.dump-simpl Int64_core.dump-simpl 
11,12c11,12
<           (Data.Array.Base.STUArray s GHC.Types.Int GHC.Types.Int)
<           (Main.C (Data.Array.Base.STUArray s GHC.Types.Int GHC.Types.Int))
---
>           (Data.Array.Base.STUArray s GHC.Int.Int64 GHC.Types.Int)
>           (Main.C (Data.Array.Base.STUArray s GHC.Int.Int64 GHC.Types.Int))
26,27c26,27
<             (Data.Array.Base.STUArray s GHC.Types.Int GHC.Types.Int)
<             (Main.C (Data.Array.Base.STUArray s GHC.Types.Int GHC.Types.Int)))
---
>             (Data.Array.Base.STUArray s GHC.Int.Int64 GHC.Types.Int)
>             (Main.C (Data.Array.Base.STUArray s GHC.Int.Int64 GHC.Types.Int)))

さまざまなインデックスの種類、これらはもちろん異なります。

33,40d32
<           l :: GHC.Types.Int
<           [LclId]
<           l = GHC.Types.I# sc } in
<         let {
<           u :: GHC.Types.Int
<           [LclId]
<           u = GHC.Types.I# sc1 } in
<         let {

インデックス typeIntの場合、GHC は、有効なインデックスの下限と上限を必要とするため、範囲外のインデックスに対していくらか有益なエラーを生成します。( のデフォルトの実装はindexでオーバーライドされませんinstance Ix Int64。)

45,46c37
<           GHC.Types.False ->
<             case poly_$w$j5 (GHC.Types.I# a) l u of wild2 { };
---
>           GHC.Types.False -> case GHC.Arr.hopelessIndexError of wild1 { };

異なるエラー、indexError対hopelessIndexError。次の相違点もインデックスエラーのみに関係します。

49,50c40
<               GHC.Types.False ->
<                 case poly_$w$j5 (GHC.Types.I# a) l u of wild2 { };
---
>               GHC.Types.False -> case GHC.Arr.hopelessIndexError of wild2 { };
58c48
<                     case poly_$w$j4 y (GHC.Types.I# sc2) of wild3 { };
---
>                     case poly_$w$j3 y (GHC.Types.I# sc2) of wild4 { };
62c52
<                         case poly_$w$j4 y (GHC.Types.I# sc2) of wild5 { };
---
>                         case poly_$w$j3 y (GHC.Types.I# sc2) of wild5 { };
77,78c67
<                                 GHC.Types.False ->
<                                   case poly_$w$j3 (GHC.Types.I# a1) l u of wild6 { };
---
>                                 GHC.Types.False -> case GHC.Arr.hopelessIndexError of wild6 { };
81,82c70
<                                     GHC.Types.False ->
<                                       case poly_$w$j3 (GHC.Types.I# a1) l u of wild7 { };
---
>                                     GHC.Types.False -> case GHC.Arr.hopelessIndexError of wild7 { };

ここでもう一度、別のインデックスタイプ:

110c98
<                                                                       GHC.Types.Int
---
>                                                                       GHC.Int.Int64
152c140
<                                                 s GHC.Types.Int GHC.Types.Int>)>)
---
>                                                 s GHC.Int.Int64 GHC.Types.Int>)>)

そして最後に、0さまざま1なトップレベルの名前を取得しました。

177,178c165,166
<       0 -> (# sc5, lvl5 #);
<       1 -> (# sc5, lvl6 #)
---
>       0 -> (# sc5, lvl #);
>       1 -> (# sc5, lvl1 #)

したがって、実際の作業を行うコード全体は同じです。それでも、1つはスタックオーバーフローを引き起こします（ただ、-K9M十分ですが、[-K8731Kここでは十分です-K8730K]）が、もう1つはそうではありません。

この違いは、実際にはインデックスエラーによって引き起こされます。インデックス付きのコードは、コードが割り当てない再帰呼び出しごとにInt2 つの boxedを割り当てます。IntInt64

Main.main_$spoly_$wa [Occ=LoopBreaker]
  :: forall s.
     GHC.Prim.Int#
     -> GHC.Prim.Int#
     -> GHC.Prim.Int#
     -> GHC.Prim.MutableByteArray# s
     -> (GHC.Prim.~#)
          *
          (Data.Array.Base.STUArray s GHC.Types.Int GHC.Types.Int)
          (Main.C (Data.Array.Base.STUArray s GHC.Types.Int GHC.Types.Int))
     -> GHC.Prim.Int#
     -> GHC.Prim.State# s
     -> (# GHC.Prim.State# s, GHC.Types.Int #)

は、配列への2 つの参照を保持します。

これにより、より多くのスタックが使用され、これらのボックス化Intされた s をガベージコレクションする必要があるため、GC の数値がはるかに大きくなります。また、インデックスエラーのサンクは、hopelessIndexErrorサンクよりも少し大きくなります。

さて、コンパイラを助けるなら

newtype ラッパーの削除
配列内で関数を正格にする (バングパターンまたはでdata C a = C !a)

または他の方法で、ワーカー内の配列への参照が1 つしかないため、指定された引数のスタックオーバーフローなしで管理するより優れたコードを生成します。したがってInt、境界に対するボックス化された s の割り当ては必要ありません。

このアルゴリズムは、コンパイラの助けを借りても、わずかに大きな引数に対してスタックオーバーフローを引き起こすことに注意してください。

haskell - STUArraysie-i == Intの場合にのみスペースリーク？

2 に答える 2

Related

Reference