Förbättra CPU-prestanda för Unigram-tokeniserare

Vi implementerade om vår Unigram-tokeniserare från grunden som ett fokuserat prestandaprojekt. Vid produktionsinmatningslängder kapar den nya kodaren p50-latensen med ungefär 5× jämfört med Hugging Faces tokenizers-kratta, ~2× jämfört med SentencePiece (C++) och ~1,5× jämfört med IREE:s tokeniserare (C), med noll heap-allokeringar i stabilt läge. I produktion reducerade detta CPU-utnyttjandet i vår inferensstack med 5–6× och skalade av tvåsiffriga millisekunder från omlistningslatensen.

LLM-inferenskostnader formuleras vanligtvis som GPU-arbete: KV-cacher, uppmärksamhetskärnor, expertroutning. Men en betydande del av produktionstrafiken körs på mycket mindre modeller, två till tre storleksordningar mindre än gränstransformatorer. Inbäddningsmodeller, klassificerare och omlistare körs fortfarande på GPU:er, men framåtkörningen är tillräckligt kort för att allt runtomkring ska börja spela roll.

Det tydligaste exemplet är en omlistare som poängsätter hundratals kandidatdokument per förfrågan. Med en liten modell slutförs GPU-beräkningen vanligtvis på ensiffriga millisekunder, men varje indata måste ändå gå igenom CPU-sidig tokenisering först, vilket förvandlar text till vokabulär-ID:n. När batchen är stor kan det utgöra en betydande del av den totala förfrågningslatensen.

Detta arbete fokuserar på XLM-RoBERTa, ett Unigram-vokabulär med 250 000 tokens som tränats med SentencePiece. Finjusterade kodare i RoBERTa-familjen är ett vanligt val för ranknings-, hämtnings- och likhetsuppgifter. Vi rapporterar enkeltrådad latens per kodning genomgående; i produktion parallelliserar vi över kärnor med hjälp av rayon.

Genom hela detta inlägg behandlar vi Hugging Faces tokenizers-kratta som den referens vi benchmarkar mot, eftersom det är standardiserad Rust-tokeniserare som de flesta team vänder sig till. SentencePiece (C++) och IREE (C) inkluderas för jämförelse som de andra två stora produktionsimplementeringarna.

Unigram-tokenisering, som introducerades av Kudo 2018 (Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates) och levererades i SentencePiece, ramar in segmentering som ett problem med den mest sannolika vägen: varje vokabulärtoken har en inlärd log-sannolikhet, och kodaren väljer den segmentering vars tokenscorer summerar till det högsta värdet. Problemet löses med Viterbialgoritmen (1967), med bytepositioner som graflager och vokabulärtoken som kanter som spänner över ett sammanhängande byterintervall. Rekursen är en endimensionell DP över bytepositioner:

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

Den yttre loopen är linjär i indatalängd, begränsad vid varje position av det längsta vokabulärtokenet (48 UTF-8-byte för XLM-RoBERTa). Den inre trie-vandringen är den heta sökvägen: på en indata på 16k tokens kör den hundratusentals övergångar och slutför tals av miljoner instruktioner per kodning.

Hugging Faces tokenizers v0.22 implementerar rekursen direkt, med en hash-mapp för den omvända sökningen och hash-mapp-barn vid varje trienod:

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
}

Och den inre loopen (förenklad) – varje prefixsökningsträff allokerar en ny sträng och söker sedan igenom hash-mappen:

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 är läsbar Rust, men mycket arbete sker som är osynligt på källkods nivå. Nästa avsnitt bryter ned vart tiden tar vägen.

Innan Viterbi körs går indatan igenom Unicode-normalisering (NFKC) och markering av ordgränser. Profilering placerar förbehandlingen på mindre än 5 % av den totala kodningstiden i våra scenarier, så vi fokuserar på Viterbis framåtkörning under resten av inlägget.

Det finns två sätt att snabba upp CPU-kod: köra färre instruktioner eller uppnå högre IPC. Cachegrind mäter det första, perf stat mäter det andra. Varje optimering i detta inlägg landar på det ena eller det andra.

CPU:er stannar upp på fyra saker: cachemissar (L1d ~4 cykler, en L3-miss-till-DRAM är hundratals), beroende inläsningskedjor som den oordnade motorn inte kan parallellisera, felaktiga grenförutsägelser (~15–20 cykler rensade per felaktig gissning) och allokatoranrop. Referensimplementeringen av unigrammotorn drabbas av alla fyra:

Flaskhals	Mekanism	Uppmätt påverkan
Allokering per träff	String::from_utf8 på de matchade bytena plus en AHashMap-sökning per trie-träff; token-ID:t finns redan i lövet, men referensen lagrar det inte där	7 295 allokeringar vid 512 tokens, 14 542 vid 1k, 299 171 vid 16k
Pekarletning per byte	En AHashMap vid varje trienod, som hash-kodar nästa byte och avrefererar två pekare per steg; Node-strukturen buntar också ihop kalla fält som is_leaf, vilket drar in dem i cachen vid varje besök	L1d-missfrekvensen förblir låg (~2,5 % vid 1k) eftersom allokatorns heta sidor finns i L1; kostnaden visas som beroende inläsningslatens
L2-tröska vid långa indata	DP-tabell, prefix-skrap och listan över utdatatokens allokeras nyligen vid varje anrop	L2-missfrekvensen stiger från 12 % vid 128 tokens till 50 % vid 16k då det kumulativa allokeringsfotavtrycket överstiger L2 på 2 MB per kärna

Referens för flaskhalsar i tokeniseraren, mekanismer och uppmätta effekter.

Den dominerande kostnaden är allokeringen per träff. Vid 1k tokens slutför referensimplementeringen ungefär 7 miljoner instruktioner per kodning vid en IPC på 2,8, varav de flesta i allokatoranrop och strängkonverteringar. L2-missar spelar bara roll efter ~1k tokens, när det kumulativa allokeringsfotavtrycket spiller över per-kärnans cache.

Referens-tokeniserarens p50- och p99-fördröjning efter inmatningsstorlek.

Referens-tokeniserarens L2-cachemissfrekvens efter inmatningsstorlek.

Allokerade bytes per encoding av referens-tokeniseraren över olika inmatningsstorlekar.

Allokeringen per token är konstant: ungefär 2 KB och ~18 allokeringar per token, oavsett indatalängd. Latensens olinjäritet kommer från L2: kumulativa byte passerar 2 MB runt 1k tokens, missfrekvensen stiger från 8 % till ~50 %, och p99-kurvan böjs därefter.

Vi jämför tre produktionstokeniserare, som alla kör samma Unigram-algoritm mot samma XLM-RoBERTa-modell:

Motor	Språk	Trie
Hugging Face	Rust	HashMap-barn prefixtrie
SentencePiece	C++	Darts dubbelmatris-trie
IREE-tokeniserare	C	Darts dubbelmatris-trie

Tokeniseringsimplementationer, språk och trie-representationer som användes i jämförelsen.

Vi länkar SentencePiece och IREE genom direkt C/C++ FFI snarare än deras Rust-omslag; omslagen lägger till allokeringar per anrop och strängkonverteringar som inte är en del av det underliggande bibliotekets kostnad.

Alla motorer är byggda med fullständiga optimeringar (O3, inhemsk målinriktning, länkningstidsoptimering). Mätningarna kördes låsta till en tyst kärna på en Intel Xeon Platinum 8488C. För varje motor och indatalängd samlar vi in väggklockans latens (p50 och p99, 10 000 iterationer efter 1 000 uppvärmningar), instruktioner som avslutats via Valgrind cachegrind, IPC och cachemissfrekvens från hårdvaruräknare i perf stat, samt heapallokeringar räknade av en global allokatoromslag runt det uppmätta fönstret.

Vid 514 tokens (+2 över 512 är BOS/EOS-injektering):

Implementering	p50-latens	Instruktioner	IPC	Allokeringar
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

Tokeniseringsfördröjning, instruktioner, IPC och allokeringar vid 514 tokens.

SP och IREE landar på ungefär en tredjedel av referensens latens. De slutför ungefär hälften så många instruktioner, körs med högre IPC och allokerar en till två storleksordningar mindre.

SentencePiece och IREE använder båda den dubbelmatristrie som introducerades av Aoe 1989 (Aoe, 1989; Karoonboonyanan). Trien är kodad i två flata heltalsmatriser, base och check:

cpp

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

En barnuppslagning är:

cpp

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

Varje steg i trievandringen kräver endast två matrisinläsningar, en heltalsaddition och en jämförelse, utan hash-kodning, pekarlöpning eller heapallokering per nod. Konstruktionen placerar varje nod så att dess barn hamnar på lediga platser i valideringsmatrisen, vilket gör att flera föräldrar kan dela regioner så länge deras barn skiljer sig åt på den byte de följer.

