Forbedring af Unigram-tokenizerens CPU-ydeevne

Vi genskabte vores Unigram-tokenizer helt fra bunden som et målrettet ydeevneprojekt. Ved inputlængder i produktionen reducerer den nye encoder p50-latensen med ca. 5× sammenlignet med Hugging Face-tokenizer-crate'en, ~2× sammenlignet med SentencePiece (C++) og ~1,5× sammenlignet med IREE's tokenizer (C) med nul heap-allokeringer i stabil tilstand. I produktionen reducerede dette CPU-forbruget i vores inferensstack med 5-6× og barberede tocifrede millisekunder af latensen for rerankeren.

Omkostningerne ved LLM-inferens opfattes normalt som GPU-arbejde: KV-cacher, attention-kerner, ekspertrouting. Men en væsentlig del af produktionstrafikken kører på meget mindre modeller, to til tre størrelsesordener mindre end de førende transformere. Embedding-modeller, klassifikatorer og rerankere kører stadig på GPU'er, men forward pass'et er kort nok til, at alt omkring det begynder at betyde noget.

Det klareste eksempel er en reranker, der scorer hundreder af kandidatdokumenter pr. forespørgsel. Med en lille model er GPU-beregningen typisk færdig på et enkelt millisekund, men hvert input skal stadig igennem CPU-side tokenisering først, hvilket omdanner tekst til vokabular-ID'er. Når batch-størrelsen er stor, kan det udgøre en væsentlig brøkdel af den samlede forespørgselslatens.

Dette arbejde retter sig mod XLM-RoBERTa, et Unigram-vokabular med 250.000 tokens trænet med SentencePiece. Finjusterede encodere i RoBERTa-familien er et almindeligt valg til rangerings-, genfindings- og lighedsopgaver. Vi rapporterer enkelttrådet latens pr. encode overalt; i produktionen paralleliserer vi på tværs af kerner ved hjælp af rayon.

Gennem dette indlæg behandler vi Hugging Face's tokenizers-crate som den reference, vi benchmarker imod, da det er den standard Rust-tokenizer, de fleste teams vælger. SentencePiece (C++) og IREE (C) er inkluderet til sammenligning som de to andre store produktionsimplementeringer.

Unigram-tokenisering, introduceret af Kudo i 2018 (Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates) og leveret i SentencePiece, opfatter segmentering som et problem med den mest sandsynlige sti: Hvert vokabulartoken har en indlært log-sandsynlighed, og encoderen vælger den segmentering, hvis tokenscores summer til den højeste værdi. Problemet løses med Viterbi-algoritmen (1967) med byte-positioner som graf-lag og vokabulartoken som kanter, der spænder over et sammenhængende byte-interval. Recurrencen er en 1D DP over byte-positioner:

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

Ydre loop er lineært i inputlængden, begrænset ved hver position af det længste vokabulartoken (48 UTF-8-bytes for XLM-RoBERTa). Det indre trie-gennemløb er hot path: på et input på 16k tokens kører det hundredvis af tusinder af overgange og eksekverer ti millioner instruktioner pr. encode.

Hugging Face's tokenizers v0.22 implementerer recurrencen direkte med et hashmap til omvendt opslag og hashmap-børn 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 det indre loop (forenklet) – ethvert præfiks-søgningstræf allokerer en ny streng og forespørger derefter hashmappet:

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 letlæselig Rust, men der foregår en masse arbejde, som er usynligt på kildekodeniveau. Næste afsnit bryder ned, hvor tiden bliver af.

Før Viterbi kører, gennemgår inputtet Unicode-normalisering (NFKC) og markering af ordgrænser. Profilering sætter præprocessing til mindre end 5 % af den samlede encoderingstid i vores scenarier, så vi fokuserer på Viterbis forward pass i resten af indlægget.

Der er to måder at fremskynde CPU-kode på: udføre færre instruktioner eller opnå højere IPC. Cachegrind måler det første, perf stat måler det andet. Enhver optimering i dette indlæg lander på den ene eller den anden.

CPU'er går i stå på fire ting: cache-misses (L1d ~4 cyklusser, en L3-miss-til-DRAM er hundredvis), afhængige indlæsningskæder, som den uudførte motor ikke kan parallelisere, branch mispredicts (~15-20 cyklusser tømmes pr. forkert gæt) og allocator-kald. Referenceunigram-motorens implementering rammer alle fire:

