Gnu Common Lisp(GCL)/Kyoto Common Lisp(KCL)の最適化について
Common Lispは、実用言語である。
なので、Common Lispの最適化がすごい例を、ちょっと書いてみたり。
GCLは、もともとのKCLを強化して、AKCL (Austin KCL)となり、それを維持強化しているもの。
（GCLのページの歴史にもそれは書いてある http://www.gnu.org/software/gcl/ )
下に示す最適化は、KCLの時代からまったく同じで、強力だった。
素朴に書くと、下のような階乗のプログラム…
(defun fa2 (x y)
(if(zerop x) y
(fa2 (1- x) (* y x))))
型をきちんと指定して、関数の返す型や、途中の変数が保持するデータが、
fixnum(小さな整数,実現によるが大体28bit〜30bitぐらい?)であると、
処理系に教える、と、下のようになる。
(defun fa3 (x y)
(declare (fixnum x y))
(if(zerop x) (the fixnum y)
(fa3 (the fixnum(1- x)) (the fixnum(* y x)))))
これをコンパイルする。
※実際には、
(disassemble 'fa3)
を実行する。
:
;; Note: Tail-recursive call of FA3 was replaced by iteration.
:
OPTIMIZE levels: Safety=0 (No runtime error checking), Space=0, Speed=3
:
/* function definition for FA3 */
static void L1()
{
:
{long V1;
long V2;
:
TTL:;
if(!((V1)==0)){
goto T2;}
base[2]= CMPmake_fixnum(V2);
vs_top=(vs_base=base+2)+1;
return;
goto T2;
T2:;
{long V3;
V3= (long)(V1)-1;
V2= (long)(V2)*(V1);
V1= V3;}
goto TTL;
}
}
となる。
ということで、TTL - goto TTL;の単純なループとなり、
ループの中の演算は、longの
乗算, マイナス1, 0との比較
という整数演算のみになっている。
ちなみに、機械語は
30: 85 d2 test %edx,%edx
32: 74 06 je 3a <_L1+0x3a>
34: 0f af ca imul %edx,%ecx
37: 4a dec %edx
38: eb f6 jmp 30 <_L1+0x30>
となっている。
(いまどきのCコンパイラなら、V3という変数はなくなって当然)
ちなみに、GCL/KCLは、コンパイルのオプションは、デフォールトで
OPTIMIZE levels: Safety=0 (No runtime error checking), Space=0, Speed=3
速度優先、実行時エラーチェック無し
となる。今回もそのまま。
今回使用したのは、
GCL (GNU Common Lisp) 2.6.6 CLtL1 Feb 10 2005 08:19:54
OSはWindowsXP
蛇足)
GCL/KCLは、Lispソースからコンパイルした、オブジェクトはC言語である。
なので、コンパイル結果を見るのが、非常に楽である。
また、GCL/KCLは、disassembleすると、こっそりとソースを再コンパイルしてそれを表示する。
GCLの基本的なアーキテクチャはKCLからほとんど変わっていない。
僕の自慢は、
このKCLの最適化を、1986年ごろ(「KCLが凄いぞ!」と世界中で有名になっていたころ)に、
KCLの作者の一人である萩谷さんに、KABAでじきじきに教えてもらったこと
である。
たけおかの Lispページ 目次
GnuEmacsと、Gnu Common Lispを一緒に使うと便利! こちら。
CommonLispで記述した、StarTrek(1976年頃流行した古いゲーム)
Prologの入門文書に飽きた人に
Prologで記述した、StarTrek(1976年頃流行した古いゲーム)
たけおか(竹岡尚三)のホームページ