För XLM-RoBERTs 250k-vokabulär får hela trien plats i ~9 MB sammanhängande minne (~780k platser × 12 byte för offset, validering och token-ID per plats). En enda kodnings het arbetsuppsättning är i storleksordningen 100 KB, vilket bekvämt får plats i L2, och maskinvaruförhämtaren låser sig fast vid det regelbundna åtkomstmönstret.

Referensen behåller däremot en hash-mapp över barn per nod, vilket kostar ungefär fyra beroende inläsningar per bytesteg. Hasha byten, läs in hinken, följ en pekare till hinkposten, följ en annan pekare till barnnoden på heapen och konsultera sedan dess egen hash-mapp för nästa byte. Heapobjekt sprids ut och de flesta inläsningar missar cachen.

SP och IREE lagrar båda token-ID:t direkt i trienoden. Referenstriens implementering returnerar endast de matchade bytena, så kodaren måste allokera en ny sträng för varje träff, leta upp den i en sidohash-mapp för att återställa token-ID:t och läsa poängen från en separat vektor. SP returnerar ID:t som triens lagrade värde och läser poängen från en platt flyttalsmatris:

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 använder ett tillståndskänsligt markör-API i stället för att returnera alla träffar i ett enda anrop, men kostnadsmodellen är den samma: token-ID:n och poäng är åtkomliga som index i platta matriser, utan allokering eller hash-kodning vid själva trievandringen. IREE allokerar endast en utdatabuffert per kodning; SP allokerar dessutom en gittermod per träff under DP:n, vilket totalt uppgår till ungefär 1 559 allokeringar vid 514 tokens.

Innan vi ändrar trien isolerar vi algoritmkostnaden från implementeringskostnaden: hur snabbt körs referensen när det onödiga arbetet har tagits bort?

Baslinjen behåller referensens hash-mapp-barn-trie men gör två ändringar. En anropsägd skrapstruktur rymmer DP-tabellen, förbehandlade byte och utdata-token-ID:n, så den heta sökvägen gör inga allokeringar efter uppvärmning. Token-ID:t och poängen lagras direkt i trienoden, vilket tar bort strängkonverteringen per träff och sökningen i sidohash-mappen.

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

Detta är samma algoritm, med samma trie-form och samma åtkomstmönster, bara utan allokeringar och utan redundanta uppslagningar. Resultat vid 514 tokens:

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

Baslinjen utan allokeringar jämfört med befintliga tokeniseringsimplementationer vid 514 tokens.

Borttagning av strängmaterialisering per träff och den sekundära hash-mappuppslagningen kapar instruktioner 2,4× jämfört med referensen. IPC sjunker med dem (2,86 → 2,62) eftersom hash-mappens pekarlöpning, tidigare dold bakom allokatorarbete, nu är den dominerande kostnaden per byte.

Referens- och baslinjetokeniseraren utan allokeringars p50- och p99-fördröjning efter inmatningsstorlek.

Referens- och baslinjetokeniseraren utan allokeringars L2-cachemissfrekvens efter inmatningsstorlek.

Baslinjen kapar p50-latensen med 2–3× jämfört med referensen i alla storlekar, och dess L2-missfrekvens stannar nära 2–3 % genom 2k tokens jämfört med referensens 8–48 %. Den återstående kostnaden är HashMap-pekarlöpningen, vilket nästa avsnitt adresserar.

Hash-mapptrien är en pekarlöpning. SP och IREE löser detta med en dubbelmatristrie (se föregående avsnitt), och vi lånar samma datastruktur. Skillnaden är att SP och IREE är generella bibliotek som stöder strömmande indata, utdata-offsets och flera kodningslägen; den flexibiliteten kostar dem extra bokföring runt trien (ett gitter i SP, en åttastegspipeline i IREE). Vi behöver inget av det, så vi inline:ar trien direkt i Viterbi-loopen och släpper 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
    }
}

Ett bytesteg kostar två matrisinläsningar, en heltalsaddition och en jämförelse. Hela trien är runt 9 MB, men varje enskild kodning vandrar bara igenom ~100 KB av den, så den heta datan stannar kvar 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 %
Baslinje	155 µs	1 170 µs	1,53M	2,59 %	16,66 %
+ Darts	68 µs	80 µs	1,10M	6,45 %	11,42 %

