Unigram токенизаторының CPU өнімділігін жақсарту

Біз Unigram токенизаторын өнімділікке бағытталған арнайы жоба ретінде нөлден бастап қайта іске қостық. Өндірістік кіріс ұзындықтарында жаңа энкодер Hugging Face tokenizers crate-пен салыстырғанда p50 кідірісін шамамен 5 есеге, SentencePiece (C++) пен салыстырғанда ~2 есеге, ал IREE токенизаторымен (C) салыстырғанда ~1,5 есеге қысқартады, сонымен бірге тұрақты күйдегі үйінді (heap) шығындары жоқ. Өндірісте бұл біздің инференция стекіндегі CPU жүктемесін 5–6 есеге азайтып, қайта ранкердің кідірісінен ондаған миллисекундты қысқартты.

LLM инференциясының құны көбінесе GPU жұмысы ретінде қарастырылады: KV кэштері, назар аудару ядролары (attention kernels), сарапшыларды бағыттау. Бірақ өндірістік трафиктің айтарлықтай бөлігі шекаралық трансформерлерден екі-үш рет кішірек әлдеқайда шағын модельдерде жұмыс істейді. Эмбеддинг модельдері, жіктеуіштер және ранкерлер әлі де GPU-да жұмыс істейді, бірақ тура өту (forward pass) оның айналасындағы нәрселердің барлығы маңызды болатындай қысқа.

Ең анық мысал — әр сұрау бойынша жүздеген кандидат құжатты бағалайтын ранкер. Шағын модельмен GPU есептеулері әдетте бір таңбалы миллисекундта аяқталады, бірақ әрбір кіріс мәтінді сөздік идентификаторларына (vocabulary IDs) айналдырып, алдымен CPU жағында токенизациядан өтуі керек. Топтама үлкен болған кезде, бұл сұраудың жалпы кідірісінің айтарлықтай бөлігін құрауы мүмкін.

Бұл жұмыс SentencePiece көмегімен оқытылған 250K токендік Unigram сөздігі бар XLM-RoBERTa бағытталған. Дәл бапталған RoBERTa отбасылық энкодерлері – рангілеу, іздеу және ұқсастық тапсырмалары үшін жиі таңдалатын таңдау. Біз бұл жерде бір ағынды кодтау кідірісін хабарлаймыз; өндірісте біз rayon көмегімен ядролар арасында параллельді түрде орындаймыз.

Осы жазба бойы біз Hugging Face компаниясының tokenizers crate кітапханасын өзіміз бенчмарк жасайтын анықтамалық ретінде қарастырамыз, өйткені бұл көптеген командалар таңдайтын әдепкі Rust токенизаторы болып табылады. SentencePiece (C++) және IREE (C) басқа екі негізгі өндірістік іске асыру ретінде салыстыру үшін енгізілген.

2018 жылы Кудо ұсынған (Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates) және SentencePiece ішінде жеткізілген Unigram токенизациясы сегментацияны ең ықтимал жол мәселесі ретінде қарастырады: әрбір сөздік токенінде үйренілген лог-ықтималдық бар, ал энкодер токен ұпайларының қосындысы ең жоғары мәнді беретін сегментацияны таңдайды. Бұл мәселе граф қабаттары ретінде байт позициялары және үздіксіз байт ауқымын қамтитын шеттер (edges) ретінде сөздік токендері бар Витерби алгоритмі (1967) арқылы шешіледі. Рекурренттік қатынас — байт позициялары бойынша бір өлшемді DP (динамикалық бағдарламалау):

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

Сыртқы цикл кіріс ұзындығы бойынша сызықтық болып табылады, әр позицияда ең ұзын сөздік токенімен шектелген (XLM-RoBERTa үшін 48 UTF-8 байты). Ішкі trie (префикс ағашы) арқылы жүру — бұл өте маңызды жол (hot path): 16k токендік кірісте ол жүздеген мың өткелдерді орындап, әр кодтау үшін он миллиондаған нұсқауларды (instructions) аяқтайды.

