Побољшање перформанси CPU-а за униграм токенизер

Поново смо имплементирали наш Unigram токенизер од нуле као фокусирани пројекат перформанси. При дужинама улаза у производњи, нови енкодер смањује p50 кашњење за отприлике 5× у поређењу са Hugging Face tokenizers крајем, ~2× у поређењу са SentencePiece (C++) и ~1.5× у поређењу са IREE-овим токенизером (C), без икаквих додељивања меморије на гомили у стационарном стању. У производњи ово је смањило искоришћеност процесора у нашем инферентном стеку за 5-6× и скинуло двоцифрени број милисекунди са кашњења реранкера.

Трошак инференце код LLM-а се обично посматра као рад графичке картице (GPU): KV кешови, језгра пажње, рутирање експерата. Међутим, значајан део производног саобраћаја ради на много мањим моделима, два до три реда величине мањим од граничних трансформатора. Модели за уградњу (embedding), класификатори и реранкери и даље раде на GPU-у, али је пролазни пролаз довољно кратак да све око њега почиње да буде важно.

Најјаснији пример је реранкер који оцењује стотине кандидата докумената по захтеву. Са малим моделом, GPU прорачун се обично завршава за једноцифрене милисекунде, али сваки унос и даље прво мора да прође кроз токенизацију на страни процесора (CPU), претварајући текст у ID-ове речника. Када је серија велика, то може да чини значајан део укупног кашњења захтева.

Овај рад је усмерен на XLM-RoBERTa, Unigram речник од 250 хиљада токена обучен помоћу SentencePiece-а. Додатни енкодери из породице RoBERTa су уобичајени избор за задатке рангирања, претраге и сличности. Свуда извештавамо о кашњењу по енкодовању са једном нити; у производњи вршимо паралелизацију по језгрима користећи rayon.

Током овог чланка третирамо Hugging Face-ов tokenizers crate као референцу са којом поредимо перформансе, пошто је то подразумевани Rust токенизер за који се већина тимова одлучује. SentencePiece (C++) и IREE (C) су укључени ради поређења као друге две велике производне имплементације.

Unigram токенизација, коју је увео Кудо 2018. године (Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates) и која се испоручује у оквиру SentencePiece-а, сегментацију посматра као проблем путање са највећом вероватноћом: сваки токен речника има научену логариттарску вероватноћу, а енкодер бира сегментацију чији резултати токена дају највећу вредност. Овај проблем се решава Витербијевим алгоритмом (1967), са позицијама бајтова као слојевима графа и токенима речника као гранама које обухватају контигуални опсег бајтова. Рекурентна релација је једнодимензионални динамички програм над позицијама бајтова:

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

Спољна петља је линеарна у односу на дужину улаза, ограничена на свакој позицији најдужим токеном речника (48 UTF-8 бајтова за XLM-RoBERTa). Унутрашња шетња кроз стабло (trie) представља критичну путању: на уносу од 16k токена, она извршава стотине хиљада прелаза и извршава десетине милиона инструкција по енкодовању.

Hugging Face-ов tokenizers v0.22 директно имплементира рекурентну релацију, са хеш-табелом за обрнуто претраживање и децом хеш-табеле на сваком чвору стабла:

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
}

И унутрашња петља (поједностављена) – свака подударност при претрази префикса додељује нову ниску а затим испитује хеш-табелу:

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% од укупног времена енкодовања у нашим сценаријима, тако да се у остатку чланка фокусирамо на пролаз унапред Витербијевог алгоритма.

Постоје два начина да се убрза процесорски код: извршити мање инструкција или постићи већи IPC (инструкција по циклусу). Cachegrind мери прво, perf stat мери друго. Свака оптимизација у овом чланку се своди на једно или друго.

Процесори застојују због четири ствари: промашаја кеша (L1d ~4 циклуса, промашај L3-до-DRAM-а је стотине хиљада), ланаца зависних учитавања које механизам ван редоследа не може да паралелизује, погрешних предвиђања гранања (~15-20 циклуса се поништава по погрешној претпоставци) и позива алокатора. Референтна имплементација униграм енкодера погађа све четири:

