שיפור ביצועי ה-CPU של מקודד unigram

מימשנו מחדש את המקודד (tokenizer) מסוג Unigram מאפס כפרויקט ממוקד שיפור ביצועים.

מחבריםPerplexity Research

מימשנו מחדש את המקודד (tokenizer) מסוג Unigram מאפס כפרויקט ממוקד שיפור ביצועים. באורכי קלט של סביבת הייצור (production), המקודד החדש מקצץ את השהיית (latency) ה-p50 בערך פי 5 לעומת ספריית ה-tokenizers של Hugging Face, פי 2 בקירוב לעומת SentencePiece (ב-C++), ופי 1.5 בקירוב לעומת המקודד של IREE (ב-C), ללא הקצאות ערימה (heap allocations) במצב מתמיד (steady-state). בסביבת הייצור, הדבר הפחית את ניצול ה-CPU במחסנית ההסקה (inference stack) פי 5-6 וקיצץ אלפיות שנייה דו-ספרתיות מהשהיית המדטרג (reranker).

מוטיבציה

עלויות האינפרנס של LLM מוצגות בדרך כלל כעבודה של GPU: מטמוני KV, קרנלים של attention, ניתוב מומחים. אבל חלק משמעותי מתעבורת הייצור רץ על מודלים הרבה יותר קטנים, קטנים בשניים עד שלושה סדרי גודל מ-transformers מהשורה הראשונה. מודלים של embeddings, מסווגים ו-rerankers עדיין רצים על GPUs, אבל ה-forward pass קצר מספיק כדי שכל מה שסביבו יתחיל להיות חשוב.

המקרה הברור ביותר הוא מדטרג המדרג מאות מסמכים מועמדים לכל בקשה. במודל קטן, חישוב ה-GPU מסתיים בדרך כלל באלפיות שנייה חד-ספרתיות, אך כל קלט עדיין חייב לעבור תחילה דרך תהליך הקידוד (tokenization) בצד ה-CPU, ההופך טקסט למזהי אוצר מילים (vocabulary IDs). כאשר האצווה (batch) גדולה, הדבר עלול להוות שברים משמעותיים מהשהיית הבקשה הכוללת.

עבודה זו מתמקדת ב-XLM-RoBERTa, אוצר מילים מסוג Unigram של 250 אלף טוקנים שאומן באמצעות SentencePiece. מקודדי RoBERTa מכווננים-מחדש הם בחירה נפוצה למשימות דירוג, אחזור ודמיון. אנו מדווחים לאורך כל הדרך על השהיה לכל encode ב-thread יחיד; בייצור אנו מבצעים מקביליזציה על פני ליבות באמצעות rayon.

לאורך פוסט זה אנו מתייחסים ל-ספריית ה-tokenizers של Hugging Face כאל הייחוס (reference) מולו אנו מבצעים בנצ'מרק, מכיוון שהיא מקודד ה-Rust ברירת המחדל שאליו מגיעים מרבית הצוותים. SentencePiece (ב-C++) ו-IREE (ב-C) כלולות לצורך השוואה כשתי מימושים עיקריים נוספים בסביבת הייצור.

אלגוריתם ויטרבי

