# Statistical Debugging for Real-World Performance Problems
> [!abstract] 概要
> 非効率な計算につながる設計と実装の欠陥はソフトウェアに広く存在する。これらの欠陥は避けることも発見することも難しい。本番実行中に深刻な性能低下とエネルギーの浪費を引き起こし、単一コアのハードウェア性能がわずかしか伸びないことやエネルギー制約への懸念の高まりとともに、ますます重大になっている。性能問題を診断し、非効率の根本原因を指摘する有効なツールが切実に求められている。性能診断の現状は初歩的である。プロファイリングは最も計算資源を消費する関数を特定できるが、最も資源を浪費する関数を特定することも、その理由を説明することもできない。性能バグ検出器は特定の種類の非効率な計算を特定できるが、一般的な性能問題の診断には向かない。統計的デバッグなどの有効な障害診断技術は機能バグ向けに提案されてきた。しかし、それらが性能問題にも有効かどうかは未解決の問いである。本論文ではまず、実世界のユーザーが性能問題をどのように観測し報告するかを理解するための実証研究を行う。この研究は、統計的デバッグが性能問題の診断に自然に適合することを示す。性能問題は、比較に基づく方法で観測され、良い入力と悪い入力の両方とともに報告されることが多いからである。次に、3 種類の述語と 2 種類の統計モデルを含む統計的デバッグのさまざまな設計点を徹底的に調べ、性能診断にどの設計点が最も有効かを理解する。最後に、性能バグの持つ独特の性質によって、サンプリング技術が診断遅延を延ばすことなく実行時の診断オーバーヘッドを下げられることを調べる。
## 論文情報
- タイトル: *Statistical Debugging for Real-World Performance Problems*
- 著者: [[Linhai Song]]・[[Shan Lu]]([[University of Wisconsin-Madison]]。Shan Lu は現在 [[University of Chicago]])
- 会議: OOPSLA '14、2014 年 10 月 20〜24 日、米国ポートランド
- DOI: 10.1145/2660193.2660234
- 原本: `.raw/papers/2014__OOPSLA__Statistical-debugging-for-real-world-performance-problems.pdf`(18 ページ)
## 概要
性能問題(性能バグ)の診断に、機能バグ向けの統計的デバッグ(成功実行と失敗実行から述語を集め、失敗と相関する述語を統計モデルで選ぶ手法)が使えるかを、3 段で調べた研究である。第 1 に、Apache・Chrome・GCC・Mozilla・MySQL のユーザー報告 65 件を調べ、性能問題は比較で気づかれ、良い入力と悪い入力が報告に含まれやすいと示した。第 2 に、20 件の再現実験と 65 件の手作業検査で、分岐述語と 2 種類の統計モデルの組が有効だと示した。第 3 に、サンプリングによる本番実行の診断でオーバーヘッドを 10% 未満に抑えても、診断能力と診断遅延がほぼ保たれると示した。
## 問題設定
- **対象**: 非効率な計算を生む実装・設計の欠陥(性能バグ)の診断である。根本原因は、非効率な実行を起こしうる静的なコード領域と定義する。
- **既存手法の限界**: プロファイラは資源が使われた場所を示すが、浪費された場所と理由は示さない。MySQL の例(Figure 1)では、問題の関数 `start_bulk_insert` はプロファイラの順位に現れなかった。個別の性能バグ検出器は特定の型(非効率な入れ子ループなど)に限られ、症状に基づかないので誤検知を生む。
- **未解決の 3 点**: (1) 性能問題で良い入力と悪い入力が得られるか。(2) どの述語と統計モデルの設計が有効か。(3) 本番実行でサンプリングは診断能力と診断遅延を保てるか。
- **前提の違い**: 機能バグは、クラッシュや誤出力のように失敗が明確である。性能問題は、遅さが大きな負荷によるのか性能バグによるのかを区別しにくい。
Figure 1: MySQL の性能バグ(`-` と `+` がパッチ)
```c
void start_bulk_insert(ha_rows rows)
{
...
- if (!rows)
- { //slow path where caching is not used
- DBUG_VOID_RETURN;
- }
- rows = rows/m_tot_parts + 1;
+ rows = rows ? (rows/m_tot_parts + 1) : 0;
...
//fast path where caching is used
DBUG_VOID_RETURN;
}
```
(Figure 1. A real-world performance bug in MySQL (the '-' and '+' demonstrate the patch))
パラメータ 0 を実装者は「キャッシュ不要」と解釈し、呼び出し側は「大きなバッファの確保」と解釈した。この不一致でキャッシュなしの極端に遅い実行が生じた。修正は不要な分岐の削除だが、特定に多くの労力を要した。
## 提案手法
新しい単一のアルゴリズムではなく、統計的デバッグの設計空間の系統的な評価が中心である。
- **統計的デバッグの枠組み**: 成功実行と失敗実行から実行時イベント E を集め、失敗と最も相関するイベントを失敗予測子として統計モデルで選ぶ。設計は入力・述語・統計モデルの 3 点である。入力設計は性能問題では実証研究の結果として自然に解ける。
- **述語**: 分岐(取られたか否かの 2 述語)、関数の戻り値(<0、≤0、>0、≥0、=0、≠0 の 6 述語)、スカラー対(変数対の大小関係の 6 述語)を評価する。命令述語は分岐と近いので除き、スレッド交錯述語は性能問題の大半が決定的なので除いた。
- **基本モデル(CBI)**: 述語が真の実行の失敗確率 Failure(P) と、観測されただけの実行の失敗確率 Context(P) の差 Increase(P) が、有意に正の述語だけを残す。順位づけは Increase と失敗実行での真の割合の調和平均 Importance を使う(統計的 Z 検定、信頼水準 0.99)。述語が実行内で真になったかだけを見て、回数は見ない。
- **ΔLDA モデル**: 潜在ディリクレ配分(LDA)から派生し、述語が実行内で真になった回数を使う。例えば、成功実行で真 10 回・偽 100 回、失敗実行で真 100 回・偽 10 回の述語は基本モデルでは無用だが、ΔLDA は失敗予測子とみなす。ループ条件の分岐は、失敗実行でイテレーションが多いと高順位になる(以後 Branch_loop)。悪いトピック数は既定の 1 とする。
- **データ収集**: C は CBI、C++ は Pin による分岐・戻り値の計装を自作した。C++ のスカラー対は Pin での評価が難しいので実験から除き、手作業検査でだけ扱った。プロファイラ比較には OProfile を使い、根本原因の関数の順位(Fun)と呼び出し連鎖まで見た順位(Stack)を評価した。
- **本番実行向けの拡張**: ユーザーが各プロファイルを成功・失敗・対象外(既定)に明示的に印付ける。比較で観測される性能問題では、対象外のプロファイルを統計的デバッグで無視する。サンプリングは CBI のソフトウェア方式と、C++ 向けのハードウェア性能カウンタ方式(N 回ごとの割り込み)を使う。
## 新規性
- 性能問題が「どう気づかれ、どう報告されるか」から、統計的デバッグの適用可能性を示した初の実証研究である。診断の実務を調べた点で、性能バグの発生・出現・修正を調べる既存の研究と異なる。
- 統計的デバッグの述語 3 種とモデル 2 種を性能問題に対して評価し、2 つの設計点(分岐と基本モデル、ループ分岐と ΔLDA)が補い合うと示した。機能バグでは基本モデルで足りたが、性能バグは回数を見るモデルが必要という知見は新しい。
- サンプリングが性能バグの診断遅延を延ばさない理由(根本原因述語が 1 回の実行で何度も真になる)を、機能バグの場合との差として示した。
## 実験設定
- **調査対象(65 件)**: 既存の性能バグベンチマーク(110 件)から、ユーザーが報告し開発者が診断・修正した 65 件を選んだ。開発者自身がコード検査で見つけたものは除く。詳細は Table 1 に示す。
Table 1: 調査対象のアプリケーションとバグ数
| スイート | 説明(言語) | バグ数 |
|---|---|---|
| Apache | HTTPD(C)、TomCat(Java)、Ant(Java) | 16 |
| Chromium | Google Chrome(C/C++) | 5 |
| GCC | GCC と G++(C/C++) | 9 |
| Mozilla | Firefox、Thunderbird(C++、JavaScript) | 19 |
| MySQL | サーバー(C/C++)、クライアントライブラリ | 16 |
| 合計 | | 65 |
(Table 1. Applications and bugs used in the study)
- **再現実験(20 件)**: 65 件のうち再現できた 20 件を使う(Table 4)。Mozilla 4、MySQL 6、Apache 4(Java を C に再実装)、GCC 6 である。残りの 45 件は、特殊なハードウェアや古いライブラリに依存して再現できなかった。1 件につき良い入力 10 と悪い入力 10 で 20 回実行する。13 件はバグ報告から多数の入力を作れた。残り 7 件(Mozilla 3、GCC 3、MySQL 1)は、提供された入力を無作為に変えて症状で良否を判定した。実験機は Intel i7-4500U、Linux 3.11 である。
- **評価指標**: 診断能力(上位の失敗予測子が根本原因に関係するか)、実行時オーバーヘッド、診断遅延(診断に要した失敗実行数)である。
- **本番実行の設定**: 既定でサンプリング率は約 1/10000、成功実行と失敗実行を各 1000 回使う。実行回数(10〜1000)とサンプリング率(約 1/100〜1/100000)も変える。良い入力が報告にない 4 件は、無作為の入力で成功実行を作る。
## 実験結果
**性能問題の観測と報告(実証研究)**
- 65 件中 51 件が比較で観測された。1 つのコードベース内の比較が 38 件(同じ入力・異なる設定 10、異なる大きさの入力 22、少し異なる機能の入力 11。重複あり)、複数のコードベース間の比較が 27 件(同じ入力の異なる版 20、異なるアプリケーション 9)、非比較が 14 件である。
Table 2: 性能問題がエンドユーザーにどう観測されたか(合計列のみ。比較カテゴリ間は重複あり)
| カテゴリ | 合計 |
|---|---|
| 1 つのコードベース内の比較 | 38 |
| 同じ入力で設定が異なる | 10 |
| 入力の大きさが異なる | 22 |
| 機能が少し異なる入力 | 11 |
| 複数のコードベース間の比較 | 27 |
| 同じ入力で同じアプリケーションの異なる版 | 20 |
| 同じ入力で異なるアプリケーション | 9 |
| 比較に基づかない | 14 |
(Table 2. How performance problems are observed by end users)
- 悪い入力は 65 件すべてで提供され、約 70%(46 件)は入力の種別として述べられた。良い入力は約 60% で明示され、32 件は多数の良い入力の作り方まで述べられた。
Table 3: バグ報告で提供された入力(合計列のみ)
| 区分 | 件数 |
|---|---|
| 悪い入力なし | 0 |
| 悪い入力 1 つ | 19 |
| 悪い入力の集合(n) | 46 |
| 良い入力なし | 27 |
| 良い入力 1 つ | 6 |
| 良い入力の集合(n) | 32 |
(Table 3. Inputs provided in users' bug reports (n: developers provide a way to generate a large number of inputs))
- 診断に平均 129 日を要した(Chrome 59 日、Apache 194 日)。診断ツールとして言及されたのはプロファイラだけで 13 件、その結果が出た後でも平均 116 日を要した。
- 無作為抽出した機能バグ 65 件では、比較による観測は 8 件だけである。Z 検定で、性能バグは 99% の信頼水準で比較により観測されやすく、良い入力も含まれやすい。
**再現実験(Table 4 と Table 5)**
Table 4 は 20 件のベンチマークの規模(Mozilla 88〜3482 KLOC など)、静的な述語数、報告された入力数を列挙する。Table 5 は 20 件の診断結果を述語×モデル別に列挙する。
**Table 4: ベンチマーク情報**
![[tab04-benchmarks.png]]
(Table 4. Benchmark information)
**Table 5: インハウス診断の実験結果**
![[tab05-inhouse-results.png]]
(Table 5. Experimental results for in-house diagnosis)
- **基本モデル**: 20 件中 8 件を診断し、8 件とも 1 位の予測子が根本原因に関係した。分岐述語が 8 件すべてを診断し、戻り値述語とスカラー対述語は Apache#3278 の 1 件だけである(Figure 2)。予測子はパッチの近く(10 行以内)にある例が多く、MySQL#44723 だけは別ファイルにあった(Figure 3)。数千〜数十万の候補述語から選べる。
- **ΔLDA モデル**: 基本モデルが失敗した 12 件のうち 11 件を診断する。分岐(ループ条件)が 11 件を診断し、戻り値・スカラー対の診断能力は Branch_loop に含まれた。1 位が根本原因のループなのは 8 件で、残る 3 件は 2〜4 位である。1 位が結果側のループ(根本原因のループが生んだ余計な仕事を処理するループ)だったためである。GCC#12322 は上位 5 位に入らなかった。
- **プロファイラとの比較**: 基本モデルが診断した 8 件で、根本原因の関数は 5 件で 11〜1037 位、3 件は一覧に載らない。呼び出し連鎖まで見て有効なのは MySQL#44723 だけである。ΔLDA では、根本原因の順位が 7 件で同等、4 件で ΔLDA が上である。
- **修正方針の示唆**: 分岐述語が最良の 7 件のうち 5 件は分岐条件の変更、2 件は分岐本体の最適化で直った。戻り値述語の 1 件は戻り値に影響する修正である。
Figure 2: Apache の性能バグ(Return 述語で診断)
```c
notified = false;
while(!notified) {
rc = pthread_cond_timedwait(
&cond, &lock, &timeToWait);
if(rc == ETIMEDOUT) {
break;
}
}
```
(Figure 2. An Apache bug diagnosed by Return)
Apache#3278 は Tomcat の停止が非決定的に約 5 秒かかる問題である。3 種類の述語がすべて、`pthread_cond_timedwait` がシグナルなしにタイムアウトしたことを指す。根本原因は `notified` の初期化が遅く、別スレッドが先にシグナルを出してしまうことで、`notified=false;` を前へ移して直った。
Figure 3: MySQL の性能バグ(Branch 述語で診断)
```c
//ha_myisam.cc
/* don't enable row cache if too few rows */
if (! rows || (rows > MI_MIN_ROWS_TO_USE_WRITE_CACHE) )
mi_extra(...);
//mi_extra() will allocate write cache
//and zero-fill write cache
// fix is to remove zero-fill operation
....
// in myisamdef.h:
// #define MI_MIN_ROWS_TO_USE_WRITE_CACHE 10
```
(Figure 3. A MySQL bug diagnosed by Branch)
MySQL#44723 は 9 行と 11 行の挿入で性能が大きく違う問題である。成功実行が取らず失敗実行が必ず取る分岐が失敗予測子で、根本原因は書き込みキャッシュの不要なゼロ埋めだった。
**手作業検査(65 件)**
- 従来の述語と基本モデルで診断できるのは 15 件で、分岐が 13 件、戻り値が 2 件、スカラー対が 0 件である。残りのうち 43 件はループの非効率が原因で、ΔLDA と Branch_loop で診断できると見込む。最後の 7 件は不要な I/O やシステムコールが主因で、いずれの述語でも診断できない。
Table 6: 述語ごとの診断可否(手作業検査。合計列のみ)
| 区分 | 件数 |
|---|---|
| 基本モデル・分岐 | 13 |
| 基本モデル・戻り値 | 2 |
| 基本モデル・スカラー対 | 0 |
| ΔLDA・Branch_loop | 43 |
| 上記の設計で診断できない | 7 |
(Table 6. How different predicates work for diagnosing user-reported performance bugs)
- ループ関連の 43 件の修正方針は、ループ削除 10、ループのインスタンスの統合 10、イテレーション数の削減 8、イテレーションの統合 10、その他 5 である。
Table 7: ループ関連バグの修正方針(合計列のみ)
| 修正方針 | 件数 |
|---|---|
| ループの削除 | 10 |
| ループインスタンスの統合(ループ間の冗長性の除去) | 10 |
| イテレーション数の削減(ループの仕事量の削減) | 8 |
| イテレーションの統合(イテレーション間の冗長性の除去) | 10 |
| その他 | 5 |
| 合計 | 43 |
(Table 7. Fix strategies for loop-related bugs)
**サンプリングによる本番実行の診断(Table 8 と Table 9)**
- **オーバーヘッド**: 既定の 1/10000 では 8% 未満で、5% 未満が 20 件中 17 件である(Table 8)。サンプリング率に敏感で、1/100000 では大半が 2% 未満、1/100 では 40% を超える例がある(Table 9)。
- **診断能力**: 成功・失敗各 1000 回では、Apache#3278 を除く 19 件で、サンプリングなしと同じ順位が得られた。サンプリング率が 1/100000 になると 4 件が診断できなくなり、より多くの実行が要る。
- **診断遅延**: 3 件は約 100 回、4 件は約 500 回の失敗実行を要し、Apache#3278 は 1000 回を超える。しかし ΔLDA が適する 11 件は失敗実行 10 回でも同じ順位が得られ、低オーバーヘッド(10% 未満)・高診断能力・短い診断遅延を同時に満たす。機能バグのサンプリングでは、ほぼ不可能な組み合わせである。
- **理由**: 性能バグの根本原因に関係する述語は 1 回の実行内で何度も真になる(だから遅い)ため、疎なサンプリングでも拾われ、無関係な述語より頻繁に拾われる。他の 9 件も、根本原因の領域が失敗実行中に数回実行されるため、遅延が 10^4 倍に延びない。
Table 8 は 10・100・500・1000 回の実行数ごとの診断結果とオーバーヘッド、Table 9 はサンプリング率ごとの診断能力・オーバーヘッド・実行当たりのサンプル数を 20 件について列挙する。
**Table 8: 実行時オーバーヘッドと診断能力(サンプリング率 1/10000)**
![[tab08-overhead-capability.png]]
(Table 8. Run-time overhead and diagnosis capability evaluated with the default sampling rate)
**Table 9: サンプリング率ごとの診断能力・オーバーヘッド・サンプル数**
![[tab09-sampling-rates.png]]
(Table 9. Diagnosis capability, overhead, and average number of samples in each run under different sampling rates)
## 考察
- 統計的デバッグは、ユーザー報告の性能問題の診断を進める。ただし最終的なパッチの設計には追加の解析が要る。ΔLDA がループを指しても、ループがなぜ非効率で、どう最適化するかは別に解析する必要がある。Table 7 のような修正方針の分類は、原因と結果の区別や修正提案を自動化する将来の性能診断系の指針となる。
- 関連研究との違い: [[X-Ray]] は入力や設定のエントリを特定してユーザー自身の解決を助けるが、本研究は開発者向けにコード上の根本原因と修正方針を示す。IntroPerf、StackMine、Yu らのトレース解析は、関数の遅延やコールスタックパターン、システムイベントの因果関係を扱う。
- 妥当性の脅威: 対象はオープンソースの 5 系統で、科学技術計算や分散システムは含まない。報告されず、修正されず、または診断経過が残らない性能問題は対象外である。再現できた 20 件の実験は、手作業検査 65 件と整合するとされる。失敗の分類(バケット化)は将来課題で、複数の根本原因が混ざる場合は未検証である。
## 強み / 弱点・課題
- 強み: 実証研究、設計空間の評価、サンプリングの 3 段が一貫し、各段の結論が次の設計の根拠になっている。プロファイラとの比較が定量的で、順位と修正方針の両面から示される。
- 強み: 性能バグの性質(繰り返し実行される)を、サンプリングの診断遅延の短縮という具体的な利点に結びつけた。
- 弱点: 再現実験は 20 件で、C/C++ 以外は再実装を要した。C++ のスカラー対述語は実験していない。65 件中 45 件は再現できず、手作業検査の予測に依存する。
- 弱点: 良い入力と悪い入力の生成は、7 件で著者が入力を無作為に変えて作った。実運用では、比較による観測をユーザーが印付ける前提が要る。
- 課題: 不要な I/O やシステムコールが主因の 7 件は診断できない。ΔLDA の 1 位が結果側のループになる場合の原因と結果の区別、失敗のバケット化、詳細な修正提案が未解決である。
## 関連
- 概念: [[Fault Localization]]
- 実体: [[X-Ray]] / [[Linhai Song]] / [[Shan Lu]]