Hugging Face компаниясының tokenizers v0.22 нұсқасы кері іздеуге арналған хэш-картаны (hash-map) және әрбір trie түйініндегі hash-map-children қолдана отырып, рекурренттік қатынасты тікелей іске асырады:

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
}

Ал ішкі цикл (қысқартылған түрі) – әрбір префикс-іздеу сәйкестігі жаңа жолды (string) бөліп алады, содан кейін хэш-картаны тексереді:

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
}

Бұл код түсінікті Rust тілінде жазылған, бірақ бастапқы код деңгейінде көрінбейтін көптеген жұмыстар орындалады. Келесі бөлімде уақыттың қайда кететіні талданады.

Витерби жұмыс істемес бұрын, кіріс деректер Юникодты нормалаудан (NFKC) және сөз шекараларын таңбалаудан өтеді. Профилизация біздің сценарийлерімізде алдын ала өңдеудің жалпы кодтау уақытының 5%-ынан аз болатынын көрсетеді, сондықтан біз жазбаның қалған бөлігінде Витербидің тура өтуіне (forward pass) назар аударамыз.

CPU кодын жылдамдатудың екі жолы бар: аз нұсқауларды орындау немесе жоғарырақ IPC алу. Cachegrind біріншісін өлшейді, perf stat екіншісін өлшейді. Осы жазбадағы әрбір оңтайландыру осылардың біреуіне немесе екеуіне де әсер етеді.

CPU төрт нәрседе кідіреді: кэш жіберіп алулары (L1d ~4 цикл, L3-тің DRAM-ға жіберіп алуы жүздеген цикл), ретсіз орындау қозғалтқышы (out-of-order engine) параллельді ете алмайтын тәуелді жүктеу тізбектері, тармақты қате болжаулар (әр қате болжау сайын ~15-20 цикл тазартылады) және аллокатор шақырулары. Анықтамалық unigram қозғалтқышының іске асырылуы осы төрт нәрсенің барлығына тап болады:

Бөгеуіл (Bottleneck)	Механизм	Өлшенген әсері
Әр сәйкестік үшін аллокация	Сәйкестендірілген байттарда String::from_utf8 және әрбір trie сәйкестігі үшін AHashMap іздеуі; токен ID-і қазірдің өзінде жапырақта бар, бірақ сілтеме оны онда сақтамайды	512 токенде 7 295 аллокация, 1k-та 14 542, 16k-та 299 171
Әр байт үшін көрсеткішті қуу (pointer chase)	Әрбір trie түйініндегі AHashMap, келесі байтты хэштеу және әр қадам сайын екі көрсеткішті дереференциялау; сонымен қатар Node құрылымы is_leaf сияқты салқын өрістерді де біріктіріп, әр кірген сайын оларды кэшке тартады	L1d жіберіп алу жиілігі төмен күйінде қалады (1k кезінде ~2.5%), өйткені аллокатордың белсенді беттері L1-де болады; бұл шығын тәуелді жүктеу кідірісі ретінде көрінеді
Ұзын кірістердегі L2 трэшингі (thrashing)	DP кестесі, префикс көмектік жады және шығыс токен тізімі әр шақыру сайын жаңадан бөлінеді	Жиынтық аллокация көлемі ядро сайығындағы 2 МБ L2 кэшінен асып кеткендіктен, L2 жіберіп алу жиілігі 128 токендегі 12%-дан 16k токенде 50%-ға дейін өседі

Токенизатордың тар орындарын, механизмдерін және өлшенген әсерлерін қараңыз.

Басты шығын — әр сәйкестік үшін жасалатын аллокация. 1k токен кезінде анықтамалық іске асыру IPC 2.8 кезінде әр кодтау үшін шамамен 7M нұсқауды аяқтайды (олардың көпшілігі аллокатор шақырулары мен жолды түрлендірулерде). L2 жіберіп алулары тек ~1k токеннен асқанда ғана маңызды болады, себебі жиынтық аллокация көлемі ядро деңгейіндегі кэштен асып түседі.

