تحسين أداء محلل رموز Unigram على المعالج

أعدنا تطبيق محلل الرموز Unigram من الصفر كإجراء يركز على الأداء. عند أطوال المدخلات للإنتاج، يقلل المشفر الجديد من زمن الانتقال p50 بنحو 5 أضعاف مقارنة بحزمة Hugging Face tokenizers، وبنحو ضعفين (2×) مقارنة بـ SentencePiece (C++)، ونحو 1.5 ضعف مقارنة بمحلل رموز IREE (C)، مع صفر تخصيصات للكومة في حالة الاستقرار. في الإنتاج، أدى ذلك إلى تقليل استخدام المعالج (CPU) في حزمة الاستدلال لدينا بمقدار 5 إلى 6 أضعاف، واختزال زمن انتقال نموذج إعادة الترتيب بمقدار خانتين عشريتين من المللي ثانية.

عادةً ما يُنظر إلى تكلفة الاستدلال للنماذج اللغوية الكبيرة (LLM) على أنها عمل وحدة معالجة الرسومات (GPU): ذاكرة التخزين المؤقت لـ KV، ونواة الانتباه، وتوجيه الخبراء. ولكن جزءاً كبيراً من حركة مرور الإنتاج يعمل على نماذج أصغر بكثير، أصغر بدرجتين إلى ثلاث درجات من محولات الحدود. لا تزال نماذج التضمين، والمصنفات، ونماذج إعادة الترتيب تعمل على وحدات معالجة الرسومات، ولكن تمريرة التمرير الأمامي قصيرة بما يكفي بحيث يبدأ كل ما حولها في الاكتساب أهمية.

الحالة الأوضح هي نموذج إعادة ترتيب يقوم بتسجيل مئات مستندات المرشحين لكل طلب. مع نموذج صغير، عادةً ما ينتهي حساب وحدة معالجة الرسومات في خانة عشرية واحدة من المللي ثانية، ولكن لا يزال يتعين على كل مدخل أن يمر عبر تحليل الرموز على جانب المعالج أولاً، مما يحول النص إلى معرفات مفرداتية. عندما تكون الدفعة كبيرة، يمكن أن يمثل ذلك جزءاً كبيراً من إجمالي زمن انتقال الطلب.

يستهدف هذا العمل XLM-RoBERTa، وهي مفردات Unigram تضم 250 ألف رمز تم التدريب عليها باستخدام SentencePiece. تُعد المشفرات المدربة خصيصاً من عائلة RoBERTa خياراً شائعاً لمهام الترتيب، والاسترجاع، والتشابه. نحن نبلغ عن زمن انتقال أحادي الخيط لكل عملية ترميز طوال الوقت؛ وفي الإنتاج نقوم بالتوازي عبر النواة باستخدام rayon.

طوال هذا المنشور، نتعامل مع حزمة tokenizers الخاصة بـ Hugging Face كمرجع نقارن أداءنا به، نظراً لأنها محلل الرموز الافتراضي المصنوع بلغة Rust والذي تلجأ إليه معظم الفرق. يتم تضمين SentencePiece (C++) و IREE (C) للمقارنة باعتبارهما التنفيدين الرئيسيين الآخرين للإنتاج.

تحليل الرموز Unigram، الذي قدمه Kudo في عام 2018 (انتظام الكلمات الفرعية: تحسين نماذج ترجمة الشبكات العصبية مع مرشحين متعددين للكلمات الفرعية) وتم شحنه في SentencePiece، يصيغ التقسيم كمسألة المسار الأكثر احتمالاً: كل رمز مفرداتي له احتمال لوغاريتمي متعلَّم، ويختار المشفر التقسيم الذي تجمَع درجات رموزه لأعلى قيمة. يتم حل المشكلة باستخدام خوارزمية فيتربي (1967)، مع مواضع البايت كطبقات رسم بياني ورموز المفردات كحواف تمتد عبر نطاق بايت متجاور. التكرار هو برمجة ديناميكية أحادية البعد عبر مواضع البايت:

python

best = [-inf] * (n + 1)
best[0] = 0
back = [None] * (n + 1)

for i in 0..n:
    if best[i] == -inf:
        continue
    if byte i is a UTF-8 continuation byte:
        continue

    walk the vocabulary trie from byte position i:
        for each matching token t ending at position j:
            cand = best[i] + score(t)
            if cand > best[j]:
                best[j] = cand
                back[j] = (i, token_id(t))

    if no token matched, fall back to <unk>

backtrack from position n using back[] to recover token IDs

