- Common Lispの
readはS式パーサーを通るため整数読み取りには過剰で、read-fixnumはバイトを直接処理することで約5倍高速化できます。 macroletで定義した%read-byteマクロにより関数呼び出しのオーバーヘッドをなくし、theによる型アサーションでSBCLの不要な型チェックを省いています。- 開発環境ではSWANKのグレイストリーム制約により
read-char+char-codeを使い、本番ではread-byte直呼びに切り替えるフィーチャーフラグで環境差を吸収しています。 - 計測の結果、
read-char版とread-byte版の速度差はほぼなく、型宣言とmacroletによるインライン展開だけで十分な最適化が得られました。
1. readのパースを軽くする
Common Lispの標準的な read 関数はS式パーサーとして動作するため、トークンの種類判定やリーダーマクロの処理が常に走ります1。
しかし、競技プログラミングでは「入力は必ず整数リテラル」という前提があり、S式をパースする必要はありません。
そこで、read-fixnum は、文字コードを直接処理し、数字か-、それ以外は区切り文字、という3択でパースを簡略化しています。
(defun read-fixnum (&optional (in *standard-input*))
(macrolet ((%read-char-code ()
`(the (unsigned-byte 8)
(char-code (read-char in nil #\Nul)))))
(let* ((c0 #.(char-code #\0))
(c9 #.(char-code #\9))
(minus nil)
(result 0))
(declare ((integer 0 #.most-positive-fixnum) result))
(loop
(let ((code (%read-char-code)))
(cond
((zerop code)
(error "Read EOF or #\Nul."))
((= code #.(char-code #\-))
(setq minus t))
((<= c0 code c9)
(return (setq result (- code c0)))))))
(loop
(let ((code (%read-char-code)))
(cond
((<= c0 code c9)
(setq result
(+ (- code c0)
(the (integer 0 #.(floor most-positive-fixnum 10))
(* result 10)))))
(t (return (if minus (- result) result)))))))))
(defun read-fixnums (n &optional (in *standard-input*))
(let ((v (make-array n :element-type 'fixnum)))
(declare ((simple-array fixnum (*)) v))
(loop for i below n
do (setf (aref v i) (read-fixnum in))
finally (return v)))Code language: Lisp (lisp)ただし、数値のあとにある空白文字の扱いに注意が必要です。
2. read-charを使った実装
まずは、EmacsのSLIME上で動く素直な実装を考えます2。
大きな流れは、
- 一文字読み取って（%read-byte）、
- 符号・数字の先頭を探し、
- 続く数字を桁にしています。
2.1. %read-byte マクロ
まずは、一文字分の文字コードを読取るマクロを作ります。
(macrolet ((%read-byte ()
`(the (unsigned-byte 8)
(char-code (read-char in nil #\Nul)))))Code language: Lisp (lisp)関数にすると呼び出しのオーバーヘッドが発生するので、macroletでローカルマクロ%read-byteを定義して、呼び出し箇所にコードが展開されるようにします3。
このマクロは、read-char で文字を読み、char-code でバイト値に変換します。
EOF時には、read-char のオプション指定で #\Nul から文字コード0を返すことにしています。
the は型アサーションで、コンパイラに「この式は (unsigned-byte 8) である」と伝え、後続の算術演算で不要な型チェックが省かれます4。
2.2. 第1ループ：符号と数字の先頭を探す
処理の最初は、数値の先頭は、数字かマイナス符号です。
符号の有無を minus でチェックし、一文字目の数値はresultに入れます。
(let* ((c0 #.(char-code #\0))
(c9 #.(char-code #\9))
(minus nil)
(result 0))
(declare ((integer 0 #.most-positive-fixnum) result))Code language: PHP (php)#. はリードタイム評価で、リーダーがこの式を読んだ瞬間に評価します。
コンパイル済みコードには数値リテラルとして埋め込まれるので実行時コストがありません5。
result が fixnum の正の範囲内に収まると宣言することで、SBCLはbignum（任意精度整数）への昇格チェックを省略します6。
(loop
(let ((code (%read-char-code)))
(cond
((zerop code)
(error "Read EOF or #\Nul."))
((= code #.(char-code #\-))
(setq minus t))
((<= c0 code c9)
(return (setq result (- code c0)))))))Code language: Lisp (lisp)#.(char-code #\0)は、ASCIIでは48、 #\9 は57です。
最初の数字が来たら (- byte 48) で数値に変換して result に入れループを抜けます。#.(char-code #\-) の - を見たら minus フラグを立てて読み進め、スペースや改行はどの条件にも引っかからないのでそのまま次へ進みます。
2.3. 第2ループは数字を足して組み立てる
(loop
(let ((code (%read-char-code)))
(cond
((<= c0 code c9)
(setq result
(+ (- code c0)
(the (integer 0 #.(floor most-positive-fixnum 10))
(* result 10)))))
(t (return (if minus (- result) result))))))Code language: Lisp (lisp)数字が続く間は result = result * 10 + digit を繰り返し、数字以外が来たらループを抜けて符号を付けて返します。(the (integer 0 #.(floor most-positive-fixnum 10)) (* result 10)) は result * 10 の段階ではまだ上限を超えていないことをコンパイラに伝えています。floor で計算した上限がリードタイム評価で定数として埋め込まれるので、この乗算がオーバーフローしないと型レベルで保証できます。
ただし、readと違って注意が必要なのが、数値以降の空白文字を消費しないことです。
次に、そのままread-lineで読み取ると、意図しない空白文字を受け取る可能性があります。
2.4. declaim と型宣言
最後に、関数の型を宣言します。
呼び出し側でこの戻り値を fixnum として扱えるようになり、ボックス化解除などの最適化が入りやすくなります。
(declaim (ftype (function * (values fixnum &optional)) read-fixnum))Code language: Lisp (lisp)declaim はファイル全体に効くグローバル宣言です7。
引数は任意（*）、戻り値は fixnum ひとつと宣言しています。&optional はmultiple valuesの文脈で「これ以降の値は省略可能」を意味する慣用表現です8。
2.5. 完成したコード
ここまでをまとめると、
(declaim (ftype (function * (values fixnum &optional)) read-fixnum))
(defun read-fixnum (&optional (in *standard-input*))
(macrolet ((%read-char-code ()
`(the (unsigned-byte 8)
(char-code (read-char in nil #\Nul)))))
(let* ((c0 #.(char-code #\0))
(c9 #.(char-code #\9))
(minus nil)
(result 0))
(declare ((integer 0 #.most-positive-fixnum) result))
(loop
(let ((code (%read-char-code)))
(cond
((zerop code)
(error "Read EOF or #\Nul."))
((= code #.(char-code #\-))
(setq minus t))
((<= c0 code c9)
(return (setq result (- code c0)))))))
(loop
(let ((code (%read-char-code)))
(cond
((<= c0 code c9)
(setq result
(+ (- code c0)
(the (integer 0 #.(floor most-positive-fixnum 10))
(* result 10)))))
(t (return (if minus (- result) result)))))))))Code language: Lisp (lisp)3. N個の整数をまとめて読む：read-fixnums
read-fixnum を使って、N個の整数をベクタに読み込む関数を作ります。
(declaim (ftype (function *
(values
(simple-array fixnum (*))
&optional))
read-fixnums))
(defun read-fixnums (n &optional (in *standard-input*))
(let ((v (make-array n :element-type 'fixnum)))
(declare ((simple-array fixnum (*)) v))
(loop for i below n
do (setf (aref v i) (read-fixnum in))
finally (return v)))Code language: Lisp (lisp)loopで i を 0 から n-1 まで回し、最後に v を返します。:element-type 'fixnum を指定すると配列が fixnum に特化され、格納時のボックス化が省かれます。
declare で配列型を明示しているのは、aref の書き込みパスで型チェックを省くためです。read-fixnum が fixnum を返すことは declaim で保証されているので、コンパイラはボックス化なしに直接書き込めます。
これを使うと、(read-fixnums n) 一発で入力行を読み切れます。
3.1. read と共通する注意点（末尾空白）
read-fixnumは、read同様、文字列を読み取る read-line と組み合わせるときに注意が必要です。
readもread-fixnumも、末尾の区切りは必ず1文字であることを暗黙の前提にしています。
連続して呼ぶ間は、最初の区切り文字を読み飛ばす設計になっているため、区切り文字が複数あっても吸収されますが、直後に read-line を呼ぶときに微妙な違いがあります。
たとえば、改行前に空白文字が含まれていると、
42 ;<= 改行前に空白文字が1つ含まれている
helloread-fixnum は 4、2 と読み進め、「空白文字」を検出した時点でループを抜けます。
次に read-line を呼ぶと、42 の行の改行は残っているので、 "" が返ります。
これは、readとも同じですが、行の末尾に空白文字が連続しているときには、見落としやすいので注意が必要です。
3.2. read との異なる注意点
また、read と read-fixnum は、解釈する区切り文字に違いがあります。
readの終端処理は、区切り文字である空白（スペース・タブ・改行・CR）を１つそのまま読み捨てます。read-fixnumの区切り文字は、空白文字だけでなく数字以外のすべての文字で、それが来た時点でそのバイトを1つ読み捨てて即座に返ります。
数値が空白文字で区切られる、という前提が満たされていれば違いはないのですが、数値の直後に文字列がある場合は、動作に違いがあります。
42helloこの例は、readだとシンボル 42HELLO を返し、次のread-lineはEOFエラーになります。
一方、read-fixnum は、h を区切りとして消費するため、read-line では "ello" が返ってきます。
4. read-byteを使った実装
本番環境では、%read-byteマクロをさらに高速化できることが考えられます。
それが、read-byte関数のインライン展開です。
(declare (inline read-byte))
(macrolet ((%read-byte ()
`(the (unsigned-byte 8)
(read-byte in nil 0))))Code language: Lisp (lisp)read-byte はバイナリストリームから1バイトを整数として直接返すので char-code の変換コストもなくなります。
4.1. 本番用の%read-byte の切り替え
ただし、read-byte は標準関数で、インライン展開するには条件があります。
それは、SBCLの read-byte は引数の型が sb-kernel:ansi-stream だとわかっていること。
その場合、入力ストリームのディスパッチをスキップして最速のパスを通ります
つまり、sb-kernel:ansi-stream 宣言と組み合わさると、バイト読み取りが関数呼び出しを経由せず直接展開されます。
一方、SWANK版ではこの条件を満たせません。
CLOSのジェネリック関数でストリーム操作を実装した「グレイストリーム」を使っているからです9。
#-swank で囲むことでSWANKなし環境にだけこの宣言を適用します。
(declare #-swank (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))))Code language: Lisp (lisp)4.2. 完成した read-fixnum関数
これで、SWANK版では read-char + char-code 経由だったバイト取得を、本番では read-byte 直呼びに変更できます。
(declaim (ftype (function * (values fixnum &optional)) read-fixnum))
(defun read-fixnum (&optional (in *standard-input*))
(declare #-swank (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 "Read EOF or #\Nul."))
((= 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)本番用の最適化は2箇所の declare と %read-byte の展開内容だけに閉じています。
ループ構造や符号処理などのロジックは1箇所にしか存在せず、フィーチャーフラグは「差異が発生する最小のスコープ」だけを覆っています。
4.3. パフォーマンス比較
100万個の整数を読み取る計測を run-benchmark で実行しました。
実行環境は、AtCoderのコードテスト環境で、負数を30%含む 0〜999999の範囲のランダムな整数をテストファイルに生成し、3回計測のストタイムを採用しました。
| 実装 | optimize なし (ms) | optimize あり (ms) | 対read比 |
|---|---|---|---|
| read | 115 | 123 | 1.00x |
| read-fixnum/char | 22 | 25 | 5.23x |
| read-fixnum/byte | 22 | 22 | 5.59x |
read-fixnum は、115ms → 22ms と read の約5倍速くなりました。read はS式パーサーを通るため整数1個あたりの処理が重く、100万回の呼び出しでその差が積み重なっています。
consedの量は両者とも同じで、これは make-array による配列確保分です。
読み取り自体でヒープアロケーションは発生していません。
ただ、予想に反して、read-char 版と read-byte 版の差はほぼありませんでした。
また、declaim (optimize (speed 3) (safety 0)) も、ほとんど変わらず、誤差の範囲です。
つまり、型宣言と the と macrolet によるインライン展開だけで十分にSBCLの最適化は効いていて、read-char版 で十分そうです。
(defun generate-test-file (path n &key (max 1000000) (negative-ratio 0))
"N個のランダムな整数をPATHに書き出す。NEGATIVE-RATIOは負数の割合（0.0〜1.0）。"
(with-open-file (out path :direction :output :if-exists :supersede)
(loop repeat n
for x = (let ((v (random max)))
(if (< (random 1.0) negative-ratio) (- v) v))
do (format out "~d~%" x))))
(defun bench-read (path n)
"readでN個の整数を読み取る。"
(with-open-file (in path :direction :input)
(let ((v (make-array n :element-type 'fixnum)))
(declare ((simple-array fixnum (*)) v))
(loop for i below n
do (setf (aref v i) (the fixnum (read in))))
v)))
(defun bench-read-fixnum (path n)
"read-fixnumでN個の整数を読み取る。"
(with-open-file (in path :direction :input
:element-type '(unsigned-byte 8))
(read-fixnums n in)))
(defun run-benchmark (&key (n 10000) (path "/tmp/bench-input.txt"))
(format t "~&テストファイル生成中: ~a (~d個)~%" path n)
(generate-test-file path n :max 1000000 :negative-ratio 0.3)
(format t "~&--- read ---~%")
(time (bench-read path n))
(format t "~&--- read-fixnum ---~%")
(time (bench-read-fixnum path n))
(values))Code language: Lisp (lisp)- リーダーマクロとはCommon Lispのリーダーが特定の文字を読んだときに呼び出す関数のことで、たとえば
'fooを(quote foo)に展開する処理もリーダーマクロによる。readはこれらの処理を経由してトークンを評価するため、単純な整数リテラルを読むだけでも汎用的なパスを通る – CLHS: Function READ #+swank/#-swankの#+と#-はフィーチャー式と呼ばれるリーダーマクロで、*features*リストにシンボルが存在するかどうかをリード時に評価してコードを取捨する。SWANKが起動すると:swankを*features*に追加するため、この分岐が機能する – CLHS: Variable FEATURESmacroletで定義したマクロはコンパイル時に展開されるため、実行時には展開後のコードが直接存在する。fletやlabelsで定義した関数は通常の呼び出しコストがかかる点で異なる – CLHS: Special Operator MACROLET- SBCLでは
theの型が実行時に満たされない場合、デフォルトでtype-errorを発生させる。(optimize (safety 0))を設定すると型チェック自体がスキップされ、違反しても未定義動作になる – SBCL User Manual: Handling of Types #.による評価は変数*read-eval*がnilのときに禁止される。信頼できないソースからS式を読む際は(let ((*read-eval* nil)) (read ...))とすることでコード実行を防ぐセキュリティ上の慣習がある – CLHS: Variable READ-EVAL- 64bit SBCLでは
most-positive-fixnumは4611686018427387903（2の62乗 − 1）で、ワード幅63bitのうち1bitをタグに使うため62bitになる。(log most-positive-fixnum 2)を評価すると62.0が返る – The Common Lisp Cookbook: Numbers declaimはファイルスコープのグローバル宣言で、declareはフォームのローカル宣言という違いがある。declareはletやdefunの本体の先頭にしか置けないが、declaimはトップレベルでいつでも書ける – CLHS: Special Operator LOCALLY / Declaration DECLARE(values fixnum &optional)はmultiple valuesの型指定子で、fixnumが必ず返り、それ以外の値は0個以上返り得ることを表す。&optionalはCLHS 4.2.3節で定義されたvalues型指定子の記法で、引数リストとは無関係 – CLHS: Type Specifier VALUES- Common Lispには標準外の拡張として「グレイストリーム」がある。グレイストリームはCLOSのジェネリック関数でストリーム操作を実装するもので、SWANKはこれを使ってストリームをラップする。そのため
sb-kernel:ansi-stream型を満たさなくなる – SBCL User Manual