Compact Regionsについて軽く

現在ghc最新は8.6です。

Compact Regionsはghc-8.2から搭載された機能です。
Compact RegionsはGC中に走査されない、連続したメモリ領域に載ったデータを提供します。

* [Hackage / compact: Non-GC'd, contiguous storage for immutable data structures](http://hackage.haskell.org/package/compact)


サーバーにバッチ処理で生成しておいたデータ(数百MBから数十GBくらいでしょうか)を持たせておくことを考えましょう。そのデータはサーバーがリクエストを捌く際にRead Onlyでアクセスされるとします。
そういうこと自体は問題によりますが、まあよくやることと思います。Redis等にアクセスするにもネットワークは遅すぎる、手元のKVSでも毎回デシリアライズ発生するのは遅すぎるといったケースですね。

しかしGHCのようなGC持つ処理系でサーバーを書く際、major GCが発生すると生存オブジェクトの総数に比例してpause(stop-the-world)が発生してしまいます。最近はメモリが数百GB-数TBあるサーバーの調達も容易になっており、そんな時pauseは時に数分に及ぶこともあるようです。

* [StackOverflow / Reducing garbage-collection pause time in a Haskell program](https://stackoverflow.com/questions/36772017/reducing-garbage-collection-pause-time-in-a-haskell-program)

上の例だと200MBで0.05sec pauseしているので、単純に正比例で計算すると、1000GBで250sec(~4.2min)もGC pauseが発生する計算になります。リクエストの途中でGCが発生して数分も待たされてしまっては使い物になりません（普通はreverse-proxyやクライアント側あたりでタイムアウトするでしょうが）。

少し横道にそれますが、Compact Regionsが提唱されたのがICFP 2015(2015-08-31..)でghc-8.2.1リリースが2017-07-22ですから、2年程度で論文の結果が実際の処理系に導入されたことになります。なかなかの速度ですね。[ICFP 2015の最中にSimon Marlowがコードレビューした](https://phabricator.haskell.org/D1264)とあるので、その時点でちゃんと動くものはあったようです。

さてこのCompact Regionsによって、先ほどのサーバーにRead Onlyのでかいデータを持たせたい問題は劇的に改善されることになります。Read Onlyのデータを丸ごとGCの走査されない領域に放り込むことが可能となるからです。それでいてそのデータは生きたオブジェクトなので、参照のコストも(redisへのネットワークアクセス、デシリアライズコストに比べて)非常に小さいものとなり、またGHC上でのcompactされた値の扱い方は他と全く変わりません。


## Compact Regionsの特徴と制約

Compactされたデータは生きたオブジェクトですが、GC中に内部を走査されません。また、シリアライズすることなくそのままネットワーク上でやりとりすることができます。
その実現の為にデータ型にはいくつかの制約が存在します。

* データ内で参照が閉じている(self-contained; 外部へのポインタを持たない)
* 内部にMutableなデータを持たない(immutability; IORefなどを含まない)
* メモリ上の表現とネットワーク上の表現が同じ(function, thunk等closureを含まない)
* Pinned ByteArray#を含まない(Cのデータ構造でそのpinnedされたアドレスが格納されているかもしれないため)

immutablilityも言ってみればself-contained制約の一種です。値が変更されてしまってデータ外の参照を持つようになってしまってはself-containedではなくなってしまうからです。

compactする際にはdeepseqとcopyが行われます。そうしてGCの管理されない連続した領域にコピーされるわけですが、これはGCで行われる処理と似ています。GCのコストを前倒して一回だけstop-the-worldは起こさないままに処理するとも見えるので、その辺の特徴は知った上で有効に扱うと良さそうです。

compact regionはメモリ表現(Compact Normal Form; CNF)が連続したメモリ上に格納されるという制約がありますが、これはcompact regionが他のcompact regionの一部になりうることを意味しています(Sharing)。
Sharingは色々なケースがありますが、ここで論文からひとつ、3.2 Sharing non-compact subgraphsのコードを引用します(論文内ではAPIが現在のものと異なりますが気にしないでください):

```haskell
do let s = [2,1]
       d = (3:s, 4:s)
   c <- mkCompact
   r <- appendCompact d
   -- 'tail (fst r)' and 'tail (snd r)' shared?
```

この`d`は木構造ではなくダイヤモンドのような構造を取っているわけですが、これを`compact`すると`s`はそれぞれコピーされます。この構造を保持したい場合は`compactWithSharing`を用います。このように`compactWithSharing`は構造を保持する処理で、`compact`より10倍程度遅くなるとか。

そうしてself-containedになることで、ようやくGCはそのオブジェクトの内部を走査する必要がなくなるわけです。オブジェクトが生きているかどうかの判定が集約されるとも考えられます（commpactedなデータの内部への参照があるかもしれないけど）。
また、Runtimeでのメモリ表現も少し特別なもの(CNF)を用意することで、ネットワーク越しにそのままやりとりすることができるようになっています。


## 実用の際気をつけること

* serializerライブラリ(ex. binary等)よりサイズが大きい(余計なデータ削ぎ落とされてないので. x2-x4になっている様がpaperにある)
* compactされた値がFreeされるタイミングはcompactされた値への参照(内部の値への参照も含む)が全てなくなった時
* Compact regionsのメモリ表現(CNF)は、デシリアライズ時にCNF内部のポインタを正しい値につなぎ直す必要がある("fixup"と呼ばれてる)。このfixup処理はCNF内の古いアドレスを、新しくアロケートされたアドレスを用いて調整する。これはABI互換性とstatic link(もしくはASLRをオフにする)に依存しており、そのため実用上、実行バイナリは完全に同じである必要がある。信頼できないデータは絶対にCNFとして読み込んではいけない。

サイズは膨れるけどシリアライズ/デシリアライズ含めたら処理コストだいたい小さいよ、とか論文にデータが載ってます。
Freeされるタイミングを意識しないといけないというのはGC管理外の値を扱う以上、必要になることですね。
3つめのポインタ修復処理はまあ仕方ないのかな..


## 使い道

ローカルネットワークでサーバ間でわいわい投げつけ合うとか楽しそうですが、僕はそちらのアーキテクチャに関してはあまり詳しくないので割愛します。まあ某銀行のHaskell処理系では任意の(かどうかはわからないけど)式をS式にしてサーバー間で投げ合っていたようですが、それと同じようなことがGHCでも出来るようになったわけです。楽しいですね。
まあしかしローカルネットワークからデータを出す際にはそのままの表現は使わない方がいいでしょう。また、ファイル書き込みやDB書き込みももちろんできるわけですが、GHCのバージョンが変わって表現が変わってデシリアライズ出来ませんでした、では困るので、それを防ぐ方法が何か必要でしょう。実行バイナリに対する一意なハッシュ値でもつけておくとか、DBへの書き込みは一般のserializeライブラリを用いるとか。大抵後者でしょうか。

冒頭に書いたようなサーバに持たせるというのが使い方としては利点もわかりやすいでしょうか。

また、単純にHaskellの値をそのままシリアライズできるので、一時的に値をファイル書き込みしたくなった場合に便利かもしれません。今までだとShowとか何かのインスタンスにする必要があったわけですが、その必要がないわけです。雑に書き込めます。多分(Pinned ByteArray#制約にどの程度引っかかるか分かってない)。


## 雑感

この機能、割といろんなGC持ち言語で欲しい（というか僕が仕事で使いたい）のだけど、immutabilityが制約として存在するんですよね。残念ながらそんな言語あまりない..というかHaskellと相性が良い機能と言えるでしょう。
GHCにはimmutabilityとかpurityを前提とした機能や最適化がそこそこあったりして、他の言語が真似しようにも真似できないことが割とあるように思います..

さてHaskellサーバーのレイテンシ遅い問題はCompact Regionsによって（一部の問題で）大きく改善されますが、今後GHCにはLinear Typesの導入が予定されています。そもそもサーバーの(Request -> IO Response)の途中でallocateされたメモリは、基本的にはレスポンス返した時点でだいたいFreeできるはずなんですよね。つまりそれらはLinear TypesによってGCを待たずに素早く解放出来る可能性があり(Linear TypesもGCの管理外でmemory allocationを扱います)、結果GC Pressureを小さくすることが出来るかもしれません。 [Linear Typesによる恩恵](https://ghc.haskell.org/trac/ghc/wiki/LinearTypes/Examples)はいくつかありますが、Linear Typesによってさらなるレイテンシ改善を期待したいです(なおその場合全体の速度は遅くなりうることは分かっているようです)。

あとdistributed-process周りでも活躍しそうです。あれもclosureをサーバ越しに投げつけるために(cf. `StaticPtr`)実行バイナリが同じことを実用上要求するのですが..Serializableクラス使うかcompactして投げるか用途に応じて開発者が選択することになりますかね。


## 参考

* http://ezyang.com/compact.html
* http://hackage.haskell.org/package/compact
* https://github.com/ghc/ghc/blob/ghc-8.6/rts/sm/CNF.c#L37