شركة فيسبوك في تطبيقات جدول التجزئة مفتوح المصدر الأمثل لاستهلاك الذاكرة بكفاءة. يتم استخدام F14 في بنية Facebook الأساسية كبديل لمعظم أنواع جداول التجزئة ويسمح لك بتقليل استهلاك الذاكرة دون التضحية بالأداء. يتفوق F14 بشكل ملحوظ على جداول تجزئة google :: sparse_hash_map ، والتي تعتبر حتى الآن الأكثر كفاءة في استخدام الذاكرة. كود المشروع مكتوب بلغة C ++ ومضمن في المكتبة .
يشير F14 إلى الخوارزميات بنظام دقة التصادم على أساس التجزئة المزدوجة بـ 14 (تخزن إحدى خلايا جدول التجزئة سلسلة من 14 فتحة ، ويتم حساب الفاصل الزمني بين الخلايا باستخدام وظيفة التجزئة الإضافية). لتسريع عمليات تصفية الخلايا ، يستخدم التطبيق تعليمات موجه SSE2 لأنظمة x86_64 و NEON لأنظمة Aarch64 ، والتي تسمح لك بموازاة عمليات اختيار الفتحات مع سلاسل المفاتيح ومفاتيح الفحص داخل السلسلة. تتم معالجة الكتل المكونة من 14 فتحة في وقت واحد ، وهو التوازن الأمثل بين كفاءة استخدام ذاكرة التخزين المؤقت للمعالج وعدد التصادمات.
ميزة F14 هي القدرة على اختيار استراتيجيات تخزين البيانات المختلفة:
- F14NodeMap - يستهلك أقل قدر من الذاكرة للمفاتيح الكبيرة والمتوسطة الحجم. يوفر تخزينًا غير مباشر للعناصر مع استدعاء في كل مرة يتم فيها إدراج وظيفة malloc ؛
- F14ValueMap - يوفر الحد الأدنى من استهلاك الذاكرة للمفاتيح الصغيرة. يتم تخزين العناصر في الخلايا نفسها (مضمنة). بالنسبة للمفاتيح المتوسطة والكبيرة ، يؤدي هذا الأسلوب إلى زيادة ملحوظة في الذاكرة ؛
- F14VectorMap أسرع للجداول الكبيرة والمفاتيح المعقدة ، ولكنه أبطأ للمفاتيح البسيطة والجداول الصغيرة. يتم تجميع العناصر في مصفوفة قريبة ويتم معالجتها بواسطة مؤشر فهرس 32 بت ؛
- F14FastMap هي استراتيجية مشتركة. إذا كان المفتاح أقل من 24 بايت ، فسيتم تحديد F14ValueMap ، وإذا كان أكثر من ذلك ، فسيتم تحديد F14VectorMap.
المصدر: opennet.ru