# TokenBpe A editorial on how tokenizers can be sped up. > Source: > Published: 2026-11-15 14:44:55+00:00 Every LLM pipeline starts with a tokenizer and almost no one thinks about it. The model gets the headlines, the tokenizer is quietly burning microseconds per token per request, forever. If you're serving millions of requests or just training on a corpus that doesn't fit in memory that "quietly" adds up. This post is a walk through TokenBpe, a BPE tokenizer that I've written from the ground up in C++20. It covers what the various components are, how each one works, what specific techniques give you a performance gain and why. All of this is based on the actual code (include/tokenizer/, src/, utils/) and the benchmark figures are from a properly audited 3 way comparison against OpenAI's tiktoken (Rust) and Hugging Face tokenizers. **Headline numbers** (Shakespeare corpus, 1.06 MB, GPT-2 vocabulary, 12 hardware threads, Intel i5-11260H): | Operation | TokenBpe | tiktoken | HF tokenizers | |---|---|---|---| | Encode, 12T (zero-copy) | **239.98 MB/s** | 45.83 MB/s | 12.08 MB/s | | Encode, 1T | **34.22 MB/s** | 11.55 MB/s | 2.11 MB/s | | Decode, 1T (zero-copy) | **341.01 MB/s** | 117.34 MB/s | 24.93 MB/s | ~5.2× tiktoken and ~19.9× HF on 12-thread encoding. And ~6.1× scaling from 1 to 12 threads natively. Let's open the hood. BPE encoding has two phases: Decoding is trivial really: just map each token id to its bytes and concatenate. The naive implementation of this is fine. The real question is where the time goes and the answer, as ever, is everywhere, a little bit at a time. So TokenBpe attacks every layer: ``` text ─▶ SWAR pre-tokenizer ─▶ dual-cursor split ─▶ per-thread cache ─▶ linked-list merge ─▶ token ids ``` with a persistent thread pool under the whole thing, a flat binary model format and a zero copy NumPy boundary on top. **The technique.** SWAR (SIMD Within A Register) does the 8 bytes per 64 bit word classification using pure integer arithmetic. No SSE/AVX intrinsics at all, it's all done in the 64 bit ALU. ``` // swar.hpp (simplified) // All 8 lanes are bytes; HIGH_BITS is OR'd in before subtracting // min so no lane can borrow from its neighbour. bool all_bytes_in_range(uint64_t v, uint8_t min, uint8_t max); bool all_ascii_lower(uint64_t v); // [a-z] bool all_ascii_upper(uint64_t v); // [A-Z] bool all_ascii_letters(uint64_t v); // both, via v | 0x20 bool all_ascii_digits(uint64_t v); // [0-9] bool all_bytes_equal(uint64_t v, uint8_t b); ``` The range check is written very carefully indeed: it rejects the high bit bytes first, then ORs in HIGH_BITS prior to subtracting min, so a lane can never borrow from its neighbour. load64 does an unaligned 64-bit load via memcpy which ends up as a single instruction. The splitter (`pre_tokenizer.hpp`) then scans: `all_bytes_equal`;`'s`, `'t`, `'m`, `'d`, `'re`, `'ve`, `'ll`; And crucially next_token() returns a std::string_view into the original buffer. No pre-token is ever materialised as a string. The caller owns the text lifetime, the splitter just points into it. **The speed payoff.** Byte classification goes from one branch per byte to one instruction per eight bytes for the majority of the scan. No regex engine is actually invoked at all. The only caveat here is that it's an approximation of GPT-2's regex (exotic Unicode whitespace can have different effects on splitting), which is why the token counts on the Shakespeare corpus differ by ~1.9% from tiktoken. Roundtrips are always exact though. **The problem**. Pre-tokenising left to right is a single dependency chain: scan, emit, scan, emit. The CPU can't get ahead of itself as each step is dependent on where the last one left off. **The technique.** `dual_cursor.hpp` finds a safe split point a space or newline within ±128 bytes of the midpoint, searching backwards first (inputs under 256 bytes aren't split) and runs **two `LexerCursor` s alternately in one fused loop**: ``` // dual_cursor.hpp — sketch find_safe_split_boundary(text); // near midpoint, whitespace-aligned LexerCursor a{begin, split}, b{split, end}; while (a.has_more() || b.has_more()) { if (a.has_more()) emit(next_token(a), out_a); if (b.has_more()) emit(next_token(b), out_b); } ``` Each cursor's dependency chain is independent so the superscalar core has two instruction streams to work on. Output order is preserved by writing the first half into out_a and the second half into out_b and then concatenating. **What it is NOT:** threading. It's a fused, allocation-free iteration that also eschews the need to materialise a std::vector[std::string_view] of pre-tokens. **The technique.** `encode_chunk_uncached_to_buffer()` (the heart of `src/encoder.cpp`) represents the pre-token as a thread-local array of nodes: ``` struct ListNode { TokenId token; int32_t prev; int32_t next; }; ``` The algorithm: `merge_ranks_`, keep the one with the globally lowest rank (not the first one encountered, training order takes priority regardless of position). If none, stop. **The speed payoff.** No string allocations at all during merging, ever. The merged bytes were already computed by add_merge() when the model was built. The cost is an O(n) scan per merge and for pre-tokens (which are almost always very short) that's a very reasonable trade. This is also where the TokenPairHash comes in: a splitmix64 style mixer on first << 32 | second, giving us unordered_map lookups that won't pathologically collide. **The technique.** Each thread gets an 8 192-slot, direct-mapped cache: ``` static_assert(sizeof(CacheSlot) == 64); // exactly one cache line // slot = fnv1a64(word) & 0x1FFF // slot = { hash, word_len, token_count, char word[22], TokenId tokens[8] } ``` **The speed payoff.** A cache hit bypasses the scratchpad, the list construction, the merge scans and the hash-map probes of the pair table it's just a single line lookup and a bulk insert. The 512kib/thread footprint remains in L2 on most cores. Decoding looks up `decode_table_[id].size()` to get the total output size, calls `resize()` once and then `memcpy` s each token's bytes forward. The table is id-indexed so decode never touches a hash map. Any ids outside the table are silently skipped (a corrupt stream just degrades rather than aborting). Result: 341mb/s, ~2.9x tiktoken, ~13.7x HF. Spawning a thread per batch kills you twice: on thread creation and on cold thread local state. TokenBpe uses a PersistentThreadPool: `hardware_concurrency() - 1` workers **plus the calling thread**, work distributed via a shared atomic cursor (`fetch_add`) a dynamic schedule with no per-item queue. The workers keep their TokenCache and ThreadScratchpad warm across calls for the life of the process. Batches go through parallel_tokenize_flat() which returns a single contiguous token array plus a prefix sum offsets array (a FlatBatch) such that chunk i is in tokens[offsets[i] .. offsets[i+1]]. No per-chunk vectors, no copies. Honest limitation: one shared task slot, non-reentrant, `threads` parameter is advisory. It's a very simple pool really, does one thing and does it well. `tolist()` The nanobind FFI (in utils/bindings.cpp) is where the vast majority of the "fast" tokenizers just quietly fall apart, they're fast at computing, then they copy everything into Python objects. TokenBpe: `encode_flat` / `encode_batch_flat` as `numpy.uint32` ndarrays whose `std::vector` is moved to the heap and owned by an `nb::capsule` — ownership transfers to NumPy, no Measured effect: ndarray encode at 239.98 MB/s vs 137.40 MB/s for the equivalent `list[list[int]]` path **1.75x purely from the boundary**. `save()`/` load()` use a compact, order-independent binary: ``` Header : magic "BPE1" | version u8 | vocab_size u32 | merge_count u32 Vocabulary : vocab_size × { id u32 | len u32 | bytes[len] } Merges : merge_count × { left u32 | right u32 | rank u32 | result u32 } ``` Load validates magic/version, clears all tables **and the thread-local cache**, then rebuilds `byte_to_token_id` (from length-1 vocab entries essential for imported GPT-2, whose byte tokens are permuted), `merge_ranks_`, and the flat decode table. A 50 257-token / 49 992-merge GPT-2 model is ~1.5 MB and loads in microseconds. There's also a trainer (frequency-weighted, recompute-based, deliberately simple) and a Hugging Face importer (`convert_hf_to_bpe.py`) that reverses GPT-2's byte-to-unicode map. Every technique maps to a specific cost it eliminates: | Technique | Eliminates | |---|---| | SWAR pre-tokenization | Regex engine overhead; 8× fewer classification steps | | `string_view` pre-tokens | String materialization + allocator traffic | | Dual cursor | Single dependency chain; enables ILP | | Linked-list merge | O(n²) vector erase-and-shift; string building | | Global lowest-rank selection | Correctness of merge priority (a subtle bug source, not just speed) | | Direct-mapped 64 B cache | Scratchpad setup + merge work for common pre-tokens | | Thread-local scratchpad/cache | Cross-thread synchronization + allocation | | Persistent pool + atomic cursor | Thread spawn cost; queue allocation | | Flat decode table + single `resize` | Hash lookups; multiple allocations | | Flat batch + prefix-sum offsets | Per-chunk vector overhead | | Zero-copy ndarray + GIL release | Python object overhead; interpreter serialization | | `BPE1` binary model | Parse overhead at load time | | `-O3 -march=native -flto` | The compiler's chances to help | The big lesson: **no single trick wins**. The speedup is the product of a dozen multiplicative factors, boundary copies, allocations, cache misses, dependency chains, each small, all compounding. `RAYON_NUM_THREADS` to the C++ pool's thread count.`fast_bpe` and `tiktoken` ``` fast_bpe (C++20) Encode 12T 239.98 MB/s 74.80 Mtok/s zero-copy ndarray fast_bpe (C++20) Encode 12T 137.40 MB/s 42.83 Mtok/s Python list[list[int]] tiktoken (Rust) Encode 12T 45.83 MB/s 14.56 Mtok/s HF tokenizers Encode 12T 12.08 MB/s 3.84 Mtok/s fast_bpe (C++20) Decode 1T 341.01 MB/s 106.30 Mtok/s zero-copy ndarray ``` Native C++ suite: 41.81 MB/s single-threaded → 254.88 MB/s on 12 threads = **6.10×** scaling. (Not a perfect 12× memory bandwidth and the single split point in the dual cursor, among other things.) Caveats to state in the post: the pre-tokenizer is an approximation (~1.9% fewer tokens on this corpus), roundtrips are exact, and `fast_bpe` vs tiktoken is not a byte-identical id comparison. ``` git clone && cd BPE_Tokenizer python -m venv .venv && source .venv/bin/activate pip install nanobind numpy # optional, for the 3-way benchmark: pip install tiktoken tokenizers cmake -S . -B build cmake --build build -j ctest --test-dir build --output-on-failure # 10 tests, 52 assertions ``` Artifacts in `build/`: `libbpe_core.a`, `tokenizer_cli`, `tokenizer_bench`, `tokenizer_tests`, `fast_bpe.*.so`. ``` python utils/convert_hf_to_bpe.py \ --vocab gpt2_tokenizer/vocab.json \ --merges gpt2_tokenizer/merges.txt \ --out gpt2.bpe python import sys sys.path.append("./build") import fast_bpe enc = fast_bpe.BpeEncoder() enc.load("gpt2.bpe") enc.encode("Hello, world!") # -> list[int] enc.encode_flat("Hello, world!") # -> numpy.uint32 ndarray (zero-copy) tokens, offsets = enc.encode_batch_flat(["line 1", "line 2"]) # chunk i -> tokens[offsets[i]:offsets[i+1]] enc.decode(tokens) # -> str # MUST run from repo root .venv/bin/python benchmark.py --chunk-kb 64 --warmup 3 --runs 9 ./build/tokenizer_bench ``` *Built with C++20, nanobind, Catch2. Code, benchmarks, and the audited comparison script are in the repo.*