絶対性能

まず, 逐次のCKYアルゴリズムをC++で記述したものと, ABCL/fプログラムを1 台で実行させた場合の速度比を示す. ABCL/fとして1 version, C++として3 version用意した. 3つのC++プログラムの違いは, メモリ管理の違いで, 一つ はC++に標準的なmalloc/freeを用いるもの, 一つは, ABCL/fが利用している, Boehm &WeiserによるC用のGC library (GC_MALLOC)を用いて行なうもの, も う一つはCKYアルゴリズムに特化したメモリ管理を自前で行なうものである.

CKYアルゴリズムは, 集合 を表現するため, およびエッジを保存する ために, 大量のメモリを消費するプログラムで, しかも一文を解析している間 はそれらのデータは決してfreeされない. 自前のメモリ管理は, その事実を利 用して, それらのデータを連続したメモリ領域の端から割り当て, 次の文では 同じ領域を繰り返し使うというものである. つまり, 1文の解析が終了した, 生きているデータがほぼ零とわかっている時点で, 割り当てた領域全てをfree をしていることに相当する. 一方, GC_MALLOCを使う場合には, 大きな文の解 析中にGCが起動されることがあり, その場合は巨大な数のエッジおよび記号を markしなくてはならない. この応用問題は巨大なデータを生成し, かつそれら が単純なlife timeを持っているため, GCにとっては不利な応用問題であると いえる. ABCL/fはGC付きの言語であるため, 参考としてあえてGCつきのCプロ グラムとの比較を行なった. 実験は全て上述したSparcStation 10上で行なっ た. また, malloc/freeについても同様に, いきているデータ全てに対して一 度ずつfreeを呼ばなくてはならないため, メモリ管理の負荷は高いプログラム になっている.

     図5.8: 

GCつきのC++を1とした時の, 他のプログラムの性能を文の長さごとに分類した ものが, 図5.8である. ABCL/fは, 任意CPU数で動作可能なバ イナリを1台で走らせたものであり, 複数プロセッサが存在していれば必要な はずのオーバーヘッド(オブジェクトの位置検査, ポーリングなど)を含んでい る. 性能は所要時間の比で表されており, グラフが高いほど性能が悪いことを 意味している. 結果は, このプログラムが の要素およびエッジのた めのメモリ管理にほとんどの時間をとられていることを明確に物語っている.

平均してABCL/fは, GCつきのC++の2.5倍程度の時間を要している. ABCL/fと C++を比較した場合の主なオーバーヘッドは,

• への参照が, C++ではただの配列参照であったものが, ABCL/f では, 同期つきの参照sync-get!に置き換わっている. これは, 配列の 参照, 取り出されたオブジェクトに対するメソッドの呼びだし, データがすで にあるかどうかの検査, など全てを含んでいる.
• 同様に, への書き込みにも, メソッド呼びだし, 待っているスレッドがあるかどうかの検査などが全て含まれる.

また, ABCL/fはmalloc/freeを用いた版よりも多くの場合に良い結果を出して いることは 注目に値する.