2005-08-21

遅いコードを貯蓄する

私は仕事柄, 書いたコードに実行速度を要求されることがある. 本当はいつも要求されていて, たまにそれに応えるという方が正しいかもしれない... とにかく, 権力者(上司, 顧客, 同僚)から "遅いので速くしろ" というお言葉を日常的に頂く. とはいえできる範囲の高速化は既に済んでいる. 無い袖は振れない.

まわりからの圧力を前にすると, 高速化の余地あるコードがある種の資産に思えてくる. 高速化の "余地" にも色々ある. 直せは確実に速くなる性質の良いもの. 複雑さ故に速くなる "かもしれない" ように見える 不確実性の高い不良債権, まだプロファイルをとっていない未公開株のストックオプション, など. そこで, 優良な財をなす投資の方法 ... つまり遅くてかつ簡単に高速化できるコードを書く方法を, いくつか提案しておく.

アクセサ

変数を直接さわらず, アクセサを定義しよう. できればマクロやインライン関数は使わず, 普通の関数/メソッドとして定義しよう. 速くしろと言われたらインライン化を進めよう.

検証

状態や入力を検証するコードを沢山埋めこもう. assert, 不変条件, 入力の verification などでコードを固める. 速くしろと言われたら, それらを適当なマクロでくくって無効化できるようにしよう.

記録と表示

ログをこまめに保存しよう. 画面にフレームレートを描こう. HTML に応答時間を表示しよう. 主記憶の消費を, 応答時間の分布を可視化しよう. アクセス数を記録しよう. 仕組みはメンテナンスできる範囲で多く細かいほどよい. モジュール単位, フレーム単位. ファイル単位. 速くしろと言われたら, これらの仕組みを少しずつ削ればいい. なおこれらの表示は地味にたもち, またエラー出力とは分離しておく. 専用のファイルやウィンドウを使うのが望ましい.

キャッシュ, バッファ, プール

何かをキャッシングするのはやめよう, 出力のバッファリングはやめよう, スレッドやソケットなどの資源を再利用するのはやめよう. 愚直に計算し, こまめに読み書きし, 素直に要求する. 速くしろと言われたら, 少しずつ倹約をはじめること.

省略

物事を省略するのはやめよう. 描画のカリング, クリッピング. 探索の枝刈り, クエリーの範囲指定. 全部描く. 全部調べる. 全部読む. 速くしろと言われたら, さぼってみるのも良いかもしれない.

パラメタ

パラメタは標準の値を使おう. データベースやサーバは出荷時の設定を, 自分のアルゴリズムなら開発中に使う最も安全な値を選ぶ. 速くしろと言われたら, おもむろに参考書を確認しよう. (しおりは前もってはさんでおいてもよい.) メモリ節約と速度のトレードオフはメモリ節約を優先する. 圧縮率, 画質などもおなじ.

特別な条件

特別な条件は知らないふりをしよう. 特別なサイズに整列したメモリブロック, 自分自身へのネットワーク接続, 同じデータフォーマット間でのコピー. 2 の乗数, 0, 1, 正方形, 一意性制約. なにごとも公平に. 速くしろと言われたら, 差別や区別を考えよう. それまで秘密は自分の胸とコメント, assertion, テストコードに秘めておく.

検索

検索に二分探索やハッシュを使うのはやめよう. 線型探索のように素朴なものほど望ましい. 凝った検索を試すのは, 速くしろと言わてからにしよう. データベース, 文字列検索ではインデクスをつくらないこと.

ソート

素朴で自明なソートを実装しよう ... ただし, 標準ライブラリにソートが用意されているときは諦めてそれを使おう. 不具合がみつかった時の言い逃れが難しい. 自分でソートを書くのは速くしろと言われてからにしよう. (比較用関数の間接参照が遅い, そんな幸せに恵まれることは少ないのだが.)

再帰呼び出し

再帰呼出しをつかおう. 無理にループを使ったり, 末尾再帰にしようとがんばらない. 速くしろと言われたら, スタックの導入を検討しよう. ただし環境によってはスタックオーバーフローの危険に備えること.

