#:g1: deftransformの紹介

Posted 2014-04-27 15:00:00 GMT

(LISP Library 365参加エントリ)

 LISP Library 365 の118日目です。

deftransformとはなにか

 deftransformは、CMUCL等のPythonコンパイラの処理系で利用できる最適化のための機能です。

インストール方法

 CMUCL等Pythonコンパイラ系で利用できます〈SBCL/SCL/CMUCL〉。
deftransform/defknownは、SBCLでは、SB-Cパッケージ、CMUCL/Scieneer CLでは、C〈COMPILER〉パッケージに含まれています。

試してみる

 Common Lispの最適化/高速化は基本的に実行時において無駄な部分を削る感じになります。
具体的には、実行時の型チェックを外したり、引数の数やキーワード引数/オプショナル引数の使われ方がコンパイル時に判明している場合は、実行時判定しないものに置き換えてしまったりします。

 大抵の場合には、コンパイラマクロ位で用は済むのですが、コンパイラマクロが基本的に型情報を扱うことができない所為で、いまいちだなと思うことがたまにありました。〈勿論、コンパイラマクロの展開時に定数になっているものは型が判別できます〉。

 この辺りの問題が、deftransformで解決できるようなので簡単に紹介してみます。

 こういう構成のgeneric:+というものがあるとします。


(defpackage generic 
  (:use)
  (:export :+))

