யூனிகிராம் டோக்கனைசர் CPU செயல்திறனை மேம்படுத்துதல்

செயல்திறனை மையமாகக் கொண்ட திட்டமாக எங்களது யூனிகிராம் டோக்கனைசரை அடிப்பில் இருந்து மீண்டும் உருவாக்கினோம்.

ஆசிரியர்கள்Perplexity Research

செயல்திறனை மையமாகக் கொண்ட திட்டமாக எங்களது யூனிகிராம் டோக்கனைசரை அடிப்பில் இருந்து மீண்டும் உருவாக்கினோம். தயாரிப்பு உள்ளீட்டு நீளங்களில், புதிய என்கோடர் p50 தாமதத்தை Hugging Face டோக்கனைசர்ஸ் கிரேட்டுடன் ஒப்பிடும்போது தோராயமாக 5×, SentencePiece (C++) உடன் ஒப்பிடும்போது ~2×, மற்றும் IREE's டோக்கனைசர் (C) உடன் ஒப்பிடும்போது ~1.5× குறைக்கிறது, மேலும் நிலையான நிலை ஹீப் ஒதுக்கீடுகள் எதுவும் இல்லை. தயாரிப்பில் இது எங்கள் இன்ஃபரன்ஸ் ஸ்டாக்கில் CPU பயன்பாட்டை 5-6× ஆகக் குறைத்தது மற்றும் ரீராங்கர் தாமதத்திலிருந்து இரட்டை இலக்க மில்லிசெகண்டுகளைக் குறைத்தது.

உந்துதல்

LLM இன்ஃபரன்ஸ் செலவு பொதுவாக GPU வேலையாக வடிவமைக்கப்பட்டுள்ளது: KV கேச், கவன கர்னல்கள், நிபுணர் ரூட்டிங். ஆனால் தயாரிப்பு போக்குவரத்தின் குறிப்பிடத்தக்க பகுதி மிகக் சிறிய மாடல்களில் இயங்குகிறது, இது எல்லை டிரான்ஸ்பார்மர்களை விட இரண்டு முதல் மூன்று ஆர்டர்கள் சிறியது. உட்பொதிவு மாடல்கள், கிளாசிஃபையர்கள் மற்றும் ரீராங்கர்கள் இன்னும் GPUகளில் இயங்குகின்றன, ஆனால் ஃபார்வர்ட் பாஸ் மிகவும் குறுகியதாக இருப்பதால் அதைச் சுற்றியுள்ள அனைத்தும் முக்கியத்துவம் பெறத் தொடங்குகின்றன.

கோரிக்கை ஒன்றுக்கு நூற்றுக்கணக்கான வேட்பாளர் ஆவணங்களை மதிப்பெண் வழங்கும் ஒரு ரீராங்கர் மிகத் தெளிவான உதாரணம் ஆகும். ஒரு சிறிய மாடலுடன், GPU கணக்கீடு வழக்கமாக ஒற்றை இலக்க மில்லிசெகண்டுகளில் முடிவடைகிறது, ஆனால் ஒவ்வொரு உள்ளீடும் முதலில் CPU-சார்ந்த டோக்கனைசேஷன் மூலம் செல்ல வேண்டும், உரை சொற்களஞ்சிய ஐடிகளாக மாற்றப்படுகிறது. தொகுதி பெரியதாக இருக்கும்போது, அது மொத்த கோரிக்கை தாமதத்தில் குறிப்பிடத்தக்க பகுதியாக மாறலாம்.

இந்த வேலை XLM-RoBERTa-வை இலக்காகக் கொண்டது; இது SentencePiece மூலம் பயிற்றுவிக்கப்பட்ட 250K-token Unigram சொல்வளத்தைப் பயன்படுத்துகிறது. Fine-tuned செய்யப்பட்ட RoBERTa-குடும்ப encoder-கள் ranking, retrieval, மற்றும் similarity பணிகளுக்கான பொதுவான தேர்வாகும். நாங்கள் முழுவதும் single-threaded per-encode latency-ஐ அறிக்கையிடுகிறோம்; production-இல் rayon பயன்படுத்தி cores முழுவதும் parallelize செய்கிறோம்.

இந்த இடுகை முழுவதும் நாங்கள் Hugging Face இன் tokenizers crate ஐ பெஞ்ச்மார்க் செய்யும் குறிப்புப் பொருளாகக் கருதுகிறோம், ஏனெனில் இது பெரும்பாலான அணிகள் அடையும் இயல்புநிலை ரஸ்ட் டோக்கனைசர் ஆகும். மற்ற இரண்டு முக்கிய தயாரிப்பு செயலாக்கங்களாக ஒப்பீட்டிற்காக SentencePiece (C++) மற்றும் IREE (C) ஆகியவை சேர்க்கப்பட்டுள்ளன.

