Bæta afköst unigram-táknara í örgjörva

Vi útfærðum Unigram-táknarann okkar upp á nýtt frá grunni sem einbeitt afkastaverkefni. Við inntakslengdir í framleiðslu sker nýi kóðarinn p50-seinkun um u.þ.b. 5× miðað við tokenizers-pakka Hugging Face, ~2× miðað við SentencePiece (C++) og ~1,5× miðað við táknara IREE (C), án þess að nokkrar stöðugar hrúguúthlutanir eiga sér stað. Í framleiðslu minnkaði þetta örgjörvanotkun í ályktunarstöflunni okkar um 5–6× og stytti seinkun endurraðara um tugi millisekúndna.

Kostnaður við ályktun stórra málmódela er venjulega skilgreindur sem grafíkvinnslu vinna: KVskyndiminni, athygliskjarnar, leiðarval sérfræðinga. En verulegur hluti framleiðsluumferðar keyrir á miklu minni módelum, tveimur til þremur stærðargráðum minni en fremstu spennar. Innbýningarmódel, flokkarar og endurraðarar keyra enn á grafíkvinnslueiningum, en framsenduferlið er nógu stutt til þess að allt í kringum það byrjar að skipta máli.

Skýrasta dæmið er endurraðari sem gefur einkunnir á hundruðum skjalaframbjóðenda í hverri beiðni. Með litlu módelum lýkur útreikningi grafíkvinnslueiningar venjulega á einum millisekúndum, en hvert inntak þarf samt að fara í gegnum táknun á hlið örgjörva fyrst, sem breytir texta í orðasafnskenni. Þegar runan er stór getur það numið verulegum hluta af heildarseinkun beiðni.

Þetta verk miðar að XLM-RoBERTa, 250 þúsunda tókena Unigram orðasafni þjálfuðu með SentencePiece. Fínstilltir kódarar úr RoBERTa-fjölskyldunni eru algeng an val fyrir röðunar-, sækjunar- og líkindaverkverkefni. Við gefum upp einþráða seinkun á hverja umkóðun; í framleiðslu hliðarumtökum við þvert á kjarna með rayon.

Í gegnum þessa færslu lítum við á tokenizers pakka Hugging Face sem viðmið sem við berum saman við, þar sem hann er sjálfgefni Rust táknarinn sem flest teymi nota. SentencePiece (C++) og IREE (C) eru meðteknir til samanburðar sem hin tvö helstu framleiðsluútgáfurnar.

Unigram táknun, kynnt af Kudo árið 2018 (Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates) og send út í SentencePiece, setur sneiðingu fram sem líklegustu-leiðar vandamál: hvert orðasafnstákn er með lærða lóg-líkindadreifingu og kódarinn velur þá sneiðingu þar sem einkunnir tákna leggjast saman í hæsta gildi. Vandamálið er leyst með Viterbi reikniritinu (1967), með bætsstaðsetningum sem línuritssvölum og orðasafnstáknum sem brúm sem spanna samfellt bætsviðbil. Endurtekningin er einvídd DP yfir bætsstaðsetningar:

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

Ytri lykkjan er línuleg m.t.t. inntakslengdar, afmörkuð á hverjum stað af lengsta orðasafnstákninu (48 UTF-8 bæti fyrir XLM-RoBERTa). Innri trie-gangan er heita leiðin: á 16k tókena inntaki keyrir hún hundruð þúsunda umskitinga og skilar tugum milljóna leiðbeininga á hverja umkóðun.

tokenizers v0.22 frá Hugging Face útfærir endurtekninguna beint, með töflu fyrir öfuga flettingu og töflubörn á hverjum trie-hnút:

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 innri lykkjan (einfölduð) – hver samsvörun í forskeytisleit úthlutar nýjum streng og leitar síðan í töflunni:

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
}

Kóðinn er læsilegur Rust, en mikið af vinnu á sér stað sem er ósýnileg á kóðastigi. Næsti hluti skiptir niður hvert tíminn fer.

Áður en Viterbi keyrir fer inntakið í gegnum Unicode-stöðlun (NFKC) og orðamörkamerkingu. Prófílsgreining setur forvinnslu í minna en 5% af heildartíma umkóðunar í okkar tilfellum, svo við einblínum á Viterbi framsendiferlið það sem eftir er af færslunni.

