Forbedring av CPU-ytelsen for unigram-tokenisereren

Vi implementerte Unigram-tokenisereren vår på nytt fra bunnen av som et målrettet ytelsesprosjekt. Ved produksjonsinndatalengder reduserer den nye encoderen p50-latensen med omtrent 5× sammenlignet med Hugging Face tokenizers-crate, ~2× sammenlignet med SentencePiece (C++) og ~1,5× sammenlignet med IREEs tokeniserer (C), med null heap-allokeringer i stabil tilstand. I produksjon reduserte dette CPU-forbruket i slutningsstakken vår med 5–6× og barberte bort tosifrede millisekunder fra rangeringslatensen.

Kostnaden for LLM-slutning blir vanligvis fremstilt som GPU-arbeid: KV-mellomlagre, oppmerksomhetskjerner, ekspertstyring. Men en vesentlig del av produksjonstrafikken kjører på mye mindre modeller, to til tre størrelsesordener mindre enn grensetransformatorer. Innbyggingsmodeller, klassifiserere og rangere kjører fremdeles på GPU-er, men fremoverpasseringen er kort nok til at alt rundt den begynner å spille en rollen.

Det tydeligste tilfellet er en ranker som scorer hundrevis av kandidatdokumenter per forespørsel. Med en liten modell fullføres GPU-beregningen typisk på enkle millisekunder, men hver inndata må fremdeles gjennom CPU-side tokenisering først, noe som gjør tekst om til vokabular-ID-er. Når batchen er stor, kan det utgjøre en betydelig brøkdel av den totale forespørselslatensen.

Dette arbeidet retter seg mot XLM-RoBERTa, et Unigram-vokabular med 250 000 tokens trent med SentencePiece. Finjusterte encodere i RoBERTa-familien er et vanlig valg for rangerings-, hentings- og likhetsoppgaver. Vi rapporterer enklettrådet latens per encodering gjennomgående; i produksjon parallelliserer vi på tvers av kjerner ved hjelp av rayon.

Gjennom dette innlegget behandler vi Hugging Faces tokenizers crate som referansen vi måler opp mot, siden det er standard Rust-tokeniserer de fleste team strekker seg etter. SentencePiece (C++) og IREE (C) er inkludert for sammenligning som de to andre store produksjonsimplementeringene.

Unigram-tokenisering, introdusert av Kudo i 2018 (Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates) og levert i SentencePiece, rammer inn segmentering som et mest-sannsynlige-sti-problem: hvert vokabulartoken har en innlært log-sannsynlighet, og encoderen velger segmenteringen der tokenskårene summerer til den høyeste verdien. Problemet løses med Viterbi-algoritmen (1967), med byte-posisjoner som graf-lag og vokabulartokene som kanter som spenner over et sammenhengende byte-område. Rekursjonen er en eendimensjonal DP over byte-posisjoner:

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

Ytre løkke er lineær i inndatalengde, begrenset ved hver posisjon av det lengste vokabulartokenet (48 UTF-8-byter for XLM-RoBERTa). Den indre trie-vandringen er den kritiske veien: på en inndata på 16k tokens kjører den hundretusenvis av overganger og pensjonerer titalls millioner instruksjoner per encodering.

Hugging Faces tokenizers v0.22 implementerer rekursjonen direkte, med et hashtabell for det omvendte oppslaget og hashtabell-barn ved hver trie-node:

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
}

Og den indre løkken (forenklet) – hvert prefiks-søk-treff allokerer en ny streng og sjekker deretter hashtabellen:

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
}

Koden er lesbar Rust, men det skjer mye arbeid som er usynlig på kildenivå. Neste seksjon bryter ned hvor tiden blir av.

Før Viterbi kjører, går inndataen gjennom Unicode-normalisering (NFKC) og merking av ordgrenser. Profilering plasserer forbehandling på mindre enn 5 % av den totale encoderings tiden i våre scenarier, så vi fokuserer på Viterbi-framoverpasseringen for resten av innlegget.

Det er to måter å få fart på CPU-kode på: utfør færre instruksjoner, eller få høyere IPC. Cachegrind måler det første, perf stat måler det andre. Hver optimalisering i dette innlegget lander på det ene eller det andre.

CPU-er stopper opp på fire ting: cache-bommer (L1d ~4 sykluser, en L3-bom-til-DRAM er hundrevis), avhengige innlastingskjeder som den uorden-utførende motoren ikke kan parallellisere, feilaktige grenspådommer (~15–20 sykluser tømt per feil gjett), og allokatorkall. Den referansebaserte unigram-motoreffektiviseringen treffer alle fire:

