最適化指針 - lisp-cookbook-ja/common-lisp GitHub Wiki

最適化

コードの最適化についてです。

Lisp方言の中でも特に実用性を重視しているCommon Lispでは、プログラムの比較的低い層まで触れるようになっています。型宣言によってオブジェクトコードから型チェックのコードをなくしたり、変数を動的エクステントとして宣言することでスタックにオブジェクトを作ったり、コンパイルしたコードを逆アセンブルして調整の参考にしたり、といったことは、Common Lispでは普通のことです。

プログラマが積極的に関与できるCommon Lispの最適化の仕組みは、ほかの多くの言語と比べたときに有利な点のひとつであり、コードの性能を確保したいときの助けになってくれるでしょう。

$$toc

最適化宣言

コードを書いてデバッグもした。しかし、コンパイルしたコードを実行してみたらどうも遅い。こういうことは、プログラミングをしているとよくあることです。そういうときは、まず最適化宣言をして、コンパイラに最適化をさせてみましょう。

最適化宣言はoptimize宣言で行います。CLHS: Declaration OPTIMIZEから文法を引用します。

(optimize {''quality'' | (''quality'' ''value'')}*)

qualityは最適化の方向性を表すシンボルです。

:compilation-speed:コンパイル速度 :debug:デバッグのしやすさ :safety:実行時エラーの検査 :space:オブジェクトコードと実行時のメモリの大きさ :speed:オブジェクトコードの速さ

規格で決められているのはこの五種類ですが、処理系がこれ以外のシンボルについて定義しても良いことになっています。実際、Steel Bank Common LispやCMU Common Lisp、LispWorksでは処理系独自のシンボルを使えます。

valueは重要性です。0から3までの整数を指定することができ、大きいほど重要になっていきます。

:0:重要でない :1:普通 :2:1と3の中間 :3:とても重要

valueを省略した場合は3と同じ意味です。valueの値をもとにコンパイラはオブジェクトコードを作りますが、具体的にどんな最適化をどのようにするかは、処理系に任されています。

;; 高速だが実行時の検査を省略していてデバッグもしづらい
;; 最終的なリリース向け
(declaim (optimize (speed 3) (debug 0) (safety 0)))

;; 実行時に検査をしてデバッグもしやすいが遅い
;; 開発途中のデバッグ向け
(declaim (optimize (speed 0) (debug 3) (safety 3)))

optimize宣言をどこですれば良いかは、場合によって変わります。ライブラリを最適化したい場合は、最適化する関数ごとにdeclareを使うか、locallyを使うと良いでしょう。'''トップレベルでdeclaimを使ってはいけません。'''ライブラリをロードするとき、システム全体に影響を与えてしまいます。アプリケーションを最適化したい場合は、システム全体についての宣言をしてからコードをコンパイルすると良いでしょう。

;;; ライブラリ

(defun fact (n)
  ;; 関数についての宣言
  (declare (optimize speed))
  (labels ((rec (n r)
             (if (zerop n) r (rec (1- n) (* n r)))))
    (rec n 1)))

;; locallyの中の式についての宣言
(locally (declare (optimize speed))
  (defun fact (n)
    (labels ((rec (n r)
               (if (zerop n) r (rec (1- n) (* n r)))))
      (rec n 1))))

