LoginSignup
24
8

More than 3 years have passed since last update.

HaskellAdvent Calendar 2019Day 10
@ruicc(Ruichi Kos)

サンクの構造を見る

Last updated at Posted at 2019-12-09

GHCでは評価戦略がデフォルトで遅延評価ですが、このために引数に関数を適用しただけでは評価自体は行われずに、サンクとして扱われます（ここではinliningやstrictness-analysis等の最適化は考慮しません）。
サンクとは評価を進めるための情報は揃っているけども(遅延評価のために)評価を進めないままに扱うための構造です。GHCでのサンクの実態は引数のないクロージャです。
そしてこのサンクの中身はHaskell上から確認する手段はありません...

と思っていたのですが、最近1は中身を確認することができる様ですね。

ghc-heap-viewはサンクを含むHeap上の構造を確認するためのライブラリです。

前提条件

ここでは以下の環境で動作確認を行っています。

  • MacOS
  • ghc-8.6
  • ghc-heap-view-0.6.0(ghc-8.8の場合は0.6.1)

インストール方法

ghc-heap-view.cabalのBuild-typeがCustomなのでSetup.hsを使う。

-- 適当にpackage取ってくる(git cloneとかでもいい)
$ stack unpack ghc-heap-view-0.6.0

$ cd ghc-heap-view-0.6.0/

$ runhaskell Setup.hs configure --user
Configuring ghc-heap-view-0.6.0...

$ runhaskell Setup.hs build
Preprocessing library for ghc-heap-view-0.6.0..
Building library for ghc-heap-view-0.6.0..
[1 of 4] Compiling GHC.Disassembler ( src/GHC/Disassembler.hs, dist/build/GHC/Disassembler.o )
[2 of 4] Compiling GHC.HeapView     ( src/GHC/HeapView.hs, dist/build/GHC/HeapView.o )
[3 of 4] Compiling GHC.AssertNF     ( src/GHC/AssertNF.hs, dist/build/GHC/AssertNF.o )
[4 of 4] Compiling GHC.HeapView.Debug ( src/GHC/HeapView/Debug.hs, dist/build/GHC/HeapView/Debug.o )

$ runhaskell Setup.hs install
Installing library in /Users/<name>/.cabal/lib/x86_64-osx-ghc-8.6.5/ghc-heap-view-0.6.0-4CmwrMCsTo5KuK9EIxn4T9
Registering library for ghc-heap-view-0.6.0..
To enable the GHCi integration, you have to load a ghci file in GHCi. To do this automatically when GHCi is started run:
echo ":script /Users/<name>/.cabal/share/x86_64-osx-ghc-8.6.5/ghc-heap-view-0.6.0/ghci" >> ~/.ghci

-- なんか言われたので実行して~/.ghciに追加する
$ echo ":script /Users/<name>/.cabal/share/x86_64-osx-ghc-8.6.5/ghc-heap-view-0.6.0/ghci" >> ~/.ghci

これによりghci上で:printHeapコマンドが使える様になります。やったぜ。

使い方

準備。とりあえずTypeApplication, BangPatternsを有効にし、Control.Exception(evaluate用)、Control.DeepSeq(deepseq, force)をimportしておきます。~/.ghciに書いておいてもいいでしょう。

$ ghci
GHCi, version 8.6.5: http://www.haskell.org/ghc/  :? for help
Loaded GHCi configuration from /Users/<name>/.ghci
Prelude> :set -XTypeApplications
Prelude> :set -XBangPatterns
Prelude> import Control.Exception as E
Prelude E> import Control.DeepSeq as DS

mapを使って単純なサンクを作ります。
mは関数適用しただけなのでまだサンクの状態。実行されません。

Prelude E DS> let m = map succ [1..10]

:printHeapでmを覗いてみます。

Prelude E DS> :printHeap m
let x1 = toArray (0 words)
    f1 = _fun{SRT_5 t1 t2 t3 t4 (SRT_2 f2 f4)}
    t1 = _thunk()
    t2 = _thunk()
    t3 = _thunk()
    t4 = _thunk()
    f2 = _fun{SRT_1 (SRT_2 t5 f3)}
    t5 = _thunk()
    f3 = _fun{SRT_4 t1 t2 t3 t5}
    f4 = _fun{SRT_2 t5 f3}
    f5 = _fun{SRT_1 (SRT_2 (SRT_2 f2 f4) (SRT_5 t1 t2 t3 f4 t4))}
    f6 = _fun
    f7 = _fun