Кіріс өлшемі бойынша эталондық токенизатордың p50 және p99 кідірісі.

Кіріс өлшемі бойынша эталондық токенизатордың L2 кэшті өткізіп алу жиілігі.

Кіріс өлшемдері бойынша эталондық токенизатордың бір encode-қа бөлетін байт саны.

Токен сайынғы аллокация тұрақты болып қалады: кіріс өлшеміне қарамастан, бір токенге шамамен 2 КБ және ~18 аллокация келеді. Кідірістің сызықтық еместігі L2-ден туындайды: жиынтық байттар 1k токен шамасында 2 МБ-тан асады, жіберіп алу жиілігі 8%-дан ~50%-ға дейін өседі, ал p99 қисығы соған сәйкес өзгереді.

Біз бірдей XLM-RoBERTa моделіне қарсы бірдей Unigram алгоритмін орындайтын үш өндірістік токенизаторды салыстырамыз:

Қозғалтқыш (Engine)	Тіл	Trie (Префикс ағашы)
Hugging Face	Rust	HashMap-children префикс ағашы
SentencePiece	C++	Darts екі массивті trie
IREE токенизаторы	C	Darts екі массивті trie

Салыстыруда қолданылған токенизатор іске асырулары, тілдер және trie-бейнелеулер.

Біз SentencePiece пен IREE-ні олардың Rust орамалары (wrappers) арқылы емес, тікелей C/C++ FFI арқылы қосамыз; орамалар түпкілікті кітапхананың шығынына кірмейтін шақыру сайынғы аллокациялар мен жолды түрлендірулерді қосады.

Барлық қозғалтқыштар толық оңтайландырулармен құрастырылған (O3, жергілікті мақсатты бағыттау, сілтеме уақытындағы оңтайландыру - link-time optimization). Өлшеулер Intel Xeon Platinum 8488C процессорындағы бір тынық ядроға бекітіліп орындалды. Әрбір қозғалтқыш пен кіріс өлшемі үшін біз қабырғалық уақыт кідірісін (p50 және p99, 1000 жылыту итерациясынан кейінгі 10 000 итерация), Valgrind cachegrind арқылы аяқталған нұсқауларды, perf stat аппараттық есептегіштерінен IPC және кэшті жіберіп алу жиілігін, сондай-ақ өлшенген терезе айналасындағы жаһандық аллокатор орамасы арқылы есептелген үйінді аллокацияларын жинаймыз.

514 токенде (512-ден +2 артық болуы BOS/EOS қосуына байланысты):

Іске асыру	p50 кідірісі	Нұсқаулар (Instructions)	IPC	Аллокациялар
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

514 токен кезіндегі токенизатордың кідірісі, нұсқаулар саны, IPC және бөлінулері.

SP және IREE кідірісі анықтамалық іске асырудың шамамен үштен бірін құрайды. Олар шамамен екі есе аз нұсқауларды аяқтайды, жоғарырақ IPC-пен жұмыс істейді және бір-екі есе аз аллокация жасайды.

SentencePiece пен IREE екеуі де 1989 жылы Aoe ұсынған екі массивті trie құрылымын пайдаланады (Aoe, 1989; Karoonboonyanan). Trie екі жалпақ бүтін массивте, base және check түрінде кодталған:

cpp

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

Ұрпақ түйінді (child) іздеу келесідей орындалады:

cpp

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