Flaskehals	Mekanisme	Målt påvirkning
Allokering per treff	String::from_utf8 på de matchede bytene pluss et AHashMap-oppslag per trie-treff; token-ID-en er allerede i bladet, men referansen lagrer den ikke der	7 295 allokeringer ved 512 tokens, 14 542 ved 1k, 299 171 ved 16k
Pekerjakt per byte	En AHashMap ved hver trie-node, hasher den neste byten og dereferensierer to pekere per trinn; Node-strukturen samler også kalde felt som is_leaf, og trekker dem inn i cachen ved hvert besøk	L1d-bomfrekvensen holder seg lav (~2,5 % ved 1k) fordi allokatorens varme sider bor i L1; kostnaden vises som avhengig innlastingslatens
L2-treskning på lange inndata	DP-tabell, prefiks-kladd og utdatert token-liste blir alle nylig allokert ved hvert kall	L2-bomfrekvensen stiger fra 12 % ved 128 tokens til 50 % ved 16k ettersom det kumulative allokeringsavtrykket overstiger den per-kjerne 2 MB L2-en

Referanse for flaskehalser, mekanismer og målte effekter for tokenizer.

Den dominerende kostnaden er allokeringen per treff. Ved 1k tokens pensjonerer (fullfører) referanseimplementeringen omtrent 7M instruksjoner per encodering ved en IPC på 2,8, de fleste av dem i allokatorkall og strengkonverteringer. L2-bommer har bare betydning etter ~1k tokens, når det kumulative allokeringsavtrykket overflyter per-kjerne-cachen.

Referanse-tokenizerens p50- og p99-latens etter inputstørrelse.

Referanse-tokenizerens L2-cache-miss-rate etter inputstørrelse.

Byte allokert per encode av referanse-tokenizeren på tvers av inputstørrelser.

Allokering per token er konstant: omtrent 2 KB og ~18 allokeringer per token, uavhengig av inndatastørrelse. Latens-uineariteten kommer fra L2: kumulative byte krysser 2 MB rundt 1k tokens, bomfrekvensen stiger fra 8 % til ~50 %, og p99-kurven bøyer seg for å matche.

Vi sammenligner tre produksjonstokeniserere, som alle kjører den samme Unigram-algoritmen mot den samme XLM-RoBERTa-modellen:

Motor	Språk	Trie
Hugging Face	Rust	HashMap-barn prefiks-trie
SentencePiece	C++	Darts dobbel-array trie
IREE-tokeniserer	C	Darts dobbel-array trie

Tokenizer-implementeringer, språk og trie-representasjoner brukt i sammenligningen.

Vi kobler SentencePiece og IREE gjennom direkte C/C++ FFI i stedet for deres Rust-omslagsfunksjoner; omslagene legger til per-kall-allokeringer og strengkonverteringer som ikke er en del av det underliggende bibliotekets kostnad.

Alle motorer er bygget med full optimalisering (O3, native-målretting, link-tid-optimalisering). Målingene kjører fastlåst til én rolig kjerne på en Intel Xeon Platinum 8488C. For hver motor og inndatastørrelse samler vi inn veggur-latens (p50 og p99, 10 000 itereringer etter 1 000 oppvarming), instruksjoner pensjonert via Valgrind cachegrind, IPC- og cache-bomfrekvenser fra perf stat-maskinvaretellere, og heap-allokeringer telt av en global allokator-omslag rundt det målte vinduet.

Ved 514 tokens (+2 over 512 er BOS/EOS-injeksjon):

Implementering	p50-latens	Instruksjoner	IPC	Allokeringer
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-latens, instruksjonsantall, IPC og allokeringer ved 514 tokens.

SP og IREE lander på omtrent en tredjedel av referansens latens. De pensjonerer omtrent halvparten så mange instruksjoner, kjører med høyere IPC, og allokerer én til to størrelsesordener mindre.

SentencePiece og IREE bruker begge dobbel-array trien introdusert av Aoe i 1989 (Aoe, 1989; Karoonboonyanan). Trien er kodet i to flate heltallsarrayer, base og check:

cpp

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

Et barn-oppslag er:

cpp

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

Hvert trinn i trie-gjennomgangen trenger bare to array-innlastinger, én heltallsaddisjon og én sammenligning, uten hashing, uten pekerjakt og uten heap-allokering per node. Konstruksjonen plasserer hver node slik at barna faller på ledige plasser i valideringsarrayet, noe som lar flere foreldre dele regioner så lenge barna deres er forskjellige på byten de følger.