in (_bco ([ (C:Num f1 f5 _fun{SRT_3 f6 _fun{_fun,_fun{t1,t2,t3}} (SRT_2 _fun{t1,_fun{t1,t2,t3}} _fun{t1,_fun})} f6 _fun _fun _fun), (C:Enum _fun{f1} _fun{f5} _fun _fun _fun _fun{_fun{f1},SRT_1 f5} _fun _fun{f5,_fun{SRT_1 (SRT_1 f1)}}), (_bco ([ (_bco ([ (_bco ([ f7 ])), (_bco ([ f7 ])), _fun ])), (_bco ([ _fun ])), _fun ]))() ]))()

let...inがずらずら出てきました。Heap上の構造は一部をsharingしていたりcyclicになっていることもあるグラフ構造なのでlet...inという表現をとっているようです。

_fun はFunClosure, _thunkはThunkClosure、とClosure表現と対応しているようです。
また、_bcoはByte-Code Objectで、ghci上で扱われるコード片を意味しています。

thunkは_thunkとしか表示されていないし、functionも_fun +αとしか表示されてなかったりとまあ分かりにくいですが、ともかく内部構造が表示されます。
この出力から何が分かるのか？というと難しいですが、ポイントはまだ評価前の構造だということです。inの直後が_bco...となっていることから、まだ評価されていない状態なのだと分かればとりあえず良いでしょう。

では次にevaluateでmを評価し、m'と名前をつけます。
m'はevaluateによってWHNF(Weak Head Normal Form)になります。つまり頭にコンストラクタが露出した状態になるはずです。WHNFの構造は型見ればわかる訳ですが、m'の型は[Integer]なので、リストの頭のcons(:)が見えている状態のはずです。
m'を:printHeapで確認してみます。

Prelude E DS> m' <- evaluate m
Prelude E DS> :printHeap m'
let t1 = (_bco ([ _fun ])) (C:Enum _fun{f1} _fun{f5} _fun _fun _fun _fun{_fun{f1},SRT_1 f5} _fun _fun{f5,_fun{SRT_1 (SRT_1 f1)}})
    f1 = _fun{SRT_5 t2 t3 t4 t5 (SRT_2 f2 f4)}
    t2 = _thunk()
    t3 = _thunk()
    t4 = _thunk()
    t5 = _thunk()
    f2 = _fun{SRT_1 (SRT_2 t6 f3)}
    t6 = _thunk()
    f3 = _fun{SRT_4 t2 t3 t4 t6}
    f4 = _fun{SRT_2 t6 f3}
    f5 = _fun{SRT_1 (SRT_2 (SRT_2 f2 f4) (SRT_5 t2 t3 t4 f4 t5))}
    x1 = S# 1
