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