Það eru tvær leiðir til að hraða örgjörvakóða: framkvæma færri leiðbeiningar eða ná meiri IPC. Cachegrind mælir það fyrra, perf stat mælir það síðara. Hver hagræðing í þessari færslu lendir á öðru hvoru.

Örgjörvar stöðvast á fjórum hlutum: skyndiminnisbrestum (L1d ~4 hringir, L3-brestur-í-DRAM eru hundruð), háðum hleðslukeðjum sem óraðraða vélbúnaðurinn getur ekki samhliðað, rangspám greina (~15-20 hringir hreinsaðir á hverja ranga giskun) og úthlutunarköllum. Tilvísunar unigram-vélútgáfan hittir á öll fjögur:

Flöskuháls	Kerfi	Mæld áhrif
Úthlutun á hverja samsvörun	String::from_utf8 á samsvörunarbætum ásamt AHashMap flettingu á hverja trie-samsvörun; tókenkennið er þegar til staðar í laufinu, en tilvísunin geymir það ekki þar	7.295 úthlutanir við 512 tóken, 14.542 við 1k, 299.171 við 16k
Ábendingaleit á hvert bæti	AHashMap á hverjum trie-hnút, sem hellir niður næsta bæti og afvísar tveimur ábendingum í hverju skrefi; Node-skrúfan safnar einnig köldum reitum eins og is_leaf, sem dregur þá inn í skyndiminni í hverri heimsókn	L1d brestutíðni heldur sér lágri (~2,5% við 1k) vegna þess að heitar síður úthlutunaraðila lifa í L1; kostnaðurinn birtist sem seinkun á háðri hleðslu
L2 högg á löngum inntökum	DP-tafla, forskeytisvinnslusvæði og framleiðslutáknalistinn eru öll nýúthlutuð í hverju kalli	L2 brestutíðni hækkar úr 12% við 128 tóken í 50% við 16k þar sem safnfótspor úthlutunar fer yfir 2 MB L2 á hvern kjarna

Tilvísun í flöskuhálsa táknara, verkferla og mæld áhrif.

Ríkjandi kostnaður er úthlutun á hverja samsvörun. Við 1k tóken skilar tilvísunarútgáfan (lýkur) um það bil 7M leiðbeiningum á hverja umkóðun með IPC 2,8, flestum þeirra í úthlutunarköllum og strengjabreytingum. L2 brestir skipta aðeins máli eftir ~1k tóken, þegar safnfótspor úthlutunar flæðir yfir skyndiminni á hvern kjarna.

p50- og p99-töf tilvísunartáknara eftir inntaksstærð.

L2-skyndiminnishvarfshlutfall tilvísunartáknara eftir inntaksstærð.

Bætir sem úthlutað er per kóðun af tilvísunartáknaranum yfir inntaksstærðir.

Úthlutun á hvern tóken er föst: um 2 KB og ~18 úthlutanir á hvern tóken, óháð stærð inntaks. Seinkunarólinearleikin kemur frá L2: uppsöfnuð bæti fara yfir 2 MB í kringum 1k tóken, brestutíðni hækkar úr 8% í ~50% og p99 ferillinn beygist til að passa við.

Við berum saman þrjá framleiðslutáknara, sem allir keyra sama Unigram reikniritið gegn sama XLM-RoBERTa módelinu:

Vél	Tungumál	Trie
Hugging Face	Rust	HashMap-barna forskeytis trie
SentencePiece	C++	Darts tvöföld-fylkis trie
IREE táknari	C	Darts tvöföld-fylkis trie

Táknaraútfærslur, tungumál og trie-framsetningar sem notaðar eru í samanburðinum.

Við tengjum SentencePiece og IREE í gegnum beina C/C++ FFI í stað Rust-umbúða þeirra; umbúðirnar bæta við úthlutunum á hvert kall og strengjabreytingum sem eru ekki hluti af kostnaði undirliggjandi bókasafns.

