パフォチューで1週間無駄にした男が考えた最強のボトルネック特定テクニック

概要

3行で

• パフォチュー中毒になった
• 結果、1週間無駄にした
• 効率的にボトルネックを特定する術を得た

パフォチューは中毒性がある

パフォチュー中毒になっていました。
思考が止まらない、便秘になる、寝られないで辛かったです。
パフォチューに中毒性があるポイントは以下の2つです

• ランダム性
• 想像と実態が異なることが多い
• お得感

ランダム性

パフォチューの成果はランダムにやってきます。
効果があると思ってやったことが効果がなかったり、
急に良い方法を思いついて効果が出たり。

ギャンブルと同じで
このランダム性が中毒性につながります。

想像と実態が異なることが多い

あ、あれやったら良いわ。
やっとパフォチュー終わったわ -> 喜びでドーパミン出る

試す
逆に遅くなる
いつになったらパフォチュー終わるのか
もう一週間なんの成果も出てないわ-> 焦りでドーパミン出る

想像と実態で二度おいしいわけです。
これもギャンブルと似ています。

ギャンブルと似ていると思います。

お得感

パフォチューは、
初期コスト、コードのメンテナンスコストを度外視すると、
トレードオフなしでパフォーマンスだけ上がります。

要するに「タダで」効果を得られるのでお得なわけです。
これは、「無料」という言葉に多くのヒトが魅了されるのと似ています。

こういうのをやりすぎた公告は、
景品表示法で規制されていますよね？

これも中毒性のポイントです。

ボトルネックがわかっていない

本題に入ります。
前述のパフォチュー中毒で過ごした1週間。
数多くの手法を試しましたが、なんの成果も出ませんでした。

その理由は

「ボトルネックがわかっていなかった」

これでした。

とはいえ、一般的に言うような「推測するな計測せよ」とか、
キャッシュの仕組み、メモリ帯域、演算ユニット、hyper threadingとかは理解しているつもりでした。

でも計測方法が間違えていました。

良い計測ツールを使え

VTuneとかは使ったことは無いですが、有料のリッチな計測ツールを使えば良いと思います。
それらを買いたくないヒトのために無料の計測ツールをご紹介します。

IACA - ループのスループットを予測できる

ループのスループットを予測できるツールです。使い方はぐぐると出てきます。
https://software.intel.com/en-us/articles/intel-architecture-code-analyzer

※ 様々な注意事項があるので、公式pdfドキュメントを見てください。例えば、vdiv, vsqrtのレイテンシーは保守的に見積もられます。

SDE - 実際に実行された命令数を計測できる

実際に実行された命令数を計測できるツールです。
https://software.intel.com/en-us/articles/intel-software-development-emulator

どの演算ユニットがボトルネックになっているかを計測できます。

このツールは使うな

使うなというほどではないですが、false positive、false negativeが発生する可能性があります。

single threadでの実行時間計測

single threadで実行した結果を元に最適化しても、multi threadで実行するとまったく結果が変わらないということが発生しました。

おそらく、hyper threadingの効果です。以下の計測結果が出たからです。
スレッド数を論理コア数に合わせると、最適化前後で実行時間が変わらない。
スレッド数を物理コア数に合わせると、最適化前後で実行時間が変わる。

最適化した箇所はIACAで計測した結果、演算ユニットボトルネック(divとsqrt)になっていた箇所でしたが、hyper threadingで他の箇所(divやsqrtが含まれない)と同時実行された結果、演算ユニットボトルネックが隠れたのだと思います。

特定関数の実行時間計測

個別に計測したときに、結構大きい割合を占めている特定関数の実行時間を短縮しても、全体の実行時間が変わらないということが発生しました。

profiler

また、profilerも役に立ちません(正確には、XCodeのInstrumentsはだめでした)。実際のボトルネック箇所ではない部分が大きく表示されていました。理由は不明。

最強のボトルネック特定テクニック

前述のようなツールが訳に立たない背景は、パフォーマンスはメモリ帯域、CPUの複雑な仕組み、hyper threadingなどが複雑に絡み合った関数になっているからです。

その中で戦う術を教えます。

モデル

前述のようなツールが役にたつためには、(近似的に)以下のように、全体の実行時間を分解できる必要があります。

// F(x, y, z): 全体の実行時間
// f(x), g(y), h(z): 各コードブロックの実行時間
// x, y, z: コードブロック
// N: 並列数
F(x, y, z, N) = (f(x) + g(y) + h(z)) / N

しかし世の中こんなに甘くないです。実際は分解不可能です

F(x, y, z, N)

どう戦うか？

-> 偏微分を使え

以下を計測します。

δF(x, y, z, N)/δx
δF(x, y, z, N)/δy
δF(x, y, z, N)/δz
δF(x, y, z, N)/δN

実践

上記モデルの考え方を実践してみます。
具体的にはどうするのでしょうか？

-> 特定コードブロックの実行回数を2倍にします。

δF/δx, δF/δy, δF/δzを計測できます。

実行を省略できる場合は省略(実行回数を0回にする)でも良いです。
コードブロックがout-of-placeアルゴリズムであれば、2倍にするのが簡単だと思います。
どちらもできない場合は以下のようなテクニックでシミュレーションします。

・メモリ書き込み時に書き込み量を2倍にしてみる
・メモリ読み込み時に読み込み量を2倍にしてみる。
・各演算ユニット(AVX add/mul, div, 普通の命令)に相当する無駄な計算を入れてみる。

そして、もっとも大きいδF/δxを最適化します。
また、最適化効果も見積もれます。
50%最適化したとしたら、全体の実行時間短縮量は、0.5 * δF/δxです。
これを見て割に合わないなら(スペック増強コストより高いなら)、やめたほうが良いです。
-> やめられないのがパフォチューですが

また、Nを変えてみます。
これはみんなやると思うので省略。

まとめ

いかがだっただろうか？