الحلقة الخارجية خطية في طول المدخل، ومحدودة في كل موضع بأطول رمز مفرداتي (48 بايت UTF-8 لـ XLM-RoBERTa). جولة التراي الداخلية هي المسار الساخن: على مدخل بـ 16 ألف رمز، تُجري مئات الآلاف من عمليات الانتقال وتسحب عشرات الملايين من التعليمات لكل عملية ترميز.

تنفذ حزمة tokenizers v0.22 التابعة لـ Hugging Face التكرار مباشرةً، باستخدام خريطة تجزئة للبحث العكسي وأطفال خريطة تجزئة عند كل عقدة تراي:

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 مقروءة، ولكن يحدث الكثير من العمل الذي يكون غير مرئي على مستوى المصدر. يحلل القسم التالي أين تذهب تلك الوقت.

قبل تشغيل فيتربي، يمر المدخل عبر تطبيع Unicode (NFKC) وتحديد حدود الكلمات. يجعل التوصيف المعالجة المسبقة أقل من 5% من إجمالي وقت الترميز في سيناريوهاتنا، لذا نركز على تمريرة فيتربي الأمامية لبقية المنشور.

هناك طريقتان لتسريع كود المعالج: تنفيذ تعليمات أقل، أو الحصول على IPC أعلى. يقيس Cachegrind الأولى، ويقيس perf stat الثانية. كل تحسين في هذا المنشور يقع على أحدهما أو الآخر.

تتوقف معالجات (CPUs) عن العمل لأربعة أسباب: إخفاقات ذاكرة التخزين المؤقت (L1d ~4 دورات، وإخفاق L3 إلى DRAM بالمئات)، وسلاسل التحميل التابعة التي لا يستطيع محرك التنفيذ غير المرتب جعلها متوازية، والأخطاء في التنبؤ بالتفرع (~15-20 دورة يتم مسحها لكل تخمين خاطئ)، ومكالمات المخصص. يحقق التنفيذ المرجعي لمحرك unigram جميع الأربعة:

عنق الزجاجة	الآلية	التأثير المقاس
التخصيص لكل مطابقة	String::from_utf8 على البايتات المطابقة بالإضافة إلى بحث AHashMap لكل مطابقة تراي؛ معرف الرمز موجود بالفعل في الورقة، لكن المرجع لا يخزنه هناك	7,295 تخصيصاً عند 514 رمزاً، 14,542 عند 1k، 299,171 عند 16k
مطاردة المؤشر لكل بايت	AHashMap عند كل عقدة تراي، مع تجزئة البايت التالي وإلغاء مرجعية مؤشرين لكل خطوة؛ يجمع هيكل العقدة أيضاً الحقول الباردة مثل is_leaf، مما يجرها إلى ذاكرة التخزين المؤقت عند كل زيارة	يبقى معدل إخفاق L1d منخفضاً (~2.5% عند 1k) لأن صفحات المخصص الساخنة تعيش في L1؛ تظهر التكلفة كزمن انتقال التحميل التابع
إرهاق L2 على المدخلات الطويلة	جدول DP، ومسودة البادئة، وقائمة رموز الإخراج كلها مخصصة حديثاً مع كل استدعاء	يرتفع معدل إخفاق L2 من 12% عند 128 رمزاً إلى 50% عند 16k حيث يتجاوز بصمة التخصيص التراكمية ذاكرة L2 البالغة 2 ميغابايت لكل نواة

مرجع عن اختناقات أداة التقسيم، وآلياتها، والتأثيرات المقاسة.

التكلفة المهيمنة هي التخصيص لكل مطابقة. عند 1k رمز، يُكمل (ينهي) التنفيذ المرجعي ما يقرب من 7M تعليمة لكل ترميز بـ IPC قدره 2.8، معظمها في مكالمات المخصص وتحويلات النصوص. إخفاقات L2 لا تهم إلا بعد ~1k رمز، بمجرد أن يفيض بصمة التخصيص التراكمية لذاكرة التخزين المؤقت لكل نواة.

زمن استجابة p50 وp99 لأداة التقسيم المرجعية حسب حجم الإدخال.

معدل أخطاء L2 في ذاكرة التخزين المؤقت لأداة التقسيم المرجعية حسب حجم الإدخال.

البايتات المخصَّصة لكل عملية ترميز بواسطة أداة التقسيم المرجعية عبر أحجام الإدخال.

