Thoughts on GCs
数日Twitterで散発的に呟いていたことをまとめる。
きっかけはkazuhoさんのツイート。
細かいこと言うと、メモリを逐次解放するつもりがないなら、malloc呼ぶのは誤り。大きなブロックを確保して、先頭から順次使っていくのが正しい戦略です。処理が単純化し使用メモリ量が減り局所性が向上する結果、速度が向上する。世代GCやサーバ等多くのプログラムで用いられる一般的な手法です
— Kazuho Oku (@kazuho) 2018年9月6日
世代別GCの件は誤りで、コンパクションをするGCのことかな?
この「大きなブロックを確保して、先頭から順次使っていく」、まったくもって正しいんだけど話を単純化しすぎてて、実用上はいくつか問題が発生する。いつブロックを確保していつ解放するのだとか。 「サーバ等」ではリクエストを受け付けてからメモリを確保してレスポンスを返したら解放すればだいたい上手くいく。しかしそれでもリクエストローカルではないデータもあるしこういうカスタムなメモリアロケーションはCじゃないとできない。
こういうリージョンベースアロケーティング、いろんな言語でやりたいんだけどそういうAPIがないのとたまに含まれる長寿オブジェクトをちゃんと扱えないといけないから難しい。たしかGHCには入ってたはず。
— κeen (@blackenedgold) 2018年9月6日
GHCにリージョンとかの名前で入ってた気がしたけど探しても見つからず。GHCのメモリにはみんな困ってるらしく、検索ノイズが大きかった。
下記の世代別GCはこれで合ってる。
この状況を近似したのが世代別GCではあるんだけどいかんせんグローバルに走るのでリクエスト単位でみると全然近似できてない
— κeen (@blackenedgold) 2018年9月6日
因みにH2Oはアロケーションを使い分けてるらしい。
リクエストで使う文字列→リクエスト毎のプールで確保し、完了時にまとめて解放
— Kazuho Oku (@kazuho) 2018年9月6日
同一H2接続のリクエスト間で共有するHPACK文字列→参照カウンタで確保しプールに登録。全てのリクエスト完了時に解放
POSTデータ→tmpfsにフォールバックするバッファに確保
H2接続を表現するオブジェクト→malloc/free
CならH2Oのように適材適所のアロケーション戦略がとれるがやっぱり手動メモリ管理を放棄したGC付き言語だと厳しい。
また、今回の自分の話はサーバとかを念頭に置いていて、常にこれが最適とは限らない。
アプリケーション毎に適したGC戦略があるんだけど残念ながら先に言語とGCがあってあとでアプリケーションが出来上がるので先出しジャンケンになってしまう。処理系作者にできるのはErlangみたいに用途を限定するかJVMみたいに色んなGCを書くくらいしかない。
— κeen (@blackenedgold) 2018年9月6日
ところでlldはメモリを開放しないというのをruiさんが度々アピールしているけどそれはGCのある言語でもできる。
アプリケーション毎の適したGC戦略ってのはGCしないというのも含まれてて、バッチ処理で完走するまでにメモリが枯渇しないならGCしない方が速い。これはlldとかでも取られてる戦略。
— κeen (@blackenedgold) 2018年9月6日
本当にGCはない方がいい。
で、やっぱりGCのある言語でもH2Oのようにリクエスト毎にリージョンを作って破棄したい。色々考えるに、このリージョンは丁度fiberとかと寿命が一致するのではと思いつく。
昨日のGC戦略の続き。最近Project Loomの件とかでfiberが気になってるんだけどそれに対応して階層的リージョンとか出来ないかな。リージョンは自身か祖先のリージョンのメモリしか触れない。そうするとfiber毎にリージョン作ってfiberと一緒に破棄が簡単に出来るようになる。
— κeen (@blackenedgold) 2018年9月7日
階層化したのはfiberに親子関係があるからと、長寿オブジェクトも親のリージョンに置いとけば寿命長く出来るだろみたいなノリ。もちろんfiberのリージョンの上にはスレッドのリージョンがあるしグローバルなリージョンもある。
しかしやはりAPIの問題がある。ところでここまででてきたリージョンは「一時的に用意されたメモリのカタマリ」くらいのゆるふわな用語だけど下記のregionはちゃんとした方のリージョン。(CF リージョンについて)
しかしこれはかなりメモリを明示的に扱えるような言語仕様じゃないとだめで、言語設計から考えないといけない。研究レベルだとλ_{Region}の変種になると思うけど実用言語だと存在しないかなぁ。
— κeen (@blackenedgold) 2018年9月7日
これは似たようなものがあったはず。
ICFP 2016でstack based gcの話があった気がするけど全然覚えてないや
— κeen (@blackenedgold) 2018年9月7日
今調べたらこれだった。 Hierarchical memory management for parallel programs まだ読んでないので自分の考えと近いかは分からない。
で、自分の考えが合理的か考えてみた。
GCの話続き。fiberみたいな実行単位とメモリを結びつけるのはある程度合理的。メモリをアロケートするのも使うのもコードだから。それをもう少し細かくしたのが関数単位にしたスタック変数になる。
— κeen (@blackenedgold) 2018年9月8日
これは少し間違ってて、自分は親のメモリにもアクセスしようとしてるからスタック変数よりは柔軟になる。しかしやっぱりそれをやろうとするとリージョンになる。 つまりリージョンを前提にした言語設計になる。
結局、既存の言語に簡単には入らなそう。世知辛い。
余談
fiber毎とかもうちょっと言うとthread毎とかにメモリプールを持つと副産物としてfiber_local, thread_localが必要なくなる。thread_localの細かい仕様は覚えてないから完全互換ではないと思うけどやりたいことは大抵実現できるはず。
— κeen (@blackenedgold) 2018年9月8日