Tokeniseringsfördröjning, instruktioner och cachemissfrekvens efter införandet av dubbel-array-trädet.

Väggklockan sjunker 2,3× från baslinjen och 4,8× från referensen. Instruktionerna sjunker ytterligare 28 % från baslinjen. Att kapa gittret och pipelinen gör att vi kan slutföra 1,10 miljoner instruktioner per kodning mot SP:s 1,82 miljoner och IREE:s 1,61 miljoner vid samma trie-form; skillnaden är den bokföring de behåller för generella API:er som vi inte behöver.

Darts-trien från optimering 1 behöver två beroende inläsningar per bytesteg. Först förälderns base-offset, sedan check-posten på kandidatens barnplats för att bekräfta att föräldern äger den. Check-posten validerar endast ägarskap. Samma fråga kan besvaras av en bitmapp per nod som registrerar vilka byte som har barn. Genom dubbelmatristriens konstruktion är biten för byte b i förälderns bitmapp satt exakt när kandidatplatsen för den byten ägs av föräldern. Bitmappen och check-matrisen bär samma information, så vi kan ta bort check-matrisen från körtidsstrukturen helt och hållet.

Bitmappsuppslagningen kompileras till ett enda bit-test mot ett 64-bitarsord, vilket körs på ungefär en cykel. Den relaterade instruktionen POPCNT, som räknar alla satta bitar i ett register, är vad andra bitmappsindexerade trie-designer använder för att beräkna ett barn-offset direkt från bitmappen. Vi behöver det inte eftersom Darts-konstruktionen redan lagrar det offset i nodens base-fält.

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

Medan vi ändå håller på packar vi de fyra fälten per nod (bitmapp, base, token-ID och poäng) i en enda 64-bytes cacheline. Ett enda nodbesök drar nu in allt: poängen och token-ID:t vi behöver vid slutnoder, plus bitmappen och base för nästa steg. Check-matrisen används endast under konstruktion och tas bort från körtidslayouten. Indexeringen i den heta sökvägen är okontrollerad eftersom triekonstruktion och loopstruktur redan garanterar gränserna. Avvägningen är Space: vid 64 byte per nod × ~780k platser växer trien från ~9 MB till ~50 MB.

Resultat vid 514 tokens:

Motor	p50	p99	Instruktioner	L2-åtkomster	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 %
Baslinje	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 %
+ Bitmapp och inline-packning	65 µs	77 µs	1,06M	1,8K	20,53 %	15,01 %

Tokeniseringsresultat vid 514 tokens efter att bitmap och inline-paketering lagts till.

Väggklockan sjunker systematiskt med ytterligare 4,5 % vid 514 tokens och växer med indatalängden, vilket når 6–7 % vid 4k och 16k. Att ta bort check-matrisen förvandlar triesteget per byte från två cacheline-inläsningar till en, vilket är 2,5× färre L2-åtkomster per kodning (1,8K jämfört med 4,6K för vanliga Darts). Missfrekvensen hoppar från 6 % till 20 %, men det mesta av det är nämnaren: med mindre än hälften så många åtkomster tar de missar vi har en större andel.

Triedatan är ungefär 50 MB (780 000 noder med 64 byte vardera). På en standardiserad Linux-process stöds det minnet av 4 KB-sidor, så hela trien spänner över cirka 12 000 distinkta virtuella sidor, långt bortom vad CPU:ns första nivås data Translation Lookaside Buffer kan rymma (Sapphire Rapids har 96 poster). Varje Viterbi-steg rör vid en annan nod, och över en 512-tokens kodning bränner vi ungefär 9 000 cykler i sidtabellsvandringar, cirka 3 % av per-kodningsbudgeten.

Lösningen är att stödja trien med 2 MB stora sidor i stället för 4 KB-sidor. Samma 50 MB spänner nu över 25 sidor, får plats i Translation Lookaside Buffer helt och hållet, och själva sidtabellskatalogerna slutar tävla med trien om L2-cachen.

Linux har två sätt att stödja minne med 2 MB-sidor. Det opportunistiska är transparenta stora sidor (THP): ditt program ber kärnan att uppgradera en minnesregion från 4 KB till 2 MB-sidor, och en bakgrundskärntråd försöker göra det när den har tid och sammanhängande fysiskt minne tillgängligt. Det andra alternativet är att allokera trien direkt från en förreserverad pool av stora sidor som kärnan sätter åt sidan vid uppstart:

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åste finnas på värden (vm.nr_hugepages inställd vid uppstart). På våra produktionsinstanser är 10 561 stora sidor reserverade; trien förbrukar 24 av dem. Efter mmap bekräftar /proc/<pid>/smaps regionen: KernelPageSize: 2048 kB, Private_Hugetlb: 49152 kB.

