Îmbunătățirea performanței CPU a tokenizatorului Unigram

Am reimplementat tokenizatorul nostru Unigram de la zero ca un proiect axat pe performanță. La lungimi de intrare de producție, noul codificator reduce latența p50 cu aproximativ 5× față de lada cu tokenizatoare Hugging Face, cu ~2× față de SentencePiece (C++) și cu ~1.5× față de tokenizatorul IREE (C), fără nicio alocare în heap în regim staționar. În producție, acest lucru a redus utilizarea CPU în stiva noastră de inferență de 5-6× și a redus cu milisecunde de ordinul zecilor latența rerankerului.

Costul de inferență LLM este de obicei prezentat ca fiind o sarcină GPU: cache-uri KV, nuclee de atenție, rutare pentru experți. Cu toate acestea, o porțiune semnificativă din traficul de producție rulează pe modele mult mai mici, cu două până la trei ordine de mărime mai mici decât transformatoarele de frontieră. Modelele de embedding, clasificatorii și rerankerele rulează în continuare pe GPU, dar pasul de forward este suficient de scurt încât tot ce este în jur începe să conteze.

Cel mai clar caz este cel al unui reranker care evaluează sute de documente candidate per cerere. Cu un model mic, calculul GPU se termină de obicei în câteva milisecunde, dar fiecare intrare trebuie totuși să treacă mai întâi prin tokenizarea pe partea de CPU, transformând textul în ID-uri de vocabular. Când lotul este mare, acest lucru poate reprezenta o fracțiune semnificativă din latența totală a cererii.

Această lucrare vizează XLM-RoBERTa, un vocabular Unigram de 250K tokenuri antrenat cu SentencePiece. Codificatorii din familia RoBERTa fin-acționați sunt o alegere comună pentru sarcinile de clasificare, regăsire și similitudine. Raportăm latența per-codificare cu un singur fir de execuție în întregul articol; în producție paralelizăm pe mai multe nuclee folosind rayon.

În această postare, tratăm lada cu tokenizatoare a Hugging Face ca referință față de care facem benchmark, deoarece este tokenizatorul Rust implicit pe care majoritatea echipelor îl aleg. SentencePiece (C++) și IREE (C) sunt incluse pentru comparație ca celelalte două implementări majore de producție.

Tokenizarea Unigram, introdusă de Kudo în 2018 (Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates) și livrată în SentencePiece, formulează segmentarea ca o problemă a celui mai probabil drum: fiecare token din vocabular are o log-probabilitate învățată, iar codificatorul alege segmentarea ale cărei scoruri de token adunate dau cea mai mare valoare. Problema este rezolvată cu algoritmul Viterbi (1967), având pozițiile de octeți ca straturi de grafic și tokenurile de vocabular ca muchii care acoperă un interval de octeți contiguu. Recurența este o programare dinamică unidimensională peste pozițiile de octeți:

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

Bucla exterioară este liniară în funcție de lungimea intrării, fiind limitată la fiecare poziție de cel mai lung token din vocabular (48 de octeți UTF-8 pentru XLM-RoBERTa). Parcurgerea interioară a trie-ului reprezintă calea critică: pe o intrare de 16k tokenuri, execută sute de mii de tranziții și finalizează zeci de milioane de instrucțiuni per codificare.

Tokenizatoarele tokenizers v0.22 ale Hugging Face implementează recurența direct, folosind o mapă hash pentru căutarea inversă și copii-mapă hash la fiecare nod din trie:

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
}

Iar bucla interioară (simplificată) – fiecare potrivire din căutarea de prefix alocă un șir nou și apoi interoghează mapa hash:

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
}

Codul este scris în Rust citeț, dar se realizează o mulțime de muncă care este invizibilă la nivelul sursei. Secțiunea următoare detaliază unde se duce timpul.

Înainte ca Viterbi să ruleze, intrarea trece prin normalizare Unicode (NFKC) și marcare a limitelor de cuvinte. Profilarea plasează preprocesarea la sub 5% din timpul total de codificare în scenariile noastre, așa că ne concentrăm pe pasul de forward Viterbi pentru restul postării.