Trie арқылы өтудің әрбір қадамы тек екі массивті оқуды, бір бүтін сан қосуды және бір салыстыруды талап етеді, мұнда ешқандай хэштеу, көрсеткіштерді қуу және түйін сайынғы үйінді аллокациясы жоқ. Құрылым әрбір түйінді соның ұрпақтары валидация массивіндегі бос орынға түсетіндей етіп орналастырады, бұл бірнеше ата-аналарға өз ұрпақтары жүретін байты бойынша ерекшеленген жағдайда аймақтарды ортақ пайдалануға мүмкіндік береді.

XLM-RoBERTa-ның 250 мыңдық сөздік қоры үшін бүкіл trie шамамен 9 МБ үздіксіз жадқа сыяды (әр слотқа арналған ығысу, валидация және токен ID үшін ~780 мың слот × 12 байт). Бір encode шақыруының қызған жұмыс жиыны шамамен 100 КБ, бұл L2 кэшке оңай сыйады, ал аппараттық prefetcher әдеттегі қатынау үлгісін бірден ұстап алады.

Керісінше, анықтамалық іске асыру әр түйін үшін бала түйіндердің хэш-картасын сақтайды, бұл әр байт қадамына шамамен төрт тәуелді жүктеуді қажет етеді. Байтты хэштеу, букетті (bucket) жүктеу, букет жазбасына көрсеткіш арқылы өту, үйіндідегі (heap) бала түйінге басқа көрсеткіш арқылы өту, содан кейін келесі байт үшін өзінің хэш-картасын тексеру. Үйінді объектілері шашырап кетеді және жүктеулердің көбісі кэшті жіберіп алады.

SP пен IREE екеуі де токен идентификаторын тікелей trie түйінінде сақтайды. Анықтамалық trie іске асырылуы тек сәйкес келген байттарды қайтарады, сондықтан энкодер әр сәйкестік үшін жаңа жолды бөліп алуы, токен идентификаторын қалпына келтіру үшін оны қосалқы хэш-картадан іздеуі және ұпайды бөлек вектордан оқуы керек. SP идентификаторды trie сақталған мәні ретінде қайтарады және ұпайды жалпақ float массивінен оқиды:

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 барлық сәйкестіктерді бір шақыруда қайтарудың орнына күйі бар курсор API (stateful cursor API) пайдаланады, бірақ шығын моделі бірдей: токен идентификаторлары мен ұпайлар жалпақ массив индекстері ретінде қолжетімді, trie арқылы жүргенде ешқандай аллокация немесе хэштеу орындалмайды. IREE әр кодтау үшін тек бір шығыс буферін бөледі; SP қосымша түрде DP кезінде әр сәйкестік үшін тор түйінін (lattice node) бөледі, бұл 514 токенде шамамен 1 559 аллокацияны құрайды.

Trie-ні өзгертпе бұрын, біз алгоритм шығынын іске асыру шығынынан бөліп аламыз: қажетсіз жұмыс алынып тасталғанда анықтамалық код қаншалықты жылдам жұмыс істейді?

Базис анықтамалықтың hash-map-children trie құрылымын сақтайды, бірақ екі өзгеріс жасайды. Шақырушыға тиесілі көмектік жады құрылымы (scratch struct) DP кестесін, алдын ала өңделген байттарды және шығыс токен идентификаторларын ұстайды, сондықтан қыздырудан кейін маңызды жол (hot path) ешқандай аллокация жасамайды. Токен идентификаторы мен ұпай тікелей trie түйінінде сақталады, бұл сәйкестік сайынғы жолды түрлендіруді және қосалқы хэш-карта іздеуді жояды.

Ішкі цикл:

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

Бұл бірдей алгоритм, бірдей trie пішіні мен бірдей қатынас үлгісі бар, тек аллокациялар мен артық іздеулер жоқ. 514 токендегі нәтижелер:

Қозғалтқыш	p50	Нұсқаулар (Instructions)	IPC	Аллокациялар
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

514 токен кезіндегі қолданыстағы токенизатор іске асыруларымен салыстырылған нөлдік бөлу негізі.

