Edited at
PrologDay 13

高速Prologコンパイラへの道


はじめに

自作のProlog処理系、O-Prologにつき世界のデファクトスタンダードであるSWI-Prologの実行速度を超えようという計画を立てていました。この度、ようやくその計画を達成しましたので忘れないうちに概要を書き記します。


発端

ベンチマークテストでよく使われるコードにQueens問題があります。チェス盤上にQueenを互いに取られないようする配置をすべて求めるという問題です。8Queensでは92の解があることがわかっています。1980年代は8Queensでベンチマークを行っていましたが、現在のコンピューターは遥かに高速ですので9Queensとしました。世界でもっともポピュラーであり高速でもあるSWI-PrologをO-Prologの性能改善のため目安としました。当初、9Queensの全解を表示するコードで比較をしていました。比較してみるとそれほど高速でもないように思えました。ところがJekejeke-Prologの作者である研究者バースさんから指摘がありました。解を表示しない場合にはかなり高速なのです。また、16回連続動作でどれだけの速度が出せるのか?という質問がありました。これは良い題材でした。SWI-Prologはおよそ350ミリ秒で実行することがわかりました。当初のO-Prologは1秒以上かかっていました。いかにしてSWI-Prologの性能に近づけるか、あるいは、超えるかということに取り組みました。

コードは次の通りです。


% 9-queens program

test16 :- between(1,16,X),test,fail.

test :- queen([1,2,3,4,5,6,7,8,9],X),fail.

queen(Data, Out) :-
queen_2(Data, [], Out).

queen_2([], _, []).
queen_2([H|T], History, [Q|M]) :-
qdelete(Q, H, T, L1),
nodiag(History, Q, 1),
queen_2(L1, [Q|History], M).

qdelete(A, A, L, L).
qdelete(X, A, [H|T], [A|R]) :-
qdelete(X, H, T, R).

nodiag([], _, _).
nodiag([N|L], B, D) :-
D =\= N - B,
D =\= B - N,
D1 is D + 1,
nodiag(L, B, D1).


コンパイラ方式

当初、O-Prologにはインタプリタしかありませんでした。速度を向上させるのに真っ先に思いつくのはコンパイラです。PrologはバックトラックやunifyがありPascalコンパイラを作るように単純にはいきません。節をif文に展開しておき、頭部のunifyを生成するものの、本体部はインタプリタの仕組みを流用する簡易な方法によりました。この結果インタプリタより40%程度の速度改善を得ることができました。PrologコードはProlog自体で書かれたコンパイラによりC言語に変換されます。これをGCCでコンパイルし、動的にリンクするという方式をとっています。日本のCommon Lisp 処理系である萩谷先生たちによるKCLをお手本としました。


末尾再帰最適化

コンパイラにしたものの40%程度の速度改善にとどまっていました。文献を読んでみると特定のPrologコードはバックトラックをせず、効率のよいCコードに変換できることがわかりました。9queensのベンチマークコードにもその特殊なコードが含まれていました。Queensの利き筋に配置されていないかどうかを確認するnodiag/3という述語です。


nodiag([], _, _).
nodiag([N|L], B, D) :-
D =\= N - B,
D =\= B - N,
D1 is D + 1,
nodiag(L, B, D1).

nodiag/3では本体部に== is など組込述語が使われています。これは恒真の述語でありバックトラックはしません。末尾で自分自身を呼び出す末尾再帰になっています。このようにバックトラックをしないことがわかっており再帰をしている場合には単純なコードに変換することができます。バックトラックをする場合にはやり直しをするために前の情報を残しておかないといけませんが、nodiagの場合にはそれがありませんから、以前の値を保管しておく必要がありません。単純化でき、ぐっと高速化することができました。9Queensの16回連続でおよそ500ミリ秒にまで実行時間を短縮することができました。

末尾再帰最適化の詳細については下記のページに詳細があります。

https://qiita.com/sym_num/items/8b92cf6f1503474792f2


GCの改良

末尾再帰最適化で速度改善したものの、SWI-Prologとはまだ160ミリ秒もの差があります。そのうちの100ミリ秒の原因はわかっていました。GC(ガベージコレクション)です。O-Prologは16回連続実行中にどうしても1回GCが起動してしまいます。GCが起動するとおよそ100ミリ秒のタイムロスが生じてしまいます。

