「One Billion Row Challenge」でJavaが10億行のファイルを2秒で処理できることを実証

原文リンク(2024-01-29)

新年の幕開けとなる2024年1月1日、Decodableの主任技術開発者であるGunnar Morling氏は、JavaコミュニティにOne Billion Row Challenge（1BRC）を立ち上げた。このチャレンジは1月末まで行われ、10億行を最速で処理するJavaコードの作成を目的としている。これまで表彰台には、1.7秒以内に処理を終えるアルゴリズムが名を連ねていた。

このチャレンジのルールは単純で、あらゆるJavaディストリビューション上で動作するSDK機能のみを使用できる。したがって、外部ライブラリやデータストアは解答から除外される。この取り組みをより深く知るため、InfoQはMorling氏、GoToの主席ソフトウェアエンジニアであるEliot Barlas氏、OpenValue RotterdamのディレクターであるRoy van Rijn氏、GraalVMの創設者でありOracleのソフトウェア開発担当副社長のThomas Wuerthinger氏にインタビューした。

InfoQ：これは非常に興味深い挑戦だと感じました。この挑戦について説明していただけますか？また、その動機を教えてください。

Morling氏： 1BRCは、テキストファイルから気温測定値を解析し、各気象観測所の最低、最高、平均気温を決定するという、見かけによらず単純なタスクに基づくコーディングチャレンジです。注意点：ファイルには10億のエントリーがあります！ 私は、高性能のプログラミング技術や新しいAPI（CPUのSIMD命令を活用するVector APIなど）、さまざまなJavaディストリビューションの機能など、Javaがいかに速くなったかを検証し証明する機会を作りたいと思いました。

InfoQ：チャレンジにはだれでも参加できますか？また、どうすれば参加できるのでしょうか。

Morling氏： まずはREADMEファイルを読んで、レポジトリを複製してください。あなたのアイデアを実装して、他の人がどう試みているか確認してみましょう。結局のところ、すべては学習なのです。

InfoQ：このチャレンジへの取り組みで、何か驚くようなことはありましたか？

Morling氏： ハッカーは、特定のキーセット（気象観測所名など）に最適化された多くのソリューションを悪用する可能性があります。そのため、特定のデータセットに限って機能させました。コミュニティの協力を得て、目的を明確にできました。

興味深いソリューションがたくさんありました。SIMDと新しいJavaネイティブメモリAPIの使用（私が期待していたもの）、SWAR（レジスタ内のSIMD）を含む高度に最適化された構文解析関数など私の期待以上でした。今では、最速のエントリに取り組んでいる人々は、CPU 命令のカウント、分岐の予測ミスの評価など、ネイティブ最適化の領域に深く入っています。

InfoQ：解決策について教えてください。また、試してみたい技術やテクニックはありましたか？

Eliot Barlas氏：

私の解決策は、利用可能なプロセッサー数と同じ範囲にファイルを分割する方法です。各パーティションには、各気象観測所の統計を別々のスレッドで計算するタスクが存在します。これらの作業が終わると、最終的な結果は統計の最終表に集約されます。

各パーティションのデータはメモリーマッピングされ、パーティションのバイト範囲全体をカバーするMappedByteBufferを介してアクセスされます。タスクは、ByteBufferを使って、パーティション内のデータを1バイトまたはintごとに移動します。気象観測所名は、sun.misc.Unsafeを用いて整数列として抽出、格納されます。

Roy van Rijn氏： この解決策は、SDKが提供する（BufferedInputStreamやHashMapのような）プレーンなデータ構造やAPIを使用することから始まった発展的な試みです。徐々に、メモリへの直接アクセスに安全ではない方法を使うようになりました。並列性、分岐のないコード、SWAR（SIMD as a Register）の実装は、このチャレンジで私の解決策をトップ候補にした要因だと思います。ストレージについては、リニアプロービングのコンセプトに基づき、配列に裏打ちされた "非常にシンプルな"ハッシュマップを独自に実装しました。

Thomas Wuerthinger氏： この解決策は、まず最初にワークロードを並列化対象のプロセッサで利用可能なコア数に分割します。Javaの機能を使って入力ファイルに対するメモリーをマッピングし、もっとも効率的なダイレクトメモリーアクセスを実現します。データを解析するもっとも内側のループは、分岐のないコードを作成し、代わりにいくつかの複雑な算術演算とビット演算を実行しようとする手法で実行されます。この課題では、入力のランダムな性質によりプロセッサが分岐を誤って予測することが多いため、性能を最大化するためには分岐を避けることが鍵となります。

InfoQ：みなさんの解決策はさらに改善可能でしょうか？

Barlas氏： プロジェクト・パナマを遠くから見守ってきたが、1BRCは応用的な方法で外国のメモリー能力を探求する機会を与えてくれました。（中略）プロジェクト・パナマのベクターAPIを使ったスピードアップにはまだ成功していません。例えば、初期段階において私はByteVector APIを使って気象観測所名の高速比較を試みました。他タイプのベクターを使って、MemorySegmentインターフェースと組み合わせることで再挑戦したいと思います。

Wuerthinger氏： 現在可能な向上策は、ターゲットとなるハードウェアに大きく依存します。具体的には、メモリ帯域幅、計算帯域幅、分岐予測への依存度といった面をトレードオフすることが挙げられます。

Roy van Rijn氏： トップでもアプローチは変わりません。私が現在探求しているコンセプトは「メカニカルシンパシー（機械的共感）」であり、テストするマシンに最適な方法で実行される命令の改良を試みています。

InfoQ：この興味深い新年最初のチャレンジについて、あなたの抱負をお聞かせください。

Morling氏： Javaとそのエコシステム、コミュニティがこれまで以上に繁栄していることは確かです！著名な開発者をはじめとする多くの人たちがこのチャレンジに参加しているのを見て、とても勇気づけられました。誰もがコーディング、あるいはコードを読むことによって知識を得ることができました。コミュニティの助けは本当に素晴らしく、お陰でこのチャレンジがここまで大きく発展できたと思います。

この挑戦は、技術者たちのコミュニティから大歓迎され、Morling氏は、その成功を「すべてが私の予想をはるかに超えていた」と語っている。成績上位はGraalVM上で動作するソリューションが占めているように見えるが、OpenJDKビルド、Amazon Corretto、Eclipse Temurinを使用した応募もあった。Morling氏はさらに「Graalは目の前の課題にぴったりで、無料で数パーセント高いパフォーマンスが得られる」とコメントした。

この挑戦は、Javaエコシステムの枠を超え、Rust、Go、C++、さらにはSQLやShellで書かれたものにまで及んだ。ジャワのエコシステムに関しては、金賞はThomas Wuerthinger氏、Quan Anh Mai氏、Alfonso Peterssen氏がそれぞれ受賞した。銀賞・銅賞に輝いたのはArtsiom Korzun氏、 Jaromir Hamala氏だ。

Morling氏はコミュニティと評価マシンを提供したDecodable社に感謝の意を表した。

このニュースは2024年2月4日にチャレンジの結果を反映するため更新されました。