多態とインターフェイス

相手の正体を知っている時でも, まずは抽象的なインターフェイスを使おう. Java なら interface, C++ なら仮想関数, C なら関数ポインタ, (dll/COM はちょっとやりすぎ.) 速くしろと言われたら, これらを関数 (Java なら static 関数) におきかえよう. C++ では無理矢理 template 化せず, 場面によっては継承を使っておくのも良い.

コレクション

一種類のコレクションだけを使おう. たとえばリストなら Java の LinkedList, C++ の std::list など, 一種類だけを使っておこう. 速くしろと言われたら, 他のコレクションに差し替えてみよう. ArrayList や std::vector は高速なのでまずは避けておく.

メモリアロケータ

メモリアロケータをカスタマイズするのはやめよう. 常に標準の new/delete, malloc()/free(), あるいはメモリリークチェックなど負荷のあるラッパを使おう. 速くしろ言われてからカスタムアロケータを試そう.

コピー

オブジェクトのコピーでは参照カウンタを避け, ディープコピーをしよう. Immutable オジェクトは共有せず, 要求されただけのインスタンスを作ろう. 速くしろと言われたら, スマートポインタや遅延コピー, インスタンスキャシュをためそう.

戻り値

関数の結果を返すのに出力引数は使わず, 戻り値をセットしたオブジェクトを返そう. C++ の場合, ポインタではなく値で返そう. コピーコンストラクタを積極的に呼出すこと. 速くしろと言われてから, 出力変数やスマートポインタを使おう.

排他制御

スレッドや入出力の排他制御はこまめにやろう. 変数アクセス, IO フラッシュ毎にロックするのが望ましい. 速くしろと言われたら, ロックの粒度を調整してみよう. ただしデッドロックの危険は常に伴う. 無理は禁物.

スクリプト言語

スクリプト言語を組み込み, それを使おう. サーバサイドなら Jython や Groove, クライアントなら Python などを組込み, 面倒の多い部分をその言語で書く. 遅いと言われたら, スクリプト部分をホスト言語で書き直そう. 置き換えができるよう, スクリプトは保守的な使い方に留めるのが無難. フレームワークがスクリプト言語に依存したり, スクリプトの記述で言語機能 (eval とか lambda とか) をフル活用すると後で困ることが多い.

設定, 構成

フラグ, オプションは変数に保存しよう. プリプロセサや定数は使わない. 振舞いは実行時にその変数を参照して変える. (Java ならシステムプロパティが利用しても良い.) 速くしろと言われたら, 変えそうにない項目の周辺からプリプロセッサでくくろう. 継続的統合をしているなら, 各設定項目毎の検証を忘れない. あとに引けない変更は最小化すること. (変更できない設定項目は別れられない恋人のようなものだ.)

最適化オプション

Release ビルドでも最適化を無効化しよう. 速くしろと言われたら, 少しずつオプションを戻していく. C++ では --no-inline を, シングルスレッドのプログラムでもマルチスレッド用のライブラリを使おう. Java では server VM を使わないのはもちろん, プロパティファイルを書換えて JIT もこっそり無効化しておこう.

デバッグ機能

デバッグ機能はフル稼働させておこう. バッファオーバーランのチェック, assert などは常に (Release ビルドでもこっそり) 有効に. ライブラリはデバッグ機能が一番強力なものを選ぼう. _DEBUG, STLport なら _STLP_DEBUG を常につけておく.

ポートフォリオを組む

個々の "低速化" はどれも慎しいものだが, これらは組み合わせによって威力を発揮する. たとえば アクセサを書きつつインライン化を無効にすれば変数アクセスは確実に遅くなる. インターフェイスを抽象化すれば, 記録のためのフックを追加しやすくなる. バッファサイズを変数のパラメタにしておけば, バッファリングの無効/有効は再コンパイルなしに切り替えらえる. バッファサイズが小さければ IO のロックを頻発できる. 状態検証の仕組みには assert を活かせる. 上の全てを試すのがむずかしいだろうから, 有効な組合せを探そう. アプリケーションによるが, だいたい一桁くらいは遅くしておいて良いとおもう.

