Goで10億行処理に挑戦：9つの手法で1分45秒から4秒へ短縮

 (benhoyt.com)
35 ポイント 投稿者 GN⁺ 2024-03-04 | 6件のコメント | WhatsAppで共有
  • 1BRC：10億行あるテキストファイルから気温の測定値を読み取り、観測所ごとの最低/平均/最高気温を計算するコードを書くチャレンジ
  • 2024年1月1日から1月31日まで実施され、最新のJavaを最大限活用することが目標だった
  • これに関心を持った人々が、さまざまな言語（Rust、Go、C++、SQL）で挑戦し始めた
  • Goで書かれた9種類のソリューションを詳しく紹介（遅いものから速いものの順）

ベースライン測定

  • cat コマンドを使って10億行のテキストデータ（13GB）を読み込むのにかかる時間は1.052秒。
  • 実際にファイルを処理する wc コマンドはほぼ1分かかる（55.710秒）。
  • AWKソリューションで問題を解くのにかかる時間は7分35秒。

ソリューション1：シンプルでイディオマティックなGo

  • Go標準ライブラリを使った最初のソリューションは1分45秒かかった。
  • bufio.Scanner で行を読み、strings.Cut で ';' を区切りとして分割する。
  • strconv.ParseFloat で気温をパースし、Goのマップを使って結果を集計する。

ソリューション2：ポインタ値を持つマップ

  • マップで2回のハッシュ計算を避けるために map[string]*stats を使用。
  • ポインタ値を使うことで、時間を1分45秒から1分31秒に短縮。

ソリューション3：strconv.ParseFloat を避ける

  • strconv.ParseFloat の代わりにカスタムコードを使って気温をパース。
  • 時間を1分31秒から55.8秒に短縮。

ソリューション4：固定小数点整数を使う

  • 気温を整数で表現して浮動小数点演算を回避。
  • 時間を55.8秒から51.0秒に短縮。

ソリューション5：bytes.Cut を避ける

  • ';' を見つけるために観測所名全体をスキャンする代わりに、末尾からパースする。
  • 時間を51.0秒から46.0秒に短縮。

ソリューション6：bufio.Scanner を避ける

  • bufio.Scanner を外し、ファイルを大きなチャンクで読み込む。
  • 時間を46.0秒から41.3秒に短縮。

ソリューション7：カスタムハッシュテーブル

  • Goのマップの代わりにカスタムハッシュテーブルを実装。
  • 時間を41.3秒から25.8秒に短縮。

ソリューション8：チャンク並列処理

  • シンプルでイディオマティックなコードを並列化し、時間を1分45秒から24.3秒に短縮。

ソリューション9：すべての最適化と並列処理

  • すべての最適化を並列処理と組み合わせ、時間を24.3秒から3.99秒に短縮。

結果表

  • すべてのGoソリューションと、最速のGoおよびJavaソリューションを比較した表を掲載。
  • Go版で最速のものは2.90秒、Java版は0.953秒で処理。
  • 1秒未満のJava版はThomas Wuerthinger（GraalVMの開発者）によるもので、この分野の専門家だからこそ可能だったようだ

最終コメント

  • 日常的なプログラミング作業では、シンプルでイディオマティックなコードが良い出発点になる。
  • データ処理パイプラインを構築する場合、コードを4倍または26倍速くできれば、ユーザー満足度を高め、計算コストを節約できる。
  • ランタイムやインタプリタを構築する場合、性能向上は重要。

GN⁺の見解

  • この記事は、Go言語を使った大規模データ処理の最適化手法を幅広く探ることで、性能最適化の興味深いケーススタディを提供している。
  • 最適化の過程では、Goの標準ライブラリを超えて、カスタムハッシュテーブルのようなデータ構造を実装することが重要な役割を果たすことを示している。
  • 並列処理の効果を強調しており、単一コア最適化と並列化を組み合わせることで驚くべき性能向上を達成している。
  • この記事は、性能に敏感なアプリケーションを開発するソフトウェアエンジニアに有用な示唆を提供する。
  • こうした最適化が実際の本番環境でどれほど有用かはユースケース次第であり、すべてのアプリケーションにこのレベルの最適化が必要とは限らない。

関連記事

6件のコメント

 
cosine20 2024-03-07

7番目のステップで具体的にどんな作業が行われたのか気になりますね。ものすごく大きな性能向上が起きた区間なので（笑）
 
sddsdd94 2024-03-06

各ステップごとに区切って性能向上にかかった時間を示しているのが興味深いですね（笑）
 
galadbran 2024-03-05

wc でも1分で……。やはり最高なのはコードを書かないことですね……ふふ。
 
jhbaek 2024-03-05

良い記事の共有ありがとうございます。かつてシステム最適化に夢中になっていた頃を思い出しますね（笑）
開発経験を積むにつれて、最高レベルまで最適化されたコードは保守が難しく、組織の環境では運用しにくいという経験を何度もしたため、次第に最適化の道から離れるようになりました。（突然の個人的な振り返り）
 
misolab 2024-03-05

組織に最適化されたコード！！
 
GN⁺ 2024-03-04
Hacker Newsの意見
  • 最初のユーザーは、データ操作のためのコード最適化を経験したことがなかったため、cat、wc などを使って基本的なベンチマークを得る最初のセクションが特に興味深かったと述べている。こうした方法は「妥当な」範囲を簡単に把握する手段だと考えている。
  • 2人目のユーザーは、Polarsライブラリを使った場合の処理時間が33秒だったと述べ、最速の手作業による最適化ソリューションに近い、最もシンプルなソリューションに関心を示している。
  • 3人目のユーザーは、Go言語のプロファイリングレポートは分かりにくいと述べており、特定のコード行の実行時間が直感的でない場合、データの予測が難しく、分岐予測器が誤予測している可能性があると説明している。
  • 4人目のユーザーは、Go言語で1BRC（1 Billion Row Challenge）を実施した結果を共有し、Go言語特有の最適化手法を学んだと述べている。たとえば、unsafe.Pointer を使った境界チェックなしのメモリ読み取り、標準ライブラリの bytes と bits パッケージの関数がアセンブリで書かれていること、ガベージコレクションを無効にする設定、スレッドにゴルーチンを固定する方法などがある。
  • 5人目のユーザーは、シェルスクリプト開発者なら、他の言語の開発者たちが準備している間に、すでにその10億行のデータ処理を終えていただろうと主張している。
  • 6人目のユーザーは、データベースはアプリケーションコードより高速で、複雑さが低く、データ更新にもより堅牢だと主張し、データベースでより多くの処理を行うべきだと強調している。
  • 7人目のユーザーは、2010年にPostgreSQLを使って、カナダ環境省の気候データ2億7000万行を照会するWebアプリを開発し、このソフトウェアが受賞した経験を共有している。このアプリは1分以内にレポートを生成できるよう最適化されていた。
  • 8人目のユーザーは、Go言語では並列コードであっても、なおGoらしいイディオマティックなコードスタイルが保たれている点が素晴らしいと述べている。
  • 9人目のユーザーは、大規模なテキストファイルをCLIで扱う際、Unicode解析を省略すると awk、grep などが一段と高速になると述べ、awk のソリューションに LC_ALL=C を追加すれば処理時間を1分未満に短縮できると主張している。
  • 最後のユーザーは、最速のJava版が最速のGo版より速いのは興味深いと述べ、Java仮想マシン（JVM）の性能はかなり優れていると評価している。