Flaskehals	Mekanisme	Målt påvirkning
Allokering pr. træf	String::from_utf8 på de matchede bytes plus et AHashMap-opslag pr. trie-træf; token-ID'et er allerede i bladet, men referencen gemmer det ikke der	7.295 allokeringer ved 512 tokens, 14.542 ved 1k, 299.171 ved 16k
Pointer-chase pr. byte	Et AHashMap ved hver trie-node, der hasher den næste byte og dereferencer to pointere pr. trin; Node-strukturen bundter også kolde felter som is_leaf og trækker dem ind i cachen ved hvert besøg	L1d miss-rate forbliver lav (~2,5 % ved 1k), fordi allocatorns hot pages ligger i L1; omkostningerne vises som afhængig indlæsningslatens
L2 thrashing på lange inputs	DP-tabel, præfiks-scratch og listen over output-tokens allokeres alle helt nyt ved hvert kald	L2 miss-rate stiger fra 12 % ved 128 tokens til 50 % ved 16k, efterhånden som det kumulative allokeringsfodaftryk overstiger L2 på 2 MB pr. kerne

Referencer tokenizer-flaskehalse, mekanismer og målte effekter.

De dominerende omkostninger er allokeringer pr. træf. Ved 1k tokens eksekverer (fuldfører) referenceimplementeringen ca. 7M instruktioner pr. encode ved en IPC på 2,8, hvor de fleste af dem er i allocator-kald og strengkonverteringer. L2-misses betyder først noget efter ~1k tokens, når det kumulative allokeringsfodaftryk overskrider kerne-cachen.

Referencetokenizerens p50- og p99-latens efter inputstørrelse.

Referencetokenizerens L2-cache-miss-rate efter inputstørrelse.

Allokerede bytes per encoding af referencetokenizeren på tværs af inputstørrelser.

Allokering pr. token er konstant: ca. 2 KB og ~18 allokeringer pr. token uanset inputstørrelse. Latensens ikke-linearitet kommer fra L2: kumulative bytes krydser 2 MB omkring 1k tokens, miss-rate stiger fra 8 % til ~50 %, og p99-kurven bøjer for at matche.

Vi sammenligner tre produktions-tokenizers, der alle kører den samme Unigram-algoritme mod den samme XLM-RoBERTa-model:

Motor	Sprog	Trie
Hugging Face	Rust	HashMap-children præfiks-trie
SentencePiece	C++	Darts double-array trie
IREE tokenizer	C	Darts double-array trie

Tokenizer-implementeringer, sprog og trie-repræsentationer brugt i sammenligningen.

Vi linker SentencePiece og IREE gennem direkte C/C++ FFI i stedet for deres Rust-wrappers; wrapperne tilføjer allokeringer pr. kald og strengkonverteringer, som ikke er en del af det underliggende biblioteks omkostninger.

Alle motorer er bygget med fulde optimeringer (O3, native targeting, link-time optimization). Målingerne kører fastlåst på én stille kerne på en Intel Xeon Platinum 8488C. For hver motor og inputstørrelse indsamler vi vægur-latens (p50 og p99, 10.000 iterationer efter 1.000 warmup), instruktioner udført via Valgrind cachegrind, IPC og cache-miss-rater fra perf stat-hardwaretællere og heap-allokeringer talt af en global allocator-wrapper omkring det målte vindue.

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

Implementering	p50-latens	Instruktioner	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, instruktionsantal, IPC og allokeringer ved 514 tokens.

SP og IREE lander på ca. en tredjedel af referencens latens. De udfører ca. halvdelen så mange instruktioner, kører ved højere IPC og allokerer en til to størrelsesordener mindre.

SentencePiece og IREE bruger begge double-array-trien introduceret af Aoe i 1989 (Aoe, 1989; Karoonboonyanan). Trien er kodet i to flade heltals-arrays, 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 børneopslag er:

cpp

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

Hvert trin i trie-gennemløbet kræver kun to array-indlæsninger, én heltalsaddition og én sammenligning, uden hashing, uden pointer-chasing og uden heap-allokering pr. node. Konstruktionen placerer hver node, så dens børn falder på ledige pladser i valideringsarrayet, hvilket gør det muligt for flere forældre at dele områder, så længe deres børn er uenige om den byte, de følger.