Сәйкестік сайынғы жолды материалдауды және қосымша хэш-карта іздеуін алып тастау анықтамалықпен салыстырғанда нұсқауларды 2,4 есеге қысқартады. Олармен бірге IPC төмендейді (2,86 → 2,62), өйткені бұрын аллокатор жұмысының артында жасырын болған хэш-карта көрсеткішін қуу қазір әр байт үшін басты шығынға айналды.

Кіріс өлшемі бойынша эталондық және нөлдік бөлу негізіндегі токенизатордың p50 және p99 кідірісі.

Кіріс өлшемі бойынша эталондық және нөлдік бөлу негізіндегі токенизатордың L2 кэшті өткізіп алу жиілігі.

Базис әр өлшемде анықтамалықпен салыстырғанда p50 кідірісін 2-3 есеге қысқартады, ал оның L2 жіберіп алу жиілігі анықтамалықтың 8-48%-ымен салыстырғанда 2k токенге дейін 2-3% шамасында қалады. Қалған шығын — HashMap көрсеткішін қуу, оны келесі бөлім шешеді.

Хэш-карта trie — бұл көрсеткішті қуу (pointer chase). SP пен IREE бұл мәселені екі массивті trie арқылы шешеді (алдыңғы бөлімді қараңыз), және біз де сол деректер құрылымын аламыз. Айырмашылығы сонда, SP пен IREE — бұл ағынды кірісті, шығыс офсеттерін және бірнеше кодтау режимдерін қолдайтын жалпы мақсаттағы кітапханалар; бұл икемділік оларға trie айналасында қосымша есеп жүргізу шығындарын тудырады (SP-де тор, IREE-де сегіз сатылы конвейер). Бізге бұлардың ешқайсысы қажет емес, сондықтан біз trie-ні тікелей Витерби циклінің ішіне енгізіп (inline), қалғанын алып тастаймыз.

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

Бір байт қадамы екі массивті оқуды, бүтін сан қосуды және салыстыруды қажет етеді. Бүкіл trie шамамен 9 МБ, бірақ кез келген бір кодтау оның тек ~100 КБ ғана шолады, сондықтан маңызды деректер L2 ішінде қалады.

Қозғалтқыш	p50	p99	Нұсқаулар (Instructions)	L2 жіберіп алу %	L3 жіберіп алу %
Hugging Face	327 µs	3,340 µs	3.66M	8.17%	14.66%
SentencePiece	127 µs	1,140 µs	1.82M	4.74%	4.07%
IREE	111 µs	132 µs	1.61M	5.82%	3.87%
Базис (Baseline)	155 µs	1,170 µs	1.53M	2.59%	16.66%
+ Darts	68 µs	80 µs	1.10M	6.45%	11.42%

Қос массивті trie-ді енгізгеннен кейінгі токенизатордың кідірісі, нұсқаулар саны және кэшті өткізіп алу жиілігі.

Қабырғалық уақыт базистен 2,3 есеге, ал анықтамалықтан 4,8 есеге төмендейді. Нұсқаулар базиске қарағанда тағы 28%-ға азаяды. Тор мен конвейерді алып тастау бізге бірдей trie пішінінде SP-тің 1.82M және IREE-нің 1.61M нұсқауларына қарсы әр кодтау үшін 1.10M нұсқауды аяқтауға мүмкіндік береді; айырмашылық — бізге қажет емес жалпы мақсаттағы API үшін сақтайтын есеп жүргізу шығындары.

1-оңтайландырудағы Darts trie құрылымы әр байт қадамына екі тәуелді жүктеуді қажет етеді. Біріншісі — ата-ананың base офсеті, содан кейін ата-ананың оған ие екенін растау үшін кандидат бала ұрпақ слотындағы check жазбасы. Check жазбасы тек иелігін тексереді. Дәл осы сұраққа қай байттардың ұрпақтары бар екенін жазып алатын түйін сайынғы битмап арқылы жауап беруге болады. Екі массивті trie құрылымы бойынша, ата-ананың битмапындағы b байтына арналған бит дәл сол байт үшін кандидат слот ата-анаға тиесілі болған кезде орнатылады. Битмап пен check массиві бірдей ақпаратты тасымалдайды, сондықтан біз check массивін орындалу уақыты құрылымынан (runtime layout) толығымен алып тастай аламыз.

