10億行チャレンジ

(morling.dev)

2 ポイント投稿者 GN⁺ 2024-01-05 | 2件のコメント | WhatsAppで共有

2024年1月の1か月間にわたって実施された One Billion Row Challenge(1BRC) は、10億行のテキストファイルを処理して Java がどこまで高速化できるかを競うパフォーマンスチャレンジ
入力は station;temperature 形式のシンプルなテキストだが、観測所ごとの 最低・平均・最高気温 を計算し、名前順に正確に出力しなければならない
実装は Javaのみ許可 され、SDKMan の配布版と openjdk.net の Early Access ビルドは使えるが、外部依存関係は禁止
参加者は GitHub の 1brc リポジトリ に pull request で提出し、提供されているベースライン実装で正解形式と性能を比較できる
評価は同一の Hetzner Cloud CCX33 環境で5回実行し、最低・最高記録を除いた3回平均でリーダーボード順位を決定する

10億行を最速で集計する Java 課題

One Billion Row Challenge は、2024年1月1日から1月31日まで開催された Java パフォーマンスチャレンジ
参加者はテキストファイルから気温測定値を読み取り、各気象観測所ごとの 最低・平均・最高気温 を計算する Java プログラムを作成する
難しさの核心は、入力ファイルが 1,000,000,000行 ある点にある
入力は1行に1つの測定値が入るシンプルな構造
- 例: Hamburg;12.0
- 例: Bulawayo;8.9
- 例: Palembang;38.8
出力は観測所名をアルファベット順に並べ、各観測所の min/mean/max 値を表示しなければならない
- 例: {Abha=5.0/18.0/27.4, Abidjan=15.7/26.0/34.1, ...}

提出ルールと実行環境

目標は、同じ処理を行う 最速の Java 実装 を作ること
最適化には仮想スレッド、Vector API と SIMD、GC 最適化、AOT コンパイルなどを活用できる
基本ルールは次のとおり
- 提出物は Java で記述しなければならない
- SDKMan で提供される Java ディストリビューションと openjdk.net の Early Access ビルドを使用できる
- Valhalla のような OpenJDK プロジェクトの EA ビルドも許可される
- 外部依存関係 は使用できない
参加者は 1brc リポジトリをクローンし、README の指示に従って実装を提出する
ベースライン実装は、比較基準と正解形式の確認用として提供されている
提出は upstream リポジトリに pull request を作成する方式で行われる

リーダーボード算出方法とコミュニティ共有

評価は Hetzner Cloud CCX33 インスタンスで実施される
- 仕様は 8 dedicated vCPU, 32 GB RAM
- time プログラムで end-to-end の実行時間を測定する
- 各提出物は5回連続で実行される
- 最も遅い実行と最も速い実行は除外される
- 残る3回の実行時間の平均がその提出物の結果となる
- 結果は leaderboard に追加される
最適化手法の議論は GitHub リポジトリの discussion で続けられている
Java 以外の言語実装を共有するための Show & Tell も用意されており、Rust、Go、C++ などの 1BRC 実装が共有されている

2件のコメント

GN⁺ 2024-01-05

Hacker Newsの意見

現時点で最高性能に見える解法 [0] は ハッシュ衝突を考慮していないので、データセットに十分多くの異なる都市が含まれていると、誤った結果を出しそうに思う
何か見落としているのか気になる
[0] https://github.com/gunnarmorling/1brc/blob/main/src/main/jav...
- その通り。昨日この問題が指摘され、実際に2つの解法が特定のデータセットに合わせたハッシュ関数に依存していて、すべての観測所名で動作しなければならないというルールに違反していたのに、評価中に見落としていた
  ひとまず該当項目はランキング表から削除し、2人の作者が提出物を修正中なので、後で再追加される予定
  [0] https://twitter.com/mtopolnik/status/1742652716919251052
次のアプローチなら全体を 0.3秒以内に処理できると思う
温度は小数1桁なので通常ケースでは約400個の値で十分で、地名も約400個と有限なので、温度×地名の組み合わせ約16万個のルックアップテーブルを作れる
この16万個が4バイトレジスタ内のどの回転位置にあってもハッシュテーブルの一意のバケットへマッピングする状態機械を自動生成し、32ビット状態レジスタで毎サイクル、状態遷移表の参照と次の4バイトのXORを行う
データ全体をメモリ速度でなめながら状態別カウンタを増やせばよく、状態は65Kしかないのでカウンタはキャッシュに収まる
AVX512ならコアあたり、このような32ビット状態機械を512個並列に走らせられるため、計算はボトルネックにならないはず
有効なバケットにマッピングされない高温/低温や未知の地名は遅いコードへ渡し、最小値/最大値の処理もこのようなエスケープで扱えば、発生は数千回だけで済む
この方式はAVX512の単一コアだけでメモリ速度で動作できるので、複数コアに分割する利点はないと思う
- ルックアップテーブルは不要。必要なのは最小値/平均/最大値だけなので、データを保存せず 1回の走査ですべて計算できる
  必要なのは400項目のハッシュテーブルと、実行中の最小値・平均・最大値の3つの浮動小数点値、平均更新用のカウント整数1つだけ
  名前に16バイト使っても全体は16KB以内に収まる
  実行時間は入出力が支配的で、その次がJSONパースになるはず
