การปรับปรุงประสิทธิภาพ CPU ของ Unigram tokenizer

เราได้พัฒนา Unigram tokenizer ขึ้นใหม่ตั้งแต่ต้นในฐานะโปรเจกต์ที่เน้นด้านประสิทธิภาพโดยเฉพาะ

ผู้เขียนPerplexity Research

เราได้พัฒนา Unigram tokenizer ขึ้นใหม่ตั้งแต่ต้นในฐานะโปรเจกต์ที่เน้นด้านประสิทธิภาพโดยเฉพาะ ที่ความยาวของอินพุตในระดับการใช้งานจริง ตัวเข้ารหัสใหม่นี้ช่วยลดความหน่วง p50 ลงได้ประมาณ 5 เท่า เมื่อเทียบกับ crate tokenizers ของ Hugging Face, ลดลงราว 2 เท่าเมื่อเทียบกับ SentencePiece (C++) และลดลงราว 1.5 เท่าเมื่อเทียบกับ tokenizer ของ IREE (C) โดยไม่มีการจัดสรรฮีปในสเตดีสเตตเลย ในการใช้งานจริงวิธีนี้ช่วยลดการใช้ CPU ในสแตกการอนุมานของเราลง 5-6 เท่า และช่วยลดความหน่วงของตัวจัดอันดับใหม่ (reranker) ลงได้ในระดับมิลลิวินาทีสองหลัก

แรงบันดาลใจ

ต้นทุนการอนุมานของ LLM มักจะถูกมองว่าเป็นงานของ GPU ได้แก่ KV cache, attention kernel, การจัดเส้นทางผู้เชี่ยวชาญ (expert routing) แต่ทว่าสัดส่วนที่มีนัยสำคัญของทราฟฟิกในระบบจริงนั้นทำงานบนโมเดลที่มีขนาดเล็กกว่ามาก ซึ่งเล็กกว่าทราฟฟิเกอร์ระดับแนวหน้าถึงสองถึงสามระดับ โมเดลฝังตัว (embedding model), ตัวจำแนกประเภท (classifier) และตัวจัดอันดับใหม่ (reranker) ยังคงทำงานบน GPU แต่รอบการส่งผ่านข้อมูลไปข้างหน้า (forward pass) นั้นสั้นพอที่ทุกสิ่งที่อยู่รอบๆ เริ่มมีความสำคัญขึ้นมา

กรณีที่ชัดเจนที่สุดคือตัวจัดอันดับใหม่ (reranker) ที่ให้คะแนนเอกสารผู้สมัครหลายร้อยรายการต่อหนึ่งคำขอ ด้วยโมเดลขนาดเล็ก การคำนวณบน GPU มักจะเสร็จสิ้นภายในหลักหน่วยมิลลิวินาที แต่อินพุตทุกตัวยังคงต้องผ่านกระบวนการทำโทเค็นฝั่ง CPU ก่อน ซึ่งเป็นการแปลงข้อความให้เป็นไอดีคำศัพท์ (vocabulary ID) เมื่อแบตช์มีขนาดใหญ่ สิ่งนั้นอาจคิดเป็นสัดส่วนที่มีนัยสำคัญของความหน่วงของคำขอทั้งหมด

งานนี้มุ่งเป้าไปที่ XLM-RoBERTa ซึ่งเป็นคำศัพท์ Unigram ขนาด 250K โทเค็นที่ฝึกด้วย SentencePiece ตัวเข้ารหัสตระกูล RoBERTa ที่ปรับแต่งละเอียด (fine-tuned) เป็นตัวเลือกทั่วไปสำหรับงานการจัดอันดับ การดึงข้อมูล และงานความคล้ายคลึง เราจะรายงานความหน่วงต่อการเข้ารหัสแบบเธรดเดี่ยวตลอดทั้งบทความนี้ ในการใช้งานจริงเราใช้ rayon เพื่อประมวลผลแบบขนานข้ามคอร์ต่างๆ

ตลอดโพสต์นี้ เราถือว่า tokenizers crate ของ Hugging Face เป็นข้อมูลอ้างอิงที่เราใช้ในการเปรียบเทียบประสิทธิภาพ เนื่องจากเป็น Rust tokenizer เริ่มต้นที่ทีมส่วนใหญ่เลือกใช้ นอกจากนี้ เรายังรวม SentencePiece (C++) และ IREE (C) ไว้สำหรับการเปรียบเทียบในฐานะการใช้งานจริงหลักอีกสองแบบ