விட்டர்பி அல்காரிதம்

2018 இல் குடோவால் அறிமுகப்படுத்தப்பட்ட யூனிகிராம் டோக்கனைசேஷன் (Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates) மற்றும் SentencePiece இல் அனுப்பப்பட்டது, பிரித்தலை மிகவும் சாத்தியமான-பாதை சிக்கலாக வடிவமைக்கிறது: ஒவ்வொரு சொற்களஞ்சிய டோக்கனும் கற்றுக்கொண்ட பதிவு-நிகழ்தகவைக் கொண்டுள்ளது, மேலும் என்கோடர் டோக்கன் மதிப்பெண்கள் அதிக மதிப்பைச் যোগ செய்யும் பிரித்தலைத் தேர்ந்தெடுக்கிறது. இந்தச் சிக்கல் Viterbi algorithm (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 பைட்டுகள்) கட்டுப்படுத்தப்படுகிறது. உள் ட்ரீ வாக் என்பது ஹாட் பாதையாகும்: 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 }

மற்றும் inner loop (simplified) – ஒவ்வொரு prefix-search match-மும் புதிய string ஒன்றை allocate செய்து, பின்னர் hash-map-ஐ probe செய்கிறது:

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 }

குறியீடு படிக்கக்கூடிய ரஸ்ட் ஆகும், ஆனால் மூல மட்டத்தில் கண்ணுக்குத் தெரியாத பல வேலைகள் நடக்கின்றன. அடுத்த பகுதி நேரம் எங்கு செல்கிறது என்பதைப் பிரிக்கிறது.

முற்படுத்தல் பற்றிய குறிப்பு

Viterbi இயங்குவதற்கு முன், input Unicode normalization (NFKC) மற்றும் word-boundary marking வழியாக செல்கிறது. எங்கள் சூழல்களில் profiling, preprocessing-ஐ மொத்த encode நேரத்தின் 5% க்கும் குறைவாக காட்டுகிறது; ஆகவே மீதமுள்ள post-இல் Viterbi forward pass-ஐ கவனம் செய்கிறோம்.

குறிப்பு செயலாக்கம் தனது நேரத்தை எங்கு செலவிடுகிறது

CPU குறியீட்டை விரைவுபடுத்துவதற்கு இரண்டு வழிகள் உள்ளன: குறைந்த வழிமுறைகளை இயக்கவும், அல்லது உயர் IPC ஐப் பெறவும். Cachegrind முதலாவதை அளவிடுகிறது, perf stat இரண்டாவதை அளவிடுகிறது. இந்த இடுகையில் உள்ள ஒவ்வொரு உகப்பாக்கமும் ஒன்றில் அல்லது மற்றொன்றில் இறங்கும்.

CPUகள் நான்கு விஷயங்களில் ஸ்தம்பிக்கின்றன: கேச் மிஸ்ஸ்கள் (L1d ~4 சுழற்சிகள், L3-miss-to-DRAM என்பது நூற்றுக்கணக்கில்), அவுட்-ஆஃப்-ஆர்டர் இன்ஜின் இணையாகச் செய்ய முடியாத சார்ந்த-சுமை சங்கிலிகள், கிளை தவறான கணிப்புகள் (தவறான யூகத்திற்கு ~15-20 சுழற்சிகள் சுத்தப்படுத்தப்படுகின்றன), மற்றும் அலகேட்டர் அழைப்புகள். குறிப்பு யூனிகிராம் இன்ஜின் செயலாக்கம் நான்கையும் தாக்குகிறது:

தடை

செய்கைமுறை

அளவிடப்பட்ட தாக்கம்

பொருத்தத்திற்கு ஒதுக்கீடு

பொருத்தப்பட்ட பைட்டுகள் மீது String::from_utf8 மற்றும் ட்ரீ பொருத்தம் ஒன்றுக்கு ஒரு AHashMap தேடல்; டோக்கன் ஐடி ஏற்கனவே இலைக்குள் உள்ளது, ஆனால் குறிப்பு அதை அங்கு சேமிக்கவில்லை

512 டோக்கன்களில் 7,295 ஒதுக்கீடுகள், 1k இல் 14,542, 16k இல் 299,171

பைட் ஒன்றுக்கு சுட்டி துரத்தல்

ஒவ்வொரு ட்ரீ முனையிலும் ஒரு AHashMap, அடுத்த பைட்டை ஹாஷ் செய்து ஒரு படிக்கு இரண்டு சுட்டிகளை டீ ரெஃபரன்ஸ் செய்கிறது; Node struct ஆனது is_leaf போன்ற கோல்டு புலங்களையும் ஒருங்கிணைத்து, ஒவ்வொரு வருகையின் போதும் அவற்றை கேச்சிற்கு இழுக்கிறது

