【Common Lisp】
型宣言でコードを速くする
（declareとdeclaim）

by
  • Common LispはデフォルトでBignumという任意精度整数を使うため、型宣言なしでは実行時に毎回型確認が走り遅くなります。
  • declareで関数内のスコープに、declaimでファイル全体に型情報をコンパイラへ伝えることで、この確認コストを省けます。
  • 特にfixnumやsimple-arrayの型宣言が効果的で、ベンチマークでは型宣言だけで約48%の高速化を確認しました。
  • optimize宣言は型ヒントと組み合わせて初めて機能し、単体では11%程度の改善にとどまります。

関連記事

1. declareとdeclaim

Common Lispはデフォルトで動的型付けです。
変数に型を書かなくても動きます。
ただし「型を書かない」ということは、「実行時に毎回型を確認する」ということでもあります。
競技プログラミングのような速度が要求される場面では、この確認コストが積み重なって遅さの原因になります。

declare と declaim は、コンパイラに型情報を伝えてこの確認を省く仕組みです。

declaredeclaim
スコープ関数・フォームの内側ファイル全体（以降）
書く場所フォームの先頭トップレベル
主な用途変数の型、局所的な最適化inline、全体の最適化方針

型宣言は、基本的にはコードの動作を変えません。
正しく動いているコードなら、型を追加して最適化しても、結果は同じになるはずです。
ただし、型宣言の整合性がないまま safety 0 にした場合には、未定義動作のリスクがあります1。

1.1. 関数やフォーム内の宣言（declare）

declare は関数やフォームの内側に書きます。
そのスコープだけに効きます。

(defun add (a b)
  (declare (type fixnum a b))
  (+ a b))Code language: Lisp (lisp)

書ける場所は「フォームのリストが始まる直後」です2。

(let ((a 0))
  (declare ...)
  ...)

(loop for i from 0 to 100
      declare (type fixnum i)
      ...)Code language: Lisp (lisp)

declare を本体の途中に書くとエラーになります。
必ず先頭に置いてください。

1.2. ファイルに書く（declaim）

declaim は、ファイルのトップレベルに書き、それ以降の全関数に効きます3。

(declaim (optimize (speed 3) (safety 0) (debug 0)))

(defun f (x) ...)  ; この関数にも
(defun g (x) ...)  ; この関数にも効くCode language: Lisp (lisp)

declare との違いはスコープで、基本的に書ける宣言の種類は同じです。

2. declareのtype宣言

Common Lispのパフォーマンスに特に有効なのは、型宣言です。

(declare (type 型名 変数名 変数名 ...))Code language: Lisp (lisp)

同じ型の変数は、型名のあとに複数を並べて書けます。

Common Lispの型指定子は、アトム型と複合型の2種類に分かれ、type の直後が括弧で始まるかどうかで区別されます。

アトム型は型名をシンボルで書くだけです。

(declare (type fixnum n))
(declare (type boolean flag))
(declare (type string s))Code language: Lisp (lisp)

複合型はリスト形式で、先頭に型名、続けてパラメータを書きます。

(declare (type (integer 0 100) n))
(declare (type (simple-array fixnum (*)) v))Code language: Lisp (lisp)

2.1. fixnum

プラットフォームが直接扱える整数です。
64bit環境のSBCLでは -2^62 から 2^62-1 の範囲です4。

(defun sum-to (n)
  (declare (type fixnum n))
  (loop for i fixnum from 0 to n
        sum i fixnum))Code language: Lisp (lisp)

ループ変数にも for i fixnum の形で書けます。

Lispのデフォルト整数は任意精度のbignumなので、ループカウンタや配列インデックスに fixnum を宣言するだけで速くなります。

2.2. simple-array

adjustable や fill-pointer がない単純な配列です。
要素アクセス aref が速くなります5。

(declare (type (simple-array fixnum (*)) freqs))Code language: Lisp (lisp)

カッコ内はサイズで、(*) は任意の長さの1次元配列を意味します。
サイズが決まっているなら (500001) のように書けます。

;; 長さ不定
(type (simple-array fixnum (*)) v)

;; 長さ固定
(type (simple-array fixnum (500001)) v)

