2010/06/26

性能へのアプローチ

http://twitter.com/yoriyuki/status/17071304021

Listp好きの人って、なぜLispをCやPythonやJavaとばかり比較して、HaskellとかMLとかとは比較しないんだろう。そのほうがよっぽど面白いのに。と、これを読んで思った。http://bit.ly/cnrWxy

ここでは性能の話をしていたから。性能の話なら、一応広く信じられているのが Fortran/C/C++あたりは性能が出るってことなんで、チャレンジするなら そっちを相手にせざるを得ない (Cf. As Fast As Cee)。 LispとMLで性能比較してもアピールする読者がごく限られるだろうし。 自分もこのネタは何度も書いてて飽きてるんだけどねぇ。 あとまあ、自分がそれでコードを書いて性能を追求したことのある言語が CとLispくらいだから、というのもある。 Haskellでどうやって性能を出したらいいのかわからないもの。

ただまあ、おおまかな傾向というのは言えるかも。

たぶん、HaskellにせよMLにせよ、性能へのアプローチの柱になってるのは コンパイラをとにかく賢くするってことだ。 コンパイラがうまいコードを出せるようなヒントの与え方、 ってノウハウはあるけれど、 最後の最後はやっぱりコンパイラにお任せ。 Schemeもわりとそっち寄りのところがあって、 例えばcall/ccはナイーブに実装するととても遅くなるのだけれど、 「それは実装がタコだからだろ」で済まされる。 理屈の上で速い実装が可能ならば、それをしていないのは 意識的な選択でなければ実装者の怠慢とされる。

Common Lisp陣営は逆の立場。今、ここに、目的の性能を達成できる Sufficiently Smart Compilerが無いのなら、ぐだぐだ言わず 俺に低レベルコードを触らせろ、というわけだ。 なぜって、アプリケーション特有の最適化のツボを一番知っているのは アプリケーションプログラマであって、コンパイラ作者じゃないのだから。 コンパイラ作者が一番最適化できるなんてのは幻想、あるいは傲慢。 (Naughty Dogのように、アプリケーション作者=コンパイラ作者である場合は別で、 その場合は効果が最大となるけどね)。 実際問題として、 例えば「確実に、ここからここまでは一切アロケーションを行わない」という コードは必要とされるわけですよ。コンパイラが解析を頑張って、その間に 作られるオブジェクトはどこにもリークしないってことを証明できれば アロケーション無しのコードを吐けるだろうけど、 そうでない時に「コンパイラがタコでした」では済まされないよ、と。

現実的には両者のハイブリッドで行くしなかないと思うのだけどね。 アプリケーション作者が一番ツボを知っているというのはたぶん真実だけど、 その部分のコードというのは全体の1%くらいで、残りの99%は コンパイラの一般的な最適化で頑張ってくれた方がずっと良い。

ただ、関数型言語陣営がSufficiently Smart Compilerの存在を 当てにしているのだとすると、ちょっと危うい見通しがある。 今現在、関数型言語のひとつのコンパイラ、例えばghcの開発に関わっている人間/予算と、 C++のひとつのコンパイラ、例えばiccの開発に関わっているそれとを比べると、 後者の方がかなり大きいだろう。 また、最適化というのは最適化したいアプリケーションがあって始めて 進むものなので、アプリケーションの量も多いに越したことはない。 さらに、プロセッサもまた主流の言語処理系が吐くコードのパターンを意識して作られる。

結局、理屈の上で関数型言語の方が最適化しやすいのだとしても、 性能の面で主流の言語が強くなるポジティブフィードバックループの前では、 理論上の優位点なんてのはわずかなアドバンテージでしかない。 その優位点が本当に現実の問題を解決するか、ということを証明するのは、 関数型言語プログラマに課された仕事だろう。

★ ★ ★

性能性能と言うけれど、関数型言語のアドバンテージは別にあるんじゃないの、 という意見もあるかもしれない。そりゃもちろんそうだけれど、 だからといって性能の方を妥協すべきではない。

Haskellで書いたらこんなに綺麗、型不整合のバグとも無縁でハッピー、 っていうのはプログラマにとっての大きなメリットだけど、 それが商用プログラムなら、お金を出してるお客さんにとっては 出来上がったものが期待した機能と性能を提供するかどうかが第一で、 プログラマがハッピーかどうかは二の次だ。 プログラマが楽しいと生産性が上がりますよ(=期間が短いので安くできますよ)、 ってのはアピールポイントだけど、安くても必要な性能が出なけりゃ意味が無い。

