युनिग्राम टोकनायझर CPU कामगिरी सुधारत आहे

आम्ही युनिग्राम टोकनायझरची कामगिरी सुधारण्याच्या उद्देशाने सुरुवातीपासून पुन्हा अंमलबजावणी केली.

लेखकPerplexity Research

आम्ही युनिग्राम (Unigram) टोकनायझरची कामगिरी सुधारण्याच्या उद्देशाने सुरुवातीपासून पुन्हा अंमलबजावणी केली. उत्पादनातील इनपुट लांबीवर, नवीन एन्कोडर Hugging Face टोकनायझर्स क्रेटच्या तुलनेत p50 लेटन्सी अंदाजे ५×, SentencePiece (C++) च्या तुलनेत सुमारे २×, आणि IREE च्या टोकनायझर (C) च्या तुलनेत सुमारे १.५× ने कमी करतो, ज्यामध्ये स्थिर-स्थिती हीप ॲलोकेशन शून्य आहे. उत्पादनात यामुळे आमच्या इन्फरन्स स्टॅकमधील CPU वापर ५-६× ने कमी झाला आणि रीरँकर लेटन्सीमध्ये दोन अंकी मिलीसेकंदांची बचत झाली.

प्रेरणा

LLM इन्फरन्सचा खर्च सामान्यतः GPU चे काम म्हणून पाहिला जातो: KV कॅशे, अटेंशन कर्नल, एक्सपर्ट रूटिंग. परंतु उत्पादन ट्रॅफिकचा एक मोठा भाग खूप लहान मॉडेल्सवर चालतो, जे फ्रंटियर ट्रान्सफॉर्मरपेक्षा दोन ते तीन पट लहान असतात. एम्बेडिंग मॉडेल्स, क्लासिफायर्स आणि रीरँकर अजूनही GPU वर चालतात, परंतु फॉरवर्ड पास इतका लहान असतो की त्याच्या सभोवतालचे सर्वकाही महत्त्वाचे वाटू लागते.

सर्वात स्पष्ट उदाहरण म्हणजे प्रत्येक विनंतीमागे शेकडो उमेदवार दस्तऐवजांची स्कोअरिंग करणारा रीरँकर. लहान मॉडेलसह, GPU संगणन सामान्यतः एकाच अंकी मिलीसेकंदात पूर्ण होते, परंतु प्रत्येक इनपुटला अजूनही प्रथम CPU-साइड टोकनायझेशनमधून जावे लागते, ज्यामुळे मजकुराचे व्होकॅब्युरी आयडीमध्ये रूपांतर होते. जेव्हा बॅच मोठी असते, तेव्हा ते एकूण विनंती लेटन्सीच्या महत्त्वपूर्ण भागाचे प्रतिनिधित्व करू शकते.

हे काम XLM-RoBERTa वर लक्ष केंद्रित करते, जे SentencePiece सह प्रशिक्षित केलेले २५०K-टोकन युनिग्राम व्होकॅब्युरी आहे. फाईन-ट्यून केलेले RoBERTa-कुटुंबातील एन्कोडर रँकिंग, रिट्रीव्हल आणि सिमिलॅरिटी कार्यांसाठी एक सामान्य पर्याय आहेत. आम्ही संपूर्णपणे सिंगल-थ्रेडेड प्रति-एनकोड लेटन्सी अहवाल देतो; उत्पादनात आम्ही rayon वापरून कोअर्समध्ये समांतर प्रक्रिया करतो.

या पोस्टमध्ये आम्ही Hugging Face चे tokenizers crate हे आमचे बेंचमार्क संदर्भ म्हणून मानतो, कारण हे डीफॉल्ट Rust टोकनायझर आहे ज्याचा बहुतांश टीम्स वापर करतात. इतर दोन प्रमुख उत्पादन अंमलबजावणी म्हणून SentencePiece (C++) आणि IREE (C) ची तुलना करण्यासाठी समाविष्ट केले आहे.

