NaN Boxing in C# to realize a fast JSON parser
Tags: csharp
Published: 2020-12-09 11:53:03

This article shows how to use  NaN Boxing to improve the performance of a JSON parser for C#  named  DynaJson.

# About DynaJson

[DynaJson](http://github.com/fujieda/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.

```csharp
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](https://github.com/neuecc/Utf8Json), [Jil](https://github.com/kevin-montrose/Jil), [Newtonsoft.Json](https://www.newtonsoft.com/json), DynamicJson. The measurement ran on .NET Core 3.1 on Ubuntu 18.04 on Azure D2Ds_v4.

![benchmakr-citm-parse](https://dev-to-uploads.s3.amazonaws.com/i/ly1dfxiblsx73wthi7kg.png)

The result shows DynaJson is quite faster than others. DynaJson is optimized for this use case, so the result is natural.
<small>
citm_catalog.json is one of the files used in [Native JSON Benchmark](https://github.com/miloyip/nativejson-benchmark). Many benchmarks for JSON parsers use this file.</small>

# 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.

```csharp
[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;
}
```

![InternalObject-layout](https://dev-to-uploads.s3.amazonaws.com/i/0sr6ow7uh7kba70r0hli.png)

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](https://en.wikipedia.org/wiki/NaN) 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.

```csharp
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`.

```csharp
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.

![benchmark-nan-boxing](https://dev-to-uploads.s3.amazonaws.com/i/gi9kzteh6we3dhvc9qg7.png)

# Other usages of NaN Boxing

JavaScript engines such as Mozilla's SpyderMonkey and WebKit's JavaScriptCore [use NaN Boxing](https://brionv.com/log/2018/05/17/javascript-engine-internals-nan-boxing/), but Google's V8 [doesn't use it](https://wingolog.org/archives/2011/05/18/value-representation-in-javascript-implementations). [LuaJIT](https://luajit.org/) and [mruby](https://github.com/mruby/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.