Cより高速なCommon Lispコードを書く

Cで書くコードの方がCommon Lispで書くより速いって人がいたら、それは彼のCの技量が高すぎるってことだね。

“If you can't outperform C in CL, you're too good at C.” — Eric Naggum

最近、Common Lispの非同期Webサーバ「Wookie」を高速化する過程で、ボトルネックになっていたHTTPリクエストのパース部分を高速に処理するライブラリを書きました。

• fast-http - A fast HTTP request/response parser for Common Lisp

既存のライブラリ「http-parse」よりも約10倍速く、Cのライブラリ「http-parser」より5%ほど高速です。

追記 (2014/10/26):
最適化をやり直し、現在は「http-parse」よりも約27倍速く、Cの「http-parser」より43% (1.4倍) ほど高速です。

追記 (2014/11/05):
設計を見なおして再実装し、現在はCの「http-parser」より6.4倍高速です。

比較対象のCのhttp-parserはNode.jsで使われているものなので、かなりの高速化が施されていると推測されますが、それをCommon Lispに移植したら少しだけ速くなりました。処理系依存のハッキーなテクニックを使ってるわけでもなく標準の機能だけで。

そこで今回は、Common Lispで高速なプログラムを書くときに僕が考えていることを共有しようと思います。ほとんど我流なので間違っているかもしれません。その場合は指摘してください。

処理系はSBCLを前提としています。

プログラムの設計段階で考慮すべきこと

早すぎる最適化は諸悪の根源である。
“Premature optimization is the root of all evil” — Donald Knuth

「早すぎる最適化」という言葉はプログラマの間で有名です。どこがボトルネックかを知ることなくやたらめったらハックをしていくと無駄にコードが複雑になることを諌める言葉です。

とはいえ、このプログラムは高速に動く必要がある、というときには設計段階で考慮しておかなければならないことがいくつかあります。

その一つがデータ構造です。

データ構造を決める

ルール5: データはすべてを決定づける。もし、正しいデータ構造を選び、ものごとをうまく構成すれば、アルゴリズムはほとんどいつも自明のものになるだろう。プログラミングの中心は、アルゴリズムではなくデータ構造にある。

“Rule 5. Data dominates. If you've chosen the right data structures and organized things well, the algorithms will almost always be self­evident. Data structures, not algorithms, are central to programming.” — Robert C. Pike

遅いプログラムは、使っているデータ構造が間違っていることが多いです。一番ありがちなのが、何にでもリストを使うというもの。

しかし、Common Lispは豊富なデータ型があり、それぞれの特性を知り、適切にデータ構造を使い分けられることが高速なプログラムを書く近道です。

List vs. Vector

たとえばListとVectorには以下のような特徴があります。

List

• 長所
  • 可変長のデータを作るときに向いている
  • 要素の型は何でも良い
  • 部分的に切り出して使うのが楽
• 短所
  • 長いリストの連結などがONの効率性
  • 長さをとる (length) の速度が線形時間かかる
  • indexを指定したランダムアクセスに向かない

Vector

• 長所
  • simple-vector (非可変長のベクタ) は高速
  • 要素の型がすべて同じときは型宣言をすることで高速になる
  • indexを指定したランダムアクセスに向く
• 短所
  • 部分的に切り出して使うみたいなときに大変

高速なプログラムを書くには、可能なら長さ固定で要素の型がすべて同じようなVectorを利用することを検討すべきです。

長さを必ずしも固定にしなくても、1024個のバッファを作って数回イテレートするほうが高速という場合もあります。

Hash Table vs. Structure vs. Class

また、似た比較として、ハッシュテーブル、構造体 (Structure)、クラスの使い分けも重要です *1。

Hash Table

• 長所
  • キーに任意のデータが使える
• 短所
  • アクセスが遅い
  • 継承はできない

Hash Tableを作る関数make-hash-tableはキーワード引数:testでテスト関数を指定することができます。キーにシンボルしか使わない場合は’eq (ポインタによる比較) を指定するとアクセスが高速になります。

Structure

• 長所
  • 軽量
  • 高速
• 短所
  • 継承はできない (:includeを使って他の構造体からfieldだけもらうことはできる)

Class

• 長所
  • 継承ができる
  • つまりユーザに拡張性を残すことができる
• 短所
  • どのメソッドやアクセサが呼ばれるかが実行時に判定されるので遅い

Common Lispでは、Structureは内部的には配列になっており、かなり高速です。キーが固定のオブジェクトをいっぱい作るようなときはStructureを使うと良いです。

ただし、これはトレードオフでもあります。

もし書いているプログラムが拡張性を持つ必要があるならClassを使ったほうがいいです。ユーザが独自の継承クラスを定義したり、メソッドモディファイアで挙動を変更できる、ということはプログラムの種類によっては重要です。

