私たちは誤差からどれだけ離れているのか——システムソフトウェア実験における測定バイアス
¶ 1. イントロダクション
システムソフトウェア分野の研究者が行う研究は、概ね「システムソフトウェアを開発する／改善する」ことに集約されます。提案した設計が有効であることを示すためには、実験によって性能が期待通りであることを証明する必要があり、多くの場合はベンチマークやカスタムアプリケーションを走らせます。しかし、その実験で得た数値は本当に正しいのでしょうか？
本記事では Todd Mytkowicz らの論文「Producing Wrong Data Without Doing Anything Obviously Wrong!」を紹介します。この論文は 300 回以上引用されており、注目を集めているだけでなく、その内容は私にとって衝撃的でした。
論文は、実験が一見問題なく見えても、初期設定によって不正確な結果データを黙って得てしまう可能性があると指摘します。その原因として、Unix システムにおける 環境変数の設定 と C++ コンパイラがオブジェクトファイルをリンクする順序の変化 が、プログラムの測定結果に非常に大きな差をもたらし得ることを示します。
¶ 2. プログラムの敏感さ
次の図は、左側のコードを「環境変数のサイズ」を変えた状態で実行した結果を示しています。
環境変数の差異により、95% 信頼水準で、実行サイクル数が 33% 程度変化していることが分かります。さらに 300% も差が出るケースすらあります。環境変数はプログラム起動前にメモリへロードされるため、環境変数のサイズが変わると、その後に配置される変数のメモリアラインメント（Alignment）に影響し、結果として性能差を生みます。
この簡単な例は、プログラムが私たちの想像以上に「敏感」であること、そしてシステム環境の初期設定が実行結果を左右し得ることを示しています。
¶ 3. 実験
実験では SPEC CPU 2006 の一部ベンチマークを使用します。
実験に用いた装置は、2 種類の CPU（Core2、Pentium 4）と、シミュレータ（m5-O3CPU）です。これにより、この偏差が特定の装置に依存しないことを検証します。
¶ 3.1 リンク順序による偏差
コンパイラがプログラムをビルドする際、複数の .o ファイルをリンクして 1 つの実行ファイルを作ります。リンクの順序が異なると、メモリ配置が変わり、結果にも差が出ます。
次の図は perlbench の結果です。デフォルトのリンク順序、アルファベット順、そしてさまざまなランダム順（3〜33）を比較しています。GCC を O2 と O3 でコンパイルして実行したときのサイクル数比が大きく変動していることが分かります。偏差がなければ、理論上この比は一定であるはずです。
すべてのベンチマークをまとめて比較すると次の通りです：
リンク順序によって、O2/O3 の比の範囲が最大で 0.95〜1.10 になり、他のベンチマークでも 0.05 程度の差が出ているものが多いことが分かります。論文によれば、これは装置やコンパイラに依存せず、似た現象が広く見られます。つまり perlbench のように範囲差が 0.15 に達する場合、そのベンチマークで実験して「10% 速くなった」と主張しても、実際には「5% 遅くなっている」可能性すらあるということです。
論文では原因も掘り下げています。m5 シミュレータ上で O3CPU モデルを使った場合、bzip2 ベンチマークではホットなループがキャッシュラインにうまく載るかどうかが性能に大きく影響する、という観察があります。シミュレータではソースが見えるため原因を推定できますが、実ハードウェアではベンダが詳細を十分に開示していないため、著者らは Intel Core2 でも同じ理由かどうかは断定できず、おそらくそうだろうと推測するに留まっています。2020 年の「今日」において、Intel CPU が十分な情報を提供しているのかは分かりません。
¶ 3.2 環境変数サイズによる偏差
前述の通り、環境変数のサイズはスタックに直接影響します。perlbench を例にすると、O2/O3 の範囲は揺れ続け、しかも偏差は不規則で、ほとんど要約・予測できません。
すべてのベンチマークを Violin Plot にすると次のようになります。
多くのベンチマークは範囲差が小さいものの、perlbench と lbm は例外です。その他の多くは 1%〜4% 程度に収まっています。リンク順序による偏差に比べれば小さいとはいえ、実験分析を誤解させるには十分な大きさです。lbm では、12% 遅くなったと思っても、実際には 9% 改善している可能性すらある、ということです。
プログラム起動時のスタック位置を固定すると、実験により O2/O3 の値は環境変数サイズによってほとんど変化しないことが示されます。また perlbench のように起動時に環境変数をヒープへコピーするものは、その後のオブジェクトアラインメントに大きな差を生みます。したがって、ヒープの開始位置を固定しても偏差を防げます。
¶ 4. 偏差の未知性（予測不能性）
初期設定によって結果が大きく変わるなら、最適な値をチューニングできるのでは？と思うかもしれません。
しかし残念ながら、先ほどのデータの通り、この偏差には規則性がありません。せいぜい「その機械で一番良い値」を選べるだけで、その値が別の機械でも最適とは限りません。
上図は Core 2 と Pentium 4 の比較で、x–y は同じリンク順序における両機械のサイクル数です。点には規則性が見られません。また丸で囲った点はそれぞれの機械で最も良いリンク方法ですが、異なるリンク順序の組み合わせになっています。つまりリンク順序の偏差は機械間でも不規則です。
環境変数サイズについても同様で、別の機械で最も効率の良い環境変数サイズは一致しません。
¶ 5. 偏差を避けるには
偏差が起こり得ることが分かった以上、できる限り避ける努力をすべきです。実は偏差は新しい話題ではなく、さまざまな科学分野で偏差への対処が行われています。
¶ 5.1 より大きなベンチマークスイート
ベンチマークの幅や複雑度を増やすことで、偏差の影響がたまたま相殺されるのではないか、という期待があります。
しかし残念ながら、著者らはこの仮説も検証しています。ベンチマークスイート全体に対して 66 種類の異なる設定を適用し、平均を取って分布を描きました。複雑度が偏差を相殺できるなら、分布は狭くなるはずですが、実際には分布は広く散らばっています。これは、ベンチマークの複雑さで初期設定による偏差を相殺することはできないことを意味します。
¶ 5.2 初期値のランダム化
統計的手法によって主張の説得力を上げる方法もあります。ランダムな初期値（初期設定）を多数用意し、T 検定などの統計手法を用いて信頼水準を示します。
上図の通り、著者らは 22 種類のリンク順序と 22 種類の環境変数サイズを組み合わせ、合計 484 種類の初期設定を用意しました。各設定を 3 回ずつ実行して平均を取り、95% 信頼水準で平均の O2/O3 比が 1.007 ± 0.003 であることを示しています。これなら、O3 の方が確かに最適化されていると言えます！
¶ 5.3 因果推論（Causal Analysis）
さらに、データから導いた結論が誤りでないことをより確信するには、因果推論（causal analysis）を採用できます。
以下は Wikipedia の定義です：
一般に、因果は一連の要因（因）とある現象（果）との関係を指す。ある結果に影響を与えるあらゆる出来事は、その結果の要因である。直接要因は結果に直接影響する要因であり、介入要因（中介要因）を必要としない。こうした観点から、因果関係は因果連関（causal nexus）とも呼ばれる。A と B の 2 つの事象があり、A がなければ B が起こらないのであれば、A は B の因であり、B は A の果である。
厳密な因果推論があれば、実験の偏差によって誤った結論を導く可能性を下げられます。
¶ 6. 結論
著者らは ASPLOS、PACT、PLDI、CGO などの 133 本の論文を分析し、この論文が指摘するような偏差に言及しているものが一つもないことを示しています。これはかなり衝撃的です。彼らの実験結果が初期値や他の偏差の影響を受けていないと、どうやって確信できるのでしょうか？
私自身も論文を読む中で、多くの論文が実験誤差をほとんど議論していないことに気づきました。統計的分析をしたり、エラーバーを描いたりするものも多くありません。実験における偏差をもっと重視すべきです。この論文は私に大きな衝撃を与えました。偏差は性能に最大 10% もの影響を与え得ます。私たちが 5% の性能改善にこだわっているとき、その主張は 10% の偏差によって左右されていないでしょうか？