;; コンパイル時だけシステム全体についての宣言をする
(eval-when (:compile-toplevel)
  (proclaim '(optimize speed)))

;; 上と同じだが紛らわしい
;; 使い方を間違っているのか意図通りなのか分かりにくい
(eval-when (:compile-toplevel)
  (declaim (optimize speed)))

;;; アプリケーション

;; システム全体についての宣言
(declaim (optimize speed))

(compile-file "code.lisp")
(load "code")
(save-application "application"
                  :toplevel-function #'main
                  :prepend-kernel t)

先に進む前に

最適化宣言をしてコンパイラに最適化をさせると、効果の差はありますが、大体は性能が良くなります。おそらく、高速になったり、メモリの消費が少なくなることでしょう。ですが、それでもまだ必要な性能に届かないこともあります。そんなときは、プログラマがコードに手を加えることで、コンパイラにより効果的なオブジェクトコードを作らせることができるかもしれません。いわゆる、手動での最適化です。

しかし、性能が悪いからといって、闇雲にいろいろと手を加えるのはおすすめしません。Donald Knuthの論文から、手動での最適化についてのとても有名な言葉を引用します。

We ''should'' forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.

これは、

  • 些細な効率を追求しても意味がない
  • 最適化のための変更にはデメリットがある

ことを伝えています。

ひとつ目は単純な話です。10秒かかる部分を二倍速くしたら5秒も速くなりますが、1秒かかる部分を二倍速くしても0.5秒です。性能に大きく影響する部分は限られるので、大きな効果を期待するには、それがどこなのか見つけなければなりません。

ふたつ目は、以降の節を読めば理解できるでしょう。手動での最適化は幅広い知識が必要なために難しく、時間もかかります。また、最適化をすると、読みにくく、変更しにくく、デバッグしにくいコードになります。僅かに性能が上がるくらいでは割に合いませんし、コードへの変更がまだ多い段階では作業の邪魔にしかなりません。

手動での最適化は、ある程度コードが完成に近づいてから、''最小限の変更で最大限の効果を得る''ことを考えながらしてください。薬も過ぎれば毒です。

プロファイリング

（書きかけ）

  • イベントベース
  • 統計的

型宣言

type宣言やftype宣言をすることで、変数や関数の型をコンパイラに知らせることができます。また、特殊形式のtheを使うことで、式の結果の型をコンパイラに知らせることができます。''型宣言と実際のオブジェクトの型が一致しなかったときにどうなるかは決められていません。''

コンパイラは型推論で変数や関数の型を決め、自動的に型に合わせた効果的なオブジェクトコードを作りますが、決められた型からは効果的なオブジェクトコードが作れないことがあります。そんなとき、型宣言でコンパイラに型を知らせることで、効果的なオブジェクトコードを作れるようになります。

オブジェクトコードの性能に大きな差が出るため、性能が必要な部分では型宣言をすると良いでしょう。適切な型が選ばれているかどうかは、逆アセンブルの結果を見て判断したり、処理系独自の拡張（例えばSteel Bank Common Lispではdescribeで関数の型を見れます）を使って知ることができます。

(defun plus-vanilla (x y) (+ x y))
(disassemble 'plus-vanilla)
;=> NIL
;->   [0]     (recover-fn)
;     [5]     (cmpl ($ 8) (% temp1))
;     [8]     (jne L66)
;     [10]    (pushl (% ebp))
;     [11]    (movl (% esp) (% ebp))
;     [13]    (pushl (% arg_y))
;     [14]    (pushl (% arg_z))
;   
;   ;;; (+ x y)
;     [15]    (movl (% arg_y) (% imm0))
;     [17]    (orl (% arg_z) (% imm0))
;     [19]    (testb ($ 3) (% imm0.b))
;     [21]    (jne L46)
;     [23]    (addl (% arg_y) (% arg_z))
;     [25]    (jno L60)
;     [27]    (nop)
;     [28]    (leal (@ 0 (% arg_y)) (% arg_y))
;     [32]    (calll (@ .SPFIX-OVERFLOW))
;     [39]    (recover-fn)
;     [44]    (jmp L60)
;   L46
;     [46]    (movl (% arg_y) (% arg_y))
;     [48]    (calll (@ .SPBUILTIN-PLUS))
;     [55]    (recover-fn)
;   L60
;     [60]    (leavel)
;     [61]    (retl)
;   
;   ;;; #<no source text>
;   L66
;     [66]    (uuo-error-wrong-number-of-args)

(defun plus-typed (x y)
  (declare (type fixnum x y))
  (the fixnum (+ x y)))
(disassemble 'plus-typed)
;=> NIL
;->   [0]     (recover-fn)
;     [5]     (cmpl ($ 8) (% temp1))
;     [8]     (jne L26)
;     [10]    (pushl (% ebp))
;     [11]    (movl (% esp) (% ebp))
;     [13]    (pushl (% arg_y))
;     [14]    (pushl (% arg_z))
;   
;   ;;; (the fixnum (+ x y))
;     [15]    (addl (% arg_y) (% arg_z))
;     [17]    (leavel)
;     [18]    (retl)
;   
;   ;;; #<no source text>
;   L26
;     [26]    (uuo-error-wrong-number-of-args)

まず、CLHS: Declaration TYPEからtype宣言の文法を引用します。

(type ''typespec'' ''var''*)

varを束縛するオブジェクトの型がtypespecだとコンパイラに知らせます。また、typeの部分は省略できます。

;; xとyの型はfixnum
(defun plus (x y)
  (declare (type fixnum x y))
  (+ x y))

;; 上の省略形
(defun plus (x y)
  (declare (fixnum x y))
  (+ x y))

次に、CLHS: Declaration FTYPEからftype宣言の文法を引用します。

(ftype ''type'' ''function-name''*)

typeをfunction-nameの型としてコンパイラに知らせます。typeには複合型指定子で特殊化したfunction型を指定します。

;; plusはふたつのfixnumを受け取り整数を返す
(declaim (ftype (function (fixnum fixnum) integer) plus))
(defun plus (x y) (+ x y))

;; ローカル関数についての型宣言
(defun outside (x y)
  (flet ((inside (x y) (+ x y)))
    (declare (ftype (function (fixnum fixnum) integer) inside))
    (inside x y)))

最後に、CLHS: Special Operator THEからtheの文法を引用します。

'''the''' ''value-type'' ''form'' => ''result''*

value-typeを、formの戻り値のresultの型としてコンパイラに伝えます。

;; 結果はfixnum
(the fixnum (+ 4 5))
;=> 9

;; 結果は符号なし16ビット整数
(the (integer 0 #.(1- (expt 2 16))) (+ 256 128))
(the (unsigned-byte 16) (+ 256 128))
;=> 384

;; 結果は整数と浮動小数点数
(the (values integer float) (truncate 3.2d0))
;=> 3, 0.20000000000000018D0

処理系によってコンパイラの型推論の性能には差があり、どのように型宣言をすれば効果があるのかもそれぞれ違います。詳しいことはそれぞれのマニュアルを読んでください。型宣言（特にthe）はコードを'''非常に読みにくくします'''ので、必要以上に宣言するのは避けたほうが良いでしょう。

インライン展開

inline宣言によって、関数をインライン展開するようコンパイラに指示できます。

関数の呼び出しを節約できるので、呼び出しのオーバヘッドがなくなりますが、オブジェクトコードが大きくなります。インライン展開されたコードが実行されればされるほど効果的です。インナーループで使われる関数についてinline宣言すると良いでしょう。実行される回数が少ないとあまり効果はありません。

(defun sum (a b c d e f) (+ a b c d e f))
(declaim (inline sum-inline))
(defun sum-inline (a b c d e f) (+ a b c d e f))

(progn
  (time (dotimes (n 100000000) (sum n n n n n n)))
  (time (dotimes (n 100000000) (sum-inline n n n n n n))))
;=> NIL
;-> (DOTIMES (N 100000000) (SUM N N N N N N)) took 1,640 milliseconds (1.640 seconds) to run 
;                       with 2 available CPU cores.
;   During that period, 1,640 milliseconds (1.640 seconds) were spent in user mode
;                       0 milliseconds (0.000 seconds) were spent in system mode
;   125 milliseconds (0.125 seconds) was spent in GC.
;    84,172,160 bytes of memory allocated.
;   (DOTIMES (N 100000000) (SUM-INLINE N N N N N N)) took 844 milliseconds (0.844 seconds) to run 
;                       with 2 available CPU cores.
;   During that period, 844 milliseconds (0.844 seconds) were spent in user mode
;                       0 milliseconds (0.000 seconds) were spent in system mode
;    48 bytes of memory allocated.

CLHS: Declaration INLINE, NOTINLINEから文法を引用します。

(inline ''function-name''*)

function-nameを'''定義する前'''にinline宣言をすると、function-nameがインライン展開されるようになります。''ただし、コンパイラはinline宣言を無視して良いことになっているので、確実にインライン展開されるかは保証されません。''

マクロやコンパイラマクロでも似たようなことができますが、それぞれ違いがあります。

;;; インライン関数

;; inline宣言はコンパイラに無視されるかもしれない
(declaim (inline stream-car))
(defun stream-car (stream) (car stream))

;; 関数なので高階関数に渡せる
(apply #'stream-car '((0 1 2))) ;=> 0

;; インライン展開を宣言で制御できる
(defun stream-car-caller (stream)
  (if stream
      (stream-car stream)       ; インライン展開される
      (locally (declare (notinline stream-car))
        (stream-car stream))))  ; インライン展開されない

;; 逆アセンブルして確認
(disassemble 'stream-car-caller)
;=> NIL
;->   [0]     (recover-fn)
;     [5]     (pushl (% ebp))
;     [6]     (movl (% esp) (% ebp))
;     [8]     (pushl (% arg_z))
;   
;   ;;; (if stream (stream-car stream) ; インライン展開される (locally (declare (notinline stream-car)) (stream-car st
;     [9]     (cmpl ($ #x13001) (@ -4 (% ebp)))
;     [16]    (je L24)
;   
;   ;;; (stream-car stream)
;     [18]    (pushl (% arg_z))
;     [19]    (movl (@ 3 (% arg_z)) (% arg_z))
;     [22]    (leavel)
;     [23]    (retl)
;   
;   ;;; (locally (declare (notinline stream-car)) (stream-car stream))
;   L24
;     [24]    (movl (@ -4 (% ebp)) (% arg_z))
;     [27]    (movl ($ 4) (% temp1))
;     [32]    (movl (@ 'STREAM-CAR (% fn)) (% temp0))
;     [38]    (leavel)
;     [39]    (jmpl (@ 6 (% temp0)))

;;; マクロ

;; 常にインライン展開される
(defmacro stream-car (stream) `(car ,stream))

;; マクロなので高階関数には直接渡せない
(apply #'(lambda (x) (stream-car x)) '((0 1 2)))        ;=> 0

;;; コンパイラマクロ

(defun stream-car (stream) (car stream))

;; 常にインライン展開される
(define-compiler-macro stream-car (stream) `(car ,stream))

;; 関数なので高階関数に渡せる
(apply #'stream-car '((0 1 2))) ;=> 0

inline宣言された関数は、高階関数に渡すことができ、インライン展開するかどうかを柔軟に切り替えられ、よりコードの意図が分かりやすくなります。特に問題がなければ、inline宣言をする方が良いでしょう。

気をつけなければいけないことがひとつあります。inline宣言された関数に変更があった場合、マクロと同じで、それを利用しているコードはすべて''再コンパイルしないと変更が反映されません''。これを忘れると、見えないバグに悩まされることになります。

(defun make-point (x y) (cons x y))
(declaim (inline point-x point-y))
(defun point-x (p) (car p))
(defun point-y (p) (cdr p))

(defun print-coordinate (p)
  (format t "(~a, ~a)~%" (point-x p) (point-y p)))

(print-coordinate (make-point 0 1))
;=> NIL
;-> (0, 1)

(defun make-point (x y) (vector x y))
(defun point-x (p) (aref p 0))
(defun point-y (p) (aref p 1))

(print-coordinate (make-point 0 1))
;>> Error: value #(0 1) is not of the expected type LIST.

動的エクステント

変数や関数についてdynamic-extent宣言をすると、束縛するオブジェクトのエクステントを動的エクステントにできます。

規格では決められていませんが、動的エクステントのオブジェクトはスタックのメモリを割り当てられるのが一般的なので、ヒープのメモリを割り当てられる無限エクステントのオブジェクトよりも高速に扱えます。一時的に使うオブジェクトを作るコストが気になるときにdynamic-extent宣言をすると良いでしょう。

(time (dotimes (n 10000)
        (let ((l (make-list n)))
          (length l))))
;=> NIL
;-> (DOTIMES (N 10000) (LET ((L (MAKE-LIST N))) (LENGTH L))) took 2,875 milliseconds (2.875 seconds) to run 
;                       with 2 available CPU cores.
;   During that period, 2,687 milliseconds (2.687 seconds) were spent in user mode
;                       78 milliseconds (0.078 seconds) were spent in system mode
;   2,172 milliseconds (2.172 seconds) was spent in GC.
;    399,960,048 bytes of memory allocated.

(time (dotimes (n 10000)
        (let ((l (make-list n)))
          (declare (dynamic-extent l))
          (length l))))
;=> NIL
;-> (DOTIMES (N 10000) (LET ((L (MAKE-LIST N))) (DECLARE (DYNAMIC-EXTENT L)) (LENGTH L))) took 1,172 milliseconds (1.172 seconds) to run 
;                       with 2 available CPU cores.
;   During that period, 1,078 milliseconds (1.078 seconds) were spent in user mode
;                       0 milliseconds (0.000 seconds) were spent in system mode
;   812 milliseconds (0.812 seconds) was spent in GC.
;    131,557,360 bytes of memory allocated.

CLHS: Declaration DYNAMIC-EXTENTから文法を引用します。

(dynamic-extent ''var''*)

varあるいはfnを束縛するオブジェクトが動的エクステントになります。''ただし、コンパイラはdynamic-extent宣言を無視して良いことになっているので、確実に動的エクステントになるかは保証されません。''

スコープを抜けると、動的エクステントのオブジェクトは捨てられてしまうので気をつけてください。また、スタックの大きさは限られているので、大きなオブジェクトは置けません。その場合はヒープのメモリを割り当てられるため、大きなオブジェクトについてdynamic-extent宣言しても効果はありません。（コードを読む人へのヒントにはなるかもしれませんが）

(print (let ((l (list 0 1 2)))
         l))
;=> (0 1 2)
;-> (0 1 2)

;; 参照できるが、すでにオブジェクトは捨てられている
(print (let ((l (list 0 1 2)))
         (declare (dynamic-extent l))
         l))
;>> Error: Stack overflow on temp stack.
;-> (((((...

;; スタックに置かれる
(time (let ((l (make-list (1- (* 8 1024)))))
        (declare (dynamic-extent l))
        (car l)))
;=> NIL
;-> (LET ((L (MAKE-LIST (1- (* 8 1024))))) (DECLARE (DYNAMIC-EXTENT L)) (CAR L)) took 0 milliseconds (0.000 seconds) to run 
;                       with 2 available CPU cores.
;   During that period, 0 milliseconds (0.000 seconds) were spent in user mode
;                       0 milliseconds (0.000 seconds) were spent in system mode
;    32 bytes of memory allocated.

;; この環境では64KB以上のオブジェクトはヒープに置かれる
(time (let ((l (make-list (* 8 1024))))
        (declare (dynamic-extent l))
        (car l)))
;=> NIL
;-> (LET ((L (MAKE-LIST (* 8 1024)))) (DECLARE (DYNAMIC-EXTENT L)) (CAR L)) took 0 milliseconds (0.000 seconds) to run 
;                       with 2 available CPU cores.
;   During that period, 0 milliseconds (0.000 seconds) were spent in user mode
;                       0 milliseconds (0.000 seconds) were spent in system mode
;    65,568 bytes of memory allocated.

コンパイラマクロ

（書きかけ）

  • 特定のコードを効果的なコードに変換する
  • 定数であれば実行時に計算して置き換えることすら可能
  • 最適化に非常に有効だが保守性が著しく悪くなる

逆アセンブル

disassembleでコンパイルした関数を逆アセンブルできます。

結果は標準出力に出力されます。規格で決められているので、きちんと準拠している処理系では使えますが、逆アセンブルした結果をどのような形式で出力するかは処理系に任されています。

;; Clozure CL 1.6：LAP（Lisp Assembly Program）
(disassemble 'car)
;=> NIL
;-> ;; "ccl:lib;level-2.lisp.newest":13317-13338
;     [0]     (recover-fn)
;     [5]     (cmpl ($ 4) (% temp1))
;     [8]     (jne L34)
;     [10]    (pushl (% ebp))
;     [11]    (movl (% esp) (% ebp))
;     [13]    (pushl (% arg_z))
;     [14]    (movl (% arg_z) (% imm0))
;     [16]    (andl ($ 7) (% imm0))
;     [19]    (cmpl ($ 1) (% imm0))
;     [22]    (jne L42)
;     [24]    (movl (@ 3 (% arg_z)) (% arg_z))
;     [27]    (leavel)
;     [28]    (retl)
;   L34
;     [34]    (uuo-error-wrong-number-of-args)
;   L42
;     [42]    (uuo-error-reg-not-list (% arg_z))

;; Steel Bank Common Lisp 1.0.45：アセンブリ言語
(disassemble 'car)
;=> NIL
;-> ; disassembly for CAR
;   ; 008D4A30:       488B51F9         MOV RDX, [RCX-7]           ; no-arg-parsing entry point
;   ;       34:       488BE5           MOV RSP, RBP
;   ;       37:       F8               CLC
;   ;       38:       5D               POP RBP
;   ;       39:       C3               RET
;   ;       3A:       CC0A             BREAK 10                   ; error trap
;   ;       3C:       02               BYTE #X02
;   ;       3D:       18               BYTE #X18                  ; INVALID-ARG-COUNT-ERROR
;   ;       3E:       54               BYTE #X54                  ; RCX
;   ;       3F:       CC0A             BREAK 10                   ; error trap
;   ;       41:       02               BYTE #X02
;   ;       42:       02               BYTE #X02                  ; OBJECT-NOT-LIST-ERROR
;   ;       43:       95               BYTE #X95                  ; RDX

;; CLISP 2.48：S式で表現したバイトコード
(disassemble (lambda (x y) (+ x y)))
;=> NIL
;-> 
;   Disassembly of function :LAMBDA
;   2 required arguments
;   0 optional arguments
;   No rest parameter
;   No keyword parameters
;   4 byte-code instructions:
;   0     (LOAD&PUSH 2)
;   1     (LOAD&PUSH 2)
;   2     (CALLSR 2 55)                       ; +
;   5     (SKIP&RET 3)

逆アセンブルの結果をもとに、きちんと最適化されたオブジェクトコードが作られているか確認したり、より効率的なオブジェクトコードが作られるコードを探したりと、最適化の強力な武器になります。

参考文献

⚠️ **GitHub.com Fallback** ⚠️