קידוד טוקנים מסוג Unigram, שהוצג על ידי Kudo בשנת 2018 (רגולריזציה של תת-מילים: שיפור מודלי תרגום של רשתות עצביות עם מספר מועמדים לתת-מילים) ושוחרר ב-SentencePiece, מתאר פיצול כבעיית המסלול הסביר ביותר (most-probable-path): לכל טוקן באוצר המילים יש הסתברות-לוגית (log-probability) נלמדת, והמקודד בוחר את הפיצול שציוני הטוקנים שלו מסתכמים לערך הגבוה ביותר. הבעיה נפתרת באמצעות אלגוריתם ויטרבי (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 הפנימי הוא הנתיב החם (hot path): בקלט של 16 אלף טוקנים, הוא מבצע מאות אלפי מעברים ומסיים עשרות מיליוני הוראות לכל קידוד.

מימוש ייחוס

ספריית ה-tokenizers של Hugging Face (גרסה 0.22) מממשת את הרקורסיה ישירות, תוך שימוש במפת גיבוב (hash-map) לחיפוש הפוך ובבניית ילדי מפת גיבוב בכל צומת עץ (trie node):

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 קריא, אך מתבצעת בו עבודה רבה שאינה גלויה ברמת המקור. הסעיף הבא מנתח לאן הולך הזמן.

הערה על עיבוד מקדים (Preprocessing)

לפני שאלגוריתם ויטרבי רץ, הקלט עובר נורמליזציה של Unicode (סוג NFKC) וסימון גבולות מילים. ניתוח פרופיילינג קובע שעיבוד מקדים תופס פחות מ-5% מסך זמן הקידוד בתרחישים שלנו, ולכן אנו מתמקדים במעבר הקדימה של ויטרבי למשך שאר הפוסט.

היכן מימוש הייחוס מבזבז את זמנו

ישנן שתי דרכים להאיץ קוד CPU: לבצע פחות הוראות, או להשיג קצב הוראות למחזור שעון (IPC) גבוה יותר. Cachegrind מודד את הראישונה, ו-perf stat מודד את השנייה. כל אופטימיזציה בפוסט זה נופלת על האחת או על השנייה.

מעבדים נתקעים בארבעה דברים: פספוס מטמון (cache misses, כאשר L1d לוקח ~4 מחזורים, ופספוס L3 ל-DRAM מגיע למאות מחזורים), שרשראות טעינה תלויות (dependent-load chains) שמנוע ביצוע-מחוץ-לסדר (out-of-order) אינו יכול להקביל, חיזוי ענפים שגוי (~15-20 מחזורים מנוקים לכל ניחוש שגוי), וקריאות למקצה (allocator). מימוש מנוע ה-unigram של הייחוס פוגע בכל ארבעתם:

צוואר בקבוק

מנגנון

השפעה נמדדת

הקצאה לכל התאמה

הפעלת String::from_utf8 על הבייטים המותאמים בתוספת חיפוש AHashMap לכל התאמת עץ; מזהה הטוקן כבר קיים בעלה, אך מימוש הייחוס אינו שומר אותו שם

7,295 הקצאות ב-512 טוקנים, 14,542 ב-1k, 299,171 ב-16k

מרדף מצביעים (pointer chase) לכל בייט

AHashMap בכל צומת עץ, המבצע גיבוב (hashing) לבייט הבא ומחלץ הפניה (dereferencing) משני מצביעים בכל שלב; מבנה הנתונים Node גם מאגד שדות קרים כמו is_leaf, וגורר אותם אל תוך המטמון בכל ביקור

שיעור פספוס L1d נשאר נמוך (~2.5% ב-1k) מפני שעמודי המקצה החמים חיים ב-L1; העלות מתבטאת כהשהיית טעינה תלויה

שחיקת L2 (L2 thrashing) בקלט ארוך

טבלת התכנות הדינמי (DP), משטח הקידומת (prefix scratch), ורשימת טוקני הפלט מוקצים כולם מחדש בכל קריאה

שיעור פספוס L2 מטפס מ-12% ב-128 טוקנים ל-50% ב-16k כאשר נפח ההקצאות המצטבר חורג מנפח ה-L2 העומד על 2 מגה-בייט לכל ליבה

הפניות לצווארי בקבוק, מנגנונים והשפעות שנמדדו של tokenizer.

העלות הדומיננטית היא ההקצאה לכל התאמה. ב-1,000 טוקנים, מימוש הייחוס מסיים (משלים) בערך 7 מיליון הוראות לכל קידוד בקצב IPC של 2.8, רובן בקריאות מקצה ובהמרות מחרוזות. פספוסי L2 משנים רק מעבר ל-~1,000 טוקנים, ברגע שנפח ההקצאות המצטבר מציף את המטמון של כל ליבה.

זמן ההשהיה p50 ו-p99 של tokenizer הייחוס לפי גודל קלט.
שיעור פספוסי מטמון L2 של tokenizer הייחוס לפי גודל קלט.
בתים שהוקצו לכל encode על ידי tokenizer הייחוס לאורך גדלי קלט שונים.

ההקצאה לכל טוקן היא קבועה: כ-2 קילו-בייט וכ-18 הקצאות לכל טוקן, ללא קשר לגודל הקלט. חוסר הליניאריות בהשהיה מגיע מ-L2: הבייטים המצטברים חוצים את סף ה-2 מגה-בייט סביב 1,000 טוקנים, שיעור הפספוס עולה מ-8% לכ-50%, ועקומת ה-p99 מתעקמת בהתאמה.

כיצד מדדנו

אנו משווים שלושה מקודדים בסביבת ייצור, שכולם מריצים את אותו אלגוריתם Unigram מול אותו מדול XLM-RoBERTa:

מנוע

שפה

עץ (Trie)

Hugging Face

Rust

עץ קידומות מבוסס HashMap-children

SentencePiece

C++

עץ מערך-כפול Darts (Darts double-array trie)

מקודד IREE

C

עץ מערך-כפול Darts (Darts double-array trie)

מימושי tokenizer, שפות וייצוגי trie ששימשו בהשוואה.

אנו מקשרים את SentencePiece ו-IREE דרך ממשק פונקציות זרות (FFI) ישיר של C/C++ במקום מעטפות (wrappers) ה-Rust שלהם; המעטפות מוסיפות הקצאות לכל קריאה והמרות מחרוזות שאינן חלק מעלות ספריית הבסיס.

כל המנועים נבנים עם אופטימיזציות מלאות (-O3, מיקוד ל-native, אופטימיזציה בזמן קישור). המדידות רצות כשהן מוצמדות לליבה שקטה אחת על מעבד Intel Xeon Platinum 8488C. עבור כל מנוע וגודל קלט אנו אוספים את השהיית שעון-קיר (p50 ו-p99, 10,000 איטרציות לאחר 1,000 חימומים), הוראות שהושלמו באמצעות Valgrind cachegrind, קצב IPC ושיעורי פספוס מטמון ממונים של perf stat, והקצאות ערימה שנספרות על ידי עטיפת מקצה גלובלי סביב חלון המדידה.

ב-514 טוקנים (+2 מעבר ל-512 הם הזרקת BOS/EOS):

מימוש

השהיית p50

הוראות (Instructions)

IPC

הקצאות (Allocations)

Hugging Face

349 מיקרו-שנייה

3.60M

2.89

7,295

SentencePiece

128 מיקרו-שנייה

1.83M

3.39

1,559

IREE

112 מיקרו-שנייה

2.28M

3.06

1

זמן השהיה של tokenizer, ספירת הוראות, IPC והקצאות ב-514 טוקנים.

SP ו-IREE מגיעים בערך לשליש מהשהיית הייחוס. הם מסיימים בערך חצי מכמות ההוראות, רצים ב-IPC גבוה יותר, ומקצים כמות קטנה ב-1 עד 2 סדרי גודל.

מדוע SentencePiece ו-IREE מהירים יותר: עץ המערך-הכפול

SentencePiece ו-IREE משתמשים שניהם בעץ המערך-הכפול (double-array trie) שהוצג על ידי 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

חיפוש צומת בן (child lookup) הוא:

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

כל שלב במעבר העץ דורש רק שני טעינות מערך, חיבור שלמים אחד והשוואה אחת, ללא גיבוב, ללא מרדף מצביעים וללא הקצאת ערימה לכל צומת. הבנייה ממקמת כל צומת כך שילדיו נופלים על חריצים פנויים במערך האימות, מה שמאפשר להורים מרובים לחלוק אזורים כל עוד הילדים שלהם נבדלים בבייט שאחריהם.

עבור אוצר המילים של XLM-RoBERTa הכולל 250K טוקנים, כל העץ נכנס לכ-9 מגה-בייט של זיכרון רציף (~780 אלף חריצים × 12 בייט עבור הסטייה, האימות ומזהה הטוקן לכל חריץ). סט העבודה החם של קידוד בודד הוא מסדר גודל של 100 קילו-בייט, ונכנס בנוחות ב-L2, ומעמיס החומרה (hardware prefetcher) ננעל על דפוס הגישה הרגולרי.

מימוש הייחוס, לעומת זאת, שומר מפת גיבוב של ילדים לכל צומת, בעלות של כארבע טעינות תלויות לכל צעד בייט. מבצע גיבוב לבייט, טוען את הדלי (bucket), עוקב אחר מצביע לכניסת הדלי, עוקב אחר מצביע נוסף לצומת הבן על גבי הערימה, ואז מתייעץ במפת הגיבוב של עצמו עבור הבייט הבא. אובייקטי הערימה מפוזרים ורוב הטעינות מפספסות את המטמון.

גם SP וגם IREE מאחסנים את מזהה הטוקן ישירות בצומת ה-trie. מימוש ה-trie המפנה מחזיר רק את הבתים התואמים, ולכן המקודד צריך להקצות מחרוזת חדשה לכל התאמה, לחפש אותה במפת hash משנית כדי לשחזר את מזהה הטוקן, ולקרוא את הניקוד מווקטור נפרד. SP מחזיר את המזהה כערך המאוחסן של ה-trie וקורא את הניקוד ממערך float שטוח:

cpp
// unigram_model.cc:567 const size_t num_nodes = trie_->commonPrefixSearch( begin, trie_results.data(), trie_results.size(), static_cast<int>(end - begin)); for (size_t k = 0; k < num_nodes; ++k) { const int id = trie_results[k].value; // already in the trie const float score = GetScoreInlined(id); // flat float[] indexed by id Lattice::Node *node = lattice->Insert(begin_pos, length); node->id = id; node->score = score; }

IREE משתמש ב-API של סמן (cursor) בעל מצב (stateful) במקום להחזיר את כל ההתאמות בקריאה אחת, אך מודל העלות זהה: מזהי טוקנים וציונים נגישים כאינדקסים של מערך שטוח, ללא הקצאה או גיבוב במסע העץ עצמו. IREE מקצה רק חושר פלט אחד לכל קידוד; SP בנוסף מקצה צומת סריג (lattice node) לכל התאמה במהלך ה-DP, בסך הכל כ-1,559 הקצאות ב-514 טוקנים.

קו בסיס (Baseline): פורט ללא הקצאות של מימוש הייחוס

לפני שמשנים את העץ, אנו מבודדים את עלות האלגוריתם מעלות המימוש: באיזו מהירות רץ מימוש הייחוס לאחר הסרת העבודה המיותרת?

קו הבסיס שומר על עץ ילדי-מפת-הגיבוב של הייחוס אך מבצע שני שינויים. מבנה עזר בבעלות הקורא (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 מיקרו-שנייה

3.66M

2.86

7,295

SentencePiece

127 מיקרו-שנייה

1.81M

3.55

1,559

IREE

111 מיקרו-שנייה

1.58M

3.26

1

קו בסיס (Baseline)

156 מיקרו-שנייה

1.53M

2.62

0

קו הבסיס ללא הקצאות בהשוואה למימושי tokenizer קיימים ב-514 טוקנים.

הסרת יצירת המחרוזת לכל התאמה והחיפוש המשני ב-hash-map חותכת את מספר ההוראות פי 2.4 לעומת המימוש המפנה. גם ה-IPC יורד איתם (2.86 → 2.62), משום שרדיפת המצביע ב-hash-map, שבעבר הוסתרה מאחורי עבודת ה-allocator, היא כעת העלות הדומיננטית לכל בית.

זמן ההשהיה p50 ו-p99 של tokenizer הייחוס וקו הבסיס ללא הקצאות לפי גודל קלט.
שיעור פספוסי מטמון L2 של tokenizer הייחוס וקו הבסיס ללא הקצאות לפי גודל קלט.

ה-baseline חותך את זמן ההשהיה ב-p50 פי 2-3 לעומת המימוש המפנה בכל גודל, ושיעור ההחטאות ב-L2 נשאר קרוב ל-2-3% עד 2k טוקנים לעומת 8-48% במימוש המפנה. העלות שנותרה היא רדיפת המצביע ב-HashMap, ואת זה הסעיף הבא מטפל.

אופטימיזציה 1: עץ מערך-כפול ללא הפשטות מיותרות

עץ מפת-הגיבוב הוא מרדף מצביעים. 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 מגה-בייט, אך כל קידוד בודד מטייל רק בכ-100 קילו-בייט ממנו, כך שהנתונים החמים נשארים ב-L2.

מנוע

p50

p99

הוראות

פספוס L2 %

פספוס L3 %

Hugging Face

327 מיקרו-שנייה

3,340 מיקרו-שנייה

3.66M

8.17%

14.66%

SentencePiece

127 מיקרו-שנייה

1,140 מיקרו-שנייה

1.82M

4.74%

4.07%

IREE

111 מיקרו-שנייה

132 מיקרו-שנייה

1.61M

5.82%

3.87%

קו בסיס (Baseline)

155 מיקרו-שנייה

1,170 מיקרו-שנייה

1.53M

2.59%

16.66%

+ Darts

68 מיקרו-שנייה

80 מיקרו-שנייה

1.10M

6.45%

11.42%

זמן השהיה של tokenizer, הוראות ויחסי פספוסי מטמון לאחר אימוץ double-array trie.

זמן שעון-קיר יורד פי 2.3 מקו הבסיס ופי 4.8 מהייחוס. ההוראות יורדות ב-28% נוספים מקו הבסיס. הסרת הסריג והצינור מאפשרת לנו לסיים 1.10 מיליון הוראות לכל קידוד לעומת 1.82 מיליון של SP ו-1.61 מיליון של IREE באותה צורת עץ; הפער הוא ספרות הנהלת החשבונות שהם שומרים עבור ממשקי API כלליים שאיננו צריכים.

אופטימיזציה 2: מפת סיביות ואריזה בתוך השורה

עץ ה-Darts מאופטימיזציה 1 דורש שתי טעינות תלויות לכל צעד בייט. תחילה סטיית הבסיס של ההורות, לאחר מכן ערך הבדיקה (check entry) בחריץ הבן המועמד כדי לאשר שההורה הוא בעליו. ערך הבדיקה רק מאמת בעלות. ניתן לענות על אותה שאלה באמצעות מפת סיביות לכל צומת המתעדת אילו בייטים מכילים ילדים. לפי מבנה עץ המערך-הכפול, הסיבית עבור בייט 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) }