อัลกอริทึม Viterbi

การทำโทเค็นแบบ Unigram ซึ่งแนะนำโดย Kudo ในปี 2018 (Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates) และใช้งานใน SentencePiece มองการแบ่งส่วนเป็นปัญหาเส้นทางที่เป็นไปได้มากที่สุด: โทเค็นคำศัพท์แต่ละตัวมีความน่าจะเป็นล็อกที่เรียนรู้มา และตัวเข้ารหัสจะเลือกการแบ่งส่วนที่ผลรวมคะแนนโทเค็นมีค่าสูงสุด ปัญหานี้ได้รับการแก้ไขด้วย อัลกอริทึม Viterbi (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

ลูปชั้นนอกเป็นแบบเชิงเส้นตามความยาวของอินพุต โดยถูกจำกัดในแต่ละตำแหน่งด้วยโทเค็นคำศัพท์ที่ยาวที่สุด (48 ไบต์ UTF-8 สำหรับ XLM-RoBERTa) การเดินผ่านทรี (trie walk) ชั้นในคือเส้นทางวิกฤต (hot path): บนอินพุตขนาด 16k โทเค็น มันจะรันการเปลี่ยนผ่านนับแสนครั้งและทำการสั่งยุติคำสั่งนับสิบล้านครั้งต่อการเข้ารหัสหนึ่งครั้ง

การใช้งานอ้างอิง

tokenizers v0.22 ของ Hugging Face ดำเนินการเกิดซ้ำโดยตรง ด้วยแฮชแมปสำหรับการค้นหาย้อนกลับและลูกของแฮชแมป (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 }

และลูปชั้นใน (แบบย่อ) – การค้นหาแบบจับคู่คำนำหน้า (prefix-search match) ทุกครั้งจะจัดสรรสตริงใหม่แล้วตรวจสอบแฮชแมป:

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 ที่อ่านง่าย แต่มีงานจำนวนมากเกิดขึ้นเบื้องหลังซึ่งมองไม่เห็นในระดับซอร์สโค้ด ส่วนถัดไปจะแจกแจงว่าเวลาหมดไปกับส่วนใดบ้าง

หมายเหตุเกี่ยวกับการประมวลผลล่วงหน้า

ก่อนที่ Viterbi จะทำงาน อินพุตจะต้องผ่านการปรับมาตรฐานยูนิโคด (NFKC) และการทำเครื่องหมายขอบเขตคำ การทำโปรไฟล์ระบุว่าการประมวลผลล่วงหน้าใช้เวลาน้อยกว่า 5% ของเวลาการเข้ารหัสทั้งหมดในสถานการณ์ของเรา ดังนั้นเราจึงมุ่งเน้นไปที่รอบการส่งผ่านไปข้างหน้าของ Viterbi สำหรับส่วนที่เหลือของโพสต์นี้

เวลาของอ้างอิงการใช้งานถูกใช้ไปกับส่วนใดบ้าง

มีสองวิธีในการเพิ่มความเร็วโค้ด CPU ได้แก่: ทำคำสั่งให้น้อยลง หรือทำให้ IPC สูงขึ้น Cachegrind วัดแบบแรก perf stat วัดแบบหลัง การเพิ่มประสิทธิภาพทุกรายการในโพสต์นี้มุ่งเน้นไปที่อย่างใดอย่างหนึ่ง

CPU มักจะหยุดชะงัก (stall) จาก 4 สิ่ง ได้แก่: การพลาดแคช (cache misses) (L1d ~4 ไซเคิล, การพลาดแคช L3 ไปยัง DRAM ใช้เวลาหลายร้อย), เชนการโหลดที่มีความเกี่ยวเนื่องกัน (dependent-load chains) ซึ่งเอนจินประมวลผลแบบนอกลำดับ (out-of-order) ไม่สามารถทำขนานกันได้, การทำนายสาขาผิดพลาด (~15-20 ไซเคิลที่ต้องล้างทิ้งต่อการคาดเดาผิดหนึ่งครั้ง), และการเรียกตัวจัดสรรหน่วยความจำ (allocator) การใช้งานเอนจิน unigram แบบอ้างอิงพบปัญหาทั้ง 4 ข้อนี้:

คอขวด

กลไก

ผลกระทบที่วัดได้

การจัดสรรหน่วยความจำต่อการจับคู่หนึ่งครั้ง

String::from_utf8 บนไบต์ที่ตรงกัน พร้อมกับการค้นหา AHashMap หนึ่งครั้งต่อการจับคู่ทรี; ไอดีโทเค็นอยู่ในโหนดใบ (leaf) อยู่แล้ว แต่การอ้างอิงไม่ได้จัดเก็บไว้ที่นั่น

การจัดสรร 7,295 ครั้งที่ 514 โทเค็น, 14,542 ครั้งที่ 1k, 299,171 ครั้งที่ 16k

การไล่พอยเตอร์ต่อหนึ่งไบต์

AHashMap ที่ทุกโหนดของทรี ทำการแฮชไบต์ถัดไปและยกเลิกการอ้างอิงพอยเตอร์สองตัวต่อหนึ่งขั้นตอน สตัรคเชอร์ Node ยังรวมฟิลด์ที่ไม่ค่อยได้ใช้งาน (cold fields) เช่น is_leaf เข้ามาด้วย ทำให้ถูกดึงเข้ามาในแคชทุกครั้งที่มีการเข้าถึง

อัตราการพลาด L1d อยู่ในระดับต่ำ (~2.5% ที่ 1k) เนื่องจากหน้าหน่วยความจำฮอตของตัวจัดสรรหน่วยความจำอยู่ใน L1; ต้นทุนจะแสดงออกมาในรูปของความหน่วงของการโหลดที่มีความเกี่ยวเนื่อง (dependent-load latency)

L2 thrashing บนอินพุตขนาดยาว

ตาราง DP, พื้นที่ทำงานคำนำหน้า (prefix scratch) และรายการโทเค็นผลลัพธ์ ล้วนถูกจัดสรรใหม่ทั้งหมดในการเรียกใช้งานแต่ละครั้ง

อัตราการพลาด L2 เพิ่มขึ้นจาก 12% ที่ 128 โทเค็น เป็น 50% ที่ 16k เนื่องจากพื้นที่การจัดสรรสะสมเกินกว่าขนาด L2 2 MB ต่อคอร์

อ้างอิงคอขวดของ tokenizer กลไก และผลกระทบที่วัดได้

ต้นทุนหลักคือการจัดสรรหน่วยความจำต่อการจับคู่ ที่ 1k โทเค็น การใช้งานอ้างอิงจะทำคำสั่งสำเร็จประมาณ 7 ล้านคำสั่งต่อการเข้ารหัสหนึ่งครั้ง ที่ IPC 2.8 โดยส่วนใหญ่อยู่ในการเรียกตัวจัดสรรหน่วยความจำและการแปลงสตริง การพลาด L2 จะมีความสำคัญก็ต่อเมื่อผ่านพ้น ~1k โทเค็นไปแล้ว เมื่อพื้นที่การจัดสรรสะสมล้นแคชต่อคอร์

เวลาแฝง p50 และ p99 ของ reference tokenizer ตามขนาดอินพุต
อัตราการพลาดแคช L2 ของ reference tokenizer ตามขนาดอินพุต
จำนวนไบต์ที่จัดสรรต่อการ encode โดย reference tokenizer ในขนาดอินพุตต่าง ๆ

การจัดสรรหน่วยความจำต่อโทเค็นมีค่าคงที่: ประมาณ 2 KB และ ~18 การจัดสรรต่อโทเค็น โดยไม่คำนึงถึงขนาดของอินพุต ความไม่เป็นเชิงเส้นของความหน่วงมาจาก L2: ไบต์สะสมเกิน 2 MB ที่ประมาณ 1k โทเค็น อัตราการพลาดไต่ขึ้นจาก 8% เป็น ~50% และเส้นโค้ง p99 โค้งตามไป

วิธีการที่เราใช้ในการวัด

เราเปรียบเทียบ tokenizer ในระบบจริงสามตัว ซึ่งทั้งหมดทำงานด้วยอัลกอริทึม Unigram แบบเดียวกันกับโมเดล XLM-RoBERTa ตัวเดียวกัน:

เอนจิน

ภาษา

ทรี

Hugging Face

Rust

ทรีคำนำหน้าแบบ HashMap-children

SentencePiece

C++

ทรีอาร์เรย์คู่แบบ Darts (Darts double-array trie)

IREE tokenizer

C

ทรีอาร์เรย์คู่แบบ Darts (Darts double-array trie)

การใช้งาน tokenizer ภาษา และการแทนค่า trie ที่ใช้ในการเปรียบเทียบ

เราเชื่อมโยง SentencePiece และ IREE ผ่าน C/C++ FFI โดยตรง แทนที่จะใช้ตัวห่อหุ้ม (wrapper) ภาษา 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

เวลาแฝงของ tokenizer จำนวนคำสั่ง IPC และการจัดสรรหน่วยความจำที่ 514 โทเค็น

SP และ IREE มีความหน่วงเหลือเพียงประมาณหนึ่งในสามของการอ้างอิง ทำงานโดยใช้คำสั่งน้อยกว่าประมาณครึ่งหนึ่ง รันด้วย IPC ที่สูงกว่า และมีการจัดสรรหน่วยความจำน้อยกว่าถึงหนึ่งถึงสองระดับ

ทำไม SentencePiece และ IREE ถึงเร็วกว่า: ทรีอาร์เรย์คู่ (Double-Array Trie)

ทั้ง 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 */ }

