HN 日本語サマリー

← 一覧へ戻る
プログラミング

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

Count the Bytes, Not the FLOPs (thepragmaticquant.com)

6 pointsby sgilda1 コメント

要約

この記事は、tsbootstrapライブラリにおけるパフォーマンス最適化の経験を共有しています。著者は、計算量(FLOPs)よりもメモリ帯域幅(バイト数)に焦点を当てることで、ブートストラップ処理の速度を劇的に向上させました。配列を事前に構築(マテリアライズ)せず、状態を保持しないという2つの原則を採用することで、3.1倍から20倍の高速化を達成しました。

全文翻訳

バイト数を数えよ、FLOPs(浮動小数点演算回数)ではなく

TL;DR: tsbootstrapの高速パスは、かつて各ブートストラップレプリケートを1つの巨大なバッチドテンソルに構築していました。ルーチンジョブでは、160 MBのテンソルがメインメモリに送られ、1つのレプリケートにつき1つの要約数値を生成するために引き戻されていました。私たちはホットパスを2つのルールを中心に再構築しました。1つは、削減(reduction)のみを消費する配列を絶対に具現化しないこと、もう1つは、導出できる状態を決して保持しないことです。現在、すべての直接比較ベンチマークセルで融合パスが有利になり、安定したベンチマークグリッドでは3.1倍から20倍の性能向上が維持されています。実行時間の大部分が乱数シードを生成するPythonで占められていた最後のしぶといセルは、シードオブジェクトを削除した再設計の検証実行で13.1 msから0.55 msに短縮されました。

完全なレプリケートテンソルは、必要であれば引き続き利用可能であり、その具現化パスにおいては、私たちのデフォルトバックエンドは既存のライブラリよりも遅いままです。その行は、他の行とともに以下に示されています。

この夏の初め、順調に進んでいると思っていたパフォーマンス強化の最中に、tsbootstrapのブロックブートストラップエンジンを、長年洗練されてきた成熟した計量経済学ライブラリであるarchと初めて直接比較しました。私たちは負けました。現実的なワークロード、数千点の時系列データに対する数千回のレプリケートにおいて、この記事で説明するコンパイル済みエンジンが存在する前は、開発中のマシンで、エンドツーエンドで数倍遅い結果となりました。私たちがこれまでに出荷したすべてのリリースにはその損失が含まれており、ユーザーはそのワークロードに遭遇した際に常にその代償を払っていましたが、私たちのツールではそれを知ることは決してできませんでした。

私はそれを予期していませんでした。私たちのベンチマークスイートは、ライブラリを自身の過去と比較するだけでした。回帰スイートは、昨日より遅くなったかどうかを教えてくれますが、ユーザーが気づくであろう正確なワークロードにおいて、他のライブラリよりも遅いことを教えてはくれません。直接比較が存在する日、その損失が現れました。それはずっとそこにありました。

プロファイラの最初の回答は、ありふれたものでした。測定された欠陥の大部分は、削除可能なインタープリタのコストでした。レプリケートごとのPythonインデックスループ、呼び出しごとに生成される数千のシードオブジェクト、積み重ねられたオブジェクトラッパーです。しかし、その下には2番目の構造的な問題がありました。反射的な修正でも勝てなかった理由です。Pythonのオーバーヘッドに対する反射的な修正は、バッチ処理です。ループを単一のベクトル化されたNumPy操作に置き換えます。バッチ処理は、インタープリタを内部ループから外し、メインメモリを介したB倍のトラフィック(Bはブートストラップレプリケート数、この物語のすべてのコストがスケールする数)と交換します。なぜなら、バッチ化された設計はすべてのレプリケートを一度に具現化するからです。既存のライブラリのレプリケートループも通常のPythonです。それは、作業セット(ループがアクティブに触れるデータ)をキャッシュに収まるほど小さく保ち、存在するリサンプルのたびに即座に消費することで勝利します。よりハードなバッチ処理では、それに勝つことはできませんでした。

ここにマシンの側の議論があります。CPUコアは、レジスタに保持しているものしか計算できません。それをあなたの「手」と考えてください。その背後にはキャッシュがあります。L1は、見上げずに手が届く机です。L2は、あなたの後ろの棚です。L3は、他のコアと共有されており、廊下にあるキャビネットです。それらすべてのかげにはDRAMがあります。メインメモリは、通りの向こうの倉庫です。ステップごとに大きくなり、遅くなります。レイテンシは、上から下まで桁違いです。ハードウェアは、それをランタイムから隠しません。ソースコードからのみ隠します。

