7

GHC での低レベルの手動ループの最適化に苦労しています。私のプログラムには、数値計算を実行するいくつかのループが含まれています。実際のデータは他のデータ構造にラップされ、プログラムは「ループ制御フロー関数」と「計算関数」に分割され、一部のデータ構造フィールドが内部ループ内で読み取られるようになります。GHC がこれらの読み取りを内側のループの外に移動するようにします。何が起こっているかを示すために、コードを簡略化したバージョンを次に示します。

data D = D !Double !C
data C = C Double

-- This function is called in every loop iteration.
-- Parameter 'c' is loop-invariant.
exampleLoopBody i a c =
  case c of C b -> a + b * fromIntegral i

-- The body of this function is a counted loop that should be optimized
foo x =
  case x
  of D acc0 c ->
    let loop i acc =
          if i > 100
          then acc
          else loop (i+1) (exampleLoopBody i acc c)
    in loop 0 acc0

すべてのループ反復は を評価しますが、はループ不変であるcase c of C bため、冗長な計算です。c冗長な case 式をループの外に置くことで、GHC がそれを取り除くことができます。

foo x =
  case x
  of D acc0 c ->
    case c             -- This case statement inserted for optimization purposes
    of C b -> b `seq`  -- It will read 'b' outside of the loop
      let loop i acc =
           if i > 100
           then acc
           else loop (i+1) (exampleLoopBody i acc c)
      in loop 0 acc0

コンパイラはインライン化しexampleLoopBodyます。その後、内側の case ステートメントは冗長になり、削除されます。

foo x =
  case x
  of D acc0 c ->
    case c
    of C b -> b `seq`
      let loop i acc =
            if i > 100
            then acc
            else loop (i+1) (acc + b * fromIntegral i) -- The inlined case expression disappears
      in loop 0 acc0

の目的はseq、case 式がデッド コードにならないようにすることです。かどうかをseqチェックします。GHC は、が計算されたので、ループ本体でその値を再利用すると便利であることに気付きました。b_|_b

ここで問題があります。関連するすべてのデータ フィールドを厳格にしたいのです。このように、データ定義に厳密性アノテーションを挿入すると、

data C = C !Double

GHC に関する限り、seqとは何の効果もありません。case c of C bGHC がそれらを削除すると、次のようになります。

foo x =
  case x
  of D acc0 c ->
    let loop i acc =
          if i > 100
          then acc
          else loop (i+1) (case c of C b -> acc + b * fromIntegral i) -- Evaluate the case in every iteration
     in loop 0 acc0

このコードはcase c of C b反復ごとに評価されますが、これは私が避けようとしていたことです。

に頼ることができない場合、ループ本体の外で強制的に計算するseq方法が他にわかりません。bこの場合に使用できるトリックはありますか？

4

2 に答える 2

2

引数を並べ替えて、ループバリアント部分をラムダに移動してみてください。

-- note the order of the arguments changed
exampleLoopBody (C b) =
  \i a -> a + b * fromIntegral i

foo (D acc0 c) =
    let
       loopBody = exampleLoopBody c 
       loop i acc =
          if i > 100
         then acc
         else loop (i+1) (loopBody i acc)
   in loop 0 acc0

また、このコードは現時点で未評価の大きな式を作成するため、ループを通過するたびにアキュムレータパラメータを強制することができます。

于 2012-04-26T21:39:01.787 に答える
0

これは、基本的にすべての理由newtypeが言語に含まれているように見えます。単純なバージョンのコードに変更data C = C !Doubleして記述するだけです。newtype C = C Doubletype の値のすべてcaseの式Cが消去されます。補足として、例にあるコードパターンは次のとおりです。

case foo of
    D acc0 c -> case c of
        C b -> ...

もっと簡潔に書くことができます：

case foo of
    D acc0 (C b) -> ...
于 2012-04-26T21:48:34.810 に答える