การสำรวจทรีในแต่ละขั้นตอนต้องการเพียงการโหลดอาร์เรย์สองครั้ง, การบวกจำนวนเต็มหนึ่งครั้ง และการเปรียบเทียบหนึ่งครั้ง โดยไม่มีการแฮช, ไม่มีไล่พอยเตอร์ และไม่มีการจัดสรรฮีปต่อโหนด กระบวนการสร้างจะวางแต่ละโหนดเพื่อให้โหนดลูกตกลงในช่องว่างในอาร์เรย์ตรวจสอบ (check array) ทำให้พ่อแม่หลายตัวสามารถใช้พื้นที่ร่วมกันได้ตราบใดที่โหนดลูกมีความแตกต่างกันที่ไบต์ถัดไป

สำหรับคำศัพท์ขนาด 250K ของ XLM-RoBERTa ทรีทั้งหมดใช้หน่วยความจำต่อเนื่องประมาณ 9 MB (~780K ช่อง × 12 ไบต์สำหรับออฟเซ็ต, การตรวจสอบ, และไอดีโทเค็นต่อช่อง) ชุดข้อมูลทำงาน (working set) ต่อการเข้ารหัสเดี่ยวมีขนาดประมาณ 100 KB ซึ่งอยู่ใน L2 ได้อย่างสบาย และตัวดึงข้อมูลล่วงหน้าของฮาร์ดแวร์ (hardware prefetcher) จะล็อกเข้ากับรูปแบบการเข้าถึงปกติ

