[解決済み] GHCはどのような最適化を確実に実行することが期待できますか？

質問

GHCには様々な最適化がありますが、それらがどのようなものなのか、またどのような状況でどの程度実行されるのかが分かりません。

私の質問は、どのような変換を毎回、あるいはほぼ毎回適用してくれると期待できるのか、ということです。もし私が頻繁に実行(評価)されるコードの一部を見て、最初に思ったことが "うーん、これは最適化すべきかも" だとしたら、次に思ったことは "考えるまでもない、GHCはこれを手に入れた" にするべきでしょうか?

論文を読んでいたら ストリームフュージョン。リスト、ストリーム、そして何もない状態へ その中で、リスト処理を別の形に書き換えて、GHCの通常の最適化によって確実に単純なループに最適化するというテクニックは、私にとって斬新でした。自分のプログラムがそのような最適化の対象になるかどうかは、どうすればわかるのでしょうか？

そこで 情報 GHCのマニュアルにあるのですが、質問に答えるための一助にしかなりません。

EDIT: 懸賞金を始めます。私が欲しいのは、lambda/let/case-floating、type/constructor/function argument specialization、strictness analysis and unboxing、worker/wrapper、その他私が省いてしまったGHCの重要な変換のリストと、説明と入力・出力コードの例、理想的には全体の効果がその部分の合計よりも大きい場合の図解などです。そして理想的には、どのような変換が しない が発生します。私は、すべての変換について小説のような長さの説明を期待しているわけではありません。2、3の文章とインラインの1行のコード例で十分です（20ページの科学論文へのリンクでなければ）。私は、コードの一部を見て、それがタイトなループにコンパイルされるかどうか、なぜそうならないか、それを作るには何を変えなければならないかについて、適切な推測ができるようになりたいと思っています。(ここでは、ストリームフュージョンのような大規模な最適化フレームワークにはあまり興味がありません。 書く これらのフレームワークが持っているものです)。

どのように解決するのですか？

このGHCのTracページ も、パスについてかなりよく説明しています。 このページ は最適化の順序を説明していますが、 Trac Wiki の大部分と同様、古くなっています。

具体的には、特定のプログラムがどのようにコンパイルされているかを見るのが一番でしょう。どの最適化が行われているかを知るには、プログラムを冗長的にコンパイルし、その際に -v フラグを使用します。私のコンピュータで見つけた最初のHaskellを例にとってみましょう。

Glasgow Haskell Compiler, Version 7.4.2, stage 2 booted by GHC version 7.4.1
Using binary package database: /usr/lib/ghc-7.4.2/package.conf.d/package.cache
wired-in package ghc-prim mapped to ghc-prim-0.2.0.0-7d3c2c69a5e8257a04b2c679c40e2fa7
wired-in package integer-gmp mapped to integer-gmp-0.4.0.0-af3a28fdc4138858e0c7c5ecc2a64f43
wired-in package base mapped to base-4.5.1.0-6e4c9bdc36eeb9121f27ccbbcb62e3f3
wired-in package rts mapped to builtin_rts
wired-in package template-haskell mapped to template-haskell-2.7.0.0-2bd128e15c2d50997ec26a1eaf8b23bf
wired-in package dph-seq not found.
wired-in package dph-par not found.
Hsc static flags: -static
*** Chasing dependencies:
Chasing modules from: *SleepSort.hs
Stable obj: [Main]
Stable BCO: []
Ready for upsweep
  [NONREC
      ModSummary {
         ms_hs_date = Tue Oct 18 22:22:11 CDT 2011
         ms_mod = main:Main,
         ms_textual_imps = [import (implicit) Prelude, import Control.Monad,
                            import Control.Concurrent, import System.Environment]
         ms_srcimps = []
      }]
*** Deleting temp files:
Deleting: 
compile: input file SleepSort.hs
Created temporary directory: /tmp/ghc4784_0
*** Checking old interface for main:Main:
[1 of 1] Compiling Main             ( SleepSort.hs, SleepSort.o )
*** Parser:
*** Renamer/typechecker:
*** Desugar:
Result size of Desugar (after optimization) = 79
*** Simplifier:
Result size of Simplifier iteration=1 = 87
Result size of Simplifier iteration=2 = 93
Result size of Simplifier iteration=3 = 83
Result size of Simplifier = 83
*** Specialise:
Result size of Specialise = 83
*** Float out(FOS {Lam = Just 0, Consts = True, PAPs = False}):
Result size of Float out(FOS {Lam = Just 0,
                              Consts = True,
                              PAPs = False}) = 95
