スペースリークの傾向とその対策を見ていきます。
ここでは3つのパターンを取り上げます。他のパターンがまだ見つかりそうな気がしているので、気がついた方は是非記事を書いてください。
注意事項
- 「サンクを積む」という表現を多用していますが、「関数適用によってサンクを大きくする」と言った意味合いで使っています。多分に誤用なので外では使わない方がいいと思います（と思ったらそういう表現を使うこともあるそうです）
- 以前の記事もそうですが、「簡約」は「評価」に統一してます
基本方針
追記:
- 正格評価
- 無限ループをしない
- 必要ない式は評価しない
- 遅延評価
- 無限ループをしない
- 必要ある式はサンクを積まない
サンクの必要とする空間と、潰した後の空間
サンクは必ずしも悪いものではありません。非常に大きなサンクの場合とそれを潰した場合に、どちらがメモリを消費するかは一概には言えないのです。
少し違いますが、わかりやすく例えるなら無限リストのようなイメージです。
infinit_list :: [Integer]
infinit_list = [1..]
無限リストは全て評価してしまってはメモリに乗りません。評価しない方がメモリを消費しないのです。
メモリの消費という点から考えると、どこかに合理的な線が引かれるはずです。サンクで保持した方が良いか、サンクを潰した方が良いか。今回はスペースリークに焦点を当てているためサンクは潰す方が良いように見えるかもしれませんが（まあ実用上も大抵そうかもしれませんが）、それはサンクの一面であって全てではないのです。
と注意書きをしたところでサンクを潰していきましょう。
TCOからのaccumulated variableに積もるサンク
スペースリークは再帰関数で発生しやすいものです。
再帰関数の最適化を行う場合、末尾呼び出し最適化(Tail Call Optimization; TCO)が行われるようにプログラムを変更することはよくあることです。
factorial_notco :: Integer -> Integer
factorial_notco 0 = 1
factorial_notco n = n * factorial_notco (n - 1)
そもそもTCOしない関数は再帰呼び出し回数が増えるにつれてスタックを消費してしまいます。それはスペースリーク以前の問題です。
そして末尾呼び出し再帰を行う際に、accmulated variableを引数に追加することもよく行われることでしょう。そのaccumulated variableはその目的上、最後まで関数適用がされ続けて（サンクが追加されつづけて！）、最後にそのサンクが返されます。
factorial_tco_leak :: Integer -> Integer
factorial_tco_leak n = go 1 n
where
go acc 0 = 1
go acc n = go (acc * n) (n - 1)
再帰のたびに変数accにサンクが積まれることがわかるでしょうか。
そのサンクの状態は以下のようになっているはずです
(...(((1 * n) * n') * n'')...)
これがスペースリークです。TCOによってスタックの消費はなくなりましたが、acc変数にはサンクが積み重ね続け、ヒープが消費されます。そして今回の関数の場合、このサンクは全て消費することが初めから分かっているので、サンクを積まずに直ぐに潰してしまって構いません。
factorial_tco_noleak :: Integer -> Integer
factorial_tco_noleak n = go 1 n
where
go !acc 0 = 1
go !acc n = go (acc * n) (n - 1)
追加したBangPatternsによって再帰のたびにaccのサンクが潰されるようになり、スペースリークは解消されました。
TCOの際にはスペースリークも気をつけましょう。
foldlとスペースリーク
もう一つ例を見ておきます。
スペースリークする代表格といえばfoldlです。嘘です現在は（少なくともGHC-7.10時点では）もう大丈夫のようです。以前はfoldlを迂闊に使うと簡単にリークするという問題があるため、代わりにfoldl'を使わなければなりませんでした。
foldlを単純に定義すれば以下のような感じでしょうか。
foldl_leak :: (b -> a -> b) -> b -> [a] -> b
foldl_leak f acc (a:as) = foldl_leak f (f acc a) as
foldl_leak _ acc _ = acc
この定義ではaccのところにサンクが追加され続け、最後に非常に大きなサンクが返されます。
このaccを随時評価して構わないかどうかは畳込み関数によりますが、問題ない場合はBangPatternを追加することで解消します。
foldl_noleak :: (b -> a -> b) -> b -> [a] -> b
foldl_noleak f !acc (a:as) = foldl_leak f (f acc a) as
foldl_noleak _ !acc _ = acc
ADTの型パラメータに積もるサンク
型パラメータに対応する式にはサンクが積もりやすいものです。型パラメータを持つADT(Algebraic Data Type)はしばしばサンクが積もり、スペースリークの原因になります。
Listを定義してみます。
data List a = Nil | Cons a (List a)
caseでのパターンマッチはコンストラクタまでしか評価されないのでした。つまり、コンストラクタの後ろにある式にはサンクが残ったままになりやすいものです。ここでいうとCons a (List a)のConsの直後のaに相当する式です。
Listをparametricに操作する関数は、基本的にListの中には触らないため、Listの個々の要素にはサンクがたまりがちです。zipWithを見てみます。
zipWith_leak :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith_leak f (a:as) (b:bs) = f a b : zipWith f as bs
zipWith_leak _ _ _ = []
この関数は二つのリスト([a]と[b])を一つのリストにジッパーのようにzipする関数ですが、parametricな関数であるため、リストの中身には触れていません。
zipWith_noleak :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith_noleak f (a:as) (b:bs) =
let x = f a b
in x `seq` (x : zipWith f as bs)
zipWith_noleak _ _ _ = []
この関数は返り値にはListというADTを返しますが、そのADTが「WHNFまで評価されるたび」にseqが発動し、サンクを潰していきます。
この手法はもちろん、List以外のADTにも用いることが出来ます。
他の対処方としてはdata定義の際にBangをつける方法です。
data List a = Nil | Cons !a (List a)
こうすることによってコンストラクタでの格納時にWHNFまで展開されます。
これはPatternではないのでBangPatternsとは言いません（名前忘れました）。
パラメトリックな型を持つADTを返すような関数は、返り値に大抵サンクが乗ることになるでしょう。それを潰すかどうかは適宜判断してください。
偏るアクションによって積もるサンク
純粋関数によってCRUD(Create-Read-Update-Delete)が可能なデータを考えましょう。
例えばData.Map.Strictです。これはStrictと名前についているので正格に「なにか」やってくれることが期待出来ます。
import Data.Map.Strict as M
biased_actions_leak :: M.Map Int String -> IO ()
biased_actions_leak map = do
hSetBuffering stdin NoBuffering
hSetBuffering stdout NoBuffering
go map
where
go map = do
putStr "Enter [urq]: "
char <- getChar
putStr "\n"
case char of
'u' -> do
let map' = M.update (\_ -> Just "heyhey!") 42 map
go map'
'r' -> do
case M.lookup 42 map of
Just x -> putStrLn $ "Found a key: " ++ x
Nothing -> putStrLn "No key (Thunk collapsed)"
go map
'q' -> return ()
_ -> go map
main = biased_actions_leak (M.singleton 42 "hey")
このプログラムを走らせ、標準入力で'u'を押し続けてみます。するとその度にサンクが積もります。'r'を押すと、その時にlookupが走り、その際にサンクが潰されます。
このプログラムが特徴的なのは、IOによってサンクが乗るかどうかが決定されることです。非常に偏った入力に対してスペースリークが発生するというプログラムなのです。
'u'の間に'r'がそこそこの頻度で発生している場合は問題が見えません。しかしプログラムはどんなに極端な入力であっても正しく動くべきです。その際に極端に大きな値や極端な偏りを考えてみることは有用なメソッドです。
対処法は単純で、サンクをupdateごとに潰せば十分です。
import Data.Map.Strict as M
biased_actions_leak :: M.Map Int String -> IO ()
biased_actions_leak map = do
hSetBuffering stdin NoBuffering
hSetBuffering stdout NoBuffering
go map
where
go map = do
putStr "Enter [urq]: "
char <- getChar
putStr "\n"
case char of
'u' -> do
let map' = M.update (\_ -> Just "heyhey!") 42 map
go $! map'
'r' -> do
case M.lookup 42 map of
Just x -> putStrLn $ "Found a key: " ++ x
Nothing -> putStrLn "No key (Thunk collapsed)"
go map
'q' -> return ()
_ -> go map
main = biased_actions_leak (M.singleton 42 "hey")
$!を追加しました。これは関数適用演算子の一種で、関数を呼び出す前に引数をWHNFまで評価します。
これで再帰する前にupdateが評価され、サンクが潰されることになります。
Data.Map.StrictのStrictとはなんだったのでしょうか。
Haddockに書いてあります。
http://hackage.haskell.org/package/containers-0.5.6.3/docs/Data-Map-Strict.html
- Key arguments are evaluated to WHNF;
- Keys and values are evaluated to WHNF before they are stored in the map.
ということで、別にupdate関数自体がstrictに適用されるわけではないのです。それはライブラリの出来る範囲を超えます。なので、以下のようにupdateの塊の様なサンクは発生してしまうのです:
(update f key (update f' key' (...(update f'' key'' map)...)))
Stateモナドのスペースリーク
上記は非常にわざとらしい例でしたが、もう少し有りうる例を載せておきます。Stateモナドです。
increment :: Integer -> StateT Integer IO ()
increment n = do
state <- get
put $ state + n
getしてその状態に対してサンクを載せてputするパターンです。
これだけでスペースリークが発生します。この場合はincrementが非常に偏って呼び出された場合に大きなスペースリークが発生します。
Stateモナドで状態はparametricに扱われており、つまりはサンクが乗りやすいのです。getした値にはサンクが乗っているかもしれないし、putした値にもサンクが乗るかもしれません。単純にputして状態を置き換えるだけならサンクは乗りませんが、getしてから更新した値をputする、というパターンはサンクが乗ることになります。
increment :: Integer -> StateT Integer IO ()
increment n = do
!state <- get
put $! state + n
getする際につぶすか、putする際に潰すかすると良いでしょう。
もしくはmodify'を用います
increment :: Integer -> StateT Integer IO ()
increment n = do
modify' $ \state -> state + n
おわりに
スペースリークを潰すためにプログラムの詳細を追うことは辛いものです。スペースリークの傾向を掴み、プログラムの動作概要から発見を出来るようになると実戦上楽になりそうですね。
もし上記にないパターンを発見した方は是非記事を書いてみてください。
上記パターンでも実際に発生した例を共有することは意義があると思います。
まあなんか包括的に考えられなくもなさそうな気はするんですよね。
ところで
パラメトリックな型を持つ値をseqやらBangやらでつぶしてしまっています...
そんなことをせずに評価順序をコントロールする方法はあるのでしょうか。