1BRC大会の紹介
- 1BRC大会では、「ありふれた容疑者たち」を処理した後、CSVファイルから温度をパースすることがボトルネックになるだろうと予測されていた。
- 温度は
-XX.X、-X.X、X.X、XX.X の4つの形式で表され、当初は Double.parseDouble() ライブラリ呼び出しが使われていた。
- しかし、ほどなくしてカスタムソリューションが登場し、そのうちの1つはループなしで分岐が2つしかない最適化された方法に見えた。
- その後、Quân Anh Mai(@merykitty) が提示したソリューションによって、Twitterの #1BRC ハッシュタグが沸騰した。このソリューションは
if 文なしで、ファイル読み取りも1回だけだった。
merykittyの魔法のようなSWAR分析
- merykittyのコードは18個のALU演算だけで構成されており、
numberOfTrailingZeros() という単一の低レベル関数呼び出しを含んでいる。
- 入力された
long 値にはCSVからの8バイトが入り、整数形式の温度（実際の温度の10倍）が出力される。
- この技術は「SIMD Within A Register」(SWAR) と呼ばれ、標準的なCPUレジスタと命令を使用する。
- コードは、数値が負かどうかの検出、符号文字の除去、小数点位置の特定、内容をテンプレートに合わせて整列、ASCII文字を数値に変換、各桁に重みを掛けて合計、符号の適用といった段階をたどる。
- これらの段階はすべてALU演算だけで実行される。
結論
- merykittyがたった数日でこれらすべてを単独でどうやって成し遂げたのかは、ブログ記事では説明しきれない本当のミステリーである。
- QuestDBはオープンソースであり、Apache 2.0ライセンスの下で高速なデータ挿入とSQL分析機能を提供する。
GN⁺の意見
- この記事は、単純な温度パース問題を解決するために考案されたSWAR技法の複雑さと創造性を示している。これは、プログラミングにおけるビット演算の強力さと最適化の重要性を強調している。
- このようなアプローチは、特にシステムプログラミングや性能に敏感なアプリケーション開発に関心のある初級ソフトウェアエンジニアにとって、興味深い事例になり得る。
- ビット演算と最適化への理解を深めるために、関連するテーマや問題を扱うオンラインコーディング大会やチュートリアルを探してみると役立つだろう。
- この技術が実際の産業環境でどのように適用できるのか、また、これに類似した最適化手法を使う他のデータベースやシステムがあるのかについて、さらなる調査が必要である。
- QuestDBのようなシステムを導入する際には、性能向上だけでなく、保守性、コードの可読性、長期的な技術サポートといった他の要素も考慮する必要がある。
1件のコメント
Hacker Newsの意見
simdjson論文に関するHacker Newsコメントの要約:
コードコンテキストに対する解釈: 提示された解決策は優れているが、データが適切に構成されているという前提が必要。効率的なエラーチェックと復旧機能は、経験豊富なパーサーにおいて大きな価値を持つ。
数値パース技術: 数値ビットフィールドをそれぞれの10のべき乗で乗算し、MULでshift/加算するのは知られた技法。Lemireのブログを参照。
SWAR(SIMD Within A Register)の説明: Java/Scalaでは、バイト配列ビューのvarハンドルを使って効率的なSWARルーチンを実装する例が多い。
SWARの簡単な定義: "SIMD Within A Register" は、1つのレジスタ内でSIMD演算を行うこと。
BRC(Branchless Ray Casting)のI/Oボトルネックに関する質問: CPUがボトルネックだというのが理解できない。
68000でのSWAR使用経験: 4バイトを一度に並列処理することは可能だったが、オーバーフロー処理が厄介だった。この記事がとても気に入った。
状態空間とスーパーオプティマイザー: 状態空間が小さいので、似た結果を出すスーパーオプティマイザーが存在するのかという質問。
AVX命令とJavaのSIMD対応: このアルゴリズムはAVX命令を使って32倍並列で実行できるが、Javaは特定の場合を除いてSIMD CPUの利用をきちんとサポートしておらず残念。
ビット操作への理解: この記事は、それ以前のどの内容よりもビット操作をよく理解できるようにしてくれたうえ、1BRCチャレンジに対するJavaソリューションを示した著者に感謝している。