直感で性能改善をするな！
こんにちは、Lumi です。最近『A Philosophy of Software Design』という本を読み終えて、個人的な感想を呟きたいところでした。この記事が感想文の一つであります。この本は、コードの複雑度（complexity）を減らすために、エンジニアが日々の開発で注意を払うべきことを述べています。おすすめです。
例
まず実際に起こった事例を見ましょう。
問題
以前の記事にも話したことですが、ある試行の成功確率は p であり、その試行を n 回（百万レベル）シミュレートしてください、 という要件がありました。実現方法は、[0, 1) 範囲の小数をランダムに生成し、その小数が p より小さいであればその試行が成功したと見なし、この操作をｎ回行うことだけです。
しかし、この極めてシンプルな方法を書く前に、未熟な筆者が思わずこう考えました：
「同じことを百万回繰り返すって、遅くならないんですか？」
「いや絶対遅いでしょう！こんな暴力的な方法より速い方法絶対あるでしょう！」
と思って、まず違う方法を探しました。そして直ちに思い出したのは、
「これ、普通に、二項分布
二項分布の試行回数ｎと確率ｐが既知数だから、成功回数のサンプリング（つまり二項分布による乱数生成）ができる何らかの公式があるはず。
偽りの改善策
見つけた二項分布乱数生成のアルゴリズムは二項分布の英語 Wikipedia Binomial distribution の最後にあります（日本語 wiki には記述すらない）：
Computational methods - Generating binomial random variates
One way to generate random samples from a binomial distribution is to use an inversion algorithm. To do so, one must calculate the probability that Pr(X=k) for all values k from 0 through n. (These probabilities should sum to a value close to one, in order to encompass the entire sample space.) Then by using a pseudorandom number generator to generate samples uniformly between 0 and 1, one can transform the calculated samples into discrete numbers by using the probabilities calculated in the first step.
正直これを見るだけでどうすべきか全く分かりません。最後は Swift で書いた統計関連のフレームワーク swiftstats のソースコードを読んでからわかってきました：
二項分布による乱数を生成するには、まず [0,1] 範囲で閾値Tをランダムに取って、そして累積分布関数の計算します。ｋ値を０からｎまで順次に累計確率計算し、その累計確率が閾値Tを超える時に取ったｋは最後の結果になります。
理解していれば結構簡単な原理ですね。しかしこの方法を実行して性能を比較したところ、前述の暴力的な方法より遥かに遅いことがわかりました。 まぁ、コードで比較することまでもなく、普通に計算量から考えても、絶対こっちの方が遅いでしょ。
そして、最初から「絶対遅い」と思った方法の実行時間は、60ms でした。
そう、時間と気力を使って、二項分布乱数生成の仕組みを検索して理解して、ソースコードを読んで、実際に書いて、性能を測って、ここまでしても性能を改善したい方法のもともとの実行時間は、60ms でした。
参ったな、自分に。
少なくとも二項分布の乱数生成方法を学んだじゃないか
性能改善する前にまず測りましょう
本題に戻ります。
本の第20章「Designing for Performance」は、ソフトウェアの性能とコードの複雑度、両者の軽重を判断する方法を述べていました。
20.1 節「How to think about performance」の冒頭部分は、次のように書かれています：
If you try to optimize every statement for maximum speed, it will slow down development and create a lot of unnecessary complexity. Furthermore, many of the “optimizations” won’t actually help performance.
そして20.2節「Measure before modifying」：
It’s tempting to rush off and start making performance tweaks, based on your intuitions about what is slow. Don’t do this! Programmers’ intuitions about performance are unreliable. This is true even for experienced developers. If you start making changes based on intuition, you’ll waste time on things that don’t actually improve performance, and you’ll probably make the system more complicated in the process.
笑い出すほど前述筆者の行動に正確に当てはまりました。
ここで著者が与えてくれたアドバイスが、性能改善する前に、まともに既存コードの性能を測ることです。目的が二つあります。
- 一つ目は、どの部分が性能への影響が一番大きかったのを知ることができます。もしまともな測量をせず、ただ統合的にテスト（筆者の場合は iOS アプリを起動して操作する）をすれば、遅いことは感じられますが、一体どこかが足を引っ張てるか、深くまで探り出すことはできません。ソフトウェアの各部分の性能を調べるには、細かく測ることが必要です。
- 二つ目は、基準値を設けることで、性能改善した後に、本当に改善したかどうかを確認できます。もし大きな改善がなければ、元のコードに戻した方が望ましい。僅かな改善のために複雑度を引き入れる理由はありません。
ちょうど最近 UIView の描画について勉強してますが、Apple 社のあの古い『View Programming Guide for iOS』の中で Tips for Using Views Effectively 節でも全く同じことを述べました：
Important: Before optimizing your drawing code, you should always gather data about your view’s current performance. Measuring the current performance lets you confirm whether there actually is a problem and, if there is, gives you a baseline measurement against which you can compare future optimizations.
感想として、本で話されたテーマでもありますが、ソフトウェア開発は時間面で要求されていることが結構あります。急いで開発している場合には、性能改善の優先度があまり高くないですが、筆者のようにゆるい独立開発の場合、「じっくり考えて最初から最適のコードを書こう」という考えによく陥ります。この機能優先開発と真逆な方向に極端に行ってしまって、時間を浪費することもよく出ています。今後は注意すべきですね。
余談ですが、勝手に性能改善しようと思ったのに、実際に改悪をやらかしたのは今回だけではありません。iOS 分野の話ですが、性能改善のためわざわざグラフィック計算用のフレームワーク Accelerate を普通のアプリに導入して並列計算するため、変数たちを余分な Array に格納することにしてしまいました。そして各事情があって、最後に得た教訓は、標準ライブラリの for...in や map による並列計算はそこまで遅くない、それに比べて Array に変数の代入と、 copy-on-write 特性による引用数の検査のほうが遅いことです。
まとめ
この記事は、筆者がソフトウェア性能改善に関する事例と、本『A Philosophy of Software Design』の性能と複雑度における議論を紹介しました。
まとめにすると：
- 開発者がソフトウェア性能に対する直感は大体当たらない
- 更にその直感の上で性能改善は絶対しないこと
- 改善する前にまず性能をまともに測りましょう
以上です。
Discussion