読者です 読者をやめる 読者になる 読者になる

レガシーコード生産ガイド

私に教えられることなら

Common Lispの最適化に挑戦してみる

CommonLisp

今まで最適化についてよくわかってなかったんだけど、自作Forthのベンチマーク計測といっしょに挑戦してみることにした。処理系はSBCL

同じように最適化についてまったくわからない人のために理解の軌跡をメモしておく。

まず他の言語の計測結果を再掲する。ついでにChromeのV8でも計測しておく。

C (-O2) 0.22
C 0.45
JavaScript(V8) 0.73
Squeak(method) 0.99
forth 1.66
Squeak(block) 2.27
Gauche 6.52

さて、CommonLispを計ってみる。まずはそのまま素のコード。

(defun fib (n)
  (if (> 2 n) n
      (+ (fib (- n 1))
         (fib (- n 2)))))

1.50秒だった。厳密ではないと思うけど、10回やった平均値を見ていく。

http://cl.cddddr.org/index.cgi?%BA%C7%C5%AC%B2%BDを参考にしつつ、最適化の宣言をつけてみる。

(defun fib (n)
  (declare (optimize (speed 3) (debug 0) (safety 0)))
  (if (> 2 n) n
      (+ (fib (- n 1))
         (fib (- n 2)))))

1.30秒。いろいろ警告が出てる。上手く最適化できてないみたいだ。ここからdisassembleを使ってコンパイル後のコードを見ていく。

(disassemble 'fib)すると

; disassembly for FIB
; Size: 152 bytes
; 05AF8165:       48895DF0         MOV [RBP-16], RBX          ; no-arg-parsing entry point
;       69:       BF04000000       MOV EDI, 4
;       6E:       488BD3           MOV RDX, RBX
;       71:       B9F5030020       MOV ECX, 536871925         ; GENERIC-<

(省略)

;       92:       41BB5C020020     MOV R11D, 536871516        ; GENERIC--

(省略)

;       C5:       41BB5C020020     MOV R11D, 536871516        ; GENERIC--

(省略)

;       EF:       41BBF0010020     MOV R11D, 536871408        ; GENERIC-+
;       F5:       41FFD3           CALL R11
;       F8:       488BCA           MOV RCX, RDX
;       FB:       EB84             JMP L0

と、何箇所かGENERICと書かれてるのが目につく。おそらく総称関数的に変数の型を判定している分遅くなってるんだろう、ということで変数の型を宣言してみる。(fib 39)がおさまればいいので、fixnumを選ぶ。

(defun fib (n)
  (declare
   (type fixnum n)
   (optimize (speed 3) (debug 0) (safety 0)))
  (if (> 2 n) n
      (+ (fib (- n 1))
         (fib (- n 2)))))

結果は0.64秒!劇的に速くなった!V8より速い。

しかしdisassembleすると、一個だけGENERICが残っている。

; 02DC3722:       4883FA04         CMP RDX, 4                 ; no-arg-parsing entry point

( 省略 )

;       7F:       41BBF0010020     MOV R11D, 536871408        ; GENERIC-+
;       85:       41FFD3           CALL R11
;       88:       488BCA           MOV RCX, RDX
;       8B:       EB9E             JMP L0

警告も併せて見ると、fib n-1fib n-2の結果を足してるところで型を判定している。fibの返り値がわからないみたいだ。

関数呼び出しの返り値の型を指定するには、

  1. 関数の返り値の型を宣言する
  2. 呼び出し時にtheで受け取る型を宣言する

と2つの方法があるみたいだ。どっちもやってみる。まずはtheから。

(defun fib (n)
  (declare
   (type fixnum n)
   (optimize (speed 3) (debug 0) (safety 0)))
  (if (> 2 n) n
      (+ (the fixnum (fib (- n 1)))
         (the fixnum (fib (- n 2))))))

続いて、トップレベルでfibの返り値の型を宣言する方法。

(declaim (ftype (function (fixnum) fixnum) fib))
(defun fib (n)
  (declare
   (optimize (speed 3) (debug 0) (safety 0))
   (type fixnum n))
  (if (> 2 n) n
      (+ (fib (- n 1))
         (fib (- n 2)))))

これでどちらも同じアセンブリコードになった。結果は0.57秒。後者は引数についての型はftypeで宣言してるから不要かと思ったけど、declareの方も無いとダメみたいだ。

この時点でdisassembleの結果は以下なんだけど、まだ大分大きいように思える。

; disassembly for FIB
; Size: 139 bytes
; 03EBBB22:       4883FA04         CMP RDX, 4                 ; no-arg-parsing entry point
;       26:       7D1C             JNL L2
;       28:       488BCA           MOV RCX, RDX
;       2B:       48D1F9           SAR RCX, 1
;       2E: L0:   48D1E1           SHL RCX, 1
;       31:       710C             JNO L1
;       33:       48D1D9           RCR RCX, 1
;       36:       41BBA8050020     MOV R11D, 536872360        ; ALLOC-SIGNED-BIGNUM-IN-RCX
;       3C:       41FFD3           CALL R11
;       3F: L1:   488BE5           MOV RSP, RBP
;       42:       5D               POP RBP
;       43:       C3               RET
;       44: L2:   488955F0         MOV [RBP-16], RDX
;       48:       488BCA           MOV RCX, RDX
;       4B:       4883E902         SUB RCX, 2
;       4F:       488BDD           MOV RBX, RBP
;       52:       488D4424F0       LEA RAX, [RSP-16]
;       57:       4883EC20         SUB RSP, 32
;       5B:       488BD1           MOV RDX, RCX
;       5E:       488918           MOV [RAX], RBX
;       61:       488BE8           MOV RBP, RAX
;       64:       E8B6FFFFFF       CALL #x1003EBBB1F
;       69:       488B55F0         MOV RDX, [RBP-16]
;       6D:       488BC1           MOV RAX, RCX
;       70:       48D1F9           SAR RCX, 1
;       73:       7304             JNB L3
;       75:       488B48F9         MOV RCX, [RAX-7]
;       79: L3:   48894DF8         MOV [RBP-8], RCX
;       7D:       4883EA04         SUB RDX, 4
;       81:       488BCD           MOV RCX, RBP
;       84:       488D4424F0       LEA RAX, [RSP-16]
;       89:       4883EC20         SUB RSP, 32
;       8D:       488908           MOV [RAX], RCX
;       90:       488BE8           MOV RBP, RAX
;       93:       E887FFFFFF       CALL #x1003EBBB1F
;       98:       488BD1           MOV RDX, RCX
;       9B:       48D1FA           SAR RDX, 1
;       9E:       7304             JNB L4
;       A0:       488B51F9         MOV RDX, [RCX-7]
;       A4: L4:   488B4DF8         MOV RCX, [RBP-8]
;       A8:       4801D1           ADD RCX, RDX
;       AB:       EB81             JMP L0

最終的に#:g1: SBCLでVOPを使ってみようみたいな話なるのかな?とりあえずここまで。

C (-O2) 0.22
C 0.45
CommonLisp(SBCL, typed) 0.57
JavaScript(V8) 0.73
Squeak(method) 0.99
CommonLisp(SBCL) 1.50
forth 1.66
Squeak(block) 2.27
Gauche 6.52
広告を非表示にする