विटर्बी अल्गोरिदम

कुडो यांनी २०१८ मध्ये सादर केलेले युनिग्राम टोकनायझेशन (Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates) आणि SentencePiece मध्ये समाविष्ट केलेले, सेगमेंटेशनला सर्वात संभाव्य-मार्ग समस्या म्हणून मांडते: प्रत्येक व्होकॅब्युरी टोकनमध्ये शिकलेली लॉग-संभाव्यता असते, आणि एन्कोडर अशी सेगमेंटेशन निवडतो ज्याचे टोकन स्कोर सर्वोच्च मूल्याची बेरीज करतात. ही समस्या विटर्बी अल्गोरिदम (१९६७) सह सोडवली जाते, ज्यामध्ये बाइट पोझिशन्स ग्राफ लेअर्स म्हणून आणि व्होकॅब्युरी टोकन्स सतत बाइट श्रेणी पसरणारे एज्स असतात. रीकरन्स ही बाइट पोझिशन्सवर एक-डायमेंशनल 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 साठी ४८ UTF-8 बाइट्स). अंतर्गत ट्राई वॉक हा हॉट पाथ आहे: १६k-टोकन इनपुटवर, तो लाखो ट्रान्झिशन्स चालवतो आणि प्रति एनकोड कोटींहून अधिक इन्स्ट्रक्शन्स पूर्ण करतो.

संदर्भ अंमलबजावणी

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) आणि वर्ड-बाउंड्री मार्किंगमधून जाते. प्रोफायलिंगनुसार आमच्या परिदृश्यांमध्ये प्रीप्रोसेसिंग एकूण एनकोड वेळेच्या ५% पेक्षा कमी आहे, म्हणून आम्ही पोस्टच्या बाकीच्या भागासाठी विटर्बी फॉरवर्ड पासवर लक्ष केंद्रित करतो.

संदर्भ अंमलबजावणी तिचा वेळ कुठे खर्च करते

CPU कोड वेगवान करण्याचे दोन मार्ग आहेत: कमी इन्स्ट्रक्शन्स कार्यान्वित करणे, किंवा उच्च IPC मिळवणे. Cachegrind पहिल्याचे मोजमाप करते, perf stat दुसऱ्याचे मोजमाप करते. या पोस्टमधील प्रत्येक ऑप्टिमायझेशन एका किंवा दुसऱ्यावर लागू होते.

CPU चार गोष्टींवर अडकतात: कॅशे मिस (L1d ~४ सायकल, L3-miss-to-DRAM शेकडो आहेत), आउट-ऑफ-ऑर्डर इंजिन समांतर करू शकत नाही अशा डिपेंडंट-लोड चेन, ब्रँच मिसप्रिडिक्ट (चुकीच्या अंदाजामागे ~१५-२० सायकल फ्लश होतात), आणि ॲलोकेटर कॉल्स. संदर्भ युनिग्राम इंजिन अंमलबजावणी या सर्व चार गोष्टींवर परिणाम करते:

बॉटलनेक

प्रक्रिया

मोजलेला प्रभाव

प्रति जुळणी ॲलोकेशन

जुळलेल्या बाइट्सवर String::from_utf8 आणि प्रत्येक ट्राई जुळणीसाठी AHashMap लूकअप; टोकन आयडी आधीपासूनच लीफमध्ये आहे, परंतु संदर्भ तो तिथे साठवत नाही

५१२ टोकन्सवर ७,२९५ ॲलोकेशन्स, १k वर १४,५४२, १६k वर २९९,१७१

प्रति बाइट पॉइंटर चेझ

प्रत्येक ट्राई नोडवर एक AHashMap, पुढील बाइट हॅश करणे आणि प्रति पायरी दोन पॉइंटर डीरेफरन्स करणे; Node स्ट्रक्चर is_leaf सारखे कोल्ड फील्ड्स देखील बंडल करते, ज्यामुळे प्रत्येक भेटीदरम्यान ते कॅशेमध्ये ओढले जातात