For XLM-RoBERTa's vokabular på 250K passer hele trien i ~9 MB sammenhængende hukommelse (~780K pladser × 12 bytes for offset, validering og token-ID pr. plads). Et enkelt encodes varme arbejdssæt er på størrelse med 100 KB, hvilket komfortabelt er i L2, og hardware-prefetcheren låser fast på det regulære adgangsmønster.

Referencen opretholder derimod et hashmap af børn pr. node, hvilket koster ca. fire afhængige indlæsninger pr. bytetrin. Hash byten, indlæs bøtten, følg en pointer til bøtte-indgangen, følg endnu en pointer til børnenoden på heapen, og slå derefter op i dens eget hashmap for den næste byte. Heap-objekter spredes, og de fleste indlæsninger misser cachen.

SP og IREE gemmer begge token-ID'et direkte i trie-noden. Referencetrie-implementeringen returnerer kun de matchede bytes, så encoderen er nødt til at allokere en ny streng for hvert match, slå det op i et side-hashmap for at gendanne token-ID'et og læse scoren fra en separat vektor. SP returnerer ID'et som triens lagrede værdi og læser scoren fra et fladt 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 bruger en tilstandsbaseret cursor-API i stedet for at returnere alle matches i et enkelt kald, men omkostningsmodellen er den samme: token-ID'er og -scores kan nås som flade array-indekser uden allokering eller hashing på selve trie-gennemløbet. IREE allokerer kun én outputbuffer pr. encode; SP allokerer derudover en gitter-node pr. match under DP'en, i alt ca. 1.559 allokeringer ved 514 tokens.

Før vi ændrer trien, isolerer vi algoritmens omkostninger fra implementeringens omkostninger: Hvor hurtigt kører referencen, når det unødvendige arbejde fjernes?

Baselinjen beholder referencens hashmap-børn-trie, men foretager to ændringer. En caller-ejet scratch-struktur indeholder DP-tabellen, præprocesserede bytes og output-token-ID'er, så hot path ikke foretager nogen allokeringer efter warmup. Token-ID og score gemmes direkte i trie-noden, hvilket fjerner strengkonverteringen pr. match og opslaget i side-hashmappet.

Indre loop:

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 algoritme med den samme trie-form og det samme adgangsmønster, bare uden allokeringer og uden redundante opslag. Resultater ved 514 tokens:

Motor	p50	Instruktioner	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
Baseline	156 µs	1,53M	2,62	0

Den nul-allokerende baseline sammenlignet med eksisterende tokenizer-implementeringer ved 514 tokens.

Fjernelse af strengmaterialisering pr. match og det sekundære hashmap-opslag reducerer instruktioner 2,4× i forhold til referencen. IPC falder med dem (2,86 → 2,62), fordi hashmap-pointer-chasing, som tidligere var skjult bag allocator-arbejde, nu er de dominerende omkostninger pr. byte.

Referencetokenizerens og den nul-allokerende baselinetokenizers p50- og p99-latens efter inputstørrelse.

Referencetokenizerens og den nul-allokerende baselinetokenizers L2-cache-miss-rate efter inputstørrelse.

Baselinjen reducerer p50-latensen med 2-3× i forhold til referencen ved hver størrelse, og dens L2 miss-rate forbliver nær 2-3 % op til 2k tokens i forhold til referencens 8-48 %. De resterende omkostninger er HashMap-pointer-chasing, som næste afsnit adresserer.

Hashmap-trien er en pointer-chase. SP og IREE løser dette med en double-array trie (se forrige afsnit), og vi låner den samme datastruktur. Forskellen er, at SP og IREE er generelle biblioteker, der understøtter streaming-input, output-offsets og flere encoderingsmetoder; den fleksibilitet koster dem ekstra bogholderi omkring trien (et gitter i SP, en rørledning i otte trin i IREE). Vi har ikke brug for noget af det, så vi inliner trien direkte i Viterbi-loppet og udelader 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 bytetrin koster to array-læsninger, en heltalsaddition og en sammenligning. Hele trien er omkring 9 MB, men en enkelt encode gennemløber kun ~100 KB af den, så de varme data forbliver i L2.

Motor	p50	p99	Instruktioner	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-latens, instruktioner og cache-miss-rate efter indførelse af double-array-trie.

