#:g1: Common Lispと多方向分岐の最適化

Posted 2015-06-23 11:13:17 GMT

Common Lispのcaseだとifの連鎖に展開されるので非効率なのが残念という話を耳にしました。
結論からすると、そんなことはないけれど、最適化されなければそういうこともある、という感じです。

Common Lispではcaseのような多方向分岐の最適化には2通りあります。

  1. caseのようなフォームを直接低レベルで効率の良い多方向分岐の記述に変換する
  2. 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では、任意のマクロはスペシャルフォームであっても良いことになっています。
しかし、マクロに位置付けられたフォームは、マクロの展開形を持っていなければならないので、処理系依存でスペシャルフォームとなっているフォームも展開されて見えます。
ということで、

  1. 展開するとifの連鎖になって見える
  2. 処理系は、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倍位の速度の開きがあるようです。

Lispと computed go

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

comments powered by Disqus