Allar vélar eru smíðaðar með fullum hagræðingum (O3, innfædd miðun, hlekkjatíma hagræðing). Mælingar keyrðu fastar á einum hljóðlátum kjarna á Intel Xeon Platinum 8488C. Fyrir hverja vél og inntaksstærð söfnum við klukkuseinkun (p50 og p99, 10.000 ítranir eftir 1.000 upphitun), leiðbeiningum skilað í gegnum Valgrind cachegrind, IPC og skyndiminnisbrestutíðni úr vélbúnaðartalningum perf stat, og hrúguúthlutunum talningu frá alheimsúthlutunarumbúðum utan um mældan glugga.

Við 514 tóken (+2 yfir 512 er BOS/EOS innspýting):

Útfærsla	p50 seinkun	Leiðbeiningar	IPC	Úthlutanir
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

Töf táknara, fjöldi leiðbeininga, IPC og úthlutanir við 514 tákn.

SP og IREE lenda í u.þ.b. þriðjungi af seinkun tilvísunarinnar. Þær skila um helmingi færri leiðbeiningum, keyra á meiri IPC og úthluta einni til tveimur stærðargráðum minna.

SentencePiece og IREE nota bæði tvöfalda fylkis trie-ið sem Aoe kynnti árið 1989 (Aoe, 1989; Karoonboonyanan). Trie-ið er kóðað í tveimur flötum heiltölufylkjum, 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

Barnsfletting er:

cpp

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

Hvert skref í trie-göngunni þarf aðeins tvær fylkishleðslur, eina heiltölusamlagningu og einn samanburð, án hash-aðgerða, án ábendingaleitar og án hestaúthlutunar á hvern hnút. Smíðin staðsetur hvern hnút þannig að börn hans lenda á lausum hólfum í staðfestingarfylkinu, sem gerir mörgum foreldrum kleift að deila svæðum svo lengi sem börn þeirra eru ósammála um bætið sem þau fylgja.

Fyrir 250K orðasafn XLM-RoBERTa passar allt trie-ið í ~9 MB af samfelldu minni (~780K hólf × 12 bæti fyrir hliðrun, staðfestingu og tókenkenni á hólf). Virk vinnusett stakrar umkóðunar er um 100 KB, þægilega í L2, og vélbúnaðarforhleðarinn læsir sér við reglulegt aðgöngumynstur.

Tilvísunin heldur aftur á móti töflu yfir börn á hvern hnút, sem kostar u.þ.b. fjórar háðar hleðslur á hvert bætaskref. Hassar bætið, hleður fötunni, fylgir ábendingu að fötufærslu, fylgir annarri ábendingu að barnshnút á heilu minni, og ráðfærir sig síðan við sína eigin töflu fyrir næsta bæti. Heila hlutir dreifast og flestar hleðslur missa af skyndiminni.

SP og IREE geyma báðir tókenkennið beint í trie-hnútnum. Trie-útfærsla tilvísunarinnar skilar aðeins samsvörunarbætum, þannig að kódarinn þarf að úthluta nýjum streng fyrir hverja samsvörun, fletta honum upp í hliðartöflu til að endurheimta tókenkennið, og lesa einkunnina úr aðskildum vigri. SP skilar kenninu sem geymdu gildi trie-sins og les einkunnina úr flötu fljótandi kommu fylki:

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 notar stöðugt bendils-API í stað þess að skila öllum samsvörunum í einu kalli, en kostnaðarlíkanið er það sama: tókenkenni og einkunnir eru aðgengilegar sem flatfylkisvísar, án úthlutunar eða hash-aðgerða á sjálfri trie-göngunni. IREE úthlutar aðeins einum úttakspúffara á hverja umkóðun; SP úthlutar auk þess ristahnút á hverja samsvörun meðan á DP stendur, samtals um 1.559 úthlutanir við 514 tóken.

Áður en trie-ið er breytt einangrum við reikniritiskostnað frá útfærslukostnaði: hversu hratt keyrir tilvísunin þegar óþarfa vinnu hefur verið sleppt?

Grunnlínan heldur trie-i tilvísunarinnar með töflubörnum en gerir tvær breytingar. Vinnusvæði í eigu kallsins geymir DP-töfluna, forvinnslu bæti og úttakstókenkenni, þannig að heita leiðin gerir engar úthlutanir eftir upphitun. Tókenkennið og einkunnin eru geymd beint í trie-hnútnum, sem fjarlægir strengjabreytingu á hverja samsvörun og aukatöfluflettingu.

