Matzにっき

_ [言語]新(？)GC手法

いつまでも引っ張ってもしょうがないので、公開。

材料

• KSMのGC手法。生成したオブジェクトをテーブル(registry)に登録することで、 Cスタックをスキャンしないconservative GCを実現
• write barrier。木山くんの世代別GCで実現されている
• single thread下でのCスタックのスキャン。Rubyをはじめ多くの実装がある。

作り方

• あるスレッドで生成したオブジェクトは全部スレッドごとのテーブル(registry)に登録
• ヒープから参照されたオブジェクトにはwrite barrierでマークをつける
• テーブルがいっぱいになるかフリーリストが空になるとminor GC。
  • ローカル変数とCスタックから参照されているオブジェクトに(上記とは別の)マークをつける(再帰しない)
  • テーブルをスキャンして、ヒープからの参照マークも、ローカルからの参照マークも付いてないものはゴミ。回収。
• minor GCで回収したオブジェクトが十分になかったりすると、major GC。 たぶん全スレッドを止めてmark and sweep。 あるいはdirty bitを使ったconcurrentなものにする余地もあるが、そこまですることはないかなと。

multi thread環境では、minor GCがスレッド独立で行うことができるので、性能が期待できる。 single thread環境では、minor GCでは全オブジェクトをスキャンしないので、live objectが多くても性能が期待できる。

問題は、minor GCで回収できるのはヒープから参照されたことがないオブジェクトだけなので、 あまりに保守的過ぎて性能向上が十分でないかもしれないということ。いくら非再帰で軽いからと言っても、 あまり頻繁に行われては意味がない。実際に実装してみないとなあ。

なお、yarvメーリングリストで、富士通研の中村さんらの「動的に割付け戦略を最適化するJavaメモリ管理機構」(情報処理学会 トランザクション 「プログラミング」 アブストラクト Vol.44 No.SIG13 - 002)が似てるということを教えてもらいました。

別に真似したわけではありませんが、完全に独創的というものを作り出すのは難しいものです。 ってtraitの時にも似たようなことを書いたような。ヒープを別に持たない点などはちょっと独自かも。

なお、このアイディアはそのうち論文にする予定です。だが、まず実装しないとな。 いつになるやら。