באותה הזדמנות, אנו אורזים את ארבעת השדות לכל צומת (bitmap, base, token ID, and score) לתוך שורת מטמון אחת בגודל 64 בייט. ביקור יחיד בצומת כעת טוען הכול: את הניקוד ואת מזהה הטוקן הדרושים לנו בצמתי terminal, וגם את ה-bitmap ואת ה-base לצעד הבא. מערך ה-check משמש רק בזמן הבנייה ונזרק מפריסת זמן הריצה. האינדוקס במסלול החם אינו נבדק, משום שבניית ה-trie ומבנה הלולאה כבר מבטיחים את הגבולות. הפשרה היא מקום: בגודל 64 בייט לצומת × כ-780 אלף slot-ים ה-trie גדל מכ-9 MB לכ-50 MB.

תוצאות ב-514 טוקנים:

מנוע

p50

p99

הוראות

גישות L2

פספוס L2 %

פספוס L3 %

Hugging Face

327 מיקרו-שנייה

3,340 מיקרו-שנייה

3.66M

15.0K

8.17%

14.66%

SentencePiece

127 מיקרו-שנייה

1,140 מיקרו-שנייה

1.82M

7.5K

4.74%

4.07%

IREE

111 מיקרו-שנייה

132 מיקרו-שנייה

