バイトを数えよ、FLOPsを数えるな

バイトを数えよ、FLOPsを数えるな Sankalp Gilda · 2026年7月11日 · tsbootstrap · performance · memory · engineering · 5,982 words · 約30分 目次 01 壁一つ: メモリトラフィック 02 ワンパス、そして何も残さない 03 壁二つ: あなたが持ち運ぶ状態 04 計測して削除した二つの最適化 05 スコアボード、損失込み TL;DR: tsbootstrapの高速パスは、かつて各ブートストラップレプリケートを一つの巨大なバッチ化されたテンソルに構築していました。ルーチンジョブでは、1億6000万バイトのテンソルがメインメモリに送られ、そこから集約された一つの要約数を得るために引き戻されていました。私たちは、削減のためだけに存在する配列をマテリアライズしない、そして導き出せる状態を持ち運ばない、という2つのルールを中心にホットパスを再構築しました。現在、すべての直接比較ベンチマークセルで融合パスが有利になり、確立されたベンチマークグリッドは、長い系列で3.1倍から20倍の性能を維持しています。最後の頑固なセル、ランタイムが主に乱数シードを生成するPythonであった部分は、再設計の検証実行でシードオブジェクトを削除した際に13.1ミリ秒から0.55ミリ秒に低下しました。レプリケートテンソル全体は、必要であれば依然として利用可能であり、そのマテリアライズパスでは、私たちのデフォルトバックエンドは既存のものよりも遅いままです。その行は、他の行とともに以下に印刷されています。 この夏の初め、パフォーマンス改善のプッシュの最中、順調に進んでいると思っていたのですが、tsbootstrapのブロックブートストラップエンジンを、長年洗練されてきた成熟した計量経済学ライブラリであるarchと初めて直接比較しました。私たちは負けました。現実的なワークロード、数千ポイントの系列の数千レプリケートにおいて、コンパイルされたエンジン（この記事で説明するもの）が存在する前に、開発に使用していたマシン上で、呼び出し全体がエンドツーエンドで数倍遅くなりました。私たちがこれまでにリリースしたすべてのバージョンにはその損失が伴っており、ユーザーはそのワークロードに正確に遭遇した場合、その代金をずっと支払っていたのです。そして、私たちのツールはそれを決して教えてくれませんでした。私はそれを予期していませんでした。私たちのベンチマークスイートは、ライブラリを自身の過去と比較するだけでした。回帰スイートは、昨日よりも遅くなったときに教えてくれますが、ユーザーが気づくであろう正確なワークロードで、他のライブラリよりも遅いことを教えてはくれません。直接比較が存在する日、その損失が現れました。それはずっとそこにありました。 プロファイラの最初の回答は、通常のものです。測定された赤字のほとんどは、除去可能なインタープリタのコストでした。レプリケートごとのPythonインデックスループ、呼び出しごとに生成される数千のシードオブジェクト、積み重ねられたオブジェクトのラッピングです。しかし、その下には第二の構造的な問題がありました。反射的な修正でさえ勝てなかった理由です。Pythonのオーバーヘッドに対する反射的な修正は、バッチ処理です。ループを単一のベクトル化されたNumPy操作に置き換えます。バッチ処理は、インタープリタを内部ループから外し、それをメインメモリを通過するB倍のトラフィック（Bはブートストラップレプリケートの数であり、この話のすべてのコストがスケールするカウントです）と交換します。なぜなら、バッチ化された設計は、すべてのレプリケートを一度にマテリアライズするからです。既存のライブラリのレプリケートループも通常のPythonです。それは、作業セット（ループがアクティブに触れるデータ）をキャッシュに収まるほど小さく保つことで勝ちます。各再サンプリングが存在するとすぐにそれを消費します。私たちは、よりハードにバッチ処理することでそれを打ち負かすことはできませんでした。 ここにマシンの側の議論があります。CPUコアは、レジスタに保持しているものしか計算できません。それをあなたの手と考えてください。その背後にはキャッシュがあります。L1は、見上げずに手が届く机です。L2は、あなたの後ろの棚です。L3は、他のコアと共有されており、廊下の向こうのキャビネットです。それらすべてを越えたところにDRAMがあります。メインメモリ、通りの向こうの倉庫です。各ステップでより大きく、より遅く、全体で数桁のレイテンシがあります。ハードウェアは、それらのいずれもあなたのランタイムから隠しません。それはあなたのソースコードからだけ隠します。 そこにブートストラップを置いてみましょう。ブートストラップとは、一度実行したことのない人のために説明すると、統計量が妥当な代替サンプル全体でどれだけ変動するかを見るためにデータを数千回再描画することです。そして、その再描画された各コピーがレプリケートです。控えめで完全に現実的なジョブを考えてみましょう。n = 10,000の観測値、B = 2,000のブートストラップレプリケート、float64（数値あたり8バイト）の系列です。バッチ化されたNumPy設計が望むように、すべてのレプリケートを一度に構築すると、B x nテンソルを要求することになります。10,000 x 2,000 x 8バイト = 1億6000万バイトです。これは、コアコンプレックスが見る数十メガバイトのL3をはるかに超えています。そのテンソルの各バイトはメインメモリに書き出され、その後、統計量がそれを一度読み取れるように引き戻されます。そして、その統計量が平均値であれば、あなたが保持する答えは2,000個の数値です。1億6000万バイトの往復で得られた16キロバイトです。 メインメモリ（DRAM）キャッシュ境界あなたのデータ n = 10,000 · float64 レプリケートテンソル 8 MB 40 MB 80 MB 120 MB 160 MB 16 kB レプリケートごとの一つの統計: (B, d) 各レプリケートはデータのコピーです。テンソルはデータよりB倍大きいです。それはDRAMにあります。同じパスで収集し、削減します。答えだけを保持します。 20 MB、1.94 GBが立っていた場所、B = 50,000。 2026-07-04にv0.4.0で測定。ストリーミングパスは0.4.0以降変更なし。 1 · アセンブル: バッチ化された設計 1億6000万バイトのバイトカウンターがあなたのデータを登る n = 10,000 · float64 各レプリケートはデータのフルコピーです: B = 2,000 × n = 10,000 × 8 バイト = 1億6000万バイト 2 · フラッド: バッチ化された設計 1億6000万バイト B倍のデータ、すべてのキャッシュを通過 あなたのデータキャッシュ境界、概略図 メインメモリ（DRAM） B倍のデータ、テンソルはキャッシュを超えます: DRAMに書き出され、一度読み戻される 3 · コラプス: 融合削減 16 kB バイトカウンターが一つの統計に低下 レプリケートごと 同じパスで収集・削減: テンソルなし、答えのみ保持 バッチ化された設計のテンソル: アセンブルされ、キャッシュ境界を通過し、答えにコラプスされます。境界は概略図であり、バイト数は作業例の算術計算です。 より大きなジョブ（短い系列の5万レプリケート）では、マテリアライズパスは1.94 GBにピークに達しましたが、ストリーミングパスは20 MBを保持していました。これは約97倍です（2026-07-04にバージョン0.4.0で測定。ストリーミングパスは0.4.0以降変更なし）。 データテーブル 数量 値 レプリケートテンソル、作業例 (n = 10,000, B = 2,000, float64) 1億6000万バイト 保持される答え（レプリケートごとの一つの平均値） 16 kB B = 50,000でのピークメモリ (n = 2,000 系列): マテリアライズ vs ストリーミング 1.94 GB vs 20 MB (~97x)、2026-07-04にv0.4.0で測定 作業例の形状でのピーク常駐メモリ、定常ブロック再サンプリング (2026-07-11測定): マテリアライズ vs ストリーミング 617 MB vs 234 MB、ここで234 MBは純粋なプロセスベースラインです。ストリーミング実行は、何も計算しない実行と区別がつきません。 マテリアライズの差は1億6000万バイトのテンソルを超えています。なぜなら、パスは返されたコピーとインデックス行列も保持するからです。 現在出荷されているtsbootstrapは、高速パスでそのテンソルを構築しません。それが停止した経緯です。 最初の壁はメモリトラフィックです。バイトそのものが階層を移動することです。第二の壁は、言語ランタイムとライブラリ自体の設計の中に隠れており、ハードウェアではなく、乱数を正しい順序で発生させるためだけに存在する状態（割り当てられたオブジェクトとシードされたジェネレータ）のコストであり、見るのに時間がかかりました。私たちは配列のマテリアライズをやめ、状態を持ち運ぶのをやめました。 壁一つ: メモリトラフィック バッチ化された設計が実際に行っていることから始めましょう。ブロック（連続した実行全体を再サンプリングし、系列を系列たらしめる短距離依存性が各ブロック内で生き残るようにする。この系列の最初の部分は、それがそうでない場合に何が起こるかについてのものです）で系列をブートストラップするには、ランダムなブロック開始を抽出し、それを再サンプリングインデックスに展開し、それらのインデックスを通してデータを収集し、各レプリケートで統計量を計算します。バッチ化されたバージョンは、それらの各操作をBレプリケート全体に対する一つの配列操作として実行します。すなわち、(B, n)インデックス行列を構築し、(B, n, d)値テンソル（dは系列の列数にすぎません）に収集し、中間軸に沿って削減します。そのテンソルの各セルの作業を数えます。移動する8バイトあたり約1回の浮動小数点加算、1回の加算です。これは、計算バウンドカーネルのようなものではありません。