#:g1: Common Lispで多方向分岐の最適化がされない場合にどうするか

Posted 2015-06-23 14:27:15 GMT

前回Common Lispと多方向分岐について書きましたが、最適化は処理系任せでした。

クロージャーの配列を使う

これをユーザーレベルでどうにかしよう、という例も昔からあって、前回紹介したSymbolicsの最適化についての議論でもJeffrey Mark Siskind氏が、配列にクロージャーを詰めれば良いじゃないか、というような発言があります。

このアイデアは割合に定番なものですが、残念ながらcaseの場合と比較してみると100倍位遅いことが多いです。

(defun 256way/vector (i)
  (let ((rand (random 10)))
    (macrolet ((fcase (i &body body)
                 `(funcall
                   (svref (vector ,@(loop :for b :in body
                                          :collect `(lambda () ,b)))
                          ,i))))
      (fcase i
             . #.(loop :for x :from 0 :repeat 256
                       :collect `(progn (* i rand)))))))

(defun 256way/case (i)
  (let ((rand (random 10)))
    (case i
      . #.(loop :for x :from 0 :repeat 256
                :collect `((,x) (progn (* i rand)))))))

(let (tem)
  (dotimes (i 1000000 tem)
    (setq tem (256way/vector 255))))
;=> 2040
#|------------------------------------------------------------|
Evaluation took:
  2.568 seconds of real time
  2.572000 seconds of total run time (2.568000 user, 0.004000 system)
  [ Run times consist of 0.052 seconds GC time, and 2.520 seconds non-GC time. ]
  100.16% CPU
  8,455,561,305 processor cycles
  10,256,001,056 bytes consed
Intel(R) Xeon(R) CPU E3-1230 v3 @ 3.30GHz
 |------------------------------------------------------------|#
(let (tem)
  (dotimes (i 1000000 tem)
    (setq tem (256way/vector 0))))
;=> 0
#|------------------------------------------------------------|
Evaluation took:
  2.608 seconds of real time
  2.612000 seconds of total run time (2.596000 user, 0.016000 system)
  [ Run times consist of 0.068 seconds GC time, and 2.544 seconds non-GC time. ]
  100.15% CPU
  8,586,032,115 processor cycles
  10,255,968,880 bytes consed
Intel(R) Xeon(R) CPU E3-1230 v3 @ 3.30GHz
 |------------------------------------------------------------|#

(let (tem)
  (dotimes (i 1000000 tem)
    (setq tem (256way/case 0))))
;=> 0
#|------------------------------------------------------------|
Evaluation took:
  0.026 seconds of real time
  0.028000 seconds of total run time (0.028000 user, 0.000000 system)
  107.69% CPU
  85,510,905 processor cycles
  0 bytes consed
Intel(R) Xeon(R) CPU E3-1230 v3 @ 3.30GHz
 |------------------------------------------------------------|#

(let (tem)
  (dotimes (i 1000000 tem)
    (setq tem (256way/case 255))))
;=> 2295
#|------------------------------------------------------------|
Evaluation took:
  0.169 seconds of real time
  0.168000 seconds of total run time (0.168000 user, 0.000000 system)
  99.41% CPU
  555,737,934 processor cycles
  0 bytes consed
Intel(R) Xeon(R) CPU E3-1230 v3 @ 3.30GHz
 |------------------------------------------------------------|#

何もしていないcaseで一番遅い場合より遅いので、速度という面では何もしない方が良いケースが多そうです。

諦めない

しかし、ここで一頑張りした例があり、load-time-valueでクロージャーの配列をロード時に固定しようというアイデアがあります。
アイデアとしては処理系が用意する分岐テーブルを自前で用意するのに近いです。 

(defun 256way/ncase (i)
  (ncase i
         . #.(loop :for x :from 0 :repeat 256
                   :collect `((,x) (progn (* ,x (random 10)))))))

(let (tem)
  (dotimes (i 1000000 tem)
    (setq tem (256way/ncase 255))))
;=> 1020
#|------------------------------------------------------------|
Evaluation took:
  0.031 seconds of real time
  0.032000 seconds of total run time (0.032000 user, 0.000000 system)
  103.23% CPU
  103,156,092 processor cycles
  0 bytes consed
Intel(R) Xeon(R) CPU E3-1230 v3 @ 3.30GHz
 |------------------------------------------------------------|#

これだと結構速度が出ていてcaseの時より速い位ですが、実はコードが違っていることに気付いたでしょうか。
ncaseはload-time-valueを利用するためフォームの周りのローカル変数は取り込めず等価なコードは実現できないのです。惜しい。

まとめ

環境を捕捉できるncaseがあれば解決かなと思いますが、可能なのでしょうか。自分は無理かなあと思っています。
何にしろ、多分、捕捉したら遅くなるのでしょう。
変数を捕捉する必要がないのならば、load-time-valueを使うのは有力なテクニックかなと思います。

■

HTML generated by 3bmd in SBCL 1.2.12

comments powered by Disqus