L1d மிஸ் விகிதம் குறைவாகவே உள்ளது (1k இல் ~2.5%) ஏனெனில் அலகேட்டர் ஹாட் பக்கங்கள் L1 இல் வாழ்கின்றன; செலவு சார்ந்த-சுமை தாமதமாகக் காட்டப்படுகிறது

நீண்ட உள்ளீடுகளில் L2 த்ராஷிங்

DP அட்டவணை, முன்னொட்டு ஸ்கிராட்ச் மற்றும் வெளியீட்டு டோக்கன் பட்டியல் அனைத்தும் ஒவ்வொரு அழைப்பிலும் புதிதாக ஒதுக்கப்படுகின்றன

ஒட்டுமொத்த ஒதுக்கீட்டு தடம் ஒரு கோர் 2 MB L2 ஐ தாண்டும்போது L2 மிஸ் விகிதம் 128 டோக்கன்களில் 12% லிருந்து 16k இல் 50% ஆக உயர்கிறது

குறிப்புக் tokenizer bottlenecks, mechanisms, and அளக்கப்பட்ட தாக்கங்கள்.

ஆதிக்கம் செலுத்தும் செலவு ஒவ்வொரு பொருத்தத்திற்குமான ஒதுக்கீடு ஆகும். 1k டோக்கன்களில், குறிப்பு செயலாக்கம் 2.8 IPC இல் என்கோட்டிற்கு தோராயமாக 7M வழிமுறைகளை ஓய்வு பெறுகிறது (நிறைவு செய்கிறது), அவற்றில் பெரும்பாலானவை அலகேட்டர் அழைப்புகள் மற்றும் சரம் மாற்றங்களில். ஒட்டுமொத்த ஒதுக்கீட்டு தடம் கோர்-வாரியான கேச்சை நிரப்பியவுடன், L2 தவறுகள் ~1k டோக்கன்களுக்குப் பிறகு மட்டுமே முக்கியத்துவம் பெறுகின்றன.

input size அடிப்படையில் reference tokenizer p50 மற்றும் p99 latency.
input size அடிப்படையில் reference tokenizer L2 cache miss rate.
input sizes முழுவதும் reference tokenizer-இனால் encode ஒன்றுக்கு allocated ஆகும் bytes.

டோக்கன் வாரியான ஒதுக்கீடு நிலையானது: உள்ளீட்டு அளவைப் பொருட்படுத்தாமல், ஒரு டோக்கனுக்கு சுமார் 2 KB மற்றும் ~18 ஒதுக்கீடுகள். தாமத நேரியலற்ற தன்மை L2 இலிருந்து வருகிறது: ஒட்டுமொத்த பைட்டுகள் 1k டோக்கன்களைச் சுற்றி 2 MB ஐக் கடக்கின்றன, மிஸ் விகிதம் 8% லிருந்து ~50% ஆக உயர்கிறது, மேலும் p99 வளைவு பொருந்துகிறது.

நாங்கள் எவ்வாறு அளவிட்டோம்

அனைத்தும் ஒரே XLM-RoBERTa மாடலுக்கு எதிராக அதே யூனிகிராம் அல்காரிதத்தை இயக்கும் மூன்று தயாரிப்பு டோக்கனைசர்களை நாங்கள் ஒப்பிடுகிறோம்:

இயந்திரம்

மொழி

ட்ரீ

Hugging Face

ரஸ்ட்

HashMap-children முன்னொட்டு ட்ரீ

SentencePiece

C++

Darts இரட்டை-வரிசை ட்ரீ

IREE டோக்கனைசர்

C

Darts இரட்டை-வரிசை ட்ரீ

ஒப்பீட்டில் பயன்படுத்தப்பட்ட tokenizer implementations, மொழிகள், மற்றும் trie பிரதிநிதிப்புகள்.

SentencePiece மற்றும் IREE ஐ அவற்றின் ரஸ்ட் ரேப்பர்கள் வழியாக இல்லாமல் நேரடி C/C++ FFI வழியாக இணைக்கிறோம்; ரேப்பர்கள் அடிப்படை நூலகத்தின் செலவின் ஒரு பகுதியாக இல்லாத அழைப்பு வாரியான ஒதுக்கீடுகள் மற்றும் சரம் மாற்றங்களைச் சேர்க்கின்றன.