今、そのマシンにブートストラップを載せてみましょう。ブートストラップとは、実行したことのない人のために一度説明すると、統計値が妥当な代替サンプル間でどれだけ変動するかを見るために、データを数千回再描画することです。各再描画されたコピーはレプリケートです。控えめな、完全に現実的なジョブを考えてみましょう。n = 10,000の観測値、B = 2,000のブートストラップレプリケート、float64(1つの数値あたり8バイト)の時系列です。バッチ化されたNumPy設計が望むように、すべてのレプリケートを一度に構築すると、B x nのテンソルを要求することになります。10,000 x 2,000 x 8バイト = 160 MBです。これは、コアコンプレックスが見る数十MBのL3をはるかに超えています。そのテンソルのすべてのバイトはメインメモリに書き出され、統計値がそれを一度読み取れるように引き戻されます。統計値が平均値の場合、保持する答えは2,000個の数値です。160 MBの往復で得られた16キロバイトです。

各レプリケートはデータのコピーです。

テンソルはデータよりB倍大きい。
それはDRAMに存在する。

収集と削減を同じパスで行う。
答えだけを保持する。

20 MB vs 1.94 GB、B = 50,000。2026-07-04にv0.4.0で測定。ストリーミングパスは変更なし。

バッチ化された設計のテンソル:組み立てられ、キャッシュ境界を氾濫し、答えに圧縮される。境界は模式的。バイト数は作業例の算術演算。
より大きなジョブ(短い時系列の5万回のレプリケート)では、具現化パスは1.94 GBに達しましたが、ストリーミングパスは20 MBに抑えられ、約97倍でした(2026-07-04にバージョン0.4.0で測定。ストリーミングパスは変更なし)。

この図のデータテーブルを見る

量値
レプリケートテンソル、作業例(n = 10,000、B = 2,000、float64)160 MB
保持される答え(レプリケートごとの平均値1つ)16 kB
B = 50,000でのピークメモリ、n = 2,000の時系列:具現化 vs ストリーミング1.94 GB vs 20 MB(約97倍)、2026-07-04にv0.4.0で測定
作業例の形状でのピーク常駐メモリ、定常ブロックリサンプリング(2026-07-11測定):具現化 vs ストリーミング617 MB vs 234 MB。ここで234 MBは純粋なプロセスベースライン。ストリーミング実行は何も計算しない実行と区別がつかない。具現化の差は160 MBテンソルを超える。なぜならパスは返されたコピーとインデックス行列も保持するため

現在出荷されているtsbootstrapは、高速パスでそのテンソルを構築しません。それがどのように止まったかの物語です。最初の壁はメモリトラフィックです。バイトそのものが階層を通過します。2番目の壁は、ハードウェアではなく、言語ランタイムとライブラリ自体の設計の中に隠れており、認識するのに時間がかかりました。それは状態(割り当てられたオブジェクトとシードされたジェネレータ)のコストであり、ランダム性が正しい順序で発生するためだけに存在します。私たちは配列の具現化をやめ、保持する状態をやめました。

壁1:メモリトラフィック

バッチ化された設計が実際に行っていることから始めましょう。ブロック(連続した実行ブロック全体をリサンプリングするため、時系列を時系列たらしめる短期依存関係は各ブロック内に生存します。このシリーズの最初の記事は、それがそうでない場合に何が起こるかについてです)で時系列をブートストラップするには、ランダムなブロック開始位置を引き出し、それらをリサンプルインデックスに展開し、それらのインデックスを通してデータを収集し、各レプリケートで統計値を計算します。バッチ化されたバージョンは、それらの各操作をBレプリケートすべてに対する1つの配列操作として実行します。(B, n)インデックス行列を構築し、(B, n, d)値テンソル(dは時系列の列数)に収集し、中央の軸に沿って削減します。

