mizdra's blog

ぽよぐらみんぐ

CPU シミュレータを用いて継続的ベンチマークを安定化させる

node.js performance ci

id:mizdra は eslint-interactive というツールをメンテナンスしています。このツールを使うと、多数の ESLint エラーを効率的に修正できます (詳しくは以前書いた記事を見てください)。

www.mizdra.net

eslint-interactive では「中規模〜大規模なコードベースであってもキビキビ動く」を大事にしてます。その一環として、eslint-interactive には CI (GitHub Actions) でベンチマークを取り、以前から大きく劣化していたら CI を fail させる仕組みがあります。

しかし CI で実行するためにノイズが大きく、よく誤検知が発生してました。そこで最近 CPU 命令数と CPU キャッシュのヒット率 をメトリクスにしたベンチマークへと移行しました。これにより、約 200% あったノイズが約 3.68% に減少し、安定してベンチマークを取れるようになりました。

非常にニッチな話なのですが、面白いかなと思い紹介してみます。

移行前のベンチマークについて

移行前のベンチマークでは、以下のような Node.js で書かれたスクリプトファイルを実行してベンチマークを取ってました。

github.com

スクリプトは lint 対象となるファイルをファイルシステム上に生成し、それに対して eslint-interactive を実行して lint エラーを修正する作りになってます。この修正に掛かる時間を performance.now で計測し、benchmark-action/github-action-benchmark というベンチマーク結果を視覚化する Actions に渡しています。

実際に視覚化されたベンチマーク結果は以下の URL から確認できます ([OBSOLETE BENCHMARK] というラベルが付いたものが、移行前のベンチマーク結果です)。

視覚化されたベンチマーク結果。commit ごとのメトリクスの変化が確認できる。

見ての通りメトリクスが波打っているのですが、ここでパフォーマンスの改善や劣化が起きている訳ではなく、ほとんど全てがノイズによるものです。いくつか前提条件の異なる数種類のベンチマーク結果があるのですが、その中には 200% のノイズ (最大値 / 最小値 * 100 - 100 から算出) を含むものもあります。

200% のノイズを含むベンチマーク結果。

eslint-interactive では 150% メトリクスが悪化した際に CI を fail させるようにしていたのですが、このノイズのせいで contributor から貰った PR で誤検知が発生して contributor を混乱させてしまったりと、よくトラブルを引き起こしてました。

ノイズが発生する理由とその大きさ

一般に、クラウド管理された CI サービスでは、物理マシンの上に仮想マシンが構築されていて、その仮想マシンの上で job を実行します。物理的なマシン 1 台を複数のユーザ・複数の job で共有するので、非常に大きなノイズが発生します。

実際に、Travis-CI で発生するノイズを調査した記事があり、これによると 50% のノイズが発生することが一般的だとされています (しかも 10,000% のノイズを持つ 4 つの外れ値を除外した上で...)。

bheisler.github.io

Note that there were four benchmark results in the cloud set with percentage differences greater than 10,000% which I’ve removed as outliers. Those were not included in the calculations above; if they were included the cloud numbers would be substantially worse. I opted to remove them after inspecting them and finding inconsistencies in those benchmark results which lead me to suspect that the logs were damaged. For example, one benchmark shows the time for each iteration increased by more than 200x but the throughput for the same benchmark appears to have increased slightly, rather than decreased as one would expect.

... many of the comparisons show shifts of +-2%, roughly similar to the noise observed in local benchmarks. However, differences of as much as 50% are fairly common with no change in the code at all, which makes it very difficult to know if a change in benchmarking results is due to a change in the true performance of the code being benchmarked, or if it is simply noise. Hence, unreliable.

あくまで Travis-CI の事例ですが、「ベンチマークの信頼性を損なう程度のノイズがある」ことはどの CI サービスにも言えることかと思います。

パッと思いつく解決策

パッと思いつく解決策は「ベンチマークの試行回数を増やし、その中央値をメトリクスとする」手法です。例えば、ベンチマークの job で10回ベンチマークスクリプトを回し、その中央値をメトリクスとします。しかし、その job が実行される仮想マシンの CPU がたまたまサーマルスロットリングを起こしていた場合、10回の計測値がすべて劣化して中央値もそれに引きづられてしまいます。複数の job に分けて計測してその影響を受けにくくすることもできますが、手間ですし、依然として一定のノイズがあります。

次に思いつく解決策は、自前の CI runners を用意して、そこでベンチマークを実行することです。GitHub Actions でいうところの self-hosted runners です。この手法なら物理的なマシンを専有できるので、かなりノイズを排除できますが、それを用意するための労力や維持費の問題が出てきます。

どちらも eslint-interactive には合わなさそうだったので、他の手段を検討することにしました。

CPU 命令数と CPU キャッシュのヒット率をメトリクスとする手法

なにか良い方法はないかと途方に暮れていたところ、まさに求めていたものはこれだ！という記事を見つけました。

pythonspeed.com

詳しい内容は記事を読んでもらえれば良いですが、いくつか要点を書くと...

  • CPU 命令数が増えたり、CPU キャッシュヒット率が低下すると、一般にパフォーマンスは劣化する
    • CPU 命令数と CPU キャッシュヒット率を見れば、パフォーマンスの変化がある程度わかる
    • 実行時間はブレやすい一方、実行された CPU 命令の数はブレにくい
    • よって壁時計時間や CPU 時間よりも一貫性のあるメトリクスが得られる
  • 「Valgrind」という仮想環境と、「Cachegrind」というCPU キャッシュプロファイラを用いる
    • この仮想環境上でベンチマーク対象のプログラムを実行し、CPU 命令数とキャッシュヒット率を計測する
    • キャッシュというのは L1 キャッシュや L2 キャッシュなどのこと
  • CPU キャッシュのコストがうまく反映されるよう、各層ごとのキャッシュヒット率を重み付けした 1 つの値で比較する
    • ハードウェアによって多少の重みが異なるが、(L1 + D1 ヒット数) + 5 × (LL ヒット数) + 35 × (RAM ヒット数) で十分
    • メトリクスが1つに結合されるので、比較もしやすい

