10億行のデータ処理に学ぶ、Rust/Go 低レイヤ最適化術（@yusuktan）【#も読】

みなさんこんにちは。

「あの人も読んでる」、第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ミスを減らす……といった泥臭い最適化が延々と続きます。

マルチスレッド化で1.08秒へ

シングルスレッドが限界に達したところで並行処理を導入します。std::thread::available_parallelism でコア数を取得し、mmap した領域をコア数分に分割。

各スレッドは独立した HashMap で集計し、最後に mpsc::channel 経由でメインスレッドにマージ結果を送ります。これにより、シングルスレッドでは20秒強だった処理が一気に 1.08秒 まで短縮されました。

Javaの最速には及ばなかった理由

ここまでの最適化を施しても、Javaのトップ実装の記録である0.8秒（Gjengsetさんの環境で測定した数値）には届きませんでした。

しかしその最速Java実装を見てみると、「ハッシュ衝突が発生しない前提のPerfect Hashing」 によって衝突時のフォールバックを省略するという、ルールギリギリの最適化を行っていることが判明。Gjengsetさんは「衝突を無視する実装は不正解だ」として、この手法は採りませんでした。

10時間半のライブコーディングからの学び

正直、10時間半というのは1本の動画として見るには長すぎるのですが、

1. perf でCPUサイクル・キャッシュミス・分岐予測ミスを分析する
2. 仮説を立てる
3. メモリ配置やSIMD、CPUキャッシュなども意識した修正で改善する

という試行錯誤のサイクルを見られるのは、他では得難い学びです。

ちなみに前回のも読 第17回で取り上げた “Are Mutexes Slow?” もGjengsetさんの動画で、こちらと地続きの話題（CPUキャッシュ・コヒーレンス）が出てきます。あわせて見るとおもしろいかと思います。

ThePrimeagen が Go の 1BRC 記事をレビューする

2本目は、Shraddha Agrawalさんによる 「Goで1BRCを6分→14秒まで縮めた」 というブログ記事を、ThePrimeagenさんがリアクション動画形式で読み解いていく1本です。

Gjengsetさんの動画が「実際にコードを書き続けるライブコーディング」なのに対し、こちらは「他人の最適化プロセスをレビューしながら自分なら何を考えるかを語る」スタイル。同じ問題を別の角度から味わえます。

Go 版の最適化ステップ

著者の記事では、「データ構造」「並行処理」「ファイル読み込み」の3つの軸で最適化が進んでいきます。

• ベースライン：bufio.Scanner で1行ずつ読み、map[string][]float64 に温度のスライスを丸ごと持つ素朴な実装
• データ構造の改善：「全温度を保持する代わりに、最小値・最大値・合計・カウントの4つだけを構造体に持つ」ように変更。GCの負担とメモリフットプリントが激減
• float64 から int64 へ：Rust版と同じ発想で、温度を整数として扱うように変更。これだけで約40秒短縮。固定精度のデータでは、汎用的な浮動小数点パースのチェックコストが想像以上に大きい、という共通の教訓
• 並行処理の導入と罠：ここがGo版ならではの面白さです。最初は「観測所ごとにgoroutineを立ち上げる」アプローチを取ったものの、goroutineが最大1万個にもなって、スケジューラのコンテキストスイッチがオーバーヘッドになり逆に遅くなった、というアンチパターンが紹介されます。これをプロデューサー/コンシューマー + バッファありchannelのモデルにつくり変えることで改善
• チャンク読み込み: bufio.Scanner の内部処理を避け、os.File の Read メソッド で64MB単位の大きなチャンクをそのまま読み込み、ワーカーに渡して並列で処理。各ワーカーが独立した部分マップをつくり、最後にマージすることでロック競合を回避

pprof を信じる姿勢

ThePrimeagenさんが何度も称賛していたのが、著者が最適化の前に必ずpprofでプロファイルを取って、データに基づいて意思決定しているところです。「なんとなく速そう」ではなく、runtime.schedule や runtime.chanrecv に時間が吸われている事実をプロファイラで確認した上で、それに対応する設計に切り替える。理屈では分かっているものの、改めてプロファイラによる調査の強力さを感じました。

さらなる最適化のアイデア

動画の終盤では、14秒の壁をさらに越えるアイデアとして、

• 標準の strconv.ParseInt を捨ててカスタムパーサーを書く
• map をやめて Trie木 や Swiss Map に置き換える
• mmap を使う
• unsafe で文字列 ↔︎ バイト列の変換コストをゼロにする

といった話題も出てきます。ここまでくると、ほとんどGjengsetさんがRustで通った道と同じです。

言語が違っても突き詰める方向は似てくる。つまりその共通部分は、プログラミング言語によらず応用可能で、汎用性の高い（しかし誰もができるわけではない）テクニックであるということが分かるかなと思います。

2本を見比べて思うこと

最後に、両方を見て個人的に印象に残ったポイントをまとめてみます。

1. 「整数として扱う」は両言語に共通する大きな勝ち筋：1BRCの温度は小数点以下1桁という固定精度なので、f64 のパースを避けて整数演算で済ませるのは、RustでもGoでも大幅な短縮につながっていました。データの性質を理解した上で、汎用的な抽象を捨てることで大きなリターンが得られていました
2. ボトルネックは大体「コア間の調整」と「割り当て」：スレッド/goroutineの数を増やすほど、HashMap のルックアップやスケジューラの切り替えコストが浮き彫りになります。マルチコアCPUで速いコードを書くための基本を押さえる題材としても、1BRCはよくできています
3. プロファイラに従う：GjengsetさんもAgrawalさんも、必ず perf / pprof を回してから次の手を打っています。職人芸が極まってくると、直感だけに基づく最適化が正解であるケースも増えてくるとは思いますが、コンピュータアーキテクチャの基礎を理解した上で思い浮かぶ「直感」を、プロファイラによる「裏付け」を得て改善していく、というように両輪で駆動していくのが良いのではないかなと感じました

おわりに

今回は1BRCをテーマに、RustのライブコーディングとGoのブログ記事レビューという2本の動画を紹介しました。同じ問題を異なる言語・異なる形式で追体験することで、最適化の本質と言語固有の事情がきれいに分離して見えてくるのが、とてもおもしろかったです。

1BRCの公式リポジトリでは、いまもさまざまな言語の実装が集められており、JavaやRust、Go以外にも多くの言語で挑戦されています。僕自身もパフォーマンス最適化を学ぶ題材として、時間を見つけて挑戦してみたいと思っています。特にプロファイラの使い方と、プロファイリング結果を元にしたデータドリブンな最適化は、テクニックとして身につける価値が非常に高いだろうなと感じています。

また次回、おすすめコンテンツを紹介していきます。お楽しみに！

maguroさんの「も読」過去記事

• 再現しないバグは直せない――AI時代のソフトウェア品質とDST（4月3日公開）
• ライブコーディング視聴のすすめ in 2026（3月6日公開）
• OSSメンテナの憂鬱 ―― “AI Slop” がもたらす疲弊（2月6日公開）

執筆者へのお便り