1.61M

4.7K

5.82%

3.87%

קו בסיס (Baseline)

155 מיקרו-שנייה

1,170 מיקרו-שנייה

1.53M

6.1K

2.59%

16.66%

+ Darts

68 מיקרו-שנייה

80 מיקרו-שנייה

1.10M

4.6K

6.45%

11.42%

+ מפת סיביות ודחיסה פנימית

65 מיקרו-שנייה

77 מיקרו-שנייה

1.06M

1.8K

20.53%

15.01%

תוצאות tokenizer ב-514 טוקנים לאחר הוספת bitmap ו-inline packing.

זמן שעון-קיר יורד באופן שיטתי ב-4.5% נוספים ב-514 טוקנים וגדל עם אורך הקלט, ומגיע ל-6-7% ב-4k וב-16k. הסרת מערך הבדיקה הופכת את צעד העץ לכל בייט משתי טעינות שורת מטמון לאחת, שהן פחות גישות L2 פי 2.5 לכל קידוד (1.8K לעומת 4.6K של Darts פשוט). שיעור הפספוס קופץ מ-6% ל-20%, אך רובו נובע מהמכנה: עם פחות מחצי מכמות הגישות, הפספוסים שכן קיימים תופסים נתח גדול יותר.

אופטימיזציה 3: דפים ענקיים עבור ה-trie