Există două moduri de a accelera codul CPU: executarea a mai puține instrucțiuni sau obținerea unui IPC mai ridicat. Cachegrind măsoară prima variantă, perf stat o măsoară pe a doua. Fiecare optimizare din această postare se încadrează în una sau cealaltă.

Procesoarele stagnează din patru motive: miss-uri de cache (L1d ~4 cicluri, un miss L3 către DRAM înseamnă sute), lanțuri de încărcări dependente pe care motorul out-of-order nu le poate paraleliza, predicții greșite ale ramurilor (~15-20 de cicluri evacuate per ghicire greșită) și apeluri către alocator. Implementarea de referință a motorului unigram le atinge pe toate patru:

Blocaj	Mecanism	Impact măsurat
Alocare per potrivire	String::from_utf8 pe octeții potriviți plus o căutare AHashMap per potrivire în trie; ID-ul tokenului se află deja în frunză, dar referința nu îl stochează acolo	7.295 alocări la 512 tokenuri, 14.542 la 1k, 299.171 la 16k
Urmărire de pointeri per octet	Un AHashMap la fiecare nod din trie, aplicând hashing pe următorul octet și dereferențiind doi pointeri per pas; structura Node grupează de asemenea câmpuri reci precum is_leaf, trăgându-le în cache la fiecare vizită	Rata de miss L1d rămâne scăzută (~2,5% la 1k) deoarece paginile active ale alocatorului locuiesc în L1; costul apare sub formă de latență a încărcărilor dependente
Thrashing L2 pe intrări lungi	Tabelul DP, zona de lucru pentru prefix și lista de tokenuri de ieșire sunt toate alocate din nou la fiecare apel	Rata de miss L2 crește de la 12% la 128 de tokenuri la 50% la 16k pe măsură ce amprenta cumulativă a alocărilor depășește memoria L2 de 2 MB per nucleu

Referință pentru blocajele tokenizerului, mecanismele și impacturile măsurate.

Costul dominant este alocarea per potrivire. La 1k tokenuri, implementarea de referință finalizează aproximativ 7M de instrucțiuni per codificare la un IPC de 2,8, cele mai multe dintre ele în apeluri de alocare și conversii de șiruri. Miss-urile L2 contează doar după ~1k tokenuri, odată ce amprenta cumulativă a alocărilor depășește cache-ul per nucleu.

Latenta p50 și p99 a tokenizerului de referință în funcție de dimensiunea intrării.

Rata de erori L2 cache a tokenizerului de referință în funcție de dimensiunea intrării.

Octeți alocați per encodare de către tokenizerul de referință, pe diferite dimensiuni de intrare.

Alocarea per token este constantă: aproximativ 2 KB și ~18 alocări per token, indiferent de dimensiunea intrării. Nelinearitatea latenței provine din L2: octeții cumulați depășesc 2 MB în jur de 1k tokenuri, rata de miss crește de la 8% la ~50%, iar curba p99 se curbează în consecință.

Comparăm trei tokenizatoare de producție, toate rulând același algoritm Unigram împotriva aceluiași model XLM-RoBERTa:

Motor	Limbaj	Trie
Hugging Face	Rust	Trie cu prefix și copii HashMap
SentencePiece	C++	Trie cu tablou dublu Darts
Tokenizator IREE	C	Trie cu tablou dublu Darts

Implementări ale tokenizerului, limbaje și reprezentări trie folosite în comparație.

Conectăm SentencePiece și IREE prin FFI direct C/C++ în loc de wrapper-ele lor în Rust; wrapper-ele adaugă alocări per apel și conversii de șiruri care nu fac parte din costul bibliotecii de bază.

