Skimming Over JSON

When running long-lived WebSocket connections with potentially hundreds of events per second, every byte of memory you can save is crucial. The native JSON.parse function is already blazing fast, but by design it loads the entire document into memory. No matter how much of the object you're actually using. My solution to this problem was to create a lazy JSON parser library.

Lazy?

The core feature of the library is it will not parse a key until you want it. Let's look at an example to best demonstrate this functionality.

import LazyObject from "json-skim";
 
const json = '{ "foo": "bar", "baz": "qux", "obj": { "nested": true } }';
const doc = new LazyObject(json);
 
doc.get("foo"); // => "bar"

The only part of the input JSON that gets parsed into a variable is the foo value. The library iterates over the input string, and skips unused branches of the tree. After the value is found it immediately quits consuming.

Skip to my foo

Stripping out chunks of unused branches in the tree turned out to be one of the core functions of the whole implementation.

Skipping a primitive is easy. For a string, find its closing quote. For a number, consume its numeric characters. For true, false, and null, we already know their lengths.

Objects and arrays are more interesting because they can contain arbitrarily nested values.

So skipValue can infer and delegate skips based on the first character:

function skipValue(s: string, pos: number): number {
  switch (s[pos]) {
    case "{":
      return skipObject();
    case "[":
      return skipArray();
    case '"':
      return skipString();
    case "t":
      return pos + 4;
    case "f":
      return pos + 5;
    case "n":
      return pos + 4;
    default:
      return skipNumber();
  }
}

The important distinction is that these functions only return pointers instead of values. One downside of the design is that it preemptively makes assumptions about values, which may be incorrect for corrupted documents.

Here's an example of how it would roughly look to extract the last key:

{
  "small": 1, // ╶ Skipped
  "big": {
    // ┌ Skipped
    "nested": {
      // │
      "data": [1, 2, 3, 4] // │
    } // │
  }, // └
  "world": "hello" // ╶ Found
}

The parser still has to inspect the characters inside big to know where that object ends, but it never turns any of them into JavaScript values or validates the keys, it just looks for the closing bracket.

Pointing at objects

Once I had a reliable way of finding the start of a value, the next step was to stop thinking of nested objects as values at all.

If the requested value is itself an object, we don't need to parse that object either. We can return another view into the original string.

if (c === "{" || c === "[") {
  return new LazyObject(s, pos);
}

This means that new LazyObject objects don't need to contain the value, merely a pointer to the start position for children to start scanning at.

const obj = doc.get("obj"); // => LazyObject
obj.get("nested"); // => true

Get into it

for (const seg of path) {
  if (typeof seg === "number") {
    pos = searchArray();
  } else {
    pos = searchObject();
  }
}

At each level, it searches only the structure necessary to find the next segment. The parser doesn't have to understand the entire document. It merely repeatedly narrows its search.

doc.get("foo", "bar", 2, "name"); // => string
// root
// └ foo
//   └ bar
//     └ [2]
//       └ name

There was an important optimization hiding in this design, too: stop consuming as soon as an indicator for the target is found.

If "foo" is the first property in a 10 MB document, get("foo") doesn't need to scan the remaining 9.99 MB. Once searchObject returns a pointer to the value, LazyObject#get can parse that one value and return immediately.

As such, the speed is entirely dependent on the order of the JSON. During testing, results spanned from ~40x to ~3x faster than using JSON.parse depending on whether the order was optimized.

One scanner to rule them all

Suppose the caller wants to get the message content, author name, and timestamp from the following event:

{
  "type": "MESSAGE_CREATE",
  "data": {
    "id": 0,
    "content": "Hello, world",
    "author": { "id": 0, "name": "Alice" }
  },
  "timestamp": "1970-01-01"
}

It would be inefficient to run three independent LazyObject#get calls, as that means walking overlapping portions of the document multiple times. To get to timestamp, we must first have passed data.content.

To do this, you can pass the paths you want to LazyObject#multi which will compile them into a single tree for the iterator to check as it consumes the document.

doc.multi({
  text: ["data", "content"],
  author: ["data", "author", "name"],
  timestamp: ["timestamp"],
});

root
├ data
│ ├ content   => text
│ └ author
│   └ name    => author
└ timestamp   => timestamp

Precompiling

If you will reuse the same query many times, it may be faster to call the exported compileQuery function and pass the value it returns into LazyObject#multi so it doesn't have to compile each time.

After compiling, the JSON structure and query structure now mirror each other. Only one scanner is needed to traverse the document and exit once all the values are discovered.

When the scanner encounters "data", it knows immediately that there are two things it might want from that object. It can descend into data once and collect both values during the same pass.

I want to stress that this isn't a faster replacement for JSON.parse in every situation. If you actually need the entire document, JSON.parse is still exactly what you want.

This library's most useful case is the opposite case: enormous JSON payloads where the consumer only needs a small fraction of the data.

https://npmjs.com/json-skim