נתוני העץ הם כ-50 מגה-בייט (780,000 צמתים ב-64 בייט כל אחד). בתהליך Linux ברירת מחדל, זיכרון זה מגובה בעמודים של 4 קילו-בייט, כך שהעץ המלא משתרע על פני כ-12,000 עמודים וירטואליים נפרדים, הרבה מעבר لما يمكن لـ Translation Lookaside Buffer של נתוני הרמה הראשונה של ה-CPU להכיל (ל-Sapphire Rapids יש 96 רשומות). כל צעד ויטרבי נוגע בצומת שונה, ומעל קידוד של 512 טוקנים אנו שורפים כ-9,000 מחזורים בהליכות טבלת עמודים, כ-3% מתקציב כל קידוד.

הפתרון הוא לגבות את העץ באמצעות עמודים ענקיים בגודל 2 מגה-בייט במקום עמודים של 4 קילו-בייט. אותו נפח של 50 מגה-בייט משתרע כעת על פני 25 עמודים, נכנס לחלוטין לתוך ה-Translation Lookaside Buffer, וספריות טבלת העמודים עצמן מפסיקות להתחרות בעץ על מטמון L2.

לינוקס מציעה שתי דרכים לבסס זיכרון על דפי 2 MB. הדרך האופורטוניסטית היא transparent huge pages (THP): התוכנית שלך מבקשת מהקרנל לשדרג אזור זיכרון מדפי 4 KB לדפי 2 MB, ו-thread קרנלי ברקע מנסה לעשות זאת כשהוא יכול ויש זיכרון פיזי רציף זמין. החלופה האחרת היא להקצות את ה-trie ישירות מ-pool של huge pages שהקרנל מקצה בצד בזמן האתחול:

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 מיקרו-שנייה

