runner の設計

設計目標

ベンチマークの結果が証拠となるのは、3 つのことが成り立つ場合だけです。実装が計測された入力に対して正しい答えを計算したこと、すべての実装が同じ条件で計測されたこと、そして計測をシード、プロトコル、環境までさかのぼれることです。runner はペイロードを実行する唯一のパッケージであり、これらの性質が規律によってではなく構造によって成り立つように作られています。検証は計時に先立ち、実装の順序はバランスが取られ、バッチサイズはキャリブレーションされ、すべての生の観測が出力されます。

数学的背景

ブロックと計測モデル

1 つのデータセットについて、ランナーは $k$ 個の実装をブロック $b = 0, 1, \dots, E + C - 1$ で計測します。 $E$ 個の探索的ブロックの後に $C$ 個の確認的ブロックが続きます（exploratory_samples と confirmatory_samples）。ブロック内では各実装が 1 つのバッチを実行します。ブロック $b$ における実装 $i$ の反復あたりの時間を次のようにモデル化します

y_{i,b} = \mu_i + \tau_{p_i(b)} + \delta\, s_i(b) + \varepsilon_{i,b},

ここで $p_i(b) \in \{0, \dots, k-1\}$ はブロック内での $i$ の位置、 $\tau_p$ は位置の効果（ブロックの最初のバッチはより冷えたキャッシュで実行されます）、 $s_i(b) = bk + p_i(b)$ はグローバルなスロット番号、 $\delta$ は線形のドリフト（サーマルスロットリング、バックグラウンドの負荷）、 $\varepsilon$ はノイズです。関心のある量は $\mu_j - \mu_i$ です。

巡回ラテン方格による順序

OrderPolicy::BalancedBlocks(order_seed) の下では、ブロック $b$ は balanced_order(k, b + o) の順序で実装を実行します。つまり位置 $p$ では実装 $(p + b + o) \bmod k$ を実行し、オフセットは $o = (\text{order\_seed} \oplus \text{run\_seed}) \bmod k$ です。したがって実装 $i$ は次の位置にあります

p_i(b) = (i - b - o) \bmod k .

バランス。 $i$ を固定すると、写像 $b \mapsto (i - b - o) \bmod k$ は任意の連続する $k$ 個の整数から $\{0, \dots, k-1\}$ への全単射です。連続する $k$ 個のブロックからなる完全な周期ごとに、各実装は各位置をちょうど 1 回ずつ占めます。位置の $k \times k$ の表はラテン方格です。

相殺。 完全な周期 $b_0, \dots, b_0 + k - 1$ にわたってモデルを足し合わせます:

\begin{aligned} \sum_{b} \tau_{p_i(b)} &= \sum_{p=0}^{k-1} \tau_p, \\ \sum_{b} s_i(b) &= k \sum_{b} b + \sum_{b} p_i(b) = k \sum_{b} b + \frac{k(k-1)}{2}. \end{aligned}

右辺はどちらも $i$ に依存しません。したがって周期の平均は次を満たします

\bar y_j - \bar y_i = \mu_j - \mu_i + (\bar\varepsilon_j - \bar\varepsilon_i),

これは位置の効果と線形のドリフトを含みません。FixedOrder では、どのブロックでも $p_i(b) = i$ であり、差は常にバイアス $\tau_j - \tau_i + \delta (j - i)$ を伴います。

相殺が厳密なのは完全な周期にわたる平均についてです。 $E + C$ を $k$ の倍数に選び、ブロック $E$ からローテーションを継続する確認フェーズが完全な周期を覆うようにしてください。ペアごとの差の中央値は厳密に不偏というよりは頑健です。ブロックごとのバイアス $\tau_{p_j(b)} - \tau_{p_i(b)} + \delta (p_j(b) - p_i(b))$ は $k$ 個の値をそれぞれ同じ頻度で取り、 $k = 2$ では $+c$ と $-c$ を交互に取ります。

バッチのキャリブレーション

タイマーには分解能 $\rho$ と開始・停止のオーバーヘッド $\omega$ があります。真に $T(n)$ かかる $n$ 回の反復のバッチは $\lvert q\rvert \le \rho$ として $\hat T = T(n) + \omega + q$ と読まれ、ランナーは $\hat T / n$ を報告します。反復あたりの時間の相対誤差は高々次のとおりです

