Haskellで実用アプリを作ってみるときれいに気持ち良く作れ、修正も型システムのおかげで安心して出来ます。しかし、出来たものはたとえば Ruby とApolloで作ったものがカラカラと軽く回るのに対して、ずっしりと重いのです。
「本物のプログラマはHaskellを使う/第9回 Haskellはなぜ遅いと思われているのか 」に遅延評価が遅くなる場合の例と原因・プロファイルを取り方・対策が掲載されていましたので写経してみました。
- Lazy2.hs
main = print $ sum [0..1000000]
sum は foldl (+) 0 として定義され、foldlが再帰によって定義されています。
sum :: (Num a) => [a] -> a sum = foldl (+) 0 foldl :: (a -> b -> a) -> a -> [b] -> a foldl f z [] = z foldl f z (x:xs) = foldl f (f z x) xs
Haskellは非正格評価ですから値を計算しないまま展開していきますから、どんどんと式が大きくなっていき、スペースを圧迫していきます。
sum [0..1000000] => foldl (+) 0 [1..1000000] => foldl (+) (0+1) [2..1000000] => foldl (+) ((0+1)+2) [3..1000000] . . . => foldl (+) ((… ((0+1)+2)+ … )+ 1000000) [] => ((… ((0+1)+2)+ … )+ 1000000) => 500000500000
プロファイラを使えばその様子が見ることが出来ます。
-- $ ghc --make -prof -auto-all Lazy2.hs [1 of 1] Compiling Main ( Lazy2.hs, Lazy2.o ) Linking Lazy2 ... $ ./Lazy2 +RTS -K100M -hc 500000500000 $ hp2ps Lazy2.hp $ gv Lazy2.ps&
$ ghc Lazy2.hs -rtsopts -prof -auto-all -caf-all [1 of 1] Compiling Main ( Lazy2.hs, Lazy2.o ) Linking Lazy2 ... $ ./Lazy2 +RTS -hc -K100M 500000500000
foldl の代わりに foldl'を使えばスペース・リークを防げます。
- Lazy3.hs
import Data.List main = print $ sum' [0..1000000] sum' :: (Num a) => [a] -> a sum' = foldl' (+) 0
foldl'のソースは以下。
-- | A strict version of 'foldl'. foldl' :: (a -> b -> a) -> a -> [b] -> a foldl' f a [] = a foldl' f a (x:xs) = let a' = f a x in a' `seq` foldl' f a' xs
foldl' は let を使っていて分かりにくいので、 where を使って書き直した myFoldl を以下に示します。
myFoldl :: (a -> b -> a) -> a -> [b] -> a myFoldl f a [] = a myFoldl f a (x:xs) = a' `seq` myFoldl f a' xs where a' = f a x
末尾再帰でスペース・リークになる例
- sum.hs
main = print $ summ 1000000 0 summ 0 acc = acc summ n acc = summ (n-1) (acc+n)
seq 関数を使い末尾再帰でのスペース・リークを回避する。
- sum2.hs
main = print $ summ 1000000 0 summ 0 acc = acc summ n acc = cnt `seq` acc' `seq` summ cnt acc' where cnt = (n-1) acc' = (acc+n)
特定の式のコストを見たいときは、ソースコード中でコスト集約点を指定（Set Cost Center）する
http://d.hatena.ne.jp/rst76/20100302/1267543361
hoge = {-# SCC "hoge" #-} <expression>
- Stricter Haskell：! によりサンクを壊す方法が記述されています。
-- Stricter Haskell http://d.hatena.ne.jp/mkotha/20110509/1304947182 main = print $ summ 1000000 0 summ 0 acc = acc summ n acc = summ cnt acc' where cnt = (n-1) acc' = (acc+n) $ ./sum Stack space overflow: current size 8388608 bytes. Use `+RTS -Ksize -RTS' to increase it.
main = print $ summ 1000000 0 summ 0 acc = acc summ n acc = summ cnt acc' where !cnt = (n-1) !acc' = (acc+n) $ ./sum 500000500000