التخصيص لكل رمز ثابت: حوالي 2 كيلوبايت و ~18 تخصيصاً لكل رمز، بغض النظر عن حجم المدخل. عدم خطية زمن انتقال يأتي من L2: البايتات التراكمية تقطع 2 ميغابايت حول 1k رمز، ويرتفع معدل الإخفاق من 8% إلى ~50%، وينحني منحنى p99 ليتطابق.

نقارن بين ثلاثة محللات رموز للإنتاج، كلها تشغل نفس خوارزمية Unigram مقابل نفس نموذج XLM-RoBERTa:

المحرك	اللغة	التراي
Hugging Face	Rust	تراي البادئة لأطفال HashMap
SentencePiece	C++	تراي مصفوفة مزدوجة Darts
محلل رموز IREE	C	تراي مصفوفة مزدوجة Darts

تنفيذات أداة التقسيم، واللغات، وتمثيلات trie المستخدمة في المقارنة.

نحن نربط SentencePiece و IREE عبر FFI مباشر لـ C/C++ بدلاً من الغلافات الخاصة بها بلغة 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 ميكروثانية	3.60 مليون	2.89	7,295
SentencePiece	128 ميكروثانية	1.83 مليون	3.39	1,559
IREE	112 ميكروثانية	2.28 مليون	3.06	1

زمن استجابة أداة التقسيم، وعدد التعليمات، وIPC، والتخصيصات عند 514 رمزًا.

تستقر SP و IREE عند حوالي ثلث زمن الانتقال الخاص بالمرجع. وهما تسحبان حوالي نصف عدد التعليمات، وتعملان عند IPC أعلى، وتخصصان من مرتبة إلى مرتبتين عشريتين أقل.

تستخدم كل من SentencePiece و IREE تراي المصفوفة المزدوجة التي قدمها Aoe في عام 1989 (Aoe, 1989; Karoonboonyanan). يتم ترميز التراي في مصفوفتين صحيحتين مسطحتين، base و check:

cpp

int base[N];   // base[node] = offset for this node's children
int check[N];  // check[child] == node validates the parent-child link

البحث عن الطفل هو:

cpp

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

تتطلب كل خطوة من خطوات اجتياز التراي قراءتي مصفوفة فقط، وجمع أقيمتين صحيحتين، ومقارنة واحدة، بدون تجزئة، وبدون مطاردة مؤشرات، وبدون تخصيص كومة لكل عقدة. يضع البناء كل عقدة بحيث يقع أطفالها على فتحات مجانية في مصفوفة التحقق، مما يسمح لعدة آباء بمشاركة المناطق طالما اختلف أطفالهم في البايت الذي يتبعونه.

بالنسبة لمفردات XLM-RoBERTa التي تبلغ 250 ألفاً، تتناسب التراي بأكملها في حوالي 9 ميغابايت من الذاكرة المتجاورة (~780 ألف فتحة × 12 بايت للإزاحة والتحقق ومعرف الرمز لكل فتحة). مجموعة العمل الساخنة لعملية ترميز واحدة تكون في حدود 100 كيلوبايت، بشكل مريح في 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، ليصبح المجموع حوالي 1,559 تخصيصاً عند 514 رمزاً.

قبل تغيير التراي، نعزل تكلفة الخوارزمية عن تكلفة التنفيذ: ما مدى سرعة تشغيل المرجع مع إزالة العمل غير الضروري؟

يحتفظ خط الأساس بتراي أطفال خريطة التجزئة الخاصة بالمرجع ولكنه يجرى تغييرين. يحمل هيكل مسودة مملوك للمستدعي جدول 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.66 مليون	2.86	7,295
SentencePiece	127 ميكروثانية	1.81 مليون	3.55	1,559
IREE	111 ميكروثانية	1.58 مليون	3.26	1
خط الأساس	156 ميكروثانية	1.53 مليون	2.62	0

خط الأساس عديم التخصيص مقارنةً بتنفيذات أداة التقسيم الحالية عند 514 رمزًا.

أدت إزالة مادية النصوص لكل مطابقة والبحث في خريطة التجزئة الثانوية إلى تقليل التعليمات بمقدار 2.4 ضعف مقارنة بالمرجع. ينخفض IPC معها (2.86 ← 2.62) لأن مطاردة مؤشر خريطة التجزئة، والتي كانت مخفية سابقاً خلف عمل المخصص، أصبحت الآن التكلفة المهيمنة لكل بايت.

زمن استجابة p50 وp99 لأداة التقسيم المرجعية وخط الأساس عديم التخصيص حسب حجم الإدخال.