For XLM-RoBERTAs 250k-vokabular får hele trien plass i ~9 MB sammenhengende minne (~780k plasser × 12 byte for forskyvning, validering og token-ID per plass). Et enkelt encodings varme arbeidssett er i størrelsesorden 100 KB, komfortabelt i L2, og maskinvarens prefetcher låser seg fast på det vanlige tilgangsmønsteret.

Referansen, derimot, beholder en hashtabell med barn per node, som koster omtrent fire avhengige innlastinger per bytetrinn. Hash byten, last inn bøtta, følg en peker til bøtteoppføringen, følg en annen peker til barnenoden på heapen, og slå deretter opp i sin egen hashtabell for neste byte. Heap-objekter spres og de fleste innlastinger bommer på cachen.

SP og IREE lagrer begge token-ID-en direkte i trie-noden. Referansetrie-implementeringen returnerer bare de matchede bytene, så encoderen må allokere en ny streng for hvert treff, slå den opp i en side-hashtabell for å gjenopprette token-ID-en, og lese skåren fra en separat vektor. SP returnerer ID-en som triens lagrede verdi og leser skåren fra en flat flyttallsarray:

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 bruker en tilstandsstyrt markør-API i stedet for å returnere alle treff i et enkelt kall, men kostnadsmodellen er den samme: token-ID-er og skårer er tilgjengelige som flate array-indekser, uten allokering eller hashing på selve trie-vandringen. IREE allokerer bare én utdata buffer per encodering; SP allokerer i tillegg en gitter-node per treff under DP-en, og totalt omtrent 1 559 allokeringer ved 514 tokens.

Før vi endrer trien, isolerer vi algoritmekostnaden fra implementeringskostnaden: hvor raskt kjører referansen med det unødvendige arbeidet fjernet?

Basinlinjen beholder referansens hashtabell-barn-trie, men gjør to endringer. En kladdstruktur eid av kcaller inneholder DP-tabellen, forbehandlede byte og utdata-token-ID-er, slik at den kritiske veien ikke gjør noen allokeringer etter oppvarming. Token-ID-en og skåren lagres direkte i trie-noden, og fjerner strengkonverteringen per treff og side-hashtabell-oppslaget.

Indre løkke:

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

Dette er den samme algoritmen, med den samme trie-formen og det samme tilgangsmønsteret, bare uten allokeringer og uten redundante oppslag. Resultater ved 514 tokens:

Motor	p50	Instruksjoner	IPC	Allokeringer
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
Basinlinje	156 µs	1,53M	2,62	0

Null-allokeringsbaseline sammenlignet med eksisterende tokenizer-implementeringer ved 514 tokens.

Fjerning av strengmaterialisering per treff og det sekundære hashtabell-oppslaget kuttes instruksjoner 2,4× mot referansen. IPC faller med dem (2,86 → 2,62) fordi hashtabell-pekerjakten, som tidligere var skjult bak allokatorarbeid, nå er den dominerende kostnaden per byte.

Referanse- og null-allokeringsbaseline-tokenizerens p50- og p99-latens etter inputstørrelse.

Referanse- og null-allokeringsbaseline-tokenizerens L2-cache-miss-rate etter inputstørrelse.

Basinlinjen reduserer p50-latensen med 2–3× sammenlignet med referansen i alle størrelser, og L2-bomfrekvensen holder seg nær 2–3 % gjennom 2k tokens sammenlignet med referansens 8–48 %. Restkostnaden er HashMap-pekerjakten, som neste seksjon adresserer.

Hashtabell-trien er en pekerjakt. SP og IREE løser dette med en dobbel-array trie (se forrige seksjon), og vi låner den samme datastrukturen. Forskjellen er at SP og IREE er generelle biblioteker som støtter strømmingsinndata, utdataforskyvninger og flere encodingsmodus; den fleksibiliteten koster dem ekstra bokføring rundt trien (et gitter i SP, en åtte-trinns pipeline i IREE). Vi trenger ikke noe av det, så vi inliner trien direkte i Viterbi-løkken og kaster resten.

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

Et bytetrinn koster to array-lesinger, en heltallsaddisjon og en sammenligning. Hele trien er rundt 9 MB, men enhver enkelt encodering vandrer bare gjennom ~100 KB av den, slik at de varme dataene forblir i L2.

Motor	p50	p99	Instruksjoner	L2-bom%	L3-bom%
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 %
Basinlinje	155 µs	1 170 µs	1,53M	2,59 %	16,66 %
+ Darts	68 µs	80 µs	1,10M	6,45 %	11,42 %

