Optimistic Stack Allocation For Java-Like Languages
論文(ACMへのリンク)
発表資料(pdf)
辞書で単語の意味を調べて繋げると「Javaライクな言語のための楽観的なスタック割り当て」ということになります。題名から予想するに「Javaライクな言語だったらだーいたいスタック割り当てで大丈夫っしょ〜」みたいな内容なのでしょう。誰ですかオブジェクト指向プログラミング言語にヒープ割り当てとガーベジコレクションが必須だなんて言ったのはプフー
なんか違う気がする。「Javaライクな言語のための最適化スタック割り当て」といったところでしょうか。自分なりにまとめてみます。翻訳ではありません。
概要
スタック割り当てはキャッシュメモリを効率的に利用できるが、安全にスタック割り当てに置き換え可能なオブジェクトを見つけるのは難しい。よって私達は手続きをまたぐエスケープ解析(interprocedural escape analysis)を必要としない、Java VMのような動的クラスロードやリフレクション、例外処理機構を持つ環境において安全にスタック割り当てを行う手法を提案する。
既存研究
従来のエスケープ解析手法はプログラム全体の解析結果を元にスタック割り当てを行う。よって動的クラスロードなどによりプログラムが変形した場合には解析をやり直す必要があり、そういった手法を適用するには困難が伴う。
Bakerの最適化スタック割り当て手法
CONS should not CONS its arguments, or, a lazy alloc is a smart allocで提案された手法は「全てのオブジェクトは一旦スタック領域に格納し、ヒープ領域からの参照された時に参照から辿れるオブジェクトをヒープに移動する」もの。参照が書き換えられたときにオブジェクトの移動をするのでライトバリアが必要。移動したオブジェクトがあった位置にはforwarding pointerを書き込む。移動前の位置を指す参照はforwarding pointerを指す先を見るのでリードバリアも必要。
提案手法
基本的に「Bakerの手法(Schemeへの実装)を元にJavaライクな言語に対して実装する」といった内容。
リードバリアの削除
Bakerの手法ではリードバリアが必要だったが、オブジェクトの移動をした際にそのオブジェクトを指していたオブジェクトの参照も書き換えればリードバリアは必要無くなる。オブジェクトの移動はヒープから参照されたとき行われるので、その時点では他にありうる参照はスタックからの参照のみである。参照の書き換えのためにスキャンしなければいけないのはスタック領域のみなのでコストはそれほど大きくならない。
ヒープ割り当てオブジェクト
スタック割り当てを経由せず、直接ヒープにオブジェクトを割り当てられるようにする。ヒープ領域に移動されるのが確実なオブジェクトをスタックに割り当てると性能劣化があるため。
スタック割り当てオブジェクトのロック
スタックに割り当てられたオブジェクトは他のスレッドからはアクセスできないようにする。
ループベースのオブジェクトスタック領域
まず提案手法ではメソッド呼び出しや返り値の受け渡しに用いるスタック領域(コールスタック)と、スタック割り当てに用いるスタック(オブジェクトスタック)は別の領域として管理する。オブジェクトスタックはリージョン(フレーム)に分割して管理し、以下の操作が可能なものとする。
- 新しいリージョンの開始
- 現在のリージョンに新しいオブジェクトを割り当てる
- 指定されたオブジェクトをヒープに移動
- 移動したオブジェクトを指すオブジェクトの検索
- リージョンとその中に含まれるオブジェクトの解放
新しいリージョンの開始をループ開始時、リージョンの解放をループの終了時に行う。リージョンはループの度に開始と解放を繰り返す。
深い再帰呼び出しをされるとスタックが大きくなってしまうという問題がある。これにはオブジェエクトスタックがある程度以上大きくなった場合はスタック割り当てをやめ、直接ヒープに割り当てるようにすることで対処する。また末尾再帰呼び出しの最適化を行なっている環境においては、ループと同等のフローであると見なして処理するものとする。
手続き内解析
提案手法では手続き内解析(intraprocedural escape analysis)のみを用いて、手続き内のコントロールフロー(ループ、分岐、例外処理)を解析し、コードとリージョンの対応をつける。
実験など
省略。
まとめ
実験結果は提案手法がスタックを利用することでメモリを効率的に利用し、高いキャッシュ効率を見込めることを示す。しかも我々の提案する手法はJavaのような動的クラスロードやリフレクション、例外処理機構を持つ環境において簡単かつ安全に実装可能である。
次はJikes RVMに実装して性能を計測します。