ในทางตรงกันข้าม การอ้างอิงจะเก็บแฮชแมปของโหนดลูกต่อหนึ่งโหนด ซึ่งมีต้นทุนประมาณสี่โหลดที่มีความเกี่ยวเนื่องต่อหนึ่งขั้นตอนไบต์ ทำการแฮชไบต์, โหลดบั๊กเก็ต (bucket), ตามพอยเตอร์ไปยังรายการบั๊กเก็ต, ตามพอยเตอร์อีกตัวไปยังโหนดลูกบนฮีป จากนั้นจึงอ้างอิงแฮชแมปของตัวเองสำหรับไบต์ถัดไป วัตถุบนฮีปจะกระจัดกระจายและโหลดส่วนใหญ่พลาดแคช

ทั้ง 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 เคอร์เซอร์แบบมีสถานะ (stateful cursor API) แทนที่จะส่งคืนการจับคู่ทั้งหมดในการเรียกครั้งเดียว แต่โมเดลต้นทุนนั้นเหมือนกัน: ไอดีโทเค็นและคะแนนสามารถเข้าถึงได้เป็นดัชนีอาร์เรย์แบบแบน โดยไม่มีการจัดสรรหรือการแฮชในการเดินผ่านทรี IREE จัดสรรบัฟเฟอร์ผลลัพธ์เพียงหนึ่งชุดต่อการเข้ารหัสหนึ่งครั้ง; SP ยังจัดสรรโหนดแลตทิส (lattice node) เพิ่มเติมต่อการจับคู่ระหว่างการทำ DP รวมเป็นการจัดสรรประมาณ 1,559 ครั้งที่ 514 โทเค็น