そのテンソルの各セルの作業を数えてみましょう。出力時に8バイト書き込み。削減のために8バイト読み戻し。約1回の浮動小数点加算、16バイト移動ごとに1回の加算。行列乗算のような計算バウンドカーネルは、1バイトをプルするごとに数百回の演算を行います。その比率、算術強度(移動するバイトあたりの計算量)は、ワークロードがプロセッサによって制限されるか、メモリシステムによって制限されるかを決定する数値です。私たちのものは、算術強度が可能な限り低いものです。コアが決して制約になることはありませんでした。それらはベンチマーク中にメモリを待っていました。収集が遅いのは、コードが解釈されているからではなく、プロセッサを忙しく保つには算術強度が低すぎるからです。それは、FLOPsの問題として評価されているバイトの問題です。

この観点から見ると、既存のライブラリのループは、時代遅れに見えるのをやめ、正しいものに見え始めます。1レプリケートずつということは、1つの(n, d)リサンプルずつということです。キャッシュに収まる作業セットであり、統計値によって即座に消費され、次のものが到着する前に消えます。その作業セットはBとともに増加しないため、DRAMがその物語にほとんど入ってきません。バッチ化された設計のトラフィックはBとともに線形に増加し、テンソルが最後のキャッシュレベルを超えると、追加のレプリケートのバイトはすべてメインメモリを介した往復を行います。NumPyのプログラミングモデルは、実際には別個の2つの決定を静かに結びつけています。ディスパッチのバッチ化とバイトのバッチ化です。ループが勝ったのは、私たちが構築していたものを構築しなかったからです。

作業例における会計としての議論全体を以下に示します。n = 10,000、B = 2,000、float64、レプリケートごとに1つの平均値。あなたのワークロードに合わせてナプキンで再計算してください。比率が重要です。

量具現化パス融合、ストリーミングパス
中間割り当て160 MB、完全なレプリケートテンソル1つの(n,)インデックス行 + スレッドあたり1つの(n, d)スクラッチ(各約80 kB)
DRAMを通過するバイト少なくともテンソルの2倍:書き出し、読み戻しキャッシュで消費、作業項目ごと
保持される有用な出力16 kB、レプリケートごとの平均値1つ16 kB、同じ答え
答えのバイトあたりの移動バイト数約20,000 : 1約1 : 1

これらは新しい洞察ではありません。コンパイラは何十年も中間配列を回避するためにループを融合してきました。そして、すべての数値プログラマは最終的にメモリの壁に遭遇します。知っておく価値があるのは、同じ壁が現在、Transformerのトレーニングとサービングを支配しているということです。それらが両方を再形成したカーネルであるFlashAttentionは、最初の図のキャプションでそのコアの動きを説明しています。それは「大規模なN×Nアテンション行列の具現化を防ぐためのタイリング」を使用しており、その1つの拒否と、周囲の操作を単一のカーネルに融合したことにより、GPT-2のアテンションで7.6倍の高速化が得られました。それが対戦する階層は、GPU版の私たちの階層です。A100のメインメモリは最大2.0 TB/sでストリーミングしますが、オンチップのSRAM(ストリーミングマルチプロセッサあたり192 KB)は、約10倍高速に動作します。同じ形状、同じ結論:作業セットを高速メモリに保持し、巨大な中間体を絶対に書き出さないこと。FlashAttentionは、古いコンパイラの原則がデータセンター規模でも依然として有効であることを証明しています。

1回のパスで、何も残さない

修正は、B幅のテンソルを構築することなく、レプリケートごとに1回のパスで、バッチ処理パイプラインが行ったすべてのことを行う単一のコンパイル済みカーネルです。ワーカーごとのスクラッチ領域は依然として存在しますが、それはB倍のデータではなく、nサイズの揮発性です。これの標準的な名前はカーネル融合です。配列を互いに渡す別々のパスの代わりに、1つのループ本体が1つのレプリケートを構築、収集、削減し、統計値のみを出力します。

各レプリケートは並列作業の1単位です。カーネルは、プライベートな(n,)インデックスバッファとプライベートな(n, d)スクラッチ領域を提供し、そのレプリケートのサンプリングインデックスをバッファに構築し、列ごとに値を通しインデックスを収集し、同じループ本体で削減器(平均、分散、標準偏差、または分位数)を適用し、(B, d)出力の1行を書き込みます。冒頭の160 MBのテンソルは決して存在しません。ピークメモリはソースデータ、ワーカーごとのスクラッチ領域、そして実際に欲しかった16 kBです。カーネルは、最初に実行されたときにマシンコードにコンパイルされます。これはジャストインタイム(JIT)コンパイルであり、最初の呼び出しコストは、コンパイル済みバックエンドがロードされる際の明示的なウォームアップスイープによってホットパスからオフセットされます。