;; 2次元
(type (simple-array fixnum (* *)) matrix)Code language: Lisp (lisp)

2.3. その他の型

(declare (type double-float x))       ; 倍精度浮動小数点
(declare (type (integer 0 100) n))    ; 範囲付き整数
(declare (type boolean flag))         ; t か nilCode language: Lisp (lisp)

3. 未使用変数の宣言（declare ignore）

ignore と ignorable の2種類があります。ignore は「この変数は使わない」と宣言し、使おうとするとコンパイラがエラーを出します。ignorable は「使っても使わなくてもよい」という宣言で、警告だけを抑えます。

(defun process (a b _unused)
  (declare (ignore _unused))
  (+ a b))Code language: Lisp (lisp)

複数変数をまとめて書けます。

(declare (ignore x y)
         (ignorable z))Code language: Lisp (lisp)

競技プログラミングでよく出るのは、loop の do 節で返り値を捨てるケースや、多値を受けて一部だけ使うケースです。

(multiple-value-bind (q r)
    (floor n 10)
  (declare (ignore r))
  q)Code language: Lisp (lisp)

ignore は型宣言と違いパフォーマンスへの影響はなく、警告をクリーンに保つための宣言です。

4. declaimのftype宣言

ftype は関数全体の型シグネチャをコンパイラに伝える宣言です。

declare の type が変数単位なのに対し、ftype は引数と戻り値をまとめて一箇所に書けます。

関数定義の前に declaim で書くのが基本パターンです。

(declaim (ftype (function (引数の型...) 戻り値の型) 関数名))Code language: Lisp (lisp)

関数が短く、ファイル内でしか使わないなら declare (type ...) でも十分ですが、
相互再帰関数や他ファイルから呼ばれる関数、let+defun で定義している関数、あるいは引数と戻り値をまとめてドキュメントとして残したい場合には、ftype が有効です。

;; 関数内だけで完結するなら declare で十分
(defun add (a b)
  (declare (type fixnum a b))
  (+ a b))

;; 外部から呼ばれる、または let+defun 構造なら ftype を使う
(declaim (ftype (function (fixnum fixnum) fixnum) add))
(defun add (a b)
  (+ a b))Code language: Lisp (lisp)

declare (type ...) を関数内に書く方法と効果はほぼ同じですが、定義より前に関数の存在を宣言できるため、相互再帰や let+defun の構造でも警告が出なくなります。

4.1. 多値を返す関数

values で複数の値を返す場合は、戻り値を (values ...) で書きます。

(declaim (ftype (function (fixnum fixnum) (values fixnum fixnum)) floor-and-rem))
(defun floor-and-rem (a b)
  (values (floor a b) (mod a b)))Code language: Lisp (lisp)

戻り値が1つもない場合は (values) と書きます。
副作用だけを目的にした関数に使います。

(declaim (ftype (function (fixnum) (values)) print-n))Code language: Lisp (lisp)

4.2. オプション引数・rest引数

&optional と &rest はそのまま書けます。

(declaim (ftype (function (fixnum &optional fixnum) fixnum) clamp-or-abs))Code language: Lisp (lisp)

&rest の場合、残りの引数の型をひとつ書きます。

(declaim (ftype (function (fixnum &rest fixnum) fixnum) sum-all))Code language: Lisp (lisp)

&key も同様に書けますが、コンパイラによってサポートの度合いが異なります。
SBCLでは &key を含む ftype を受け付けますが、最適化への寄与は限定的です。

4.3. 高階関数（functionを引数に取る）

関数を引数に取る場合は、その引数の型を (function ...) で書きます。

(declaim (ftype (function ((function (fixnum) fixnum) fixnum) fixnum) apply-twice))
(defun apply-twice (f n)
  (funcall f (funcall f n)))Code language: Lisp (lisp)

(function (fixnum) fixnum) は「fixnum を受け取り fixnum を返す関数」という型です。
戻り値側に関数型を書くことも同様にできます。

5. declaimのinline宣言

小さな関数を呼び出し箇所に展開させます。
関数呼び出しのオーバーヘッドがなくなります。

inline は関数定義の外から指定するので declaim を使います。

