![digraph {
subgraph cluster_a {
label = "静的領域"
labelloc = b
style=filled
b [shape=record, label="{.\n.\ninfo\ntable | entry\ncode\n.\n.}"]
}
a [shape=record, label="<ip>infoptr | データ色々..."]
a:ip -> b:e [weight=100]
}](generic.png)
通常のHaskellの値(代数的データ型および関数)と、未評価の計算を表すサンクは、全てポインタで参照される。ポインタが指す先は通常はヒープ上のオブジェクトだが、静的セクションに置かれていることもある。いずれにしてもレイアウトは同じで、以下の一般形をとる。
オブジェクトの先頭1ワードは静的領域へのポインタ(infoポインタ)で、この値を評価(関数なら適用)するためのコード(entry code)と、このオブジェクトの種類に関する情報を集積したレコードを指している。なお、GHCにおける1ワードはポインタと同じ大きさ、つまり32ビットOSなら32ビット、64ビットOSなら64ビットである。これはIntの精度と同じでもある。
代数的データ型の評価済みの値では、infoポインタが構築子の種類を表し、その後に構築子の引数を入れるスロットが続く。したがって、N引数の構築子で作られたデータならN+1ワードを占有する。ただし無引数の構築子は静的領域に置かれて共有されるので、それ自身ではスペースを消費しない。例として、(Just x, Nothing)というデータは次のように表現される。
![digraph {
subgraph cluster_a {
label = "静的領域"
labelloc = b
style=filled
Nothing [shape=record]
}
tup [shape=record, label="(,)|<fst>|<snd>"]
fst [shape=record, label="Just|<val>"]
tup:fst -> fst
tup:snd -> Nothing
fst:val -> x
x [shape=none]
}](algebraic.png)
GHCではIntやDoubleなどの型はプリミティブではなく、内部に非ボックス化型(ja)を持つ代数的データ型として定義されている。これらの非ボックス化数値型はポインタ経由でなく直接扱われる生の値で、データ構築子の引数として使われた場合にはメモリオブジェクトの中に直接埋め込まれる。Ptr aの内部表現であるAddr#についても同様。例えば、(36 :: Int)の内部表現は次のような2ワードのオブジェクトである。
![graph {
x [shape=record, label="I#|36#"]
}](int.png)
文字列はCharのリストなので、以上のことから、完全に評価済みなら1文字あたり5ワードを占めることが分かる。これは64ビット環境だと1文字40バイトに相当し、相当な贅沢品である。
![digraph {
cons1 [shape=record, label="(:)|<head>|<tail>"]
cons2 [shape=record, label="(:)|<head>|<tail>"]
char1 [shape=record, label="C#|'海'#"]
char2 [shape=record, label="C#|'老'#"]
"..." [shape=none]
cons1:head -> char1
cons1:tail -> cons2
cons2:head -> char2
cons2:tail -> "..."
}](string.png)
(評価済みの)関数では、infoポインタが関数本体のコードを指し、その後に自由変数の値が保存される。ここでいう自由変数とは、関数本体で使われている変数のうち、その関数の外なおかつトップレベル以外の場所で定義された変数のこと。例えば「\a -> x + a + 1」は次のように表現される。
![digraph {
subgraph cluster_a {
label="静的領域"
labelloc = b
style=filled
b [shape=record, label="{a=arg0;\nx=closure[1];\nEVAL(a);\n.\n.}"]
}
clo [shape=record, label="<fun>|<free>"]
x [shape=none]
clo:fun -> b
clo:free -> x
}](function.png)
サンクは関数と同じ形で表現される。
非ボックス化タプル(ja)は実行時表現を持たない。「(# a, b #)」を返す関数は、単にaとbの二つの値をレジスタ(かスタック)に入れて返す。
Core言語はGHCが使う中間言語の一つで、そのなかで最も高水準(つまりHaskell寄り)のものである。GHCが行う最適化のうち派手なものはすべてCore言語に対して適用される。プログラムの低水準の振る舞い(たとえば、「このループでメモリ確保は発生する？」「この式はどのタイミングで評価される？」)を理解したり、GHCの最適化の結果を見たりするのには、Core言語形式の中間出力を読むと良い。特に、小さいループを可能な限り高速化したい場合など、最適化後のCore出力を比較しながらコードをいじるのが有効なことがある。
Core形式の最終形(最適化された後、STG言語に変換される直前)は-ddump-prepで読める。例として以下に、小さなモジュールと、それをghc-7.0.1 -ddump-prep(最適化なし)でコンパイルした結果を表示しておく。
module M where mylength :: [a] -> Int mylength [] = 0 mylength (_:xs) = 1 + mylength xs
Rec { M.mylength [Occ=LoopBreaker] :: forall a_aaz. [a_aaz] -> GHC.Types.Int [GblId, Arity=1] M.mylength = \ (@ a_aaM) (ds_sjK :: [a_aaM]) -> case ds_sjK of _ { [] -> GHC.Types.I# 0; : _ xs_sjP -> let { sat_sjT :: GHC.Types.Int [LclId] sat_sjT = M.mylength @ a_aaM xs_sjP } in let { sat_sjU :: GHC.Types.Int [LclId] sat_sjU = GHC.Types.I# 1 } in GHC.Num.+ @ GHC.Types.Int GHC.Num.$fNumInt sat_sjU sat_sjT } end Rec }
Core言語は大ざっぱにHaskellのサブセットと考えることができる。小さな言語であり、言語要素と言えるのは「関数適用」「ラムダ抽象」「let/letrec」「case」だけ。これに加えて、以下の点でHaskellと大きく違う。
型抽象と型適用が明示的。つまり多相関数が明示的に型パラメタを取る。例えば「length :: [a] -> Int」という関数は、値パラメタとしてリストを取るのに加えて型パラメタ「a」を取る。ラムダ抽象と関数適用の際、型パラメタには「@」を前置して区別する。「length = \ (@ a) (xs :: [a]) -> ...」のように定義し、「length @ Char str」のように使う。
型理論の言葉では、System Fωにcoercionを付け加えたSystem FCをベースにしている、らしい。これらの型情報は次の中間言語STGに変換される際に捨て去られ、実行時には跡形も残らないので、以降では無視する。
-ddump-prep形式のCore言語の売りの一つは、実際のマシン上での動作と言語要素との間に比較的素直な対応があることだ。大体以下のようなものである。なお細かい最適化は省いた。
大きく見ると、新しい式の評価はcaseによって(のみ)開始され、評価済みの値に到達することによって(のみ)終わる。これは、caseが検査対象をWHNFにまで評価するということとちょうど一致している。
このように、-ddump-prepで出力されるCore形式は、言語要素が実行時の振る舞いにほぼ一対一で対応するという点で低水準な理解に適している。一方で、低水準すぎて長くて読み難いことがあるので、そういう場合は最適化直後のCore表現を-ddump-simplで見ることができる。GHCによる最適化の具合を見るだけならこちらが見易いかもしれない。-ddump-prepでの形式と異なる点は以下など。
HaskellからCoreへの変換過程は、主に構文糖を取り除くことで行われ、脱糖(desugar)と呼ばれる。具体的には、リスト内包表記をifとconcatMapへ、do記法を(>>=)へ、whereをletへ、ガードをifへ、ifをcaseへ、など。
さらに、型クラスが「辞書渡し」変換によって取り除かれる。まず、それぞれのクラスに対して対応するレコード型("辞書"の型)が作られる。
class Show a where show :: a -> String ↓ data Show a = D:Show{ show :: a -> String }
instance宣言は、そのレコード型の変数になる。文脈のあるinstance宣言は関数になる。
instance Show Int where show = ... ↓ dShow_Int :: Show Int dShow_Int = D:Show{ show = ... }
instance (Show a) => Show [a] where show = ... ↓ dShow_List :: Show a -> Show [a] dShow_List d = D:Show{ show = ... }
クラス制約を要求する関数は、辞書を受けとる関数になる。
print :: (Show a) => a -> IO () print = putStrLn . show ↓ print :: Show a -> a -> IO () print d = putStrLn . show d
次の関数を考える。
cube :: Int -> Int cube x = x * x * x
静的型のあるネイティブコンパイル型言語なら(そして掛け算のできるCPUなら)、この乗算は一個あたり機械語の一命令にコンパイルされることが期待されると思う。実際、最適化が有効ならGHCはそのようなコードを生成する。以下はghc-7.0.1 -O -ddump-prepの出力。
M.cube :: GHC.Types.Int -> GHC.Types.Int [GblId, Arity=1, Caf=NoCafRefs, Str=DmdType U(L)m, Unf=OtherCon []] M.cube = \ (x_sjU :: GHC.Types.Int) -> case x_sjU of _ { GHC.Types.I# x1_sjX -> case GHC.Prim.*# x1_sjX x1_sjX of sat_sk1 { __DEFAULT -> case GHC.Prim.*# sat_sk1 x1_sjX of sat_sk2 { __DEFAULT -> GHC.Types.I# sat_sk2 } } }
一方、最適化なしでは、生成されるコードは全く異なる。
M.cube :: GHC.Types.Int -> GHC.Types.Int [GblId, Arity=1, Unf=OtherCon []] M.cube = \ (x_sjx :: GHC.Types.Int) -> let { sat_sjz :: GHC.Types.Int [LclId] sat_sjz = GHC.Num.* @ GHC.Types.Int GHC.Num.$fNumInt x_sjx x_sjx } in GHC.Num.* @ GHC.Types.Int GHC.Num.$fNumInt sat_sjz x_sjx
ここで、GHC.Num.$fNumIntはNum Intを表現する辞書であり、GHC.Num.*はその辞書から(*)関数を選択する関数。これは2回の余分なメモリ確保と少なくとも2回の間接ジャンプ、数え切れないほどのメモリアクセスを伴うコードである。
以下に、GHCが行う最適化のうち特に重要だと思う二つを紹介する。
GHCは激しいインライン化を行なう。
インライン化の恩恵は、単に関数呼び出しのオーバーヘッドを消すことよりも、コードの複製によって新しい最適化が可能になることにある。例として、上のcube関数を考える。まずIntについての(*)の実装は次のように書ける。
timesInt :: Int -> Int -> Int timesInt = \x y -> case x of I# x' -> case y of I# y' -> I# (x' *# y')
このtimesIntは呼び出し一回あたり一回のメモリ確保(構築子を被せる)と、二回のcase検査(構築子を剥ぎ取る)を行なう。よって、cubeからこれを普通に呼び出すと、メモリ確保二回にcase四回が必要になる。
一方、timesIntをcubeにインライン化しすれば、GHCが局所的な最適化を適用して無駄を省く余地が生まれる。ここでは、同じ変数を複数回検査しているのを一回にする最適化と、I#を被せてすぐ剥がすのを省略する最適化が可能。最終的なcubeのコードはメモリ確保一回と検査一回しか行なわない。
GHCの-funfolding-use-thresholdフラグに大きな値(例えば100)を渡すと、GHCは通常より積極的にインライン化を行なうようになる。実行ファイルの肥大化・コンパイル時間の増大と引き換えに、実行速度がかなり大きく(例えば20%)改善されることがある。
インライン化による中間データの排除は魅力的な最適化だが、いつも可能とは限らない。対象となる関数が大きすぎたり再帰的だったりする場合、インライン化によって望ましくないコード膨張が発生することがある。そこで定義本体を複製せずに中間データの排除を行なう最適化があれば嬉しい。それを可能にするのがworker/wrapper変換である。
再帰関数の例としてreplicateを使う。
replicate :: Int -> a -> [a] replicate 0 _ = [] replicate n x = x : replicate (n-1) x
脱糖して(-)や(==)のインライン化を行い整理すると、次のようなものが得られる。
replicate :: Int -> a -> [a] replicate = \n x -> case n of I# n' -> case n' ==# 0# of True -> [] False -> x : replicate (I# (n' -# 1#)) x
この定義では、再帰一回ごとにI#を付けたり外したりする無駄がある。ここでworker/wrapper変換が必要になる。
replicateは受け取ったInt型のnに対して即座にcaseを使い、I#構築子を剥ぎ取っている。worker/wrapper変換の第一段階は、予めI#構築子を外された後のInt#を受け取るような定義を新しく作ることである。
$wreplicate :: Int# -> a -> [a] $wreplicate = \n' x -> case n' ==# 0# of True -> [] False -> x : replicate (I# (n' -# 1#)) x
これは実際の仕事を行なう関数なのでworkerと呼ばれる。名前の「$w」はそれを示している。
次にこのworkerを使ってreplicateを定義しなおす。
{-# INLINE replicate #-} replicate :: Int -> a -> [a] replicate = \n x -> case n of I# n' -> $wreplicate n' x
新しいreplicateは$wreplicateを薄くラップするだけの関数になるのでwrapperと呼ぶ。wrapperは常に小さい関数であり、コード膨張の危険なしにあらゆる呼び出し元にインライン化できる。このインライン化によって中間データを排除するというのがこの変換の基本的な考え方である。
手始めにreplicateを$wreplicateへインライン化する。
$wreplicate = \n' x -> case n' ==# 0# of True -> [] False -> x : case (I# (n' -# 1#)) of I# n'' -> $wreplicate n'' x
これで、I#構築子を作ってすぐに排除していることが明らかな形になったので、局所的な変換でこれを取り除くことができる。最終的にGHCが生成するコードは次のようなものである。
$wreplicate :: Int# -> a -> [a] $wreplicate = \n' x -> case n' ==# 0# of True -> [] False -> x : $wreplicate (n' -# 1#) x {-# INLINE replicate #-} replicate :: Int -> a -> [a] replicate = \n x -> case n of I# n' -> $wreplicate n' x
$wreplicateはI#構築子を一切使わない効率的な形になった。同様に、外からreplicateを呼ぶ箇所には全てwrapperがインライン化され、可能ならば中間のI#構築子が排除されることが期待できる。
このようにインライン化とworker/wrapper変換は強力な最適化であり、コードの効率を大幅に向上させ得る。しかしこれは同時に、これらの最適化が阻害されるとパフォーマンスに重大な悪影響があるということでもある。これらの最適化ができないのはどういう場合か。呼ぶべき関数が実行時まで決まらないときである。決まっていない関数をインライン化することはできないし、同様にworker/wrapperの恩恵も受けられない。
呼ぶべき関数が決まらないという状況は高階関数をコンパイルするときに発生するほか、型クラスで多重定義された関数についても発生する。(辞書渡しの実装を考えれば、多重定義関数は暗黙に高階関数である)。例として、replicateの多重定義版であるgenericReplicateを考えてみる。
genericReplicate :: (Integral a) => a -> b -> [b] genericReplicate 0 _ = [] genericReplicate n x = x : genericReplicate (n-1) x
これをghc-7.0.1 -O2でコンパイルしたものが以下。詳細はどうでもいいが、酷いコードなのが分かると思う。
lvl_rvs :: GHC.Integer.Type.Integer [GblId, Caf=NoCafRefs, Str=DmdType] lvl_rvs = GHC.Integer.Type.S# 1 lvl1_rvu :: GHC.Integer.Type.Integer [GblId, Caf=NoCafRefs, Str=DmdType] lvl1_rvu = GHC.Integer.Type.S# 0 Rec { T.genericReplicate [Occ=LoopBreaker] :: forall a_aaz b_aaA. GHC.Real.Integral a_aaz => a_aaz -> b_aaA -> [b_aaA] [GblId, Arity=1, Caf=NoCafRefs, Str=DmdType L] T.genericReplicate = \ (@ a_agZ) (@ b_ah0) ($dIntegral_ah1 :: GHC.Real.Integral a_agZ) -> let { a_svo :: GHC.Real.Real a_agZ [LclId] a_svo = GHC.Real.$p1Integral @ a_agZ $dIntegral_ah1 } in let { $dNum_sv7 [Dmd=Just D(SAAATAAAL)] :: GHC.Num.Num a_agZ [LclId, Str=DmdType] $dNum_sv7 = GHC.Real.$p1Real @ a_agZ a_svo } in let { a1_svq :: GHC.Classes.Eq a_agZ [LclId] a1_svq = GHC.Num.$p1Num @ a_agZ $dNum_sv7 } in let { lvl2_svi :: a_agZ -> b_ah0 -> [b_ah0] [LclId] lvl2_svi = T.genericReplicate @ a_agZ @ b_ah0 $dIntegral_ah1 } in let { lvl3_svb :: a_agZ [LclId, Str=DmdType] lvl3_svb = GHC.Num.fromInteger @ a_agZ $dNum_sv7 lvl_rvs } in let { lvl4_sv9 [Dmd=Just L] :: a_agZ [LclId, Str=DmdType] lvl4_sv9 = GHC.Num.fromInteger @ a_agZ $dNum_sv7 lvl1_rvu } in \ (ds_dr0 :: a_agZ) (ds1_dr1 :: b_ah0) -> case GHC.Classes.== @ a_agZ a1_svq ds_dr0 lvl4_sv9 of _ { GHC.Bool.False -> GHC.Types.: @ b_ah0 ds1_dr1 (lvl2_svi (GHC.Num.- @ a_agZ $dNum_sv7 ds_dr0 lvl3_svb) ds1_dr1); GHC.Bool.True -> GHC.Types.[] @ b_ah0 } end Rec }
この種の非効率を回避するには、多重定義関数(あるいは高階関数)自体をインライン化させるのが効果的だ。その多重定義関数の呼び出し元で具体的な型が分かっているなら、インライン化によって多重定義を排除できる。こういう場合、GHCが自動でインライン化しないような大き目の関数についても、INLINE/INLINABLEプラグマを使ってインライン化を指示すると良いことがある。例えばControl.MonadのmapM_関数にはINLINEが指定されている。
多重定義関数の場合にはもう一つ、SPECIALIZEプラグマを使うという方法もある。この方法では余分なコードの複製を避けることができるが、多重定義をどの型で解決するかが予め分かっていないと使えないという欠点がある。また、インライン化の場合と同じく、呼び出し元において具体的な型が分かっていないと効果がない。
どちらの方法も使えないときは、GHCの自動最適化に期待することができないので、手動で最適化を行なうことになる。中間データの排除なら、(Int -> Int)の関数を受け取る高階関数を(Int# -> Int#)を受け取るように書き換えるなど。この方法の欠点は、低水準かつGHC依存のプリミティブ型を直接扱う必要があること。
worker/wrapper変換についてもう少し詳しく見る。変換によって生成されるworkerを元の関数と比べると、引数の型や戻り値の型が違う。
元の関数の引数が以下の条件をすべて満たしている場合、workerには、その引数を渡す代わりにそれの内容(フィールド)が直接渡される。
これによって直接渡されることになったフィールドに対しても、この操作は再帰的に適用される(workerの引数が増えすぎない限りにおいて)。また、ある引数が全く使われていない場合、workerはそれを受け取らない。
元の関数の戻り値が以下の条件をすべて満たしている場合、workerは戻り値の内容(フィールド)を個々に(非ボックス化タプルで)返す。
この変換は再帰的には適用されない。つまり、(Int, (Char, Bool))を返す関数に対して(# Int, (Char, Bool) #)を返すworkerは生成され得るが、(# Int, Char, Bool #)や(# Int#, Char#, Bool #)を返すworkerは生成されない。
worker/wrapper変換は低水準のループを書くときに特に重要である。内側のループの中に無駄なデータ構築子の付け外しが残ると、性能に致命的な悪影響を与えることがある。一方で、そういった無駄さえなければ、単純なループに関してGHCはCで書いたものに大きく劣らないコードを生成できる。
低水準コードの例として、以下にファイルのCRCを求めるプログラムを貼っておく。アルゴリズムはUNIXのcksumユーティリティのもの。これをghc-7.0.1 -O2 -fllvmでコンパイルすると、手元の環境では約240MiB/sの性能が出る。これはGNU Coreutilsのcksumより5%ほど速い。
{-# LANGUAGE BangPatterns #-} import Data.Array.Unboxed import Data.Array.Base(unsafeAt) import Data.Bits import qualified Data.ByteString.Lazy as BSL import Data.Word main = BSL.getContents >>= print . cksum cksum :: BSL.ByteString -> Word32 cksum str = complement $ foldl next crc sizebytes where sizebytes = map fromIntegral $ takeWhile (>0) $ iterate (`shiftR` 8) size (crc, size) = crcAndSize str -- メインループ。必要なworker/wrapperがなされるように正格性を付け加える -- ここで余分な構築子が残ると速度が1/3くらいになる crcAndSize :: BSL.ByteString -> (Word32, Word) crcAndSize str = BSL.foldl' acc (0, 0) str where acc (s, sz) c = (n, sz') where !n = next s c !sz' = sz + 1 -- 1バイトのCRCを計算する。これがcrcAndSizeにインライン化されることが重要 -- さもなくば毎回tableが評価済みかどうかを調べることになる {-# INLINE next #-} next :: Word32 -> Word8 -> Word32 next s c = (s `shiftL` 8) `xor` table `unsafeAt` (fromIntegral $ c `xor` fromIntegral (s `shiftR` 24)) -- unsafeAtを使って境界検査を省く。添字はIntで常に0から数えることに注意 -- fromIntegralは最適化で消えるのでどんどん使う -- 表の生成は一回だけなので遅くても良い table :: UArray Word8 Word32 table = listArray (0, 0xff) $ map f [0..] where f k = iterate g (fromIntegral k `shiftL` 24) !! 8 g k = if k .&. 0x80000000 == 0 then k1 else k1 `xor` 0x4c11db7 where k1 = k `shiftL` 1
GHCのworker/wrapper変換に満足できないなら、相当の変換を自分でやることもできる。その場合、変換は単に引数や戻り値の中身を直接渡すことにとどまらない。かなり広い範囲の最適化が一種のworker/wrapper変換として捉えられるらしい。
+RTS -pによる時間/確保量プロファイル(ja)は、コードのどの部分が時間を使っているかを素早く把握するのに便利。
あまり実行時間の長くないプログラムでは、時間プロファイルのための標本が少なすぎて精度が足りない(実行のたびに結果が変わったり)ことがあるので、-V0.005などとして解像度を増すと良い。
ものすごく頻繁に呼ばれる関数(自分でモナドを定義した場合の(>>=)など)にコスト集約点を設定すると、プロファイル自体のコストが跳ね上がって、プロファイル結果が少なからず撹乱されることがある。-auto-allを使っていて、特定の定義からコスト集約点を外したい場合には、それにINLINEプラグマを指定すると、コスト集約点の自動設定を抑制することができる。
一つの例では、モナド定義からコスト集約点を外したことでプロファイル付き実行時間が40%ほど短縮され、プロファイル結果での各関数の所要時間が複雑に変動した。
GCの大まかな動きを把握するには+RTS -sオプション(ja)を使うと良い。GCのコストを減らすには大きく二つの方向がある。回数を減らすか、一回あたりの時間を減らすか。
GCの回数を減らすには、プログラムの総メモリ確保量を減らせば良い。特に、確保されてすぐ捨てられるような中間データを排除できるとうれしい。マクロにはアルゴリズムの工夫、ミクロにはworker/wrapper変換の活用が効果的。どのコードが大量のメモリ確保を行なっているかは、時間/確保量プロファイルで知ることができる。
回数を減らすもう一つの方法は、単純にメモリ領域を広く取ること。これには+RTS -Aか+RTS -Hを使う。これはメモリが余っている場合にしか使えないが、労せずして劇的な高速化が可能なこともある。
GC一回あたりに掛かる時間について。これはコピーしなければならないデータ量の影響を強く受ける。このため、瞬間瞬間のメモリ使用量を抑えることを考える。データ構造を工夫してサイズを減らす、たとえばStringの代わりにTextを使うことが有効。どんなデータがメモリを圧迫しているかはヒーププロファイルで調べることができる。
メモリ使用量を抑えるためにはもう一つ、データの寿命を短かくするという方向性もある。これには生成したデータをなるべく早く捨てるようにする(よりeagerに)という方法と、必要になる直前までデータを生成しないようにする(よりlazyに)という方法がある。これに関しては、ヒープ上のデータを「使用前/使用中/使用後/使用されない」に分類する経歴プロファイルが役に立つことがある。
最後に、スタックが深くなるとGHCのGCは非常に遅いので、大きなスタックを作るのは多少無理してでも避けた方が良い。特に、多数回の繰り返しを行なうIOコードは末尾再帰にすると良いことが多い。(この問題はGHC 7.2.1で解消されるかもしれない)
newtypeで定義された型は、その中身と全く同じ実行時表現を持つ。最適化の観点から見るとnewtypeとtypeにあまり違いはない。
構築子フィールドの型指定にUNPACKプラグマ(ja)を付けると、その型の中身を直接(たとえばIntの代わりにInt#を)保持することができる。UNPACKプラグマはフィールドの型が単一構築子のデータ型である場合にのみ意味を持つ。
これはオブジェクト一個あたり2ワードの節約になっているほか、構築子を繰り返し外すコストも軽減される。逆にworker/wrapperが働かないなどで、Int#ではなくIntを要求する関数にそのデータを渡す場合は、構築子を新規に確保する必要が発生する。
Reader、State、Contといったモナドの実体は関数のnewtypeである。これらのモナドを使う時は、関数を明示的に定義して引数を引き回すことの略記法として使っているのだから、実行時性能も関数を直接書いた場合に劣らないことが期待される。しかし実際にはそうならないことがある。例として以下の(特に意味のない)コードを考える。
module T where import Control.Monad.Reader import Control.Monad.Trans import Data.Char import System.IO data Env = Env { envSink :: !Handle , envUnused :: !Int } type Proc = ReaderT Env IO display0 :: String -> Proc () display0 name = do sink <- asks envSink lift $ hPutStrLn sink name' where name' = map toLower name
display0は普通のモナドなスタイルで書かれたコードだ。実はこれは次のように関数を直接書くのに比べて効率の悪いコードにコンパイルされる。
display1 :: String -> Env -> IO () display1 name env = hPutStrLn (envSink env) name' where name' = map toLower name
Coreを見てみよう。これはghc-7.0.1 -O2 -ddump-simpl -dsuppress-coercions(castの詳細を省略する)の出力。
T.display0 :: GHC.Base.String -> T.Proc () [GblId, Arity=1, Str=DmdType L, Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=1, Value=True, ConLike=True, Cheap=True, Expandable=True, Guidance=IF_ARGS [0] 16 6}] T.display0 = \ (name_als :: GHC.Base.String) -> let { name'_sX4 [Dmd=Just L] :: [GHC.Types.Char] [LclId, Str=DmdType] name'_sX4 = GHC.Base.map @ GHC.Types.Char @ GHC.Types.Char GHC.Unicode.toLower name_als } in (\ (r_Xut :: T.Env) (eta_B1 :: GHC.Prim.State# GHC.Prim.RealWorld) -> case r_Xut of _ { T.Env ds_drs _ -> case GHC.IO.Handle.Text.hPutStr1 ds_drs name'_sX4 eta_B1 of _ { (# new_s_avl, _ #) -> GHC.IO.Handle.Text.hPutChar1 ds_drs System.IO.hPrint2 new_s_avl } }) `cast` ...
問題は、display0は3引数(name, env, State#トークン)の関数としてコンパイルされて欲しい(display1はそうなる)のに、1引数になっていることである。つまり、name_alsを受け取った後、name'_sX4サンクを確保し、2引数の関数クロージャを返すようになっている。クロージャ確保/未知関数呼び出しのコストに加え、display0がenvについて正格だという情報が使えないのでworker/wrapper変換を阻害する。この問題は関数をラップするモナドを使っている場合いつでも発生し得る。
これは別にGHCの欠陥でこうなる訳ではない。display0を手動で脱糖すると次のようになる。
display0 = \name -> let name' = map toLower name in asks envSink >>= \sink -> (lift $ hPutStrLn sink name')
ここからさらに(>>=)をインライン化すれば、name'の定義が二つのラムダの間に挟まった形が得られる。この間に挟まったname'こそがdisplay0のアリティを1にしている原因である。
name'の定義を内側のラムダの中に移動させればこの問題は解決するが、GHCはそれを行なわない。これは、例えば「d = display0 "Foo"」としてdを百回呼んだ場合に、name'の再計算が毎回行なわれることがないようにするためである。そのような使い方をするつもりはない、あるいは毎回再計算しても構わないとプログラマが考えているとしても、それをGHCに伝える方法はないので、GHCは保守的にならざるを得ない。
この問題に対する一応の回避策は、name'などローカル変数を全てラムダの内側で定義することである。例えば次のようにする。
display2 :: String -> Proc () display2 name = do _ <- return () -- no sharing, please. let name' = map toLower name sink <- asks envSink lift $ hPutStrLn sink name'
これでもまだGHCのお節介によってletが動かされ、アリティが1になる危険がある。-fno-full-lazinessを使ってletの外側への移動を無効化すればだいたい問題ないだろう。このdisplay2をghc-7.0.1 -O2 -fno-full-laziness -ddump-simpl -dsuppress-coercionsでコンパイルする。
T.display21 [InlPrag=INLINE[0]] :: GHC.Base.String -> T.Env -> GHC.Prim.State# GHC.Prim.RealWorld -> (# GHC.Prim.State# GHC.Prim.RealWorld, () #) [GblId, Arity=3, Str=DmdType LU(SU)L, Unf=...省略...] T.display21 = \ (w_sWI :: GHC.Base.String) (w1_sWJ :: T.Env) (w2_sWO :: GHC.Prim.State# GHC.Prim.RealWorld) -> case w1_sWJ of _ { T.Env ww_sWL ww1_sWM -> T.$wa1 w_sWI ww_sWL ww1_sWM w2_sWO } T.display2 :: GHC.Base.String -> T.Proc () [GblId, Arity=3, Str=DmdType LU(SU)L, Unf=...省略...] T.display2 = T.display21 `cast` ...
無事3引数になり、worker/wrapper変換が適用された。
GHCにおけるIOおよびSTの定義は次のようになっている。
newtype IO a = IO (State# RealWorld -> (# State# RealWorld, a #)) newtype ST s a = ST (State# s -> (# State# s, a #))
つまり、IOとSTは関数をラップしたモナドである。にもかかわらず、これらのモナドでは上記の問題は発生しない。これはGHCがState# s型を特別扱いしていることによる。すなわち、引数の型が「State# s」の形であるラムダは、高々一回しか呼ばれないと仮定される(stateハック)。一回しか呼ばれないならばローカル変数の再計算を恐れる必要がないので、letをラムダの内側に移動する最適化が可能になる。
場合によっては、生のバイト列をHaskellから明示的に操作したいことがある。メモリの読み書きにはForeign.PtrおよびForeign.Storableの関数を使う。メモリ確保については、GCで管理されるメモリブロックをGHCランタイムに要求する方法と、mallocやmmapなどGC管理外のメモリ確保手段を使う方法がある。明示的なメモリ操作は全く安全でないので注意。
ランタイムからメモリブロックを得るにはGHC.ExtsのnewByteArray#やnewPinnedByteArray#やnewAlignedPinnedByteArray#を使う。これらはいずれもMutableByteArray#を返すが、newByteArrayが返すものはGCによって移動する可能性があるのに対して、「pinned」と名の付いたものはメモリ中に固定されたバイト配列を返す。MutableByteArray#に対してはGHC.Extsの関数群で読み書きを行なえる。変更不可なByteArray#が欲しい場合はMutableByteArray#に内容を書き込んだ上でunsafeFreezeByteArray#を使う。
固定されたバイト配列からはbyteArrayContents#を使ってAddr#を取り出せるので、ポインタ経由のアクセスが可能。ただしポインタ(Addr#)はGCの関知外なので、ポインタ操作をしている間そのByteArray#が生存していることを保証しなければならない。これにはtouch#を使う。
これは低水準であまりに煩雑なので、実際にはForeign.ForeignPtrを使うと良い。mallocForeignPtrを呼ぶと、固定されたByteArray#をカプセル化したForeignPtrが得られる。withForeignPtrを使ってポインタを取り出せば、生存期間の面倒はライブラリ側で見てくれる。またForeignPtrは同じインタフェースで外部から確保されたメモリを管理することもできる。後始末用の関数(freeとかfcloseとか)を渡しておけば、そのForeignPtrが参照されなくなったときに呼び出してくれる。
他のラッパも紹介しておく。
unsafeCoerceを使った邪悪なテクニックによって速度を稼げる場合が存在する。GHCではnewtypeは元の型と同じ実行時表現を持つので、newtypeのデータ構築子は実質的に恒等関数でコスト0になる
newtype MyInt = MyInt Int f :: Int -> MyInt f x = MyInt x -- f x = x と同じようにコンパイルされる
しかし、例えば[Int]を[MyInt]に変換しようと思うと、実行時表現は同じであるにもかかわらずコストがかかる。
g :: [Int] -> [MyInt] g xs = map MyInt xs -- 実行時にmapしないといけない
これをunsafeCoerceで誤魔化すことができる。
g :: [Int] -> [MyInt] g xs = unsafeCoerce xs
GHCは恐ろしい速度で改善され続けている。GHCのマイナーバージョンアップによって、生成されるコードが5%程度速くなることは珍しくない。
Haskellコードの高速化に挫折したらFFIでCやアセンブリを呼べば良い。(別に挫折していなくてもいいが)
foreign importする関数がHaskellにコールバックしないことが保証されている場合、「foreign import unsafe」を使うと効率の良い呼び出しが生成される。
unsafeで宣言された関数にのみ、固定されていないByteArray#を渡すことができる(ただしおそらくドキュメントされていない機能)。その関数はポインタを受け取るが、それを保存して後で使おうとしてはいけない(GCで動くかもしれないので)。ByteArray#などのプリミティブ型をFFIで使うにはUnliftedFFITypesという拡張が必要である。