simdjson - JSONをGB/秒単位でパースする
(github.com)-
SIMD命令セットを使って既存のパーサーより2.5倍高速にパース
-
実行時にCPUごとに最適化されたパーサーを自動選択 : Haswell(AVX2)/Westmere(SSE4.2)/ARM64/その他64
-
完全なJSONおよびUTF-8バリデーションをサポート
-
1つの .h + .cpp ファイル
-
RapidJSON比で25%、sajson比で50%の命令セットしか使用しない
SIMD命令セットを使って既存のパーサーより2.5倍高速にパース
実行時にCPUごとに最適化されたパーサーを自動選択 : Haswell(AVX2)/Westmere(SSE4.2)/ARM64/その他64
完全なJSONおよびUTF-8バリデーションをサポート
1つの .h + .cpp ファイル
RapidJSON比で25%、sajson比で50%の命令セットしか使用しない
4件のコメント
さまざまなバインディング / ポートがありますね。
ZippyJSON: simdjson プロジェクト向けの Swift バインディング。
libpy_simdjson: libpy を使った simdjson 向けの高速 Python バインディング。
pysimdjson: simdjson プロジェクト向けの Python バインディング。
simdjson-rs: Rust ポート。
simdjson-rust: Rust ラッパー（バインディング）。
SimdJsonSharp: .NET Core 向けの C# 版（バインディングおよびフルポート）。
simdjson_nodejs: simdjson プロジェクト向けの Node.js バインディング。
simdjson_php: simdjson プロジェクト向けの PHP バインディング。
simdjson_ruby: simdjson プロジェクト向けの Ruby バインディング。
fast_jsonparser: simdjson プロジェクト向けの Ruby バインディング。
simdjson-go: Golang アセンブリを使った Go ポート。
rcppsimdjson: R バインディング。
Rust版 - https://github.com/simd-lite/simd-json
QConでの開発者による発表内容「Parsing JSON Really Quickly: Lessons Learned」
https://www.youtube.com/watch?v=wlvKAT7SZIQ
リンク先の講演動画の書き起こし:
https://www.infoq.com/presentations/simdjson-parser/
どうやってこれほど高速な速度を出せるのか気になって読んでみたのですが、まさにありとあらゆる黒魔術の結晶体と言えそうです。要点を大まかにまとめると次のとおりです。
[序論]
ほとんどのJSONパーサーライブラリはドライブのシーケンシャル読み取り速度より遅い
私（講演者 Daniel Lemire）のシステムドライブで大きなテキストファイルをシーケンシャルに読み込む速度は 2.2 GB/s だが、主要なJSONライブラリのパース速度はこれに追いつかなかった。
1 GB/s を超えるパース速度を出すライブラリがめったになかったので、私たちで自作することにした。
その結果、ドライブ帯域を完全に使い切れる処理速度を達成した。計算すると入力1バイトあたりCPUはわずか1.5サイクルしか使っていない。どうやってこれを達成したのか？
[各種原則]
分岐をできるだけ避ける
たとえば乱数を配列に入れる単純なコードでも、数値が奇数かどうかを判定する if 文を1つ入れるだけで5倍遅くなる。これはCPUの分岐予測に失敗したときのコストが大きいためだ。
上で示したコードでビット演算により if 文を取り除くと、速度はほぼ元に戻る。
コードを繰り返し実行すると分岐予測の精度が上がって性能低下が減ることはあるが、結局これは非決定的な動作なので、分岐予測が効く場面では性能を予測したり測定したりすることが難しくなる。
より広いワードを使うためにSIMDを積極的に使う
SIMD命令を使うと64ビットより広いワードのレジスタを使えるため、1サイクルでより多くのデータを処理できる。（たとえば SSE や NEON は128ビット、AVX は256ビット）そのため、可能な限りSIMDを積極的に使った。これが入力データ1バイトあたりわずか1.5サイクルしか使わずに済んだ秘訣である。
SIMDを使うために特定プロセッサ依存の組み込み関数（intrinsic function）を使った。アセンブリ言語を直接使うことは推奨しない。
メモリ/オブジェクトの割り当てを避ける
性能を継続的に測定する
ベンチマーク駆動で開発した。私たちのCIには性能ベンチマークが含まれている。
参考までに、CPU負荷の高い処理をするときはCPUの動作周波数が常に変化する点を覚えておく必要がある。
[実例]
例1: 正しいUTF-8かどうかを検証する
入力された任意のデータが正しいUTF-8コードポイントかどうかを検証する作業は、一般に複数の分岐を含む処理だ。
私たちはSIMDで32バイトのデータを最大20サイクルで、分岐なしに正しいUTF-8かどうか検証する方法を作った。
UTF-8のバイトは整数値として最大244を超えないので、SIMD命令でデータを256ビットレジスタに入れ、各バイトから整数244を飽和演算（Saturation arithmetic: 結果値の範囲を制限する演算）で引いたうえで、0以外の値がないかだけを確認すればよい。
この方法は分岐を使う方法より20倍以上速い！
例2: 文字種を分類する
JSONをパースするには、カンマ、コロン、括弧、空白など各種文字を種類ごとに分類する必要がある。
x86-64 と ARM NEON には16バイトサイズのルックアップテーブルを一度に引く命令がある。
1バイトを上位4ビットと下位4ビットに分け、あらかじめ用意した2つのルックアップテーブルをそれぞれ適用し、その結果を AND 演算する。
コードは汚く見えるが、たった5命令で分岐なしに16文字を分類できる。
例3: エスケープ文字を検出する
バックスラッシュ() を前に付けて表すエスケープ文字を、分岐なしに検出できるだろうか？ 特にバックスラッシュ自体をエスケープするためにバックスラッシュが連続する場合も処理しなければならない。
この場合、奇数番目のバックスラッシュだけを見ればよいというトリックがある。
偶数番目の位置と奇数番目の位置を表すビットマスクを定数として用意し、複雑なビット演算を経ることで分岐なしにエスケープ文字をふるい分けられる。
エスケープされた引用符を除外すると、残るのは文字列を表すための引用符である。
こうして求めた引用符の位置をビットマスクとして持ち、xor ビット演算を繰り返すと文字列の位置を表すビットマスクを求められる。この部分は大半のプロセッサで1命令で処理できる。
ビット集合と文字列位置を対応づける方法にもトリックがあるが、時間の都合で省く。
例4: 数値をパースする
数値をパースするのは非常にコストの高い処理だ。よく最適化されたC関数で浮動小数点数のパースをベンチマークしたところ、0.09 GB/s というひどい速度が出た。明らかなボトルネックだった。
数値をパースするほとんどのコードは、一度にバイト単位で処理するのが普通だ。これは決して速くない。
8文字を取り出して1つの64ビット整数にし、講演者が土曜の夜更けに考案した特定の式に当てはめると、この8文字が連続した8桁の数字かどうか判定できる。これは特に桁数の多い数値ほどパースに時間がかかるため重要だ。
Stack Overflow を見ると8桁の整数を高速にパースするコードスニペットもあった。SIMDを使えばさらに改善できるが、重要なのはこのように一度に大量のデータを処理する戦略のアイデアを得ることだ。
[その他]
ランタイムディスパッチ
ハードウェア依存のコードが多く入るため、各プロセッサ向けに最適化された関数ができるが、実行時にプロセッサの種類に合った関数を呼び出すようにするのがかなり難しかった。
何がそんなに難しいのか分からないかもしれないが、問題はコンパイラの種類を問わない移植性のあるコードでこれを実装することだった。コンパイラによってはバグもあり、言語レベルでこうした仕組みを支援しているわけでもない。
この点は、simdjson が他のプロジェクトに簡単に統合できる単一ヘッダーファイルのオープンソースライブラリであるため重要だった。
その他
複数の言語で使えるようにそれぞれラッパーがある。
Rust への移植版があり、Go と C# の移植も準備中だが、Java 版はない。
このプロジェクトで使われた複数の数学的な式は共同著者の Geoff Langdale と考案したもので、VLDB Journal に関連論文を出版した。（ https://doi.org/10.1007/s00778-019-00578-5 ）
おお、よく読ませていただきました。ありがとうございます！