Битмапты іздеу бір 64 биттік сөзге қарсы бір биттік тестке дейін жинақталады, бұл шамамен бір циклде орындалады. Тіркелімдегі орнатылған биттердің барлығын санауға арналған қатысты POPCNT нұсқауы — бұл басқа битмаппен индекстелетін trie жобалары битмаптан тікелей бала ұрпақ офсетін есептеу үшін қолданатын нәрсе. Бізге бұл қажет емес, өйткені Darts құрылымы бұл офсетті түйіннің base өрісінде қазірдің өзінде сақтайды.

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

Осы ретте біз түйін сайынғы төрт өрісті (битмап, base, токен идентификаторы және ұпай) бір 64 байттық кэш жолына жинақтаймыз (пакуем). Енді бір түйінге кіру барлығын бірден әкеледі: терминалдық түйіндерде қажет болатын ұпай мен токен идентификаторы, сонымен қатар келесі қадамға арналған битмап пен base. Check массиві тек құрастыру кезінде ғана қолданылады және орындалу уақыты орналасуынан алынып тасталады. Маңызды жолдағы (hot path) индекстеу тексерілмейді (unchecked), өйткені trie құру және цикл құрылымы шекараларды қазірдің өзінде кепілдендіреді. Мұның айырбасы — кеңістік: әр түйінге 64 байт × ~780K слот кезінде trie ~9 МБ-тан ~50 МБ-қа дейін өседі.

514 токендегі нәтижелер:

Қозғалтқыш	p50	p99	Нұсқаулар (Instructions)	L2 қатынастары (accesses)	L2 жіберіп алу %	L3 жіберіп алу %
Hugging Face	327 µs	3,340 µs	3.66M	15.0K	8.17%	14.66%
SentencePiece	127 µs	1,140 µs	1.82M	7.5K	4.74%	4.07%
IREE	111 µs	132 µs	1.61M	4.7K	5.82%	3.87%
Базис (Baseline)	155 µs	1,170 µs	1.53M	6.1K	2.59%	16.66%
+ Darts	68 µs	80 µs	1.10M	4.6K	6.45%	11.42%
+ Битмап және ішкі буып-түю	65 µs	77 µs	1.06M	1.8K	20.53%	15.01%

Bitmap және inline packing қосқаннан кейінгі 514 токендегі токенизатор нәтижелері.

Қабырғалық уақыт 514 токенде жүйелі түрде тағы 4,5%-ға төмендейді және кіріс ұзындығымен бірге өсіп, 4k және 16k кезінде 6-7%-ға жетеді. Check массивін алып тастау байт сайынғы trie қадамын екі кэш жолының жүктеуінен біреуге дейін қысқартады, бұл әр кодтау үшін 2,5 есе аз L2 қатынастарын береді (қарапайым Darts үшін 4.6K қарсы 1.8K). Жіберіп алу жиілігі 6%-дан 20%-ға дейін секіреді, бірақ мұның көбі бөлімге (denominator) байланысты: қатынастар екі еседен астам аз болғандықтан, орын алған жіберіп алулар жалпы уақыттың үлкен бөлігін алады.

Trie деректері шамамен 50 МБ (әрқайсысы 64 байт болатын 780 000 түйін). Әдепкі Linux процесінде бұл жад 4 КБ беттермен қамтамасыз етіледі, сондықтан толық trie шамамен 12 000 бөлек виртуалды беттерді қамтиды, бұл процессордың бірінші деңгейдегі Translation Lookaside Buffer (TLB) сыйдыра алатын көлемінен әлдеқайда көп (Sapphire Rapids-та 96 жазба бар). Әрбір Витерби қадамы басқа түйінді қозғайды, ал 512 токендік кодтау кезінде біз бет-кесте (page-table) өткелдерінде шамамен 9 000 циклды жоғалтамыз, бұл әр кодтау бюджетінің шамамен 3%-ы.