Tokenizer-latens, instruksjoner og cache-miss-rater etter innføring av double-array trie.

Veggur faller 2,3× fra basinlinjen og 4,8× fra referansen. Instruksjoner faller ytterligere 28 % fra basinlinjen. Kutting av gitteret og pipelinen lar oss pensjonere 1,10M instruksjoner per encodering mot SPs 1,82M og IREEs 1,61M ved samme trie-form; gapet er bokføringen de beholder for generell API som vi ikke trenger.

Darts-trien fra optimalisering 1 trenger to avhengige innlastinger per bytetrinn. Først foreldrens baseforskyvning, deretter check-oppføringen ved den potensielle barnplassen for å bekrefte at forelderen eier den. Check-oppføringen validerer bare eierskap. Det samme spørsmålet kan besvares av et per-node bildekart som registrerer hvilke byte som har barn. Ved konstruksjonen av dobbel-array-trien settes bitten for byte b i foreldrens bildekart nøyaktig når kandidatplassen for den byten eies av forelderen. Bildekartet og check-arrayet bærer den samme informasjonen, så vi kan fjerne check-arrayet fra kjøretidsstrukturen fullstendig.

Bildekartoppslaget kompileres til en enkelt bitttest mot ett 64-biters ord, som kjører på omtrent en syklus. Den tilhørende POPCNT-instruksjonen, som teller allesatte biter i et register, er det andre bildekart-indekserte trie-design bruker til å beregne en barnforskyvning direkte fra bildekartet. Vi trenger det ikke fordi Darts-konstruksjonen allerede lagrer den forskyvningen i nodens basefelt.

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

Mens vi holder på, pakker vi de fire feltene per node (bildekart, base, token-ID og skåre) inn i én 64-bytes cachelinje. Et enkelt nodebesøk trekker nå inn alt: skåren og token-ID-en vi trenger ved terminale noder, pluss bildekartet og basen for neste trinn. Check-arrayet brukes bare under konstruksjon og fjernes fra kjøretidslayouten. Indeksering på den kritiske veien er ukontrollert fordi trie-konstruksjon og løkkestruktur allerede garanterer grensene. Avveiningen er Rom: med 64 byte per node × ~780k plasser vokser trien fra ~9 MB til ~50 MB.

Resultater ved 514 tokens:

Motor	p50	p99	Instruksjoner	L2-tilganger	L2-bom%	L3-bom%
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 %
Basinlinje	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 %
+ Bildekart og inline-pakkig	65 µs	77 µs	1,06M	1,8K	20,53 %	15,01 %

Tokenizer-resultater ved 514 tokens etter å ha lagt til bitmap og inline-pakking.