Toate motoarele sunt construite cu optimizări complete (O3, targetare nativă, optimizare la timpul de link-uire). Măsurătorile rulează fixate pe un singur nucleu silențios pe un Intel Xeon Platinum 8488C. Pentru fiecare motor și dimensiune de intrare colectăm latența wall-clock (p50 și p99, 10.000 de iterații după 1.000 de încălziri), instrucțiuni finalizate prin Valgrind cachegrind, ratele de miss IPC și cache din contoarele hardware perf stat, și alocările în heap contate de un wrapper de alocator global în jurul ferestrei măsurate.

La 514 tokenuri (+2 peste 512 reprezintă injecția BOS/EOS):

Implementare	Latență p50	Instrucțiuni	IPC	Alocări
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

Latenta tokenizerului, numărul de instrucțiuni, IPC și alocările la 514 tokenuri.

SP și IREE se situează la aproximativ o treime din latența referinței. Ele finalizează aproximativ jumătate din numărul de instrucțiuni, rulează la un IPC mai ridicat și alocă cu unu-două ordine de mărime mai puțin.

SentencePiece și IREE folosesc ambele trie-ul cu tablou dublu introdus de Aoe în 1989 (Aoe, 1989; Karoonboonyanan). Trie-ul este codificat în două tablouri de întregi plate, base și check:

cpp

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

O căutare de copil este:

cpp

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

Fiecare pas al parcurgerii trie-ului necesită doar două citiri din tablou, o adunare de întregi și o comparație, fără hashing, fără urmărire de pointeri și fără alocare în heap per nod. Construcția plasează fiecare nod astfel încât copiii să cadă pe sloturi libere din tabloul de validare, permițând mai multor părinți să partajeze regiuni atât timp cât copiii lor diferă prin octetul pe care îl urmează.

Pentru vocabularul de 250K al XLM-RoBERTa, întregul trie încape în ~9 MB de memorie contiguă (~780K sloturi × 12 biți/octeți pentru offset, validare și ID-ul tokenului per slot). Setul de lucru activ al unei singure codificări este de ordinul a 100 KB, încadrându-se confortabil în L2, iar prefetcher-ul hardware se fixează pe modelul de acces regulat.

Referința, prin contrast, menține o mapă hash de copii per nod, costând aproximativ patru încărcări dependente per pas de octet. Se aplică hashing pe octet, se încarcă bucket-ul, se urmează un pointer către intrarea din bucket, se urmează un alt pointer către nodul copil din heap, apoi se interoghează propria mapă hash pentru următorul octet. Obiectele din heap se împrăștie și majoritatea încărcărilor dau miss în cache.

SP și IREE stochează ambele ID-ul tokenului direct în nodul trie. Implementarea de referință a trie-ului returnează doar octeții potriviți, așa că codificatorul trebuie să aloce un șir nou pentru fiecare potrivire, să îl caute într-o mapă hash laterală pentru a recupera ID-ul tokenului și să citească scorul dintr-un vector separat. SP returnează ID-ul ca valoare stocată a trie-ului și citește scorul dintr-un tablou plat de numere cu virgulă mobilă:

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 folosește un API cu cursor cu stare în loc să returneze toate potrivirile într-un singur apel, dar modelul de cost este același: ID-urile tokenurilor și scorurile sunt accesibile ca indici de tablou plat, fără alocare sau hashing în timpul parcurgerii trie-ului propriu-zise. IREE alocă un singur tampon de ieșire per codificare; SP alocă în plus un nod de rețea (lattice) per potrivire în timpul programării dinamice, totalizând aproximativ 1.559 de alocări la 514 tokenuri.

Înainte de a schimba trie-ul, izolăm costul algoritmului de costul implementării: cât de repede rulează referința cu munca inutilă eliminată?

Baseline-ul păstrează trie-ul cu copii-mapă hash al referinței, dar face două modificări. O structură de lucru deținută de apelant deține tabelul DP, octeții preprocesați și ID-urile tokenurilor de ieșire, astfel încât calea critică nu face nicio alocare după încălzire. ID-ul tokenului și scorul sunt stocate direct în nodul trie, eliminând conversia de șir per potrivire și căutarea în mapa hash laterală.

Buclă interioară:

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,
        }
    }
}

