この記事では、以前C# Tokyoで行ったプレゼンテーションを元に、JSONパーザーDynaJsonで用いているNaN Boxingという最適化技法について説明する。この記事はC# Advent Calendar 2020の6日目の記事である。
DynaJsonについて
DynaJsonはDynamicJson互換の高速なJSONパーザーである。DynamicJsonを便利に利用しているが、処理速度に不満があるので高速なものを開発した。
DynaJsonではDynamicJsonと同じく、以下のようにJSON文字列をパーズした結果のオブジェクトをdynamic型で受け取り、C#のオブジェクトと同様にメンバーアクセス演算子でメンバーにアクセスできる。この仕様は、大きなJSONをduck typingで処理するときに便利である。
以下にDynaJsonのベンチマーク結果を示す。約1.7MBあるcitm_catalog.json1のパーズに掛かった時間をUtf8Json, Jil, Newtonsoft.Json, DynamicJsonと比較している。測定はAzure D2ds_v4のUbuntu 18.04上で.NET Core 3.1 で行った。
結果を見るとDynaJsonがとても速いことがわかる。もちろん、このようなユースケースが速くなるように作ったので速いのは当たり前である。
NaN Boxingによる最適化
大きなJSONファイルをパーズすると、JSONの値を表すオブジェクトを大量に生成することになる。そこでDynaJsonでは、これを16バイトの構造体で表している。構造体の大きさを16バイトに抑えると、コピーが128bit SIMD命令のロード・ストア各一回ですむので速くなる。
以下に示したのがその構造体である。Explicitレイアウトでフィールドを重ねて16バイトに畳んでいる。String, Array, Dictionaryについては、Typeフィールドの値に基づく排他利用なので重ねても問題ない。問題はdoubleのNumberの上位4バイトにenum型のTypeを重ねていることだ。こんなことをしたらNumberが壊れてしまわないのか。
これを壊さないように実現するのがNaN Boxingである。NaNは浮動小数点演算におけるゼロのゼロ除算や、負の平方根などで生じる値である。IEEE 754で定められたNaNのバイナリ表現の一つは0xfff8000000000000である2。このうち下位51ビットは任意の値でよいので、NaN Boxingはここにデータを詰め込む。
enum型のJsonTypeの定義を以下に示す。まずnull, true, falseをJsonTypeに押し込んだ上で、各メンバーにNaNの上位バイトとして正しい値を割り当てている。これらは、通常のdoubleの上位4バイトとは衝突しない値であり、下位4バイトが何であれdoubleとして正当な値になる。
このJsonTypeの使用例を以下に示す。ToValueはInternalObjectが表す値を取り出すメソッドである。obj.TypeがJsonType.NullからJsonType.Objectのいずれでもない場合は、通常のdoubleの上位4バイトなのでobj.Numberを返している。これでNumberとTypeが上位4バイトで共存できる。
NaN Boxingの効果を測定したベンチマークを以下に示す。ClassはInternalObjectをクラスにした場合、StructはNaN Boxingを用いずに20バイト(8+8+4)の構造体にした場合、NaN BoxingはNaN Boxingで16バイトにした場合である。 20バイトの構造体にするだけで20%の性能改善があるが、NaN Boxingでさらに6.8%も改善する。
広く使われているNaN Boxing
NaN Boxingは、MozillaのSpiderMonkeyやWebKitのJavaScriptCoreといった、JavaScriptの処理系で使われている。ただし、GoogleのV8では使われてない。ほかにはLuaJITやmrubyといった使用例がある。これらの使用例では、ポインターもdoubleに重ねて8バイトに収めている。C#ではmanaged pointerをdoubleに重ねることはできないので、InternalObjectを8バイトにすることは残念ながらできない。
- Native JSON Benchmarkが使用しているファイルの一つで、さまざまなJSONパーザーのベンチマークに用いられていている。
- それ以外はWikipediaを参照してほしい