This article shows how to use NaN Boxing to improve the performance of a JSON parser for C# named DynaJson.
About DynaJson
DynaJson is a fast JSON parser for C# compatible with DynamicJson. I feel DynamicJson is very useful but lack sufficient performance, so I developed a faster replacement.
DynaJson acts the same as DynamicJson, as shown below. It returns a dynamic type value representing a JSON object resulting from parsing a JSON string. We can access each member of the JSON object with the member access operator like a C# object. This manner is useful to process a large JSON with duck typing.
dynamic json = JsonObject.Parse(@"{
""foo"": ""json"",
""nest"": {""foobar"": true}
}");
string a1 = json.foo; // "json"
bool a2 = json.nest.foobar; // true
A benchmark result of DynaJson is shown below. The benchmark measured the time to process a large JSON file named citm_catalog.json, whose size is about 1.7MB. The benchmark compared DynaJson with Utf8Json, Jil, Newtonsoft.Json, DynamicJson. The measurement ran on .NET Core 3.1 on Ubuntu 18.04 on Azure D2Ds_v4.
The result shows DynaJson is quite faster than others. DynaJson is optimized for this use case, so the result is natural.
citm_catalog.json is one of the files used in Native JSON Benchmark. Many benchmarks for JSON parsers use this file.
An optimization by NaN Boxing
JSON parsers generate a large number of objects representing JSON values on parsing a large JSON file. So DynaJson represents a JSON value as a 16 bytes structure type. Copying a 16 bytes structure is much faster than larger ones because it needs only one load and store instruction for 128bit SIMD operations.
vmovdqu xmm0,xmmword ptr [rdi]
vmovdqu xmmword ptr [rsp+8],xmm0
The definition of the structure is shown below. It folds members into 16 bytes with an Explicit layout. The parser uses each of String
, Array
, and Dictionary
alternately based on the value of Type
, so the members can be laid out at the same offset. How about Number
and Type
? Type
of an enum type overlaps the upper 4 bytes of Number
. It can seemingly break Number.
[StructLayout(LayoutKind.Explicit)]
internal struct InternalObject
{
[FieldOffset(4)] public JsonType Type;
[FieldOffset(0)] public double Number;
[FieldOffset(8)] public string String;
[FieldOffset(8)] public JsonArray Array;
[FieldOffset(8)] public JsonDictionary Dictionary;
}
NaN Boxing can realize the overlap safely. NaN, standing for Not a Number, represents zero divided by zero and the square root of a negative number in floating-point arithmetics. See the Wikipedia entry for more details. One of the binary representations of NaN defined in IEEE 754 is 0xfff8000000000000. The lower 51 bits can have an arbitrary number, so NaN Boxing boxes data in the bits.
The definition of an enum type JsonType
is shown below. JsonType
has not only types of JSON values but also the values themselves for null, true, and false. The definition assigns a legitimate value as the upper 4 bytes of NaN to each member. The values never collide with the upper part of ordinary doubles. Any conjunctions with any lower 4 bytes become a legitimate double.
enum JsonType : uint
{
Null = 0xfff80001,
True = 0xfff80002,
False = 0xfff80003,
String = 0xfff80004,
Array = 0xfff80005,
Object = 0xfff80006
}
A usage of JsonType
is shown below. ToValue
is a method to extract a value JsonValue
represents. If the value of obj.Type
is not anything in the defined members, it must be an upper 4 bytes of an ordinary double, so ToValue
returns obj.Number
. This manner realizes the clear separation of Number
and Type
.
object ToValue(InternalObject obj)
{
switch (obj.Type)
{
case JsonType.Null:
return null;
case JsonType.True:
return true;
case JsonType.False:
return false;
case JsonType.String:
return obj.String;
case JsonType.Array:
case JsonType.Object:
return new JsonObject(obj);
default:
return obj.Number;
}
}
The following benchmark result shows the effect of NaN Boxing. The benchmark measured parsing time in each definition of InternalObject
as a class, 20 bytes (8 + 8 + 4) structure without NaN Boxing, and 16 bytes one with NaN Boxing. The 20 bytes structure made the parser 20% faster than the class, and NaN Boxing improved 6.8% more.
Other usages of NaN Boxing
JavaScript engines such as Mozilla's SpyderMonkey and WebKit's JavaScriptCore use NaN Boxing, but Google's V8 doesn't use it. LuaJIT and mruby also use NaN Boxing. These implementations overlap a pointer with a double and compact the size of all values into 8 bytes. C# doesn't allow a managed pointer to overlap a double, so it is impossible to compact InternalObject
into 8 bytes.
Top comments (0)