Мұны түзету жолы — trie-ні 4 КБ беттердің орнына 2 МБ үлкен беттермен (huge pages) қамтамасыз ету. Сол 50 МБ қазір 25 бетті қамтиды, TLB буферіне толығымен сыяды, ал бет-кесте директорияларының өзі trie-мен L2 кэші үшін бәсекелесуін тоқтатады.

Linux жүйесінде жадты 2 МБ беттермен қамтамасыз етудің екі жолы бар. Біріншісі — мөлдір үлкен беттер (transparent huge pages - THP): бағдарламаңыз ядродан жад аймағын 4 КБ-тан 2 МБ беттерге жаңартуды сұрайды, ал фондық ядро треді уақыты мен қолжетімді үздіксіз физикалық жады болған кезде оны жасауға тырысады. Екінші балама — ядро жүктелу кезінде бөліп қоятын алдын ала резервтелген үлкен беттер бассейнінен (huge-page pool) trie-ні тікелей бөліп алу:

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

Бассейн хостта болуы тиіс (жүктелу кезінде орнатылған vm.nr_hugepages). Біздің өндірістік даналарымызда 10 561 үлкен бет сақталған; trie олардың 24-ін тұтынады. mmap кейін /proc/<pid>/smaps аймақты растайды: KernelPageSize: 2048 kB, Private_Hugetlb: 49152 kB.

Ұтыс жұмыс жиынтығының ұзындығына пропорционалды және тұрақты түрде кіріс өлшемдері бойынша 3–12% қабырғалық уақытты құрайды:

Токендер	Үлкен беттерсіз	Үлкен беттермен	Δ
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%

Үлкен беттермен және онсыз токенизатордың кіріс өлшемдері бойынша кідірісі.

Ең үлкен ұтыс 4k токенде байқалады, мұнда жұмыс жиынтығы бет-кесте трафигі trie деректерімен L2 өткізу қабілеті үшін белсенді түрде бәсекелесетіндей үлкен. 4k-тан асқан соң ұтыс азаяды, өйткені L3 жіберіп алулары басым болып, бет-кесте өткелдері жалпы уақыттың кішірек бөлігіне айналады.

Үш оңтайландыруды біріктіре отырып, мұнда біз сынақтан өткізген басқа кез келген RoBERTa токенизаторына қарсы өлшенген соңғы қозғалтқыш берілген. Жергілікті C++ SentencePiece және C IREE бинарлы файлдарымен қатар, біз өндірістік пайдаланушы қол жеткізетін дайын Rust орама кратерін де сынақтан өткіздік: sentencepiece және iree-tokenizer. sentencepiece кратері әрбір кіріс өлшемінде жергілікті C++ бинарлы файлына қарағанда 1.6-1.9 есе жоғары кідірісті көрсетеді, бұл қосымша шығын ораманың әр кодтау сайын әрқайсысы өзінің бөлік мәтінінің көшірмесін ұстайтын токен бөліктерінің жаңа тізімін бөлуінен туындайды. iree-tokenizer кратері әрбір кіріс өлшемі үшін ішкі буферінің өлшемін бейімдейді, бұл жергілікті IREE бинарлы файлы кіріс өлшеміне қарамастан төлейтін тұрақты кодтау сайынғы аллокацияны болдырмайды, және бұл аллокация нақты токенизация жұмысынан басым болатын қысқа кірістерде ең маңызды болып табылады. Өндірістік кіріс ұзындықтарында тұрақты шығын амортизацияланады және ораманың токендерді қайтадан Rust тіліне көшіруден болатын шақыру сайынғы қосымша шығыны оның кідірісін жергілікті бинарлы файлдың кідірісінен жоғары көтереді.