Vegguret faller systematisk ytterligere 4,5 % ved 514 tokens og vokser med inndatalengde, og når 6–7 % ved 4k og 16k. Å fjerne check-arrayet gjør trie-trinnet per byte om fra to cachelinje-innlastinger til én, som er 2,5× færre L2-tilganger per encodering (1,8K mot vanlige Darts' 4,6K). Bomfrekvensen hopper fra 6 % til 20 %, men det meste av det er nevneren: med mindre enn halvparten så mange tilganger tar bommene vi faktisk har, en større del.

Trie-dataene er omtrent 50 MB (780 000 noder på 64 byte hver). På en standard Linux-prosess støttes dette minnet av 4 KB-sider, slik at hele trien spenner over omtrent 12 000 distinkte virtuelle sider, langt over det CPU-ens første-nivås databuffer for oversettelse av sideadresser (TLB) kan holde (Sapphire Rapids har 96 oppføringer). Hvert Viterbi-trinn berører en annen node, og over en 512-tokens encodering brenner vi omtrent 9 000 sykluser i sidetabellvandringer, omtrent 3 % av budsjettet per encodering.

Løsningen er å støtte trien med 2 MB store sider i stedet for 4 KB-sider. De samme 50 MB spenner nå over 25 sider, får plass i oversettelsesbufferen fullstendig, og selve sidetabellkatalogene slutter å konkurrere med trien om L2-cachen.

Linux har to måter å støtte minne på med 2 MB-sider. Den opportunistiske er transparente store sider (THP): programmet ditt ber kjernen om å oppgradere en minneregion fra 4 KB- til 2 MB-sider, og en bakgrunnskjerntråd prøver å gjøre det når den har tid og sammenhengende fysisk minne tilgjengelig. Det andre alternativet er å allokere trien direkte fra en forhåndsreservert pool av store sider som kjernen setter til side ved oppstart:

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

Poolen må eksistere på verten (vm.nr_hugepages satt ved oppstart). På våre produksjonsinstanser er 10 561 store sider reservert; trien forbruker 24 av dem. Etter mmap bekrefter /proc/<pid>/smaps regionen: KernelPageSize: 2048 kB, Private_Hugetlb: 49152 kB.

Gevinsten er 3–12 % veggur på tvers av inndatastørrelser, konsekvent og proporsjonal med arbeidssettets lengde:

Tokens	Uten store sider	Med store sider	Δ
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-latens med og uten huge pages på tvers av inputstørrelser.

Den største seieren er ved 4k tokens, der arbeidssettet er stort nok til at sidetabell-trafikk aktivt konkurrerte med trie-data om L2-båndbredde. Utover 4k minker gevinsten fordi L3-bommer dominerer og sidetabellvandringer blir en mindre del av totaltid.

Ved å trekke de tre optimaliseringene sammen, er her den endelige motoren målt mot hver eneste andre RoBERTa-tokeniserer vi testet. Ved siden av de native C++ SentencePiece- og C IREE-binærene, benchmarkte vi også de ferdige Rust-omslagene en produksjonsbruker ville strekke seg etter, sentencepiece og iree-tokenizer. sentencepiece-craten måler 1,6–1,9× høyere latens enn den native C++-binæren ved hver inndatastørrelse, der overheaden kommer fra at omslaget allokerer en ny liste med token-biter, der hver holder sin egen kopi av bit-teksten, ved hver encodering. iree-tokenizer-craten tilpasser sin interne buffer til hver inndata, noe som unngår en konstant allokering per encodering som den native IREE-binæren betaler uavhengig av inndatastørrelse, og det betyr mest ved korte inndata der allokeringen ellers ville dominert det faktiske tokeniseringsarbeidet. Ved produksjonsinndatalengder amortiserer den konstante kostnaden og omslagets egen per-kall-overhead fra kopiering av token tilbake til Rust skyver latensen over den native binærens.

p50- og p99-latens per encode på tvers av tokenizer-implementeringer og inputstørrelser.

Den endelige motoren kjører den samme Viterbi over det samme 250 000-tokens vokabularet, allokerer ingenting på den kritiske veien, og produserer token-nøyaktig utdata mot referansen. Hvert bytetrinn er nå en enkel 64-bytes cachelinje-innlasting, én bitttest og én heltallsaddisjon, ned fra et HashMap-oppslag, et allokatorkall og flere spesialtilfelle-grener i baseline-implementeringen. Instruksjoner per encodering falt fra 3,66M til 1,04M, et 3,5× fall. Vegguret matcher det forholdet ved korte inndata og utvides ytterligere ved lange inndata, der referansens allokeringer per token begynner å overflyte L2 og L3.

I praksis reduserte dette arbeidet CPU-forbruket i forbehandlingslaget i slutningsstakken vår med 5–6× og barberte tosifrede millisekunder av rangeringslatensen.

Hoveddelen av latensreduksjonen kom fra lette endringer som fjernet bortkastet arbeid: å fjerne allokeringer per encodering, erstatte HashMap-barn-trien med en dobbel-array, og fjerne generell-API-overheaden. Bruk av det eksisterende per-node-bildekartet som gyldighetssjekk og støtte for trien med 2 MB store sider utgjorde til sammen 10–20 % på toppen av det større byttet til en dobbel-array trie, avhengig av inndatastørrelse.

De ferdige Rust-omslagene rundt SentencePiece og IREE illustrerer det samme poenget omvendt. På toppen av native C- og C++-tokeniserere er FFI-grensen og per-kall-allokeringene som omslagene introduserer, synlige i latens-tallene. Rust-kilden for den endelige Viterbi-encoderen er tilgjengelig på github.com/perplexityai/pplx-garden.

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

Motivasjon

Viterbi-algoritmen

Referanseimplementering

En merknad om forbehandling

Hvor referanseimplementeringen bruker tiden sin

Hvordan vi målte

Hvorfor SentencePiece og IREE er raskere: Dobbel-array trien

Basinlinje: En null-allokeringsport av referansen

Optimalisering 1: Dobbel-array trie uten ekstra abstraksjoner

Optimalisering 2: Bitkart og integrert pakking

Optimalisering 3: Store sider for trie-strukturen

Siste sammenligning

Avsluttende tanker

Referanser

Sitat