14

mapAndSum以下のコードブロックの関数は、以下のすべての機能mapを組み合わせたものですsum(main関数に別の関数が適用されていることを気にしないsumでください。これは、出力をコンパクトにするためだけに役立ちます)。はmap遅延してsum計算されますが、は累積パラメータを使用して計算されます。アイデアはmap、メモリに完全なリストがなくても結果を消費でき、その後(のみ)sum「無料」で利用できるようにすることです。main関数は、を呼び出すときに反駁できないパターンに問題があったことを示していmapAndSumます。この問題について説明させてください。

Haskell標準によると、反駁できないパターンの例let (xs, s) = mapAndSum ... in print xs >> print sは次のように翻訳されます。

(\ v ->    print (case v of { (xs, s) -> xs })
        >> print (case v of { (xs, s) -> s }))
$ mapAndSum ...

したがって、両方のprint呼び出しはペア全体への参照を運び、リスト全体がメモリに保持されます。

私たち(私の同僚のToni Dietzeと私)は、明示的なcaseステートメントを使用してこれを解決しました(「bad」と「good2」を比較してください)。ところで、これを見つけるのにかなりの時間がかかりました..!

さて、私たちが理解していないのは2つあります。

  • mapAndSumそもそもなぜ機能するのですか?また、反駁できないパターンを使用しているため、リスト全体をメモリに保持する必要がありますが、明らかにそうではありません。そして、をに変換するletcase、関数は完全に怠惰な動作になります(スタックがオーバーフローするまで、しゃれは意図されていません)。

    GHCによって生成された「コア」コードを調べましたが、それを解釈できる限り、実際には上記と同じ翻訳が含まletれていました。したがって、ここでは手がかりはなく、代わりにさらに混乱します。

  • なぜ「悪い」のですか?最適化がオフの場合は機能しますが、オンの場合は機能しませんか?

実際のアプリケーションに関する1つの注意点は、大きなテキストファイルのストリーム処理(フォーマット変換)を実現すると同時に、別のファイルに書き込まれる値を蓄積することです。示されているように、私たちは成功しましたが、2つの質問が残っており、回答により、今後のタスクと問題に対するGHCの理解が向上する可能性があります。

ありがとうございました!