Vinsten är 3–12 % i väggklocka över indatalängder, konsekvent och proportionell mot arbetsuppsättningens längd:

Tokens	Utan stora sidor	Med stora sidor	Δ
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 %

Tokeniseringsfördröjning med och utan huge pages över olika inmatningsstorlekar.

Den största vinsten är vid 4k tokens, där arbetsuppsättningen är tillräckligt stor för att sidtabellstrafik aktivt tävlade med triedata om L2-bandbredd. Utöver 4k krymper vinsten eftersom L3-missar dominerar och sidtabellsvandringar blir en mindre andel av den totala tiden.

Genom att sammanföra de tre optimeringarna är här den slutliga motorn uppmätt mot varje annan RoBERTa-tokeniserare vi testade. Vid sidan av de inhemska C++ SentencePiece- och C IREE-binärfilerna benchmarkade vi även de färdiga Rust-omslagspaketen som en produktionsanvändare skulle vända sig till, sentencepiece och iree-tokenizer. Paketet sentencepiece uppmäter 1,6–1,9× högre latens än den inhemska C++-binärfilen vid varje indatalängd, där omkostnaden kommer från att omslaget allokerar en ny lista med token-delar, som var och en håller sin egen kopia av deltexten, vid varje kodning. Paketet iree-tokenizer storleksanpassar sin interna buffert till varje indata, vilket undviker en konstant allokering per kodning som den inhemska IREE-binärfilen betalar oavsett indatalängd, och det spelar störst roll vid korta indata där allokeringen annars skulle dominera det faktiska tokeniseringsarbetet. Vid produktionsinmatningslängder amorteras den konstanta kostnaden och omslagets egen omkostnad per anrop från att kopiera tokens tillbaka till Rust driver dess latens över den inhemska binärfilens.

p50- och p99-fördröjning per encoding över tokeniseringsimplementationer och inmatningsstorlekar.

Den slutliga motorn kör samma Viterbi över samma 250 000-tokens vokabulär, allokerar ingenting på den heta sökvägen och producerar token-exakt utdata gentemot referensen. Varje bytesteg är nu en enda 64-bytes cacheline-inläsning, ett bitmappstest och en heltalsaddition, ner från en HashMap-sökning, ett allokatoranrop och flera specialfallsregler i baslinjeimplementeringen. Instruktioner per kodning föll från 3,66M till 1,04M, ett fall på 3,5×. Väggklockan matchar det förhållandet vid korta indata och breddas ytterligare vid långa indata, där referensens allokeringar per token börjar spilla över L2 och L3.

I praktiken reducerade detta arbete CPU-utnyttjandet i förbehandlingslagret i vår inferensstack med 5–6× och skalade av tvåsiffriga millisekunder från omlistningslatensen.

Merparten av latensminskningen kom från lätta ändringar som tog bort slösat arbete: att släppa allokeringar per kodning, ersätta HashMap-barn-trien med en dubbelmatris och skala bort den generiska API-omkostnaden. Att använda den befintliga bitmappen per nod som giltighetskontroll och stödja trien med 2 MB stora sidor bidrog sammantaget med 10–20 % ovanpå det större skiftet till en dubbelmatristrie, beroende på indatalängd.

De färdiga Rust-omslagspaketen runt SentencePiece och IREE illustrerar samma poäng bakvänt. Ovanpå inhemska C- och C++-tokeniserare är FFI-gränserna och allokeringarna per anrop som omslagen introducerar synliga i latenssiffrorna. Rust-källkoden för den slutliga Viterbi-kodaren finns tillgänglig på github.com/perplexityai/pplx-garden.

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

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

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

Stora sidor — 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

Viterbialgoritmen

Referensimplementering

En anmärkning om förbehandling

Vart referensimplementeringen lägger sin tid

Hur vi mätte

Varför SentencePiece och IREE är snabbare: Dubbelmatristrien

Baslinje: En nollallokeringsport av referensen

Optimering 1: Dubbelmatristrie utan extra abstraktioner

Optimering 2: Bitmap och inline-packning

Optimering 3: Huge pages för trie-strukturen

Slutlig jämförelse

Avslutande tankar

Referenser

Citering