CPU-Leistung des Unigram-Tokenizers verbessern

Wir haben unseren Unigram-Tokenizer im Rahmen eines gezielten Leistungsprojekts von Grund auf neu implementiert. Bei produktionsüblichen Eingabelängen senkt der neue Encoder die p50-Latenz um das etwa 5-Fache gegenüber der Hugging Face Tokenizers Crate, um das ca. 2-Fache gegenüber SentencePiece (C++) und um das ca. 1,5-Fache gegenüber dem IREE-Tokenizer (C), bei null Steady-State-Heap-Allokationen. In der Produktion reduzierte dies die CPU-Auslastung in unserem Inferenz-Stack um das 5- bis 6-Fache und verkürzte die Latenz der Reranker um zweistellige Millisekunden.

Die Inferenzkosten für LLMs werden meist als GPU-Arbeitslast betrachtet: KV-Caches, Attention-Kernels, Expert-Routing. Ein bedeutender Teil des produktiven Traffics läuft jedoch auf weitaus kleineren Modellen, die zwei bis drei Größenordnungen kleiner sind als führende Transformer. Embedding-Modelle, Klassifikatoren und Reranker laufen zwar weiterhin auf GPUs, aber der Forward-Pass ist kurz genug, dass das gesamte Umfeld an Bedeutung gewinnt.

Das deutlichste Beispiel ist ein Reranker, der pro Anfrage Hunderte von Kandidatendokumenten bewertet. Bei einem kleinen Modell ist die GPU-Berechnung typischerweise in niedrigen einstelligen Millisekunden abgeschlossen, aber jede Eingabe muss zunächst die CPU-seitige Tokenisierung durchlaufen, bei der Text in Vokabular-IDs umgewandelt wird. Bei großen Batches kann dies einen wesentlichen Teil der gesamten Anfrage-Latenz ausmachen.

Diese Arbeit konzentriert sich auf XLM-RoBERTa, ein Unigram-Vokabular mit 250.000 Tokens, das mit SentencePiece trainiert wurde. Feinabgestimmte Encoder der RoBERTa-Familie sind eine gängige Wahl für Ranking-, Retrieval- und Ähnlichkeitsaufgaben. Wir berichten durchgehend über die Single-Threaded-Latenz pro Kodierung; in der Produktion parallelisieren wir über Kerne hinweg unter Verwendung von rayon.

In diesem Beitrag behandeln wir die Tokenizers Crate von Hugging Face als Referenz, gegen die wir testen, da es sich um den standardmäßigen Rust-Tokenizer handelt, auf den die meisten Teams zurückgreifen. SentencePiece (C++) und IREE (C) sind zum Vergleich als die beiden anderen großen produktiven Implementierungen enthalten.

Die Unigram-Tokenisierung, 2018 von Kudo eingeführt (Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates) und in SentencePiece ausgeliefert, fasst die Segmentierung als Problem des wahrscheinlichsten Pfads auf: Jedes Vokabular-Token hat eine gelernte Log-Wahrscheinlichkeit, und der Encoder wählt die Segmentierung, deren Token-Scores die höchste Summe ergeben. Das Problem wird mit dem Viterbi-Algorithmus (1967) gelöst, wobei Byte-Positionen als Graph-Ebenen und Vokabular-Tokens als Kanten dienen, die einen zusammenhängenden Byte-Bereich überspannen. Die Rekursion ist eine eindimensionale dynamische Programmierung (DP) über Byte-Positionen:

python

best = [-inf] * (n + 1)
best[0] = 0
back = [None] * (n + 1)

for i in 0..n:
    if best[i] == -inf:
        continue
    if byte i is a UTF-8 continuation byte:
        continue

    walk the vocabulary trie from byte position i:
        for each matching token t ending at position j:
            cand = best[i] + score(t)
            if cand > best[j]:
                best[j] = cand
                back[j] = (i, token_id(t))

    if no token matched, fall back to <unk>

backtrack from position n using back[] to recover token IDs

Die äußere Schleife verläuft linear zur Eingabelänge und ist an jeder Position durch das längste Vokabular-Token begrenzt (48 UTF-8-Bytes für XLM-RoBERTa). Der innere Trie-Durchlauf ist der Hot-Path: Bei einer Eingabe mit 16.000 Tokens führt er Hunderttausende von Übergängen aus und verarbeitet pro Kodierung zig Millionen Anweisungen.