in _thunk t1 x1 : _thunk t1 (_thunk _fun{S# 10} x1)

またlet...inがずらずら並んでいますが、inの後を見ると、cons(:)が露出していることが確認できます。そしてリストのそれぞれの要素はthunkのままであることも確認できます。
想定通りWHNFであることが確認できる訳です！

次にforce(x `deepseq` x)を使って全ての要素を評価し、m''と名前をつけます。リストの要素のthunkが全て評価されるはずです。

Prelude E DS> !m'' <- return $ force m
Prelude E DS> :printHeap m''
S# 2 : S# 3 : S# 4 : S# 5 : S# 6 : S# 7 : S# 8 : S# 9 : S# 10 : S# 11 : [] 4493884136
Prelude E DS> m
[2,3,4,5,6,7,8,9,10,11]

S#はIntegerの値コンストラクタです。リストの中身が全て評価されていることが確認できます。

関数適用を多量に重ねる例

もう一つ例を。Mapのupdate関数を何度も適用してサンクが積もる様子を確認してみます。
簡単なMapを作り(m)、update関数(up)を用意しておきます。

$ ghci
Prelude E D> import Data.Map
Prelude E D Data.Map> fromList [("hey", 1), ("hoy", 2)]
fromList [("hey",1),("hoy",2)]
Prelude E D Data.Map> let m = fromList [("hey", 1), ("hoy", 2)]
Prelude E D Data.Map> :printHeap m
let x1 = toArray (0 words)
    t1 = _thunk()
    t2 = _thunk()
    t3 = _thunk()
    t4 = _thunk()
    f1 = _fun{SRT_1 (SRT_2 t5 f2)}
    t5 = _thunk()
    f2 = _fun{SRT_4 t1 t2 t3 t5}
    f3 = _fun{SRT_2 t5 f2}
    f4 = _fun
    f5 = _fun
    f6 = _fun
    f7 = _fun
    f8 = _fun
    f9 = _fun
    f10 = _fun{f11,f9}
    f11 = _fun
    f12 = _fun
in (_bco ([ (C:Num _fun{SRT_5 t1 t2 t3 t4 (SRT_2 f1 f3)} _fun{SRT_1 (SRT_2 (SRT_2 f1 f3) (SRT_5 t1 t2 t3 f3 t4))} _fun{SRT_3 f4 _fun{_fun,_fun{t1,t2,t3}} (SRT_2 _fun{t1,_fun{t1,t2,t3}} _fun{t1,_fun})} f4 _fun _fun _fun), (_bco ([ (_bco ([ f5 ])), (_bco ([ f6 ])), ([] 4435094248), (_bco ([ f5 ])), (_bco ([ f6 ])), (_bco ([ (C:Ord (C:Eq _fun _fun) _fun _fun _fun _fun _fun _fun _fun), _fun ])), _fun{SRT_1 (SRT_1 (SRT_1 (SRT_1 (SRT_1 (SRT_1 (SRT_1 (SRT_1 (SRT_1 (SRT_1 (SRT_1 (SRT_1 (SRT_2 _fun (SRT_2 _fun{SRT_2 f7 (SRT_5 f8 f9 f10 f12 _fun{f8,f9,_fun{f7,f8},f10,f12})} f11)))))))))))))} ]))() ]))()
Prelude E D Data.Map> let up = update Just "hey"

関数fをn回重ねて大きいthunkを作る関数、accThunkを定義します。

Prelude E D Data.Map> let accThunk n f x = if n == 1 then return (f x) else accThunk (n-1) f (f x)

40回くらいupdateを重ねて:printHeapで確認してみます。

Prelude E D Data.Map> m' <- accThunk 40 up m
Prelude E D Data.Map> :printHeap m'
let x1 = toArray (0 words)
    f1 = _fun (C:Ord (_thunk x2) _fun{x2} _fun{x2} _fun{x2} _fun{x2} _fun{x2} _fun{x2} _fun{x2}) _fun (C# 'h' : C# 'e' : C# 'y' : x3)
    x2 = C:Ord (C:Eq _fun _fun) _fun _fun _fun _fun _fun _fun _fun
    x3 = [] 4435094248
    t1 = _bco ([  ])
    t2 = _thunk()
    t3 = _thunk()
    t4 = _thunk()
    t5 = _thunk()
    f2 = _fun{SRT_1 (SRT_2 t6 f3)}
    t6 = _thunk()
    f3 = _fun{SRT_4 t2 t3 t4 t6}
    f4 = _fun{SRT_2 t6 f3}
    f5 = _fun
    f6 = _fun
    f7 = _fun
    f8 = _fun
    f9 = _fun
    f10 = _fun
    f11 = _fun{f12,f10}
    f12 = _fun
    f13 = _fun
in (_bco ([  ])) f1 (t1 f1 (t1 f1 (t1 f1 (t1 f1 (t1 f1 (t1 f1 (t1 f1 (t1 f1 (t1 f1 (t1 f1 (t1 f1 (t1 f1 (t1 f1 (t1 f1 (t1 f1 (t1 f1 (t1 f1 (t1 f1 (t1 f1 (t1 f1 (t1 f1 (t1 f1 (t1 f1 (t1 f1 (t1 f1 (t1 f1 (t1 f1 (t1 f1 (t1 f1 (t1 f1 (t1 f1 (t1 f1 (t1 f1 (t1 f1 (t1 f1 (t1 f1 (t1 f1 (t1 f1 (t1 f1 (_bco ([ (C:Num _fun{SRT_5 t2 t3 t4 t5 (SRT_2 f2 f4)} _fun{SRT_1 (SRT_2 (SRT_2 f2 f4) (SRT_5 t2 t3 t4 f4 t5))} _fun{SRT_3 f5 _fun{_fun,_fun{t2,t3,t4}} (SRT_2 _fun{t2,_fun{t2,t3,t4}} _fun{t2,_fun})} f5 _fun _fun _fun), (_bco ([ (_bco ([ f6 ])), (_bco ([ f7 ])), x3, (_bco ([ f6 ])), (_bco ([ f7 ])), (_bco ([ x2, _fun ])), _fun{SRT_1 (SRT_1 (SRT_1 (SRT_1 (SRT_1 (SRT_1 (SRT_1 (SRT_1 (SRT_1 (SRT_1 (SRT_1 (SRT_1 (SRT_2 _fun (SRT_2 _fun{SRT_2 f8 (SRT_5 f9 f10 f11 f13 _fun{f9,f10,_fun{f8,f9},f11,f13})} f12)))))))))))))} ]))() ]))())))))))))))))))))))))))))))))))))))))))

t1とt1がずらずら並ぶ様子が見て取れます。これがメモリリークの正体(の一種)です。
evaluateでWHNFまで評価します。

Prelude E D Data.Map> m'' <- evaluate m'
Prelude E D Data.Map> :printHeap m''
let x1 = C# 'h'
    f1 = _fun
    x2 = C:Num _fun{SRT_5 t1 t2 t3 t4 (SRT_2 f2 f4)} _fun{SRT_1 (SRT_2 (SRT_2 f2 f4) (SRT_5 t1 t2 t3 f4 t4))} _fun{SRT_3 f5 _fun{_fun,_fun{t1,t2,t3}} (SRT_2 _fun{t1,_fun{t1,t2,t3}} _fun{t1,_fun})} f5 _fun _fun _fun
    t1 = _thunk()
    t2 = _thunk()
    t3 = _thunk()
    t4 = _thunk()
    f2 = _fun{SRT_1 (SRT_2 t5 f3)}
    t5 = _thunk()
    f3 = _fun{SRT_4 t1 t2 t3 t5}
    f4 = _fun{SRT_2 t5 f3}
    f5 = _fun
    x3 = Tip 4416806304
in Bin (x1 : C# 'e' : C# 'y' : [] 4435094248) ((_bco ([ f1 ])) x2) x3 (Bin (x1 : C# 'o' : _thunk _fun{140434867224912} 1) ((_bco ([ f1 ])) x2) x3 x3 1) 2

すると、update関数が全て評価されてWHNFに、つまりコンストラクタBinが見える様になりました。
MapのコンストラクタBinはexportされてませんが、以下で確認できます。

また、Lazy Mapを使ったので、valueがまだ評価されていないことも確認できます。
（さらに、細かいことですがMapのkeyを"hey", "hoy"と適当に用意したのですが、頭文字のx1 = C# 'h' が共有されていることも確認できたりします.. そして"hey"は完全に評価されているのに"hoy"は"ho"までしか見えてないですね。"hey"の評価はupdate関数を"hey"で行ったために全て評価する必要があった、"hoy"はOrdのために二文字目まで評価出来れば十分だった、ということでしょう。ちょっと面白いですね）

どのように動いているのか？

levity polymorphic type classが使われています。

class HasHeapRep (a :: TYPE rep) where
    getClosureData :: a -> IO Closure

instance HasHeapRep (a :: TYPE 'LiftedRep) where
    getClosureData = getClosure

instance HasHeapRep (a :: TYPE 'UnliftedRep) where
    getClosureData x = getClosure (unsafeCoerce# x)

instance Int# ~ a => HasHeapRep (a :: TYPE 'IntRep) where
    getClosureData x = return $
        IntClosure { ptipe = PInt, intVal = I# x }

instance Word# ~ a => HasHeapRep (a :: TYPE 'WordRep) where
    getClosureData x = return $
        WordClosure { ptipe = PWord, wordVal = W# x }

instance Int64# ~ a => HasHeapRep (a :: TYPE 'Int64Rep) where
    getClosureData x = return $
        Int64Closure { ptipe = PInt64, int64Val = I64# (unsafeCoerce# x) }

instance Word64# ~ a => HasHeapRep (a :: TYPE 'Word64Rep) where
    getClosureData x = return $
        Word64Closure { ptipe = PWord64, word64Val = W64# (unsafeCoerce# x) }

instance Addr# ~ a => HasHeapRep (a :: TYPE 'AddrRep) where
    getClosureData x = return $
        AddrClosure { ptipe = PAddr, addrVal = I# (unsafeCoerce# x) }

instance Float# ~ a => HasHeapRep (a :: TYPE 'FloatRep) where
    getClosureData x = return $
        FloatClosure { ptipe = PFloat, floatVal = F# x }

instance Double# ~ a => HasHeapRep (a :: TYPE 'DoubleRep) where
    getClosureData x = return $
        DoubleClosure { ptipe = PDouble, doubleVal = D# x }

Heapの構造を確認するにはLiftedな型だけではなくてArray#やInt#等のUnliftedやUnboxedなデータ構造も同様に対処できないといけないからですね。なるほどね。後はHeap構造にアクセス出来る特殊な関数2を呼び出して、Haskell上での表現(Closure型)に変換して返しているだけです（雑な理解）。

ghci以外で用いるには

今回はghci上で:printHeapを使う形で紹介しましたが、ghc-heap-viewを使ってGHC.HeapViewを単純にimportすれば同様のことはコード上でも可能です。

まとめ

ghc-heap-viewの使い方と、それを用いて関数適用によって構成されたサンクが評価されるにつれてその構造を変えていく様子を確認しました。
今までWHNFの話をする際には概念的な話しか出来なかったわけですが、それを直接確かめる手段ができたということですね。遅延評価周りの話もしやすくなったかと思います多分。

  1. ghc-heap-viewのver0.1見ればわかりますが、これ2012年からあるんですね..知らんかった.. ↩

  2. Haskellの言語能力的にサンクのままのHeapの構造にはアクセスできないので、これはGHC-APIによって用意された特殊な関数です。 ↩

24
8
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
24
8