*** Float inwards:
Result size of Float inwards = 95
*** Simplifier:
Result size of Simplifier iteration=1 = 253
Result size of Simplifier iteration=2 = 229
Result size of Simplifier = 229
*** Simplifier:
Result size of Simplifier iteration=1 = 218
Result size of Simplifier = 218
*** Simplifier:
Result size of Simplifier iteration=1 = 283
Result size of Simplifier iteration=2 = 226
Result size of Simplifier iteration=3 = 202
Result size of Simplifier = 202
*** Demand analysis:
Result size of Demand analysis = 202
*** Worker Wrapper binds:
Result size of Worker Wrapper binds = 202
*** Simplifier:
Result size of Simplifier = 202
*** Float out(FOS {Lam = Just 0, Consts = True, PAPs = True}):
Result size of Float out(FOS {Lam = Just 0,
                              Consts = True,
                              PAPs = True}) = 210
*** Common sub-expression:
Result size of Common sub-expression = 210
*** Float inwards:
Result size of Float inwards = 210
*** Liberate case:
Result size of Liberate case = 210
*** Simplifier:
Result size of Simplifier iteration=1 = 206
Result size of Simplifier = 206
*** SpecConstr:
Result size of SpecConstr = 206
*** Simplifier:
Result size of Simplifier = 206
*** Tidy Core:
Result size of Tidy Core = 206
writeBinIface: 4 Names
writeBinIface: 28 dict entries
*** CorePrep:
Result size of CorePrep = 224
*** Stg2Stg:
*** CodeGen:
*** CodeOutput:
*** Assembler:
'/usr/bin/gcc' '-fno-stack-protector' '-Wl,--hash-size=31' '-Wl,--reduce-memory-overheads' '-I.' '-c' '/tmp/ghc4784_0/ghc4784_0.s' '-o' 'SleepSort.o'
Upsweep completely successful.
*** Deleting temp files:
Deleting: /tmp/ghc4784_0/ghc4784_0.c /tmp/ghc4784_0/ghc4784_0.s
Warning: deleting non-existent /tmp/ghc4784_0/ghc4784_0.c
link: linkables are ...
LinkableM (Sat Sep 29 20:21:02 CDT 2012) main:Main
   [DotO SleepSort.o]
