t1ha = تجزئة إيجابية سريعة

تقريبا عن أسرع وظيفة تجزئة 64 بت مع جودة لائقة.

هذه ترجمة للمقال الأصلي ليونيد يوريف .

عند حذف اقتباسات طويلة من الرياضيات الأساسية ، يمكن تلخيصها:

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

لذلك ، أستطيع أن أقول إن t1ha ظهر نتيجة للبحث عن حل وسط بين الجودة والسرعة ، مع مراعاة قدرات المعالجات الحديثة والأساليب الموجودة بالفعل (المجموعات الحسابية المنطقية) لمزج التبعيات ونشرها ( تأثير الانهيار).

النسخة الأساسية من t1ha هي واحدة من أسرع وظائف التجزئة المحمولة لبناء جداول التجزئة وغيرها من التطبيقات ذات الصلة. يركز الإصدار الأساسي من t1ha على أبنية endian ذات 64 بت ، ويأخذ قيمة ملح 64 بت (بذرة) وينتج نتيجة 64 بت ، والتي تتضمن تقوية بطول المفتاح والبذور. تجدر الإشارة إلى أن t1ha مصمم بشكل متعمد لإرجاع 0 لبيانات الإدخال الصفرية (مفتاح بحجم الصفر وبذور صفرية).

الجودة

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

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

يتوافق عدد الاصطدامات على جميع المستويات (المتغيرات) من t1ha مع مفارقة أعياد الميلاد . لصياغتها بدقة - يتوافق احتمال الاصطدام في t1ha مع احتمال تزامن القيم المنفصلة العشوائية مع الشاهد المقابل.
ولوحظ وجود احتمال مماثل للتصادم في جميع وظائف التجزئة عالية الجودة. ومع ذلك ، هذا هو الاحتمال الوحيد ، لذلك يمكن أن يختلف العدد الفعلي للتصادمات لكل مجموعة بيانات محددة.

بعد نشر هذه المقالة لأول مرة ، اكتشف إيف أورتن ، أن t1ha1() الأول لا يفي دائمًا بمعايير الانهيار الصارم . هذا العيب غير مهم للتطبيقات المستهدفة من t1ha1() وغير ملحوظ من الناحية العملية. ومع ذلك ، يتم التخلص من هذا العيب في المستوى / المتغير t1ha2() التالي ، والذي كان من المقرر أصلاً توفير جودة أعلى قليلاً. في المعالجات الجديدة ، التي تستخدم الإصدارات الحالية من المجمعين ، يكون t1ha2() في المتوسط ​​دورة واحدة أسرع من t1ha1() ، وفي بقية الحالات يمكن أن يكون دورة واحدة أبطأ. تجدر الإشارة إلى أن t1ha2() بالإضافة إلى ذلك يوفر وضع تجزئة الدفق ونتائج 128 بت.

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

المعايير

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

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

بالإضافة إلى ذلك ، يحتوي موقع المشروع على جداول تحتوي على نتائج لقياسات الأداء من خلال نسخة معدلة من SMHasher من Reini Urban . يمكن للمرء التحقق من جميع الأرقام و / أو الحصول على نتائج على معالج معين باستخدام مترجم معين.

هنا يمكنك مقارنة t1ha ببعض أقرب منافسيها.

تجزئة المفاتيح القصيرة (متوسط ​​1..31 بايت).
انظر إلى العمود الأيمن "Cycles / Hash" (الأصغر هو الأفضل) :

ضرب المفاتيح الطويلة (256 كيلو بايت).
انظر إلى العمود الأوسط "MiB / Second" (الأكبر هو الأفضل) :

المتغيرات من t1ha

تطوير t1ha كان أول هذه الأهداف هو الحصول على وظيفة محمولة سريعة ذات جودة عالية بما يكفي لبناء طاولات التجزئة.

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

• إصدار مبسط لمنصات 32 بت ، كلاهما صغير وكبير endian.
• البديل باستخدام تعليمات AES-NI ، ولكن بدون AVX.
• خياران باستخدام إرشادات AES-NI و AVX.

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

• t1ha0() - هو الخيار الأسرع للمعالج الحالي.
• t1ha1() - هو الإصدار 64 بت المحمول الأساسي من t1ha.
• t1ha2() - هو إصدار 64 بت محمول مع اهتمام أكثر قليلاً بالجودة.
• t1ha3() - هو نسخة محمولة 128 بت سريعة لبصمات الأصابع.
• الخ

في هذا المخطط ، يُفترض أن t1ha0() هو مرسل يقوم بإعادة التوجيه وفقًا للنظام الأساسي وقدرات المعالج الحالي. بالإضافة إلى ذلك ، يمكن تقديم استخدام اللواحق "_le" و "_be" لاختيار صريح بين المتغيرات endian الصغيرة والكبيرة endian. وبالتالي ، هناك العديد من وظائف التجزئة ، تحت لوحة "t1ha" الآن ، وسوف تنمو هذه العائلة في المستقبل ، بما في ذلك إصدار مُحسّن لـ E2K الروسية "Elbrus".