Die Tokenizers v0.22 von Hugging Face implementiert die Rekursion direkt, mit einer Hash-Map für die Rückwärtssuche und Hash-Map-Kindern an jedem Trie-Knoten:

rust

vocab:        Vec<(String, f64)>           // indexed by token ID
token_to_ids: AHashMap<String, u32>        // reverse lookup
trie:         Trie<u8>                     // byte-level prefix trie

struct Node<Label> {
    is_leaf: bool,
    children: AHashMap<Label, Node<Label>>, // heap-allocated map per node
}

Und die innere Schleife (vereinfacht) – jeder Prefix-Search-Treffer allokiert eine neue Zeichenkette und fragt dann die Hash-Map ab:

rust

fn encode_optimized(&self, sentence: &str) -> Result<Vec<String>> {
    // alloc
    let mut best = vec![BestPathNode::default(); sentence.len() + 1];

    let mut starts_at = 0;
    while starts_at < sentence.len() {
        for tok_bytes in self.trie.common_prefix_search(sentence.bytes().skip(starts_at)) {
            // alloc per match
            let token: String = String::from_utf8(tok_bytes).unwrap();
            // hash lookup
            let id = self.token_to_ids.get(&token).unwrap();
            let score = self.vocab[*id as usize].1;
            // DP update at best[starts_at + tok_bytes.len()]
            // ...
        }
        starts_at += mblen;
    }
    // backtrace into Vec<String>, one allocation per output token
}

Der Code ist lesbarer Rust-Code, aber es findet viel Arbeit statt, die auf Quellcode-Ebene unsichtbar ist. Der nächste Abschnitt schlüsselt auf, wohin die Zeit fließt.

Bevor Viterbi ausgeführt wird, durchläuft die Eingabe eine Unicode-Normalisierung (NFKC) und eine Wortgrenzenmarkierung. Profiling ergibt in unseren Szenarien einen Anteil der Vorverarbeitung an der gesamten Kodierungszeit von weniger als 5 %, weshalb wir uns im Rest des Beitrags auf den Viterbi-Forward-Pass konzentrieren.

Es gibt zwei Möglichkeiten, CPU-Code zu beschleunigen: weniger Anweisungen ausführen oder eine höhere IPC (Anweisungen pro Takt) erreichen. Cachegrind misst Ersteres, perf stat misst Letzteres. Jede Optimierung in diesem Beitrag zielt auf das eine oder das andere ab.

CPUs blockieren bei vier Dingen: Cache-Misses (L1d ~4 Zyklen, ein L3-Miss-zu-DRAM sind Hunderte), abhängige Ladeketten, die die Out-of-Order-Engine nicht parallelisieren kann, Fehlvorhersagen bei Verzweigungen (~15-20 Zyklen Leerlauf pro falscher Vermutung) und Allokator-Aufrufe. Die Implementierung der Referenz-Unigram-Engine trifft auf alle vier:

Engpass	Mechanismus	Gemessene Auswirkung
Allokation pro Treffer	String::from_utf8 auf den übereinstimmenden Bytes plus eine AHashMap-Abfrage pro Trie-Treffer; die Token-ID steht bereits im Blatt, aber die Referenz speichert sie dort nicht	7.295 Allokationen bei 512 Tokens, 14.542 bei 1k, 299.171 bei 16k
Pointer-Chasing pro Byte	Eine AHashMap an jedem Trie-Knoten, die das nächste Byte hasht und pro Schritt zwei Pointer dereferenziert; die Node-Struktur bündelt auch kalte Felder wie is_leaf, was sie bei jedem Besuch in den Cache zieht	Die L1d-Miss-Rate bleibt niedrig (~2,5 % bei 1k), da heiße Allokator-Seiten im L1 leben; die Kosten zeigen sich als Latenz bei abhängigen Ladevorgängen
L2-Thrashing bei langen Eingaben	DP-Tabelle, Prefix-Scratch und die Liste der Ausgabe-Tokens werden bei jedem Aufruf frisch allokiert	Die L2-Miss-Rate klettert von 12 % bei 128 Tokens auf 50 % bei 16k, da der kumulative Allokations-Footprint den pro Kern verfügbaren 2 MB L2 überschreitet

Referenz zu Engpässen, Mechanismen und gemessenen Auswirkungen des Tokenizers.