Уско грло	Механизам	Измерен утицај
Алокација по подударности	String::from_utf8 на подударним бајтовима плус AHashMap претрага по подударности стабла; ID токена је већ у листовима, али га референца тамо не чува	7.295 алокација на 512 токена, 14.542 на 1k, 299.171 на 16k
Праћење показивача по бајту	AHashMap на сваком чвору стабла, хеширање следећег бајта и деференцирање два показивача по кораку; структура Node такође пакује хладна поља попут is_leaf, увлачећи их у кеш при свакој посети	Стопа промашаја за L1d остаје ниска (~2.5% на 1k) зато што вруће странице алокатора живе у L1; трошак се појављује као кашњење зависног учитавања
Гушење L2 кеша на дугим улазима	DP табела, привремени префикс и излазна листа токена се све новоалоцирају при сваком позиву	Стопа промашаја за L2 расте са 12% на 128 токена до 50% на 16k како акумулирани отисак алокације премашује L2 од 2 MB по језгру

Referentna uska grla tokenizatora, mehanizmi i izmjereni uticaji.

Доминантни трошак је алокација по подударности. На 1k токена, референтна имплементација извршава (завршава) отприлике 7 милиона инструкција по енкодовању са IPC-ом од 2.8, од чега је већина у позивима алокатора и конверзијама ниски. L2 промашаји су важни тек након ~1k токена, када акумулирани отисак алокације преплави кеш по језгру.

P50 i P99 kašnjenje referentnog tokenizatora po veličini ulaza.

Stopa promašaja L2 keša referentnog tokenizatora po veličini ulaza.

Broj bajtova alociranih po kodiranju referentnim tokenizatorom kroz različite veličine ulaza.

Алокација по токену је константна: око 2 KB и ~18 алокација по токену, без обзира на величину улаза. Нелинеарност кашњења долази од L2: акумулирани бајтови прелазе 2 MB око 1k токена, стопа промашаја расте са 8% на ~50%, а крива p99 се савија у складу са тим.

Поредимо три производна токенизера, који сви покрећу исти Unigram алгоритам на истом XLM-RoBERTa моделу:

Мотор	Језик	Стабло (Trie)
Hugging Face	Rust	Префисно стабло са децом у виду HashMap-а
SentencePiece	C++	Darts стабло са двоструким низом
IREE токенизер	C	Darts стабло са двоструким низом

Implementacije tokenizatora, jezici i prikazi trie-a korišćeni u poređenju.

Повезујемо SentencePiece и IREE преко директног C/C++ FFI уместо кроз њихове Rust омотаче; омотачи додају алокације по позиву и конверзије ниски које нису део трошка основне библиотеке.

Сви механизми су изграђени уз пуне оптимизације (O3, циљање нативног хардвера, оптимизација времена повезивања). Мерења се извршавају везана за једно мирно језгро на Intel Xeon Platinum 8488C процесору. За сваки мотор и величину улаза прикупљамо кашњење стварног времена (p50 и p99, 10.000 итерација након 1.000 загревања), извршене инструкције путем Valgrind cachegrind-а, IPC и стопе промашаја кеша са хардверских бројача perf stat-а, као и алокације на гомили које броји омотач глобалног алокатора око мереног прозора.

На 514 токена (+2 преко 512 је убацивање BOS/EOS):

Имплементација	p50 кашњење	Инструкције	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

Kašnjenje tokenizatora, broj instrukcija, IPC i alokacije pri 514 tokena.

SP и IREE достижу отприлике трећину референтног кашњења. Они извршавају отприлике упола мање инструкција, раде на већем IPC-у и алоцирају један до два реда величине мање.

SentencePiece и IREE користе стабло са двоструким низом које је увео Aoe 1989. године (Aoe, 1989; Karoonboonyanan). Стабло је кодирано у два равна низа целих бројева, 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

Претрага детета је изведена као:

cpp

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

Сваки корак проласка кроз стабло захтева само два учитавања из низа, једно сабирање целих бројева и једно поређење, без хеширања, без праћења показивача и без алокације на гомили по чвору. Конструкција поставља сваки чвор тако да његова деца падају на слободне слотове у низу валидације, омогућавајући више родитеља да деле регионе све док се њихова деца разликују по бајту који прате.

