みなさんこんにちは。
「あの人も読んでる」、第18回目の投稿です。maguro (X @yusuktan)がお届けします。
今回は、「One Billion Row Challenge（1BRC：10億行のデータ処理チャレンジ）」を取り上げます。
1BRCは、もともとはJavaコミュニティから始まったプログラミングチャレンジで、「10億行のテキストデータ（気象観測所の名前と温度がセミコロン区切りになっている）から、観測所ごとの最小値・最大値・平均値を計算する」という課題です。具体的には、以下のようなデータが入力として与えられます。
Hamburg;12.0
Bulawayo;8.9
Palembang;38.8
Hamburg;34.2
St. John's;15.2
Cracow;12.6
期待される出力の例は以下のようなフォーマットです。
Hamburg;12.0;23.1;34.2
Bulawayo;8.9;22.1;35.2
Palembang;38.8;39.9;41.0
シンプルな課題ですが、ファイルサイズはおよそ10GB超。素朴に書くと数分以上かかる処理を、いかに数秒〜十数秒まで縮めるかが見どころで、最適化の腕の見せ所がたくさん詰まったお題です。
今回は、このチャレンジにRustで挑むJon Gjengsetさんのライブコーディング動画と、Go言語での最適化ブログ記事をThePrimeagenさんがリアクションする動画を紹介します。同じ問題を別言語で解いていくのを見比べることで、「言語に依存しない最適化の原理」と「言語固有の落とし穴」がきれいに浮かび上がってきます。
Rust で 1BRC に挑む（10時間半のライブコーディング）
まず1本目は、Jon Gjengsetさんが1BRCにRustで挑んだ、約10時間半 [^1] にわたるライブコーディングのアーカイブです。外部クレートの利用は禁止（標準ライブラリのみ）というルールの中で、perfによるプロファイリングと最適化をひたすら繰り返していく、まさに職人芸と忍耐強さの動画になっています。
ちなみに1BRCの公式のルールが Rules and limits にまとめられています。要点をかいつまんでまとめると、以下のようになっています。
- 外部ライブラリの利用は禁止。lodash、numpy、Boostなど一切不可で、各言語の標準ライブラリのみで実装すること
- 実装は単一のソースファイルとして提出すること。ライブラリを丸ごとコピペしてくる「裏技」も禁止
- 計算はアプリケーションの実行時に行うこと。ビルド時にあらかじめデータを処理しておくのは不可
- 入力値の範囲：
- 観測所名：非nullなUTF-8文字列、最小1文字・最大100バイト（1バイト文字なら100文字、2バイト文字なら50文字、といった具合）
- 気温：非nullなdouble値、
-99.9〜99.9の範囲（両端含む）で、常に小数点以下1桁
- ユニークな観測所名は最大10,000個
- 特定のデータセットの性質に依存した実装は不可。上記制約を満たす任意の観測所名・任意の分布で動作すること
シングルスレッドでの最適化
最初は素朴に、std::fs::File + BufReader + .lines() で1行ずつ読み、HashMap に集計していくナイーブな実装からスタート。シングルスレッドで実行時間はおよそ 90〜100秒 です。ここから、perf でプロファイルを取りながら順番にボトルネックを潰していきます。
- 文字列割り当ての削減：観測所名のパースで毎回
Stringをつくると重いので、&[u8]のまま処理し、UTF-8検証もスキップ（from_utf8_unchecked）。 mmapの導入：libcクレート [^2]経由でmmapシステムコールを直接呼び出してファイル全体をメモリにマップ。madvisシステムコール[^3] でシーケンシャル読み込みであることをカーネルに伝え、I/Oを高速化。これだけで32秒まで短縮- 数値のカスタムパース：標準の
f64パースが意外と重かったため、温度が常に小数点以下1桁である性質を利用して、整数 (i16) として読み込むカスタムパーサーに置き換える。さらに、マイナス記号の判定で発生する分岐予測ミス（Branch Misprediction）がCPUパイプラインをストールさせていることをperfで見抜き、ifを取り除いたブランチレス実装に書き換える - 区切り文字検索の高速化：改行や
;を1バイトずつ探すのは遅いので、まずはカリカリに最適化されているlibcのmemchrを導入。さらに nightly のstd::simdで64バイトを一度に検索する版にも挑戦
ここまでくると、perf の出力は実行時間の半分以上が HashMap のルックアップとハッシュ計算になります。Rustの標準ライブラリがデフォルトで利用する SipHash は暗号学的安全性を確保するために遅いので、より単純で高速な独自ハッシュ（FxHash風のXORと乗算の組み合わせ）を自作します。が、単純化しすぎるとハッシュ衝突が増えて逆に遅くなり、観測所名をヒープ上ではなくインライン化する ArrayVec 風の構造体をつくってTLBミスを減らす……といった泥臭い最適化が延々と続きます。