型分岐最適化

sbcl(1.0.28)は、適切に型宣言を行っておけば、冗長な型判定を実行コードから除外してくれるようだ。

例えば次のようなマクロを定義する。

(defmacro get-type (obj)
  `(typecase ,obj
     (list   :list)
     (fixnum :fixnum)
     (vector :vector)
     (t      :others)))

; ↓のような定義でも可
;(defmacro get-type (obj)
;  `(cond ((typep ,obj 'list)   :list)
;         ((typep ,obj 'fixnum) :fixnum)
;         ((typep ,obj 'vector) :vector)
;         (t                    :others)))

これは単純にobjに対応する型名を返すだけものだが、これをdisassembleすると次のような結果となる。

(disassemble
  (lambda (obj)
    (declare (optimize (safety 0)))  ; disassembleの出力を見やすくするために(safety 0)を宣言
    (get-type obj)))

;disassembly for (LAMBDA (OBJ))
; 0B197ECC:       8BC1             MOV EAX, ECX               ; no-arg-parsing entry point
;      ECE:       2407             AND AL, 7
;      ED0:       3C03             CMP AL, 3
;      ED2:       750B             JNE L1
;      ED4:       8B15987E190B     MOV EDX, [#xB197E98]       ; :LIST
;      EDA: L0:   8BE5             MOV ESP, EBP
; ... 省略 ...
;      EFB:       3CF6             CMP AL, 246
;      EFD:       7608             JBE L3
;      EFF: L2:   8B159C7E190B     MOV EDX, [#xB197E9C]       ; :OTHERS
;      F05:       EBD3             JMP L0
;      F07: L3:   8B15A07E190B     MOV EDX, [#xB197EA0]       ; :VECTOR
;      F0D:       EBCB             JMP L0
;      F0F: L4:   8B15A47E190B     MOV EDX, [#xB197EA4]       ; :FIXNUM
;      F15:       EBC3             JMP L0

出力コード(のコメント)の中に:LISTや:VECTORなどが含まれていることが見てとれる。
「objの型を検査して、分岐し、結果(keyword)を返す」というようなことをやっているのだろう。
ほぼマクロの定義通りのコードといった感じだ。


今度は、同じものに型宣言を加えて、再度disassembleを行う。

(disassemble
  (lambda (obj)
    (declare (optimize (safety 0))
             (list obj))           ; objはlist型
    (get-type obj)))

; disassembly for (LAMBDA (OBJ))
; 0B1C9562:       8B1538951C0B     MOV EDX, [#xB1C9538]       ; :LIST
                                                              ; no-arg-parsing entry point
;        8:       8BE5             MOV ESP, EBP
;        A:       F8               CLC
;        B:       5D               POP EBP
;        C:       C3               RET

型宣言(この場合はlist型)を加えると、出力させるコードは明らかに短くなっており、宣言された型以外に対応する節が完全に除外されていることが分かる。
ちゃんと型宣言をみて、最適化が行われているようだ。


この型宣言による最適化があると、ある種の汎用的な関数が(気分的に)書きやすくなるので嬉しい。
例えば、次のコード。

;; 標準のeltと似た動作をする関数をinline宣言付きで定義
(declaim (inline %elt))
(defun %elt (object index)
  (typecase object
    (list   (nth index object))
    (string (char object index))
    (array  (aref object index))))

;;;;;;;;
;;;; 型宣言付きで%eltを使う場合と、charを直接使う場合を比較
(disassemble
 (lambda (x i) 
   (declare (optimize (safety 0)) (string x))
   (%elt x i)))

(disassemble 
 (lambda (x i) 
   (declare (optimize (safety 0)))
   (char x i)))

;; どちらも同じ結果(↓)を出力する
; disassembly for (LAMBDA (X I))
; 0B1E7077:       8B7DFC           MOV EDI, [EBP-4]           ; no-arg-parsing entry point
;       7A:       8BD6             MOV EDX, ESI
;       7C:       8B0548701E0B     MOV EAX, [#xB1E7048]       ; #<FDEFINITION object for SB-KERNEL:HAIRY-DATA-VECTOR-REF>
;       82:       B908000000       MOV ECX, 8
;       87:       FF7504           PUSH DWORD PTR [EBP+4]
;       8A:       FF6005           JMP DWORD PTR [EAX+5]
NIL

%eltは複数の型に対応する汎用的なアクセサだが、型宣言を付与することで、より特殊な関数を直接呼び出すのと同じ効果が得られている。※ applyを適用した場合は異なる?
そのため、型分岐のオーバヘッドを嫌って、わざわざ個別に(elt-char、elt-vectorelt-xxx)関数を定義し使用する必要性が(完全にではないにしても、ある程度は)なくなるように思う。


残念なのは、この最適化は処理系(この場合は、sbcl)依存だということだ。
試しにclispで同様のコードを実行してみたところ、上記最適化は行われていなかった。※ ただし、僕はclispをほとんど使わないので分からないが、何かを上手くやれば最適化されるかもしれない