За XLM-RoBERTa вокабулар од 250k, цело стабло стаје у ~9 MB контигуалне меморије (~780k слотова × 12 бајтова за офсет, валидацију и ID токена по слоту). Активни радни скуп једног енкодовања је реда величине 100 KB, удобно у L2 кешу, а хардверски префечер се закључава на регулараван образац приступа.

Референца, за супротност, чува хеш-табелу деце по чвору, што кошта отприлике четири зависна учитавања по бајтном кораку. Хеширај бајт, учитај бакет, прати показивач до уноса у бакет, прати други показивач до чвора детета на гомили, затим консултуј његову сопствену хеш-табелу за следећи бајт. Објекти на гомили се раштркају и већина учитавања промаши кеш.

SP и IREE чувају ID токена директно у чвору стабла. Референтна имплементација стабла враћа само подударне бајтове, тако да енкодер мора да алоцира нову ниску за сваку подударност, да је потражи у споредној хеш-табели да би повратио ID токена, и да прочита скор из засебног вектора. SP враћа ID као ускладиштену вредност стабла и чита скор из равног низа децималних бројева са покретном зарезом:

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 курсора уместо враћања свих подударности у једном позиву, али је модел трошкова исти: ID-ови токена и скорови су доступни као индекси равног низа, без алокације или хеширања при самом пролазу кроз стабло. IREE алоцира само један излазни бафер по енкодовању; SP додатно алоцира чвор решетке по подударности током DP-а, што укупно чини отприлике 1.559 алокација на 514 токена.

Пре промене стабла, изолујемо трошак алгоритма од трошка имплементације: колико брзо референца ради са уклоњеним непотребним радом?

Базна линија задржава референтно стабло са децом у хеш-табели, али прави две промене. Привремена структура у власништву позиваоца садржи DP табелу, претпроцесиране бајтове и ID-ове излазних токена, тако да критична путања не врши никакве алокације након загревања. ID токена и скор су смештени директно у чвор стабла, чиме се уклањају конверзија ниски по подударности и претрага у споредној хеш-табели.

Унутрашња петља:

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

Ово је исти алгоритам, са истим обликом стабла и истим обрасцем приступа, само без алокација и без сувишних претрага. Резултати на 514 токена:

Мотор	p50	Инструкције	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
Базна линија	156 µs	1.53M	2.62	0

Osnovna varijanta bez alokacija u poređenju s postojećim implementacijama tokenizatora pri 514 tokena.

Уклањање материјализације ниски по подударности и секундарне претраге у хеш-табели смањује инструкције 2.4× у поређењу са референцом. IPC опада са њима (2.86 → 2.62) зато што праћење показивача у хеш-табели, које је претходно било скривено иза рада алокатора, сада постаје доминантни трошак по бајту.

P50 i P99 kašnjenje referentnog i osnovnog tokenizatora bez alokacija po veličini ulaza.

Stopa promašaja L2 keša referentnog i osnovnog tokenizatora bez alokacija po veličini ulaza.

Базна линија смањује p50 кашњење за 2-3× у поређењу са референцом при свакој величини, а њена стопа промашаја за L2 остаје близу 2-3% кроз 2k токена у поређењу са референтних 8-48%. Преостали трошак је праћење показивача у HashMap-у, којем се бави следећи одељак.

Стабло засновано на хеш-табели представља праћење показивача. SP и IREE ово решавају помоћу стабла са двоструким низом (погледајте претходни одељак), а ми позајмљујемо исту структуру података. Разлика је у томе што су SP и IREE општи за чије се потребе подржавају стримовање улаза, излазни офсети и више начина кодирања; та флексибилност их кошта додатне евиденције око стабла (решетка у SP-у, осмостепени цевовод у IREE-у). нама ништа од тога није потребно, па уграђујемо стабло директно у Витербијеву петљу и одбацујемо остало.

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

Бајтни корак кошта два читања из низа, сабирање целих бројева и поређење. Цело стабло има око 9 MB, али било које појединачно енкодовање пролази само кроз ~100 KB њега, тако да врући подаци остају у L2.