Die dominierenden Kosten sind die Allokationen pro Treffer. Bei 1k Tokens führt die Referenzimplementierung pro Kodierung etwa 7M Anweisungen mit einer IPC von 2,8 aus, die meisten davon bei Allokator-Aufrufen und String-Konvertierungen. L2-Misses spielen erst ab ca. 1k Tokens eine Rolle, sobald der kumulative Allokations-Footprint den Cache pro Kern übersteigt.

p50- und p99-Latenz des Referenz-Tokenizers nach Eingabegröße.

L2-Cache-Miss-Rate des Referenz-Tokenizers nach Eingabegröße.

Vom Referenz-Tokenizer pro Encode allokierte Bytes über verschiedene Eingabegrößen hinweg.

Die Allokation pro Token ist konstant: etwa 2 KB und ~18 Allokationen pro Token, unabhängig von der Eingabegröße. Die Nichtlinearität der Latenz resultiert aus dem L2: Die kumulativen Bytes überschreiten 2 MB bei etwa 1k Tokens, die Miss-Rate steigt von 8 % auf ~50 %, und die p99-Kurve krümmt sich entsprechend.

Wir vergleichen drei produktive Tokenizer, die alle denselben Unigram-Algorithmus mit demselben XLM-RoBERTa-Modell ausführen:

Engine	Sprache	Trie
Hugging Face	Rust	HashMap-Kinder Prefix-Trie
SentencePiece	C++	Darts Double-Array-Trie
IREE-Tokenizer	C	Darts Double-Array-Trie

Tokenizer-Implementierungen, Sprachen und Trie-Darstellungen, die im Vergleich verwendet werden.

Wir verknüpfen SentencePiece und IREE über direktes C/C++ FFI anstelle ihrer Rust-Wrapper; die Wrapper fügen Allokationen pro Aufruf und String-Konvertierungen hinzu, die nicht Teil der Kosten der zugrunde liegenden Bibliothek sind.

Alle Engines sind mit vollen Optimierungen (O3, natives Targeting, Link-Time-Optimierung) gebaut. Die Messungen werden an einen dedizierten, ruhenden Kern auf einem Intel Xeon Platinum 8488C gebunden. Für jede Engine und Eingabegröße sammeln wir die Wall-Clock-Latenz (p50 und p99, 10.000 Iterationen nach 1.000 Warmup-Durchläufen), die Anweisungen über Valgrind Cachegrind, IPC und Cache-Miss-Raten von perf stat Hardware-Countern sowie Heap-Allokationen, die durch einen globalen Allokator-Wrapper um das Messfenster gezählt werden.

Bei 514 Tokens (die +2 gegenüber 512 sind BOS/EOS-Injektion):

Implementierung	p50-Latenz	Anweisungen	IPC	Allokationen
Hugging Face	349 µs	3,60M	2,89	7.295
SentencePiece	128 µs	1,83M	3,39	1.559
IREE	112 µs	2,28M	3,06	1

Tokenizer-Latenz, Befehlsanzahl, IPC und Allokationen bei 514 Token.

SP und IREE liegen bei etwa einem Drittel der Latenz der Referenz. Sie führen etwa halb so viele Anweisungen aus, laufen mit höherer IPC und allokieren ein bis zwei Größenordnungen weniger.

SentencePiece und IREE verwenden beide den Double-Array-Trie, der 1989 von Aoe eingeführt wurde (Aoe, 1989; Karoonboonyanan). Der Trie ist in zwei flachen Integer-Arrays, Base und Check, kodiert:

cpp

int base[N];   // base[node] = offset for this node's children
int check[N];  // check[child] == node validates the parent-child link

Ein Kind-Lookup ist:

cpp

int next = base[node] + byte;
if (check[next] == node) { /* valid transition; child node = next */ }

Jeder Schritt des Trie-Durchlaufs benötigt nur zwei Array-Ladevorgänge, eine Integer-Addition und einen Vergleich, ohne Hashing, ohne Pointer-Chasing und ohne Heap-Allokation pro Knoten. Die Konstruktion platziert jeden Knoten so, dass seine Kinder auf freie Plätze im Validierungs-Array fallen, was es mehreren Eltern ermöglicht, Bereiche zu teilen, solange ihre Kinder sich in dem Byte unterscheiden, dem sie folgen.