เบสไลน์: การพอร์ตตัวอ้างอิงแบบไม่มีการจัดสรรหน่วยความจำ

ก่อนที่จะเปลี่ยนทรี เราแยกต้นทุนของอัลกอริทึมออกจากต้นทุนการใช้งาน: ตัวอ้างอิงทำงานเร็วแค่ไหนเมื่อเอางานที่ไม่จำเป็นออกไป?

เบสไลน์ยังคงรักษาทรีแบบแฮชแมปของโหนดลูกของการอ้างอิงไว้ แต่ทำการเปลี่ยนแปลงสองอย่าง สตัรคเชอร์พื้นที่ทำงานที่ผู้เรียกเป็นเจ้าของ (caller-owned scratch struct) จะเก็บตาราง 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

baseline แบบไม่จัดสรรหน่วยความจำเปรียบเทียบกับการใช้งาน tokenizer ที่มีอยู่ที่ 514 โทเค็น

การนำการสร้างสตริงต่อการจับคู่และการค้นหาแฮชแมปสำรองออก ช่วยลดจำนวนคำสั่งลง 2.4 เท่าเมื่อเทียบกับการอ้างอิง IPC ลดลงตามไปด้วย (2.86 → 2.62) เนื่องจากกระบวนการไล่พอยเตอร์ของแฮชแมป ซึ่งเดิมทีถูกซ่อนไว้เบื้องหลังงานของตัวจัดสรรหน่วยความจำ กลายเป็นต้นทุนหลักต่อไบต์ในตอนนี้

เวลาแฝง p50 และ p99 ของ reference และ baseline tokenizer แบบไม่จัดสรรหน่วยความจำตามขนาดอินพุต
อัตราการพลาดแคช L2 ของ reference และ baseline tokenizer แบบไม่จัดสรรหน่วยความจำตามขนาดอินพุต

เบสไลน์ช่วยลดความหน่วง p50 ลง 2-3 เท่าเมื่อเทียบกับการอ้างอิงในทุกขนาด และอัตราการพลาด L2 ยังคงอยู่ใกล้ระดับ 2-3% ผ่าน 2k โทเค็น เทียบกับ 8-48% ของการอ้างอิง ต้นทุนที่เหลือคือการไล่พอยเตอร์ของ HashMap ซึ่งจะได้รับการแก้ไขในส่วนถัดไป

การเพิ่มประสิทธิภาพ 1: ทรีอาร์เรย์คู่โดยไม่มีนามธรรมส่วนเกิน

ทรีแฮชแมปคือการไล่พอยเตอร์ SP และ IREE แก้ปัญหานี้ด้วยทรีอาร์เรย์คู่ (ดูส่วนก่อนหน้า) และเราหยิบยืมโครงสร้างข้อมูลเดียวกันมาใช้ ความแตกต่างคือ SP และ IREE เป็นไลบรารีเอนกประสงค์ที่รองรับอินพุตแบบสตรีมมิ่ง, ออฟเซ็ตเอาต์พุต, และโหมดการเข้ารหัสหลายแบบ ความยืดหยุ่นนั้นมีต้นทุนเป็นงานเก็บบันทึกเพิ่มเติมรอบๆ ทรี (แลตทิสใน SP, ไพปไลน์แปดขั้นตอนใน IREE) เราไม่ต้องใช้สิ่งเหล่านี้เลย ดังนั้นเราจึงฝังทรีลงในลูป Viterbi โดยตรงและตัดส่วนที่เหลือออก

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 miss%

L3 miss%

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%

เวลาแฝงของ tokenizer จำนวนคำสั่ง และอัตราการพลาดแคชหลังนำ double-array trie มาใช้

เวลาจริงลดลง 2.3 เท่าจากเบสไลน์และ 4.8 เท่าจากการอ้างอิง จำนวนคำสั่งลดลงอีก 28% จากเบสไลน์ การตัดแลตทิสและไพปไลน์ออกช่วยให้เราทำคำสั่งสำเร็จ 1.10M คำสั่งต่อการเข้ารหัส เทียบกับ 1.82M ของ SP และ 1.61M ของ IREE ที่รูปร่างทรีเดียวกัน ส่วนต่างคือค่างานเก็บบันทึกที่พวกมันรักษาไว้สำหรับ API เอนกประสงค์ที่เราไม่ต้องใช้