同じバイト志向は、より小さなノブにも現れます。リサンプリングインデックステンソルはint64ではなくint32であり、フットプリントを半分にします(インデックスが32ビットでアドレス指定できる範囲を超えた場合に明示的に発生する例外であり、サイレントオーバーフローではありません)。また、返されるシミュレーションテンソルはfloat32で要求できますが、すべてのモデルフィットとすべての削減はfloat64のままです。ストレージのdtype選択、どちらもトラフィックのために行われました。

外部からは1つの引数です。具現化呼び出しと融合呼び出しは、同じメソッド仕様とシードを取ります。

import numpy as np
from tsbootstrap import MovingBlock, bootstrap, bootstrap_reduce

x = np.random.default_rng(0).standard_normal(10_000)

# the materializing path: every replicate, as arrays
res = bootstrap(
    x, method=MovingBlock(block_length="auto"),
    n_bootstraps=2_000, random_state=0)

# the fused path: same resampling, one pass, only the statistic survives
red = bootstrap_reduce(
    x, method=MovingBlock(block_length="auto"), statistic="mean",
    n_bootstraps=2_000, random_state=0, backend="compiled")
lo, hi = red.quantile(0.05), red.quantile(0.95)

メモリへの影響は微妙ではありません。Bに対するピークメモリのスキャン(2026-07-04にv0.4.0で測定。ストリーミングパスは変更なし)では、n = 2,000の時系列に対するB = 50,000での完全なレプリケートテンソルの保持は1.94 GBのコストがかかりました。同じ5万回のレプリケートに対する削減パスは20 MBでピークに達し、約97倍軽量でした。削減パスのピークは、保持する統計値の数とともに増加し、パスの長さ(B個の完全な時系列ではなく、B行の回答)とともに増加するため、5万回のレプリケートは容量計画の問題ではなくなります。

パスを融合したことで、大規模なワークロードは勝ちました。しかし、すべてに勝ったわけではありません。それが勝てなかったセルは、2番目の壁が現れる場所です。

壁2:保持する状態

融合カーネルが出荷された後、1つのベンチマークセルが動かなくなりました。それは最小のセル、i.i.d.リサンプリング(独立したドロー、ブロックなし、最も単純なブートストラップ)で、短い時系列(観測値200、レプリケート999)でした。既存のライブラリに負け続け、その隣のセルが倍々で落ちていく中、そのセルは13.1ミリ秒で釘付けになったままでした。このような小さなカーネルはマイクロ秒で終了します。何かがクロックを占有していました。私はついに全体の呼び出しをプロファイルしました。私が誇りに思っていた部分ではなく。

カーネルは無罪でした。ほとんど実行されていませんでした。

そのセルの壁時間の約95%は、カーネルが起動する前、Pythonで乱数シードをセットアップするのに費やされていました。そして、これは固定のディスパッチコストではありません。これはO(B)スケールする税金であり、シリアルなオブジェクト割り当てループであり、小さなジョブではクロックを支配し、カーネルが開始する前に最大のジョブに線形に増加します。

[画像][動画]

同じワークロードを2回、状態再設計の検証実行で示します。左側では、レプリケートごとのシードオブジェクトが、リサンプリングが行われる前にPythonで1つずつ構築されており、経過時間の約95%を占め、カーネルは待機しています。右側では、各レプリケートのキーは、1つのルートキーとそのインデックスの純粋関数であり、カーネル内で導出されます。13.1 msが0.55 ms(n = 200で23.8倍のエンドツーエンド)になります。カーネルの算術演算は同一です。

この図のデータテーブルを見る:同じワークロードを2回、状態再設計の検証実行で

設計ストリームごとの状態このセル(n = 200、B = 999)
Mersenne Twister(古典的なデフォルト)ストリームあたり約2.5 kBを保持N/A
Pythonで具現化されたB個のシードオブジェクトレプリケートごとに1つのオブジェクト、シリアルに構築13.1 ms(約95%がシードセットアップ)
1つの128ビットルートから導出されたキーなし、(ルート, レプリケート)の純粋関数0.55 ms