Für das 250k-Vokabular von XLM-RoBERTa passt der gesamte Trie in ~9 MB zusammenhängenden Speicher (~780k Slots × 12 Bytes für Offset, Validierung und Token-ID pro Slot). Das aktive Arbeitsset einer einzelnen Kodierung liegt in der Größenordnung von 100 KB, bequem im L2, und der Hardware-Prefetcher rastet auf dem regelmäßigen Zugriffsmuster ein.

Die Referenz hingegen unterhält pro Knoten eine Hash-Map der Kinder, was etwa vier abhängige Ladevorgänge pro Byte-Schritt kostet. Byte hashen, Bucket laden, einem Pointer zum Bucket-Eintrag folgen, einem weiteren Pointer zum Kind-Knoten auf dem Heap folgen, dann dessen eigene Hash-Map für das nächste Byte konsultieren. Heap-Objekte streuen, und die meisten Ladevorgänge verpassen den Cache.

SP und IREE speichern die Token-ID direkt im Trie-Knoten. Die Referenz-Trie-Implementierung gibt nur die übereinstimmenden Bytes zurück, also muss der Encoder für jeden Treffer einen neuen String allokieren, ihn in einer Side-Hash-Map nachschlagen, um die Token-ID wiederherzustellen, und den Score aus einem separaten Vektor lesen. SP gibt die ID als gespeicherten Wert des Tries zurück und liest den Score aus einem flachen Float-Array:

cpp

// unigram_model.cc:567
const size_t num_nodes = trie_->commonPrefixSearch(
    begin, trie_results.data(), trie_results.size(),
    static_cast<int>(end - begin));

for (size_t k = 0; k < num_nodes; ++k) {
    const int   id    = trie_results[k].value;   // already in the trie
    const float score = GetScoreInlined(id);     // flat float[] indexed by id
    Lattice::Node *node = lattice->Insert(begin_pos, length);
    node->id = id;
    node->score = score;
}

IREE verwendet eine zustandsbehaftete Cursor-API, anstatt alle Treffer in einem einzigen Aufruf zurückzugeben, aber das Kostenmodell ist dasselbe: Token-IDs und Scores sind als Indizes in flachen Arrays erreichbar, ohne Allokation oder Hashing beim Trie-Durchgang selbst. IREE allokiert pro Kodierung nur einen Ausgabepuffer; SP allokiert während der DP zusätzlich einen Lattice-Knoten pro Treffer, was insgesamt etwa 1.559 Allokationen bei 514 Tokens ergibt.

Bevor wir den Trie ändern, isolieren wir die Algorithmus-Kosten von den Implementierungskosten: Wie schnell läuft die Referenz, wenn die unnötige Arbeit entfernt wird?

Die Baseline behält den Hash-Map-Kinder-Trie der Referenz bei, nimmt aber zwei Änderungen vor. Eine Scratch-Struktur in Besitz des Aufrufers enthält die DP-Tabelle, die vorverarbeiteten Bytes und die Ausgabe-Token-IDs, sodass der Hot-Path nach dem Aufwärmen keine Allokationen mehr vornimmt. Die Token-ID und der Score werden direkt im Trie-Knoten gespeichert, was die String-Konvertierung pro Treffer und die Side-Hash-Map-Abfrage entfernt.

Innere Schleife:

rust

for pos in 0..n {
    if scratch.prep[pos] & 0xC0 == 0x80 { continue; }
    let s0 = scratch.best_score[pos];
    if s0 == f32::NEG_INFINITY { continue; }

    let mut node = 0u32;
    for end in pos..n {
        let byte = scratch.prep[end];
        match self.nodes[node as usize].children.get(&byte) {
            Some(&child) => {
                node = child;
                let n = &self.nodes[node as usize];
                if n.is_terminal {
                    let total = s0 + n.score;
                    if total > scratch.best_score[end + 1] {
                        scratch.best_score[end + 1] = total;
                        scratch.best_start[end + 1] = pos as u32;
                        scratch.best_id[end + 1] = n.token_id;
                    }
                }
            }
            None => break,
        }
    }
}

Dies ist derselbe Algorithmus, mit derselben Trie-Form und demselben Zugriffsmuster, nur ohne Allokationen und ohne redundante Lookups. Ergebnisse bei 514 Tokens:

Engine	p50	Anweisungen	IPC	Allokationen
Hugging Face	326 µs	3,66M	2,86	7.295
SentencePiece	127 µs	1,81M	3,55	1.559
IREE	111 µs	1,58M	3,26	1
Baseline	156 µs	1,53M	2,62	0

Die Zero-Allocation-Baseline im Vergleich mit bestehenden Tokenizer-Implementierungen bei 514 Token.

Das Entfernen der String-Materialisierung pro Treffer und der sekundären Hash-Map-Abfrage senkt die Anweisungszahl um das 2,4-Fache gegenüber der Referenz. Die IPC sinkt mit ihnen (2,86 → 2,62), weil das Pointer-Chasing der Hash-Map, das zuvor hinter Allokator-Arbeit verborgen war, nun die dominanten Kosten pro Byte darstellt.

p50- und p99-Latenz des Referenz- und Zero-Allocation-Baseline-Tokenizers nach Eingabegröße.

L2-Cache-Miss-Rate des Referenz- und Zero-Allocation-Baseline-Tokenizers nach Eingabegröße.

Die Baseline senkt die p50-Latenz um das 2- bis 3-Fache gegenüber der Referenz bei jeder Größe, und ihre L2-Miss-Rate bleibt bei ~2-3 % bis 2k Tokens, verglichen mit den 8-48 % der Referenz. Die verbleibenden Kosten sind das Hash-Map-Pointer-Chasing, das der nächste Abschnitt behandelt.

Der Hash-Map-Trie ist ein Pointer-Chasing. SP und IREE lösen dies mit einem Double-Array-Trie (siehe vorherigen Abschnitt), und wir übernehmen dieselbe Datenstruktur. Der Unterschied besteht darin, dass SP und IREE Allzweckbibliotheken sind, die Streaming-Eingabe, Ausgabe-Offsets und mehrere Kodierungsmodi unterstützen; diese Flexibilität kostet sie zusätzliche Buchhaltung um den Trie herum (ein Lattice bei SP, eine achtstufige Pipeline bei IREE). Wir brauchen das alles nicht, also inlinen wir den Trie direkt in die Viterbi-Schleife und verwerfen den Rest.

rust

fn child(&self, node: u32, byte: u8) -> Option<u32> {
    let base = self.base[node as usize];
    let next = base + byte as i32;
    if self.check[next as usize] == node as i32 {
        Some(next as u32)
    } else {
        None
    }
}

Ein Byte-Schritt kostet zwei Array-Ladevorgänge, eine Integer-Addition und einen Vergleich. Der gesamte Trie ist etwa 9 MB groß, aber jede einzelne Kodierung durchläuft nur ~100 KB davon, sodass die heißen Daten im L2 bleiben.

Engine	p50	p99	Anweisungen	L2 Miss %	L3 Miss %
Hugging Face	327 µs	3.340 µs	3,66M	8,17 %	14,66 %
SentencePiece	127 µs	1.140 µs	1,82M	4,74 %	4,07 %
IREE	111 µs	132 µs	1,61M	5,82 %	3,87 %
Baseline	155 µs	1.170 µs	1,53M	2,59 %	16,66 %
+ Darts	68 µs	80 µs	1,10M	6,45 %	11,42 %

Tokenizer-Latenz, Anweisungen und Cache-Miss-Raten nach Einführung des Double-Array-Trie.

Die Wall-Clock-Zeit sinkt um das 2,3-Fache gegenüber der Baseline und das 4,8-Fache gegenüber der Referenz. Die Anweisungen sinken um weitere 28 % gegenüber der Baseline. Durch das Weglassen von Lattice und Pipeline können wir 1,10M Anweisungen pro Kodierung ausführen, verglichen mit 1,82M bei SP und 1,61M bei IREE bei gleicher Trie-Form; die Lücke ist die Buchhaltung, die sie für Allzweck-APIs führen, die wir nicht benötigen.

Der Darts-Trie aus Optimierung 1 benötigt zwei abhängige Ladevorgänge pro Byte-Schritt. Erst der Base-Offset des Elternteils, dann der Check-Eintrag am Kandidaten-Kind-Slot, um zu bestätigen, dass der Elternteil ihn besitzt. Der Check-Eintrag validiert nur die Eigentümerschaft. Dieselbe Frage kann durch eine Bitmap pro Knoten beantwortet werden, die aufzeichnet, welche Bytes Kinder haben. Durch die Konstruktion des Double-Array-Tries ist das Bit für Byte b in der Bitmap des Elternteils genau dann gesetzt, wenn der Kandidatenslot für dieses Byte vom Elternteil besessen wird. Die Bitmap und das Check-Array tragen dieselbe Information, daher können wir das Check-Array vollständig aus der Laufzeitstruktur entfernen.