\frac{\omega + \rho}{T(n)} ,

これはバッチが大きくなるにつれて小さくなります。キャリブレーションは $T(n)$ が target_batch_time_us $= t$ に達するように $n$ を選びます。 $n_0 = \min(\max(\text{min\_batch\_iterations}, 1), \text{max\_batch\_iterations})$ から始め、バッチが有効で、 $T(n) < t$ 、 $T(n) <$ max_sample_time_us、 $n <$ max_batch_iterations である間、次のサイズは次のとおりです

n_{j+1} = \min\Bigl(n_{\max},\ \max\Bigl(n_j + 1,\ \Bigl\lceil \frac{n_j\, t}{T(n_j)} \Bigr\rceil\Bigr)\Bigr),

計測された時間が $0$ の場合は、比の代わりに $10\, n_j$ を使います。

線形のコスト。 $T(n) = c\,n$ なら、最初の更新で $n_1 = \lceil t / c\rceil$ となり $T(n_1) \in [t, t + c)$ です。再試行は 1 回で足ります。

アフィンのコスト。 バッチごとの固定コスト $a > 0$ を伴う $T(n) = a + c\,n$ の場合、更新は $f(n) = n t / (a + c n)$ の不動点反復です。その不動点は $a + c n^* = t$ を解くので $n^* = (t - a)/c$ であり、

f'(n) = \frac{a\, t}{(a + c n)^2}, \qquad f'(n^*) = \frac{a}{t} < 1 .

この反復は $n^*$ の近くで比率 $a/t$ で縮小します。固定コストが目標の 10 % なら、再試行のたびに残りの差が 10 分の 1 になります。各ステップで $n$ は少なくとも 1 増え、 $n$ は max_batch_iterations で上限が設けられているため、ループは高々 $n_{\max} - n_0$ 回の再試行で終了します。

QuickCheck プリセット（ $t = 1000$ µs）と 1 µs のタイマーでは、キャリブレーションされたバッチの量子化誤差は高々 $0.1\,\%$ です。ブラウザでは performance.now() が 100 µs 以上に粗くされることがあります。それに応じて目標を引き上げてください。

設計上の決定

計時の前に検証する

問題。 高速だが誤った答えが高速化に見えてはなりません。選択肢。 計時ループ内で検証する、後で検証する、前に検証する。選択。 ランナーはデータセットごとに、まず新しい clone_input/prepare と initial_context から、実装ごとに sequence_length 回の操作からなる検証系列を実行し、オラクルと比較します。計時はその後に始まります。理由。 計時内で検証すると検証も計時されてしまい、後で検証すると失敗した入力を計測の隣に示せません。系列はステップからステップへ next_context を引き継ぐため、状態を持つ操作（累積器、丸めモード、パーサの状態）は計測されるのと同じ順序で検証されます。

オラクルを呼び出す前に、ランナーは値でない実行結果を次のように対応付けます:

実装の結果	検証ステータス
`Unsupported(reason)`	`Unsupported(reason)`
`ParseFailure`, `Aborted`, `Timeout`	`InfrastructureFailure(...)`
`ExpectedDifference(reason)`	`ExpectedDifference(reason)`
`Value`, `RaisedFlags`, `Trapped`	オラクルが判定

関係オラクルでは、実装の順序なしペア $i < j$ のすべてがステップごとに比較されます。イベントはペアの 2 番目の実装に帰属します。早期に終わった系列（next_context = None）は、両側が生成したステップについて比較されます。Invalid と InfrastructureFailure は失敗として数えられます。失敗すると、シュリンカーが設定されていればそれが起動され、シード、両方のフィンガープリント、縮小パス、最小入力を伴う ValidationFailure が出力されます。

失敗は計測を止めません。レポートはそのデータセットにおける失敗した実装の系列を取り除き、代わりに不一致を表示します。

ランダム化ではなくバランスの取れたシード付きローテーション