Токенизатор іске асырулары мен кіріс өлшемдері бойынша бір encode-қа арналған p50 және p99 кідірісі.

Соңғы қозғалтқыш сол 250 000 токендік сөздік бойынша сол Витербиді орындайды, маңызды жолда ештеңе бөлмейді және анықтамалыққа сәйкес дәл токендік шығыс өндіреді. Байт сайынғы әрбір қадам енді HashMap тексеруінен, аллокатор шақыруынан және базистік іске асырудағы бірнеше арнайы жағдайлы тармақтардан төмендетіліп, бір 64 байттық кэш жолын жүктеу, бір битмап тексеруі және бір бүтін сан қосу болып табылады. Әр кодтау үшін нұсқаулар 3.66M-нан 1.04M-ға дейін азайды, бұл 3.5 еселік төмендеу. Қабырғалық уақыт қысқа кірістерде бұл қатынасқа сәйкес келеді және ұзақ кірістерде одан әрі кеңейе түседі, мұнда анықтамалықтың токен сайынғы аллокациялары L2 және L3 кэштерінен асып түсе бастайды.

Іс жүзінде бұл жұмыс инференция стегіміздің алдын ала өңдеу қабатындағы CPU жүктемесін 5-6 есеге азайтып, қайта ранкердің кідірісінен ондаған миллисекундты қысқартты.

Кідірістің негізгі бөлігі бос жұмысты жойған жеңіл өзгерістерден келді: кодтау сайынғы аллокацияларды тоқтату, HashMap-children trie құрылымын екі массивті trie-мен алмастыру және жалпы API (generic-API) шығындарын алып тастау. Қолданыстағы түйін сайынғы битмапты жарамдылықты тексеру ретінде пайдалану және trie-ні 2 МБ үлкен беттермен қамтамасыз ету кіріс өлшеміне байланысты екі массивті trie-ге жасалған үлкен ауысудың үстіне 10-20% үлес қосты.

SentencePiece пен IREE айналасындағы дайын Rust орама кратері де дәл осы жағдайды керісінше көрсетеді. Жергілікті C және C++ токенизаторларының үстіне, орамалар енгізетін FFI шекарасы мен шақыру сайынғы аллокациялар кідіріс мәндерінде көрінеді. Соңғы Витерби энкодерінің Rust бастапқы коды github.com/perplexityai/pplx-garden мекенжайында қолжетімді.

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

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

IREE токенизаторы — https://github.com/iree-org/iree

Kudo, T. (2018). Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates. https://arxiv.org/abs/1804.10959

Viterbi, A. J. (1967). Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Transactions on Information Theory. https://en.wikipedia.org/wiki/Viterbi_algorithm

Aoe, J. (1989). An efficient digital search algorithm by using a double-array structure. IEEE Transactions on Software Engineering. https://ieeexplore.ieee.org/document/31365/

Karoonboonyanan, T. An Implementation of Double-Array Trie. https://linux.thai.net/~thep/datrie/datrie.html

POPCNT (x86) — https://www.felixcloutier.com/x86/popcnt

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

Мотивация

Витерби алгоритмі

Анықтамалық іске асыру

Алдын ала өңдеу туралы ескерту

Анықтамалық іске асыру уақытын қайда жұмсайды

Біз қалай өлшедік

Неліктен SentencePiece пен IREE жылдамырақ: Екі массивті Trie

Базис (Baseline): Анықтамалық кодтың нөлдік аллокациялық порты

1-оңтайландыру: Қосымша абстракцияларсыз екі массивті Trie

2-ші оңтайландыру: Битмап және ішкі буып-түю

3-ші оңтайландыру: Триге арналған үлкен беттер

Қорытынды салыстыру

Қорытынды ойлар

Әдебиеттер

Дәйексөз