Der Bitmap-Lookup kompiliert zu einem einzelnen Bittest gegen ein 64-Bit-Wort, der in etwa einem Zyklus läuft. Die verwandte POPCNT-Anweisung, die alle gesetzten Bits in einem Register zählt, ist das, was andere Bitmap-indizierte Trie-Designs verwenden, um einen Kind-Offset direkt aus der Bitmap zu berechnen. Wir brauchen das nicht, da die Darts-Konstruktion diesen Offset bereits im Base-Feld des Knotens speichert.

rust

#[repr(C, align(64))]
struct NodeHot {
    bitmap:   [u64; 4],     // 32 B  — "which bytes have children"
    base:     i32,          //  4 B  — child slot offset
    token_id: i32,          //  4 B  — vocab id (-1 if not terminal)
    score:    f64,          //  8 B  — Viterbi log-prob
    _pad:     [u8; 16],     // 16 B  — pad to one cache line
}

// Lookup: one cache-line load, one bit test, one add.
fn child(&self, parent: u32, byte: u8) -> Option<u32> {
    let h = &self.node_hot[parent as usize];
    if !h.bitmap.test(byte) { return None; }
    Some(h.base.wrapping_add(byte as i32) as u32)
}

Während wir dabei sind, packen wir die vier Felder pro Knoten (Bitmap, Base, Token-ID und Score) in eine 64-Byte-Cache-Zeile. Ein einzelner Knotenbesuch zieht nun alles ein: den Score und die Token-ID, die wir bei Terminal-Knoten benötigen, plus Bitmap und Base für den nächsten Schritt. Das Check-Array wird nur während der Konstruktion verwendet und aus dem Laufzeit-Layout gestrichen. Die Indizierung im Hot-Path erfolgt ohne Prüfung, da Trie-Konstruktion und Schleifenstruktur die Grenzen bereits garantieren. Der Kompromiss ist Space (Platz): Bei 64 Bytes pro Knoten × ~780k Slots wächst der Trie von ~9 MB auf ~50 MB.

Ergebnisse bei 514 Tokens:

Engine	p50	p99	Anweisungen	L2 Zugriffe	L2 Miss %	L3 Miss %
Hugging Face	327 µs	3.340 µs	3,66M	15,0K	8,17 %	14,66 %
SentencePiece	127 µs	1.140 µs	1,82M	7,5K	4,74 %	4,07 %
IREE	111 µs	132 µs	1,61M	4,7K	5,82 %	3,87 %
Baseline	155 µs	1.170 µs	1,53M	6,1K	2,59 %	16,66 %
+ Darts	68 µs	80 µs	1,10M	4,6K	6,45 %	11,42 %
+ Bitmap und Inline Packing	65 µs	77 µs	1,06M	1,8K	20,53 %	15,01 %

Tokenizer-Ergebnisse bei 514 Token nach Hinzufügen von Bitmap und Inline-Packung.

Die Wall-Clock-Zeit sinkt systematisch um weitere 4,5 % bei 514 Tokens und wächst mit der Eingabelänge, wobei sie 6-7 % bei 4k und 16k erreicht. Das Weglassen des Check-Arrays macht aus dem Trie-Schritt pro Byte zwei Cache-Zeilen-Ladevorgänge statt eines, was 2,5-mal weniger L2-Zugriffe pro Kodierung bedeutet (1,8K gegenüber den 4,6K von einfachem Darts). Die Miss-Rate springt von 6 % auf 20 %, aber das meiste davon ist der Nenner: Mit weniger als halb so vielen Zugriffen nehmen die Misses, die wir haben, einen größeren Anteil ein.