Innri lykkja:

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

Þetta er sama reikniritið, með sama trie-lögun og sama aðgöngumynstri, bara án úthlutana og óþarfra flettinga. Niðurstöður við 514 tóken:

Vél	p50	Leiðbeiningar	IPC	Úthlutanir
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
Grunnlína	156 µs	1,53M	2,62	0

Grunnlína án úthlutana borin saman við fyrirliggjandi táknaraútfærslur við 514 tákn.

Að fjarlægja strengjaútfærslu á hverja samsvörun og aukatöfluflettingu sker leiðbeiningar 2,4× miðað við tilvísunina. IPC fellur með þeim (2,86 → 2,62) vegna þess að ábendingaleit töflunnar, sem áður var falin á bak við úthlutunarvinnu, er nú ríkjandi kostnaður á hvert bæti.

p50- og p99-töf tilvísunar- og grunnlínu-táknara án úthlutana eftir inntaksstærð.

L2-skyndiminnishvarfshlutfall tilvísunar- og grunnlínu-táknara án úthlutana eftir inntaksstærð.

Grunnlínan sker p50-seinkun um 2-3× miðað við tilvísunina á öllum stærðum, og L2 brestutíðni hennar heldur sér nálægt 2-3% í gegnum 2k tóken á móti 8-48% tilvísunarinnar. Eftirstandandi kostnaður er HashMap ábendingaleitin, sem næsti hluti tekur á.

Tafla trie-ið er ábendingaleit. SP og IREE leysa þetta með tvöföldu-fylkis trie (sjá fyrri hluta), og við lánum sama gagnaskipulag. Mismunurinn er sá að SP og IREE eru almenn bókasöfn sem styðja straum-inntak, úttakshliðranir og margar umkóðunarstillingar; sú sveigjanleiki kostar þau aukabókhald í kringum trie-ið (rist í SP, átt-þrepa leiðsla í IREE). Við þurfum ekkert af því, svo við fellum trie-ið beint inn í Viterbi lykkjuna og sleppum afganginum.

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

Bætaskref kostar tvær fylkishleðslur, heiltölusamlagningu og samanburð. Allt trie-ið er um 9 MB, en hver stök umkóðun gengur aðeins í gegnum ~100 KB af því, þannig að heitu gögnin haldast í L2.

Vél	p50	p99	Leiðbeiningar	L2 brestur%	L3 brestur%
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%
Grunnlína	155 µs	1.170 µs	1,53M	2,59%	16,66%
+ Darts	68 µs	80 µs	1,10M	6,45%	11,42%

Töf táknara, leiðbeiningar og skyndiminnishvarfshlutföll eftir innleiðingu double-array trie.

Klukkutími fellur 2,3× frá grunnlínu og 4,8× frá tilvísuninni. Leiðbeiningar falla um önnur 28% frá grunnlínu. Að klippa ristinguna og leiðsluna gerir okkur kleift að skila 1.10M leiðbeiningum á hverja umkóðun á móti 1.82M SP og 1.61M IREE við sömu trie-lögun; bilið er bókhaldið sem þau halda úti fyrir almenn API sem við þurfum ekki.

Darts trie-ið frá Hagræðingu 1 þarf tvær háðar hleðslur á hvert bætaskref. Fyrst grunnhliðrun foreldris, síðan check-færslan í mögulegu barnshólfi til að staðfesta að foreldrið eigi það. Check-færslan staðfestir aðeins eignarhald. Sömu spurningu má svara með bitamynd á hvern hnút sem skráir hvaða bæti eiga börn. Með smíði tvöfalda-fylkis trie-sins er batið fyrir bæti b í bitamynd foreldris stillt nákvæmlega þegar mögulega hólfið fyrir það bæti er í eigu foreldris. Bitamyndin og check-fylkið bera sömu upplýsingar, þannig að við getum sleppt check-fylkinu úr keyrsluskipulaginu alveg.

Bitamyndarflettingin þýðist yfir í eitt bitapróf gegn einu 64-bita orði, sem keyrir á u.þ.b. einum hring. Tengda POPCNT-leiðbeiningin, sem telur öll stillt bit í skrár, er það sem önnur bitamyndatengd trie-hönnun notar til að reikna barnshliðrun beint úr bitamyndinni. Við þurfum þess ekki vegna þess að Darts smíðin geymir þá hliðrun þegar í base-reit hnútsins.

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