(declaim (inline bottom-freq))
(defun bottom-freq (freqs M)
  (declare (type (simple-array fixnum (*)) freqs)
           (type fixnum M))
  (loop for i from 1 to M
        minimize (aref freqs i)))Code language: Lisp (lisp)

declare (inline bottom-freq) を関数の内側に書いても、自分自身をインライン展開する意味にはならないので注意が必要です。
なおHyperSpecの仕様では、inline 宣言はあくまでコンパイラへのヒントで、コンパイラが無視することも許されています6。
再帰関数などインライン展開できないケースは無視されます。

6. optimize宣言

optimize宣言は、品質指標、つまりコンパイラの「意欲」を上げる宣言です。
関数ごとに declare で宣言することも、declaim で

たとえば、デバッグ不要の実行環境なら、

(declare (optimize (speed 3) (safety 0) (debug 0)))Code language: Lisp (lisp)

ただし、コンパイラにもよりますが、typeの指定などの型ヒントが前提で、optimize宣言だけでは、そこまでパフォーマンスが上がりません。

optimize宣言は、speed、safety、debug、space、compilation-speed の5種類があり、各項目は0から3の数値で指定します7。
SBCLのデフォルト値は、sb-c::*policy* や(sb-ext:describe-compiler-policy)で確認でき、すべて 1 でした。


;=> ((INHIBIT-WARNINGS 1) (SPEED 1) (SPACE 1) (SAFETY 1) (DEBUG 1) (COMPILATION-SPEED 1)) Code language: Lisp (lisp)
  • speed は、実行速度の優先度で、3が最大です。
    高くするとコンパイラがインライン展開やループ最適化をより積極的に行います。
  • safety は、実行時チェックの量です。
    3にすると配列の境界チェックや型チェックをすべて行い、0にすると省略します。
    つまり、0 にすると速くなりますが、バグがあったときにエラーではなく未定義動作になり、気づきにくくなりません8。
  • debug はデバッグ情報の量です。
    0にするとバックトレースが簡素になります。
    開発中は1以上にしておくと、エラー時にどこで落ちたか追いやすくなります。
  • space はコードサイズの優先度で、組み込み開発などで使います。

6.1. 型宣言に比べると optimize の効果は限定的

素数列を求める素朴な関数で、実行速度を比較してみました。

(defun primes-baseline (limit)
  (loop for n from 2 to limit
        when (loop for i from 2 to (isqrt n)
                   never (zerop (mod n i)))
        collect n))Code language: Lisp (lisp)

これに、optimizeやtypeのある・なしでどう変わるかをベンチマーク計測しました。

limit=1000000, 5 runs

baseline          2.8286 sec
optimize only     2.5261 sec  （-11%）
type only         1.4671 sec  （-48%）
optimize + type   1.4566 sec  （-48%）

結果に、大きく影響しているのは type だということがわかります。
optimizeは、「おまじない」みたいな感じですね。

実行したコードは、

(defun primes-optimize (limit)
  (declare (optimize (speed 3) (safety 0) (debug 0)))
  (loop for n from 2 to limit
        when (loop for i from 2 to (isqrt n)
                   never (zerop (mod n i)))
        collect n))

(defun primes-typed (limit)
  (declare (type fixnum limit))
  (loop for n fixnum from 2 to limit
        when (loop for i fixnum from 2 to (isqrt n)
                   never (zerop (mod n i)))
        collect n))

(defun primes-both (limit)
  (declare (optimize (speed 3) (safety 0) (debug 0)))
  (declare (type fixnum limit))
  (loop for n fixnum from 2 to limit
        when (loop for i fixnum from 2 to (isqrt n)
                   never (zerop (mod n i)))
        collect n))

(defun bench (name fn limit times)
  (let ((start (get-internal-real-time)))
    (dotimes (_ times) (funcall fn limit))
    (let ((elapsed (/ (- (get-internal-real-time) start)
                      internal-time-units-per-second 1.0)))
      (format t "~20a ~7,4f sec~%" name elapsed))))

;; ウォームアップ
(primes-baseline 1000)
(primes-optimize 1000)
(primes-typed 1000)
(primes-both 1000)