معدل أخطاء L2 في ذاكرة التخزين المؤقت لأداة التقسيم المرجعية وخط الأساس عديم التخصيص حسب حجم الإدخال.

يقلل خط الأساس زمن الانتقال p50 بمقدار 2 إلى 3 أضعاف مقارنة بالمرجع عند كل حجم، ويظل معدل إخفاق L2 الخاص به قريباً من 2-3% من خلال 2k رمز مقارنة بـ 8-48% للمرجع. التكلفة المتبقية هي مطاردة مؤشر HashMap، والتي يعالجها القسم التالي.

تراي خريطة التجزئة هي مطاردة مؤشر. تحل SP و IREE هذه المشكلة باستخدام تراي مصفوفة مزدوجة (انظر القسم السابق)، ونحن نستعير نفس هيكل البيانات. الفرق هو أن SP و IREE هما مكتبتان عامتا الغرض تدعمان الإدخال المتدفق، وإزاحات الإخراج، وأوضاع ترميز متعددة؛ تكلف تلك المرونة bookkeeping إضافياً حول التراي (شبكة في 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.66 مليون	8.17%	14.66%
SentencePiece	127 ميكروثانية	1,140 ميكروثانية	1.82 مليون	4.74%	4.07%
IREE	111 ميكروثانية	132 ميكروثانية	1.61 مليون	5.82%	3.87%
خط الأساس	155 ميكروثانية	1,170 ميكروثانية	1.53 مليون	2.59%	16.66%
+ Darts	68 ميكروثانية	80 ميكروثانية	1.10 مليون	6.45%	11.42%

زمن استجابة أداة التقسيم، والتعليمات، ومعدلات أخطاء ذاكرة التخزين المؤقت بعد اعتماد trie ثنائي المصفوفة.

ينخفض وقت ساعة الحائط بمقدار 2.3 ضعف عن خط الأساس و 4.8 ضعف عن المرجع. تنخفض التعليمات بنسبة 28% أخرى عن خط الأساس. يتيح لنا قطع الشبكة وخط الأنابيب سحب 1.10 مليون تعليمة لكل ترميز مقابل 1.82 مليون لـ SP و 1.61 مليون لـ IREE بنفس شكل التراي؛ الفجوة هي الـ bookkeeping الذي يحتفظون به لواجهات برمجة التطبيقات ذات الغرض العام التي لا نحتاجها.

تحتاج تراي Darts من التحسين 1 إلى عمليتي تحميل تباريتين لكل خطوة بايت. أولاً إزاحة قاعدة الأب، ثم إدخال التحقق في فتحة الطفل المرشح لتأكيد أن الأب يمتلكها. إدخال التحقق يثبت الملكية فقط. يمكن الإجابة على نفس السؤال بواسطة خريطة بت لكل عقدة تسجل البايتات التي لها أطفال. بناءً على تصميم تراي المصفوفة المزدوجة، يتم تعيين البت للبايت 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)
}

بينما نحن في صدد ذلك، نقوم بتعبئة الحقول الأربعة لكل عقدة (خريطة البت، القاعدة، معرف الرمز، والدرجة) في خط ذاكرة تخزين مؤقت واحد بحجم 64 بايت. تجلب زيارة عقدة واحدة الآن كل شيء: الدرجة ومعرف الرمز اللذين نحتاجهما في العقد الطرفية، بالإضافة إلى خريطة البت والقاعدة للخطوة التالية. تُستخدم مصفوفة التحقق فقط أثناء البناء ويتم إسقاطها من تخطيط وقت التشغيل. فهرسة المسار الساخن غير مفحوصة لأن بناء التراي وهيكل الحلقة يضمنان الحدود بالفعل. المقايضة هي المساحة: عند 64 بايت لكل عقدة × ~780 ألف فتحة، تنمو التراي من ~9 ميغابايت إلى ~50 ميغابايت.

النتائج عند 514 رمزاً:

المحرك	p50	p99	التعليمات	عمليات الوصول إلى L2	نسبة إخفاق L2%	نسبة إخفاق L3%
Hugging Face	327 ميكروثانية	3,340 ميكروثانية	3.66 مليون	15.0 ألف	8.17%	14.66%
SentencePiece	127 ميكروثانية	1,140 ميكروثانية	1.82 مليون	7.5 ألف	4.74%	4.07%
IREE	111 ميكروثانية	132 ميكروثانية	1.61 مليون	4.7 ألف	5.82%	3.87%
خط الأساس	155 ميكروثانية	1,170 ميكروثانية	1.53 مليون	6.1 ألف	2.59%	16.66%
+ Darts	68 ميكروثانية	80 ميكروثانية	1.10 مليون	4.6 ألف	6.45%	11.42%
+ خريطة البت والتعبئة المضمنة	65 ميكروثانية	77 ميكروثانية	1.06 مليون	1.8 ألف	20.53%	15.01%