Acesta este același algoritm, cu aceeași formă de trie și același model de acces, doar că fără alocări și fără căutări redundante. Rezultate la 514 tokenuri:

Motor	p50	Instrucțiuni	IPC	Alocări
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

Referința fără alocări comparată cu implementările existente ale tokenizerului la 514 tokenuri.

Eliminarea materializării șirurilor per potrivire și a căutării secundare în mapa hash reduce instrucțiunile de 2,4× față de referință. IPC-ul scade odată cu acestea (2,86 → 2,62) deoarece urmărirea pointerilor din mapa hash, ascunsă anterior în spatele muncii alocatorului, a devenit acum costul dominant per octet.

Latenta p50 și p99 a tokenizerului de referință și a referinței fără alocări, în funcție de dimensiunea intrării.

Rata de erori L2 cache a tokenizerului de referință și a referinței fără alocări, în funcție de dimensiunea intrării.

Baseline-ul reduce latența p50 de 2-3× față de referință la orice dimensiune, iar rata sa de miss L2 rămâne în jur de 2-3% până la 2k tokenuri, comparativ cu 8-48% la referință. Costul rămas este urmărirea pointerilor în HashMap, pe care o abordează secțiunea următoare.

Trie-ul cu mapă hash este o urmărire de pointeri. SP și IREE rezolvă acest lucru cu un trie cu tablou dublu (vezi secțiunea anterioară) și împrumutăm aceeași structură de date. Diferența este că SP și IREE sunt biblioteci generice care acceptă intrare în flux, offseturi de ieșire și moduri multiple de codificare; această flexibilitate le costă evidență contabilă suplimentară în jurul trie-ului (o rețea în SP, un pipeline în opt etape în IREE). Noi nu avem nevoie de nimic din toate acestea, așa că integrăm trie-ul direct în bucla Viterbi și eliminăm restul.

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
    }
}

Un pas pe octet costă două citiri din tablou, o adunare de întregi și o comparație. Întregul trie are în jur de 9 MB, dar orice codificare unică parcurge doar ~100 KB din el, așa că datele active rămân în L2.

Motor	p50	p99	Instrucțiuni	Miss L2 %	Miss L3 %
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%

Latenta tokenizerului, instrucțiunile și ratele de erori de cache după adoptarea trie-ului dublu-array.

Timpul wall-clock scade de 2,3× față de baseline și de 4,8× față de referință. Instrucțiunile scad cu încă 28% față de baseline. Renunțarea la rețea (lattice) și la pipeline ne permite să finalizăm 1,10M instrucțiuni per codificare față de 1,82M la SP și 1,61M la IREE la aceeași formă de trie; diferența o reprezintă evidența contabilă pe care o mențin pentru API-uri generice de care nu avem nevoie.

Trie-ul Darts de la Optimizarea 1 necesită două încărcări dependente per pas de octet. Mai întâi offsetul de bază al părintelui, apoi intrarea check din slotul candidat al copilului pentru a confirma că părintele îl deține. Intrarea check validează doar proprietatea. Aceeași întrebare poate fi răspunsă printr-o hartă de biți per nod care înregistrează ce octeți au copii. Prin construcția trie-ului cu tablou dublu, bitul pentru octetul b din harta de biți a părintelui este setat exact atunci când slotul candidat pentru acel octet este deținut de părinte. Harta de biți și tabloul check transportă aceleași informații, așa că putem elimina complet tabloul check din structura de rulare.

Căutarea în harta de biți se compilează într-un singur test de bit împotriva unui cuvânt pe 64 de biți, care rulează în aproximativ un ciclu. Instrucțiunea POPCNT aferentă, care numără toți biții setați dintr-un registru, este ceea ce alte designuri de trie indexate prin hartă de biți folosesc pentru a calcula direct un offset de copil din harta de biți. Nu avem nevoie de ea deoarece construcția Darts stochează deja acel offset în câmpul base al nodului.

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)
}