- 単一コアでは メモリ帯域幅を飽和させられない。コアはメモリ並列性とレイテンシに制限される
  最新のx86サーバーチップの多くは、クロックあたり2つのSIMDロードをretireできるので、AVX2基準で1GHzあたり32GB/s程度が可能であり、コアあたりの帯域を最大化するのにAVX-512が必須というわけではない
  ただしDRAMから読むなら、もっと早い段階、通常のサーバーでは10〜16GB/s付近で頭打ちになる可能性が高い
  データの大半がRAMへあふれる限り、単一コアのスループットは大きく落ち、大きなストリーミング処理ではほぼ常にマルチコア並列性が有利
  L3キャッシュよりはるかに大きいメモリブロックを割り当て、あらかじめページフォールトを起こしておいてから、タイトなループで展開したベクトルロード（AVX2/AVX-512）を行えば簡単に確認できる
- 次の状態が常に前の状態に依存しているのに、状態機械をどうやって並列実行できるのか分からない
  また、状態レジスタをどう解釈するのかも疑問。入力4バイトとXORすると、想定外の地名では実質的に47億個の可能な値のどれにでもなり得る
  想定された地名でも4バイトより長い場合、共通接頭辞を持つ別の名前と区別するには、それぞれ複数の状態が必要なのではないかと思う
- ルール解釈を確認する必要がありそう。既知の400地名に特化しつつ、遅いパスで追加の名前をサポートするコードが有効なのかは明確ではない
  ルールでは、データ生成器が固定された観測所名の集合を使うとしても、どの解法も任意のUTF-8観測所名で動作しなければならないとされている
- 地名を見つけるには、結局 ファイル全体を読んでパースしなければならない
最も遅い実行と最も速い実行を捨て、残り3回の平均を使う方式より、遅い2回を捨てるか、単に最速値を認めるほうがよいと思う
良い実行結果を捨てる妥当な理由はないと思う
- これは トリム平均（Trimmed Mean） という、かなり標準的な測定方法: https://statisticsbyjim.com/basics/trimmed-mean/
- 最良の実行を捨てる理由はある。システムが予測可能に動作し、バックグラウンド処理のせいで遅くなるだけだと考えるなら、最良実行を使うのは筋が通る
  しかしプログラム内部に非決定性の要因が少しでもあれば、これは思ったよりよくあることだが、最良時間は代表性が低くなる可能性が高い
  関連して https://tratt.net/laurie/blog/2019/minimum_times_tend_to_mis... が良い記事
- 最速の実行を捨てるのが受け入れられないなら、なぜ最遅の実行を捨てることには賛成するのか疑問
ルールを厳密に見る立場だと、初回実行時にバックグラウンドデーモンを起動してファイル全体をメモリに載せて固定し、その後の実行が実質的に線形スキャンだけで済むようにキャッシュまで先読みしたくなる
初回実行で結果を事前計算することも、ルールをどこまで拡大解釈するかによっては可能に見えるし、数値をあらかじめより密な形式にパースしておき、後続の実行でそのまま累積和として読んでもよさそう
コンテストの趣旨にはまったく合わないが、見えているルール上は禁止されていないように見える
事前計算が嫌なら、入力を事前にソートしたり、事前にパースしたり、圧縮・ソート・ソート済みメモリ配置のような抜け道も可能
極端に言えば、calculate_time スクリプトにパッチを当てて0秒を返すようにし、競合相手には9999を返すようにすることもできる
- 参加者にコンテストで実際に使う正確なファイルを提供すると、本当に問題が起きる
  入力を読まずに答えを1行でハードコードすることから、ファイル内容を知らない前提で処理することまで、事前計算のグレーゾーンが10億段階くらいある
  何が公平な事前計算で、何がそうでないのかを判定するコンテストになりかねない
  だから機械学習コンテストでは、参加者に最終データを見せない
- これはこのルールに違反しそう
  計算はアプリケーション実行時点で行われるべきで、ビルド時点で計測ファイルを処理して結果をバイナリに焼き込んではならない、とされている
- ルール上、各実行は別々の tmpfs で走らせ、実行間にすべてのプロセスとページキャッシュを消すよう明記すべきだと思う
これは単にディスク速度に縛られる問題ではないかと思う。SIMD やマルチスレッド化のような最適化に意味があるのか疑問
観測所数やハッシュ参照方式によって変わるだろうが、入出力に比べて測定できるほどなのかは懐疑的
- ディスクアクセスは並列化でき、NVMe は非常に高速なので、ボトルネックはディスクより CPU 側かもしれない
  最新ハードウェアを前提に設計されたシステムはこの点を活用しており、私が働く redpanda.com もその一例
  パースは計算時間の大きな部分を占め、区切り文字を探す SWAR のような SIMD 技法が役に立つ可能性がある
  こうしたアルゴリズムのきれいな実装を見たいなら Stringzilla がよい: https://github.com/ashvardanian/StringZilla
  初回実行後にファイルが完全にメモリにキャッシュされる点については、ここで答えた: https://news.ycombinator.com/item?id=38864034
