インライン展開手作り風味 — #:g1

Posted 2011-11-08 23:07:00 GMT

Clojure 1.3 のパフォーマンスに驚いた話を読んで、なるほどインライン展開が肝なら、手動で展開すれば良いんじゃないだろうかと思って作ってみました。

(defmacro adefun (name args &body body)
  `(defun ,name (,@args)
     (macrolet ((self (,@args) `(,',name ,,@args)))
       ,@body)))

(eval-when (:compile-toplevel :load-toplevel :execute) (adefun rename-to-inline (new old expr) (cond ((atom expr) expr) ((consp (car expr)) (cons (cond ((eq 'cl:quote (caar expr)) (car expr) ) ((eq old (caar expr)) (cons new (cdar expr)) ) (T (self new old (car expr))) ) (self new old (cdr expr)) )) (T (cons (car expr) (self new old (cdr expr)) )))))

(declaim (type (unsigned-byte 4) *depth*)) (defvar *depth* 0)

(defmacro defun-inline-self (name level (&rest args) &body body) (let* ((inline-name (gensym (format nil "INLINE-~A-" name))) (gargs (map-into (copy-list args) #'gensym)) (binds (mapcar (lambda (x y) ``(,',x ,,y)) args gargs))) `(defun ,name (,@args) (macrolet ((,inline-name (,@gargs) (if (< ,level *depth*) `(let (,,@binds) ,@',body ) `(compiler-let ((*depth* (1+ *depth*))) (let (,,@binds) ,@',(rename-to-inline inline-name name body )))))) ,@(rename-to-inline inline-name name body )))))

展開をする際に展開を制御しないと無限に展開されてしまうのが問題になりますが、今回は、CLtL1にはあった、compiler-letを使って一定回数以上展開されないように制御してみています。 使い方ですが、
(defun-inline-self name depth (args) ...)
のように使います。 ほぼdefunと同じですが、展開する深さを名前の後に指定します。 ■ さて、果してこれが効果があるのかを計時してみます。 まず、件のエントリーで紹介されているCの実装
% gcc -O3 fib.c
% time ./a.out
./a.out  0.26s user 0.00s system 95% cpu 0.273 total
ということで、0.273sが目標になります。ディスアセンブルした行数の求め方が良く分からないのですが、
% ndisasm ./a.out|wc -l
4129
というところでした。 以下の動作環境はSBCL 1.0.53です。 まず、最適化オプションを付けてコンパイルしたもの
(locally
  (declare (optimize
            (safety 0) (speed 3) (debug 0)))

(defun fib-nomal (n) (declare (fixnum n)) (the fixnum (if (<= n 1) 1 (+ (fib-nomal (1- n)) (fib-nomal (- n 2)) )))))

(fib-nomal 38) ;⇒ 63245986 ---------- Evaluation took: 0.855 seconds of real time 0.840000 seconds of total run time (0.840000 user, 0.000000 system) 98.25% CPU 2,047,746,762 processor cycles 0 bytes consed

Intel(R) Core(TM)2 Duo CPU P8600 @ 2.40GHz

一応最適化してあるのですが、3倍位遅いです。ディスアセンブルした行数は、30行。 次に同じものをinline宣言したもの
(declaim (inline fib-inline))

(locally (declare (optimize (safety 0) (speed 3) (debug 0)))

(defun fib-inline (n) (declare (fixnum n)) (the fixnum (if (<= n 1) 1 (+ (fib-inline (1- n)) (fib-inline (- n 2)) )))))

(fib-inline 38) ;⇒ 63245986 ---------- Evaluation took: 0.664 seconds of real time 0.660000 seconds of total run time (0.660000 user, 0.000000 system) 99.40% CPU 1,590,673,338 processor cycles 80 bytes consed

Intel(R) Core(TM)2 Duo CPU P8600 @ 2.40GHz

展開しきれていないという警告が出ますが、一応インライン展開しています。ディスアセンブルした行数は、60行。 インライン展開しても、時間は、Cの約2倍の時間がかかっています。 さて、今回作った手作りインライン展開マクロ。 展開は、深さ4で展開します。ちなみに展開された後は下記のような感じで2350行になります。
(PROGN
 (EVAL-WHEN (:COMPILE-TOPLEVEL) (SB-C:%COMPILER-DEFUN 'MY-FIB-INLINE 'NIL T))
 (EVAL-WHEN (:LOAD-TOPLEVEL :EXECUTE)
   (SB-IMPL::%DEFUN
    'MY-FIB-INLINE
    (SB-INT:NAMED-LAMBDA MY-FIB-INLINE (N)
      (BLOCK MY-FIB-INLINE
        (MACROLET ((#:INLINE-MY-FIB-INLINE-1296 (#:G1297)
                     (IF (< 4 ROOT.FUNCTION.INLINE1-INTERNAL::*DEPTH*)
                         `(LET ((N ,#:G1297))
                            (DECLARE (FIXNUM N))
                            (THE FIXNUM
                              (IF (<= N 1)
                                  1
                                  (+ (MY-FIB-INLINE (1- N))
                                     (MY-FIB-INLINE (- N 2))))))
                         `(SB-CLTL2:COMPILER-LET
                               ((ROOT.FUNCTION.INLINE1-INTERNAL::*DEPTH*
                                 (1+ ROOT.FUNCTION.INLINE1-INTERNAL::*DEPTH*)))
                            (LET ((N ,#:G1297))
                              (DECLARE (FIXNUM N))
                              (THE FIXNUM
                                (IF (<= N 1)
                                    1
                                    (+ (#:INLINE-MY-FIB-INLINE-1296 (1- N))
                                       (#:INLINE-MY-FIB-INLINE-1296 (- N 2))))))))))
          (DECLARE (FIXNUM N))
          (THE FIXNUM
            (IF (<= N 1)
                1
                (+
                 (SB-CLTL2:COMPILER-LET
                      ((ROOT.FUNCTION.INLINE1-INTERNAL::*DEPTH*
                        (1+
                         ROOT.FUNCTION.INLINE1-INTERNAL::*DEPTH*)))
                   (LET ((N (1- N)))
                     (DECLARE (FIXNUM N))
                     (THE FIXNUM
                       (IF (<= N 1)
                           1
                           .....
(locally
  (declare (optimize
            (safety 0) (speed 3) (debug 0)))

(defun-inline-self my-fib-inline 4 (n) (declare (fixnum n)) (the fixnum (if (<= n 1) 1 (+ (my-fib-inline (1- n)) (my-fib-inline (- n 2)) )))))

(my-fib-inline 38) ;⇒ 63245986 ---------- Evaluation took: 0.266 seconds of real time 0.260000 seconds of total run time (0.260000 user, 0.000000 system) 97.74% CPU 635,394,249 processor cycles 0 bytes consed

Intel(R) Core(TM)2 Duo CPU P8600 @ 2.40GHz

がんばった甲斐があって、Cと同じ位の速度になりました。ちなみにディスアセンブルした行数は、2550行になります。 ■ 他にも効果があるのかと思って試してみましたが、大した速度向上は見られませんでした。 fibのようなものはインライン展開が効果的、ということみたいです。 ■

comments powered by Disqus