- Common Lispでループ内から繰り返し呼ぶ関数に
make-arrayがあると、GCの負荷がボトルネックになる。 defparameterで配列をグローバルに確保しfill-pointerで使い回すと、メモリ割り当てを1回に抑えられる。letとdefunを組み合わせたレキシカルクロージャにすれば、配列をグローバルに露出させずに同じ効果を得られる。- ただし、
declaim ftypeで関数宣言をしないと、コンパイル時未定義に警告が出ます。
1. 問題：ループ内でのmake-array
ループの中で繰り返し呼ぶ関数で、毎回 make-array していて効率が悪くなっていました。
配列のメモリ割り当てがループ回数分だけ積み重なり、ボトルネックになっているようでした。
そこで、配列を一度だけ確保して使い回したいと思います。
たとえば、リストの要素の出現頻度を数える関数を考えます。
(defun frequency-vector (lst M)
(let ((v (make-array (1+ M) :element-type 'fixnum :initial-element 0)))
(loop for a_n in lst
do (incf (aref v a_n))
finally (return v))))Code language: Lisp (lisp)この実装では呼ぶたびに、頻度を記録する配列を make-array しています。
1回の呼び出しならまったく問題ありませんが、これを10万回ループから呼ぶと話が変わります。
make-array はOSやアロケータとのやりとりを伴い、確保したオブジェクトはガベージコレクタの追跡対象になります。
GCが走るたびに処理が止まり、ループ全体の時間を押し上げます1。
2. defparameterで配列をグローバルに確保する
まずは、素直な解決策として、配列をグローバル変数に出します。
(defparameter *v*
(make-array 500001
:element-type 'fixnum
:fill-pointer 0
:initial-element 0))
(defun frequency-vector (lst M)
(declare (type fixnum M)
(optimize (speed 3) (safety 0)))
(setf (fill-pointer *v*) (1+ M))
(fill *v* 0)
(loop for a_n in lst
do (incf (aref *v* a_n))
finally (return *v*)))Code language: Lisp (lisp)名前に * をつけるのはCommon Lispのダイナミック変数の慣習で、「グローバルに変更される変数」を示します2。
こうすれば、make-array はプログラム起動時に1回だけ走ります3。
fill-pointer はこの配列の論理的な長さを表す値で、setf で書き換えられます4。(setf (fill-pointer *v*) (1+ M)) とすれば、500001要素ぶんの実メモリはそのままに、length や map などのシーケンス関数には長さ M+1 の配列として見えます。
aref は fill-pointer を無視して全領域にアクセスできますが、シーケンス操作はすべて fill-pointer の範囲内に収まります5。
fill では配列を0で上書きします。
毎回走りますが、確保済みのメモリへの連続書き込みなのでキャッシュに乗りやすく、make-array より大幅に速くなりました。
2.1. グローバル汚染の問題
ただし、defparameter による解決には欠点があります。
それは、*v* がグローバルな名前空間に露出してしまうこと。
別のモジュールや関数が誤って *v* を書き換えると、frequency-vector の動作が壊れます。
また、frequency-vector を並行して2つ呼ぶと、同じ *v* を共有するので競合します。
テストで状態をリセットしにくいという問題もあります。
3. クロージャで配列を閉じ込める
そこで、let と defun を組み合わせます。
そうすると、配列をスコープの外に見せずに保持できます。
(let ((v (make-array 500001
:element-type 'fixnum
:fill-pointer 0
:initial-element 0)))
(defun frequency-vector (lst M)
(declare (type fixnum M)
(optimize (speed 3) (safety 0)))
(setf (fill-pointer v) (1+ M))
(fill v 0)
(loop for a_n in lst
do (incf (aref v a_n))
finally (return v))))Code language: Lisp (lisp)let はレキシカルスコープを作ります。v はこのブロックの中でしか名前で参照できません。
ただし defun で定義された frequency-vector は、自分が定義されたスコープの v を捕捉して閉じ込めます。
したがって、let のブロックを抜けても v はGCされず、frequency-vector が生きている限り存在し続けます。
これが「レキシカルクロージャ」です6。
グローバル変数と違って、frequency-vector 経由でしかアクセスできなくなりました。
3.1. C言語のstaticとLispのクロージャ
この設計は、C言語の static ローカル変数と同じ発想ですが、構造には違いがあります。
C言語の静的変数（static）は、関数呼び出しをまたいで値が保持されます。
// C Style
void frequency_vector(int *lst, int len, int M, int *result) {c
static int v[500001];
memset(v, 0, (M + 1) * sizeof(int));
for (int i = 0; i < len; i++) result[lst[i]]++;
}Code language: C++ (cpp)Lispのクロージャも同じように、呼び出しをまたいで v を保持しますが、厳密には違いがあります。
Cの static がコンパイル時に決まる固定の1個であるのに対し、クロージャは実行時に生成される独立した環境です。
それは「インスタンスを複数作れるか」ということにも関係しています。
確かに、Lispの letブロック内にdefunで書いたクロージャでは、すべて同じ変数を共有します。
しかし、Lispでは、letブロック内に lambda を使ってクロージャを生成することもできます。
そうすれば、それぞれ独立した v を持つカウンターをいくつでも作れます7。
(defun make-frequency-counter (max-size)
(let ((v (make-array (1+ max-size)
:element-type 'fixnum
:fill-pointer 0
:initial-element 0)))
(lambda (lst M)
(setf (fill-pointer v) (1+ M))
(fill v 0)
(loop for a_n in lst
do (incf (aref v a_n))
finally (return v)))))
(defparameter counter-a (make-frequency-counter 1000))
(defparameter counter-b (make-frequency-counter 5000))Code language: Lisp (lisp)このとき、counter-a と counter-b はそれぞれ独立した配列を持ち、互いに干渉しません。
つまり、defun を1つ定義するだけなら動作はCの static と同じですが、クロージャを返す関数として設計すれば状態を持った関数を動的に量産できます。
4. 補足：let+defunで出るSTYLE-WARNING
ところで、let の中に書いた defun には、少し問題があります。
; caught STYLE-WARNING:
; undefined function: COMMON-LISP-USER::FREQUENCIES-FROM-VECTORCode language: JavaScript (javascript)SBCLはファイルをコンパイルするとき、トップレベルの defun を先にスキャンして関数名を登録します。
ところが、let で包まれた defun はトップレベルとして認識されません。
そのため、コンパイラは frequencies-from-vector の存在を知らないまま、それを呼ぶ側の関数をコンパイルしてしまいます。
ただ、実行時には let が評価されて関数は定義されます。
したがって動作はしますが、コンパイル時点では未定義扱いなのです。
4.1. declaim ftypeでの関数宣言する
コンパイル時点でシンボルの関数定義をするには、ファイルの先頭で declaim を使い、関数の存在をコンパイラに予告します。
(declaim (ftype (function (list fixnum) (vector fixnum))
frequency-vector))
(let ((v (make-array 500001
:element-type 'fixnum
:fill-pointer 0
:initial-element 0)))
(defun frequency-vector (lst M)
(declare (type fixnum M)
(optimize (speed 3) (safety 0)))
(setf (fill-pointer v) (1+ M))
(fill v 0)
(loop for a_n in lst
do (incf (aref v a_n))
finally (return v))))Code language: Lisp (lisp)(ftype (function (list fixnum) (vector fixnum)) ...) は「引数が list と fixnum、戻り値が fixnumのvector の関数」という型シグネチャです。
これでコンパイラは関数の存在と型を把握できるため、let+defun の構造でも警告が出なくなります。
カプセル化を保ちたいライブラリコードではこちらが適しています。
5. まとめ
ループ内で配列を繰り返し使う関数は、make-array をループの外に出すだけでGCの負担を大きく減らせます。fill-pointer を使えば、大きめに確保した配列を必要な長さに切り詰めて使い回せます。
defparameter で実現できますが、グローバル汚染を避けたければ let と defun を組み合わせたクロージャ構造を使います。
このクロージャは、Cの静的変数と動作は似ていますが、複数インスタンスを作れる点で異なります8。
- Common LispのGCは多くの実装でstop-the-worldを採用しており、コレクション中はすべてのスレッドが停止します。アロケーションが増えるほどコレクション頻度が上がり、停止時間の合計が増えます。 – Pro mailing list: on Common Lisp and parallel GC
- この慣習は「earmuff（イヤーマフ）規約」と呼ばれます。
defvarやdefparameterで定義された変数は自動的にspecial宣言され、ダイナミックスコープで動作します。earmuffをつけることで、レキシカル変数と視覚的に区別できます。 – Common Lisp – Wikipedia defparameterはファイルをリロードするたびに値を上書きします。一方defvarは初回のみ値を設定し、既にバインドされている場合は変更しません。起動時に一度だけ確保したい配列にはdefvarの方が安全な場合もあります。 – CLHS: Macro DEFPARAMETER, DEFVARfill-pointerに指定できる値は0以上かつarray-total-size以下の非負整数です。範囲外の値を設定するとエラーになります。 – CLHS: Accessor FILL-POINTERarefがfill-pointerを無視する動作はCommon Lisp標準の仕様です。fill-pointerより大きいインデックスへのアクセスは未定義ではなく、合法的に行えます。 – CLtL2: 17.5 Fill Pointers- レキシカル変数への参照を持つ関数が、定義時の環境ごと保持される仕組みです。
letの上にlambdaやdefunを載せるパターンは “let over lambda” とも呼ばれます。 – Let Over Lambda - 同じ
letブロックの中に複数のdefunを置くと、それらはすべて同じvを共有するクロージャになります。ゲッターとセッターを1つのバインディングで共有する、オブジェクト指向的なカプセル化と同じ構造です。 – Successful Lisp – Chapter 11 fill-pointerと:adjustable tを組み合わせると、vector-push-extendで実メモリサイズ自体を動的に拡張することもできます。今回のような上限が既知のケースでは不要ですが、上限が不定の場合は選択肢になります。 – CLHS: Function ADJUST-ARRAY