Haskellのスペースリークとプロファイリング
目次
プロファイラ
プログラムをチューニングしたい時は、どの関数のどの部分がどれだけのCPU時間やメモリを消費しているのかがわかると便利なことがある。例えば特定の関数がCPU時間の90%を使っている時に、時間をかけて他の部分をチューニングしても、プログラム全体の実行時間の削減への効果は低い。基本的にはCPUやメモリのコストの高い関数から見直していくと良い。
GHCにはプロファイラが付属しているので、CPUの消費時間やメモリの消費量を分析でき、結果をグラフ化することもできる。
7. Profiling — Glasgow Haskell Compiler 8.10.1 User's Guide
1. プロファイリングを行うためには、まず、幾つかオプションを付けて対象のプログラムをコンパイルする。
ghc -prof -fprof-auto -rtsopts -O3 -o prog prog.hs
2. 次に、RTS (ランタイムシステム) の色々なオプションを付けてプログラムを実行すると、実行時のデータを採集してまとめてくれる。
全体的なレポートを採る
./prog +RTS -p
この場合、結果はprog.profに出力される。
前回の記事で比較に使った4段4次のRunge-Kuttaのプログラムで試してみた結果 (一部) は以下のようになった。CPU時間の大半が、結果を出力する際に文字列化して整形する部分に使われてしまっているのがわかる。rk44は計算が軽いので仕方ないかもしれないが、メインの計算部分より重いのは残念な気がする。
Sat Dec 1 10:03 2018 Time and Allocation Profiling Report (Final)
rk44 +RTS -p -RTS
total time = 0.25 secs (248 ticks @ 1000 us, 1 processor)
total alloc = 459,835,272 bytes (excludes profiling overheads)
COST CENTRE MODULE SRC %time %alloc
toString Main rk44.hs:28:1-50 72.6 83.0
writeLists Main rk44.hs:41:1-54 9.3 9.3
rk44.kf Main rk44.hs:56:9-79 5.2 4.8
rk44.ss Main rk44.hs:57:9-44 3.6 1.0
rk44.kf.\ Main rk44.hs:56:58-67 2.4 0.3
lorentz Main rk44.hs:(174,1)-(179,49) 2.0 0.1
rk44 Main rk44.hs:(49,1)-(58,66) 2.0 0.6
individual inherited
COST CENTRE MODULE SRC no. entries %time %alloc %time %alloc
MAIN MAIN <built-in> 113 0 0.0 0.0 100.0 100.0
CAF Main <entire-module> 225 0 0.0 0.0 95.6 99.9
main Main rk44.hs:319:1-19 226 1 0.0 0.0 95.6 99.9
lorentz Main rk44.hs:(174,1)-(179,49) 227 1 1.6 0.1 95.6 99.9
lorentz.file Main rk44.hs:175:7-26 230 1 0.0 0.0 0.0 0.0
lorentz.fps Main rk44.hs:176:7-64 233 1 0.4 0.0 16.1 7.5
l_dxdt Main rk44.hs:170:1-35 248 39996 0.0 0.0 0.0 0.0
メモリ消費を詳しく調べる
./prog +RTS -[h,hm,hd,hy,hr,hb]
結果はprog.profやprog.hpに出力される。グラフにしたい場合は結果をpsに変換するツールもある。
hp2ps -c prog.hp
pdfにする場合はさらに変換する。
ps2pdf prog.ps prog.pdf
rk44で試してみた結果は以下のようになった。
-h コストセンター
-hm モジュール
-hd コンストラクタ
-hy 型
-hr リテイナー
誰がオブジェクトを保持しているのかを説明してくれる。あるオブジェクトに到達できるポインタを直接持っているオブジェクト。
7. Profiling — Glasgow Haskell Compiler 8.10.1 User's Guide
-hb 履歴
- lag : 生成後、使用待ちの状態
- use : 最初の使用後で、最後の使用前の状態
- drag : 最後の使用後で、最後の参照が消える前の状態
- void : 1度も使用されなかったオブジェクト
スペースリークなどへの対応
GHCはガベージコレクタを持っているので、メモリについて意識する必要はあまりないが、プログラムによってはサンク (遅延評価による未評価の値) が蓄積してスペースリークと呼ばれるメモリの浪費が起きることがある。メモリが破壊されることはまずないと思うが、メモリリークと同様の現象は起きてしまう。また、状況によっては (パフォーマンスを落とさずに) メモリの消費量を一定以下に抑えたいという場合もあるかもしれない。そんな時はプロファイラを使ってどこでサンクが蓄積されているのかを調べた上で、プログラムの構成を見直したり、単に、部分的にあるいは全体的に正格評価すれば良い場合もある。
末尾再帰への書き換え
関数の再帰呼び出し後に何らかの処理が残されているような再帰関数で、コンパイラの最適化が効かなかった時、サンクが蓄積されてしまうことがある。再帰後の処理結果を引数に織り込むなどして、再帰呼び出し後に処理が残らない形に書き変えると、再帰はループに置き換え可能なので、スペースリークを回避できるかもしれない。
-- 末尾再帰になっていない例 (これくらいなら最適化が効くかもしれない) fact :: Integer -> Integer fact n | n < 2 = 0 | otherwise = n * fact (n - 1) -- 末尾再帰に書き換えた例 factT :: Integer -> Integer factT n = f n 1 where f m t | m < 2 = t | otherwise = f (m - 1) (m * t)
実際のリスト生成の回避
計算の途中でリストが生成されていると考えるとわかりやすい処理があり、コード上もそのように表現されたとしても、実際にはリスト生成を必要としない場合がある。より抽象的なリスト操作関数を使ったりして気をつけると、コンパイラが最適化して不必要なリスト生成を回避してくれることがある。
-- いずれも実際にはリストは生成されないはず sum [1..1000000] foldl1 (*) [1..10000] -- リスト生成させる (product . reverse) [1..10000]
正格評価版$!とseq
関数適用演算子$には正格評価版$!があり、引数を弱頭部正規形 (WHNF) まで評価してから関数適用する。また、a `seq` bのようにseq関数を適用すると、aを評価してからbを返す。言語標準の機能。
f $! p q r a `seq` b `seq` (a, b)
正格フィールド
データ型を定義する時、値コンストラクタのフィールドの型名の前に!をつけると、引数が評価されてから値がつくられるようになる。こちらも言語標準の機能。
data StrictData = StrictData !Integer !String
BangPatterns
また、BangPatternsプラグマを指定すると、任意の変数束縛時に、変数名の前に!を付けることで個々の変数を評価することができるようになる。
9.1. Language options — Glasgow Haskell Compiler 8.10.1 User's Guide
StrictとStrictData
GHC8.0.2以降では、StrictDataプラグマを指定すると、値コンストラクタの引数は自動的に!が付けられた状態になる。また、Strictプラグマではこれに加えて、関数やwhere、letなどの変数束縛時にもデフォルトで評価が行われるようになる。逆に遅延評価したい場合に変数の前に~を付ける。
{-# LANGUAGE Strict #-} {-# LANGUAGE StrictData #-}
同様の効果は-XStrictData、-XStrictフラグでも得られる。
9.1. Language options — Glasgow Haskell Compiler 8.10.1 User's Guide