Vægur-latensen falder 2,3× fra baselinjen og 4,8× fra referencen. Instruktioner falder yderligere 28 % fra baselinjen. At skære gitteret og rørledningen væk giver os mulighed for at udføre 1,10M instruktioner pr. encode mod SP's 1,82M og IREE's 1,61M ved samme trie-form; forskellen er det bogholderi, de holder for generelle API'er, som vi ikke har brug for.

Darts-trien fra optimering 1 behøver to afhængige indlæsninger pr. bytetrin. Først forældrens base-offset, derefter check-indgangen ved den kandidat-børneplads for at bekræfte, at forælderen ejer den. Check-indgangen validerer kun ejerskab. Det samme spørgsmål kan besvares af en bitmap pr. node, der registrerer, hvilke bytes der har børn. Ved konstruktionen af double-array-trien er bitten for byte b i forældrens bitmap sat præcis, når kandidatpladsen for den pågældende byte ejes af forælderen. Bitmap- og check-arrayet bærer den samme information, så vi kan fjerne check-arrayet helt fra runtime-strukturen.

Bitmap-opslaget kompileres til en enkelt bittest mod ét 64-bit ord, hvilket kører på ca. en cyklus. Den relaterede POPCNT-instruktion, som tæller alle satte bitte i et register, er det, andre bitmap-indekserede trie-design bruger til at beregne en børne-offset direkte fra bitmap'en. Vi behøver den ikke, fordi Darts-konstruktionen allerede gemmer den offset i nodens base-felt.

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

Når vi nu er i gang, pakker vi de fire felter pr. node (bitmap, base, token-ID og score) ind i én 64-bytes cache-linje. Et enkelt nodebesøg trækker nu alt ind: den score og det token-ID, vi har brug for ved terminal-noder, plus bitmap og base til næste trin. Check-arrayet bruges kun under konstruktionen og fjernes fra runtime-layoutet. Hot path-indeksering tjekkes ikke, fordi trie-konstruktion og loop-struktur allerede garanterer grænserne. Kompromiset er Space: ved 64 bytes pr. node × ~780K pladser vokser trien fra ~9 MB til ~50 MB.

Resultater ved 514 tokens:

Motor	p50	p99	Instruktioner	L2-adgange	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 og inline-pakning	65 µs	77 µs	1,06M	1,8K	20,53 %	15,01 %

Tokenizer-resultater ved 514 tokens efter tilføjelse af bitmap og inline-pakning.

Vægur-latensen falder systematisk med yderligere 4,5 % ved 514 tokens og vokser med inputlængden, idet den når 6-7 % ved 4k og 16k. Fjernelse af check-arrayet omdanner trie-trinlet pr. byte fra to cache-linje-indlæsninger til én, hvilket er 2,5× færre L2-adgange pr. encode (1,8K mod de 4,6K for almindelig Darts). Miss-raten springer fra 6 % til 20 %, men det skyldes primært nævneren: med under halvdelen så mange adgange tager de misses, vi har, en større andel.

Trie-dataene er ca. 50 MB (780.000 noder med 64 bytes hver). På en standard Linux-proces understøttes denne hukommelse af 4 KB-sider, så hele trien spænder over ca. 12.000 forskellige virtuelle sider, langt ud over hvad CPU'ens første-niveau data Translation Lookaside Buffer kan indeholde (Sapphire Rapids har 96 indgange). Hvert Viterbi-trin berører en anden node, og over et encode på 512 tokens brænder vi ca. 9.000 cyklusser af på sidetabelgennemløb, ca. 3 % af budgettet pr. encode.

Løsning er at understøtte trien med 2 MB huge pages i stedet for 4 KB-sider. De samme 50 MB spænder nu over 25 sider, passer fuldstændigt ind i Translation Lookaside Buffer, og sidetabelmapperne stopper med at konkurrere med trien om L2-cachen.

Linux har to måder at understøtte hukommelse med 2 MB-sider på. Den opportunistiske er transparent huge pages (THP): dit program beder kernen om at opgradere et hukommelsesområde fra 4 KB- til 2 MB-sider, og en baggrundstråd i kernen forsøger at gøre det, når den har tid og sammenhængende fysisk hukommelse til rådighed. Det andet alternativ er at allokere trien direkte fra en forud reserveret huge-page-pulje, som kernen lægger til side ved opstart:

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

