I prototyped a v128-based lexer optimization using the JSON parser in moonbitlang/core as the target. This note distills the design into a SIMD lexer pipeline that can be applied to JSON, JavaScript, and other languages.
The short version is that bitmasks are indeed the key abstraction. However, the main opportunity is not matching CST node kinds after construction. It is classifying input bytes and extracting only the positions where lexical context can change.
A typical pipeline can be decomposed as follows:
UTF-8 bytes
↓
1. classify
↓
character-class bitmaps
↓
2. context carving
↓
context-corrected bitmaps
↓
3. coalesce
↓
token-start / token-kind bitmaps
↓
4. compress
↓
flat token positions + kinds
↓
5. unfused parser
The goal is not to interpret the entire grammar directly with SIMD.
SIMD broadly enumerates what each byte might be. A small scalar state machine then processes only the sparse positions that can change context. Finally, mask operations eliminate invalid candidates in bulk.
Load 16 bytes at a time and classify every lane in parallel.
For JSON, the minimum useful set of masks is:
quote : "
backslash : \
structural : { } [ ] : ,
whitespace : space tab LF CR
control : byte < 0x20
The result is not yet a token stream. It is a bitmap for each character class.
input: { "x": [1, 2] }
quote: 1 1
structural: 1 1 1 1 1 1
whitespace: 1 1 1 1
ASCII punctuation can be classified with a two-table nibble lookup: use i8x16.swizzle on a 16-entry low-nibble table and a 16-entry high-nibble table, then intersect the results.
class(byte) = lo_table[byte & 0x0f]
& hi_table[byte >> 4]
This scales better than adding more independent comparisons as the number of character classes grows.
Classification is context-free. In the following JSON, it therefore marks ] } , inside the string as structural candidates too:
{"text": "not ] } , structural"}Context carving takes these broad candidate masks, cuts out spans such as strings, comments, and regular expressions, then removes or reclassifies candidates that are impossible in that context.
For JSON, this consists of:
- Enumerating only the events in
quote | backslash - Tracking the parity of each backslash run
- Retaining only unescaped quotes
- Computing
inside_stringwith a prefix XOR over the quote mask - Removing structural candidates inside strings
Conceptually:
inside_string = prefix_xor(unescaped_quotes)
real_structural = structural & ~inside_string
A standard bit-enumeration loop is useful here:
while mask != 0:
lane = ctz(mask)
process(lane)
mask &= mask - 1
Ordinary bytes do not branch one by one. Only characters capable of changing state, such as quotes and backslashes, are processed.
Instead of tokenizing the whole input sequentially, the algorithm cuts exceptional lexical contexts out of the complete set of candidates as masks:
all candidates
├─ ordinary code
├─ string spans
├─ line/block comment spans
├─ regex spans
├─ template literal spans
└─ JSX spans
In JavaScript, for example, classification can only identify / as a slash candidate:
a / b // division
/foo/.test(x) // regexp
// comment
/* comment */Context carving uses the lexer mode and surrounding state to determine the span, then invalidates operator, identifier, or punctuation candidates inside it, or replaces them with context-specific kinds.
This does not mean parsing a context-sensitive language entirely with SIMD. It means performing broad context-free candidate generation with SIMD, then reducing context-sensitive decisions to sparse event processing.
Immediately after classification, we only know that individual bytes resemble digits, word characters, or operator characters.
Coalescing groups adjacent candidates:
1 2 3 . 4 5 → number candidate
f o o _ 1 → identifier candidate
> > = → operator candidate
t r u e → keyword candidate
For JSON, this stage finds the starts of numbers and the literals true, false, and null. JavaScript adds identifiers, keywords, and multi-character operators.
The final bitmap representation is compressed into flat arrays suitable for the parser:
positions : Array[UInt32]
kinds : Array[Byte]
Storing positions and kinds in contiguous arrays is more cache-friendly than allocating a boxed object for every token. Lookahead is cheap as well.
The parser no longer has to restart the lexer each time it requests a token. It can inspect kinds[i + 1] or kinds[i + 2] directly. This unfused lexer/parser contract can be as important as SIMD classification itself.
Bitmasking CST node kinds can still help with tree traversal or set-membership checks inside a parser.
But once a CST exists, the system has already paid for:
- Sequentially scanning the input
- Branching on tokens
- Allocating nodes
- Constructing source ranges and child arrays
That is too late to provide the main lexer speedup.
The more useful design is to represent kinds as small integers in a flat token stream before CST construction, reducing parser branches and making lookahead cheap. The most valuable bitmasks describe input positions, character classes, and token candidates—not already constructed nodes.
The existing API in moonbitlang/core/json accepts parse(StringView), which means UTF-16 input. The current v128_load operates on byte arrays, so the UTF-16 prototype had to gather eight scalar lanes to construct each vector.
Under this constraint, a fully SIMD-classified UTF-16 lexer pipeline could not recover its classification overhead. A narrower scanner, however, worked well: it searched long JSON strings only for quotes, backslashes, and control characters.
The production-oriented prototype therefore uses a hybrid scanner:
short string:
scalar scan
long ordinary string:
scalar prefix
→ v128 special-character scan
→ scalar tail
escape/control encountered:
existing slow path
The following are preliminary measurements from one machine. Runtime load causes noticeable variation, so the trend matters more than the absolute values.
| Workload | Scalar | SIMD | Speedup |
|---|---|---|---|
| Special-character scan over 65,536 UTF-16 code units / native | 71.6 µs | 12.7 µs | 5.6x |
| Same / wasm | 85.6 µs | 32.5 µs | 2.6x |
| Parsing a JSON array of 1,000 long strings / native | 1.28 ms | 0.399 ms | 3.2x |
| UTF-8 token-start pipeline / native | ~182 µs | 102–118 µs | 1.5–1.8x |
For typical JSON dominated by short strings, performance was roughly neutral, with small regressions of a few percent in some runs. The full UTF-8 pipeline was also about 11% slower than scalar on wasm at this stage, so it was not connected to the production parser.
To make a simdjson/Oxc-style pipeline effective for MoonBit JSON, the input contract should change as well:
- Add
parse_utf8(Bytes/BytesView) - Generate structural positions and a flat token tape in stage 1
- Build
Jsonin stage 2 while retaining slices into the original bytes - Decode and unescape only strings that require it
- Optionally expose a lazy or tape-based API alongside the tree API
The current Json API ultimately allocates String, Array, and Map values. Once lexing becomes faster, allocation, string materialization, and number conversion become dominant. A large end-to-end improvement therefore requires a combination of SIMD classification, a flat token contract, lazy decoding, and a low-allocation representation—not a single SIMD trick.
The core SIMD lexer pattern is:
- Classify broadly: generate candidates without context
- Carve sparsely: process only the few events that change state
- Filter with masks: eliminate contextually impossible candidates in bulk
- Compress flatly: pass cache-friendly position and kind arrays to the parser
Bitmasks are not merely a faster way to switch on node kinds. Their more important role is to represent the input so that most of it can be discarded as “nothing interesting happens here,” reducing the amount of information that must be handled sequentially.