【Section 7】
SBCLの処理系の特性を活かす視点
（Common Lispと計算効率）

by

これまでの問題で扱ったのは「計算量のオーダーを変える改善」と「型宣言による定数倍の改善」でした。

この付録では、SBCL固有の実行環境・I/O・言語特性に関する実践知識をまとめます。

関連記事

1. 浮動小数点数の設定

*read-default-float-format* を double-float に設定すると、ファイル先頭以降の read で読み込まれる浮動小数点リテラルがすべて double-float として扱われます。

(setf *read-default-float-format* 'double-float)Code language: Lisp (lisp)

リテラルの型は接尾辞でも明示できます。
1.5d0 は double-float、1.5e0 は single-float です。
e0 は *read-default-float-format* の影響を受けません1。

出力については、format の ~f は処理が遅いため、大量出力には princ か write を使います2。

(princ 1.23456789d0)       ; => 1.23456789d0
(format t "~,10f" 1.0d0)   ; => 1.0000000000（小数点以下10桁、遅い）Code language: Lisp (lisp)

1.1. 多倍長整数（bignum）

SBCLの fixnum は63ビット幅で、最大値は most-positive-fixnum（= 2^62 – 1）です3。

この範囲を超えると、自動的に bignum に昇格してオーバーフローなしで計算が続きます。

most-positive-fixnum          ; => 4611686018427387903
(+ most-positive-fixnum 1)    ; => 4611686018427387904（bignum、エラーにならない）
(expt 10 30)                  ; => 1000000000000000000000000000000（正確に計算）Code language: Lisp (lisp)

bignum 演算はヒープ割り当てが発生するため fixnum より遅くなります。
値が fixnum の範囲内に収まると保証できる場合は型宣言を使って最適化できます（問題47参照）。

1.2. 有理数（ratio）

整数同士を / で割ると、浮動小数点数ではなく有理数になります。
誤差なく正確な値を保持します4。

(/ 1 3)                    ; => 1/3（0.333... にならない）
(= (+ 1/3 1/3 1/3) 1)     ; => TCode language: Lisp (lisp)

浮動小数点に変換するには float の第2引数で型を指定します。

(float 1/3 1.0d0)    ; => 0.3333333333333333d0Code language: Lisp (lisp)

1.3. 文字列は文字の配列

string は (simple-array character (*)) として実装されています。
char によるインデックスアクセスはO(1)です。

(char "hello" 1)    ; => #\eCode language: Lisp (lisp)

ASCII範囲のみの文字列は (simple-base-string) 型として内部表現され、メモリ消費が少なくなります5。

(type-of "hello")   ; => (SIMPLE-BASE-STRING 5)Code language: Lisp (lisp)

2. 整数入力の高速化

read は汎用パーサで、整数10^5個の読み込みがボトルネックになることがあります。
バイト単位で読んで整数を直接組み立てる専用関数で回避します。

declaim ftype は関数の型シグネチャをファイルレベルで宣言する構文です6。
(function * (values fixnum &optional)) は「任意の引数を受け取り、fixnum を1つ返す」関数を意味します。

(declaim (ftype (function * (values fixnum &optional)) read-fixnum))

(defun read-fixnum (&optional (in *standard-input*))
  (declare (inline read-byte)
           #-swank (sb-kernel:ansi-stream in))
  (macrolet ((%read-byte ()
               `(the (unsigned-byte 8)
                     #+swank (char-code (read-char in nil #\Nul))
                     #-swank (read-byte in nil 0))))
    (let* ((minus  nil)
           (result (loop (let ((byte (%read-byte)))
                           (cond ((<= 48 byte 57) (return (- byte 48)))
                                 ((zerop byte)    (error "EOF"))
                                 ((= byte #.(char-code #\-)) (setq minus t)))))))
      (declare ((integer 0 #.most-positive-fixnum) result))
      (loop
        (let ((byte (%read-byte)))
          (if (<= 48 byte 57)
              (setq result
                    (+ (- byte 48)
                       (the (integer 0 #.(floor most-positive-fixnum 10))
                            (* result 10))))
              (return (if minus (- result) result))))))))Code language: Lisp (lisp)

いくつか補足します。

sb-kernel:ansi-stream はSBCL固有の型宣言です。
SLIMEでは標準IOがバイナリストリームでないため、#-swank でSLIME環境をガードしています。
:swank フィーチャーが存在する環境ではこの宣言がスキップされます。

macrolet は関数内でローカルなマクロを定義する構文です。
ここではSLIME環境と本番環境でバイト読み込み方法を切り替えています。

整数のパース部分では、ASCIIコードの 48〜57 が '0'〜'9' に、45 が - に対応します。
空白や改行をスキップしながら最初の数字を探し、続く数字で桁を積み上げます。
the で中間値の型を宣言することでオーバーフロー検査を省いています。

read との速度比較の目安として、整数10^5個の読み込みで read は200〜500ms、read-fixnum は20〜50ms程度です。

3. 出力のバッファリング

大量の行を逐次出力すると、システムコールのオーバーヘッドが積み重なります。
一度文字列ストリームに書き溜めてからまとめて出力します。

(defmacro with-buffered-stdout (&body body)
  (let ((out (gensym "OUT")))
    `(let ((,out (make-string-output-stream :element-type 'base-char)))
       (let ((*standard-output* ,out))
         ,@body)
       (write-string (get-output-stream-string ,out)))))Code language: Lisp (lisp)

gensym は重複しないシンボルを生成します7。
マクロ展開時のシンボル衝突を防ぐためのイディオムです。
*standard-output* を let で動的に再束縛することで、ブロックを抜けると元のストリームに戻ります。
get-output-stream-string でバッファ内容を文字列として取得し、最後に一括出力します。

使い方は以下の通りで、format t の出力がすべてバッファに貯まり、ブロックを抜けた時点でまとめて書き出されます。

(with-buffered-stdout
  (dotimes (i n)
    (format t "~a~%" (answer i))))Code language: Lisp (lisp)

4. 子プロセスでスタックサイズを拡張する

SBCLのデフォルトスタックサイズは2MBで、深さ10^4〜10^5程度の再帰で control-stack-exhausted エラーになります8。
問題39（木の高さ）で見た通り、DFS・再帰的DP・深い分割統治では必須の対処です。

#-swank
(unless (member :child-sbcl *features*)
  (quit
   :recklessly-p t
   :unix-status
   (process-exit-code
    (run-program *runtime-pathname*
                 `("--control-stack-size" "256MB"
                   "--noinform"
                   "--disable-ldb"
                   "--lose-on-corruption"
                   "--end-runtime-options"
                   "--eval" "(push :child-sbcl *features*)"
                   "--script" ,(namestring *load-pathname*))
                 :output t :error t :input t))))Code language: Lisp (lisp)

#-swank はSLIMEでの誤作動を防ぐガードです。
SLIMEでは :swank フィーチャーが存在するため、このブロック全体がスキップされます。

起動の流れは次の通りです。
最初の起動時は :child-sbcl フィーチャーが存在しないため unless ブロックが実行されます。
quit で現在のプロセスを終了しながら、run-program で新しいSBCLプロセスを --control-stack-size 256MB で起動します。
新プロセスは起動時に (push :child-sbcl *features*) を評価済みなので、同じファイルを再実行しても unless が偽になり再起動ループが止まります。

--noinform は起動バナーの非表示、--disable-ldb はデバッガの無効化、--lose-on-corruption はメモリ破壊時の即終了を指定するオプションです9。

根本的な解決策は問題39・42で示した「反復に書き換える」方法です。
スタック拡張は書き換えが困難な場合の回避手段として位置づけてください。

  1. この変数は読み込みだけでなく出力にも影響します。プリンタは浮動小数点数を表示する際、数値の型が *read-default-float-format* と一致していれば指数マーカーを省略します。double-float に設定した状態で (write 1.5d0) を実行すると 1.5 と表示され、d0 サフィックスが付きません。 – CLHS: Variable READ-DEFAULT-FLOAT-FORMAT
  2. 接尾辞は s（short-float）、f（single-float）、d（double-float）、l（long-float）、e（*read-default-float-format* に従う）の5種類あります。SBCLでは long-float は double-float と同一の表現になります。 – The Common Lisp Cookbook – Numbers
  3. CLHSでは fixnum の幅は実装依存とされており、最低でも (signed-byte 16) の上位型であることだけが保証されます。64bit環境のSBCLでは1ビットをタグビットに使用するため、63bitになります。32bit環境では31bitになります。 – CLHS: Type FIXNUM
  4. 有理数の分子と分母はどちらも bignum になれるため、巨大な分数も正確に扱えます。例として (/ (1+ (expt 2 100)) (expt 2 100)) は 1267650600228229401496703205377/1267650600228229401496703205376 という巨大な有理数を返します。また結果の分母が1になる場合（例：(* 1/2 4)）は自動的に整数に変換されます。 – The Common Lisp Cookbook – Numbers
  5. SBCLの内部表現では、simple-base-string の各文字は8bitバイト列として格納されます。一方、Unicode文字を含む (simple-array character (*)) では各文字が32bitで格納されるため、ASCII専用文字列は同じ長さで4分の1のメモリで済みます。 – SBCL Internals: Memory Layout
  6. ftype 宣言はコンパイラへのヒントとして機能し、SBCLは宣言と矛盾する呼び出しを検出したときにコンパイル時警告を出します。また関数が返す型を宣言しておくと、呼び出し側のコードで型推論が効きやすくなり、追加の型チェック命令を省ける場合があります。 – SBCL User Manual
  7. gensym は内部カウンタをインクリメントしながら G1、G2 のような名前のシンボルを生成します。引数に文字列を渡すとプレフィックスを変えられるため、(gensym "OUT") は OUT1、OUT2 のような名前になります。生成されたシンボルはどのパッケージにも属さない（uninterned）ため、ユーザーコードの変数名と衝突しません。 – The Common Lisp Cookbook
  8. SBCLマニュアルでは --control-stack-size オプションのデフォルト値が2MBと明記されています。このエラーは末尾呼び出し最適化が適用されない深い再帰でも発生します。コンテストでよくある問題として、木のDFSや分割統治の再帰深度がノード数に比例するケースが該当します。 – SBCL User Manual
  9. LDBはSBCLに組み込まれた低レベルデバッガ（Low-level DeBugger）で、通常のLisp条件システムでは捕捉できないメモリ破壊などの致命的エラー時に起動します。スクリプト実行では不要であり、--disable-ldb で無効化しておくとメモリを節約できます。ただしSBCLが--enable-ldb付きでビルドされていない場合はこのオプション自体が効果を持ちません。 – sbcl(1) Linux man page