L1d मिस दर कमी राहतो (~१k वर २.५%) कारण ॲलोकेटर हॉट पेज L1 मध्ये राहतात; खर्च डिपेंडंट-लोड लेटन्सी म्हणून दिसून येतो

लांब इनपुटवर L2 थ्रॅशिंग

DP टेबल, प्रिफिक्स स्क्रॅच, आणि आउटपुट टोकन लिस्ट प्रत्येक कॉलवर नवीनपणे ॲलोकेट केले जातात

संचित ॲलोकेशन फूटप्रिंट प्रति-कोर २ MB L2 पेक्षा जास्त झाल्यामुळे L2 मिस दर १२८ टोकन्सवरील १२% वरून १६k वर ५०% पर्यंत वाढतो

संदर्भ टोकनायझरच्या अडथळ्यांचे, यंत्रणांचे आणि मोजलेल्या परिणामांचे संदर्भ.

मुख्य खर्च प्रति जुळणी ॲलोकेशन आहे. १k टोकन्सवर, संदर्भ अंमलबजावणी २.८ च्या IPC वर प्रति एनकोड अंदाजे ७M इन्स्ट्रक्शन्स पूर्ण करते, त्यापैकी बहुतेक ॲलोकेटर कॉल्स आणि स्ट्रिंग रूपांतरणांमध्ये असतात. संचित ॲलोकेशन फूटप्रिंट प्रति-कोर कॅशे ओव्हरफ्लो झाल्यानंतर, L2 मिस फक्त ~१k टोकन्स नंतर महत्त्वाचे ठरतात.

इनपुट आकारानुसार संदर्भ टोकनायझर p50 आणि p99 विलंब.
इनपुट आकारानुसार संदर्भ टोकनायझर L2 कॅश चुकण्याचा दर.
इनपुट आकारांनुसार संदर्भ टोकनायझरद्वारे प्रत्येक एन्कोडसाठी वाटप केलेले बाइट्स.

प्रति-टोकन ॲलोकेशन स्थिर आहे: इनपुट आकाराची पर्वा न करता, प्रति टोकन सुमारे २ KB आणि ~१८ ॲलोकेशन्स. लेटन्सीची नॉन-लिनियरिटी L2 मधून येते: संचित बाइट्स १k टोकन्सच्या आसपास २ MB ओलांडतात, मिस दर ८% वरून ~५०% पर्यंत वाढतो, आणि p99 वक्र जुळण्यासाठी वाकतो.

आम्ही कसे मोजले

आम्ही तीन उत्पादन टोकनायझर्सची तुलना करतो, जे सर्व समान XLM-RoBERTa मॉडेलविरुद्ध समान युनिग्राम अल्गोरिदम चालवतात:

इंजिन

भाषा

ट्राय

Hugging Face

Rust

HashMap-children प्रिफिक्स ट्राय

SentencePiece

C++

Darts डबल-ॲरे ट्राय

IREE टोकनायझर

C

Darts डबल-ॲरे ट्राय

तुलनेत वापरलेल्या टोकनायझर अंमलबजावण्या, भाषा आणि ट्राय प्रतिनिधित्वे.

आम्ही Rust रॅपर्सऐवजी थेट C/C++ FFI द्वारे SentencePiece आणि IREE जोडतो; रॅपर्स प्रति-कॉल ॲलोकेशन्स आणि स्ट्रिंग रूपांतरणे जोडतात जी अंतर्निहित लायब्ररीच्या खर्चाचा भाग नाहीत.

