八発白中

はてなブログに引越しました。

Clack Meetup #1 を開催します

f:id:nitro_idiot:20150120165947p:plain

3月5日 (木) に「Clack Meetup #1」というイベントをサムライト株式会社のオフィスにて開催します。

Clackは拙作のCommon LispにおけるWeb application environmentであり、4年前にリリースされてから先日ようやくv1.0がリリースされました。

Clack MeetupではそのClackと共に、その周辺のエコシステム――WebフレームワークやDBアクセスライブラリ含む――の、Common LispのWeb開発全般の話を扱う予定です。

サムライトでの導入事例など、実際に動いているプロダクトの話も少しする予定なので、興味がある方はぜひご参加ください。

高速なCommon LispのWebサーバ「Woo」を作りました

ここ一ヶ月ほど手掛けていたCommon LispのWebサーバ「Woo」が一応の完成に至りましたのでお知らせします。Clack-compatibleなAPIになっており、現状運用しているClackのWebアプリケーションでそのままお試しいただけます。

高速であることを最優先に設計しており、Hunchentootの4倍、Wookieの3.5倍高速に動きます。現状ではCommon Lispのサーバでは最速ではないでしょうか。*1

Benchmarks

いくつかのCommon Lispのサーバと、Node.js、Go、Pythonのサーバを比較してみました。縦軸はreq/secで、高いほうが多くのリクエストを捌けることを意味します。

f:id:nitro_idiot:20141219152449p:plain

Wooは、PythonのTornadoより約9.5倍、Node.jsの約1.9倍のリクエストを捌けます。一方、Goには少し負けています。

この結果を以ってNode.js遅すぎとか言うつもりは全くなくて、むしろNode.jsがRubyPythonと比べて2倍以上の差をつけているのは純粋に驚きました。Node.jsが速いと言われるのもわかります。

複数CPUコアを有効に使えるように、Workerプロセス数を指定したベンチマークも取りました。

f:id:nitro_idiot:20141219153408p:plain

こちらではRubyUnicornをnginxの裏に置いて試してみました。WooはUnicornの約2.4倍以上のパフォーマンスが出ています。Goよりはさらに差がつけられてしまっていますね。子プロセスへのディスパッチをまともにやらなければ。

ベンチマーク方法などの詳細はWooのリポジトリのBenchmarkをご覧ください。

Installation

インストールには以下のものが必要です。

その後、GitHubからWooをcloneしてbenchmark/woo.lispを実行するとサーバが立ち上がります。

$ mkdir -p ~/common-lisp && cd ~/common-lisp
$ git clone https://github.com/fukamachi/woo
$ sbcl --load woo/benchmark/woo.lisp

Why so fast?

WooがHunchentootやWookieに比べて圧倒的な差をつけているのはなぜ?と聞かれます。

最も大きいのは、non-blockingなサーバであり、さらにWookieと違って裏側でlibevを使っていることが大きいです。これで1.5倍くらいは違いますね。 *2

その他はアプリケーションレベルのボトルネックを丁寧に一つ一つ取り除いていきました。

おわりに

WooはGitHubにて公開されています。フィードバックをお待ちしています。

また、Wooは雇い主であるサムライト株式会社の全面的な協力を得て完成を迎えました。現在サムライトではCommon Lisperを募集しておりますので興味がある方は以下のWantedlyからご応募ください。

*1:高速なものとしてteepeedee2が有名ですが、CFFIのAPI変更に追随しておらず動かないようです。同僚が修正を加えた上でLinuxで試したところ、Node.jsより少し速い程度だった、と言っていたのでたぶんWooのほうが速いんじゃないかな

*2:ベンチマーク時のWookieはlibevent2を使っており、現状はlibuvに移行しています。どちらもlibevよりオーバーヘッドが大きく遅い。

サムライト株式会社に入社しました

somewrite logo

本日11月17日、サムライト株式会社プログラマとして入社しました。

サムライトはCommon Lispという最先端の技術を使う数少ないWeb企業です。

今月の頭までどこかの会社に雇用されるなど想像もしていなかったことです。

それがつい2週間前、兼ねてからTwitter上でやり取りをしていた @Rudolph_Miller が高速な広告配信サーバをCommon Lispで書きたいと言って人を募集しているのを見たことをきっかけに、社員で入る気はなかったにせよ何か共同で開発すれば僕もいくらか助けになるかもしれないと思ってすぐに会う約束をし、対面で詳しい話を聞くにつれ、いよいよ入社してフルコミットしたほうができることも多いだろうと考え、終には「いつまで居られるかわかりませんよ」という念押しをしつつも、一時振るう刀をこの会社に預けることにした次第です。



所感。