平成30年6月にAZ-Prologの開発者である稲葉さんとお話しをする機会がありました。O-Prologの弱点のひとつであるGCのことをお話ししたところ、「GCはポインタを書き換えるだけであり時間はかからないはずですよ」ということでした。さて?それはどういう意味なのか?と一晩考えていました。朝、ようやくその意味が理解できました。Prologの場合には失敗によるバックトラックがあります。バックトラックが生じた場合には前回バックトラックを起こした時刻以後に生じたセルはすべて不要なのでした。Lispなど通常の言語では失敗という概念はありません。計算は最後まで成功が継続します。ですからどのセルが生きているのか、不要なのかをセルを調べまわって回収する必要がありました。Prologの場合にはそのようなことをする必要はないのです。

  -------------------        0

 |
 | heap area
 |
 ------------------- 7000000
|
| working area
-------------------- 10000000

図はO-Prologのセル領域です。構造体配列によりセルを構成しています。1000万個のセルを持っています。従来はこれをひとまとまりとして使っていました。ここに節のデータやunifyにより生ずる中間結果のセルなどをごちゃまぜにして使っていました。これを図のようにヒープエリアとワーキングエリアに区分けしました。700万個と300万個に分けました。ヒープはhpポインタ、ワーキングエリアはwpポインタで管理しています。hpはセルをLisp同様に自由リストの鎖として管理しています。節のデータなど永続的に保存するものをここに置いています。足りなくなった場合にはマーク&スイープによりGCをします。

wpは7,000,0001 番目のセルから順番に必要に応じて使っていきます。unifyのときに使うセルをここから切り出します。セルが必要なくなった場合にはこのwpを単純に書き換えるだけでGCが行われます。具体例を考えてみます。


foo(X) :- bar(X).
foo(X) :- boo(X).

bar(X) :- fail.
boo(1).

このような節があったとして ?- foo(X). という質問をしたとします。最初の節を調べてbar(X)を辿ります。しかしこれはfailですから失敗です。ところでここまでunifyしてきたことは以後においてまったく必要ありません。ですから節を調べる前にwpポインタの位置を記憶しておきます。bar(x)が失敗だと分かったときにはwpの値をもとの値に書き換えます。これだけでセルを回収できます。個々のセルが生きているかどうかを調べるまでもありません。全部、必要ありません。回収はポインタを書き換えるだけです。さて、2番目の節を調べにいきます。boo(x)を調べます。そうするとboo(1)がありますから成功します。X=1であることがわかり、成功です。

この後、REPLに戻ります。このときもwpの値を初期値の7,000,001に戻します。これでGCは済んでしまいます。

一方、ヒープの方はそうはいきません。ここには節を表すセルがリストとして置かれています。foo(X) :- bar(X)を削除してfoo(X) :- goo(X) にしますと不要なセルが生じます。これはhpポインタ管理していて7,000,000個近くを消費したときにGCを起動しマーク&スイープにより回収しています。もっともヒープにGCがかかることは滅多にありません。通常、蓄えている節のデータを削除、変更することはそれほど多くはありません。

ワーキングエリアはunifyのために頻繁にセルが消費、不要となります。これの回収はwpポインタを書き換えるだけです。

このようにしておよそ100ミリ秒を時間短縮することができました。


本体部の生成コード


インタプリタの流用

GCを改良したことにより100ミリ秒を時間短縮し、16回連続で400ミリ秒程度にまで時間短縮できました。あと60ミリ秒をなんとかしないといけません。細かい節約をあれこれ試してみました。しかし、大きな効果はありませんでした。60ミリ秒を短縮するには大きな変更をする必要ありました。

従来のコンパイラの生成するCコードは中途半端でした。インタプリタを流用しているのです。


foo(X) :- bar(X).
foo(X) :- boo(X).

bar(X) :- fail.
boo(1).

先ほどのコードの実行を追いかけてみます。?- foo(X).を証明するのにbar(x)を調べないといけません。インタプリタはこれをトレイルスタックというものに積み込んで調べます。まずはbar(x)をトレールに積みます。bar(x)を調べてみるとそれはfailを本体部にもっていますので、さきほどトレールスタックに積み込んだbar(x)と置き換えます。failは失敗しますので、トレールスタックをクリアにして最初からやり直しです。boo(x)をトレールスタックにおいて調べなおします。ようやくboo(1)を見つけて証明は終わりです。