सर्व इंजिन पूर्ण ऑप्टिमायझेशनसह (O3, नेटिव्ह टार्गेटिंग, लिंक-टाइम ऑप्टिमायझेशन) बिल्ड केले आहेत. Intel Xeon Platinum 8488C वरील एका शांत कोरवर पिन करून मोजमाप चालवले जातात. प्रत्येक इंजिन आणि इनपुट आकारासाठी आम्ही वॉल-क्लॉक लेटन्सी (p50 आणि p99, १,००० वार्मअप नंतर १०,००० पुनरावृत्ती), व्हॅलग्रिंड कॅशेग्राइंड द्वारे पूर्ण केलेल्या इन्स्ट्रक्शन्स, perf stat हार्डवेअर काउंटरवरून IPC आणि कॅशे मिस दर, आणि मोजलेल्या विंडोभोवती जागतिक ॲलोकेटर रॅपरद्वारे मोजलेले हीप ॲलोकेशन्स गोळा करतो.

५१४ टोकन्सवर (५१२ वर +२ म्हणजे BOS/EOS इन्जेक्शन):

अंमलबजावणी

p50 लेटन्सी

इन्स्ट्रक्शन्स

IPC

ॲलोकेशन्स

Hugging Face

३४९ µs

३.६०M

२.८९

७,२९५

SentencePiece

१२८ µs

१.८३M

३.३९

१,५५९

IREE

११२ µs

२.२८M

३.०६

१

514 टोकनवर टोकनायझर विलंब, सूचनांची संख्या, IPC, आणि वाटप.

SP आणि IREE ची लेटन्सी संदर्भाच्या अंदाजे एक तृतीयांश आहे. ते सुमारे अर्ध्या इन्स्ट्रक्शन्स पूर्ण करतात, उच्च IPC वर चालतात, आणि एक ते दोन पट कमी ॲलोकेशन करतात.

SentencePiece आणि IREE का वेगवान आहेत: डबल-ॲरे ट्राय

SentencePiece आणि IREE दोन्ही १९८९ मध्ये Aoë द्वारे सादर केलेल्या डबल-ॲरे ट्रायचा वापर करतात (Aoë, १९८९; 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 च्या २५0K व्होकॅबसाठी, संपूर्ण ट्राय सतत मेमरीच्या ~९ MB मध्ये बसते (प्रति स्लॉट ऑफसेट, व्हॅलिडेशन आणि टोकन आयडीसाठी ~७८0K स्लॉट × १२ बाइट्स). एका एनकोडचा हॉट वर्किंग सेट १०० 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 एकाच कॉलमध्ये सर्व जुळण्या परत करण्याऐवजी स्टेटफुल कर्सर API वापरते, परंतु खर्च मॉडेल समान आहे: टोकन आयडी आणि स्कोर फ्लॅट-ॲरे इंडेक्स म्हणून प्रवेशयोग्य आहेत, ट्राय वॉकवर कोणतेही ॲलोकेशन किंवा हॅशिंग नाही. IREE प्रति एनकोड फक्त एक आउटपुट बफर ॲलोकेट करते; SP अतिरिक्तपणे DP दरम्यान प्रति जुळणी लॅटिस नोड ॲलोकेट करते, ज्यामुळे ५१४ टोकन्सवर एकूण सुमारे १,५५९ ॲलोकेशन्स होतात.

बेसलाइन: संदर्भाचे झिरो-ॲलोकेशन पोर्ट

ट्राय बदलण्यापूर्वी, आपण अल्गोरिदमचा खर्च अंमलबजावणीच्या खर्चापासून वेगळा करतो: अनावश्यक काम काढून टाकल्यास संदर्भ किती वेगाने चालतो?

बेसलाइन संदर्भाची हॅश-मॅप-चिल्ड्रेन ट्राय ठेवते पण दोन बदल करते. कॉलर-मालकीची स्क्रॅच स्ट्रक्चर 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, } } }

हा समान अल्गोरिदम आहे, ज्याचा ट्राय आकार समान आहे आणि ॲक्सेस पॅटर्न समान आहे, फक्त कोणतेही ॲलोकेशन नाही आणि कोणतेही अतिरीक्त लूकअप नाहीत. ५१४ टोकन्सवर परिणाम:

इंजिन

p50

इन्स्ट्रक्शन्स

IPC

ॲलोकेशन्स

Hugging Face

३२६ µs

३.६६M

२.८६

७,२९५

