bench の設計

設計目標

floating における性能に関する主張は再現可能でなければならず、ノイズと混同されてはなりません。bench は Maremark フレームワークを、このリポジトリ専用の小さなツールキットに仕立てます。ベンチマークは正しさのオラクルを備えた不変の仕様であり、各実行はその環境とプロトコルを記録し、計時結果はロバストな対応付き統計で集約され、その不確かさはブートストラップ信頼区間として報告されます。計測（計時、JSONL のストリーミング）はコアごとのテストパッケージと tools/benchmark.py で行われます。このパッケージは実験を記述し、そのデータを集約するだけです。

数学的背景

1 つの観測が計測するもの

Maremark はまず実装とデータセットごとにバッチサイズを較正します。プロトコルの最小反復回数 $n_0$ から始めてバッチを計時し、バッチが目標バッチ時間 $T$ （Development プリセットで 5 ms、RegressionGate で 10 ms）より短く、かつ反復回数の上限に達していない間、次の値で再試行します

n_{k+1} = \min\Bigl(n_{\max},\ \max\bigl(n_k + 1,\ \lceil n_k T / t_k \rceil\bigr)\Bigr),

ここで $t_k$ は計測されたバッチ時間です。1 つの観測は $n$ 回の呼び出しからなる 1 回の計時バッチであり、呼び出しあたりの平均時間 $x = t_{\text{batch}} / n$ をマイクロ秒単位で記録します。バッチ内で平均することでクロックの分解能の影響が除かれます。残るバッチ間の変動は、以下の統計で扱います。

ブロックと対応付け

確認フェーズは $m$ 個のブロックからなります（Development では $m = 10$ 、RegressionGate では $20$ ）。ブロック $j$ では各実装が 1 回ずつ、 $K$ 個の実装の巡回順 $(j + o) \bmod K$ で計測されます。オフセット $o$ はシードから導かれるため、連続する $K$ ブロックにわたって各実装が最初に実行される回数は等しくなります。ベースライン $B$ と候補 $C$ について、観測はブロック順に並べられ、対応付けられます：

d_j = c_j - b_j, \qquad j = 1, \dots, m .

緩やかなドリフト（周波数スケーリング、熱状態、バックグラウンド負荷）は同じブロックの $b_j$ と $c_j$ に同様に影響し、 $d_j$ では相殺されます。

点推定

$\operatorname{med}$ を標本中央値として、

\Delta_{\%} = 100 \cdot \frac{\operatorname{med}(d)}{\operatorname{med}(b)}, \qquad \text{speedup} = \frac{\operatorname{med}(b)}{\operatorname{med}(b) + \operatorname{med}(d)} .

中央値の破綻点は 50 % です。ブロックの半数までが任意に乱されても（プリエンプトされたバッチ、ページフォールトの嵐など）、推定値が任意に動くことはありません。これが bench の集約における外れ値の扱いであり、観測は一切捨てられません。Maremark のプロトコルは外れ値ポリシーも指定します（Development では ReportOnly、RegressionGate では TukeyFence）。これは記録されるプロトコル識別情報の一部ですが、観測はフィルタされずに出力され、このパッケージの集約もフィルタを適用しません。

判定は $\Delta_{\%}$ を実用上の閾値 $\delta$ と比較します。 $\Delta_{\%} \le -\delta$ なら Faster、 $\Delta_{\%} \ge \delta$ なら Slower、それ以外は Equivalent です。 $\delta$ より小さい差は、どれほど精密に計測されていても無関係とみなされます。

標本分位数

Maremark は線形補間による分位数（Hyndman と Fan の type 7¹1 R. J. Hyndman, Y. Fan, “Sample quantiles in statistical packages”, The American Statistician 50(4), 1996. ）を用います。ソート済みの値 $s_0 \le \dots \le s_{N-1}$ と $f \in [0, 1]$ について、 $h = f (N - 1)$ として

Q(f) = s_{\lfloor h \rfloor} + \bigl(h - \lfloor h \rfloor\bigr) \bigl(s_{\lceil h \rceil} - s_{\lfloor h \rfloor}\bigr),

したがって $Q(1/2)$ は通常の中央値です（ $N$ が偶数なら中央の 2 値の平均）。

ブートストラップ信頼区間

$\operatorname{med}(d)$ の不確かさはパーセンタイル・ブートストラップ²2 B. Efron, R. J. Tibshirani, An Introduction to the Bootstrap, Chapman & Hall, 1993, chapter 13. で推定します。 $r = 1, \dots, R$ について：

$\{1, \dots, m\}$ から復元抽出で一様に $m$ 個の添字 $i_1, \dots, i_m$ を引く。
再標本の中央値 $\theta^{*}_r = \operatorname{med}(d_{i_1}, \dots, d_{i_m})$ を計算する。

$\theta^{*}_{(1)} \le \dots \le \theta^{*}_{(R)}$ とソートします。信頼水準 $c$ （パーセント）について $\alpha = (100 - c) / 200$ とします。区間は

\bigl[\, L, U \,\bigr] = \bigl[\, Q^{*}(\alpha),\ Q^{*}(1 - \alpha) \,\bigr],

