Seminar:CommonLisp:2004

Seminar:CommonLisp:2004

Franz 社セミナー


「2日間みっちり!Lispチュートリアル&Lispセミナー&Lisp事例紹介」

Lisp セミナー(一日目)

Franz 社 CEO
和田先生

Lisp チュートリアル(一日目)

飲み会

Lisp 事例紹介(二日目)

お茶会


参加者のコメント


「ACL7.0の新しい正規表現」補足

Shiro: 時間の都合で削った話を書いておきます。 最適化の局面でマクロを利用することについて。

正規表現をVMで実行するにあたって、いくつの「レジスタ」---部分マッチとか 繰り返し回数を保存するもの---を必要とするかは、正規表現のコンパイル時に 定まります。正規表現をLispコードに変換する場合は、必要なだけのレジスタを マシンスタックに取ることが出来ます。しかしVMの場合、VM自体のコンパイル時 には必要なレジスタ数がわかりません。(Lispでalloca()が使えれば良かったんですが)

当初は、実行時にレジスタ用にベクタをアロケートしていました。 最終的には、バックトラック用のVMスタック(fixnumのsimple-vector)の最初の方を レジスタとして使用しています。

しかし、VMスタックのアロケート自身にも時間がかかります。あらかじめ 決まった個数のレジスタをローカル変数としてVM内に取って置く、という方法も 考えられます。例えば16個はVMに取ったレジスタを使い、レジスタ数がそれを 越えた場合はVMスタックを使うと。そうすると、バックトラックの無い正規表現 では、VMスタックベクタのアロケートが省ける分速くなるかもしれません。

Lispで配列そのものをマシンスタックに取ることが出来ないので、 固定したローカル変数を宣言しておくことになります。スピルしていない レジスタへのアクセスは当該ローカル変数へのアクセスに、そうでない場合は VMスタックベクタへのインデックスアクセスになります。 実行時の条件分岐はできるだけ避けたいので、レジスタをアクセスするその時に なって条件判断や演算をしたくはありません。

そこで、ひとつのVM記述から、実行時の使用レジスタ個数がそれぞれ 0個、2個、4個、8個、16個、それ以上(スピル有り)、等の場合に最適化 されたクロージャを生成するようにマクロを変更し、 正規表現コンパイル時に最適なクロージャを返すようにしてベンチマークを 取りました。クロージャのバリエーションも色々変えたりして。 で、結局、現在の方法が一番速いことがわかった次第です。

この試験は、VMループのコード自体に手を加えずに、全て上位のマクロの変更で 行いました。(VMループのコードをトラバースしてレジスタアクセス コードを書き換えるようなマクロを使いました)。 マクロがなかったら、多分テストそのものをあきらめていたんじゃないかと思います。

ちょっといじってベンチマークを取って、という最適化は非常にストレスフルな 作業です。作業効率が悪いとアイディアを試すのが億劫になりますし、限られた 時間内に試せる技法の空間も狭くなります。 実行時間より実装時間を重視する理由として、 「マシン時間よりプログラマ時間の方が高価である」ことが良く言われますが、 本当に実行時間を重視したいなら、実装時間がばかにならないオーダーで 効いて来るのだと思います。


過去のセミナー

More ...