Linking SleepSort ...
*** C Compiler:
'/usr/bin/gcc' '-fno-stack-protector' '-Wl,--hash-size=31' '-Wl,--reduce-memory-overheads' '-c' '/tmp/ghc4784_0/ghc4784_0.c' '-o' '/tmp/ghc4784_0/ghc4784_0.o' '-DTABLES_NEXT_TO_CODE' '-I/usr/lib/ghc-7.4.2/include'
*** C Compiler:
'/usr/bin/gcc' '-fno-stack-protector' '-Wl,--hash-size=31' '-Wl,--reduce-memory-overheads' '-c' '/tmp/ghc4784_0/ghc4784_0.s' '-o' '/tmp/ghc4784_0/ghc4784_1.o' '-DTABLES_NEXT_TO_CODE' '-I/usr/lib/ghc-7.4.2/include'
*** Linker:
'/usr/bin/gcc' '-fno-stack-protector' '-Wl,--hash-size=31' '-Wl,--reduce-memory-overheads' '-o' 'SleepSort' 'SleepSort.o' '-L/usr/lib/ghc-7.4.2/base-4.5.1.0' '-L/usr/lib/ghc-7.4.2/integer-gmp-0.4.0.0' '-L/usr/lib/ghc-7.4.2/ghc-prim-0.2.0.0' '-L/usr/lib/ghc-7.4.2' '/tmp/ghc4784_0/ghc4784_0.o' '/tmp/ghc4784_0/ghc4784_1.o' '-lHSbase-4.5.1.0' '-lHSinteger-gmp-0.4.0.0' '-lgmp' '-lHSghc-prim-0.2.0.0' '-lHSrts' '-lm' '-lrt' '-ldl' '-u' 'ghczmprim_GHCziTypes_Izh_static_info' '-u' 'ghczmprim_GHCziTypes_Czh_static_info' '-u' 'ghczmprim_GHCziTypes_Fzh_static_info' '-u' 'ghczmprim_GHCziTypes_Dzh_static_info' '-u' 'base_GHCziPtr_Ptr_static_info' '-u' 'base_GHCziWord_Wzh_static_info' '-u' 'base_GHCziInt_I8zh_static_info' '-u' 'base_GHCziInt_I16zh_static_info' '-u' 'base_GHCziInt_I32zh_static_info' '-u' 'base_GHCziInt_I64zh_static_info' '-u' 'base_GHCziWord_W8zh_static_info' '-u' 'base_GHCziWord_W16zh_static_info' '-u' 'base_GHCziWord_W32zh_static_info' '-u' 'base_GHCziWord_W64zh_static_info' '-u' 'base_GHCziStable_StablePtr_static_info' '-u' 'ghczmprim_GHCziTypes_Izh_con_info' '-u' 'ghczmprim_GHCziTypes_Czh_con_info' '-u' 'ghczmprim_GHCziTypes_Fzh_con_info' '-u' 'ghczmprim_GHCziTypes_Dzh_con_info' '-u' 'base_GHCziPtr_Ptr_con_info' '-u' 'base_GHCziPtr_FunPtr_con_info' '-u' 'base_GHCziStable_StablePtr_con_info' '-u' 'ghczmprim_GHCziTypes_False_closure' '-u' 'ghczmprim_GHCziTypes_True_closure' '-u' 'base_GHCziPack_unpackCString_closure' '-u' 'base_GHCziIOziException_stackOverflow_closure' '-u' 'base_GHCziIOziException_heapOverflow_closure' '-u' 'base_ControlziExceptionziBase_nonTermination_closure' '-u' 'base_GHCziIOziException_blockedIndefinitelyOnMVar_closure' '-u' 'base_GHCziIOziException_blockedIndefinitelyOnSTM_closure' '-u' 'base_ControlziExceptionziBase_nestedAtomically_closure' '-u' 'base_GHCziWeak_runFinalizzerBatch_closure' '-u' 'base_GHCziTopHandler_flushStdHandles_closure' '-u' 'base_GHCziTopHandler_runIO_closure' '-u' 'base_GHCziTopHandler_runNonIO_closure' '-u' 'base_GHCziConcziIO_ensureIOManagerIsRunning_closure' '-u' 'base_GHCziConcziSync_runSparks_closure' '-u' 'base_GHCziConcziSignal_runHandlers_closure'
link: done
*** Deleting temp files:
Deleting: /tmp/ghc4784_0/ghc4784_1.o /tmp/ghc4784_0/ghc4784_0.s /tmp/ghc4784_0/ghc4784_0.o /tmp/ghc4784_0/ghc4784_0.c
*** Deleting temp dirs:
Deleting: /tmp/ghc4784_0

先頭から見て *** Simplifier: から、すべての最適化段階が行われる最後の段階まで、かなり多くのことがわかります。

まず、Simplifierはほぼすべてのフェーズの間で実行されます。これによって、多くのパスを書くことが非常に容易になります。例えば、多くの最適化を実装する場合、手動で行う代わりに、変更を伝搬させるための書き換えルールを作成するだけでよいのです。シンプリファイアは、インライン化やフュージョンなど、多くの単純な最適化を包含している。私が知っている主な制限は、GHCが再帰的な関数のインライン化を拒否することと、fusionが動作するためには、物事が正しく命名されていなければならないことです。

次に、実行されたすべての最適化の一覧を見てみましょう。

• 特殊化

  スペシャル化の基本的な考え方は、関数が呼び出される場所を特定し、ポリモーフィックでない、つまり呼び出される型に特化したバージョンの関数を作成することで、ポリモーフィズムとオーバーロードを取り除くことです。また、コンパイラにこのような処理をさせるために SPECIALISE のプラグマがあります。例として、階乗関数を考えてみよう。

  fac :: (Num a, Eq a) => a -> a
  fac 0 = 1
  fac n = n * fac (n - 1)
  
  

  コンパイラは使用される乗算のプロパティを知らないので、これを最適化することは全くできません。しかし、もしそれが Int のように、型だけが異なる新しいバージョンを作成することができるようになりました。

  fac_Int :: Int -> Int
  fac_Int 0 = 1
  fac_Int n = n * fac_Int (n - 1)
  
  

  次に、以下のルールが実行され、unboxed で動作するものができあがります。 Int の方がはるかに高速です。特殊化の別の見方として、型クラス辞書と型変数への部分適用がある。

  その ソース には、たくさんのメモが含まれています。