- ワークロードとハードウェアに完全に依存する。一般消費者向け SSD でも 2TB のうち 700GB だけを使えば 7GB/s（56Gbps）を容易に維持できる
  通常のサーバーにはこうした SSD を15台挿せるだけの PCIe レーンが十分あるので、サーバーの入出力帯域はメモリ帯域に近い水準になる
  より高価なサーバーは PCIe 5.0 のように、より高速でより多くのレーンを持つ
  このファイルは10億行なので圧縮時は約1GBで、最初の捨て実行の後はメモリに入るため、このシナリオでは入出力帯域は重要ではない
  GitHub リポジトリには非圧縮で 12GB と書かれているが、それでも入出力帯域が重要ではないことを確認してくれる
- Daniel Lemire のこの発表が興味深い: https://www.youtube.com/watch?v=wlvKAT7SZIQ
  要点は、ディスクがボトルネックになることはまれだということ
- OS とファイルシステムによって異なる。入力ファイルは約 12GB で、32GB メモリのマシン上で5回実行されるため、初回実行後にはファイル全体がメモリにキャッシュされる可能性がある
  例えば Linux で ext2 を使うと初回実行後にファイル全体をキャッシュする可能性が高いが、ZFS ではそうでないかもしれない
- 最速でパースするには、全部 RAM に載せて末尾から逆方向に処理するのが明らかによさそう
  そうすれば数値が下位桁から上位桁の順に現れ、その後に区切り文字と文字列が続き、EOF か改行に出会うまで進められる
ルール上、提出物はすべての入力に対して正しく動作しなければならないが、create_measurements.sh で生成される特定の入力に合わせてチューニングでき、おそらくそうすべきだという意味に見える
例えば、与えられた観測所集合に合わせた完全ハッシュ関数を使う提出物も想像できる
- この要件があるなら、テストデータは例示データと違うものにするのが賢明
  そうすれば過学習的な最適化を防げる
- UTF-8 のせいではるかに難しくなる。ただしルールの精神ではなく文言だけに従うなら、127より大きいバイトを検出した瞬間に遅い実装へ渡せばよい
  127より大きいバイトはマルチバイト UTF-8 文字を意味する
遊びで awk 対 Java の速度比較をしてみた
awk -F';' で観測所ごとの合計、件数、最小値、最大値を蓄積し、END で平均を計算して出力するスクリプト
- PostgreSQL のファイル外部データラッパーとの速度比較を見てみたい: https://www.postgresql.org/docs/current/file-fdw.html
  file_fdw で CSV ファイルを外部テーブルにし、GROUP BY station_name で MIN、AVG、MAX を計算する方式
- ClickHouse local で実行すると約 15.2秒 になる
  clickhouse local で file('measurements.txt', 'CSV', 'station String, t Float32') を読み、観測所ごとに min、max、avg をグループ化し、max_threads = 8 で実行する
  時間の大半はファイルのパースに使われる
- sum 変数はかなり大きくなり得るので、ストリーミング平均を使うのがよい
  例えば new_mean = ((n*old_mean)+temp)/(n+1) のような方式
面白いチャレンジだが、Java専用なのが惜しい。人々が直接 JVMバイトコード を手で作り始める時が楽しみ
- 議論を見ると、さまざまな言語での提出物があるようだ。Go、Rust、Python、C++などがある
  [0] https://github.com/gunnarmorling/1brc/discussions
- あるいは「Javaで書かなければならない」を「実行開始にJVMを使わなければならない」と解釈することもできるし、Javaから別プロセスを起動することは明らかに可能
面白い。Advent of Codeの打ち上げのような感じ
言語間の公平な比較なら、makeとビルド時間も含めるべき。Java/Mavenを何年も使っていなかったが、./mvnw clean verify のダウンロードが2分目に入っているのを見て、その理由を思い出した
- Javaのビルド時間は非常に速い。今測っているのは インターネット速度
  それに、インクリメンタルコンパイルのビルドツールとしてはGradleの方が速い
- ビルド時間を含めるならプログラミング時間も含め、どちらもコードが寿命の間に実行される回数で割るべき
  プログラミングを学ぶのにかかった時間の適切な割合も加えるべき
  こうしたチャレンジでは、非常にナイーブな版が勝つ可能性が高く、非現実的なだけでなくチャレンジの趣旨にも反すると思う
- なぜ clean するのか分からない
  キャッシュを捨てておいて遅いと言っているようなもの
- Mavenは不要
  外部依存関係は使えないと書かれている
チェコ工科大学のCの科目で、非常によく似た課題があった
すべての学生の提出物が継続的に ランキング表 で評価され、より良い成績のための追加点、実質的にはステータス点を得ようと、多くの学生が何十時間も最適化に費やしていた

dlehals2 2024-01-10

1位が6秒なんですね……驚きです

10億行チャレンジ

10億行を最速で集計する Java 課題

提出ルールと実行環境

リーダーボード算出方法とコミュニティ共有

関連記事

2件のコメント

Hacker Newsの意見