Die Trie-Daten sind etwa 50 MB groß (780.000 Knoten zu je 64 Bytes). In einem Standard-Linux-Prozess wird dieser Speicher durch 4 KB-Seiten gesichert, sodass der gesamte Trie etwa 12.000 verschiedene virtuelle Seiten überspannt, weit über das hinaus, was der Translation Lookaside Buffer der ersten Ebene der CPU aufnehmen kann (Sapphire Rapids hat 96 Einträge). Jeder Viterbi-Schritt berührt einen anderen Knoten, und bei einer Kodierung mit 512 Tokens verbrauchen wir etwa 9.000 Zyklen für Page-Table-Walks, etwa 3 % des Budgets pro Kodierung.

Die Lösung besteht darin, den Trie mit 2 MB-Huge-Pages statt 4 KB-Seiten zu sichern. Die gleichen 50 MB überspannen nun 25 Seiten, passen vollständig in den Translation Lookaside Buffer, und die Page-Table-Verzeichnisse selbst konkurrieren nicht mehr mit dem Trie um den L2-Cache.

Linux bietet zwei Möglichkeiten, Speicher mit 2 MB-Seiten zu sichern. Die opportunistische Methode sind Transparent Huge Pages (THP): Ihr Programm bittet den Kernel, einen Speicherbereich von 4 KB auf 2 MB-Seiten zu aktualisieren, und ein Hintergrund-Kernel-Thread versucht dies, wenn er Zeit und zusammenhängenden physikalischen Speicher zur Verfügung hat. Die andere Alternative besteht darin, den Trie direkt aus einem vorreservierten Huge-Page-Pool zu allokieren, den der Kernel beim Booten beiseitelegt:

rust

let raw = unsafe {
    libc::mmap(
        std::ptr::null_mut(),
        alloc_len,
        libc::PROT_READ | libc::PROT_WRITE,
        libc::MAP_PRIVATE | libc::MAP_ANONYMOUS | libc::MAP_HUGETLB,
        -1,
        0,
    )
};

Der Pool muss auf dem Host existieren (vm.nr_hugepages beim Booten gesetzt). Auf unseren Produktionsinstanzen sind 10.561 Huge Pages reserviert; der Trie verbraucht 24 davon. Nach dem mmap bestätigt /proc/<pid>/smaps den Bereich: KernelPageSize: 2048 kB, Private_Hugetlb: 49152 kB.

Der Gewinn beträgt 3–12 % Wall-Clock-Zeit über alle Eingabegrößen hinweg, konsistent und proportional zur Länge des Arbeitssets:

Tokens	Ohne Huge Pages	Mit Huge Pages	Δ
130	15,7 µs	15,2 µs	−3,6 %
514	65,4 µs	63,1 µs	−3,4 %
1.026	129,5 µs	125,3 µs	−3,3 %
4.098	773 µs	679 µs	−12,0 %
16.386	3.808 µs	3.554 µs	−6,8 %

Tokenizer-Latenz mit und ohne Huge Pages über verschiedene Eingabegrößen hinweg.

Der größte Gewinn liegt bei 4k Tokens, wo das Arbeitsset groß genug ist, dass Page-Table-Traffic aktiv mit Trie-Daten um L2-Bandbreite konkurrierte. Über 4k schrumpft der Gewinn, da L3-Misses dominieren und Page-Table-Walks einen kleineren Anteil der Gesamtzeit ausmachen.

Wenn wir die drei Optimierungen zusammenfassen, ist hier die finale Engine, gemessen gegen jeden anderen RoBERTa-Tokenizer, den wir getestet haben. Neben den nativen C++ SentencePiece- und C-IREE-Binaries haben wir auch die erhältlichen Rust-Wrapper-Crates getestet, auf die ein produktiver Benutzer zurückgreifen würde: sentencepiece und iree-tokenizer. Die sentencepiece-Crate misst eine 1,6- bis 1,9-fach höhere Latenz als die native C++-Binary bei jeder Eingabegröße, wobei der Overhead daher rührt, dass der Wrapper bei jeder Kodierung eine frische Liste von Token-Stücken allokiert, von denen jedes eine eigene Kopie des Stücktextes enthält. Die iree-tokenizer-Crate dimensioniert ihren internen Puffer auf jede Eingabe, was eine konstante Allokation pro Kodierung vermeidet, die die native IREE-Binary unabhängig von der Eingabegröße zahlt; dies ist besonders bei kurzen Eingaben wichtig, wo die Allokation ansonsten die eigentliche Tokenisierungsarbeit dominieren würde. Bei produktiven Eingabelängen amortisieren sich die konstanten Kosten, und der Overhead des Wrappers durch das Zurückkopieren von Tokens in Rust drückt seine Latenz über die der nativen Binary.

