静的解析によるメソッド探索の高速化

概要

論文の詳細を見る
効率のよいオブジェクト指向言語の実装のためには、メソッド探索を高速化することが重要である。このために種々のメソッド・キャッシュ法が提案されてきた。ルックアップ・キャッシュやインライン・キャッシュは市販のSmalltalk処理系などで実際に使われている。キャッシュ法が改善されるにしたがって、キャッシュがミスしたときのオーバーヘッドがメソッド探索の性能に与える影響が大きくなってきている。したがってキャッシュがミスした場合のメソッド探索も高速化しなければシステム全体の性能は向上しない。プログラムの静的解析によってメソッド探索を高速化する手法としてタイプ推論を用いる方法やディスパッチ表を用いる方法が提案されている。タイプ推論は時間がかかることが問題で、高速化の追求は行なわれているものの、コンパイルの1フェーズとなるほどに実用的な時間では実行できない。ディスパッチ表は可能なクラスとセレクタの組み合わせに対して予めメソッドを計算して表に保存しておくものであるが、単純な実装では表が巨大になる。現在では表の充填率を100%近くに圧縮する方法が開発されているが、Smalltalkなどでは実用化されるほどには小さくならない。また2つの値を元にして表を引くことと、圧縮した場合にはセレクタ正当性のチェックが必要になることから、ある程度以上の高速化は望めない。本稿ではプログラムの静的解析によるメソッド探索を高速でかつ実用的なものにする手法について考察する。
一般社団法人情報処理学会の論文
1996-03-06

静的解析によるメソッド探索の高速化

スポンサーリンク

概要

著者

関連論文

スポンサーリンク