SentencePiece

१२७ µs

१.८१M

३.५५

१,५५९

IREE

१११ µs

१.५८M

३.२६

१

बेसलाइन

१५६ µs

१.५३M

२.६२

०

514 टोकनवर विद्यमान टोकनायझर अंमलबजावण्यांच्या तुलनेत शून्य-वाटप बेंचमार्क.

प्रति-जुळणी स्ट्रिंग मटेरियलायझेशन आणि दुय्यम हॅश-मॅप लूकअप काढून टाकल्यामुळे संदर्भाच्या तुलनेत इन्स्ट्रक्शन्स २.४× ने कमी होतात. त्यांच्यासह IPC कमी होते (२.८६ → २.६२) कारण हॅश-मॅप पॉइंटर चेझ, जो पूर्वी ॲलोकेटरच्या कामामागे लपलेला होता, आता प्रति बाइट मुख्य खर्च बनला आहे.

इनपुट आकारानुसार संदर्भ आणि शून्य-वाटप बेंचमार्क टोकनायझर p50 आणि p99 विलंब.
इनपुट आकारानुसार संदर्भ आणि शून्य-वाटप बेंचमार्क टोकनायझर L2 कॅश चुकण्याचा दर.

बेसलाइन प्रत्येक आकारावर संदर्भाच्या तुलनेत p50 लेटन्सी २-३× ने कमी करते, आणि तिचा L2 मिस दर संदर्भाच्या ८-४८% च्या तुलनेत २k टोकन्सपर्यंत २-3% जवळ राहतो. उरलेला खर्च 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 } }

एक बाइट पायरी दोन ॲरे रीड, एक पूर्णांक बेरीज आणि एक तुलना खर्च करते. संपूर्ण ट्राय सुमारे ९ MB आहे, परंतु कोणतीही एकल एनकोड तिची फक्त ~१०० KB ट्रेव्हल करते, त्यामुळे हॉट डेटा L2 मध्ये राहतो.

इंजिन

p50

p99

इन्स्ट्रक्शन्स

L2 मिस%

L3 मिस%

Hugging Face

३२७ µs

३,३४० µs

३.६६M

८.१७%

१४.६६%

SentencePiece

१२७ µs

१,१४० µs

१.८२M

४.७४%

४.०७%

IREE

१११ µs

१३२ µs

१.६१M

५.८२%

३.८७%

बेसलाइन

१५५ µs

१,१७० µs

१.५३M

२.५९%

१६.६६%

+ Darts

६८ µs

८० µs

१.१०M

६.४५%

११.४२%

दुहेरी-अॅरे ट्राय स्वीकारल्यानंतर टोकनायझर विलंब, सूचना आणि कॅश चुकांची दर.

वॉल-क्लॉक बेसलाइनवरून २.३× आणि संदर्भावरून ४.८× ने कमी होते. इन्स्ट्रक्शन्स बेसलाइनवरून आणखी २८% कमी होतात. लॅटिस आणि पाइपलाइन कापल्यामुळे आम्हाला समान ट्राय आकारावर SP च्या १.८२M आणि IREE च्या १.६१M च्या तुलनेत प्रति एनकोड १.१०M इन्स्ट्रक्शन्स पूर्ण करता येतात; हा फरक सामान्य-हेतू API साठी ते ठेवलेले बुककीपिंग आहे ज्याची आम्हाला गरज नाही.

ऑप्टिमायझेशन २: बिटमॅप आणि इनलाईन पॅकिंग