Meðan við erum í þessu pökkuðum við reitunum fjórum á hvern hnút (bitamynd, base, tókenkenni og einkunn) í eina 64-bita skyndiminnislínu. Stök heimsókn á hnút dregur nú inn allt: einkunnina og tókenkennið sem við þurfum á enda hnútum að halda, auk bitamyndar og base fyrir næsta skref. Check-fylkið er aðeins notað við smíði og er sleppt úr keyrsluskipulaginu. Vinnusvæði vinnusvæðis er óathugað vegna þess að trie-smíði og lykkjuskipulag tryggja mörkin fyrir og eftir. Málamiðlunin er pláss: við 64 bæti á hvern hnút × ~780K hólf stækkar trie-ið úr ~9 MB í ~50 MB.

Niðurstöður við 514 tóken:

Vél	p50	p99	Leiðbeiningar	L2 aðgangar	L2 brestur%	L3 brestur%
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%
Grunnlína	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%
+ Bitamynd og innbyggð pökkun	65 µs	77 µs	1,06M	1,8K	20,53%	15,01%

Niðurstöður táknara við 514 tákn eftir að bæta við bitakorti og innbyggðri pökkun.

Klukkutími fellur kerfisbundið um önnur 4,5% við 514 tóken og stækkar með inntakslengd, nær 6-7% við 4k og 16k. Að sleppa check-fylkinu breytir trie-bætaskrefinu úr tveimur skyndiminnislínuhleðslum í eina, sem eru 2,5× færri L2 aðgangar á hverja umkóðun (1.8K á móti 4.6K einfaldra Darts). Brestutíðnin stökkur úr 6% í 20%, en stór hluti þess er nefnarinn: með innan við helmingi færri aðgöngum taka brestirnir stærri hlut.

Trie-gögnin eru um 50 MB (780.000 hnútar á 64 bæti hver). Í sjálfgefnu Linux ferli er minninu stutt af 4 KB síðum, þannig að allt trie-ið spannar um 12.000 aðskildar sýndarsíður, langt fram úr því sem fyrsta stigs gagnasíðuflýtiminni örgjörvans getur haldið (Sapphire Rapids er með 96 færslur). Hvert Viterbi skref snertir annan hnút, og yfir 512 tókena umkóðun brennum við u.þ.b. 9.000 hringjum í síðutöflugöngum, um 3% af kostnaðaráætlun á hverja umkóðun.

Lausnin er að styðja við trie-ið með 2 MB risasíðum í stað 4 KB síðna. Sömu 50 MB spannar nú 25 síður, passa alveg í síðuflýtiminnið, og sjálfar síðutöflumöppurnar hætta að keppa við trie-ið um L2 skyndiminni.

Linux er með tvær leiðir til að styðja minni með 2 MB síðum. Sú tækifærismiðaða er gagnsæjar risasíður (THP): forritið þitt biður kjarnann um að uppfæra minnissvæði úr 4 KB í 2 MB síður, og bakgrunnsþráður reynir að gera það þegar hann hefur tíma og samfellt eðlilegt minni tiltækt. Hinn kosturinn er að úthluta trie-inu beint úr forfráteknum risasíðupotti sem kjarninn tekur frá við ræsingu:

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

Potturinn þarf að vera til staðar á hýslinum (vm.nr_hugepages stillt við ræsingu). Á framleiðslutilvikum okkar eru 10.561 risasíður fráteknar; trie-ið eyðir 24 þeirra. Eftir mmap staðfestir /proc/<pid>/smaps svæðið: KernelPageSize: 2048 kB, Private_Hugetlb: 49152 kB.

Ávinningurinn er 3–12% klukkutími yfir inntaksstærðir, stöðugur og í hlutfalli við lengd vinnusetsins:

Tóken	Án risasíðna	Með risasíðum	Δ
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%

Töf táknara með og án risasíðna yfir inntaksstærðir.

Stærsti sigurinn er við 4k tóken, þar sem vinnusetið er nógu stórt til að síðutöfluumferð var virkilega að keppa við trie-gögn um L2 bandbreidd. Fyrir ofan 4k minnkar ávinningurinn vegna þess að L3 brestir ráða ríkjum og síðutöflugöng verða minni hluti af heildartíma.