يمكن فهم فكرة عامة عن المجموعة الحالية من الوظائف وخصائصها من خلال النظر إلى مخرجات الاختبار المضمنة ( make check ). تجدر الإشارة إلى أن جميع الوظائف تجتاز جميع اختبارات SM Hasher ، وأن أداء متغيرات AES-NI يختلف اختلافًا كبيرًا وفقًا لطراز المعالج:

 Intel(R) Core(TM) i7-6700K CPU @ 3.00GHz Build by GNU C/C++ compiler 8.2 [...] - use RDPMC_40000001 as clock source - measure granularity and overhead: 53 cycles, 0.0188679 iteration/cycle Bench for tiny keys (7 bytes): t1ha0 : 13.14 cycle/hash, 1.877 cycle/byte, 1.598 Gb/s @3GHz t1ha1_64le : 15.14 cycle/hash, 2.163 cycle/byte, 1.387 Gb/s @3GHz t1ha2_atonce : 15.50 cycle/hash, 2.163 cycle/byte, 1.387 Gb/s @3GHz t1ha1_64be : 16.78 cycle/hash, 2.397 cycle/byte, 1.251 Gb/s @3GHz xxhash32 : 17.17 cycle/hash, 2.453 cycle/byte, 1.223 Gb/s @3GHz StadtX : 17.59 cycle/hash, 2.513 cycle/byte, 1.194 Gb/s @3GHz t1ha0_32le : 18.28 cycle/hash, 2.612 cycle/byte, 1.149 Gb/s @3GHz t1ha0_32be : 20.24 cycle/hash, 2.892 cycle/byte, 1.037 Gb/s @3GHz xxhash64 : 22.17 cycle/hash, 3.167 cycle/byte, 0.947 Gb/s @3GHz t1ha2_atonce128* : 29.93 cycle/hash, 4.277 cycle/byte, 0.701 Gb/s @3GHz t1ha2_stream* : 79.81 cycle/hash, 11.402 cycle/byte, 0.263 Gb/s @3GHz HighwayHash64_avx2 : 83.75 cycle/hash, 11.964 cycle/byte, 0.251 Gb/s @3GHz HighwayHash64_sse41 : 85.25 cycle/hash, 12.179 cycle/byte, 0.246 Gb/s @3GHz t1ha2_stream128* : 99.06 cycle/hash, 14.152 cycle/byte, 0.212 Gb/s @3GHz HighwayHash64_portable: 480.75 cycle/hash, 68.679 cycle/byte, 0.044 Gb/s @3GHz HighwayHash64_pure_c : 652.58 cycle/hash, 93.226 cycle/byte, 0.032 Gb/s @3GHz Bench for large keys (16384 bytes): t1ha0 : 1185.00 cycle/hash, 0.072 cycle/byte, 41.478 Gb/s @3GHz t1ha2_atonce : 3436.00 cycle/hash, 0.210 cycle/byte, 14.305 Gb/s @3GHz t1ha2_atonce128* : 3440.00 cycle/hash, 0.210 cycle/byte, 14.288 Gb/s @3GHz t1ha1_64le : 3449.00 cycle/hash, 0.211 cycle/byte, 14.251 Gb/s @3GHz t1ha2_stream* : 3479.00 cycle/hash, 0.212 cycle/byte, 14.128 Gb/s @3GHz t1ha2_stream128* : 3508.00 cycle/hash, 0.214 cycle/byte, 14.011 Gb/s @3GHz StadtX : 3550.00 cycle/hash, 0.217 cycle/byte, 13.846 Gb/s @3GHz xxhash64 : 4121.00 cycle/hash, 0.252 cycle/byte, 11.927 Gb/s @3GHz t1ha1_64be : 4567.00 cycle/hash, 0.279 cycle/byte, 10.762 Gb/s @3GHz HighwayHash64_avx2 : 4580.00 cycle/hash, 0.280 cycle/byte, 10.732 Gb/s @3GHz HighwayHash64_sse41 : 6412.00 cycle/hash, 0.391 cycle/byte, 7.666 Gb/s @3GHz t1ha0_32le : 7191.00 cycle/hash, 0.439 cycle/byte, 6.835 Gb/s @3GHz t1ha0_32be : 7928.00 cycle/hash, 0.484 cycle/byte, 6.200 Gb/s @3GHz xxhash32 : 8197.00 cycle/hash, 0.500 cycle/byte, 5.996 Gb/s @3GHz HighwayHash64_portable: 41895.27 cycle/hash, 2.557 cycle/byte, 1.173 Gb/s @3GHz HighwayHash64_pure_c : 53296.11 cycle/hash, 3.253 cycle/byte, 0.922 Gb/s @3GHz 

يمكنك العثور على مزيد من المعلومات والكود المصدري هنا .

شكرا للقراءة!