ऑप्टिमायझेशन १ मधील Darts ट्रायला प्रति बाइट पायरी दोन डिपेंडंट लोड आवश्यक आहेत. प्रथम पालकाचा बेस ऑफसेट, नंतर पालक त्याची मालकी घेतो याची पुष्टी करण्यासाठी उमेदवार चाइल्ड स्लॉटवरील चेक एंट्री. चेक एंट्री फक्त मालकी प्रमाणित करते. प्रति-नोड बिटमॅपद्वारे समान प्रश्नाचे उत्तर दिले जाऊ शकते जे रेकॉर्ड करते की कोणत्या बाइट्सची बालके आहेत. डबल-ॲरे ट्रायच्या रचनेनुसार, पालकाच्या बिटमॅपमधील बाइट b साठी बिट तेव्हाच सेट केली जाते जेव्हा त्या बाइटसाठी उमेदवार स्लॉटची मालकी पालकाकडे असते. बिटमॅप आणि चेक ॲरे समान माहिती वाहून नेतात, त्यामुळे आपण रनटाइम स्ट्रक्चरमधून चेक ॲरे पूर्णपणे काढून टाकू शकतो.

बिटमॅप लूकअप एका ६४-बिट शब्दाविरुद्ध एकाच बिट चाचणीमध्ये संकलित होते, जे सुमारे एका सायकलमध्ये चालते. संबंधित 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) }

आपण हे करत असताना, आपण चार प्रति-नोड फील्ड (बिटमॅप, बेस, टोकन आयडी आणि स्कोर) एका ६४-बाइट कॅशे लाइनमध्ये पॅक करतो. एक सिंगल नोड भेट आता सर्वकाही ओढते: टर्मिनल नोड्सवर आपल्याला आवश्यक असलेला स्कोर आणि टोकन आयडी, तसेच पुढील पायरीसाठी बिटमॅप आणि बेस. चेक ॲरे फक्त बांधकामादरम्यान वापरला जातो आणि रनटाइम लेआउटमधून काढला जातो. हॉट-पाथ इंडेक्सिंग अनचेक्ड आहे कारण ट्राय बांधकाम आणि लूप रचना आधीच मर्यादा हमी देतात. स्पेस हा ट्रेड-ऑफ आहे: प्रति नोड ६४ बाइट्स × ~७८0K स्लॉटसह ट्राय ~९ MB वरून ~५० MB पर्यंत वाढते.

५१४ टोकन्सवर परिणाम:

इंजिन

p50

p99

इन्स्ट्रक्शन्स

L2 ॲक्सेस

L2 मिस%

L3 मिस%

Hugging Face

३२७ µs

३,३४० µs

३.६६M

१५.०K

८.१७%

१४.६६%

SentencePiece

१२७ µs

१,१४० µs

१.८२M

७.५K

४.७४%

४.०७%

IREE

१११ µs

१३२ µs

१.६१M

४.७K

५.८२%

३.८७%

बेसलाइन

१५५ µs

१,१७० µs

१.५३M

६.१K

२.५९%

१६.६६%

+ Darts

६८ µs

८० µs

१.१०M

४.६K

६.४५%

११.४२%

+ बिटमॅप आणि इनलाईन पॅकिंग

६५ µs

७७ µs

१.०६M

१.८K

२०.५३%

१५.०१%

बिटमॅप आणि इनलाइन पॅकिंग जोडल्यावर 514 टोकनवरील टोकनायझर परिणाम.

वॉल-क्लॉक ५१४ टोकन्सवर पद्धतशीरपणे आणखी ४.५% ने कमी होते आणि इनपुट लांबीसह वाढते, ४k आणि १६k वर ६-७% पर्यंत पोहोचते. चेक ॲरे काढून टाकल्याने प्रति बाइट ट्राय पायरी दोन कॅशे-लाइन लोडवरून एकावर जाते, जी प्रति एनकोड २.५× कमी L2 ॲक्सेस करते (साध्या Darts च्या ४.६K विरुद्ध १.८K). मिस दर ६% वरून २०% पर्यंत वाढतो, परंतु त्यातील बहुतेक छेद आहे: अर्ध्याहून कमी ॲक्सेससह, आपल्याकडे असलेल्या मिस मोठा हिस्सा घेतात.

ऑप्टिमायझेशन ३: ट्रीसाठी ह्युज पेजेस