Þegar þessum þremur hagræðingum er safnað saman er hér lokavélin mæld gegn hverjum öðrum RoBERTa táknara sem við prófuðum. Hlið við hlið við innfædd C++ SentencePiece og C IREE tvíundarskrár, prófuðum við einnig tilbúnu Rust umbúðapakka sem framleiðslunotandi myndi ná í, sentencepiece og iree-tokenizer. Pakkinn sentencepiece mælir 1,6-1,9× hærri seinkun en innfædd C++ tvíundarskrá á hverri inntaksstærð, þar sem yfirbyggingin kemur frá því að umbúðirnar úthluta nýjum lista yfir táknstykkja, þar sem hvert um sig heldur sínu eintaki af stykkitextanum, á hverja umkóðun. IREE-táknarapakki stærðarstillir innri biðminni sitt við hvert inntak, sem kemur inni vegna stöðugrar úthlutunar á hverja umkóðun sem innfædda IREE tvíundarskráin greiðir óháð inntaksstærð, og það skiptir mestu máli við stutt inntak þar sem úthlutunin myndi annars ráða yfir raunverulegri táknunarvinnu. Við framleiðslu inntakslengdir jafnast fastur kostnaðurinn út og eigin kallkostnaður umbúðanna við að afrita tóken aftur inn í Rust ýtir seinkun þeirra yfir seinkun innfæddu tvíundarskrárinnar.

p50- og p99-töf per kóðun yfir táknaraútfærslur og inntaksstærðir.

Lokavélin keyrir sama Viterbi yfir sama 250.000 tókena orðasafn, úthlutar engu á heitu leiðinni og skilar tóken-nákvæmu úttaki gegn tilvísuninni. Hvert bætaskref er nú stök 64-bita skyndiminnislínuhleðsla, eitt bitapróf og ein heiltölusamlagning, niður úr HashMap leit, úthlutunarkalli og nokkrum sértilviksgreinum í grunnlínuútgáfunni. Leiðbeiningar á hverja umkóðun féllu úr 3.66M í 1.04M, sem er 3,5× lækkun. Klukkutími passar við það hlutfall á stuttum inntökum og breikkar meira á löngum inntökum, þar sem úthlutanir tilvísunarinnar á hvern tóken byrja að flæða yfir L2 og L3.

Í framkvæmd minnkaði þetta verk örgjörvanotkun í forvinnslulagi ályktunarstöflunnar okkar um 5–6× og stytti seinkun endurraðara um tugi millisekúndna.

Stærsti hluti seinkunarminnkunarinnar kom frá léttvægum breytingum sem fjarlægðu sóaða vinnu: að sleppa úthlutunum á hverja umkóðun, skipta út HashMap-barna trie fyrir tvöfalt fylki, og strika út yfirbyggingu almenns API. Að nota fyrirliggjandi bitamynd á hvern hnút sem gildisstaðfestingu og styðja við trie-ið með 2 MB risasíðum saman náðu 10-20% ofan á stærri skiptið yfir í tvöfalt-fylkis trie, eftir inntaksstærð.

Tilbúnir Rust umbúðapakkar í kringum SentencePiece og IREE sýna sama punkt öfugt. Ofan á innfædda C og C++ táknara eru FFI-mörkin og úthlutanir á hvert kall sem umbúðirnar kynna til sögunnar sýnilegar í seinkunartölum. Rust-kóðinn fyrir loka Viterbi kódarann er fáanlegur á 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}
}

Hvatning

Viterbi reikniritið

Tilvísunarútgáfa

Athugasemd um forvinnslu

Hvar tilvísunarútgáfan eyðir tíma sínum

Hvernig við mældum

Af hverju SentencePiece og IREE eru hraðari: Tvöfalda fylkis trie-ið

Grunnlína: Núll-úthlutunar útgáfa af tilvísuninni

Hagræðing 1: Tvöfalt-fylkis trie án aukasöfnunar

Bestun 2: Bitkort og innbyggð pökkun

Bestun 3: Stórar síður fyrir trie

Loka samanburður

Lokaorð

Heimildir

Tilvitnun