نتائج أداة التقسيم عند 514 رمزًا بعد إضافة bitmap والتعبئة الداخلية.

ينخفض وقت ساعة الحائط بشكل منتظم بنسبة 4.5% أخرى عند 514 رمزاً وينمو مع طول المدخل، ليصل إلى 6-7% عند 4k و 16k. يؤدي إسقاط مصفوفة التحقق إلى تحويل خطوة التراي لكل بايت من تحميلين لخط ذاكرة التخزين المؤقت إلى تحميل واحد، وهو ما يمثل عدد عمليات وصول أقل لـ L2 بمقدار 2.5 ضعف لكل عملية ترميز (1.8 ألف مقابل 4.6 ألف لـ Darts العادية). يرتفع معدل الإخفاق من 6% إلى 20%، ولكن الجزء الأكبر من ذلك يرجع إلى المقام: مع أقل من نصف عدد عمليات الوصول، تأخذ الإخفاقات التي نواجهها حصة أكبر.

بيانات التراي تبلغ حوالي 50 ميغابايت (780,000 عقدة بحجم 64 بايت لكل منها). في عملية لينكس افتراضية، يتم دعم هذه الذاكرة بصفحات بحجم 4 كيلوبايت، لذا تمتد التراي الكاملة عبر حوالي 12,000 صفحة افتراضية متميزة، وهو ما يتجاوز بكثير ما يمكن تخزينه في مخزن مؤقت ترجمة العناوين للبيانات في المستوى الأول للمعالج (يحتوي Sapphire Rapids على 96 إدخالاً). تلمس كل خطوة من خطوات فيتربي عقدة مختلفة، وعبر عملية ترميز بـ 512 رمزاً نحرق ما يقرب من 9,000 دورة في عمليات المشي في جدول الصفحات، حوالي 3% من ميزانية كل عملية ترميز.

الحل هو دعم التراي بصفحات ضخمة بحجم 2 ميغابايت بدلاً من صفحات 4 كيلوبايت. نفس ال50 ميغابايت تمتد الآن على 25 صفحة، وتتناسب بالكامل في مخزن مؤقت ترجمة العناوين، وتتوقف دلائل جدول الصفحات نفسها عن التنافس مع التراي على ذاكرة L2 المؤقتة.

يحتوي لينكس على طريقتين لدعم الذاكرة بصفحات بحجم 2 ميغابايت. الطريقة الانتهازية هي الصفحات الضخمة الشفافة (THP): يطلب برنامجك من النواة ترقية منطقة ذاكرة من صفحات 4 كيلوبايت إلى 2 ميغابايت، وتحاول سلسلة خلفية للنواة القيام بذلك عندما يكون لديها الوقت والذاكرة الفيزيائية المتجاورة المتاحة. البديل الآخر هو تخصيص التراي مباشرة من مسبح صفحات ضخمة محجوز مسبقاً تخصصه النواة جانباً عند الإقلاع:

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%

زمن استجابة أداة التقسيم مع الصفحات الضخمة وبدونها عبر أحجام الإدخال.

أكبر مكسب هو عند 4k رمز، حيث تكون مجموعة العمل كبيرة بما يكفي لكي تتنافس حركة مرور جدول الصفحات بشكل نشط مع بيانات التراي على نطاق L2 الترددي. ما بعد 4k يتقلص المكسب لأن إخفاقات L3 تهيمن وتصبح عمليات المشي في جدول الصفحات حصة أصغر من إجمالي الوقت.