ハードが速くなってきたから性能を気にする時代じゃなくなった、 なんて言う人もいるけれど、 (世界中で求められている総計算量/世界中の総計算資源)を考えれば、 むしろ大部分のコードは今以上の性能を求められてると言えるんじゃなかろうか。 そりゃ周辺部分では性能要件は緩くなってきたけれど、 言語としてそういうニッチだけを狙うというのは目標が小さかろう。 (特定のビジネスや特定の処理系がポジションとしてニッチを狙うのはありだが。)

★ ★ ★

さてそろそろ、12億レコード喰わせるのに3時間かかってる処理を 50倍に高速化する作業に戻らねば。

Tag: Programming

2010/06/22

gitメモ

gitにもだいぶ慣れてきた。 仕事のプロジェクトでは最近Gerritが 導入され、パッチを手元のトピックブランチから直接提出できるようになったので、 gitのワークフローで 書いたフローよりも簡単なフローで回している。

• トピックブランチ work-FOOで作業。
• パッチ作成は別ブランチwrap-FOOにて。詳細なコミットログclog-FOO.txtを書いといて

  git reset --hard version1.0
  git merge --squash work-FOO
  git commit -F clog-FOO.txt
  テスト
  git push gerrit HEAD:refs/for/version1.0
  

  これでパッチがレビューに回る。

最近良く使うのはgit stash。 例えばトピックブランチwork-FOOで作業中、wrap-BARでのパッチが差し戻されて fixしなくちゃならなくなったら:

git stash                  # 作業中の変更をコミットせずに一時退避
git checkout work-BAR
...作業、コミット...
git checkout wrap-BAR
...パッチ作成、gerritにpush...
git checkout work-FOO
git stash pop              # 変更中の状態に戻す

いるべきブランチとは別のブランチで作業を進めちゃった時なども git stashしてブランチを移動後git stash popで変更だけ移せる。便利。

Tags: Programming, git

2010/06/21

言語Xは速い、というのは

昨日のエントリへのリンクが拡散しているようなのでちょっと補足めいた雑談。

定量的な速度の話になった時点で、純粋な言語そのものではなく 処理系込みの話になる、っていうのはいちいち断らなくてもいい…よね? 「実際にそういうことができる処理系が今存在しているか」っていうのは 言語選択に影響を与えるファクタであろうと思う。

普通に書いたLispと普通に書いたCならCの方がずっと速い。 Lisp版の方が安全で、簡潔で、汎用的だろうけれど。 違いが出るのはそっからどこまで追い込めるかという伸びしろの部分なんだけど、 それを重視すべきかどうかというのはプロジェクトに依存する。 コンパイラを出し抜いてまで性能を稼ぐ必要のある案件っていうのは 全体の割合では減ってきてはいるだろうと思う (もっとも、サーバサイドの スケーラビリティが重視される流れになって、「性能が足りなければ マシンを増やせばいいじゃない」とか「2年待てばチップが速くなるよ」 なんて能天気に構えていられなくなってきてはいると思うけど)。

個人的にはCommon Lispの処理系はこの先もっと頑張らないとまずいんじゃないか と思ってる。といっても普段使ってる処理系はAllegroだけだし、それも 限界まで使い込んでるわけじゃないので外してるかもしれないけど。

• inter-proceduralな、あるいはプログラム全体を見ての最適化はもう C/C++では普通だけれど、Common Lispの場合、関数単位でのダイナミックな 置き換えがいつでも可能という前提があるため、ちょっとこの分野で遅れを 取っているのではなかろうか。インライン展開程度ならマクロで、 inter-proceduralな情報を利用することで可能になる型チェックの 省略などについては人手で型宣言をつけてやることで補償できるけれど、 ソフトウェアの規模が増大すれば、自動化しないと破綻するだろうし。
• Lisp族というくくりで言えば、Stalinがwhole program analysisの 強さは証明しちゃってるのだけど、コンパイル時間が増大するのは大問題。 C++もそれでつまづいてる。ここはひとつ、動的言語の誇りにかけて、 全プログラム解析とインクリメンタルな関数の置き換えを両立させて 欲しいものだ。例えば関数を動的に置き換えると関数毎に閉じた最適化に リセットされるけど、そのままほっとくと勝手に解析が進んで次第に 最適化の範囲が広がってくとか。
• 型というかメタ情報に対するサポートってのはもっとあっていいと 思うんだよね。Allegro CLだとfixnumをメモリアドレスと見なして 生メモリに直接触れるので(正確には8byte alignedなアドレスを3bitシフトした 値をfixnumで扱うんだけど、fixnumのタグが000なので ネイティブコードレベルではint64_t*で書いてるのと同じコードになる)、 例えばそれを使ってshared memoryをmmapした領域に 自分でメモリアロケータを書けたりするんだけど、 Lisp的にはアドレスとfixnumの区別がつかないんで、 void*とintptr_tの区別があるCよりも状況が悪い。 がっつり型検査しろとは言わないけど、「ここはaligned pointerだよ」、とか 「ここはaligned pointer同士の差分だよ」とか宣言しといたら ある程度自動的に矛盾箇所 (差分だけ使ってmemrefしてるとか) は 検出できるだろう。少なくともそういう検証ルーチンをコンパイラに組み込める フックがあったらいいなあ。自分でcode walker書けばできるんだけどさ。