実際に記事の中では、Python で書かれたプログラムを対象にこの手法を適用したところ、0.000001% 以内のノイズに収まったと紹介しています。

なんと sqlite でも長年同様の方法でベンチマークを取っているそうです。

Valgrind/Cachegrind を使った手法を試すには

Valgrind/Cachegrind を使ってCPU 命令数とキャッシュヒット率を計測し、キャッシュコストを考慮した単一のメトリクスを計算する...ところまで自動でやってくるスクリプトを、件の記事の筆者が作っています。手軽に試したいならこれを使うと良いと思います。より一貫性のある結果を得るために ASLR (アドレス空間配置のランダム化) を無効化する機能も入ってます。

github.com

Valgrind/Cachegrind を使った手法のデメリット

もちろん銀の弾丸ではないので、デメリットや注意点があります。

  • 他のソフトウェアとベンチマークメトリクスを比較する用途には使えない
    • CPU 時間を計測している訳ではないので
    • 「1つのソフトウェアが以前と比較して改善したか・劣化したか」の比較のみに使える
  • 遅い
    • 仮想環境で実行するので
    • ただしノイズを排除するために複数回実行する手間はなくなる
  • 実際にユーザが利用する CPU をエミュレート出来るわけではない
  • 命令ごとの実行コストの違いが反映されていない
    • 命令の種類によってコスト異なるはずだが、それが無視されてる
  • CPU 以外のハードウェアのシミュレートがされない
    • 例えばファイルシステムへの I/O はシミュレーターレートされない
    • そういったものがが支配的なプログラムでは、ノイズが大きくなるはず
  • 最新世代の CPU で実装されているような最適化がシミュレートされない
    • 少し古い世代の CPU の最適化がシミュレートされるようになってるため
    • 現実のパフォーマンスと多少ギャップがある
  • 他にも色々...

試してみた

eslint-interactive では、以前からパフォーマンスが改善したか劣化したかがわかれば良いのでマッチしそうな感じがします。そこで、実際にこの手法を試してみることにしました。

github.com

その結果、ノイズが 200% => 3.68% と大幅に減少しました :tada:

ベンチマーク結果のグラフにも、はっきりとその成果が現れています。

新しいベンチマークのグラフ。大きなノイズは見られない。

実際にパフォーマンスを劣化させる変更を仕込んで、CI が fail することも確認できました。きちんとパフォーマンスの劣化を検知できているようです。

今の所大きな外れ値も出ておらず、非常に安定しているように見えています。

試してみて気になったこと

試した上でいくつか気になったことも書いてみます。

  • 実行が遅い！
    • 直接実行すると 3 秒 (ref)、Valgrind/Cachegrind を経由すると 2分46秒 (ref)
    • 仮想環境で実行しているためと思われる...が遅すぎる気もする
  • ランダム性を排除するために、いくつかオプションを渡す必要がある
  • ノイズが思っていたよりも大きい
    • 記事の Python プログラムの事例では 10 回の試行で 0.000001% 以内に収まってる
    • しかし eslint-interactive では 30 回の試行で 3.68% のノイズがあった
    • node コマンドに渡すオプションが不十分で、ランダム性が十分に排除しきれてない?
      • V8 や Node.js に詳しい人が見たら何かわかるかも
      • 誰かわかりませんか！
    • eslint-interactive ではファイルシステムへの I/O が支配的なため?
      • インメモリな仮想的なファイルシステムへ書き込むようにしたら良い?
      • 試しにやってみた
      • 確かにファイルシステムへの I/O が原因っぽい
      • しかしインメモリなファイルシステムに fixture を用意する都合上、fixture を作成するコードも Valgrind/Cachegrind 上で実行する羽目になってる
        • CPU 命令数の総量が増える (21 billion instructions => 27 billion instructions) のでその分ノイズの変化量も小さくなる、というバイアスがある点には注意
        • 加えてベンチマークの実行時間が 3分 => 4分に増えた
      • ちょっと導入するか悩ましい

まとめ

  • クラウド管理の CI では、ベンチマークの信頼性を損なうのに十分なノイズがある
  • そうした環境でも安定的にベンチマークを取るには...
    • CPU 命令数とCPU キャッシュヒット率を見れば良い
      • Valgrind/Cachegrind を使う
    • ランタイムのランダム性を排除する
      • ASLR の無効化、seed の固定化など
  • Valgrind/Cachegrind のシミュレートは完璧ではない
    • 現実のパフォーマンスと多少のギャップがある
    • シミュレートされないリソースへのアクセスはノイズの原因となる

思ったよりもノイズを小さくできなかったですが、パフォーマンスの劣化を検知する用途としては十分そうです。これで不安定なベンチマークともおさらばできそうです。

合わせて読みたい

  • 2022/2/13追記
    • 「シミュレーター」が「シュミレーター」になっていたの直しました (全く気づかなかった…) (ブコメありがとうございます)

ポケットモンスター・ポケモン・Pokémon・は任天堂・クリーチャーズ・ゲームフリークの登録商標です.

当ブログは @mizdra 個人により運営されており, 株式会社ポケモン及びその関連会社とは一切関係ありません.