LISPUSER

LISPMEMOLisp isn't a language, it's a building material. -- Alan Kay

(top)  (memo)  (rss)

自力で最適化コンパイル コンパイラマクロ

あろはさんところ (http://alohakun.blog7.fc2.com/blog-entry-701.html ) の GCC の最適化関連の話らしいネタ で Shiro さんのコメントに compiler-macro がさらっと出てきいたので。

CommonLisp処理系の多くは、formatの文字列が定数ならコンパイル時に「format文字列をコンパイル」 します。つまりformat文字列を解釈して行われるであろう動作を直接コードとして吐き出します。 前にコメントしたcompiler-macroを使ってるんで、デフォルトの最適化に不満があれば 自分で最適化するコードを書いてオーバライドできます。

Allegro CLに書いた正規表現ライブラリでも、正規表現が定数文字列の時はコンパイル時に 「その正規表現に従って実行するプログラム」を生成してコンパイルするようなcompiler-macro を書きました。

まあ、アドホックな職人技の世界ではありますね。

ここで compiler-macro とはなんぞや?と思った人や、ふつうのマクロを思いうかべた人のために 軽く説明しておきます。

C の printf と同様に Lisp でも FORMAT は遅いので、パラメータが全部定数ならコンパイル時に 解決してくれてもいいじゃんと思うことはありませんか?

そこで ANSI CL のコンパイラマクロです。FORMAT はあんまり高速じゃないので、コンパイル時に引数が 定数のみなら超絶最適化をかましてしみます。

(defun fast-format (stream fmt &rest args)
  "format を呼び出す (インタプリタとコンパイラが分離している環境のインタプリタ向け)"
  (apply #'format `(,stream ,fmt ,@args)))

(define-compiler-macro fast-format (stream fmt &rest args)
  "パラメータが全て定数なら (write-string 文字列) にコンパイルする。それ以外は普通の format に"
  (if (every #'constantp args)
    `(write-string ,(apply #'format `(nil ,fmt ,@args)) ,stream)
    `(format ,stream ,fmt ,@args)))

変数が入っていると普通の format ですが、

CL-USER> (disassemble (lambda (x) (fast-format t "~A + ~A = ~A~%" 3 x 8)))
; 10ED3D9A:       BA27000005       MOV EDX, 83886119          ; no-arg-parsing entry point
;       9F:       8B3D683DED10     MOV EDI, [#x10ED3D68]      ; "~A + ~A = ~A~%"
;       A5:       BE0C000000       MOV ESI, 12
;       AA:       8B45F4           MOV EAX, [EBP-12]
;       AD:       8945F0           MOV [EBP-16], EAX
;       B0:       C745EC20000000   MOV DWORD PTR [EBP-20], 32
;       B7:       8B056C3DED10     MOV EAX, [#x10ED3D6C]      ; #<FDEFINITION object for FORMAT>
;       BD:       B914000000       MOV ECX, 20
;       C2:       FF75F8           PUSH DWORD PTR [EBP-8]
;       C5:       FF6005           JMP DWORD PTR [EAX+5]
;       C8:       CC0A             BREAK 10                   ; error trap
;       CA:       02               BYTE #X02
;       CB:       18               BYTE #X18                  ; INVALID-ARG-COUNT-ERROR
;       CC:       4D               BYTE #X4D                  ; ECX
; 
NIL

もし引数が数値もしくは文字のみだと驚異の最適化がかかります。

CL-USER> (disassemble (lambda () (fast-format t "~A + ~A = ~A~%" 3 5 "8")))
; 110A726E:       8B1540720A11     MOV EDX, [#x110A7240]      ; "3 + 5 = 8
                                                              ; "
                                                              ; no-arg-parsing entry point
;       74:       BF27000005       MOV EDI, 83886119
;       79:       8B0544720A11     MOV EAX, [#x110A7244]      ; #<FDEFINITION object for WRITE-STRING>
;       7F:       B908000000       MOV ECX, 8
;       84:       FF75F8           PUSH DWORD PTR [EBP-8]
;       87:       FF6005           JMP DWORD PTR [EAX+5]
;       8A:       90               NOP
;       8B:       90               NOP
;       8C:       90               NOP
;       8D:       90               NOP
;       8E:       90               NOP
;       8F:       90               NOP
;       90:       CC0A             BREAK 10                   ; error trap
;       92:       02               BYTE #X02
;       93:       18               BYTE #X18                  ; INVALID-ARG-COUNT-ERROR
;       94:       4D               BYTE #X4D                  ; ECX
; 
NIL
CL-USER> 

やりました。文字列 + write-string に見事最適化されてします。

興味のある人は ANSI CL の規格書 HyperSpec をどうぞ。実例が見たい場合には Edi Weitz 氏の cl-ppcre 等で使用されています。

posted: 2007/04/01 14:57 | permanent link to this entry | Tags: MISC

(top)  (memo)  (rss)