15.2 מיקרו-שנייה

−3.6%

514

65.4 מיקרו-שנייה

63.1 מיקרו-שנייה

−3.4%

1,026

129.5 מיקרו-שנייה

125.3 מיקרו-שנייה

−3.3%

4,098

773 מיקרו-שנייה

679 מיקרו-שנייה

−12.0%

16,386

3,808 מיקרו-שנייה

3,554 מיקרו-שנייה

−6.8%

זמן ההשהיה של tokenizer עם huge pages וללא huge pages על פני גדלי קלט שונים.

הרווח הגדול ביותר הוא ב-4k טוקנים, שבהם סט העבודה גדול מספיק כך שתעבורת טבלת העמודים התחרתה באופן פעיל עם נתוני העץ על רוחב פס L2. מעבר ל-4k הרווח מצטמצם מכיוון שפספוסי L3 שולטים והליכות טבלת עמודים הופכות לחלק קטן יותר מסך הזמן.

השוואה סופית

כאשר מאחדים את שלוש האופטימיזציות יחד, הנה המנוע הסופי הנמדד מול כל מקודד RoBERTa אחר שבחננו. לצד קבצי ה-C++ הנייטיבים של SentencePiece והבינאריים של C IREE, עשינו בנצ'מרק גם לספריות המעטפת (wrapper crates) המוכנות של Rust שמשתמש בסביבת ייצור יגיע אליהן, sentencepiece ו-iree-tokenizer. ספריית sentencepiece מודדת השהיה גבוהה פי 1.6-1.9 מאשר הבינארי הנייטיבי של C++ בכל גודל קלט, כאשר העודף נובע מכך שהמעטפה מקצה רשימה חדשה של חלקי טוקנים, שכל אחד מהם מחזיק עותק משלו של טקסט החלק, בכל קידוד. ספריית iree-tokenizer מתאימה את גודל החושר הפנימי שלה לכל קלט, מה שמונע הקצאה קבועה לכל קידוד שהבינארי הנייטיבי של IREE משלם ללא קשר לגודל הקלט, והדבר חשוב ביותר בקלטים קצרים שבהם ההקצאה הייתה שולטת אחרת בעבודת הקידוד בפועל. באורכי קלט של סביבת הייצור העלות הקבועה מתאזנת והעודף לכל קריאה של המעטפה עצמה מהעתקת טוקנים בחזרה לתוך Rust דוחף את ההשהיה שלה מעל הבינארי הנייטיבי.