Întrucât tot ne aflăm aici, împachetăm cele patru câmpuri per nod (hartă de biți, bază, ID token și scor) într-o singură linie de cache de 64 de octeți. O singură vizită la nod aduce acum totul: scorul și ID-ul tokenului de care avem nevoie la nodurile terminale, plus harta de biți și baza pentru pasul următor. Tabloul check este folosit doar în timpul construcției și este eliminat din layout-ul de rulare. Indexarea pe calea critică nu este verificată deoarece construcția trie-ului și structura buclei garantează deja limitele. Compromisul îl reprezintă spațiul: la 64 de octeți per nod × ~780K sloturi, trie-ul crește de la ~9 MB la ~50 MB.

Rezultate la 514 tokenuri:

Motor	p50	p99	Instrucțiuni	Accese L2	Miss L2 %	Miss L3 %
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 și împachetare în linie	65 µs	77 µs	1,06M	1,8K	20,53%	15,01%

Rezultatele tokenizerului la 514 tokenuri după adăugarea bitmap-ului și a împachetării inline.

Timpul wall-clock scade sistematic cu încă 4,5% la 514 tokenuri și crește odată cu lungimea intrării, atingând 6-7% la 4k și 16k. Renunțarea la tabloul check transformă pasul trie-ului per octet din două încărcări de linii de cache în una, ceea ce înseamnă de 2,5× mai puține accese L2 per codificare (1,8K față de 4,6K în cazul Darts simplu). Rata de miss sare de la 6% la 20%, dar o mare parte din aceasta reprezintă numitorul: având mai puțin de jumătate din numărul de accese, miss-urile pe care le avem ocupă o pondere mai mare.

Datele trie-ului au aproximativ 50 MB (780.000 de noduri a câte 64 de octeți fiecare). Pe un proces Linux implicit, acea memorie este susținută de pagini de 4 KB, astfel încât întregul trie se întinde pe aproximativ 12.000 de pagini virtuale distincte, mult peste ceea ce poate ține Translation Lookaside Buffer de nivelul întâi al date-cache-ului procesorului (Sapphire Rapids are 96 de intrări). Fiecare pas Viterbi atinge un nod diferit, iar pe parcursul unei codificări de 512 tokenuri consumăm aproximativ 9.000 de cicluri în parcurgerile tabelei de pagini, reprezentând cam 3% din bugetul per codificare.

Soluția este să sprijinim trie-ul cu pagini mari de 2 MB în loc de unele de 4 KB. Aceeași 50 MB se întinde acum pe 25 de pagini, încape în întregime în Translation Lookaside Buffer, iar directoarele tabelei de pagini în sine încetează să mai concureze cu trie-ul pentru cache-ul L2.

Linux are două moduri de a susține memoria cu pagini de 2 MB. Cel oportunist este reprezentat de paginile mari transparente (THP - transparent huge pages): programul tău cere kernelului să actualizeze o regiune de memorie de la pagini de 4 KB la 2 MB, iar un fir de execuție de fundal din kernel încearcă să facă acest lucru atunci când are timp și memorie fizică contiguă disponibilă. Cealaltă alternativă este alocarea trie-ului direct dintr-un fond pre-rezervat de pagini mari pe care kernelul îl pune deoparte la pornire:

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,
    )
};

Fondul trebuie să existe pe gazdă (vm.nr_hugepages setat la pornire). Pe instanțele noastre de producție, sunt rezervate 10.561 de pagini mari; trie-ul consumă 24 dintre ele. După mmap, /proc/<pid>/smaps confirmă regiunea: KernelPageSize: 2048 kB, Private_Hugetlb: 49152 kB.

Câștigul este de 3–12% timp wall-clock în funcție de dimensiunile intrării, fiind consistent și proporțional cu lungimea setului de lucru:

Tokenuri	Fără pagini mari	Cu pagini mari	Δ
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%

Latenta tokenizerului cu și fără huge pages pentru diferite dimensiuni de intrare.

