構造体のスタックへの割り当て

SBCLのマニュアル(ver 1.0.37)にも書いてあることだけど ... 。

通常は構造体のインスタンスを作成するとヒープ上にそのための領域が割り当てられる。
これには(おそらく)ヒープ割り当て＋GC処理のコストが伴うので、構造体としてまとめるよりも、その各フィールドを個別に扱った方が、パフォーマンス的には有利だったりする。

;; sbcl-1.0.40
;;
;; 構造体のインスタンス作成のコストを測るためプログラム

;; 範囲を表す構造体
(defstruct range
  start 
  end)

;; 範囲をランダムに複数生成し、それらの距離の合計値を求める
;; 1) 構造体を使う場合
(time 
 (let ((total 0))
   (loop REPEAT 1000000
     DO
     (let ((r (make-range :start (random 100) :end (random 100))))
       (incf total (- (range-end r) (range-start r)))))
   total))
Evaluation took:
  0.076 seconds of real time
  0.068005 seconds of total run time (0.064004 user, 0.004001 system)
  [ Run times consist of 0.016 seconds GC time, and 0.053 seconds non-GC time. ]
  89.47% CPU
  152,191,506 processor cycles
  15,998,952 bytes consed        ; 約15MBのコンスが発生
--> -27532

;; 2) 構造体を使わない場合
(time 
 (let ((total 0))
   (loop REPEAT 1000000
     DO
     (let ((start (random 100))
           (end   (random 100)))
       (incf total (- end start))))
   total))

Evaluation took:
  0.037 seconds of real time
  0.036002 seconds of total run time (0.036002 user, 0.000000 system)
  97.30% CPU
  73,238,322 processor cycles
  0 bytes consed                ; コンスなし
--> -6527

ただし、以下の二つの条件を満たせば、インスタンスがヒープではなくスタックに割り当てられるようになる。

1. 構造体定義の前にコンストラクタ関数をインライン宣言する
2. 作成される構造体のインスタンスに対してdynamic-extent宣言を行う

;; 3) 構造体を使う場合(スタック割り当て版)
(declaim (inline make-range))
(defstruct range
  start 
  end)

(time 
 (let ((total 0))
   (loop REPEAT 100000
     DO
     (let ((r (make-range :start (random 100) :end (random 100))))
       (declare (dynamic-extent r))
       (incf total (- (range-end r) (range-start r)))))
   total))
Evaluation took:
  0.005 seconds of real time
  0.004000 seconds of total run time (0.004000 user, 0.000000 system)
  80.00% CPU
  10,287,186 processor cycles
  0 bytes consed               ; スタックへの割り当てなのでコンスは発生しない
--> -15697

これでインスタンス生成のコストをほとんど気にせず構造体を使うことができる*1。

*1:もちろんextentがdynamicで良い場合だけだけど ...