#: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の時より速い位ですが、実はコードが違っていることに気付いたでしょうか。
ncaseload-time-valueを利用するためフォームの周りのローカル変数は取り込めず等価なコードは実現できないのです。惜しい。

まとめ

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


HTML generated by 3bmd in SBCL 1.2.12

comments powered by Disqus