Crowley's Three Axes of JSON Queryin

This is a long one, with notes on the ongoing development and re-development of crowley, some light literature review, and armchair theorizing about how to think about JSON querying as a process. Headers:

In the last month or so, I've been occupying myself with improving crowley. This has mostly involved slowing down and rethinking a lot of assumptions, hence why it does not yet have cross-platform binaries (sorry Muk! I promise I'll get to your PR soon!).

I've made a handful of optimizations that speed it up non-trivially - we're now about 3.0-3.3x faster than ijson for comparable tasks, where we were around 2.8-3.1x faster at the time of 0.1.0. But as I was tooling around with those changes, I gradually got a bit frustrated.

crowley started out pretty simple - take json-event-parser's Read implementation, take jsongrep's DFA, fuse them together, ta-da! fast streaming query engine. But combining off-the-shelf parts was leaving a lot of performance on the table, especially because json-event-parser is, by its own admission, not hyper-focused on being the fastest streaming parser possible.

But there were a lot of optimizations we could make in theory that would require entangling the parser logic with the query/DFA logic, and even implementing some of the less intrusive optimizations resulted in a tangled mess. Here's the apply_array_index_transition method for EngineState:

fn apply_array_index_transition(&mut self) { if let Some(frame) = self.stack.last_mut() && let FrameContext::Array { ref mut index } = frame.context { let current_index = *index; *index += 1;

if self.track_path { self.path.push(PathType::Index(current_index)); }

// Transition from the array frame's DFA state on this index. self.current_state = frame.dfa_state.and_then(|state| { self.dfa .get_index_symbol_id(current_index) .and_then(|sym| self.dfa.transition(state, sym)) });

// Early termination: if this transition is dead AND no future // index in this array can produce a valid transition, AND there // are no active captures being materialized, we can stop. if self.current_state.is_none() && self.active_captures.is_empty() && let Some(parent_state) = frame.dfa_state && !self.has_future_index_match(parent_state, current_index + 1) { self.try_terminate(); } } }

if self.track_path? if self.active_captures.is_empty()? if !self.has_future_index_match()? No fewer than four separate chained boolean checks? What is this stuff doing in an array transition? Why did I organize it this way?

Of course, the answer is 'because I kept getting new ideas for features/optimizations and adding them piecemeal rather than architecting them in from the start'. In fairness, I wouldn't have seen these opportunities at all without having made the first draft - but it does reinforce my belief that an iterative, Agile-style development approach requires a strong commitment to modularity and willingness to burn down and rebuild the current implementation before the unplanned feature load becomes overwhelming.

So that's what I started working on a couple weeks ago: rewriting basically all of it (except for Micah's DFA logic, which for the moment I'm treating as fragile wizardry) with my current set of features and optimizations in mind.

Of course, a complete redesign opens the door to OTHER features and optimizations, forcing me to repeat this whole process recursively up to the limit of my patience/sanity.

When I was initially sketching out what would become crowley and shopping around for a SAX-style streaming JSON parser, I spent a little while looking for SIMD implementations. I'd previously heard of, attempted to read, and then failed to understand Langdale & Lemire (2019) 'Parsing Gigabytes of JSON per Second', which impressed upon me that REALLY fast JSON parsing in the 2020s would involve SIMD.

But while some SIMD parser implementations existed for Rust, none of them were SAX-style streaming parsers. L&L's reference implementation worked exclusively on in-memory JSON with a built-in 4GB limit, because their goal was to construct an entire tree for repeated use, rather than a one-time stream access for transient queries.

Even with the current rise in RAM prices, workflows that requires parsing <4GB of JSON at a time don't require streaming, so I left it to the side.

But after working with json-event-parser, I figured, no, we could totally do SIMD parsing here - we just need to do it chunk-by-chunk, in a way that requires us to only move forward and never backtrack. The DFA already lets us do this since it never backtracks. The main problem is dealing with content that crosses chunk and buffer boundaries.

The basic process for SIMD JSON parsing goes as follows:

We take some chunk of JSON input - for the moment, let's stick to 64-byte-long chunks. Here's the sample L&L use in their paper:

{ "\"Nam[{": [ 116,"\\" , 234, "true", false ], "t":"\"" }

Valid JSON follows a few convenient rules: first, all characters OUTSIDE of strings are required to be valid ASCII, while all characters INSIDE strings are Unicode codepoints (almost always utf8). This means not ALL parsing steps need to be sequential - each individual byte can be parsed individually, in whatever order we like (including simultaneously), and the results will be valid outside of strings.

The catch, of course, is that we need a way to determine whether a given character is inside a string or not. But since double quotes " are themselves ASCII...

L&L use a series of dense bit-twiddling hacks for this purpose. This is harder than it may sound, because strings can themselves contain quotes, which are escaped with : the bit-twiddling below handles that:

(taken from Langdale & Lemire (2019) page 7)

{ "\"Nam[{": [ 116,"\\" , 234, "true", false ], "t":"\"" } : Original text

1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_ : Even bits (for bit-twiddling hacks) _1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1 : Odd bits (for bit-twiddling hacks)

1___1_____1________1____1________1____1___________1_1_1___11 : Q (naive quote locations) 111________________1111_______________________________111_ : B (Is this byte a backslash?)

1__________________1__________________________________1___ : S = B & ~(B << 1) (Is this the start of a chain of backslashes?)

1___________________ : ES = S & E (get all the slash starts that begin on an even offset) 111____________________1______________________________111_ : EC = B + ES (yields carries on backslash sequences with even starts) 1___________ : ECE = EC & ~B (filter out backslashes to get carries only) ________________________________________________________________ : OD1 = ECE & ~E (select only end of sequences ending on an odd offset)

1_____________________________________________________1___ : OS = S & O (get all the slash starts that begin on an odd offset) ___1_______________1111__________________________________1 : OC = B + OS (otherwise the same as above) ___1_____________________________________________________1 : OCE = OC & ~B ___1_____________________________________________________1 : OD2 = OCE & E

__1_____________________________________________________1 : OD = OD1 | OD2 (merge to get the ends of all odd-length sequences of backslashes) 1_________1________1____1________1____1___________1_1_1____1 : Q &= ~OD (remove escaped quotes from naive quote search) 1111111111_________11111_________11111____________11__11111 : R = CLMUL (Q ,~0) (carry-less multiplication by all 1s to find the range of strings, including the starting quote but excluding the ending quote)

All of this is branchless and works simultaneously on as many bits as you can fit into a register - the only inconvenient operation here is clmul(), the carry-less multiplication, which isn't necessarily available for wider registers, and we'll need some special handling for it later.

Now that we know the ranges of strings, we can locate our structural and 'pseudo-structural' characters.

Structural characters include {, }, [, ], ,, :, which explicitly demarcate the beginning and end of objects, the beginning and end of arrays, and separate elements and keys from values, respectively.

The paper formally defines 'pseudo-structural' characters as 'any non-whitespace character outside of strings preceded by either a structural character or whitespace'.

Usefully, these are the places where JSON atoms (strings starting from the opening ", numbers, and true/false/null literals) begin. So long as we assume that the subject is valid JSON, this actually allows us to distinguish the type of any encountered JSON atom from the first byte: strings obviously start with ", but numbers always start with either a digit or -, and the true/false/null literals all start with different characters.

(taken from Langdale & Lemire (2019) page 9)

{ " \" Nam [{": [ 116 ," \\ " , 234 , " true ", false ], "t":" \" " }: input data 1_________1________1____1________1____1___________1_1_1____1 : Q (quote locations, no longer naive) 1111111111_________11111_________11111____________11__11111_ : R (string range [)) 1_________11_1_1____1_______1____1_______1_______11____1_______1 : S (structural) 1____________1_1__________1_1____1_______1_____1__1__________1 : W (whitespace of any kind)

1 ____________1_1____1_______1____1_______1_______11____1_______1 : S = S & ~R (eliminate quoted regions from structural characters)

1 _1_________11_1____11____1_1____1_1____11_______11_1_111____1_1 : S = S|Q (restore ending quotes to pseudo-structural characters) 111 _________11111___11____1111___111____111_____11111_111____111 : P = S|W (to find pseudo-structural, first find all structural or whitespace characters) _111_________11111___11____1111___111____111_____11111_111____11 : P = P << 1 (then advance the structural-whitespace mask forward by one) _____________1_1_1__________1_1__________1_1_____11____1_______1 : P &= ~W & ~R (now eliminate remaining whitespace and quoted characters - voila, we have pseudo-structural characters!) 1 _1_________11_1_1__11____1_1_1__1_1____11_1_____11_1_111____1_1 : S = S|P (now merge pseudo-structural and structural character masks together) 1 _1__________1_1_1__11______1_1__1_1_____1_1_____11_1__11______1 : S & ~(Q & ~R) (eliminate ending quotes from the structural character list)

And look at that: for every single byte in the original 64-byte chunk, we now have a corresponding bit that indicates if that byte is an explicit control character ({, }, [, ], ,, :) or the starting point of a value. This is all computed branchlessly, with (not quite but we'll get to that later) fully local reasoning on each byte individually. It trivially scales from 64 bytes to 128, 256, 512, however large a chunk you can handle.

Having calculated this 'relevance mask' we've substantially simplified the task of JSON querying. We can navigate the JSON tree using only the structural and pseudo-structural characters: everything else is necessary for value return, but not navigation - and crucially, the DFA is capable of navigating one byte at a time.

Langdale & Lemire goes considerably further in its design, but this is where our interaction with it mostly ends - we also remove the final step above, since we actually don't want to remove ending quotes from our pseudo-structural characters: L&L do that because their scheme involves building a big tape representing the whole JSON tree and they want to save as much space as possible, but we're not constructing jack, so we actually want to keep the ending quotes.

For reference, here is a Rust implementation of the above logic operating on 64-byte chunks:

const EVENS: u64 = 0b1010101010101010101010101010101010101010101010101010101010101010; const ODDS: u64 = 0b010101010101010101010101010101010