この会社には何もありません。従業員は20人程度でありながら、サービスは手広く大胆なほど。その彼らが手狭なオフィスで18個しかない椅子を取り合うように座っている。

さらに驚愕すべきことに、現在プログラマは2人しかいない。しかし、その彼らも孤軍奮闘という悲嘆にくれた様子もなく呑気にCommon LispのBaaSを立ちあげたいなどと放胆なことを言う。しかもそれがCTOと言うからさらに驚きである。

今後、僕はこの会社と共にCommon Lisp界、Webの世界を沸かせることをやります。

これを読んでいる人で、現職で自分でなくともできるような仕事に不満を感じている人。これから大学を出て名を売りたいと思っている大学生。無能で保守的な上司に飽き飽きしている人。 この会社では退職者が遺したクソに縛られることもありません。この会社で一緒に面白いことをやりましょう。

舞台はあります。この舞台で一緒に踊ろうという気概のある方は @nitro_idiot までご一報ください。

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リクエストのパース部分を高速に処理するライブラリを書きました。

既存のライブラリ「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とかもありますね。可能ならnconcnreverseを使えると効率的です。

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

推測するな、計測せよ。
“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 + concatenateを連続で行うような場合に使えます。

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

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

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

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

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

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

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

おわりに

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

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

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

参考

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

*2:SBCL 1.2.4では-4611686018427387904〜4611686018427387903

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

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

自分のTwitpicの画像・動画をダウンロードできるスクリプトを書きました

Twitpicの公式ブログで、Twitpicが今月終了することが告知されているようです。

追記 (2014/09/19): Twitpicが買収されたので終了しない、ということを公式Twitterアカウントでツイートしています。 詳細は今後公開されると思いますが、終了に向けてのダウンロードの必要はなくなりそうです。
追記 (2014/10/17): Twitpicの買収が失敗したようで、再び終了する告知が出ています。

僕は昔少し使っていた程度ですが、それでもサービスが無くなるのは寂しいですね。ブコメで誰か書いているのを見ましたが、こうしてデータが消えていくと文化が後世に残らないので数十年後困ると思う。

ともかく今月の話なので、昔の写真が上がってるからダウンロードしておかないとなー、と思ってバックアップ用スクリプトを書いてみました。

※ちなみに終了告知には「数日中にデータのエクスポート機能を提供する予定」、と書かれているので待っていれば公式のダウンロード機能が使えそうです。

追記 (2014/09/09):

Twitpic公式で写真/動画のエクスポート機能が追加されました。


設定ページの一番下でエクスポートリクエストができ、準備ができたらダウンロードリンクが表示されるようです。


ダウンロードしてみたら、写真や動画だけでなく投稿時のツイート内容がtweets.txtに保存されています。それに倣って僕のスクリプトも同様の内容を出力するようにしました。


投稿日時情報がファイル名に含まれていないのが残念かな……重要だと思うんだけど。

重要そうな機能

  • 動画にも対応しています
  • 投稿日時がファイル名になっているのでいつ投稿したかがわかります
  • ファイル名の最後5ケタはTwitpicのIDです
    • http://twitpic.com/{ID} にアクセスすると対応するTwitpicのページが見られます。
  • 投稿時のコメントをテキストファイルに出力します

必要なもの

使うにはCommon Lisp処理系とQuicklispが必要です。

Common Lisp処理系

特にこだわりがなければSBCLClozure CLがおすすめです。

Mac OSならHomebrewで簡単にインストールできます。

$ brew install sbcl

Ubuntuならapt-getでインストールできるはずです。

$ sudo apt-get install sbcl

Quicklisp

Quicklispをインストールします。

公式サイトの言うとおりにインストールしてもいいですが、以下のコマンドを叩けば一発でインストールできます。

$ (curl -L http://beta.quicklisp.org/quicklisp.lisp && echo '(progn (quicklisp-quickstart:install) (ql:add-to-init-file))') | sbcl

ダウンロード

以下のリンクを右クリックして「リンク先を保存」します。

実行

以下のコマンドを実行します。twitpic-dl.lispの部分は先ほどダウンロードしたファイルのパスです。

$ sbcl --noinform --load twitpic-dl.lisp

f:id:nitro_idiot:20140906105714p:plain

するとユーザ名を聞かれるので自分の名前を入れてEnterを押します。

f:id:nitro_idiot:20140906105549p:plain

ダウンロードが始まります。ファイル名は投稿日時になっています。途中サーバエラーが出た場合は間隔をおいて自動でリトライします。

Ctrl-Cでいつでも終了できます。途中で終了した場合、再度実行すればダウンロードしていないファイルのみダウンロードを再開します。

何か問題があったら@nitro_idiotにご連絡ください。

ソースコード

Gistに上がっています。ライセンスはPublic Domainなのでご自由にご利用ください。

Twitpic backup script