• フロートアウト

  EDIT: 私はどうやら以前から誤解していたようです。私の説明は全く変わってしまいました。

  この基本的な考え方は、繰り返してはいけない計算を関数の外に出すということです。例えば、こんなのがあったとする。

  \x -> let y = expensive in x+y
  
  

  上記のラムダでは、関数が呼ばれるたびに y が再計算されます。より良い関数で、浮動小数点が生成されます。

  let y = expensive in \x -> x+y
  
  

  処理を容易にするために、他の変換を適用することもできる。例えば、このようなことが起こります。

   \x -> x + f 2
   \x -> x + let f_2 = f 2 in f_2
   \x -> let f_2 = f 2 in x + f_2
   let f_2 = f 2 in \x -> x + f_2
  
  

  ここでも繰り返しの計算が省かれる。

  は ソース は、この場合、非常に読みやすい。

  現時点では、隣接する2つのラムダ間のバインディングはフローティングされません。例えば、このようなことは起こりません。

  \x y -> let t = x+x in ...
  
  

  へ

   \x -> let t = x+x in \y -> ...
  
  

• 内側に浮く

  ソースコードを引用します。

  の主な目的は floatInwards そのため、物を割り当ててスタックに保存した後、選択したブランチでそれが必要でないことが判明するようなことがないようにします。

  例えば、こんな式があったとしよう。

  let x = big in
      case v of
          True -> x + 1
          False -> 0
  
  

  もし v と評価されます。 False を使用することにより x これはおそらく大きなサンクであり、時間とスペースを浪費しています。内側に浮かせると、これが修正され、このようになります。

  case v of
      True -> let x = big in x + 1
      False -> let x = big in 0
  
  

  で置き換えられ、その後、単純化されます。

  case v of
      True -> big + 1
      False -> 0
  
  

  本紙 は、他のトピックもカバーしているが、かなり明確なイントロダクションを提供している。なお、フローティング・インとフローティング・アウトは、その名前に反して、2つの理由から無限ループに陥ることはない。

  1. フロートインフロートインで、次のようになります。 case 文、float out は関数を扱います。
  2. パスの順番は決まっているので、無限に交互になることはないはずです。

• 需要分析

  要求分析、または厳密性分析は、変換というよりも、その名前が示すように、情報収集のためのパスです。コンパイラは、常に引数（または少なくともその一部）を評価する関数を見つけ、それらの引数をcall-by-needではなくcall-by-valueで渡します。サンクのオーバーヘッドを回避できるため、多くの場合、この方がはるかに高速になります。Haskellの多くのパフォーマンス問題は、このパスが失敗するか、コードが単に十分に厳密でないかのどちらかで発生します。簡単な例としては foldr , foldl および foldl' はスタックオーバーフローを起こし、2番目はヒープオーバーフローを起こしますが、最後のは厳密性のため正常に動作します。これはおそらく、これらの中で最も理解しやすく、最もよく文書化されているものでしょう。ポリモーフィズムやCPSのコードは、しばしばこれを打ち破ると私は思っています。