ट्राय डेटा सुमारे ५० MB आहे (प्रत्येक ६४ बाइट्सवर ७८0,००० नोड्स). डीफॉल्ट लिनक्स प्रक्रियावर, ती मेमरी ४ KB पेजद्वारे समर्थित असते, त्यामुळे संपूर्ण ट्राय सुमारे १२,००० भिन्न व्हर्च्युअल पेजपर्यंत पसरते, जी CPU च्या पहिल्या-स्तरीय डेटा भाषांतर लूकअसाइझ बफरपेक्षा खूप पुढे आहे (Sapphire Rapids मध्ये ९६ नोंदी आहेत). प्रत्येक विटर्बी पायरी एका वेगळ्या नोडला स्पर्श करते आणि ५१२-टोकन एनकोडवर आपण पेज-टेबल वॉकमध्ये सुमारे ९,००० सायकल जाळतो, जो प्रति-एनकोड बजेटच्या सुमारे ३% आहे.

यावर उपाय म्हणजे ४ KB ऐवजी २ MB ह्युज पेजसह ट्राय समर्थित करणे. समान ५० MB आता २५ पेजमध्ये पसरते, भाषांतर लूकअसाइझ बफरमध्ये पूर्णपणे बसते, आणि पेज-टेबल डायरेक्टर स्वतः L2 कॅशेसाठी ट्रायशी स्पर्धा करणे थांबवतात.

लिनक्समध्ये मेमरी २ MB पेजसह समर्थित करण्याचे दोन मार्ग आहेत. संधीसाधू एक म्हणजे ट्रान्सपरंट ह्युज पेजेस (THP): तुमचा कार्यक्रम कर्नलला मेमरी प्रदेश ४ KB वरून २ MB पेजमध्ये श्रेणीसुधारित करण्यास सांगतो, आणि जेव्हा त्याच्याकडे वेळ आणि सतत भौतिक मेमरी उपलब्ध असते तेव्हा पार्श्वभूमी कर्नल थ्रेड तो करण्याचा प्रयत्न करतो. दुसरा पर्याय म्हणजे कर्नल बूटच्या वेळी बाजूला ठेवलेल्या पूर्व-राखीव ह्युज-पेज पूलवरून थेट ट्राय ॲलोकेट करणे:

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 सेट केले आहे). आमच्या उत्पादन इन्स्टन्सवर, १०,५६१ ह्युज पेजेस आरक्षित आहेत; ट्राय त्यापैकी २४ वापरते. mmap नंतर, /proc/<pid>/smaps प्रदेशाची पुष्टी करते: KernelPageSize: 2048 kB, Private_Hugetlb: 49152 kB.

इनपुट आकारांमध्ये फायदा ३-१२% वॉल-क्लॉक आहे, जो सुसंगत आणि वर्किंग-सेट लांबीच्या प्रमाणात आहे:

टोकन्स

ह्युज पेजशिवाय

ह्युज पेजसह

Δ

१३०

१५.७ µs

१५.२ µs

−३.६%

५१४

६५.४ µs

६३.१ µs

−३.४%

१,०२६

१२९.५ µs

१२५.३ µs

−३.३%

४,०९८

७७३ µs

६७९ µs

−१२.०%

१६,३८६

३,८०८ µs

३,५५४ µs

−६.८%

इनपुट आकारांनुसार ह्यूज पेजेससह आणि त्यांशिवाय टोकनायझर विलंब.

सर्वात मोठा फायदा ४k टोकन्सवर आहे, जिथे वर्किंग सेट इतका मोठा आहे की पेज-टेबल ट्रॅफिक L2 बँडविड्थसाठी ट्राय डेटाशी सक्रियपणे स्पर्धा करत होती. ४k च्या पलीकडे फायदा कमी होतो कारण L3 मिस वर्चस्व गाजवतात आणि पेज-टेबल वॉक एकूण वेळेचा लहान हिस्सा बनतात.

अतिम अंतिम तुलना