การเพิ่มประสิทธิภาพ 2: บิตแมปและการแพ็คอินไลน์

ทรี Darts จากการเพิ่มประสิทธิภาพ 1 ต้องใช้โหลดที่มีความเกี่ยวเนื่องสองครั้งต่อขั้นตอนไบต์ เริ่มจากออฟเซ็ต base ของพ่อแม่ จากนั้นจึงไปที่รายการ check ที่ช่องลูกที่เป็นไปได้เพื่อยืนยันว่าพ่อแม่เป็นเจ้าของมัน รายการ check ใช้สำหรับตรวจสอบความเป็นเจ้าของเท่านั้น คำถามเดียวกันนี้สามารถตอบได้ด้วยบิตแมปต่อหนึ่งโหนดที่บันทึกว่าไบต์ใดที่มีโหนดลูก ตามโครงสร้างของทรีอาร์เรย์คู่ บิตสำหรับไบต์ b ในบิตแมปของพ่อแม่จะถูกตั้งค่าก็ต่อเมื่อช่องที่เป็นไปได้สำหรับไบต์นั้นถูกเป็นเจ้าของโดยพ่อแม่ บิตแมปและอาร์เรย์ check มีข้อมูลเดียวกัน ดังนั้นเราจึงสามารถตัดอาร์เรย์ check ออกจากโครงสร้างรันไทม์ได้อย่างสมบูรณ์

การค้นหาบิตแมปคอมไพล์เป็นการทดสอบบิตเดียวกับคำขนาด 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) }

ในขณะเดียวกัน เราแพ็คฟิลด์สี่รายการต่อโหนด (บิตแมป, base, ไอดีโทเค็น, และคะแนน) ลงในแคชไลน์ขนาด 64 ไบต์หนึ่งชุด การเยี่ยมชมโหนดเดียวตอนนี้ดึงทุกอย่างเข้ามา: คะแนนและไอดีโทเค็นที่เราต้องการที่โหนดปลายทาง รวมถึงบิตแมปและ base สำหรับขั้นตอนถัดไป อาร์เรย์ check ถูกใช้เฉพาะระหว่างการสร้างและถูกตัดออกจากเลย์เอาต์รันไทม์ การทำดัชนีเส้นทางวิกฤตไม่มีการตรวจสอบ (unchecked) เนื่องจากกระบวนการสร้างทรีและโครงสร้างลูปรับประกันขอบเขตอยู่แล้ว ข้อแลกเปลี่ยนคือสเปซ: ที่ 64 ไบต์ต่อโหนด × ~780K ช่อง ทรีจึงเติบโตจาก ~9 MB เป็น ~50 MB

ผลลัพธ์ที่ 514 โทเค็น:

เอนจิน

p50

p99

คำสั่ง

การเข้าถึง L2

L2 miss%

L3 miss%

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%

ผลลัพธ์ของ tokenizer ที่ 514 โทเค็นหลังเพิ่ม bitmap และ inline packing

เวลาจริงลดลงอย่างเป็นระบบอีก 4.5% ที่ 514 โทเค็น และเพิ่มขึ้นตามความยาวของอินพุต โดยไปถึง 6-7% ที่ 4k และ 16k การตัดอาร์เรย์ check ออกเปลี่ยนขั้นตอนทรีต่อไบต์จากการโหลดแคชไลน์สองครั้งเหลือเพียงครั้งเดียว ซึ่งทำให้การเข้าถึง L2 น้อยลง 2.5 เท่าต่อการเข้ารหัส (1.8K เทียบกับ 4.6K ของ Darts แบบปกติ) อัตราการพลาดพุ่งขึ้นจาก 6% เป็น 20% แต่ส่วนใหญ่เป็นผลมาจากตัวหาร: ด้วยจำนวนการเข้าถึงที่น้อยกว่าครึ่งหนึ่ง การพลาดที่เรามีจึงคิดเป็นสัดส่วนที่ใหญ่กว่า

การเพิ่มประสิทธิภาพ 3: ฮิวจ์เพจสำหรับไทร

