تمكنت GitHub من تشغيل عملية طيّ حالة الأحرف، أو Case Folding، بسرعة تتجاوز 45 غيغابايت في الثانية على نواة واحدة من خلال إعادة تصميم الحلقة البرمجية بحيث لا تتوقف عند أول بايت غير ASCII، بل تمسح المخزن المؤقت كاملاً دون فروع تحكم تعتمد على البيانات. وتستخدم الشركة هذه العملية في محرك بحث الشيفرة Blackbird، الذي يفهرس أكثر من 180 مليون مستودع وما يزيد على 480 تيرابايت من الشيفرة المصدرية.
عرض Alexander Neubeck وGreg Orzell تفاصيل هذا التصميم في تدوينة منشورة على مدونة GitHub في 31 يوليو 2026. وأعلنت التدوينة أيضاً إتاحة النتيجة في مكتبة Rust مفتوحة المصدر تحمل اسم casefold.
طيّ الحالة ليس مجرد تحويل إلى أحرف صغيرة
تحتاج محركات البحث والأدوات التي تطابق النصوص إلى تمثيل قياسي يجعل السلاسل التي تختلف في حالة الأحرف متساوية عند المقارنة. ويظهر ذلك في البحث، والتعابير النمطية غير الحساسة لحالة الأحرف، وأسماء المستخدمين وأسماء المضيفين.
لكن تحويل النص إلى أحرف صغيرة لا يؤدي الغرض نفسه. فالتحويل إلى أحرف صغيرة قد يعتمد على اللغة والسياق، مثل اختلاف شكل حرف سيغما اليوناني في نهاية الكلمة وداخلها، أو اختلاف قواعد الحرف I في التركية. أما طيّ الحالة فمصمم للمقارنة، ولذلك يكون مستقلاً عن اللغة والسياق. كما تختلف النتيجة في حالات مثل الحرف الألماني ß، والحرف التركي İ، وسيغما اليونانية النهائية.
تنفذ المكتبة طيّاً بسيطاً واحداً إلى واحد، وفق الحالتين C وS في ملف CaseFolding.txt التابع لقاعدة بيانات محارف Unicode. ولا تنفذ عمليات الطيّ متعددة المحارف، مثل تحويل ß إلى ss، ولا عمليات الطيّ الخاصة باللغة التركية.
إزالة التحسين الذي كان يبطئ الحلقة
بما أن الشيفرة المصدرية تتكون في معظمها من محارف ASCII، فإن المسار الأسرع يركز على تحويل الأحرف اللاتينية الكبيرة من A إلى Z إلى أحرف صغيرة. كان التصميم البديهي يتوقف فور العثور على بايت غير ASCII، ثم ينقل بقية النص إلى مسار Unicode. لكن الاختبارات على معالج Apple M4 أظهرت أن هذا الأسلوب لا يتجاوز نحو 3 غيغابايت في الثانية.
يرجع السبب الرئيسي إلى فروع التحكم داخل الحلقة. وبدلاً من اختبار كل بايت والتوقف مبكراً، تجمع الخوارزمية البت الأعلى لجميع البايتات في متغير واحد، ثم تختبر النتيجة بعد انتهاء المسح. أما اختبار وقوع البايت ضمن نطاق الأحرف الكبيرة فيُنفذ حسابياً عبر طرح الحرف A مع الالتفاف ومقارنة الناتج بالعدد 26. وبعد ذلك يُستخدم قناع حسابي لتعيين البت الخامس في البايت، وهو ما يحوّل الحرف الكبير إلى صغير من دون فرع أو كتابة شرطية.
تسمح هذه البنية للمترجم LLVM بإنشاء تعليمات متجهة تعالج 16 بايت في كل مرة باستخدام NEON على Apple M4. والنتيجة تتجاوز 45 غيغابايت في الثانية، أي تقترب من حد عرض نطاق الذاكرة. وتشير قياسات GitHub إلى أن إزالة الخروج المبكر هي العامل الذي أتاح المتجهة؛ فالإبقاء على الخروج المبني على البيانات يمنع إنشاء تعليمات متجهة حتى لو أصبحت بقية الحلقة خالية من الفروع.
لماذا لا يكون المسح المدمج الأسرع دائماً؟
اختبرت GitHub حلاً وسطاً يعتمد على فحص ASCII في كتل، ثم تحويل المقدمة ASCII. ويقرأ هذا الأسلوب البيانات مرتين، لكنه حقق نحو 23 غيغابايت في الثانية، أي أسرع بكثير من الحلقة الساذجة، مع الحفاظ على القدرة على التوقف عند أول كتلة غير ASCII.
أما دمج الفحص والتحويل في حلقة واحدة تعمل على كتل من 16 بايت، فكان أبطأ، إذ بلغ نحو 8.7 غيغابايت في الثانية مقابل 23 غيغابايت في الثانية للحل ذي المرورين. ووفق التدوينة، يؤدي فرع الخروج المبكر بعد كل كتلة إلى منع المترجم من فك الحلقة أو إخفاء زمن الانتظار بين القراءة والاختبار والتحويل والكتابة. لذلك تفوقت حلقتان نظيفتان وقابلتان للمتجهة على حلقة واحدة تلمس البيانات مرات أقل لكنها تحتوي على فرع يعتمد على المحتوى.
تقليل التخصيصات في الذاكرة
تأخذ الدالة simple_fold سلسلة String بالملكية، ما يسمح لها بتعديل مخزنها المؤقت وإعادته مباشرة. فإذا كان النص ASCII بالكامل، تُعاد الذاكرة نفسها بعد تحويل الأحرف في مكانها، من دون مخزن ثانٍ أو نسخ إضافي.
وعند وجود محارف غير ASCII، لا تُنشئ الخوارزمية مخزناً جديداً إلا عندما تصل إلى محرف يتغير طوله أو محتواه. وتوضح التدوينة أن معظم عمليات الطي تحافظ على طول UTF-8 أو تقلله، لكن المحرفين U+023A وU+023E يمكن أن يزيد طول كل منهما من بايتين إلى ثلاثة. ولهذا تحجز الخوارزمية مرة واحدة سعة قصوى تعادل 1.5 مرة تقريباً طول الإدخال، بدلاً من توسيع المخزن تدريجياً وإعادة نسخ البيانات.
كما تنقل مجموعات البايتات التي لم تتغير باستخدام copy_nonoverlapping، بدلاً من نسخها بايتاً بعد بايت. وتبقي بعض النصوص غير اللاتينية، مثل CJK وHangul وKana والعربية والعبرية والرموز، في تخصيصها الأصلي عندما لا تحتوي على محارف تحتاج إلى طي.
معالجة Unicode في فضاء البايت
تحتوي Unicode 16.0 على 1484 عملية طيّ بسيطة، لكن GitHub ضغطت جدولها إلى 1776 بايتاً عبر استغلال تجمع المحارف القابلة للطي في صفحات من 64 نقطة ترميز. ولاختبار ما إذا كان محرف ما يحتاج إلى طي، تستخدم الخوارزمية خريطة بتات؛ فإذا كانت البت المقابلة غير مفعلة، يُرفض المحرف فوراً من دون فك UTF-8 أو البحث في جدول تجزئة.
داخل الصفحات التي تحتوي على عمليات طي، تخزن الخوارزمية نطاقات متجاورة بدلاً من سجل منفصل لكل نقطة ترميز. وتوصف النطاقات ببداية ونهاية وخطوة وفارق، ما يقلص نحو 1484 عملية إلى 238 نطاقاً موزعة على 59 صفحة. كما تستخدم مقارنة متوازية على ثمانية مفاتيح في وقت واحد لتحديد النطاق المناسب.
بعد العثور على النطاق، تُحسب المحارف المطوية عبر جمع بايتي على مستوى UTF-8 مع ثابت خاص بالنطاق، بدلاً من فك المحرف إلى نقطة ترميز ثم إعادة ترميزه. ويسمح ذلك بالتعامل مع تغيّر الطول، مثل تحويل U+212A، رمز الكلفن، من ثلاثة بايتات إلى الحرف k ذي البايت الواحد، أو تحويل U+023A إلى محرف يبلغ ثلاثة بايتات.
يفترض هذا الأسلوب أن الإدخال UTF-8 صحيح ومختصر، وهو افتراض تضمنه أنواع String وstr في Rust. أما البيانات الخام القادمة من مصادر أخرى، فيجب التحقق من صحتها أو تطبيعها قبل استخدام هذه الحسابات.
النتيجة وحدود القياسات
في حالة ASCII الشائعة، تتجاوز سرعة المكتبة 45 غيغابايت في الثانية، وهي أسرع بأكثر من 50% من الدالة غير المكافئة تماماً str::to_lowercase، وفق القياسات الواردة في التدوينة. وفي أسوأ حالات الإدخال التي تحتاج معظم محارفها إلى الطي، كانت الحلول المعتمدة على الحسابات في فضاء البايت أسرع تقريباً بمرتين من مسار فك UTF-8 وإعادة ترميزه المحسن.
تؤكد GitHub أن الأرقام ونسب المقارنة إرشادية وليست قابلة للنقل حرفياً بين المعالجات، لأنها تعتمد على المتجهة التلقائية، وSWAR، وحسابات البايتات بترتيب little-endian، إضافة إلى عرض نطاق الذاكرة وبنية المعالج. وتلخص التدوينة الفكرة في مبدأين: مسح المسار الشائع كاملاً دون فروع، وتنفيذ المسار النادر الخاص بـUnicode في فضاء البايت بدلاً من فك المحارف وإعادة ترميزها.