このようにトレイルスタックに証明すべき本体部を順次積み込んで調べていくのがインタプリタの仕組みです。Prologの動作原理である導出原理のやり方そのままに行っています。しかし、これには無駄があります。トレールスタックに積み込むという作業です。当初のコンパイラは各節をC言語のif文にしておくことによって時間短縮をしていますが、本体部はバックトラックがあるのでややこしいです。そこで本体部はインタプリタの仕組みを流用してその都度トレールスタックに積んでいました。ここを本格的に変更することにしました。


新方式の試行錯誤

トレールスタックを使わない方法を考えました。最初に考えたのはバックトラックをネストしたループとして生成する方法でした。


while(1){
if(foo(X) == YES)
return(YES);
while(1){
if(boo(X) == YES)
return(YES)
}
undo()
}

foo(X)、boo(X)はバックトラックします。これをやるのにfoo(X)などの関数に内部状態をも持たせようとしました。それはstaticにして内部状態を保存しておき呼び出される都度状況に応じて実行すべき節を選ぶという構想でした。しかしこれはややこし過ぎました。コンパイラを作り始めたものの、早々、壁にぶつかってしまいました。何か他の方法を考えないといけないようでした。


継続渡し

何かヒントはないかと何度か読んでいるはずのノービッグ先生の「実用Common Lisp」を読み直しました。ここでのLispで実装したPrologコンパイラは継続渡しを使っていました。次に証明すべき述語を次々に渡していく方法でした。これが参考になりました。また、WarrenさんのProlog用の抽象マシンWAMの本も読み直してみました。WAMではproceed命令があります。これにより本体部を実行し失敗した場合には次の節のコードに制御を移動する仕組みになっていました。

これらを参考にしてC言語でproceed命令を作りました。これは2つの引数を持ちます。 proceed(body, cont) となっていてbodyには本体部をリストにしたものを渡します。contにはその本体部が全部終わった後に証明すべき述語を渡します。proceed命令はそれらを繋げつつ、最初に証明すべき述語を調べます。その述語にはその後で証明すべき述語の列を与えます。

次のようなコードを生成します。


body = ...;
if(proceed(body,cont) == YES)
return(YES);

unbind(save2);
set_wp(save3);

proceed命令はちょっとややこしいことをやっていて、連言や選言、そして各述語の種類に応じて振り分けるということやっています。この結果コンパイラの生成するコードは単純です、従来のコンパイラからの変更は軽微で済みました。


実行結果

さあ、queensのコードを新コンパイラでコンパイルできるようになりました。SWI-Prologを超えることができたのでしょうか?


O-Prolog Ver 1.55(Chika)
| ?- compile_file('queens.pl').
pass1
pass2
compiling test16
compiling test
compiling queen
compiling queen_2
compiling qdelete
compiling tail nodiag
invoke gcc
yes
| ?- ['queens.o'].
yes
| ?- time(test16).
Elapsed Time=0.350529 (second)
no
|

同じコードをSWI-Prologで実行すると下記のようです。


?- time(test16).
% 4,596,069 inferences, 0.344 CPU in 0.352 seconds (98% CPU, 13370383 Lips)
false.

?-

僅差ではありますが、SWI-Prologの実行時間を超えることができました。成功です。

ver1.57 より上記の動作となります。2018年10月21日バージョンアップ。


書籍

O-Prologは書籍の付録です。「Prolog処理系を作ろう」という2年前に電子出版で出したものです。これは本文との対応関係があるので付録のソースコードはあまり効率のよくない古いバージョンです。

この度、速度について目標を達成しましたので、続編の「Prolog処理系を作ろうパート2」を準備します。そこではこの新方式の詳細な説明と全ソースコードを付録として付けることとなっています。

https://www.amazon.co.jp/dp/B01M3TVQ5M

追記

パート2を書くつもりだったのですが、あれこれと多忙で断念しました。その代わりに既に電子出版済みの「Prolog処理系を作ろう」の付録のソースに追加でver1.60の全ソースも追加しています。


参考文献

実用Common Lisp

ピーター・ノーヴィグ (著), 杉本宣男 (翻訳)

Prologマシン

金田 悠紀夫 (著)