Puljen skal eksistere på værten (vm.nr_hugepages indstillet ved opstart). På vores produktionsinstanser er 10.561 huge pages reserveret; trien forbruger 24 af dem. Efter mmap bekræfter /proc/<pid>/smaps området: KernelPageSize: 2048 kB, Private_Hugetlb: 49152 kB.

Gevinsten er 3–12 % vægur-latens på tværs af inputstørrelser, konsistent og proportional med arbejdssættets længde:

Tokens	Uden huge pages	Med 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-latens med og uden huge pages på tværs af inputstørrelser.

Den største gevinst er ved 4k tokens, hvor arbejdssættet er stort nok til, at sidetabeltrafik aktivt konkurrerede med trie-data om L2-båndbredde. Ud over 4k mindskes gevinsten, fordi L3-misses dominerer, og sidetabelgennemløb bliver en mindre del af den samlede tid.

Når vi samler de tre optimeringer, er her den endelige motor målt mod alle andre RoBERTa-tokenizers, vi testede. Ved siden af de native C++ SentencePiece- og C IREE-binaries benchmarked vi også de færdige Rust-wrapper-crates, som en produktionsbruger ville vælge, sentencepiece og iree-tokenizer. Sentencepiece-craten måler 1,6-1.9× højere latens end den native C++-binary ved enhver inputstørrelse, hvor overheaden kommer fra wrapperen, der allokerer en ny liste af token-dele, som hver holder sin egen kopi af delteksten, ved hvert encode. Iree-tokenizer-craten tilpasser sin interne buffer til hvert input, hvilket undgår en konstant allokering pr. encode, som den native IREE-binary betaler uanset inputstørrelse, og det betyder mest ved korte inputs, hvor allokeringerne ellers ville dominere det faktiske tokeniseringsarbejde. Ved produktionsinputlængder amortiseres de konstante omkostninger, og wrapperens egne overheads pr. kald ved kopiering af tokens tilbage til Rust presser dens latens over den native binarys.

p50- og p99-latens per encoding på tværs af tokenizer-implementeringer og inputstørrelser.

Den endelige motor kører den samme Viterbi over det samme vokabular på 250.000 tokens, allokerer intet på hot path og producerer token-nøjagtigt output i forhold til referencen. Hvert bytetrin er nu en enkelt 64-bytes cache-linje-indlæsning, én bittest og én heltalsaddition, ned fra et hashmap-opslag, et allocator-kald og adskillige specialtilfældes-forgreninger i baseline-implementeringen. Instruktioner pr. encode faldt fra 3,66M til 1,04M, et fald på 3,5×. Vægur-latensen matcher det forhold ved korte inputs og udvides yderligere ved lange inputs, hvor referencens allokeringer pr. token begynder at overbelaste L2 og L3.

I praksis reducerede dette arbejde CPU-forbruget i præprocessing-laget i vores inferensstack med 5-6× og barberede tocifrede millisekunder af latensen for rerankeren.

Hovedparten af latensreduktionen kom fra letvægtsændringer, der fjernede spildt arbejde: fjernelse af allokeringer pr. encode, udskiftning af hashmap-børn-trien med en double-array og fjernelse af generic-API-overhead. Brug af den eksisterende bitmap pr. node som validitetstjek og understøttelse af trien med 2 MB huge pages tegnede sig samlet for 10-20 % oven i det større skift til en double-array trie, afhængigt af inputstørrelse.

De færdige Rust-wrapper-crates omkring SentencePiece og IREE illustrerer det samme punkt omvendt. Oven på de native C- og C++-tokenizers er FFI-grænsen og de allokeringer pr. kald, som wrapperne introducerer, synlige i latens-tallene. Rust-koden til den endelige Viterbi-encoder er tilgængelig 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}
}

Motivation

Viterbi-algoritmen

Referenceimplementering

En bemærkning om præprocessing

Hvor referenceimplementeringen bruger sin tid

Sådan målte vi

Hvorfor SentencePiece og IREE er hurtigere: Double-array-trien

Baseline: En nul-allokeringsport af referencen

Optimering 1: Double-array trie uden ekstra abstraktioner

Optimering 2: Bitmap- og inline-pakning

Optimering 3: Store sider til trie'en

Endelig sammenligning

Afsluttende tanker

Referencer

Citering