Мотор	p50	p99	Инструкције	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%
Базна линија	155 µs	1,170 µs	1.53M	2.59%	16.66%
+ Darts	68 µs	80 µs	1.10M	6.45%	11.42%

Kašnjenje tokenizatora, instrukcije i stope promašaja keša nakon usvajanja double-array trie-a.

Време извршавања опада 2.3× у односу на базну линију и 4.8× у односу на референцу. Инструкције падају за још 28% у односу на базну линију. Уклањање решетке и цевовода нам омогућава да извршимо 1.10M инструкција по енкодовању наспрам SP-ових 1.82M и IREE-ових 1.61M при истом облику стабла; разлика је у књиговодству које они одржавају за опште API-је који нам нису потребни.

Darts стабло из Оптимизације 1 захтева два зависна учитавања по бајтном кораку. Прво родитељски base офсет, затим check унос на слоту кандидата детета да се потврди да је родитељ власник. Check унос само потврђује власништво. Исто питање се може решити битмапом по чвору која бележи који бајтови имају децу. Конструкцијом стабла са двоструким низом, бит за бајт b у битмапи родитеља је постављен тачно када кандидат слот за тај бајт припада родитељу. Битмапа и check низ носе исте информације, тако да можемо у потпуности да уклонимо check низ из рутинске структуре. Претрага битмапе се компајлира у један тест бита над једном 64-битном речју, што се извршава за отприлике један циклус.

Претрага битмапе се компајлира у један тест бита над једном 64-битном речју, што се извршава у отприлике једном циклусу. Сродна инструкција POPCNT, која броји све постављене битове у регистру, је оно што други дизајни стабла индексирани битмапом користе за директно израчунавање офсета детета из битмапе. То нам није потребно јер 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)
}

Док то радимо, пакујемо четири по-чвору поља (битмапу, базу, ID токена и скор) у једну кеш линију од 64 бајта. Једна посјета чвору сада учитава све: скор и ID токена који су нам потребни у терминалним чворовима, плус битмапу и базу за сљедећи корак. Провјеравајући низ се користи само током изградње и избацује се из распореда у раду. Индексирање у врућој путањи није провјерено, јер изградња trie-ја и структура петље већ гарантују границе. Компромис је простор: на 64 бајта по чвору × ~780K слотова trie расте са ~9 MB на ~50 MB.

Резултати на 514 токена:

Мотор	p50	p99	Инструкције	L2 приступи	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%
Базна линија	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%

Rezultati tokenizatora pri 514 tokena nakon dodavanja bitmape i inline pakovanja.

Време извршавања систематично опада за додатних 4.5% на 514 токена и расте са дужином улаза, достижући 6-7% на 4k и 16k. Уклањање check низа претвара корак стабла по бајту са два учитавања кеш линије у једно, што значи 2.5× мање L2 приступа по енкодовању (1.8K наспрам 4.6K код обичног Darts-а). Стопа промашаја скаче са 6% на 20%, али је већина тога именител: са мање од половине приступа, промашаји које имамо зазимају већи удео.

Подаци стабла су величине приближно 50 MB (780.000 чворова по 64 бајта). На подразумеваном Linux процесу, та меморија је подржана страницама од 4 KB, тако да цело стабло обухвата око 12.000 различитих виртуелних страница, далеко изнад онога што меморијски башер за превођење адреса (TLB) првог нивоа процесора може да садржи (Sapphire Rapids има 96 уноса). Сваки Витербијев корак дотиче другачији чвор, а током енкодовања од 512 токена потрошимо отприлике 9.000 циклуса у шетњама кроз табелу страница, што је око 3% буџета по енкодовању.

Решење је да се стабло подржи великим страницама од 2 MB уместо оних од 4 KB. Истих 50 MB сада обухвата 25 страница, у потпуности стаје у TLB, а директоријуми табеле страница престају да се такмиче са стаблом за L2 кеш.