問題。 位置とドリフトの効果は、固定された順序にバイアスをもたらします。選択肢。 固定された順序、ブロックごとの独立したランダムな置換、巡回ラテン方格。選択。 上で導いた巡回ローテーションを、シード付きのオフセットとともに使います。理由。 ランダムな置換は位置を期待値の上でしかバランスさせません。10 ブロックと 3 つの実装では、ある実装が 4 回最初に実行されることも容易に起こります。ローテーションはすべての周期で位置を厳密にバランスさせ、それでもどの実装から始めるかはシードが決めます。

キャリブレーションされたバッチと、既定では実装ごとに 1 つのサイズ

問題。 単一の操作は短すぎて計時できません。選択。 各実装は個別にキャリブレーションされ（BatchPolicy::PerImplementation）、それぞれが目標の時間に達します。BatchPolicy::SharedBatchSize はすべてのサイズをその最小値 $n = \min_i n_i$ に置き換えます。これはバッチあたりの作業量が同一でなければならない実験のためのもので、その代償として遅い実装ではバッチが短くなり、タイマーの相対誤差が大きくなります。反復あたりの値 $\hat T / n$ はバッチの平均です。バッチは独立な反復ごとのノイズの分散を $n$ 分の 1 にしますが、バッチ内の裾も隠してしまいます。

明示的な計時の境界

時計は @bench.monotonic_clock_start/monotonic_clock_end（µs）です。それが何を囲むかはフィクスチャの SetupPolicy によって決まります:

セットアップ	`ExcludedFromMeasurement`	`IncludedInMeasurement`
`PerRun`, `PerDataset`, `PerImplementation`	一度準備してキャッシュする。バッチごとに: 開始、 $n \times$ （実行、畳み込み）、停止	除外の場合と同じ。ただし一度きりの準備は、最初に実行されるバッチ（通常はウォームアップバッチ）の計時区間内に入ります
`PerSample`, `PerBatch`	準備、開始、 $n \times$ （実行、畳み込み）、停止、リセット	開始、準備、 $n \times$ （実行、畳み込み）、リセット、停止
`PerIteration`	$n \times$ （準備、開始、実行、畳み込み、停止、リセット）、時間は合計されます	開始、 $n \times$ （準備、実行、畳み込み、リセット）、停止

ここでの prepare は clone_input を含みます。synchronize は毎回の開始の直前と毎回の停止の前に呼ばれます。出力シンクの finish と @bench.Bench::keep は停止の後、計時の外で実行されます。keep は、結果が使われない処理をコンパイラが取り除くのを防ぎます。イベントの出力が計時区間内で行われることはありません。

セットアップを除外した PerIteration にはコストがあります。バッチあたり $n$ 回タイマーを読むため、量子化誤差は $n\rho / (n c) = \rho / c$ となり、バッチサイズとともに小さくなりません。タイマーの分解能に比べて長い操作にのみ使ってください。

フィクスチャのライフサイクルと番兵のサンプル ID

フィクスチャの prepare と reset は SampleContext または ResetContext を受け取り、その sample_id がランナーの現在の作業をフィクスチャに伝えます:

`sample_id`	フェーズ
`-1`	検証系列
`-1000 - w`	ウォームアップバッチ $w$
`-3`	ウォームアップ後のリセット（長寿命のセットアップのみ）
`-2 - r`	$r$ 回の再試行後のキャリブレーションバッチ。`-2` はキャリブレーション後のリセットでもあります
`-100000 - r`	探索的ブロック $r$
`r`	確認的ブロック $r$
`confirmatory_samples`	キャッシュされた準備済みの値の最後のリセット

長寿命のセットアップ（PerRun、PerDataset、PerImplementation）は、実装とデータセットごとに一度準備され、ウォームアップ後とキャリブレーション後にリセットされ、データセットの終わりに再びリセットされます。ランナーは実装ごとに 1 つのキャッシュを持つため、現在のところ PerRun と PerDataset は PerImplementation と同様に振る舞います。

ウォームアップ

各実装は、warmup_iterations 個のバッチを実行し、かつ warmup_time_us を費やすまで、反復 1 回のバッチを実行します。バッチ数の上限は $\max(\text{warmup\_iterations}, \text{max\_batch\_iterations})$ です。すべての実装に同じウォームアップが適用されるため、JIT コンパイルやキャッシュによる優位を持って計測を始める実装はありません。

