Posted 2015-06-23 11:13:17 GMT
Common Lispのcase
だとif
の連鎖に展開されるので非効率なのが残念という話を耳にしました。
結論からすると、そんなことはないけれど、最適化されなければそういうこともある、という感じです。
Common Lispではcase
のような多方向分岐の最適化には2通りあります。
case
のようなフォームを直接低レベルで効率の良い多方向分岐の記述に変換するif
の連鎖を検査して、ある条件を満した場合に、低レベルで効率の良い多方向分岐の記述に変換するです。
case
を最適化case
を直接変換する方式には、CLISPや、Symbolics Genera 7以降のLマシン(3600系)があるようです。
Generaの方は、手元のOpen Generaで確認してみましたが、どうも3600シリーズ限定の機能の様子。
(case x
((0) ...)
((1) ...)
((2) ...)
((3) ...)
(otherwise :default))==>
(compiler:computed-go x ... )
のような変換がされるようです。
ソースがないので詳細は不明ですが、computed-go
とあるので、何か計算型gotoのプリミティブがあるのかもしれません。
参考のSLUGのメールによるとGenera 7.1位とのことなので、1987年位にはあった機能ということになります。
CLISPのほうは、case
の場合ハッシュテーブルで分岐用のテーブル作成するようです。
case
をif
や、cond
まで展開した後ではこうならないようなので、case
にはオプティマイザが付いているのでしょう。
case
から低レベルなフォームへの変換についてCommon Lispでは、任意のマクロはスペシャルフォームであっても良いことになっています。
しかし、マクロに位置付けられたフォームは、マクロの展開形を持っていなければならないので、処理系依存でスペシャルフォームとなっているフォームも展開されて見えます。
ということで、
if
の連鎖になって見えるif
の連鎖から多方向分岐の最適化はしない場合でも最適化していないとは限りません。
この場合、disassemble
でもしてみないと分からない、ということになります。
ちょっとややこしい。
if
の並びから多方向分岐を検出して最適化if
の並びから多方向分岐を検出して最適化する方式を採用している処理系は、古くは、Lucid CL、Allegro CLがあるようです。
Lucid CLは、version 4(1990)辺りから、Allegro CLもversion 4辺り(1993辺り?)なので結構古くからある最適化です。
Clozure CLは、1.8(2012年)からこの最適化が入りました。
どの処理系もCLISPのように分岐用のテーブルを作成して分岐するので要素数に比例してどんどん遅くなるということはありません。
この最適化では、テーブルを作成することが多いですが、最適化の発動条件もテーブルが作れるかどうか、という感じになります。
処理系によって、最大の分岐数や、範囲と値の分布状況によって発動したりしなかったりします。
この条件は処理系のマニュアルに載っていたりいなかったりという感じですが、載ってないことの方が多い印象です。
SBCL、CMUCL、ECL、LispWorks辺りはこの最適化が搭載されていません。現在最も身近なSBCLに搭載されていないため、Common Lispはこの類の最適化はしないものと思われても仕方ないかなあとも思います。
256分岐位のcase
でベンチを作成して実行してみると、最速と最遅では大体10倍位の速度の開きがあるようです。
MacLISPでは、所謂 computed go が使えました。
(defun foo (x)
(prog ()
(cond ((minusp x) (go a))
(t (go b)))
a (print 'foo)
b (print 'bar)))
こういうものが
(defun bar (x)
(prog ()
(go (cond ((minusp x) 'a)
(t 'b)))
a (print 'foo)
b (print 'bar)))
こんな感じに書けるのですが、Common Lispでは採用されなかったようです。
Fortran 90で computed go が廃止予定になり実際に廃止になったのは、Fortran 95だったようですが、代わりにcase
が入りました。
代わりに入ったということは、恐らくcase
には computed go 的な最適化はそれなりに期待されているのでしょう。
CLtL1のgo
の解説によれば、 computed go は case
で効率を落さず代用できる、ということなので似たような状況だったかと思いますが、実際の所、最適化はされたりされなかったりです。
Wikipedia:Multiway branchで引用されているクヌース先生のStructured Programming with go to Statements
の話では、多方向分岐については、非効率な実装をされがちというのは昔から嘆かれることが多かったようですが、Common Lispの場合も忘れられている処理系が結構あるという所なのかなあ、という所です。
■
HTML generated by 3bmd in LispWorks Personal Edition 6.1.1