資産をとりくずす

さて, いざ速くしろと言われたら何から手をつければ良いだろうか. まず締切りと目的をはっりさせよう. 競合製品との比較検討だろうか, 反応速度の印象改善だろうか. サービスの拡大によるスケールだろうか. 目的によってゴールは異なる.

それから測定をしよう. 測定機構が導入されていればそれを使い, なければさっと組込んで計ろう. 現状を知らずに高速化はできない. プロファイルだけでなく, アプリケーションよりの指標も使おう. (フレームレート, 反応時間, 最大同時接続数など.) 測定結果と目的をてらしあわせて具体的な数値目標を決めよう. どうあがいても目的を達成できそうにないなら, 無駄に貯金を使うのはもったいない. またいつか別の要求がくるのだ. 手持を少しだけとりくずして, 努力したことにして済ます.

目的が現実的でコミットに同意できるなら, さあ, とりかかろう. コードベースをブランチしよう. 測定結果もレポジトリにチェックインし, 日々の成果を記録に残そう. いきなり劇的な高速化をしてはいけない. 1 割か 2 割速くする. じりじりと速度を延ばし, 顧客や上司の顔色をうかがう. 設定された目的に誇張があったなら, 途中結果でも満足してくれるかもしれない. "速くなった" と印象づけることができれば, 性能以外の手段と組み合わせて目的を達成できることもある. そんなかんじで, 期日までに少しずつ速度を改善しよう. ただし, 目標を達成してはいけない. まだ高速化できるという誤解を生む. これは非現実的な目標設定の原因になる. 劇的な高速化は快感だし, 英雄扱いは気分がいい. しかし, その誘惑に屈してはいけない. 最大限努力したけど少しだけ及びませんでした. そうアピールする. 少しくらい目標に届かなくても, 他の交渉や調整でなんとかなることは多い. 少しだけ値引きして契約できるかもしれない. GUI の変更によって体感速度を改善できるかもしれない. ハードウェアのもつ "へそくり" を使えるかもしれない.

最後の切札, 確実に高速化できるオプションを一つだけ用意しておく. ふだん高速化を要求されたときに使わないこと. 後がなくなったとき: たとえばクビになりそうな時, プロジェクトが打ち切りになりそうなとき, その他の理由でコードが自分の手を離れる時, それを振舞おう.

不良債券を処分する

速くできるコードが資産だとしたら, 借金/不良債券はどんなコードだろう? 速くできないコードだろうか. 何かおかしい. よくチューンされたコードほど不良債権になってしまう. そこで, "速くできるはずなのに速くできないコード" を不良債権だとしよう. "計測できないコード" はその代表格だ. 計測の仕組みがないコード. プロファイラのおかげで簡単なプログラムは不良債権化しないのだが, プロファイラが使えない環境もある. またプロセスをまたいで動くシステムや, データベースやネットワークのように外部のシステムに依拠したシステムもそのままだと不良債権になりうる. (最近はそういうシステムが多いだろう.) 速くしろと言われたら, 不良債権を気にしよう. ボトルネックの疑いがある不良債権はがんばって処分しよう.

不良債権を処理する ... つまり計測の仕組みのないコードに対して計測の仕組みを組込む ... のは, とても難しい. それは自動テストの仕組みがないコードにテストの仕組みを組込むのに似ている. 大抵はそこで挫ける. 挫けて直感を頼った高速化に走る. やがて高速化破産がおこる. 直感指向の高速化によってコードがメンテナンス不能に追いやられる.

なんとか踏み止まろう. 覚悟を決めて少しずつ償却していこう. まず, コードを汚してでも計測の仕組みを作る. あとで消すのが前提の, 場当り的なものでいい. そのためのブランチだ. 高速化そのものと違い, 計測用のコードは高速化作業が終わったら消すこともできる. 計測は自動でなくていい. 完全でなくていい. 今よりマシにする方法を考える. 問題の範囲を少しでも絞りこむ. 実験と試行のターンアラウンドを効率化する. 決して計測を諦めないこと. 高速化のテクニックを次々と提案する高速化中毒者たちの圧力に屈しないこと.