データのコピーをするな

せっかく良いデータ型を選んでも、データのコピーを行うと遅いしメモリも食います。

とはいえ難しいのは、どこでデータのコピーが行われるのか、というのが自明ではないこと。

たとえば、subseqは必ずシーケンスのコピーを返します。たとえ(subseq seq 0)と呼び出しても、新しいシーケンスを作ります。既存のhttp-parseが遅い理由の一つはこれでした。

シーケンスの部分データを切り貼りして最終的にシーケンスを返したい、ようなプログラムの場合は「XSubseq」を使うと高速です。

他にはリストに対するappendとかreverseとかもありますね。可能ならnconcやnreverseを使えると効率的です。

何はともあれベンチマーク

推測するな、計測せよ。
“Don’t guess, measure!”

書き終わったら、何はともあれベンチマークを取ります。

ベンチマーク

Common Lispには標準でtimeというマクロがあり、実行時間やメモリ・CPU使用率などを表示してくれます。

(time (loop repeat 100000 do (http-parse parser callbacks data)))

;-> Evaluation took: ; 0.431 seconds of real time ; 0.431906 seconds of total run time (0.430379 user, 0.001527 system) ; 100.23% CPU ; 1,288,960,305 processor cycles ; 0 bytes consed

これは今後何度も実行することになるので、run-benchmarkなどの名前でどこかに定義しておくのは重要です。修正した内容が高速化に役立ったか、むしろ遅くなったかとかが即座にわかります。

また、この数値がどんどん速くなっていくのを見るのは楽しいです。意外と重要。

プロファイル

プログラム内でどの部分に時間がかかっているかを知るにはプロファイルを取ります。

SBCLでは標準でプロファイラが付属しています。

;; プロファイルを取るパッケージ名を指定 (sb-profile:profile “FAST-HTTP” “FAST-HTTP.BYTE-VECTOR” “FAST-HTTP.PARSER” “FAST-HTTP.URL”)

;; 何かコードを実行 (time (loop repeat 100000 do (http-parse parser callbacks data)))

;; プロファイルレポートを表示 (sb-profile:report)

fast-httpのプロファイル結果は以下のようになっています。

seconds | gc | consed | calls | sec/call | name

 0.000 |      0.000 |  32,960 | 43,000,000 |   0.000000 | FAST-HTTP.PARSER::CHECK-HEADER-OVERFLOW
 0.000 |      0.000 |       0 |    200,000 |   0.000000 | FAST-HTTP.PARSER::INIT-MARK
 0.000 |      0.000 |       0 |          1 |   0.000000 | FAST-HTTP.PARSER::MAKE-MARK
 0.000 |      0.000 |       0 |          1 |   0.000000 | FAST-HTTP.PARSER:MAKE-LL-CALLBACKS
 0.000 |      0.000 |  81,712 |    100,000 |   0.000000 | FAST-HTTP.PARSER:HTTP-PARSE
 0.000 |      0.000 |       0 |          1 |   0.000000 | FAST-HTTP.PARSER:MAKE-LL-PARSER
 0.000 |      0.000 | 439,072 |    100,000 |   0.000000 | FAST-HTTP.PARSER:HTTP-PARSE-HEADERS
 0.000 |      0.000 |       0 |    800,000 |   0.000000 | FAST-HTTP.URL:PARSE-URL-CHAR

---

 0.000 |      0.000 | 553,744 | 44,200,003 |            | Total

estimated total profiling overhead: 62.41 seconds overhead estimation parameters: 6.e-9s/call, 1.412e-6s total profiling, 5.8999996e-7s internal profiling

どれも合計0秒以下なのでちょっとわかりにくいですが、上から順に時間がかかっている関数が表示されています。GCにかかった時間、メモリの使用量 (consed)、何回呼ばれたか、呼び出し1回あたりの実行時間が並んでいます。

言うまでもなく、対処するべきは上の方にある関数からです。

まずはcallsの欄を見て、その関数が自分の予想を超える回数呼び出されているとしたら、それを減らす方法を考えます。無駄なループなどが見つかるかもしれません。

型宣言とoptimize

ここからはプロファイラの結果に基いて、個別の関数を最適化する方法です。

けど、楽してプログラムが高速になるなら、それほどうまい話はないですよね？

適切なデータ構造を使っている場合、型宣言を追加するだけでかなり高速になることがあります。

特に、「数値」と「配列」に関しては顕著です。

もし変数の数値がfixnumの範囲 *2 に収まるなら(declare (type fixnum 変数名))とすると、数値演算や比較の関数がコンパイル時に決定できるので高速になります。