(defun generic:+ (&rest args) (reduce #'+_2op args :initial-value (etypecase (car args) (NUMBER 0) (STRING (make-string 0)) (VECTOR (make-sequence 'vector 0)) (LIST (make-list 0)))))

(defun +_2op (x y) (cond ((and (numberp x) (numberp y)) (+ x y)) ((and (stringp x) (stringp y)) (concatenate 'string x y)) ((and (listp x) (listp y)) (concatenate 'list x y)) ((and (and (vectorp x) (not (stringp x))) (and (vectorp y) (not (stringp y)))) (concatenate 'vector x y)) (T (error "Type mismatch: (~S ~S)." x y))))

 文字列等、シークエンスも数字も扱えるような関数です。

(generic:+ 1 1)
;=>  2

(generic:+ '(a b c) '(d e f)) ;=> (A B C D E F)

(generic:+ "abc" "def") ;=> "abcdef"

 これはこれで良いのですが、型が決まっているような状況で遅いのが気になります。計測してみると、数値専用の関数を利用した場合と比べても10倍以上遅いようです。

(defun tak (x y z)
  (declare (optimize (debug 0) (safety 0) (speed 3))
           (fixnum x y z))
  (if (<= x y)
      z
      (tak (tak (generic:+ -1 x) y z)
           (tak (generic:+ -1 y) z x)
           (tak (generic:+ -1 z) x y))))

(tak 18 9 0) ;=> 9 #|------------------------------------------------------------| Evaluation took: 2.272 seconds of real time 2.272142 seconds of total run time (2.216139 user, 0.056003 system) [ Run times consist of 0.040 seconds GC time, and 2.233 seconds non-GC time. ] 100.00% CPU 5,439,652,227 processor cycles 379,901,584 bytes consed

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

(defun tak-normal (x y z) (declare (optimize (debug 0) (safety 0) (speed 3)) (fixnum x y z)) (if (<= x y) z (tak-normal (tak-normal (+ -1 x) y z) (tak-normal (+ -1 y) z x) (tak-normal (+ -1 z) x y))))

(tak-normal 18 9 0) ;=> 9 #|------------------------------------------------------------| Evaluation took: 0.167 seconds of real time 0.164011 seconds of total run time (0.164011 user, 0.000000 system) 98.20% CPU 398,458,152 processor cycles 0 bytes consed

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

 書き直せば良いという話もありますが、ここは最適化でがんばってみましょう。
まずは、可変長引数の処理をコンパイラマクロを利用して実行時からコンパイル時に移動してみます。

(define-compiler-macro generic:+ (&rest args)
  (reduce (lambda (x form)
            `(+_2op ,x ,form))
          args
          :initial-value `(etypecase ,(car args)
                            (NUMBER 0)
                            (STRING (make-string 0))
                            (VECTOR (make-sequence 'vector 0))
                            (LIST (make-list 0)))
          :from-end T))
(tak 18 9 0)
;=> 9
#|------------------------------------------------------------|
Evaluation took:
  0.485 seconds of real time
  0.484030 seconds of total run time (0.484030 user, 0.000000 system)
  99.79% CPU
  1,161,442,746 processor cycles
  0 bytes consed

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

 大分速くなりました。コンパイラマクロを展開すると(generic:+ -1 z)は

(+_2OP -1 
       (+_2OP Z
              (ETYPECASE -1
                (NUMBER 0)
                (STRING (MAKE-STRING 0))
                (VECTOR (MAKE-SEQUENCE 'VECTOR 0))
                (LIST (MAKE-LIST 0)))))

となっているので、速くなるのは分かります。しかし、+_2opが扱うのはFIXNUMであることをDECLAREで指定しているので、+_2op内部で改めてわざわざ判定しているのが勿体無いというところです。
この隔靴掻痒感をdeftransformでどうにかしてみます。

(sb-c:defknown +_2op (t t) t)

(sb-c:deftransform +_2op ((x y) (fixnum fixnum)) `(cl:+ x y))

 deftransformは、コンパイラマクロっぽいですが、コンパイラの最適化で作用します。〈ICR(Implicit Continuation Representation)の最適化の際に変換されるようです。〉
上記の例では、2つの引数がどちらもFIXNUMの場合の式の変換方法を指定しています。

(tak 18 9 0)
;=> 9
#|------------------------------------------------------------|
Evaluation took:
  0.169 seconds of real time
  0.168010 seconds of total run time (0.168010 user, 0.000000 system)
  99.41% CPU
  404,691,399 processor cycles
  0 bytes consed

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

 DISASSEMBLEすると+_2opが消えているのも確認できます。

; disassembly for TAK (assembled 225 bytes)
L0:     CMP R13, RAX                    ; no-arg-parsing entry point
        JLE L1
        MOV [RBP-24], RCX
        MOV [RBP-32], R13
        MOV [RBP-40], RAX
        LEA RSI, [R13-2]
        MOV RDI, RBP
        LEA RDX, [RSP-16]
        SUB RSP, 56
        MOV R13, RSI
        MOV [RDX], RDI
        MOV RBP, RDX
        CALL #x1018BDCD7B
        MOV RCX, [RBP-24]
        MOV R13, [RBP-32]
        MOV RAX, [RBP-40]
        MOV [RBP-8], RDI
        MOV RSI, RAX
        SAR RSI, 1
        ADD RSI, -1
        MOV R8, R13
        MOV RDI, RBP
        SHL RSI, 1
        LEA R9, [RCX+RCX]
        SAR R8, 1
        LEA RDX, [RSP-16]
        SUB RSP, 56
        MOV R13, RSI
        MOV RAX, R9
        MOV RCX, R8
        MOV [RDX], RDI
        MOV RBP, RDX
        CALL #x1018BDCD7B
        MOV RAX, [RBP-40]
        MOV R13, [RBP-32]
        MOV RCX, [RBP-24]
        MOV R8, RDI
        MOV [RBP-16], R8
        LEA RBX, [RCX-1]
        MOV RDI, R13
        MOV R10, RAX
        MOV RSI, RBP
        SHL RBX, 1
        SAR R10, 1
        LEA RDX, [RSP-16]
        SUB RSP, 56
        MOV R13, RBX
        MOV RAX, RDI
        MOV RCX, R10
        MOV [RDX], RSI
        MOV RBP, RDX
        CALL #x1018BDCD7B
        MOV R8, [RBP-16]
        MOV R13, [RBP-8]
        MOV RAX, R8
        MOV RCX, RDI
        SAR RCX, 1
        JMP L0
L1:     MOV R10, RCX
        SHL R10, 1
        MOV RDI, R10
        MOV RSP, RBP
        POP RBP
        RET

 ちなみに、比べてみると分かりますが、CL:+を使ったものとDISASSEMBLEの結果は同じになっているので、速度も全く同じということになります。

関連

まとめ

 今回は、deftransformを紹介してみました。
上記の例は、deftransformの初歩的なところです。もっと突っ込んだことが色々できるようですので、面白いと思った方は試してみて、記事でも書いてもらえると嬉しいです。
ちなみに、参考資料ですが、ウェブにもほとんど転がっていないようで、処理系内部での使われ方を参照する他ないようです。
deftransformは、完全に処理系依存機能ですが、他の処理系でもこういった類の最適化ができないかを調べてみたいと思います。

comments powered by Disqus