高速化と投機

資産をとりくずす一方で, 実験としてアルゴリズムやアーキテクチャの改善にとりくもう. 実験は別のブランチでしよう. トランクを破壊してはいけない. もしトランクで実験をしてしまうと, 実験の残骸をトランクから取り除けないまま開発が続く危険にあう. そうした残骸は負債になって, 後のメンテナを苦しめるだろう. アルゴリズムの変更は完全な投機だ. うまくいくあてはない. しかし楽しくもある. 道楽と言っていいかもしれない. "低速化" したコード資産は, もっぱらそうした実験のための時間を捻出するための貯蓄だと考える. もし幸いにして高速化ができたなら, それは油田を掘りあてたようなものだ. 整理をして, 貯蓄に加える. すぐに使わない. 高速化は やれ と言われ, 人的資源(もっぱら時間)を確保できるまでやらないこと.

アルゴリズムの変更に限らず, 一般に高速化は投機的な性格をもつ. 先に示したような優良債券さえ, 測定をしてみると大半はがらくただと気付くことになる. 残念ながら大半のコードはボトルネックになってくれない. 高速化は投機だと意識する. 遅いコードの貯蓄なしに高速化をするのは生活費をとりくずして株を買うようなものだ. 身を滅ぼす. ギャンブラーになりたいのでないなら, 投機の前には測定をして, 自分の残高を見積ろう.

幸い速度は納期と異り, 開発者を増やして解決するものではない. 基本的にはコードを書いた本人にしか高速化の可能性はわからない. (特に速度が重要なモジュールは高速化技術をもつ人間が開発しているはずだ.) だから自分ができないといえばそこで話は終わる. ただし商談も一緒に終わるかもしれない. 意思決定をしよう. プロジェクトの進捗や顧客の顔色をうかがい, 資産と照らしあわせて投機の可否をとろう. 胃の痛む仕事だけれど.

高速化コンサルティング

高速化は開発者自身にしかできないと書いた. しかし例外はある. より凄腕のプログラマがより優れたアリゴリズムとハードウェアの特性を最大限に活かしたコードに書換えて...といった英雄譚のことではない (そういうのもたまにあるけど.) 自信を持って設計したアーキテクチャを否定するバックドアの開設, メンテナンスを思うと青ざめるほど不条理で奇怪なマジックナンバーの埋め込み, 書いたコードを無に帰すサードパーティ・コンポーネントの導入. このような開発者自身の利害と衝突する高速化を, 当人が進んでやることはない. とぼけてやらないこともあるし, 気付けないこともある. この種の高速化は他人にしかできない.

仮にこの "他者による" 高速化を専門とした仕事があるとする. その仕事はたとえばこんな風になるだろう: 設計の意図をあえて無視して冷徹に計測結果を分析, まったく離れたモジュール間のタイミング依存, 計算負荷の相関に着目する. 謎のグローバル変数に保存した特別な状態をループカウンタ設定のヒントとして参照する...

専門職ではないけれど, 私からみるとほとんど黒魔術に見えるこうした作業を得意とする人が世の中にはたしかにいる. 彼らは経営陣の判断で性能問題が火の車となっているプロジェクトに投入され, 次バージョンでのメンテナンスはおろか翌週のコード・リリースにむけた安定化作業など現場の都合を無視して次々と謎のフラグをつけたし, なぜだかよくわからないまましかし確かに高速化を達成する. プロジェクトは打ち切りを逃れる. デスマーチはつづく. その結果うまれたバグを直すのはプロジェクト担当者の仕事になる.

私は彼らを "高速化コンサルタント" と呼びたい. 開発者に嫌われながら仕事をし, しかし企業経営の点からは有意な成果を残す人々. 同じチームで働きたくはないけれど, いないと困るハッカーたち. そして彼ら高速化コンサルタントの世話にならないよう, 私は "遅いコード" 資産を慎重に無駄なく運用したいと願うのだ.

でもここ一年ですっからかん, 毎日ひやひや暮らしています...