ข้อมูลทรีมีขนาดประมาณ 50 MB (780,000 โหนดที่ 64 ไบต์ต่อโหนด) บนกระบวนการ Linux เริ่มต้น หน่วยความจำนั้นสนับสนุนด้วยเพจขนาด 4 KB ดังนั้นทรีทั้งหมดจึงครอบคลุมเพจเสมือนที่แตกต่างกันประมาณ 12,000 เพจ ซึ่งเกินกว่าที่บัฟเฟอร์ Translation Lookaside ข้อมูลระดับแรกของ CPU จะสามารถเก็บได้ (Sapphire Rapids มี 96 รายการ) แต่ละขั้นตอนของ Viterbi สัมผัสโหนดที่แตกต่างกัน และในการเข้ารหัส 512 โทเค็น เราเผาผลาญรอบการทำงานประมาณ 9,000 ไซเคิลในการเดินตารางเพจ (page-table walks) ซึ่งคิดเป็นประมาณ 3% ของงบประมาณต่อการเข้ารหัส

การแก้ไขคือการสนับสนุนทรีด้วย 2 MB huge pages แทนที่จะเป็น 4 KB ขนาด 50 MB เท่าเดิมตอนนี้ครอบคลุม 25 เพจ, พอดีใน Translation Lookaside Buffer ทั้งหมด และไดเรกทอรีตารางเพจเองก็หยุดแย่งชิงแคช L2 กับทรี

Linux มีสองวิธีในการสนับสนุนหน่วยความจำด้วยเพจขนาด 2 MB วิธีแรกคือ transparent huge pages (THP): โปรแกรมของคุณขอให้เคอร์เนลอัปเกรดภูมิภาคหน่วยความจำจากเพจ 4 KB เป็น 2 MB และเธรดเคอร์เนลเบื้องหลังพยายามทำเช่นนั้นเมื่อมีเวลาและหน่วยความจำจริงแบบต่อเนื่องพร้อมใช้งาน อีกทางเลือกหนึ่งคือการจัดสรรทรีโดยตรงจากพูล 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 ที่ตั้งค่าตอนบูต) บนอินสแตนซ์การใช้งานจริงของเรา มีการจอง huge pages ไว้ 10,561 เพจ; ทรีใช้ไป 24 เพจ หลังจากคำสั่ง mmap /proc/<pid>/smaps ยืนยันภูมิภาคดังกล่าว: KernelPageSize: 2048 kB, Private_Hugetlb: 49152 kB

ผลลัพธ์ที่ได้คือเวลาจริงที่ดีขึ้น 3–12% ข้ามขนาดอินพุต ซึ่งสอดคล้องและเป็นสัดส่วนกับความยาวของชุดข้อมูลทำงาน:

โทเค็น

ไม่มี huge pages

มี huge pages

Δ

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%

เวลาแฝงของ tokenizer ทั้งแบบมีและไม่มี huge pages ในขนาดอินพุตต่าง ๆ

ผลลัพธ์ที่ยอดเยี่ยมที่สุดคือที่ 4k โทเค็น ซึ่งชุดข้อมูลทำงานมีขนาดใหญ่พอที่ทราฟฟิกตารางเพจแข่งขันกับข้อมูลทรีสำหรับแบนด์วิดท์ L2 อย่างแข็งขัน เกินกว่า 4k ผลลัพธ์จะลดลงเนื่องจากการพลาด L3 ครอบงำและการเดินตารางเพจกลายเป็นสัดส่วนที่เล็กกว่าของเวลาทั้งหมด

การเปรียบเทียบครั้งสุดท้าย