• Worker Wrapperのバインド

  Worker/Wrapper変換の基本的な考え方は、単純な構造体の上でタイトなループを行い、末端でその構造体との間で変換を行うことです。例えば、ある数の階乗を計算するこの関数を考えてみましょう。

  factorial :: Int -> Int
  factorial 0 = 1
  factorial n = n * factorial (n - 1)
  
  

  の定義を使って Int をGHCで調べると、次のようになります。

  factorial :: Int -> Int
  factorial (I# 0#) = I# 1#
  factorial (I# n#) = I# (n# *# case factorial (I# (n# -# 1#)) of
      I# down# -> down#)
  
  

  でコードがカバーされていることに注目してください。 I# s? このようにすることで削除できます。

  factorial :: Int -> Int
  factorial (I# n#) = I# (factorial# n#)
  
  factorial# :: Int# -> Int#
  factorial# 0# = 1#
  factorial# n# = n# *# factorial# (n# -# 1#)
  
  

  この具体的な例はSpecConstrでも可能でしたが、ワーカー／ラッパー変換は非常に一般的なことが可能です。

• 共通部分式

  これも厳密性解析と同様、実にシンプルな最適化でありながら、非常に効果的です。基本的な考え方は、2つの式が同じであれば、同じ値を持つということです。例えば、もし fib がフィボナッチ数の計算機である場合、CSEは以下のように変換します。

  fib x + fib x
  
  

  に入っています。

  let fib_x = fib x in fib_x + fib_x
  
  

  で、計算が半分になります。しかし、残念ながら、他の最適化の邪魔になることもある。もう一つの問題は、二つの式が同じ場所になければならないことと、それらが 構文的に は同じであって、値で同じではありません。例えば、次のようなコードでは、インライン化を重ねないとCSEは発火しません。

  x = (1 + (2 + 3)) + ((1 + 2) + 3)
  y = f x
  z = g (f x) y
  
  

  しかし、llvm を使ってコンパイルした場合、その Global Value Numbering パスのために、この一部が結合されるかもしれません。

• リベレートケース

  この変換は、コードの爆発を引き起こすという事実の他に、ひどく文書化されていないように思われます。以下は、私が見つけたわずかなドキュメントを再フォーマットした（そして少し書き直した）バージョンです。

  このモジュールは Core を、そして case を自由変数に設定します。基準は、もし case を持つ場合、その再帰的呼び出しは展開に置き換えられる。たとえば、次のような場合です。

  f = \ t -> case v of V a b -> a : f t
  
  

  内側の f が置き換えられます。

  f = \ t -> case v of V a b -> a : (letrec f = \ t -> case v of V a b -> a : f t in f) t
  
  

  シャドーイングが必要なことに注意してください。簡略化すると、次のようになる。

  f = \ t -> case v of V a b -> a : (letrec f = \ t -> a : f t in f t)
  
  

  これは、より良いコードです。 a は内側の letrec からの投影が必要なのではなく v . これは 自由変数 を扱うSpecConstrとは異なります。 引数 のように、既知の形式である。

  SpecConstrの詳細については、以下を参照してください。

• SpecConstr - これは、次のようなプログラムを変換します。

  f (Left x) y = somthingComplicated1
  f (Right x) y = somethingComplicated2
  
  

  に入っています。

  f_Left x y = somethingComplicated1
  f_Right x y = somethingComplicated2
  
  {-# INLINE f #-}
  f (Left x) = f_Left x
  f (Right x) = f_Right x
  
  

  拡張例として、次のような定義を考えてみましょう。 last :

  last [] = error "last: empty list"
  last (x:[]) = x
  last (x:x2:xs) = last (x2:xs)
  
  

  まず、これを次のように変換します。

  last_nil = error "last: empty list"
  last_cons x [] = x
  last_cons x (x2:xs) = last (x2:xs)
  
  {-# INLINE last #-}
  last [] = last_nil
  last (x : xs) = last_cons x xs
  
  

  次に、シンプリファイアが実行され、次のようになります。

  last_nil = error "last: empty list"
  last_cons x [] = x
  last_cons x (x2:xs) = last_cons x2 xs
  
  {-# INLINE last #-}
  last [] = last_nil
  last (x : xs) = last_cons x xs
  
  

  このプログラムでは、リストの先頭を何度もボックス化したり、ボックス化解除したりしていないので、より高速になったことに注意してください。また、インライン化は、新しい、より効率的な定義を実際に使用できるようにし、再帰的な定義をより良くするために、非常に重要であることに注意してください。

  SpecConstrは、多くのヒューリスティックによって制御されています。論文で紹介されているのは、このようなものです。

  1. ラムダは明示的に、アリティは a .
  2. 右側は"十分に小さい"フラグで制御されているものです。
  3. この関数は再帰的であり、右手側で特殊化可能な呼び出しが使用される。
  4. 関数の引数がすべて存在する。
  5. 引数のうち少なくとも1つは、コンストラクタのアプリケーションである。
  6. その引数は、関数内のどこかでケース分析されている。

  しかし、ヒューリスティックはほぼ確実に変化しています。実際、この論文では、別の第6のヒューリスティックに言及しています。

  議論に特化する x 場合のみ x は のみ によって精査される。 case 通常の関数に渡されたり、結果の一部として返されることはない。

これは非常に小さなファイル（12行）なので、おそらくそれほど多くの最適化は発動していないでしょう（全部やったとは思いますが）。また、なぜそのパスを選んだのか、なぜその順番にしたのかもわかりません。