「言語よりは環境の問題」と言えばそうなのかもしれないけれど、 マクロで低レベルコードを吐かせたり、なんていう話になってくると 言語と処理系と開発環境は相互に支えあってて切り離しては語れないよなあ、 とも思う。処理系と独立した言語仕様があること自体は、 プログラムの正当性の検証という見地から重要なんだけどね。

Tags: Programming, Lisp

2010/06/20

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

Valvallowさんの『Lisp は「C 言語並みに速い」「C 言語より速い場合がある」』 を読んで、 故Eric Naggumの c.l.lへのポスト を思い出した。

一年以上前にCommon Lispで書いためっちゃCPUヘビーな関数を、 ものは試しと最適化してみたら、一回の呼び出し当たりダメダメな623µsから 快適な4.7µsに縮んだよ。

全く同等の機能を持つCの関数は呼び出しあたり92µsかかっていたんだけど、 みんなそこまで最適化して満足してたんだ。 Common LispだとCでやるよりもずっと素早く色々なアルゴリズムを試せるから、 Cでひとつ最適化を試してる間に全く別の方法やアプローチを試してみることが できる。こういうことはほんとに良くあるんだ。 つまり、Cプログラマが最適な実装を見つけ出すよりも速く、 良いCommon Lispプログラマは最適なアルゴリズムかつ最適な実装を見つけることが 出来るってこと。

Cで考える連中はCが速いって思ってる。 でもそれは、彼らがCommon Lispが遅いって思っている以上に真実からは遠いんだ。 本当に速いCコードを書くのはとてつもなく難しいんだぜ。 下手するとコンパイラの吐くコードを眺めて、 結局自分でアセンブリを書くハメになったりする。 俺もCPUから最後の血の一滴まで絞り出すようなコードを書いたことはあるけれど、 Allegro CLのインストラクションレベルプロファイラや ハック可能なLAP (ありがとう、Duane!)、それからコンパイラマクロによる コード変換 (これはCLの標準機能だ) を使わずにやるのは難しかっただろうな。 Cプログラマはこういう道具を持ってないんだよ。

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

(DuaneはFranz Inc.のDuane Rettig。LAPはLisp Assembly Program。 まあインラインアセンブリみたいなもの。)

このポストは1999年のものだけれど、 マクロと低レベル機能の組み合わせで、色々がアルゴリズムが効果的に 試せるってのは今でも当てはまる。 ただ、今の時代だと、Allegro CLにも不満はあるなあ。 キャッシュミスの影響とか簡単に見られるようになってくれると有難いんだけどなあ。

Tags: Programming, Lisp

2010/06/20

テストの最適化

テストの話を出したのでついでに。

今関わってるプロジェクトでは、標準のテストを流すのに25分くらいかかる。 一応もっと速い簡易テストもあるんだけれど、カバレッジが低くて 自分が触っている範囲にはあまり有効でない。 わりと、障害時対策とか高負荷時のバイパスとかそういうあたりを 触ることが多いので、正常系のテストはあんまり役に立たないのだ。

とは言っても、テストが重い理由は他にもあって、単体テストと結合テストが ちゃんと分けられてないんで、ちょっとしたことを試すのにも依存する モジュールがぞろぞろついてきたりしている。このへんうまくスタブを書いて 単体テストだけに絞ればもっとずっと良くなると思うんだけど、 なかなかそこまで手が回らない。

テストの「効率の悪さ」というのもカバレッジ分析と同じ原理で 測れるかなあ。テスト実行中に極端に重複して実行されている パスがあったら、多分そこが改善の余地があるってことだろう。 ああ、でもループ内で実行される関数はそれだけ回数が多く出てきちゃうから、 そのぶんの効果はさっぴかないとならないか。何にせよ、「ここは無駄なテストを しているよ」と指摘してくれるツールがあると便利だろうなあ。

(ちなみにAllegro CLにはカバレッジツールがついてるんだけど、 フラグを有効にしてリコンパイルしないとならないので まだうまく使えてない。(declare (optimize (speed 3) (debug 0)))な コードが大量にあるので結構面倒なのだ。)

Tag: Programming