ここで $Q^{*}$ はソート済みブートストラップ中央値の type 7 分位数です。 $c = 95$ 、 $R = 10\,000$ のとき、これは $[Q^{*}(0.025), Q^{*}(0.975)]$ 、すなわちソート済み再標本の位置 $249.975$ と $9749.025$ （0 始まり）での線形補間です。区間は $\operatorname{med}(d)$ に対するもので、単位はマイクロ秒です（パーセントではありません）。

乱数の添字は、呼び出し側のシードで初期化された xorshift64* 生成器³3 S. Vigna, “An experimental exploration of Marsaglia’s xorshift generators, scrambled”, ACM TOMS 42(4), 2016. から得られ（シードが 0 の場合は固定の定数に置き換えられます）、添字は状態を $m$ で割った余りです。剰余によるバイアスは高々 $m / 2^{64}$ です。シードを固定すれば区間はデータの決定的な関数となるため、解析を再実行すると正確に再現されます。

リグレッションの判定

is_significant_regression は次の両方を要求します

\Delta_{\%} \ge \delta \quad\text{and}\quad L > 0 :

中央値での速度低下が実用上意味のある大きさであり、かつ、中央値の対応差の 95 % 区間が低速側でゼロを含まないこと。第 1 の条件は、小さいが精密に計測された変化を検出してしまうことを防ぎ、第 2 の条件は、大きいがノイズの多い変化を検出してしまうことを防ぎます。

設計上の判断

平均ではなく対応付き中央値

計時の分布は右に裾が長く、ときどき大きな外れ値を含みます。差の平均と $t$ 区間はそうした外れ値に支配されてしまいます。ブロックで対応付けた差の中央値はロバストで正規性の仮定を必要とせず、ブートストラップは中央値の分散公式なしにその区間を与えます。

用途ごとに固定されたパラメータ

confirmatory_regression は $\delta = 3\,\%$ 、 $R = 10\,000$ 、 $c = 95\,\%$ に固定されているため、呼び出し側がリグレッションゲートを弱めることはできません。paired_hotspot は $\delta$ とシードを呼び出し側から受け取り、探索的なホットスポットレポート用に $R = 2000$ を用います。信頼水準は 0.95 として渡されますが、Maremark はこの値をパーセントとして解釈するため、報告される区間はブートストラップ分布の中央 0.95 % であり、ほぼブートストラップ中央値の一点になります。スイートはそこから $\Delta_{\%}$ のみを表示するので、影響はありません。

最小中央値による自動チューニング

tune_dataset は各候補を、有効な確認サンプルの中央値で評価し、中央値が最小のものを返します。完全な同点は候補 id で決着します。スコアは主基準と副基準の両方として @tune.select_best に渡されるため、最速から $\delta$ 以内の候補のうち副基準が最小のもの、つまりやはり最速のものが選ばれます。したがって実用上の閾値は選択に影響しません。スケールをまたいだ 2 候補間の交差点は、データセットごとのラベルから Maremark が計算します。

オラクル付きの不変フィクスチャ

immutable_bench は各入力をスケールごとに一度だけ生成し、すべての出力を独立した参照値と照合します。誤った結果を計算する高速な実装は、比較に勝つのではなく実行を失敗させます。

データとしての環境

environment は各実行についてターゲット、プロファイル、データ型ラベルを記録し、外側のツールだけが知る情報（マシン、周波数ポリシー、コミット）を external-metadata として示します。これにより 2 つの成果物を読む人は、その数値が比較可能かどうかを判断できます。パッケージ自体は環境をまたいだ実行の比較は行いません。

正しさ／不変条件

集約の決定性。 観測とシードを固定すれば、paired_hotspot、confirmatory_regression、tune_dataset はどの実行でも同じ値を返します（ブロック id によるソート、シード付き生成器、決定的なタイブレーク）。
対応付け。 サンプルはブロック順に対応付けられます。サンプル数が異なる場合はエラー（MismatchedPairs）であり、黙って切り詰めることはありません。
区間の順序。 $Q^{*}$ は引数について単調であり、 $c > 0$ に対して $\alpha < 1 - \alpha$ であるため、 $L \le U$ が成り立ちます。
スケール不変性。 すべてのサンプルに定数 $\lambda > 0$ を掛けると $\operatorname{med}(d)$ 、 $L$ 、 $U$ は $\lambda$ 倍になり、 $\Delta_{\%}$ 、判定、評決は変わりません。したがって時間の単位は問題になりません。

却下した代替案

平均化の前に外れ値を捨てる。 どんなフェンスも調整定数を必要とし、サンプルを暗黙に変えてしまいます。中央値を使えばそれは不要です。
2 つのサンプル集合の非対応比較。 $B$ と $C$ の計測の間のドリフトが、差にそのまま入り込みます。
正規理論に基づく区間。 計時データにはない対称な誤差を仮定しています。

境界

計時、プロセス制御、ファイル出力は行いません。それらは Maremark のランナーと tools/benchmark.py が担います。
絶対的な性能目標は設けません。閾値は相対的な差に適用されます。
性能の結果が正しさに関する主張を変えることはなく、ベンチマークは native ターゲットでのみ実行されます。

R. J. Hyndman, Y. Fan, “Sample quantiles in statistical packages”, The American Statistician 50(4), 1996. ↩
B. Efron, R. J. Tibshirani, An Introduction to the Bootstrap, Chapman & Hall, 1993, chapter 13. ↩
S. Vigna, “An experimental exploration of Marsaglia’s xorshift generators, scrambled”, ACM TOMS 42(4), 2016. ↩