Go言語で最速のJSONデコーダーを作った話

はじめに

こんにちは。Sugawara Yuutaです。今回は高校の休み時間に考え、空いた時間で作ったJSONデコーダーについて紹介したいと思います。
知ってる限りでは、汎用型受け入れ型をとっているデコーダー（つまり、標準パッケージと同じスタイルという意味です）の中では最速です。

モチベーション

Go言語で開発を始めて、（Go言語のコミュニティーのスタイルがJavaScriptなどと比べるとなんでも標準ライブラリでやってしまうようなのにも関わらず）サードパーティー製のJSONデコーダーが多く作られていることに驚きました。

しかし、大規模なものから小規模なものまで試してみて、それぞれが必ずしも共通しているとは限らない、たくさんの問題を持っていることに気づきました。それについては下のセクションで詳しく取り上げます。

今までのJSONデコーダーが持つ問題

具体的なライブラリの名前は出さないでおきます。

• CPU依存（アセンブリを使ったりして、速くなる可能性を得る代わりにamd64以外が対応されなくなったりします。例えばM1やRaspberry Piはarm64です。）
• ユーザーに優しくない（標準パッケージと互換性がなかったり、操作が複雑だったり直感的ではないなど。）
• 事前準備が必要（ユーザーがSwitch-caseを書く必要があったり、コード生成を使うため一手間増え、開発の作業工程が複雑化します。）
• メンテナンスがされていない（新しい言語のバージョンがサポートされていなかったり、EOLパッケージに依存していたりします。）
• 結局速くない！（リフレクションを多用していたり、io.Readerのサポートが弱かったりします。）

これからのJSONデコーダーの目指すもの

• CPU依存　→ Pure Goで再現。それがたとえアセンブリのJITやSIMDを使っているものよりも遅くなったとしても、個人的には価値はあると思います。
• ユーザーに優しくない/事前準備が必要 → Go言語の標準パッケージは使い方が直感的でわかりやすいものになるように作られているため、互換性を保つだけで達成されます
• 結局速くない！　→ 上の二つを守りながらも、高速化を常に頭の中に入れた開発をすることを心がけます。

このようなことを達成するために、今回紹介するsugawarayuuta/sonnetを作りました。

sugawarayuuta/sonnet

https://github.com/sugawarayuuta/sonnet

特徴

• 標準パッケージのデコーダーととほとんど互換（将来的には完全互換になる予定）
• 高速。だいたい標準パッケージの5倍の速さで、json-iterator/goやgoccy/go-jsonより速く、場合によってはbytedance/sonic（最速を謳っている）よりも速い。

ベンチマーク

https://github.com/RichardHightower/json-parsers-benchmark/blob/master/data/citm_catalog.json

BenchmarkEncodingJson-4               56          19289518 ns/op         5850983 B/op      33049 allocs/op
BenchmarkSonnet-4                    313           3477650 ns/op          905760 B/op       5469 allocs/op
BenchmarkGoccyGoJson-4               247           4855301 ns/op         2989978 B/op      14323 allocs/op
BenchmarkJsonIteratorGo-4            225           5163313 ns/op         1339385 B/op      34599 allocs/op
BenchmarkSegmentioEncoding-4         130           9156341 ns/op         5129332 B/op       3303 allocs/op
BenchmarkBytedanceSonic-4            274           4235117 ns/op         3848331 B/op      10505 allocs/op

以上のようになっています。ベンチマークはGoに標準搭載されているものを使用していて、グラフの単位はns/opなので短い方が速いです。
速さが気にならないプロジェクトなら問題はないのですが、標準パッケージであるencoding/jsonは相当遅いです。
もし気になった方がいましたらご自分で計測されることをお勧めします。

デコーダーの実装

• マップを作り型に特化した処理を保存する。

Go言語のマップには、キーは比較できるものなら使用可という特徴があります。
Goのポインターは比較可能です
unsafeを使って値をキャストすることによって動的に型を取得できます。
取得した型はポインターになっており、reflectパッケージ内部では*rtypeと呼ばれていて、型が同じであれば、アドレスも同じになります

以上のことを踏まえると、*rtypeがkeyでfunctionがvalueのマップを作ることができます。そのため、2回目からはリフレクションの使用回数を減らすことができます。

• マップを置き換えることのできる場所は配列または固定長の配列にする。

例えばbyteをキーにしたい場合、最大値が256しかないことを利用して[256]boolなどのような固定長の配列を作って代用することができます。

• 場合によってはマップを自作する

僕の場合、構造体の情報を調べる箇所にロビンフッドハッシュ法を用いてstringでsetして[]byteでgetできるようなマップをhash/maphash標準パッケージを利用して自作しました。
意外なことですが、僕の環境ではxxhashなどを使ったときよりも速かったです。

• ポインター演算

Go 1.17でunsafe.Addが追加され、より簡単にポインター演算ができるようになりました。
僕のパッケージではこれを多用していて、例えば構造体のフィールドにアクセスするときは、 structType にキャストすることによってそこまでのオフセットを取得することができます。
配列にも同じことが言えてunsafe.Add(ポインター, 配列の長さ*要素の型の大きさ)で配列に新しいアイテムを追加するための新しいポインターを取得することができます

• go:linkname

例えばreflectやruntimeのパッケージ内でエクスポートされていない機能などがある場合に、手元にエイリアスを作成することによって使用することができます。現在はしていませんが、init()関数等でそれが動いているかどうかを確認し、動いてなければ標準ライブラリにフォールバックするなどすると、エクスポートされていない機能にアクセスする不安をなくすことができます。

• mapassign_faststr

mapassign_faststrを上記の方法でエイリアスをreflectから作成する場合に、もっと低レイヤーの実装を見てみると、（僕はパニックした時のスタックトレースを辿って気づきました）場所を確保した後に値からコピーを発生させて挿入しているということがわかりました。代わりにruntimeからのエイリアスを作り、場所を確保した後、そのポインターに直接代入することによって大幅にアロケーションを減らすことに成功しました。