அனைத்து engines-மும் முழு optimizations-களுடன் (O3, native targeting, link-time optimization) build செய்யப்படுகின்றன. அளவீடுகள் Intel Xeon Platinum 8488C-இல் ஒரு அமைதியான core-க்கு pinned செய்யப்பட்ட நிலையில் இயக்கப்படுகின்றன. ஒவ்வொரு engine-க்கும் input size-க்கும், நாம் wall-clock latency (p50 மற்றும் p99, 1,000 warmup-க்கு பின் 10,000 iterations), Valgrind cachegrind வழியாக instructions retired, perf stat hardware counters-இலிருந்து IPC மற்றும் cache miss rates, மற்றும் அளவிடப்பட்ட window-ஐச் சுற்றியுள்ள global allocator wrapper மூலம் எண்ணப்பட்ட heap allocations ஆகியவற்றை சேகரிக்கிறோம்.

514 டோக்கன்களில் (512 ஐ விட +2 என்பது 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

514 token-களில் tokenizer latency, instruction count, IPC, மற்றும் allocations.

SP மற்றும் IREE ஆகியவை குறிப்பின் தாமதத்தில் தோராயமாக மூன்றில் ஒரு பங்கில் இறங்குகின்றன. அவை பாதியாக பல வழிமுறைகளை ஓய்வு பெறுகின்றன, அதிக IPC இல் இயங்குகின்றன, மேலும் ஒன்று முதல் இரண்டு ஆர்டர்கள் குறைவாக ஒதுக்கீடு செய்கின்றன.

SentencePiece மற்றும் IREE ஏன் வேகமானவை: இரட்டை-வரிசை ட்ரீ

SentencePiece மற்றும் IREE இரண்டும் 1989 இல் Aoe ஆல் அறிமுகப்படுத்தப்பட்ட இரட்டை-வரிசை ட்ரீயைப் பயன்படுத்துகின்றன (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 பைட்டுகள்). ஒரு ஒற்றை என்கோட்டின் ஹாட் ஒர்க்கிங் செட் 100 KB அளவில் உள்ளது, L2 இல் வசதியாக உள்ளது, மேலும் வன்பொருள் ப்ரீபெட்ச்சர் வழக்கமான அணுகல் வடிவத்தில் பூட்டுகிறது.

இதற்கு நேர்மாறாக, குறிப்பு ஒவ்வொரு முனையிலும் குழந்தைகளின் ஹாஷ்-மேப்பை வைத்திருக்கிறது, இது பைட் படிக்கு தோராயமாக நான்கு சார்ந்த சுமைகளை செலவிடுகிறது. பைட்டை ஹாஷ் செய்யவும், பக்கெட்டை ஏற்றவும், பக்கெட் உள்ளீட்டிற்கு ஒரு சுட்டியைப் பின்தொடரவும், ஹீப்பில் உள்ள குழந்தை முனைக்கு மற்றொரு சுட்டியைப் பின்தொடரவும், பின்னர் அடுத்த பைட்டிற்காக அதன் சொந்த ஹாஷ்-மேப்பைப் பார்க்கவும். ஹீப் பொருள்கள் சிதறுகின்றன மற்றும் பெரும்பாலான சுமைகள் கேச்சைத் தவறவிடுகின்றன.

SP மற்றும் IREE இரண்டும் டோக்கன் ஐடியை நேரடியாக ட்ரீ முனையில் சேமிக்கின்றன. குறிப்பு ட்ரீ செயலாக்கம் பொருத்தப்பட்ட பைட்டுகளை மட்டுமே தருகிறது, எனவே என்கோடர் ஒவ்வொரு பொருத்தத்திற்கும் ஒரு புதிய சரத்தை ஒதுக்க வேண்டும், டோக்கன் ஐடியை மீட்க பக்க ஹாஷ்-மேப்பில் அதைத் தேட வேண்டும், மற்றும் தனி திசையனிலிருந்து மதிப்பெண்ணைப் படிக்க வேண்டும். SP ட்ரீயின் சேமிக்கப்பட்ட மதிப்பாக ஐடியைத் தருகிறது மற்றும் பிளாட் மிதவை வரிசையிலிருந்து மதிப்பெண்ணைப் படிக்கிறது:

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 ஒரே அழைப்பில் அனைத்து பொருத்தங்களையும் தருவதற்கு பதிலாக நிலை அடிப்படையிலான கர்சர் ஏபிஐ ஐப் பயன்படுத்துகிறது, ஆனால் செலவு மாதிரி ஒன்றுதான்: டோக்கன் ஐடிகளும் மதிப்பெண்களும் பிளாட்-அவரி குறியீடுகளாக அணுகக்கூடியவை, ட்ரீ நடையில் ஒதுக்கீடு அல்லது ஹாஷிங் இல்லை. IREE ஒவ்வொரு என்கோட்டிற்கும் ஒரு வெளியீட்டு बफर ஐ மட்டுமே ஒதுக்குகிறது; SP கூடுதலாக DP இன் போது ஒரு பொருத்தத்திற்கு ஒரு லேட்டிஸ் முனையை ஒதுக்குகிறது, இது 514 டோக்கன்களில் தோராயமாக 1,559 ஒதுக்கீடுகளைக் கொண்டுள்ளது.

அடிநிலை: குறிப்பின் பூஜ்ஜிய-ஒதுக்கீட்டு போர்ட்

ட்ரீயை மாற்றுவதற்கு முன், அல்காரிதம் செலவை செயலாக்க செலவிலிருந்து பிரிக்கிறோம்: தேவையற்ற வேலை அகற்றப்பட்டவுடன் குறிப்பு எவ்வளவு வேகமாக இயங்குகிறது?

அடிநிலையானது குறிப்பின் ஹாஷ்-மேப்-குழந்தைகள் ட்ரீயை வைத்திருக்கிறது ஆனால் இரண்டு மாற்றங்களைச் செய்கிறது. அழைப்பாளர் சொந்தமான ஸ்கிராட்ச் அமைப்பு DP அட்டவணை, முற்படுத்தப்பட்ட பைட்டுகள் மற்றும் வெளியீட்டு டோக்கன் ஐடிகளை வைத்திருக்கிறது, எனவே வார்மப்பிற்குப் பிறகு ஹாட் பாதை எந்த ஒதுக்கீடுகளையும் செய்யாது. டோக்கன் ஐடி மற்றும் மதிப்பெண் நேரடியாக ட்ரீ முனையில் சேமிக்கப்படுகின்றன, இது பொருத்த வாரியான சரம் மாற்றம் மற்றும் இரண்டாம் நிலை ஹாஷ்-மேப் தேடலை நீக்குகிறது.

உள் லூப்:

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

514 token-களில் existing tokenizer implementations-உடன் ஒப்பிடப்பட்ட zero-allocation baseline.

பொருத்த வாரியான சரம் உருவாவதை நீக்குவது மற்றும் இரண்டாம் நிலை ஹாஷ்-மேப் தேடல் குறிப்புடன் ஒப்பிடும்போது வழிமுறைகளை 2.4× குறைக்கிறது. ஹாஷ்-மேப் சுட்டி துரத்தல், முன்பு அலகேட்டர் வேலைக்குப் பின்னால் மறைக்கப்பட்டிருந்தது, இப்போது பைட் வாரியான ஆதிக்கம் செலுத்தும் செலவாக இருப்பதால் IPC அதனுடன் குறைகிறது (2.86 → 2.62).

input size அடிப்படையில் reference மற்றும் zero-allocation baseline tokenizer p50 மற்றும் p99 latency.
input size அடிப்படையில் reference மற்றும் zero-allocation baseline tokenizer L2 cache miss rate.

baseline, ஒவ்வொரு அளவிலும் reference-ஐ விட p50 latency-ஐ 2-3× குறைக்கிறது, மேலும் அதன் L2 miss rate 2k tokens வரை reference-ன் 8-48%-க்கு எதிராக சுமார் 2-3% ஆகவே உள்ளது. மீதமுள்ள செலவு HashMap pointer chase ஆகும், இதை அடுத்த பகுதி address செய்கிறது.

உகப்பாக்கம் 1: கூடுதல் சுருக்கங்கள் இல்லாத இரட்டை-வரிசை ட்ரீ

hash-map trie என்பது ஒரு pointer chase. SP மற்றும் IREE இதை double-array trie மூலம் தீர்க்கின்றன (முந்தைய பகுதியைப் பார்க்கவும்), மேலும் அதே data structure-ஐ நாங்கள் எடுத்துக்கொள்கிறோம். வேறுபாடு என்னவென்றால், SP மற்றும் IREE ஆகியவை streaming input, output offsets, மற்றும் பல encoding modes-ஐ ஆதரிக்கும் general-purpose libraries ஆகும்; அந்த flexibility காரணமாக trie-ஐச் சுற்றி கூடுதல் bookkeeping தேவைப்படும் (SP-இல் lattice, IREE-இல் eight-stage pipeline). எங்களுக்குத் அதில் எதுவும் தேவையில்லை; ஆகவே trie-ஐ நேரடியாக Viterbi loop-இல் inline செய்து, மீதியை drop செய்கிறோம்.

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%

double-array trie-ஐ ஏற்றுக்கொண்ட பின் tokenizer latency, instructions, மற்றும் cache miss rates.

வால்-கிளாக் அடிநிலையிலிருந்து 2.3× மற்றும் குறிப்பிலிருந்து 4.8× குறைகிறது. வழிமுறைகள் அடிநிலையிலிருந்து மேலும் 28% குறைகின்றன. லேட்டிஸ் மற்றும் பைப்லைனை வெட்டுவது SP இன் 1.82M மற்றும் IREE இன் 1.61M க்கு எதிராக ஒரே ட்ரீ வடிவத்தில் என்கோட்டிற்கு 1.10M வழிமுறைகளை ஓய்வு பெற அனுமதிக்கிறது; இடைவெளி என்பது எங்களுக்குத் தேவையில்லாத பொதுவான-நோக்க ஏபிஐகளுக்காக அவர்கள் வைத்திருக்கும் புத்தக பராமரிப்பு ஆகும்.

உகப்பாக்கம் 2: பிட்மேப் மற்றும் இன்லைன் பேக்கிங்

உகப்பாக்கம் 1 இலிருந்து Darts ட்ரீக்கு ஒரு பைட் படிக்கு இரண்டு சார்ந்த சுமைகள் தேவைப்படுகின்றன. முதலில் பெற்றோரின் அடிப்படை ஆஃப்செட், பின்னர் பெற்றோருக்கு சொந்தமானது என்பதை உறுதிப்படுத்த வேட்பாளர் குழந்தை இடத்திலிருக்கும் சரிபார்ப்பு உள்ளீடு. சரிபார்ப்பு உள்ளீடு உரிமையை மட்டுமே சரிபார்க்கிறது. எந்த பைட்டுகளுக்கு குழந்தைகள் உள்ளன என்பதைப் பதிவு செய்யும் முனை வாரியான பிட்மேப் மூலம் அதே கேள்விக்கு பதிலளிக்க முடியும். இரட்டை-வரிசை ட்ரீயின் கட்டுமானத்தின் மூலம், பெற்றோரின் பிட்மேப்பில் பைட் bக்கான பிட், அந்த பைட்டுக்கான வேட்பாளர் இடம் பெற்றோருக்கு சொந்தமானதாக இருக்கும்போது சரியாக அமைக்கப்படும். பிட்மேப்பும் சரிபார்ப்பு வரிசையும் அதே தகவலைக் கொண்டுள்ளன, எனவே ரன்டைம் அமைப்பிலிருந்து சரிபார்ப்பு வரிசையை முழுமையாக கைவிடலாம்.

பிட்மேப் தேடல் ஒரு 64-பிட் வார்த்தைக்கு எதிரான ஒற்றை பிட் சோதனையாகத் தொகுக்கப்படுகிறது, இது தோராயமாக ஒரு சுழற்சியில் இயங்கும். தொடர்புடைய POPCNT வழிமுறை, இது ஒரு பதிவேட்டில் உள்ள அனைத்து அமைக்கப்பட்ட பிட்டுகளையும் கணக்கிடுகிறது, பிட்மேப்பிலிருந்து நேரடியாக ஒரு குழந்தை ஆஃப்சைட்டைக் கணக்கிட மற்ற பிட்மேப்-சுட்டப்பட்ட ட்ரீ வடிவமைப்புகள் பயன்படுத்துவதாகும். Darts கட்டுமானம் ஏற்கனவே அந்த ஆஃப்சைட்டை முனையின் அடிப்படை புலத்தில் சேமித்து வைத்துள்ளதால் எங்களுக்கு இது தேவையில்லை.

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

அதே சமயம், node ஒன்றுக்கான நான்கு fields-ஐ (bitmap, base, token ID, மற்றும் score) ஒரு 64-byte cache line-இல் pack செய்கிறோம். இப்போது node-ஐ ஒருமுறை visit செய்வதே தேவையான அனைத்தையும் கொண்டுவருகிறது: terminal nodes-இல் எங்களுக்குத் தேவைப்படும் score மற்றும் token ID, மேலும் அடுத்த படிக்கான bitmap மற்றும் base. check array கட்டுமானத்தின் போது மட்டுமே பயன்படுத்தப்படுகிறது, runtime layout-இலிருந்து நீக்கப்படுகிறது. trie construction மற்றும் loop structure ஏற்கனவே bounds-ஐ உறுதி செய்வதால் hot-path indexing unchecked ஆகும். trade-off என்பது space: node ஒன்றுக்கு 64 bytes × ~780K slots என்ற அளவில் 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%

bitmap மற்றும் inline packing சேர்த்த பிறகு 514 token-களில் tokenizer முடிவுகள்.

வால்-கிளாக் முறையே 514 டோக்கன்களில் மற்றொரு 4.5% குறைகிறது மற்றும் உள்ளீட்டு நீளத்துடன் அதிகரிக்கிறது, 4k மற்றும் 16k இல் 6-7% ஐ அடைகிறது. சரிபார்ப்பு வரிசையை கைவிடுவது பைட் வாரியான ட்ரீ படியை இரண்டு கேச்-வரி சுமைகளிலிருந்து ஒன்றாக மாற்றுகிறது, இது என்கோட்டிற்கு 2.5× குறைவான L2 அணுகல்களாகும் (சாதாரண Darts இன் 4.6K உடன் ஒப்பிடும்போது 1.8K). மிஸ் விகிதம் 6% இலிருந்து 20% ஆகத் தாண்டுகிறது, ஆனால் அதில் பெரும்பாலானவை வகு எண் ஆகும்: பாதிக்கும் குறைவான அணுகல்களுடன், நமக்கு இருக்கும் தவறுகள் பெரிய பங்கைப் பெறுகின்றன.

உகப்பாக்கம் 3: ட்ரைக்கான பெரிய பக்கங்கள்

ட்ரீ தரவு தோராயமாக 50 MB ஆகும் (ஒவ்வொன்றும் 64 பைட்டுகளில் 780,000 முனைகள்). இயல்புநிலை லினக்ஸ் செயல்முறையில், அந்த நினைவகம் 4 KB பக்கங்களால் ஆதரிக்கப்படுகிறது, எனவே முழு ட்ரீயும் சுமார் 12,000 தனித்துவமான மெய்நிகர் பக்கங்களைக் கொண்டுள்ளது, இது CPU இன் முதல்-நிலை தரவு Translation Lookaside Buffer ஐ விட மிக அதிகம் (Sapphire Rapids 96 உள்ளீடுகளைக் கொண்டுள்ளது). ஒவ்வொரு விட்டர்பி படியும் வேறுபட்ட முனையைத் தொடுகிறது, மேலும் 512-டோக்கன் என்கோட்டில் பக்க-அட்டவணை நடைகளில் தோராயமாக 9,000 சுழற்சிகளை எரிக்கிறோம், இது என்கோட் வாரியான பட்ஜெட்டில் சுமார் 3% ஆகும்.

4 KB பக்கங்களுக்குப் பதிலாக 2 MB பெரிய பக்கங்களுடன் ட்ரீயை ஆதரிப்பதே திருத்தமாகும். அதே 50 MB இப்போது 25 பக்கங்களைக் கொண்டுள்ளது, Translation Lookaside Buffer இல் முழுமையாகப் பொருந்துகிறது, மேலும் பக்க-அட்டவணை கோப்பகங்களே L2 கேச்சுக்கு ட்ரீயுடன் போட்டியிடுவதை நிறுத்துகின்றன.

Linux-க்கு memory-ஐ 2 MB pages-ஆல் back செய்ய இரண்டு வழிகள் உள்ளன. opportunistic வழி transparent huge pages (THP): உங்கள் program, ஒரு memory region-ஐ 4 KB-இலிருந்து 2 MB pages-ஆக உயர்த்த kernel-ஐ கேட்கிறது, மேலும் பின்னணி kernel thread-ன் கைவசம் நேரமும் தொடர்ச்சியான physical memory-உம் இருக்கும் போது அதைச் செய்ய முயல்கிறது. மற்ற மாற்று, boot நேரத்தில் kernel ஒதுக்கும் pre-reserved huge-page pool-இலிருந்து trie-ஐ நேரடியாக allocate செய்வதாகும்:

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%

input sizes முழுவதிலும் huge pages உடன் மற்றும் இல்லாமல் tokenizer latency.

மிகப்பெரிய வெற்றி 4k டோக்கன்களில் உள்ளது, அங்கு வேலை செய்யும் தொகுப்பு L2 அலைவரிசைக்காக பக்க-அட்டவணை ட்ராஃபிக் ட்ரீ தரவுடன் தீவிரமாக போட்டியிடும் அளவுக்கு பெரியது. 4k க்கு அப்பால் லாபம் சுருங்குகிறது ஏனெனில் L3 தவறுகள் ஆதிக்கம் செலுத்துகின்றன மற்றும் பக்க-அட்டவணை நடைகள் மொத்த நேரத்தில் சிறிய பங்காகின்றன.

இறுதி ஒப்பீடு

மூன்று optimizations-ஐ ஒன்றாகக் கொண்டு, நாங்கள் சோதித்த மற்ற அனைத்து RoBERTa tokenizer-களுக்கு எதிராக அளவிடப்பட்ட இறுதி engine இதோ. native C++ SentencePiece மற்றும் C IREE binaries-க்கு இணையாக, production user ஒருவர் தேர்ந்தெடுக்கும் off-the-shelf Rust wrapper crates-ஐயும் நாங்கள் benchmark செய்தோம்: sentencepiece மற்றும் iree-tokenizer. sentencepiece crate, ஒவ்வொரு input size-இலும் native C++ binary-யை விட 1.6-1.9× அதிக latency-ஐ அளிக்கிறது; காரணம் wrapper, ஒவ்வொரு encode-இலும் புதிய token pieces பட்டியலை allocate செய்து, ஒவ்வொரு piece text-இன் தனித்தனி நகலை வைத்திருப்பதிலிருந்து வரும் overhead. iree-tokenizer crate, தன் internal buffer-ஐ ஒவ்வொரு input-க்கும் ஏற்ப size செய்வதால், native IREE binary input size-ஐப் பொருட்படுத்தாமல் செலுத்தும் constant per-encode allocation-ஐத் தவிர்க்கிறது; மற்றும் இது குறுகிய inputs-இல் மிகவும் முக்கியம், அங்கு allocation உண்மையான tokenization வேலைக்கு ஆதிக்கம் செலுத்தக்கூடும். production input lengths-இல் இந்த constant cost amortize ஆகிறது, மேலும் tokens-ஐ மீண்டும் Rust-க்கு copy செய்வதிலிருந்து wrapper-ன் சொந்த per-call overhead, அதன் latency-ஐ native binary-யின் latency-க்கு மேலே தள்ளுகிறது.

tokenizer implementations மற்றும் input sizes முழுவதிலும் encode ஒன்றுக்கு p50 மற்றும் p99 latency.

இறுதி எஞ்சின் அதே 250,000-டோக்கன் சொற்களஞ்சியத்தின் மீது அதே விட்டர்பியை இயக்குகிறது, ஹாட் பாதையில் எதையும் ஒதுக்காது, மேலும் குறிப்புக்கு எதிராக டோக்கன்-துல்லியமான வெளியீட்டை உருவாக்குகிறது. ஒவ்வொரு பைட் படியும் இப்போது ஒற்றை 64-பைட் கேச்-வரி சுமை, ஒரு பிட்மேப் சோதனை மற்றும் ஒரு முழு எண் சேர்ப்பு ஆகும், இது அடிநிலை செயலாட்டத்தில் HashMap ஆய்வு, அலகேட்டர் அழைப்பு மற்றும் பல சிறப்பு-வழக்கு கிளைகளிலிருந்து குறைக்கப்பட்டுள்ளது. என்கோட்டிற்கான வழிமுறைகள் 3.66M இலிருந்து 1.04M ஆகக் குறைந்துள்ளது, இது 3.5× வீழ்ச்சியாகும். வால்-கிளாக் குறுகிய உள்ளீடுகளில் அந்த விகிதத்துடன் பொருந்துகிறது மற்றும் நீண்ட உள்ளீடுகளில் மேலும் விரிவடைகிறது, அங்கு குறிப்பின் டோக்கன் வாரியான ஒதுக்கீடுகள் L2 மற்றும் L3 ஐ நிரப்பத் தொடங்குகின்றன.

முடிவுரை சிந்தனைகள்

நடைமுறையில் இந்த வேலை எங்கள் இன்ஃபரன்ஸ் ஸ்டாக்கின் முற்படுத்தல் அடுக்கில் CPU பயன்பாட்டை 5-6× ஆகக் குறைத்தது மற்றும் ரீராங்கர் தாமதத்திலிருந்து இரட்டை இலக்க மில்லிசெகண்டுகளைக் குறைத்தது.

தாமதக் குறைப்பின் பெரும்பகுதி வீணான வேலையை அகற்றிய இலகுரக மாற்றங்களிலிருந்து வந்தது: என்கோட் வாரியான ஒதுக்கீடுகளைக் கைவிடுவது, HashMap-children ட்ரீயை இரட்டை-வரிசையால் மாற்றுவது மற்றும் பொதுவான-API ஓவர்ஹெட்டை அகற்றுவது. செல்லுபடியாகும் சோதனையாக இருக்கும் முந்தைய முனை வாரியான பிட்மேப்பைப் பயன்படுத்துவதும் மற்றும் 2 MB பெரிய பக்கங்களுடன் ட்ரீயை ஆதரிப்பதும் சேர்ந்து இரட்டை-வரிசை ட்ரீயுக்கான பெரிய மாற்றத்திற்கு மேல் 10-20% கணக்கிடப்பட்டன, இது உள்ளீட்டு அளவைப் பொறுத்தது.

SentencePiece மற்றும் IREE சுற்றியுள்ள ஆஃப்-தி-ஷெல்ஃப் ரஸ்ட் ரேப்பர் கிரேட்கள் அதே புள்ளியை தலைகீழாக விளக்குகின்றன. சொந்த C மற்றும் C++ டோக்கனைசர்களுக்கு மேல், FFI எல்லையும் ரேப்பர்கள் அறிமுகப்படுத்தும் அழைப்பு வாரியான ஒதுக்கீடுகளும் தாமத எண்களில் தெரியும். இறுதி விட்டர்பி என்கோடருக்கான ரஸ்ட் மூலமானது 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}
}