זמן ההשהיה p50 ו-p99 לכל encode בין מימושי tokenizer וגדלי קלט שונים.

המנוע הסופי מריץ את אותו ויטרבי על פני אותו אוצר מילים של 250,000 טוקנים, אינו מקצה דבר בנתיב החם, ומייצר פלט תואם-טוקן (token-exact) מול הייחוס. כל צעד בייט הוא כעת טעינת שורת מטמון בת 64 בייט יחידה, בדיקת מפת סיביות אחת, וחיבור שלמים אחד, ירידה מבדיקת HashMap, קריאת מקצה ומספר ענפי מקרה-קצה במימוש קו הבסיס. הוראות לכל קידוד ירדו מ-3.66 מיליון ל-1.04 מיליון, ירידה פי 3.5. זמן שעון-קיר תואם יחס זה בקלטים קצרים ומתרחב עוד יותר בקלטים ארוכים, שבהם הקצאות לכל טוקן של הייחוס מתחילות להציף את L2 ו-L3.

מחשבות לסיום

בפועל עבודה זו הפחיתה את ניצול ה-CPU בשכבת העיבוד המקדים של מחסנית ההסקה שלנו פי 5-6 וקיצצה אלפיות שנייה דו-ספרתיות מהשהיית המדטרג.

עיקר ההפחתה בהשהיה הגיע משינויים קלי-משקל שהסירו עבודה מיותרת: ביטול הקצאות לכל encode, החלפת ה-trie מסוג HashMap-children ב-double-array, והסרת העומס של ה-API הגנרי. השימוש ב-bitmap הקיים לכל צומת כבדיקת תקינות, יחד עם גיבוי ה-trie ב-huge pages בגודל 2 MB, תרמו יחד 10-20% בנוסף למעבר הגדול יותר ל-trie מסוג double-array, בהתאם לגודל הקלט.

ספריות המעטפת המוכנות של Rust סביב SentencePiece ו-IREE ממחישות את אותה נקודה בכיוון הפוך. מעל מקודדי C ו-C++ נייטיבים, גבול ה-FFI וההקצאות לכל קריאה שמכניסות המעטפות גלויים במספרי ההשהיה. קוד המקור ב-Rust עבור מקודד ויטרבי הסופי זמין בכתובת github.com/perplexityai/pplx-garden.

מקורות

מקודדים של Hugging Face — https://github.com/huggingface/tokenizers

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

מקודד IREE — https://github.com/iree-org/iree

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

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

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

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

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

עמודים ענקיים (Huge pages) — https://docs.kernel.org/admin-guide/mm/hugetlbpage.html

ציטוט

BibTeX
@online{perplexity2026ImprovingUnigramTokenizerCpuPerformance,
  author = {{Perplexity} and Vladimir Zaytsev and Bex Brooker and Daisy Lee and Roshan Shankar},
  title = {{Improving unigram tokenizer CPU performance}},
  date = {2026-05-20},
  url = {https://www.perplexity.ai/hub/blog/improving-unigram-tokenizer-cpu-performance}
}