GHCでのパターンマッチングのパフォーマンス

Question

私は作成したデータタイプ（基本的には "ストリーム"を扱う）のために "追加"関数を書いています。しかし、このデータ型には、無限、ヌル、固定長、可変長、既に追加されたさまざまなタイプの "ストリーム"を扱う12種類のコンストラクタがあります。

入力タイプと出力タイプの間に論理があります信じられないほど複雑ではありません。 *（12をして、それらの試合の内側に一致するか、144例に対して

だけのパターンマッチ（おそらく単純なプロキシタイプでラップすることによって）広いカテゴリーに対する

1. マッチ：

   は、私は二つのアプローチを検討してきました12）。特定の組み合わせに対してワイルドカードマッチでこれを100に減らすことはできましたが、それはそれです。

私は2番目のアプローチがより醜いと維持するのは難しいと知っていますが、それを無視して、GHCは2番目のアプローチを最適化しやすくしますか？単純なジャンプテーブル（またはおそらく2つのジャンプテーブル）で2番目のアプローチを行うことができれば、それはより速くなると思われます。しかし、それが線形チェックをしているなら、はるかに遅くなります。

GHC最適化パターンは、（非常に大きなものでも）一定時間ジャンプテーブルに一致しますか？

Answer 1

はい、GHCはこのようなパターンマッチを最適化します。最初の7つのコンストラクタは、ポインタのタグ付けによって特に最適化されます。私は残りがジャンプテーブルによって処理されると信じています。しかし、144のケースは維持するのが難しく、コードサイズを監視する必要があります。あなたは本当にそのすべての事件が必要ですか？

Answer 2

巨大なcase-blockと小さなベンチマークを書く小さなHaskellスクリプトを書くのは難しくありません。たとえば：Test1.hsとTest2.hs：あなたはこのコードを実行した場合

module Main (main) where 

mapping = zip ['!'..'z'] (reverse ['!'..'z']) 

test_code = 
    [ 
    "module Main where", 
    "", 
    "tester :: String -> String", 
    "tester cs = do", 
    " c <- cs", 
    " case transform c of", 
    " Just c' -> [c']", 
    " Nothing -> [c ]", 
    "", 
    "input = concat [ [' '..'z'] | x <- [1..10000] ]", 
    "", 
    "main = print $ length $ tester $ input", 
    "" 
    ] 

code1 = 
    test_code ++ 
    [ 
    "transform :: Char -> Maybe Char", 
    "transform c = lookup c " ++ show mapping 
    ] 

code2 = 
    test_code ++ 
    [ 
    "transform :: Char -> Maybe Char", 
    "transform c =", 
    " case c of" 
    ] ++ 
    map (\(k, v) -> " " ++ show k ++ " -> Just " ++ show v) mapping ++ 
    [ 
    " _ -> Nothing" 
    ] 

main = do 
    writeFile "Test1.hs" (unlines code1) 
    writeFile "Test2.hs" (unlines code2) 

、それは二つの小さなHaskellのソースファイルを生成します。前者は文字を文字にマップするのにPrelude.lookupを使います。後者は巨大なケースブロックを使用します。両方のファイルには、大量のデータリストにマッピングを適用し、結果のサイズをプリントするコードが含まれています。 （この方法はI/Oを避け、他の点では支配的な要因になります。）私のシステムでは、Test1は数秒で実行されますが、Test2はほとんど瞬間です。

これ以上の読者の方は、Data.Map.lookupを使用して速度を比較してみてください。

これは、パターン照合が、キー/値マッピングのリストのO（n）トラバースよりもはるかに高速であることを証明しています。しかし、あなた自身のベンチマークを作り上げてください。ネストされたケースとフラットケースの自動生成を試み、その結果をタイミングさせることができます。私の推測は、あなたに大きな違いは見られないが、それを試してみてくださいということです。