性能評価

GSとESの処理系を試験的に実装し、KLIC標準配布パッケージに含まれる9つのプログ ラムを用いて、標準KLIC (org)、GS、ESのそれぞれの性能を測定した。 またGSについては全変数をヒープに割付けるもの(GSH)と、スタック変数を用いるも の(GSS)の両者の性能を測定した。 この測定結果に基づき、9つのプログラムを表1のように分類し、それ ぞれの代表例の結果を表2に示す。

表 1: プログラムの分類

分類	基準	プログラム
type1	org / GSS 1.0	nrev, deriv, primes
type2	org / GSS < 1.5	quick sort, kkqueen, pascal
type3	org / GSS < 2.0	factorial, hanoi

表 2: 計測結果

分類	例		org	GSH	GSS	ES
type1	nrev	実行時間 [ms]	199	207	206	197
		速度比	1.00	0.96	0.97	1.01
		ＧＣ [回数]	44	39	37	37
type2	kkqueen	実行時間 [ms]	560	452	430	405
		速度比	1.00	1.24	1.30	1.38
		ＧＣ [回数]	78	29	21	21
type3	factorial	実行時間 [ms]	214	231	120	114
		速度比	1.00	0.93	1.78	1.88
		ＧＣ [回数]	22	4	0	0

nrev : リストの反転。 kkqueen : N-Queens。queen の数 = 10 factorial : 11 の階乗。10000 回繰り返し

表2より、GC回数の減少と実行時間が短縮に強い相関があることが わかる。 このGC回数の減少要因を調べるために、ヒープ消費量を測定したところ、 標準KLICの消費量を1とした場合の各方法での消費量は図4のよう になった。 すなわちゴールレコードによるヒープ消費の比率が大きいものほど、スタックの利用 やスタック変数導入の効果が高いことが明らかになった。

一方GSSとESを比較すると、いずれのプログラムにおいてもESの方が高速である。 Prologではバックトラックが生じる可能性があるため一般にGSよりもESが有利である が、KL1ではバックトラックはなく、またヒープ消費量も同一である。 したがって、ESの優位性は以下のような要因によるものと考えられる。

1. スタック変数がn回出現するとき
   GS：読出2n-1回、書込2回
   ES：読出n回、書込2回
2. 構造体生成タイミング
   GS：第1ゴール呼び出し直前
   ES：構造体参照ゴール呼び出し直前
   すなわちESの方が時間的参照局所性がよい。