21

私はhaskellコードの一部で定義された2つの関数を持っています：

lengthwtilde [] = 0
lengthwtilde ~(_:xs) = 1 + lengthwtilde xs

lengthwotilde [] = 0
lengthwotilde (_:xs) = 1 + lengthwotilde xs

両方をghciで（を使用して:set +s）テストするlengthwtildeと、（パターンマッチの前にチルダがあるもの）のパフォーマンスlengthwotildeが約3秒よりも大幅に遅いことがわかります。

*Main> lengthwtilde [1..10000000]
10000000
(19.40 secs, 1731107132 bytes)
*Main> lengthwotilde [1..10000000]
10000000
(16.45 secs, 1531241716 bytes)

どうしてこれなの？

4

1 に答える 1

43

パターンマッチの前にを追加する~と、そのマッチは反駁できなくなります。これは、パターンに余分な怠惰を追加することと考えることができます。これにより、評価に絶対に一致する必要がない限り、一致が失敗することはありません。簡単な例を次に示します。

Prelude> (\ (_:_) -> "non-empty") []
"*** Exception: <interactive>:2:2-23: Non-exhaustive patterns in lambda

Prelude> (\ ~(_:_) -> "oops") []
"oops"

反駁できないパターン一致では、空のリストでパターン一致が失敗しても、バインドされた変数が評価されないため、エラーは発生しません。基本的に、反駁できないパターンマッチは、関数を次のように変換します。

\ xs -> let (_:_) = xs in "oops"

長さ関数を遅くするのは、この余分な怠惰のラッピングです。同じlet-binding変換を適用するとlengthwtilde、

lengthwtilde [] = 0
lengthwtilde xs' = let (_:xs) = xs' in 1 + lengthwtilde xs

これがどのように評価されるかを考えてください。トップレベルでは、を取得します1+lengthwtilde xs。しかし、xsは自由変数であるため、評価されません。したがって、次のステップで、最初xsに評価されて、の2番目のケースと一致するかどうかが判断されlengthwtilde、プロセスが繰り返されます。

これをと比較してlengthwotildeください。この関数では、関数の2番目のケースでマッチングを行うと、引数も強制的に評価されます。最終結果は同じですが、別のサンクを強制的に残すよりも早くアンラップできる方が効率的です。

技術的lengthwtildeには少し複雑です。引数は2番目のブランチですでに評価されています。これは、どのブランチにいるかを判断する方法であるためですが、再帰呼び出しに渡されると、引数は再ラップされます。

生成されたコアを確認できると便利です。lengthwotildeこれが（から生成された：から生成されghc -O0た）の出力です

Foo.lengthwotilde =
  \ (@ t_afD)
    (@ a_afE)
    ($dNum_afF :: GHC.Num.Num a_afE)
    (eta_B1 :: [t_afD]) ->
    letrec {
      lengthwotilde1_af2 [Occ=LoopBreaker] :: [t_afD] -> a_afE
      [LclId, Arity=1]
      lengthwotilde1_af2 =
        \ (ds_dgd :: [t_afD]) ->
          case ds_dgd of _ {
            [] -> GHC.Num.fromInteger @ a_afE $dNum_afF (__integer 0);
            : ds1_dge xs_af1 ->
              GHC.Num.+
                @ a_afE
                $dNum_afF
                (GHC.Num.fromInteger @ a_afE $dNum_afF (__integer 1))
                (lengthwotilde1_af2 xs_af1)
          }; } in
    lengthwotilde1_af2 eta_B1

関数lengthwotilde1_af2はすぐcaseに引数ds_dgd（これは入力リストです）に対してaを実行し、次にケース内で再帰してサンクを形成することに注意してください（いくつかの拡張があります）。

1 + len [2..]
1 + (1 + len [3..])
1 + (1 + (1 + len [4..])

最終的には1+（1 +（1 +（1 + ..）））の評価が必要です。

これがlengthwtilde

Foo.lengthwtilde =
  \ (@ t_afW)
    (@ a_afX)
    ($dNum_afY :: GHC.Num.Num a_afX)
    (eta_B1 :: [t_afW]) ->
    letrec {
      lengthwtilde1_afM [Occ=LoopBreaker] :: [t_afW] -> a_afX
      [LclId, Arity=1]
      lengthwtilde1_afM =
        \ (ds_dgh :: [t_afW]) ->
          case ds_dgh of wild_X9 {
            [] -> GHC.Num.fromInteger @ a_afX $dNum_afY (__integer 0);
            : ipv_sgv ipv1_sgw ->
              GHC.Num.+
                @ a_afX
                $dNum_afY
                (GHC.Num.fromInteger @ a_afX $dNum_afY (__integer 1))
                (lengthwtilde1_afM
                   (case wild_X9 of _ {
                      [] ->
                        (Control.Exception.Base.irrefutPatError
                           @ () "foo.hs:(3,1)-(4,42)|(_ : xs)")
                        `cast` (UnsafeCo () [t_afW] :: () ~# [t_afW]);
                      : ds1_dgk xs_aeH -> xs_aeH
                    }))
          }; } in
    lengthwtilde1_afM eta_B1

これを評価すると、別のサンクが形成されます。

len [1..]
1 + (len (if null [1..] then error else [2..]))
1 + (len [2..])
1 + (1 + len (if null [2..] then error else [3..]))

最終的には、最初に取得したのと同じ一連の追加が発生しますが、反駁できないパターンの失敗を処理するための追加のロジックがいくつかあります。

(:)さて、コンパイルされたコードを最適化して実行している場合、ghcは、引数がすでに評価されており、この時点でコンストラクターを使用することがわかっているため、引数がnullになる可能性がないことをほぼ確実に検出します。そして、コードをコンパイルしてghc -O2実行すると、両方の関数が同じ時間で実行されます。どちらの方法でもサンクの連鎖が発生するため、どちらもかなり悪いです。の標準的な定義は、適切な定義lengthと同様に、はるかに優れていfoldl'ます。

于 2013-03-03T02:42:09.350 に答える