เมื่อนำการเพิ่มประสิทธิภาพทั้งสามอย่างมารวมกัน นี่คือเอนจินตัวสุดท้ายที่วัดเทียบกับ tokenizer ของ RoBERTa ตัวอื่นๆ ที่เราทดสอบ นอกเหนือจากไบนารี SentencePiece C++ และ IREE C แบบเนทีฟแล้ว เรายังได้ทดสอบ crate ตัวห่อหุ้ม Rust แบบสำเร็จรูปที่ผู้ใช้ในระบบจริงเลือกใช้ด้วย ได้แก่ sentencepiece และ iree-tokenizer crate sentencepiece มีความหน่วงสูงกว่าไบนารี C++ แบบเนทีฟ 1.6-1.9 เท่าในทุกขนาดอินพุต โดยค่าใช้จ่ายส่วนเกินมาจากตัวห่อหุ้มที่จัดสรรรายการชิ้นส่วนโทเค็นใหม่ ซึ่งแต่ละชิ้นถือสำเนาข้อความชิ้นส่วนของตัวเอง ในการเข้ารหัสแต่ละครั้ง crate iree-tokenizer กำหนดขนาดบัฟเฟอร์ภายในให้กับแต่ละอินพุต ซึ่งหลีกเลี่ยงการจัดสรรต่อการเข้ารหัสแบบคงที่ที่ไบนารี IREE แบบเนทีฟต้องจ่ายโดยไม่คำนึงถึงขนาดอินพุต และนั่นมีความสำคัญมากที่สุดที่อินพุตสั้นซึ่งการจัดสรรจะครอบงำงานการทำโทเค็นจริง ที่ความยาวอินพุตในระดับการใช้งานจริง ต้นทุนคงที่นี้จะถูกเกลี่ย (amortize) และค่าใช้จ่ายส่วนเกินต่อการเรียกของตัวห่อหุ้มจากการคัดลอกโทเค็นกลับเข้าไปใน Rust ทำให้ความหน่วงสูงกว่าไบนารีแบบเนทีฟ

เวลาแฝง p50 และ p99 ต่อการ encode ในหลายการใช้งาน tokenizer และขนาดอินพุต

เอนจินสุดท้ายรัน Viterbi แบบเดียวกันบนคำศัพท์ 250,000 โทเค็นตัวเดียวกัน, ไม่มีการจัดสรรหน่วยความจำบนเส้นทางวิกฤต, และให้ผลลัพธ์ที่ตรงกันทุกโทเค็นเทียบกับการอ้างอิง แต่ละขั้นตอนไบต์ตอนนี้เป็นการโหลดแคชไลน์ขนาด 64 ไบต์ครั้งเดียว, การทดสอบบิตแมปหนึ่งครั้ง, และการบวกจำนวนเต็มหนึ่งครั้ง ลดลงจากการตรวจสอบ HashMap, การเรียกตัวจัดสรรหน่วยความจำ, และสาขาเคสพิเศษหลายสาขาในการใช้งานแบบเบสไลน์ คำสั่งต่อการเข้ารหัสลดลงจาก 3.66M เป็น 1.04M ซึ่งลดลง 3.5 เท่า เวลาจริงตรงกับอัตราส่วนนั้นที่อินพุตสั้นและกว้างขึ้นที่อินพุตยาว ซึ่งการจัดสรรต่อโทเค็นของการอ้างอิงเริ่มล้น L2 และ L3

ความคิดส่งท้าย

ในการใช้งานจริง งานนี้ช่วยลดการใช้ CPU ในเลเยอร์การประมวลผลล่วงหน้าของสแตกการอนุมานของเราลง 5-6 เท่า และช่วยลดความหน่วงของตัวจัดอันดับใหม่ (reranker) ลงได้ในระดับมิลลิวินาทีสองหลัก

ส่วนใหญ่ของการลดความหน่วงมาจากการเปลี่ยนแปลงน้ำหนักเบาที่นำงานที่สูญเปล่าออกไป: การตัดการจัดสรรต่อการเข้ารหัสออก, การแทนที่ทรี HashMap-children ด้วยอาร์เรย์คู่, และการตัดค่าใช้จ่ายส่วนเกินของ API ทั่วไปออก การใช้บิตแมปต่อโหนดที่มีอยู่แล้วเป็นการตรวจสอบความถูกต้องและการสนับสนุนทรีด้วย 2 MB huge pages รวมกันคิดเป็น 10-20% นอกเหนือจากการเปลี่ยนไปใช้ทรีอาร์เรย์คู่ครั้งใหญ่ ขึ้นอยู่กับขนาดของอินพุต

crate ตัวห่อหุ้ม Rust สำเร็จรูปสำหรับ SentencePiece และ IREE แสดงให้เห็นประเด็นเดียวกันในทางกลับกัน นอกเหนือจาก tokenizer ภาษา C และ C++ แบบเนทีฟแล้ว ขอบเขต FFI และการจัดสรรต่อการเรียกที่ตัวห่อหุ้มแนะนำสามารถมองเห็นได้ในตัวเลขความหน่วง ซอร์สโค้ด Rust สำหรับตัวเข้ารหัส Viterbi ตัวสุดท้ายมีอยู่ที่ 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}
}