bitcannon — GPT-family pre-tokenization as a bitstream program, replacing the scalar FSMs.
Follows Interleaved Bitstream Execution for Multi-Pattern Regex Matching on GPUs (MICRO'25, doi 10.1145/3725843.3756052). The paper's two ideas that carry over to a CPU:
- Bit-parallel regex. Compile the grammar into character-class bitstreams (one bit per input byte) plus boolean ops and carry-propagating adds. 64 input bytes are decided per 64-bit register op, branchlessly — the FSM's per-token unpredictable branch disappears.
- Interleaved execution. Do NOT run one loop per bitstream instruction over the whole
input (that is the "sequential" baseline the paper beats: every intermediate stream is
materialised and re-read). Instead fuse all instructions into ONE block-wise loop, so an
intermediate stream lives in a register for the ~100 ops it is needed and dies there. The
only thing that reaches memory is the final
startsbitmap (n/8 bytes).
The paper's third contribution (dependency-aware thread-data mapping) is a GPU concern — it resolves cross-block dependencies by recomputing them on other SMs. On one core the blocks are visited in order, so those dependencies are carried in a handful of scalar registers and, for the one genuinely backward-in-time rule, patched into the already-written bitmap.
We do not re-derive character classes: [classify] already emits one Atom tag per byte. The
builder folds those 16 atoms into a grammar-specific dense 3-bit code and extracts 3
bit-planes of it; every class stream is then a 2–3 op boolean function of the planes.
Grammars: [bitcannon_deepseek], [bitcannon_byte_level] (GPT-2), [bitcannon_cl100k]. All three
byte-exact with the oniguruma oracle over a block-phase sweep — see tests/parity.rs.