بجمع التحسينات الثلاثة معاً، إليك المحرك النهائي مقيساً ضد كل محلل رموز RoBERTa آخر اختبرناه. إلى جانب ثنائيات C++ SentencePiece و C IREE الأصلية، قمنا أيضاً بقياس حزم غلاف Rust الجاهزة التي يلجأ إليها مستخدم الإنتاج، sentencepiece و iree-tokenizer. تقيس حزمة sentencepiece زمن انتقال أعلى بـ 1.6-1.9 ضعف من ثنائي C++ الأصلي عند كل حجم مدخل، مع قدوم النفقات العامة من الغلاف الذي يخصص قائمة جديدة من قطع الرموز، تحمل كل منها نسختها الخاصة من نص القطعة، في كل عملية ترميز. تحجم حزمة iree-tokenizer مخزنها المؤقت الداخلي لكل مدخل، مما يتجنب تخصيصاً ثابتاً لكل ترميز يدفعه ثنائي IREE الأصلي بغض النظر عن حجم المدخل، وهذا يهم أكثر في المدخلات القصيرة حيث يهيمن التخصيص بخلاف ذلك على عمل تحليل الرموز الفعلي. عند أطوال مدخلات الإنتاج، تتلاشى التكلفة الثابتة وتدفع النفقات العامة لكل استدعاء للغلاف من نسخ الرموز مرة أخرى إلى Rust زمن الانتقال الخاص به ليكون فوق الثنائي الأصلي.

زمن استجابة p50 وp99 لكل عملية ترميز عبر تنفيذات أداة التقسيم وأحجام الإدخال.

يشغل المحرك النهائي نفس فيتربي عبر نفس مفردات الرموز الـ 250,000، ولا يخصص شيئاً على المسار الساخن، وينتج إخراجاً مطابقاً تماماً للرموز مقارنة بالمرجع. كل خطوة بايت هي الآن تحميل واحد لخط ذاكرة تخزين مؤقت بحجم 64 بايت، واختبار خريطة بت واحد، وجمع عدد صحيح واحد، بانخفاض عن فحص HashMap، ومكالمة مخصص، والعديد من فروع الحالات الخاصة في تنفيذ خط الأساس. انخفضت التعليمات لكل ترميز من 3.66 مليون إلى 1.04 مليون، بانخفاض قدره 3.5 أضعاف. يتطابق ساعة الحائط مع هذه النسبة عند المدخلات القصيرة ويتسع أكثر عند المدخلات الطويلة، حيث تبدأ تخصيصات المرجع لكل رمز في الفائض فوق L2 و L3.

في الممارسة العملية، قلل هذا العمل من استخدام المعالج (CPU) في طبقة المعالجة المسبقة لحزمة الاستدلال لدينا بمقدار 5 إلى 6 أضعاف واختزل زمن انتقال نموذج إعادة الترتيب بمقدار خانتين عشريتين من المللي ثانية.

جاء الجزء الأكبر من تقليل زمن الانتقال من التغييرات الخفيفة التي أزالت العمل المهدر: إسقاط تخصيصات كل ترميز، واستبدال تراي أطفال HashMap بمصفوفة مزدوجة، وتجريد نفقات واجهة برمجة التطبيقات العامة. أدى استخدام خريطة البت لكل عقدة الموجودة كفحص صحة ودعم التراي بصفحات ضخمة بحجم 2 ميغابايت مجتمعين إلى حساب 10-20% علاوة على التبديل الأكبر إلى تراي مصفوفة مزدوجة، اعتماداً على حجم المدخل.

توضح حزم غلاف 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). انتظام الكلمات الفرعية: تحسين نماذج ترجمة الشبكات العصبية مع مرشحين متعددين للكلمات الفرعية. https://arxiv.org/abs/1804.10959

Viterbi, A. J. (1967). حدود الأخطاء للرموز الالتفافية وخوارزمية فك ترميز مثلى مقاربياً. معاملات IEEE في نظرية المعلومات. https://en.wikipedia.org/wiki/Viterbi_algorithm

Aoe, J. (1989). خوارزمية بحث رقمية فعالة باستخدام هيكل مصفوفة مزدوجة. معاملات IEEE في هندسة البرمجيات. https://ieeexplore.ieee.org/document/31365/

Karoonboonyanan, T. تنفيد لتراي المصفوفة المزدوجة. https://linux.thai.net/~thep/datrie/datrie.html

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

الصفحات الضخمة — https://docs.kernel.org/admin-guide/mm/hugetlbpage.html

BibTeX

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

الدافع

خوارزمية فيتربي

التنفيذ المرجعي

ملاحظة حول المعالجة المسبقة

أين يقضي التنفيذ المرجعي وقته

كيف قمنا بالقياس

لماذا تكون SentencePiece و IREE أسرع: شجرة التراي ذات المصفوفة المزدوجة

خط الأساس: نقل المرجع بدون تخصيصات

التحسين 1: تراي المصفوفة المزدوجة بدون تجريدات إضافية

التحسين 2: حزم الصور النقطية والضمنية

التحسين 3: صفحات ضخمة لشجرة البحث

المقارنة النهائية

أفكار ختامية

المراجع

استشهاد