तीन ऑप्टिमायझेशन्स एकत्र घेतल्यावर, येथे अंतिम इंजिन आहे, जे आम्ही तपासलेल्या इतर प्रत्येक RoBERTa tokenizer विरुद्ध मोजले आहे. नेटिव्ह C++ SentencePiece आणि C IREE binaries सोबतच, आम्ही production user वापरला असता अशा off-the-shelf Rust wrapper crates, sentencepiece आणि iree-tokenizer यांचेही benchmark केले. sentencepiece crate प्रत्येक input size वर नेटिव्ह C++ binary पेक्षा 1.6-1.9× जास्त latency दाखवते; यामागचे overhead हे wrapper प्रत्येक encode वर token pieces ची एक ताजी यादी allocate करत असल्यामुळे येते, ज्यातील प्रत्येक piece text ची स्वतःची copy धरून ठेवतो. iree-tokenizer crate आपला internal buffer प्रत्येक input नुसार आकारित करते, ज्यामुळे प्रत्येक encode साठी लागणारे constant allocation टळते; नेटिव्ह IREE binary input size काहीही असला तरी हे allocation करते, आणि short inputs वर हे सर्वात महत्त्वाचे ठरते, कारण तिथे अन्यथा tokenization च्या प्रत्यक्ष कामावर allocation चा प्रभाव जास्त पडला असता. उत्पादनातील input lengths वर हा constant cost amortize होतो, आणि tokens परत Rust मध्ये copy करण्यामुळे wrapper कडून येणारा स्वतःचा per-call overhead त्याची latency नेटिव्ह binary पेक्षा जास्त ढकलतो.

टोकनायझर अंमलबजावण्या आणि इनपुट आकारांनुसार प्रत्येक एन्कोडसाठी p50 आणि p99 विलंब.

अतिम अंतिम इंजिन समान २५०,०००-टोकन व्होकॅब्युरीवर समान विटर्बी चालवते, हॉट पाथवर काहीही ॲलोकेट करत नाही, आणि संदर्भाविरुद्ध टोकन-अ‍ॅक्झॅक्ट आउटपुट तयार करते. प्रत्येक बाइट पायरी आता बेसलाइन अंमलबजावणीमधील HashMap प्रोब, ॲलोकेटर कॉल आणि अनेक विशेष-प्रकरणांच्या शाखांमधून खाली, एक सिंगल ६४-बाइट कॅशे-लाइन लोड, एक बिटमॅप चाचणी आणि एक पूर्णांक बेरीज आहे. प्रति एनकोड इन्स्ट्रक्शन्स ३.६६M वरून १.०४M पर्यंत घसरल्या, ३.५× घट. लहान इनपुटवर वॉल-क्लॉक त्या गुणोत्तराशी जुळते आणि लांब इनपुटवर आणखी रुंद होते, जिथे संदर्भाची प्रति-टोकन ॲलोकेशन्स L2 आणि L3 ओव्हरफ्लो होऊ लागतात.

अंतिम विचार

सराव, या कामामुळे आमच्या इन्फरन्स स्टॅकच्या प्रीप्रोसेसिंग लेअरमधील CPU वापर ५-६× ने कमी झाला आणि रीरँकर लेटन्सीमध्ये दोन अंकी मिलीसेकंदांची बचत झाली.

लेटन्सी घट, बर्‍याचशा हलक्या वजनाच्या बदलांमुळे आली ज्यांनी वाया गेलेले काम काढून टाकले: प्रति-एनकोड ॲलोकेशन्स काढून टाकणे, HashMap-चिल्ड्रेन ट्रायला डबल-ॲरेने बदलणे, आणि जेनेरिक-API ओव्हरहेड काढून टाकणे. वैधतेची तपासणी म्हणून विद्यमान प्रति-नोड बिटमॅप वापरणे आणि ट्रायला २ MB ह्युज पेजसह समर्थित करणे यामुळे डबल-ॲरे ट्रायमधील मोठ्या बदलाच्या वर १०-२०% योगदान मिळाले, इनपुट आकारावर अवलंबून.

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