また、配列がsimple-vector (非可変長) の場合、要素の型がすべて同じ場合なども型宣言はかなり有効です。

たとえば (unsigned-byte 8) のsimple-vectorは以下のように宣言します。

;; 長さ不定の非可変長のバイトベクタ (declare (type (make-array (unsigned-byte 8) (*)) 変数名))

長さも固定の場合は以下のように書けます。

;; 長さ3の非可変長のバイトベクタ (declare (type (simple-array (unsigned-byte 8) (3)) 変数名))

型宣言をしたらoptimize宣言も追加します。

(declare (optimise (speed 3) (safety 2)))

speedは速度優先でコンパイル、safetyは実行時に型チェックを行うかどうかを表しています。(safety 0)にすると実行時に型チェックを行いません。

Common Lispにはlocallyというスペシャルフォームがあり、部分的にdeclareすることもできます。通常は(safety 3)にしておき、ホットスポットのみ(safety 0)にしたりできます。Common Lispの便利なところですね。

関数のインライン化

関数自体は高速だけど、呼び出し回数が多い場合は関数呼び出しコスト自体が高くつくことがあります。

そういう場合は関数をインライン宣言することで呼び出しコストをゼロにできます。

(declaim (inline 関数名))

ただし、インライン化するとプロファイル結果に出てこなくなりますし、デバッグもしづらくなるので適度に使うべきです。

コンパイル時までに計算できることはする

ここからはちょっと大変で、プログラムによって最適化の方法が変わってきます。

一つの方針として、「コンパイル時までに決定できることは決定しておく」という方法があります。

たとえば以下のような関数があるとします。

(defun invoke-callback (parser name) (let ((fn (symbol-function (intern (concatenate 'string "PARSER-" (symbol-name name))) parser))) (when fn (handler-case (funcall obj) (error (e) (princ e *error-output*))))))

(invoke-callback parser 'body-cb)

実行時にシンボルをinternしてfuncallしています。しかし、引数が定数なので、internまではコンパイル時に解決できます。同等のマクロとして再定義したほうが高速です *3。

また、もっと小さな範囲で解決したい場合はリードマクロの#.が使えます。

これは、後に続く式をリード時に実行し、その結果を式に埋め込むものです。リード時に解決できるものならこちらが使えます。

(\= byte #.(char-code #\A))

(番外編) 高速なライブラリ

せっかく高速なプログラムを書いたのに、使っているライブラリが遅いせいで全体が遅くなる、という場合があります。そのため使うライブラリが高速かどうかを知っておくことは重要です。

たとえば以下の3つのライブラリは高速に動作します。

• fast-io: バイトベクタを高速に使うライブラリ
• XSubseq: 高速にsubseqを行うライブラリ
• jsown: JSONライブラリ

ただし、fast-ioを使えば必ずしも高速というわけではなく、長さ不定のバイトベクタを作る場合などに効いてきます。

XSubseqはsubseq + concatenateを連続で行うような場合に使えます。

JSONライブラリではcl-jsonやyasonなどがありますが、これらは拡張性を優先しているため遅いです。高速なJSON処理が必要な場合はjsownが使えます。

高速なライブラリを見分けるには

ライブラリが高速かどうかを見分けるのに僕が見ているポイントなどを書いておきます。

• クラスを使っていないか

クラスを使っているライブラリは実行速度より拡張性を優先しています *4。

• flexi-streams (trivial-gray-streams) を使っていないか

flexi-streamsを始めとしたGray Streamsはメソッド呼び出しを行うので遅いです。

• ベンチマーク用のコードがあるか

ベンチマーク実行用のコードがあると、そのライブラリは速度を重要視して書かれている可能性があります。

おわりに

僕はこんな感じで高速なプログラムを書いています。

他の言語だと高速なプログラムはCで書いてFFIで繋ぐみたいなことをしないといけないけど、Common LispだとCommon Lispで書いても高速なのがいいですね。

最適化って、努力した分だけ利くってわけでもないのでつらいですが、最終的に高速なCommon Lispコードが書けるとかなり脳汁が出るのでおすすめです。

参考

• How to make LISP go faster than C (PDF)
• John Fremlin's blog: How to optimise Common Lisp under SBCL: profiling (draft)
• 最適化 - Common LISP users jp

*1:Property listやAssociation listのような、オブジェクトをlistで代替する方法もありますが、言うまでもなく遅いので無視します

*2:SBCL 1.2.4では-4611686018427387904〜4611686018427387903

*3:同等のことをコンパイラマクロですることもできます。関数として定義しておきたい場合はコンパイラマクロを使います。

*4:もちろん、クラスを使っていてもコンパイル時に走るコード (マクロ内でしか使われていないとか) なら問題ありません。