Investigate Aho-Corasick pre-tokenization for ASCII throughput
Nobody has claimed this yet.
Assessment
- Difficulty
- 5/5
- Estimated time
- Over a week
- Newbie friendliness
- 25/100
- Issue type
- Feature
- Clarity
- Needs clarification
- Activity status
- Stale
- Tech stack
- csharp
- Domain
- performance
Research direction
Start by benchmarking CountTokens and Encode on the described ASCII-dominant inputs, then compare the Aho-Corasick approach with GitHub's bpe crate and the SIMD and pre-computed-table options. Done means selecting and implementing a viable approach that raises ASCII throughput from about 140 MiB/s toward the 300+ MiB/s goal.
Written by the indexing model from the issue text.
Description
Context
Our current throughput on ASCII-dominant text is 120-143 MiB/s (CountTokens/Encode on Python code and Bitcoin whitepaper). On cached multilingual/CJK text we reach 571 MiB/s, which is competitive with top Rust implementations.
However, GitHub's bpe crate achieves ~400-500 MiB/s on general text by using Aho-Corasick for pre-tokenization, giving it O(n) worst-case complexity vs the standard O(n²) BPE merge loop.
Goal
Close the gap on ASCII throughput from ~140 MiB/s to 300+ MiB/s.
Research areas
-
Aho-Corasick pre-tokenization — Build an Aho-Corasick automaton from the BPE vocabulary to match longest tokens in a single linear scan, bypassing iterative merge. GitHub's
bpecrate proves this approach works. -
SIMD-accelerated byte processing — Use
System.Runtime.Intrinsics(AVX2/NEON) for:- Fast ASCII detection (skip UTF-8 decode for pure ASCII runs)
- Vectorized pattern matching in the pre-tokenizer regex
- Bulk byte classification
-
Pre-computed merge tables — For common token pairs, store pre-computed merge results to skip the BPE priority queue entirely.
References
- GitHub blog: So many tokens, so little time
- GitHub rust-gems/bpe
- TokenDagger — 2-4x over tiktoken via PCRE2 JIT
- Dominant language
- C#
- Stars
- 92
- Forks
- 7
- Avg merge
- 2m
- Merged PRs (30d)
- 2
Getting set up
- No Dockerfile or Docker Compose file
- No pull request template
- Read the contributing guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Similar issues
-
Difficulty 2/5 1-3 hours Newbie friendliness 77/100
Maintainers usually reply within 1 day
-
:watch: Not Triaged advanced-concepts/subsvc dotnet-csharp/svc
Difficulty 1/5 1-3 hours Newbie friendliness 84/100
Maintainers usually reply within 1 day
-
enhancement no-stack-trace
Difficulty 2/5 1-3 hours Newbie friendliness 66/100
greenshot/greenshot#1618 · 3 comments ·
Maintainers usually reply within 1 day
-
Difficulty 2/5 1-3 hours Newbie friendliness 67/100
microsoft/aspire.dev#1962 ·
Maintainers usually reply within 1 day
-
needs-area-label
Difficulty 2/5 1-3 hours Newbie friendliness 73/100
Maintainers usually reply within 1 day