- SBCLは関数単位でコンパイルするため、引数の型は宣言がなければ何でもありの
Tとして扱われる。 - 返り値に
ftypeを宣言した関数は、その型情報が呼び出し元に伝わり、連鎖的に型推論が効いていく。 - 型宣言を集中させるべき場所は、外から値が入ってくる変換関数の返り値とループ内の破壊的変更を含む変数。
1. 型宣言を書いたCommon Lisp
Common Lispでプログラミングの効率化の問題を解いていました。
そこで、几帳面に declaimとftypeを並べていたのですが、「まるでCのヘッダファイルにそっくり」だと思いました1。
(declaim (ftype
(function (fixnum (simple-array fixnum (*)))
fixnum)
sum-array))Code language: Lisp (lisp)このLispコードは、さしずめC言語なら、
int sum_array(int n, int* arr);Code language: Arduino (arduino)通常、Lispは自由で、型を書かなくても動きます。
それが、コンパイラへのヒントを書き足していくと、どんどん窮屈になります。
2. SBCLの型推論とコンパイル単位
SBCLの型推論の仕組みを理解すると、型宣言をどこに集中させるべきかが見えてきます。
その核となるのは、関数単位でコンパイルするという設計です。
ある関数をコンパイルするとき、SBCLは「この関数がどこから呼ばれるか」を考慮しません。
引数の型は、ftype宣言がなければ、T、つまり「何でもあり」として扱われます。
呼び出し元がどれだけ型を絞り込んでいても、その情報は関数の中に伝わらないのです2。
逆に、関数の型宣言は、呼び出し側に伝わります。ftypeで返り値の型を宣言した関数の型情報は、呼び出し元に流れ込んで、さらに先の変数や演算の推論に使われます。
たとえば、リストをfixnumの配列に変換する関数に次の宣言を書くとします。
(declaim (ftype (function (list)
(simple-array fixnum (*)))
list->fixnum-array))
(defun list->fixnum-array (lst)
(make-array (length lst)
:element-type 'fixnum
:initial-contents lst))Code language: Lisp (lisp)こう宣言しておくと、list->fixnum-arrayの返り値を受け取った変数がsimple-array fixnum (*)だとSBCLが把握できます。
そこからarefでアクセスすれば、要素型がfixnumと確定しているのでボクシングなしの整数演算になります3。
2.1. 型推論を「連鎖」させる
この仕組みを活かすと、型宣言は連鎖的に効きます。
外から値が入ってくる変換点の関数にftypeを書いておくと、その返り値を受け取ったlet*の束縛変数の型が確定します。
そこから呼ばれる関数の引数の型も確定して、さらに内部の演算まで型が伝わっていきます。
(defun process (lst)
(let ((arr (list->fixnum-array lst))) ; ここの型が simple-array fixnum (*) と確定する
(loop for i below (length arr)
sum (aref arr i)))) ; aref の最適化が連鎖して効くCode language: Lisp (lisp)逆に、変換点の宣言が欠けていると推論が途切れます。readや汎用のsortから返ってきた値は型がTのままで、内部をどれだけ几帳面に書いても効果が薄れます4。
「どこに宣言を書くか」の答えは、ここにあります。
つまり、外から内への入口になる関数の返り値です。
2.2. 変数の束縛
関数型スタイルは、基本的に自然と型推論が通りやすくなります。
let*で束縛して以後変えない変数は、束縛時の型がそのまま有効です。
SBCLはその変数に別の型が代入される可能性を考えなくていいからです。
一方、setfで書き換える変数は、保守的に扱われます。
たとえば、ループ変数は、カウンタを加算していくようなときに型がわかりにくくなるので、明示すればよいわけです5。
;; bad
(loop with total = 0
for x across arr
do (incf total x)
finally (return total))
;; good
(loop with total fixnum = 0
for x fixnum across arr
do (incf total x)
finally (return total))Code language: Lisp (lisp)3. 警告をガイドに使う
最初から全部書くより、宣言なしでコンパイルしてSBCLの警告を見るほうが手間が少ないです。
SBCLが出すnote: unable to optimizeやnote: doing ... coercionのメッセージは、推論が途切れた場所を指しています。
それが実質的なホットスポット検出器になります。
警告が出た関数にだけftypeを足す順番で進めると、ボイラープレートを最小限に抑えられます6。
Common Lispは型を書かなくても動きます。
SBCLに限れば、書けばCに近づきます。
その振れ幅の広さ自体がLispらしさで、どこに書くかを選べる自由があります。
几帳面に全部書くのも、推論に任せて全部省くのも、どちらも「選択」です。
パフォーマンスが必要な境界だけ締めて、内側は推論に任せる——それが読みやすさと速度を両立する進め方になります。
4. どこに書いて、どこを省くか
型宣言を集中させる場所は三種類になります。
- 入口の変換関数——外から入ってくるリストや入力値を
simple-arrayに変換する関数です。
ここに返り値の型を宣言すると、連鎖が始まります。 - 汎用ライブラリとして切り出した関数——二分探索や順位統計のような、複数の箇所から呼ばれる汎用処理です。
関数単位で最適化が完結するのでftypeを書く価値があります。
呼び出し元の文脈に依存せず、単体で速くなります7。 - 破壊的変更を含むループの変数——
loop内でカウンタや累積値をsetfする変数にdeclareを足します。
逆に省いていいのは、連鎖してきた推論が型を確定できる内部の関数です。simple-arrayを引数として受け取ってsortにそのまま渡すような関数は、宣言がなくても推論が通ることが多いです。
declaimはファイルのトップレベルフォームとして使われ、コンパイル時に宣言を有効にします。コンパイル後も効果が持続するかどうかはANSI仕様では未定義で、実装依存です。 – The Common Lisp Cookbook – Performance Tuning and Tipsftype宣言は、渡された引数の型が宣言と合致するときだけ最適化が働きます。合致しない場合はエラーにならず、宣言が無視されます。 – The Common Lisp Cookbook – Performance Tuning and Tips- SBCLでは
(simple-array fixnum (*))のような特殊化配列は、要素をヒープ上のLispオブジェクトへのポインタではなく、ワード列として直接格納します。宣言がない場合、SBCLは汎用配列と見なしてアクセスのたびにアンボクシングのコストが発生します。 – MX: Arrays and Boxing in Common Lisp & SIMD in SBCL - 関数内のローカルな型推論を補完したい場合は、
(the fixnum x)のようにtheフォームで型を明示する方法もあります。ftypeが関数境界を越えて情報を伝えるのに対し、theは式単位で型を伝えます。 – A Nickel’s Worth: Optimizing CL - SBCLのデフォルトコンパイルポリシーでは、型宣言はランタイムにアサーションとして検査されます。型違反があればエラーが出るので、宣言を足しながら
safetyを高く保って動作確認するのが安全です。(safety 0)にすると型チェックが無効になり、型違反はヒープ破壊につながる可能性があります。 – SBCL User Manual – Declarations as Assertions (declaim (optimize (speed 3) (safety 3)))のように速度と安全性を同時に高く設定すると、型チェックを維持しながら最適化の注意書きを受け取れます。開発中はsafetyを下げないのが無難です。 – The Common Lisp Cookbook – Performance Tuning and Tipsdeclaimで宣言したftypeは、同じファイル内に後から書いたdefunに適用されます。defunより先にdeclaimを置くのが通例です。宣言後に関数を再定義した場合、宣言なしで先にコンパイルされた呼び出し元は型情報を使えていない可能性があります。 – SBCL User Manual