Cel mai mare câștig este la 4k tokenuri, unde setul de lucru este suficient de mare încât traficul tabelei de pagini concura activ cu datele trie-ului pentru lățimea de bandă L2. Dincolo de 4k, câștigul scade deoarece miss-urile L3 domină, iar parcurgerile tabelei de pagini devin o pondere mai mică din timpul total.

Reunind cele trei optimizări, iată motorul final măsurat față de orice alt tokenizator RoBERTa pe care l-am testat. Alături de binarele native C++ SentencePiece și C IREE, am evaluat și pachetele de wrapper Rust gata de utilizare la care ar apela un utilizator de producție, sentencepiece și iree-tokenizer. Crate-ul sentencepiece măsoară o latență de 1,6-1,9× mai mare decât binarul nativ C++ la fiecare dimensiune de intrare, overhead-ul provenind din faptul că wrapper-ul alocă o listă proaspătă de bucăți de token, fiecare deținând propria copie a textului bucății, la fiecare codificare. Crate-ul iree-tokenizer își dimensionează tamponul intern pentru fiecare intrare, evitând o alocare constantă per codificare pe care binarul nativ IREE o plătește indiferent de dimensiunea intrării, iar acest lucru contează cel mai mult la intrări scurte unde alocarea ar domina altfel munca efectivă de tokenizare. La lungimi de intrare de producție, costul constant se amortizează, iar overhead-ul propriu per apel al wrapper-ului din copierea tokenurilor înapoi în Rust împinge latența sa deasupra binarului nativ.

Latenta p50 și p99 per encodare, în funcție de implementările tokenizerului și de dimensiunile de intrare.

Motorul final rulează același Viterbi peste același vocabular de 250.000 de tokenuri, nu alocă nimic pe calea critică și produce o ieșire cu tokenuri exacte față de referință. Fiecare pas pe octet este acum o singură încărcătură de linie de cache de 64 de octeți, un test de hartă de biți și o adunare de întregi, în scădere față de o interogare HashMap, un apel de alocator și mai multe ramuri pentru cazuri speciale din implementarea baseline. Instrucțiunile per codificare au scăzut de la 3,66M la 1,04M, o scădere de 3,5×. Timpul wall-clock respectă acest raport la intrări scurte și se mărește și mai mult la intrări lungi, unde alocările per token ale referinței încep să depășească L2 și L3.

În practică, această muncă a redus utilizarea CPU în stratul de preprocesare al stivei noastre de inferență de 5-6× și a redus cu milisecunde de ordinul zecilor latența rerankerului.

Cea mai mare parte a reducerii latenței a provenit din modificări ușoare care au eliminat munca irosită: renunțarea la alocările per codificare, înlocuirea trie-ului cu copii-mapă hash cu un tablou dublu și eliminarea overhead-ului API-ului generic. Folosirea hărții de biți existente per nod ca verificare a validității și susținerea trie-ului cu pagini mari de 2 MB au reprezentat împreună 10-20% în plus față de trecerea mai amplă la un trie cu tablou dublu, în funcție de dimensiunea intrării.

Pachetele wrapper Rust gata de utilizare pentru SentencePiece și IREE ilustrează același punct în sens invers. Deasupra tokenizatoarelor native C și C++, granița FFI și alocările per apel pe care le introduc wrapper-ele sunt vizibile în valorile de latență. Sursa Rust pentru codificatorul Viterbi final este disponibilă la github.com/perplexityai/pplx-garden.

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

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

Tokenizator IREE — 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

Pagini mari (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}
}

Motivație

Algoritmul Viterbi

Implementare de referință

O notă despre preprocesare

Unde își petrece timpul implementarea de referință

Cum am măsurat

De ce SentencePiece și IREE sunt mai rapide: Trie-ul cu tablou dublu

Baseline: O portare cu alocări zero a referinței

Optimizarea 1: Trie cu tablou dublu fără abstracții suplimentare

Optimizarea 2: Împachetare bitmap și în linie

Optimizarea 3: Pagini mari pentru trie

Comparație finală

Gânduri de încheiere

Referințe

Citat