p50- und p99-Latenz pro Encode über Tokenizer-Implementierungen und Eingabegrößen hinweg.

Die finale Engine führt denselben Viterbi über dasselbe 250.000-Token-Vokabular aus, allokiert nichts auf dem Hot-Path und erzeugt token-exakte Ausgaben gegenüber der Referenz. Jeder Byte-Schritt ist nun ein einzelner 64-Byte-Cache-Zeilen-Ladevorgang, ein Bitmap-Test und eine Integer-Addition, statt einer Hash-Map-Prüfung, einem Allokator-Aufruf und mehreren Spezialfall-Verzweigungen in der Baseline-Implementierung. Die Anweisungen pro Kodierung fielen von 3,66M auf 1,04M, ein 3,5-facher Rückgang. Die Wall-Clock-Zeit entspricht diesem Verhältnis bei kurzen Eingaben und weitet sich bei langen Eingaben weiter aus, wo die Allokationen pro Token der Referenz beginnen, L2 und L3 zu überlaufen.

In der Praxis reduzierte diese Arbeit die CPU-Auslastung in der Vorverarbeitungsschicht unseres Inferenz-Stacks um das 5- bis 6-Fache und verkürzte die Reranker-Latenz um zweistellige Millisekunden.

Der Großteil der Latenzreduzierung kam durch leichtgewichtige Änderungen, die verschwendete Arbeit eliminierten: das Streichen von Allokationen pro Kodierung, das Ersetzen des Hash-Map-Kinder-Tries durch ein Double-Array und das Strippen des Overheads der generischen API. Die Verwendung der existierenden Bitmap pro Knoten als Validitätsprüfung und das Sichern des Tries mit 2 MB-Huge-Pages machten zusammen 10-20 % zusätzlich zum größeren Wechsel auf einen Double-Array-Trie aus, abhängig von der Eingabegröße.

Die erhältlichen Rust-Wrapper-Crates um SentencePiece und IREE illustrieren denselben Punkt im Umkehrschluss. Bei nativen C- und C++-Tokenizern sind die FFI-Grenze und die Allokationen pro Aufruf, die die Wrapper einführen, in den Latenzzahlen sichtbar. Der Rust-Quellcode für den finalen Viterbi-Encoder ist unter github.com/perplexityai/pplx-garden verfügbar.

Hugging Face tokenizers — https://github.com/huggingface/tokenizers

SentencePiece — https://github.com/google/sentencepiece

IREE tokenizer — https://github.com/iree-org/iree

Kudo, T. (2018). Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates. https://arxiv.org/abs/1804.10959

Viterbi, A. J. (1967). Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Transactions on Information Theory. https://en.wikipedia.org/wiki/Viterbi_algorithm

Aoe, J. (1989). An efficient digital search algorithm by using a double-array structure. IEEE Transactions on Software Engineering. https://ieeexplore.ieee.org/document/31365/

Karoonboonyanan, T. An Implementation of Double-Array Trie. https://linux.thai.net/~thep/datrie/datrie.html

POPCNT (x86) — https://www.felixcloutier.com/x86/popcnt

Huge pages — https://docs.kernel.org/admin-guide/mm/hugetlbpage.html

BibTeX

@online{perplexity2026ImprovingUnigramTokenizerCpuPerformance,
  author = {{Perplexity} and Vladimir Zaytsev and Bex Brooker and Daisy Lee and Roshan Shankar},
  title = {{Improving unigram tokenizer CPU performance}},
  date = {2026-05-20},
  url = {https://www.perplexity.ai/hub/blog/improving-unigram-tokenizer-cpu-performance}
}

Motivation

Der Viterbi-Algorithmus

Referenzimplementierung

Eine Anmerkung zur Vorverarbeitung

Wofür die Referenzimplementierung ihre Zeit aufwendet

Wie wir gemessen haben

Warum SentencePiece und IREE schneller sind: Der Double-Array-Trie

Baseline: Ein Zero-Allocation-Port der Referenz

Optimierung 1: Double-Array-Trie ohne zusätzliche Abstraktionen

Optimierung 2: Bitmap und Inline-Packen

Optimierung 3: Huge Pages für den Trie

Abschließender Vergleich

Schlussgedanken

Referenzen

Zitieren