Tokenizers are a standard example of code you can’t vectorise: a loop that switches on each character, with data-dependent branches everywhere. Niles Salter has spent more than two years on an accelerated Zig parser, and at Software You Can Love Vancouver 2026 he explains why that reputation is wrong and how to write tokenizers differently. His reframing is to treat each instruction as a hardware-accelerated loop of fixed length. Once you see subtract, count-trailing-zeros and vector compaction that way, most of a tokenizer’s branching moves into a few instructions. His final version tokenizes the Zig standard library at about 2 GB/s on one core, against about 0.5 GB/s for the conventional tokenizer, and he says it’s close to going into the real Zig compiler.
Why was tokenization ever “unoptimizable”?
The talk opens with SIMD basics: one vpaddq on a ymm register does four 64-bit adds. That lowers front-end pressure (decoder, scheduler, instruction cache) and gets more work done per micro-op. Most SIMD explanations stop at SAXPY-style arithmetic, which is trivially parallel and sits at the “optimizable” end of Salter’s spectrum. Tokenization used to sit at the other end. simdjson showed parsing could run at gigabytes per second, but Salter’s question is whether people can explain why.
He answers with a puzzle. He walks through a loop of kxnorw, ktestw, kxorw and kshiftlw on AVX-512 mask registers, a bit at a time, and asks what operation it emulates. Someone guesses count-leading-zeros, which is close. The loop flips bits while they’re zero, flips the first one bit and stops. That’s what an add-with-carry chain does in hardware.
“Instead, let’s think of an instruction as a hardware-accelerated loop of a fixed size.”
The conventional tokenizer is a bit-scanning loop
A textbook tokenizer keeps a cursor, switches on the first character of each token, then loops over “continuation” characters (letters, digits, underscore for an identifier) until something else appears. Salter makes two observations. First, whether each byte is alphanumeric doesn’t depend on any other byte, so you can compute it for a whole chunk of the file at once as a bitmask. Second, the inner loop then becomes “walk a bitmask until the first zero”, which is the same loop as the opening puzzle. So it can be replaced by one subtract, or by count-trailing-zeros, cutting the branch count by up to 64×.
The win isn’t mainly skipping characters, since tokens are short. It’s branch prediction. A byte-at-a-time tokenizer makes the CPU guess the length of every token from the lengths of the previous ones. The bitmask version takes nearly all of that guessing away.
The specific trick is to shift the mask to the cursor, invert it, subtract one, and AND with the inverted value. The borrow propagates through the trailing zeros exactly as grade-school subtraction does, and leaves a mask of the bits that flipped. A popcount of that mask gives the token length, and ctz does it in one instruction. Salter stresses that the dedicated instruction isn’t what matters. He got more than a 2× speedup on a single-board computer with no hardware ctz. What matters is having primitives that carry information from the low bits to the high bits.
That “heat-seeking” tokenizer reached about 820 MB/s.
Compaction: emitting every token at once
The second primitive is compaction. Given data and a mask, keep the selected elements and pack them to the front of the register. Scalar PEXT does this for bits, and AVX-512 VPCOMPRESSB does it for 64 bytes at a time. PDEP and vector expand do the reverse.
With compaction, the tokenizer stops walking tokens and emits all of them at once. Shifting the alphanumeric mask left and right and AND-NOTing with the original gives bitmasks of token starts and token ends. Compressing the index vector 0…63 with those masks gives every start index, end index and length in the chunk with no branches. Token-kind bytes come out the same way.
Worked example: IPv4 parsing in a handful of instructions
To make it concrete, Salter goes through parsing "123.45.6.78" into a u32, which he claims is now the fastest known IPv4 parser. In outline: a masked load with bzhi and vpblendmb (fault-suppressed, so reading past the end of the buffer is safe) fills unused bytes with dots. A compare-not-equal marks digits. Shift-and-AND-NOT finds where each octet starts and ends. Two compressions give per-octet start and end indices, and their difference is each octet’s length, computed without branches. vpshufb moves each octet into its own 32-bit lane, vpshldd (a funnel shift) lines up the place-value multipliers 100/10/1, and vpdpbusd does the multiply-accumulate. One reduction then gives the answer.
The full tokenizer applies the same lane trick to keywords and multi-character operators. Candidate words are padded into separate lanes, hashed, and compared against a table in parallel.
The compacting tokenizer, in three phases
The production design has three phases. Phase one classifies every byte with a single vpermb lookup into a 128-byte table (about three cycles on Intel). The table values are chosen so that characters that can appear in multi-character operators map to 1–15, which feeds straight into a vpshufb-based DFA. Non-ASCII bytes go to a UTF-8 validator. Phase two is, in his words, “a ton of bit manipulation”: escaped characters, unescaped quotes, comment starts, and which comment, string and character-literal regions overlap, all done on bitmasks in registers rather than byte by byte. Phase three fixes up keyword and builtin kinds and writes the output.
He also argues for writing token boundaries as a bitmask instead of index arrays. The output is then source-size / 8 bytes, and the k-th token is found with select, the standard operation from succinct data structures. PDEP gives you select for 64 bits.
The first compacting version reached 1.4 GB/s on 3,253 files, against 0.51 GB/s for the legacy tokenizer on the same run.
512-bit bitstrings and VPTERNLOG
The last step was to stop treating 64 bytes as the unit. Process 512-byte chunks and keep eight 64-bit bitmasks in one zmm register, and the logic phase works on 512-bit bitstrings, as long as you can emulate AND/OR/XOR, shifts and subtract at that width. Bitwise ops get 8× fewer instructions. vpternlogq does better still: it evaluates any three-input boolean function from an 8-bit truth-table immediate, and in the common case replaces about 16 instructions. Shifts need two instructions (cross-lane valign is slow, so avoid it where you can). Subtract is the weak spot, because the borrow has to cross 64-bit lanes, and emulating it costs about as much as the scalar loop it replaces. The overall result is about 2 GB/s.
In Q&A, Salter says ARM’s 128-bit NEON isn’t a dead end. Using LD4’s interleaved loads makes movemask and its inverse cheap. Because the Zig tokenizer ships as source and is compiled on the user’s machine, CPUs without AVX-512 just get a different code path. His advice to “mortals” is to read x << 1 as “information about the previous character,” much as you would when writing GPU code.
Key takeaways
- Treat instructions such as subtract,
ctzand compress as fixed-length loops implemented in hardware. Data-dependent loops that look serial often turn out to be one of them. - Character classification doesn’t depend on neighbouring bytes, so you can compute it for a whole chunk as bitmasks and keep the serial part of tokenizing small.
- Most of the speed comes from removing branch mispredictions, not from skipping bytes. Token-length guessing is what slows conventional tokenizers down.
- Vector compaction (
VPCOMPRESSB,PEXT) turns start and end bitmasks into index arrays with no branches, so every token in a chunk is emitted at once. - Widening the logic to 512-bit bitstrings, with
VPTERNLOGhandling three-input boolean expressions, gave the last jump from 1.4 to about 2 GB/s. Multi-lane subtract is still the expensive part. - Lookup tables (
vpermb,vpshufb) can be designed so that one table’s output is a valid index into the next, which makes a SIMD DFA cheap.
Source
- Talk: “Accelerating the Zig Tokenizer (with AVX-512)”
- Speaker: Niles Salter
- Event: Software You Can Love Vancouver 2026
- Length: 49 minutes
- Video: https://www.youtube.com/watch?v=E6dWIwPLx3s
- Code: the Accelerated-Zig-Parser project (shown in the talk)