tsbootstrapにおける再現性は、レプリケートごとの契約です。レプリケートiは、そのランダムストリームにバインドされており、作業がどのようにチャンク化されても、または何スレッドで実行されても安定しています。明白な実装は、ストリームを具現化することです。呼び出しごとにB個のシードオブジェクトを事前に生成し、レプリケートごとに1つずつ配布します。正しいですが、呼び出しごとにO(B)のPythonオブジェクトが割り当てられます。大規模なワークロードではカーネルがそれを凌駕しましたが、小さなワークロードではセットアップがランタイムそのものでした。私たちはデータテンソルの具現化をやめましたが、状態のテンソルの具現化は続けていました。

用語、一度だけ説明します。PRNG(擬似乱数ジェネレータ)は、科学計算におけるすべての「ランダム」ドローの背後にある決定論的アルゴリズムです。同じシードを与えれば、同じシーケンスを再生します。これがブートストラップを再現可能にする理由です。

壁2には2つの側面があります。1つ目は通常のPythonオーバーヘッドです。B個のオブジェクトの割り当て、B回のループ、すべての呼び出しで発生します。2つ目はPythonよりも深く、GPUユーザーが10年前にこれを解決した理由です。従来のPRNGは、Random123論文の言葉を借りれば、「逐次依存状態変換として設計」されています。各ドローは、次のドローが依存する状態ブロックを変更します。これは逐次実行とストリームごとのメモリを強制します。状態とはメモリを意味します。Mersenne Twisterインスタンスは約2.5 kBの状態を保持します。バイト数よりも悪いのはシーケンシングです。順序通りに進化しなければならない状態は、1万個の独立したワーカーに渡されることを抵抗します。

Random123の著者らが提案した代替手段は、状態を保持しないカウンターベースのジェネレータです。これは設計を反転させます。ランダムネスを進行させる機械として扱うのをやめ、純粋関数として扱います。キーとカウンターを与えればビットが得られ、状態は一切ありません。どのワーカーでも、他のドローを最初に計算することなく、ストリームbのドローkを計算できます。

そこで、シードオブジェクトを削除し、釘付けだったセルが落ちました。以前は13.1 ms、その後は0.55 ms。同じボックスでの再設計の検証実行で、同じカーネル算術演算を使用しています。数学的な内容は何も変わりませんでした。セットアップ作業が存在しなくなっただけです。

それに取って代わったのはこれです。エグゼキュータは、単一の128ビットルートキーとレプリケート数を取ります。各バックエンドはそこからストリームを導出します。コンパイル済みカーネル内では、各レプリケートのキーは、ルートとレプリケートインデックスから、いくつかの整数混合ラウンドによって計算されます。割り当てなし、保持なし、Pythonなし。私たちの病気はPython的で、オブジェクト割り当てコストであり、スレッドあたりのキロバイトではなく、Random123が診断した病気とまったく同じでした。順序で保持される状態は、純粋関数であるべき場所でした。レプリケートbのキーは、(ルート, b)の純粋関数になりました。特定のドローは、そのキーとカウンターの純粋関数です。その文が設計全体であり、その結果が保証です。レプリケートを1つのスレッドまたは8つのスレッドで、任意の順序で実行しても、出力はビット単位で同一です。なぜなら、スケジュールの影響を受ける共有状態がないからです。その保証は pedantry ではありません。CIの失敗が実際の回帰を意味し、スレッドスケジュールのノイズではないことを意味し、公開された間隔が数ヶ月後に異なるコア数を持つマシンでバイト単位で再生できるようにするものです。

ドローを実行するジェネレータは、その正確な名前を受けるに値します。コンパイル済みカーネルは、Philox-4x32-10を実行します。これは、同じRandom123論文(Salmon et al., SC 2011)からのカウンターベースジェネレータです。10ラウンド、標準的な乗数定数です。これは、NVIDIAがcuRANDのPhiloxデバイスジェネレータとして出荷しているものと同じアルゴリズム、同じ定数であり、JAXがそのランダムAPI全体を構築したスプリットキーの考え方と同じです。32ビットバリアントは、CPUカーネルと配列バックエンドGPUポート間で整数インデックスストリームをいつかビット単位で同一にできるようにするために意図的に選択されました。ラップトップ上の統計ライブラリとデータセンターのトレーニング実行が、同じ理由で、同じ関数の同じ10ラウンドからランダムネスを引き出しています。状態は並列化しません。関数は並列化します。これらはデフォルトには触れません。出荷されているデフォルトバックエンドは変更されておらず、以前のリリースとバイト単位で互換性があります。Philoxパスは`backend=