(let ((limit 1000000) (times 5))
  (format t "limit=~a, ~a runs~%~%" limit times)
  (bench "baseline"        #'primes-baseline limit times)
  (bench "optimize only"   #'primes-optimize limit times)
  (bench "type only"       #'primes-typed    limit times)
  (bench "optimize + type" #'primes-both     limit times))

(sb-ext:quit)Code language: Lisp (lisp)

7. 実用パターン

本番環境では、ファイルの先頭に declaim を書いておくと全関数に効いて楽です。

(declaim (optimize (speed 3) (safety 0) (debug 0)))Code language: Lisp (lisp)

個別の関数には declare で型を追加します。

(defun frequencies-from-vector (VA_n M)
  (declare (type fixnum M)
           (type (simple-array fixnum (*)) VA_n)
           (optimize (speed 3) (safety 0)))
  (let ((v (make-array (1+ M)
                       :element-type 'fixnum
                       :initial-element 0)))
    (declare (type (simple-array fixnum (*)) v))
    (loop for a fixnum across VA_n
          do (incf (aref v a)))
    v))Code language: Lisp (lisp)

7.1. SBCLでの確認方法（disassemble）

型宣言が効いているか確認するには disassemble を使います。

(disassemble #'frequencies-from-vector)Code language: Lisp (lisp)

宣言前後でアセンブリの行数が減っていれば最適化が効いています9。

SBCLは型が曖昧なまま最適化できない箇所に note: unable to optimize という警告を出します。
この警告を消していくのが型宣言チューニングの実践的なやり方です10。

開発中は safety 1 か safety 2 のままにしてこの警告を確認し、テストが通ってから safety 0 に切り替えると安全です。

  1. 型宣言とoptimize宣言の組み合わせについて、Common Lisp Cookbookに実践的な例が多数掲載されています。 – The Common Lisp Cookbook – Performance Tuning
  2. declare が書けるフォームはHyperSpecで定義されており、defun、let、flet、labels、lambda、do、dotimes、dolist など多数あります。 – CLHS: Symbol DECLARE
  3. declaim はマクロで、展開時に proclaim を呼び出します。proclaim は関数なので実行時に評価されますが、declaim はコンパイル時にも効果を持ちます。競技プログラミングではこの違いはほぼ意識する必要はありません。 – CLHS: Function PROCLAIM
  4. HyperSpec上のfixnumの範囲は実装依存で、少なくとも (signed-byte 16) の範囲を含むことだけが保証されています。SBCLの64bit環境では most-positive-fixnum は 4611686018427387903 です。実際の値は most-positive-fixnum と most-negative-fixnum で確認できます。 – CLHS: Type FIXNUM
  5. adjustable や fill-pointer を持つ配列は simple-array に該当しません。make-array に :adjustable t や :fill-pointer を指定した配列に (simple-array ...) を宣言しても、コンパイラが最適化を適用できない場合があります。 – The Common Lisp Cookbook – Performance
  6. HyperSpecには「A compiler is free to ignore this declaration.」と明記されています。SBCLは実際にはほぼ従いますが、再帰関数など展開できないケースでは無視されます。 – CLHS: Declaration INLINE, NOTINLINE
  7. optimize宣言の品質指標（quality）はHyperSpecで speed、safety、debug、space、compilation-speed の5種類が定義されています。処理系によっては独自の品質指標を追加で受け付けることもあります。 – CLHS: Declaration OPTIMIZE
  8. safety 0 で型宣言と実際の型が食い違った場合、エラーではなく誤った計算結果やクラッシュが起きます。競技プログラミングではコードが正しければ問題は起きません。バグがあれば不正解になるだけなので、リスクは限定的です。 – SBCL User Manual
  9. The Common Lisp CookbookにSBCLでの disassemble の出力例が掲載されており、型宣言の有無でアセンブリのバイト数が大きく変わることが確認できます。 – The Common Lisp Cookbook – Performance
  10. SBCLではコンパイラノートを sb-ext:muffle-conditions で抑制したり、sb-ext:unmuffle-conditions で再表示したりできます。開発中は警告を表示した状態で型宣言を追加していくのが効率的です。 – SBCL User Manual