なぜ遅延パターンがsplitAt関数のバージョンにマッチするのですか？

Question

splitAt関数は（https://wiki.haskell.org/Lazy_pattern_match）以下のように実施することができる。

import Prelude hiding (splitAt) 
splitAt :: Int -> [a] -> ([a], [a]) 
splitAt n xs = 
    if n<=0 
    then ([], xs) 
    else 
     case xs of 
      [] -> ([], []) 
      y:ys -> 
      case splitAt (n-1) ys of 
       ~(prefix, suffix) -> (y : prefix, suffix) -- Here using lazy pattern match 

main :: IO() 
main = do 
    let r = splitAt 1000000 $ repeat 'a' 
    print $ length $ fst r 

と厳格なパターンマッチを使用しては非常に速度を遅くすることができます。

time ./lazy  -- 0.04s user 0.00s system 90% cpu 0.047 total 
time ./strict -- 0.12s user 0.02s system 96% cpu 0.147 total 

理由がわかりません。この記事によると、厳密なバージョンでは、パターンが適合するかどうかを確認するために、より多くのメモリとすべての再帰呼び出しが必要になる場合があります。しかし、私は怠惰なバージョンもすべての再帰呼び出しを必要とし、再帰関数呼び出しの結果を格納するメモリが必要だと思います。その違いは何ですか？

Answer 1

いくつかの違いがあります。

はのはGHC Haskellでは~

11行の評価がパターンマッチングによって駆動される場合とない場合の変種との間の動作の違いに見てみましょう。パターンがケース式または関数定義のLHSでマッチすると、パターンのコンストラクタを評価する必要があります。したがって、 splitAt 1000000 (repeat 'a')を評価することは、 splitAt 999999 ...への再帰呼び出しから得られた (,)コンストラクタを一致させること、最後には splitAt 0 ...の最後の呼び出しに至るまでに依存します。これには、スタック領域の評価が必要です。実際、それはかなり多い。クラッシュを避けるためにスタックを数回成長させる必要があります。

さらに、lengthが処理を開始する前に、結果の文字列"aaaaa..."全体がヒープ上に構築されます。 （repeatの最適化のために、結果の2番目の要素は実際には循環的にリンクされたリストであり、再帰的評価では全く新しいものを割り当てません）。

パターンマッチが遅延すると、 splitAt 1000000 (repeat 'a')の戻り値は、splitAtを再帰呼び出しすることなく、('a':_thunk1, _thunk2)と評価されます。これは、保護されたコアカチオンとして知られているパターンです。さらなる評価は、(,)および(:)のようなデータコンストラクタの後ろに隠されているため、別のケース式によって要求された場合にのみ実行されます。

fstへの呼び出しが離れ_thunk2をスローし、それは今まで評価されません。 、最初(:)コンストラクタを消費'a'値を投げ、その後、_thunk1に再帰呼び出しを行うことによりlength開始への呼び出し。この時点ではメモリ内にまだ(:)のコンストラクタが参照されていないので、ガベージコレクタは次に実行するときに自由に解放できます。 （'a'の値は共有されているので、まだポインタがあるので、このプロセス中には収集も割り当てもされません）

_thunk1が評価された場合は少し微妙です。それはsplitAt 999999 ...への再帰呼び出しを行います。結果は('a':_thunk3, _thunk4)になります。 _thunk4は何も保持されていないので、いつでもガベージコレクションが可能です。上記のように、lengthの評価が進行する。 (:)コンストラクタはもはやメモリに保持されず、自由に収集できます。

評価は、一度に1つのヒープ上の単一の(:)コンストラクタを保持し、スタック領域をまったく消費することなく行われます。 GHCのガベージコレクタの実行時間は、常駐セットのサイズによって異なります。この場合、は実際にはとなります。

私はこの場合、あなたが見ている速度の違いだと思っています。引数が+RTS -sである2つのプログラムを実行し、最大常駐サイズとガベージコレクタの実行時間に関する統計を調べてください。

GHCはであり、実際にはという巧妙な最適化が可能です。私はそれをチェックアウトしていないが、私はいくつかのケースではbuild関数の点で明示的な(:)アプリケーションの観点からアルゴリズムを書き換えることができることを知っている。そうするなら、foldr/build fusionが(:)コンストラクタの割り当てを完全に取り除くことができます。 （はい、lengthは主に動作するように融合を構築/ foldrを可能にし、効率のためにいくつかの本当にクールなトリックを経由してfoldrで定義されています。）

そのような場合、あなたは怠惰で行われても、少ない割り当てを見つけるだろう大文字と小文字は区別されますが、厳密な場合も同様です。私はそれがここで起こっているとは思わないが、私はテストしていないので、わからない。