Linux има два начина да ослони меморију на странице од 2 MB. Опортунистички је transparent huge pages (THP): ваш програм тражи од кернела да надогради област меморије са страница од 4 KB на 2 MB, а позадински kernel thread покушава то да уради када има времена и доступне континуалне физичке меморије. Друга алтернатива је да се trie директно доделити из унапријед резервисаног huge-page пула који кернел издваја при покретању система:

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 великих страница; стабло троши 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%

Kašnjenje tokenizatora sa i bez ogromnih stranica kroz različite veličine ulaza.

Највећи добитак је на 4k токена, где је радни скуп довољно велики да је промет табеле страница активно конкурисао са подацима стабла за L2 пропусни опсег. Изнад 4k добитак се смањује јер L3 промашаји доминирају, а шетње кроз табеле страница постају мањи удео у укупном времену.

Спајајући све три оптимизације заједно, овде је коначни мотор измерен у поређењу са сваким другим RoBERTa токенизером који смо тестирали. Уз нативне C++ SentencePiece и C IREE бинарне датотеке, бенчмарковали смо и готове Rust омотачке пакете (crates) које би производни корисник искористио, sentencepiece и iree-tokenizer. Пакет sentencepiece има 1.6-1.9× веће кашњење од нативног C++ бинарног фајла на свакој величини улаза, при чему редукција долази од тога што омотач алоцира нову листу делова токена, од којих сваки држи сопствену копију текста дела, при сваком енкодовању. Пакет iree-tokenizer димензионише свој интерни бафер према сваком улазу, што избегава константну алокацију по енкодовању коју нативни IREE бинарни фајл плаћа без обзира на величину улаза, а то је најважније код кратких уноса где би алокација иначе доминирала стварним радом токенизације. При дужинама улаза у производњи, константни трошак се амортизује и сопствени трошак омотача по позиву од копирања токена назад у Rust гура његово кашњење изнад кашњења нативног бинарног фајла.

P50 i P99 kašnjenje po kodiranju kroz implementacije tokenizatora i veličine ulaza.

Коначни мотор извршава исти Витербијев алгоритам над истим вокабуларом од 250.000 токена, не алоцира ништа на критичној путањи и производи излаз са тачним токенима у поређењу са референцом. Сваки бајтни корак је сада једно учитавање кеш линије од 64 бајта, један тест битмапе и једно сабирање целих бројева, што је смањење са претходне проба у HashMap-у, позива алокатора и неколико грана за посебне случајеве у базној имплементацији. Инструкције по енкодовању су пале са 3.66M на 1.04M, што је пад од 3.5×. Време извршавања прати тај однос на кратким улазима и додатно се повећава на дугим улазима, где референтне алокације по токену почињу да преплављују L2 и L3 кеш.

У пракси овај рад је смањио искоришћеност процесора у претпроцесирајућем слоју нашег инферентног стека за 5-6× и скинуо двоцифрени број милисекунди са кашњења реранкера.

Највећи део смањења кашњења потекао је од лаганих промена које су уклониле изгубљени рад: уклањање алокација по енкодовању, замена стабла са децом у HashMap-у са двоструким низом, и уклањање вишка општег API-ја. Коришћење постојеће битмапе по чвору као провере валидности и подржавање стабла великим страницама од 2 MB заједно су чинили 10-20% додатка на већу промену на стабло са двоструким низом, у зависности од величине улаза.

Готови Rust омотачи око SentencePiece-а и IREE-а илуструју исту ствар у обрнутом смеру. Поред нативних C и C++ токенизера, FFI граница и алокације по позиву које омотачи уводе видљиви су у бројевима кашњења. Изворни код у Rust-у за коначни Витерби енкодер доступан је на 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}
}

Мотивација

Витербијев алгоритам

Референцна имплементација

Напомена о претпроцесирању

Гдје референтна имплементација проводи своје вријеме

Како смо мерили

Зашто су SentencePiece и IREE бржи: стабло са двоструким низом

Базна линија: Порт референце без алокација

Оптимизација 1: Стабло са двоструким низом без додатних апстракција

Оптимизација 2: Битмапа и инлајн паковање

Оптимизација 3: Велике странице за трие

Коначно поређење

Завршне мисли

Референце

Цитирање