2004-12-14 [長年日記]
λ. HaskellでScheme処理系を実装 (3)
末尾再帰で10000!を計算すると、とりあえずGuileと同じくらいのスピードは出てるのだけど、fib(30)を素朴な再帰で計算したらやたら遅かった。プロファイルをとってみたら total alloc が 13GBほど。そりゃ遅い気がする。
こんなにメモリを消費している理由を確認するためにVMのコンパイル結果を-ddump-stgでダンプしてみると、予想通り命令一ステップ実行するごとにletが……。最適化でアンパックされると思ってた引数/返り値のデータ構造を毎回ヒープに割り付けてるよ、うわーん。
色々と試してみると、GHC の worker wrapper transformation は、返り値の型がネストしたデータ構造だった場合にトップレベルしかアンパックしてくれないっぽいな。引数の方はネストしててもアンパックしてくれるから、これは CPR analyser の制限なのかな? あと、正格性解析によって引数がアンパッカブルと判定される条件もいまいち良く分かってないんだよなぁ。
一応 single threaded な使い方はしてるはずだから、アンパックしてくれなくても single threadedness を検出して破壊的に更新してくれるってのでもいいんだけど……それも叶わないし、切ないね。Haskellにも linear type があればいいのにと初めて本気で思ったよ。
とか、ぐだぐた考えながら、自分でアンパックしたコードを書いてプロファイルを取ってみる。total alloc は 13GB から 4GB まで減り、実行時間が110秒から70秒に減った。また実行時間にしめるGC時間は20%から14%に減った。むー、思ったより速くならなかったな。まあスタックとかもリストで表現してるし、他にも色々と富豪なことしてるから、こんなものか。さて、どうしようかな。
λ. Constructed Product Result Analysis for Haskell, Clem Baker-Finch, Kevin Glynn, Simon Peyton Jones
.
λ. GHC の worker wrapper transformation への不満
(2005-09-11 追記) 上で「GHC の worker wrapper transformation は、返り値の型がネストしたデータ構造だった場合にトップレベルしかアンパックしてくれないっぽい」と書いたことについての簡単な具体例。GHCの worker wrapper transformation だと、内側のタプルがすぐ消費される場合でもヒープに割り当てられてしまう。
- 元のコード
-
test :: Int -> (Int, (Int,Int)) test x = (x,(x+1,x+2)) - GHC の worker wrapper transformation
-
{-# INLINE test #-} test :: Int -> (Int, (Int,Int)) test x = case wtest x of (# a, b #) -> (a, b) wtest :: Int -> (# Int, (Int,Int) #) wtest x = (# x, (x+1, x+2) #) - 期待する worker wrapper transformation
-
{-# INLINE test #-} test :: Int -> (Int, (Int,Int)) test x = case wtest x of (# a, b, c #) -> (a, (b, c)) wtest :: Int -> (# Int, Int, Int #) wtest x = (# x, x+1, x+2 #)
(2005-09-16 追記) ちなみに、GHCではIO型は「newtype IO a = IO (State# RealWorld -> (# State# RealWorld, a #))」と定義されているので、IO型を返すような関数は同じ制約を受ける。IO型を利用したコードが遅くなる一つの理由がこれだと思う。
- 元のコード
test2 :: Int -> IO (Int,Int) test2 x = return (x,x+1)- 期待する worker-wrapper transformation
{-# INLINE test2 #-} test2 :: Int -> IO (Int,Int) test2 x = IO (\s -> case wtest2 x s of (# s, a, b #) -> (# s, (a,b) #)) wtest2 :: Int -> State# RealWorld -> (# State# RealWorld, Int, Int #) wtest2 x s = (# s, x, x+1 #)
【2006-04-28追記】 GHC-6.4.1の compiler/cprAnalysis/CprAnalyse.lhs には以下のように書いてあった。うーむ。「enabling this would lose laziness」が何故なのか良く分からない。
The analysis here detects nested CPR information. For example, if a function returns a constructed pair, the first element of which is a constructed int, then the analysis will detect nested CPR information for the int as well. Unfortunately, the current transformations can't take advantage of the nested CPR information. They have (broken now, I think) code which will flatten out nested CPR components and rebuild them in the wrapper, but enabling this would lose laziness. It is possible to make use of the nested info: if we knew that a caller was strict in that position then we could create a specialized version of the function which flattened/reconstructed that position.
It is not known whether this optimisation would be worthwhile.
So we generate and carry round nested CPR information, but before using this info to guide the creation of workers and wrappers we map all components of a CPRInfo to NoCprInfo.