サブプロセスワーカーによるクラッシュの隔離

問題。 セグメンテーション違反を起こしたり無限ループしたりする候補は、実験を終わらせてしまいます。選択。 Implementation::worker は各操作を、強制キャンセルのハンドラを持つタスクグループ内の子プロセスとして実行し、stdout と stderr を並行してキャプチャし、タイムアウトや非ゼロの終了を結果に変換します。理由。 結果はデータであり、数えられ、報告され、リプレイできます。ワーカーではプロセスの生成が計測される操作の一部になりますが、これは正しさのコーパスや安全でないコードには許容できても、マイクロベンチマークには適しません。

シードと識別情報

実行シードは GenerationContext(seed, "default", case_id, DatasetKey(scale, index), fixture.id, fixture.version) でそのままフィクスチャに届きます。そこから @generator.derive_seed でデータセットごとのシードを導出してください。混合については generator の設計で説明しています。同じシードがローテーションのオフセットも決めます。プロトコル、プラン、環境スナップショットと合わせて、シードが計時値以外のすべてを決定します。

正しさと不変条件

すべてのデータセットと実装について検証が計時に先立ちます。
バランス。 連続する $k$ 個のブロックごとに、各実装は各位置を 1 回ずつ占めます（上で証明したとおり）。
データセットごとのイベントの順序。 検証と失敗、次に実装ごとに 1 つのキャリブレーションイベント、次に $k(E + C)$ 個の観測（探索的なものが先）。要約は最後のデータセットの後に一度だけ出力されます。
件数。 observation_count $= \lvert\text{scales}\rvert\cdot k (E + C)$ 、calibration_count $= \lvert\text{scales}\rvert \cdot k$ 、validation_count は比較したステップの数です。
有効性。 バッチ内の操作が値を生成しなかったか、コンテキストの系列を終わらせた場合、観測は valid = false になります。
停止性。 キャリブレーションは高々 $n_{\max} - n_0$ 回の再試行、ウォームアップは高々 $\max(\text{warmup\_iterations}, n_{\max})$ 個のバッチ、縮小は高々 max_steps 回の候補の評価を行います。
リセットの規律。 短寿命の準備済みの値（検証系列、PerSample、PerBatch、PerIteration）はちょうど 1 回リセットされます。キャッシュされた長寿命の値は、ウォームアップ後、キャリブレーション後、データセットの終わりにリセットされ、その間は再利用されるため、reset はそれを再利用可能な状態にしておかなければなりません。

採用しなかった代替案

ブロックごとのランダムな置換。 期待値の上でしかバランスが取れません。
Williams 計画。 一次の持ち越し効果（直前にどの実装が実行されたか）もバランスさせますが、 $k$ が奇数の場合は周期あたり $2k$ 個のブロックが必要です。巡回順序では、ブロック内で常に実装 $i - 1$ が $i$ の前に置かれます。
各反復を計時する。 短い操作ではタイマーのオーバーヘッドと分解能が支配的になります。バッチはそれらを償却します。
区間が十分狭くなったら止める。 逐次的な停止規則は固定サンプルの区間を無効にします。サンプル数はプロトコルで固定されています。
計時の後に検証する。 誤った結果を、破棄すべき計測から切り離してしまいます。

境界

ランナーはスレッドの固定、CPU 周波数の固定、プロセスの隔離を行いません。それらについて宣言した内容を EnvironmentSnapshot に記録します。
experiment_design、outlier_policy、validation_coverage、practical_delta_pct はプロトコルに保存されますが、実行を変えることはありません。カバレッジの指定にかかわらず、検証はデータセットごとに 1 回、計時の前に実行されます。
比較や判断は計算しません。それは stats が行います。
スケールごとに 1 つの入力を実体化します。ブロックごとに入力を再生成することはありません。
protocol_identity、したがって run_id が含むのは、ウォームアップ回数、確認サンプル数、実用的な閾値だけです。
サブプロセスワーカーには native ターゲットが必要です。run 自体には非同期ランタイム（native、JS、wasm。wasm-gc は不可）が必要です。
実装間の一次の持ち越し効果はバランスされません。