{-# LANGUAGE BangPatterns #-}

-- Tested with The Glorious Glasgow Haskell Compilation System, version 7.4.2.

module Main where


import Control.Arrow (first)
import Data.List (foldl')
import System.Environment (getArgs)


mapAndSum :: Num a => (a -> b) -> [a] -> ([b], a)
mapAndSum f = go 0
  where go !s (x : xs) = let (xs', s') = go (s + x) xs in (f x : xs', s')
                       -- ^ I have no idea why it works here. (TD)
        go !s []       = ([], s)


main :: IO ()
main = do
  let foo  = mapAndSum (^ (2 :: Integer)) [1 .. 1000000 :: Integer]
  let sum' = foldl' (+) 0
  args <- getArgs
  case args of
    ["bad" ]  -> let (xs, s) = foo in print (sum xs) >> print s
    ["bad?"]  -> print $ first sum' $ foo
              -- ^ Without ghc's optimizer, this version is as memory
              -- efficient as the “good” versions
              -- With optimization “bad?” is as bad as “bad”. Why? (TD)
    ["good1"] -> print $ first' sum' $ foo
                   where first' g (x, y) = (g x, y)
    ["good2"] -> case foo of
                    (xs, s) -> print (sum' xs) >> print s
    ["good3"] -> (\ (xs, s) -> print (sum' xs) >> print s) $ foo
    _ -> error "Sorry, I do not understand."
4

1 に答える 1

18

mapAndSome最初に、なぜうまく機能するのかを答えさせてください。表示されるのは (非常に可能性が高い)、Philip Wadler が「<a href="http://homepages.inf.ed.ac.uk/wadler」で説明した最適化の効果です。 /topics/garbage-collection.html" rel="noreferrer">ガベージ コレクターでいくつかのスペース リークを修正する". 簡単な要約: ガベージ コレクターがフォームのサンクを認識fst xx、タプル コンストラクターに対して既に評価されている場合、たとえば(y,z)に置き換えfst xられy、他の場所で参照されていない場合は解放される可能性がありzます。

あなたのコードではs'、の結果がgoタプルに評価され、GCing の 1 回のラウンドの後、タプルへの参照を保持せず、蓄積されたパラメーターに置き換えられます。

それでは、コアを調べて他のパターンを見てみましょう。fooバインディングは次のようにコンパイルされます。

foo_r2eT :: ([Type.Integer], Type.Integer)

foo_r2eT =
  case $wgo_r2eP mapAndSum1 lvl2_r2eS
  of _ { (# ww1_s2d7, ww2_s2d8 #) ->
  (ww1_s2d7, ww2_s2d8)
  }

"bad"ケースのコードは次のとおりです (lvl18_r2fdは「悪い」):

case eqString ds_dyA lvl18_r2fd of _ {
  False -> $wa_s2da new_s_a14o;
  True ->
    case ds1_dyB of _ {
      [] ->
        case Handle.Text.hPutStr2
               Handle.FD.stdout lvl17_r2fc True new_s_a14o
        of _ { (# new_s1_X15h, _ #) ->
        Handle.Text.hPutStr2
          Handle.FD.stdout lvl16_r2fb True new_s1_X15h
        };
      : ipv_sIs ipv1_sIt -> $wa_s2da new_s_a14o
    }

lvl17_r2fcモジュール レベルで 2 つの値が出力されていることがわかりますlvl16_r2fb。コードは次のとおりです。

lvl17_r2fc :: String
[GblId]
lvl17_r2fc =
  case foo_r2eT of _ { (xs_Xqp, s_Xq9) ->
  $w$cshowsPrec
    0
    (Data.List.sum_sum' xs_Xqp Data.List.genericDrop2)
    ([] @ Char)
  }

lvl16_r2fb :: String
[GblId]
lvl16_r2fb =
  case foo_r2eT of _ { (xs_apS, s_Xqp) ->
  $w$cshowsPrec 0 s_Xqp ([] @ Char)
  }

式の内部ではなく、モジュール レベルでバインドされるのはなぜですか? これは、レイジー リフティングの影響です。これは、共有を増加させる別の最適化であるため、スペースのパフォーマンスに悪影響を与えることがあります。この効果の別の発生については、GHC チケット 719を参照してください。

そのため、lvl17_r2fc原因の評価fooが評価され、左のエントリが遅延して出力されます。残念ながら、lvl16_r2fbまだ生きていて、完全なタプルを保持しています。また、ガベージ コレクターはこれがセレクター サンクであることを認識できない (ように見える) ため、Wadler の最適化は有効になりません。

対照的に、ここに"good1"akaのコードがありますlvl8_r2f1:

            case eqString ds_dyA lvl8_r2f1 of _ {
              False -> $wa2_s2dI w3_s2cF;
              True ->
                case ds1_dyB of _ {
                  [] ->
                    Handle.Text.hPutStr2
                      Handle.FD.stdout lvl7_r2f0 True w3_s2cF;
                  : ipv_sHg ipv1_sHh -> $wa2_s2dI w3_s2cF
                }
            } } in

出力される値は次の文字列です。

lvl7_r2f0 :: String
[GblId]
lvl7_r2f0 =
  case foo_r2eT of _ { (x_af6, y_af7) ->
  show_tuple
    (:
       @ ShowS
       (let {
          w2_a2bY [Dmd=Just L] :: Type.Integer

          w2_a2bY = lgo_r2eU mapAndSum1 x_af6 } in
        \ (w3_a2bZ :: String) ->
          $w$cshowsPrec 0 w2_a2bY w3_a2bZ)
       (:
          @ ShowS
          (\ (w2_a2bZ :: String) ->
             $w$cshowsPrec 0 y_af7 w2_a2bZ)
          ([] @ ShowS)))
    ([] @ Char)
  }

ご覧のとおり、タプルは 1 回だけ分解され、両方の値が使用されます。そのため、タプル全体を参照するものは何もなく、ガベージ コレクションの対象になる可能性があります。"good2"と についても同様です"good3"

"bad?"最適化されていない場合、次のコードが得られます。

 case eqString ds_dyA (unpackCString# "bad?")
                 of _ {
                   False -> fail2_dyN realWorld#;
                   True ->
                     case ds1_dyB of _ {
                       [] ->
                         $
                           @ (Type.Integer, Type.Integer)
                           @ (IO ())
                           (System.IO.print
                              @ (Type.Integer, Type.Integer) $dShow_rzk)
                           ($
                              @ ([Type.Integer], Type.Integer)
                              @ (Type.Integer, Type.Integer)
                              (Control.Arrow.first
                                 @ (->)
                                 Control.Arrow.$fArrow(->)
                                 @ [Type.Integer]
                                 @ Type.Integer
                                 @ Type.Integer
                                 sum'_rzm)
                              foo_rzl);
                       : ipv_szd ipv1_sze -> fail2_dyN realWorld#
                     }
                 } } in

viaの実装は反駁可能なパターンを使用するため、ガベージ コレクタが適切に処理する種類のセレクタ サンクが生成されます。first***

最適化された場合、物事は少し散らばっていますが、関連するコードは次のとおりです(最後の値は出力されているものです):

w_r2f2 :: Type.Integer

w_r2f2 =
  case foo_r2eT of _ { (x_aI1, y_aI2) ->
  lgo_r2eU mapAndSum1 x_aI1
  }

lvl9_r2f3 :: String -> String
[GblId, Arity=1]
lvl9_r2f3 =
  \ (w2_a2bZ :: String) ->
    $w$cshowsPrec 0 w_r2f2 w2_a2bZ

w1_r2f4 :: Type.Integer

w1_r2f4 = case foo_r2eT of _ { (x_aI6, y_aI7) -> y_aI7 }

lvl10_r2f5 :: String -> String
[GblId, Arity=1]
lvl10_r2f5 =
  \ (w2_a2bZ :: String) ->
    $w$cshowsPrec 0 w1_r2f4 w2_a2bZ

lvl11_r2f6 :: [ShowS]
[GblId]
lvl11_r2f6 =
  :
    @ ShowS lvl10_r2f5 ([] @ ShowS)

lvl12_r2f7 :: [ShowS]
[GblId]
lvl12_r2f7 = : @ ShowS lvl9_r2f3 lvl11_r2f6

lvl13_r2f8 :: ShowS
[GblId]
lvl13_r2f8 = show_tuple lvl12_r2f7

lvl14_r2f9 :: String
[GblId]
lvl14_r2f9 = lvl13_r2f8 ([] @ Char)

の使用はfirstインライン化されています。への2 つの呼び出しが見られるため、セレクターのように見えcase foo_r2eTますが、スペース リークが発生しやすくなっていw1_rf24ます (したがって、ランタイムが Wadler の最適化を適用することを期待しています)。静的なサンクではうまく機能しないのでしょうか? 実際、解説は、最新の場合、動的に割り当てられたセレクター サンクについてのみ説明しています。したがって、あなたfooがモジュールレベルの値 (またはむしろ遅延リフト可能) ではなく、何らかの入力に依存している場合w1_rf24は、動的に割り当てられるため、特別な処理の対象となる可能性があります。しかし、とにかくコードは非常に異なって見えるかもしれません。

于 2012-07-24T08:10:41.600 に答える