t1ha = फास्ट पॉजिटिव हैश

सभ्य गुणवत्ता के साथ सबसे तेज़ पोर्टेबल 64-बिट हैश फ़ंक्शन के बारे में।

यह लियोनिद यूरीव के मूल लेख का अनुवाद है।

अंतर्निहित गणित के लंबे उद्धरणों को स्वीकार करते हुए, इसे संक्षेप में प्रस्तुत किया जा सकता है:

• उच्च प्रदर्शन सुनिश्चित करते हुए उपरोक्त सभी आवश्यकताओं को पूरा करना काफी कठिन समस्या है, जिसे हल करना हमें एक अच्छा क्रिप्टोग्राफिक हैश फ़ंक्शन प्रदान करेगा। लेकिन हम अभी ऐसा नहीं करने जा रहे हैं।
• बुनियादी गुणवत्ता प्रदान करने के लिए पर्याप्त संख्या में ALU परिचालनों की आवश्यकता होती है। इसे सीधे शब्दों में कहें, तो गुणवत्ता हमेशा गति के साथ समझौता करती है।
• ALU परिचालनों की थोड़ी चौड़ाई से थोड़ी अधिक चौड़ाई के साथ एक उच्च गुणवत्ता वाले परिणाम को प्राप्त करने के लिए मिश्रणों की संख्या में कई गुना वृद्धि और इसलिए बुनियादी ALU संचालन से अधिक की आवश्यकता होती है।
• सामान्य तौर पर, एक तेज़ हैश फ़ंक्शन बनाने में गति, गुणवत्ता और परिणाम बिटनेस के बीच एक भारित समझौता प्राप्त करना शामिल होता है ।

इसलिए, मैं कह सकता हूं कि t1ha गुणवत्ता और गति के बीच एक समझौते की खोज के परिणामस्वरूप दिखाई दिया, एक ही समय में आधुनिक प्रोसेसर की क्षमताओं और पहले से पाए गए तरीकों (अंकगणितीय-तार्किक संयोजनों) के मिश्रण और प्रसार निर्भरता को ध्यान में रखते हुए। हिमस्खलन प्रभाव)।

T1ha का मूल संस्करण हैश टेबल और अन्य संबंधित अनुप्रयोगों के निर्माण के लिए सबसे तेज पोर्टेबल हैश फ़ंक्शन में से एक है। T1ha का मूल संस्करण 64-बिट छोटे-एंडियन आर्किटेक्चर पर केंद्रित है, 64-बिट नमक मूल्य (बीज) लेता है और 64-बिट परिणाम उत्पन्न करता है, जिसमें कुंजी-लंबाई और बीज द्वारा मजबूती शामिल है। यह ध्यान देने योग्य है कि t1ha को जानबूझकर शून्य इनपुट डेटा (शून्य आकार और शून्य बीज की कुंजी) के लिए 0 वापस करने के लिए डिज़ाइन किया गया है।

गुणवत्ता

सभी पहलुओं में एक हैश फ़ंक्शन की गुणवत्ता का मूल्यांकन करना काफी मुश्किल हो सकता है। यह या तो विश्लेषणात्मक रूप से या विभिन्न सांख्यिकीय परीक्षणों को लागू करके किया जा सकता है। दुर्भाग्य से, गुणवत्ता और गति के बीच एक समझौता के साथ हैश कार्यों के मूल्यांकन के लिए विश्लेषणात्मक दृष्टिकोण बहुत प्रभावी नहीं है। इसके अलावा, इस तरह के कार्यों का एक तुलनात्मक विश्लेषणात्मक मूल्यांकन व्यक्तिपरक हो जाता है।

इसके विपरीत, सांख्यिकीय परीक्षण स्पष्ट मात्रात्मक अनुमान प्रदान कर सकते हैं। ऐसे उद्देश्यों के लिए अच्छी तरह से सिद्ध परीक्षण पैकेज हैं, जैसे एसएमएचशर । T1ha के लिए , परिणाम सरल हैं - सभी t1ha विकल्प बिना किसी टिप्पणी के सभी परीक्षण पास करते हैं। दूसरी ओर, किसी को यह नहीं मान लेना चाहिए कि t1ha में उन गुणों की अधिकता है जो लक्ष्य अनुप्रयोग के लिए आवश्यक हैं (हैशिंग टेबल बनाने के लिए)।

T1ha के सभी स्तरों (वेरिएंट) पर टकराव की संख्या जन्मदिन के विरोधाभास से मेल खाती है। इसे सख्ती से तैयार करने के लिए - t1ha में टकराव की संभावना संगत बिटनेस के साथ यादृच्छिक असतत मूल्यों के संयोग की संभावना से मेल खाती है।
सभी उच्च-गुणवत्ता वाले हैश फ़ंक्शन में टकराव की एक समान संभावना देखी जाती है। हालांकि, यह केवल संभावना है, इसलिए प्रत्येक विशिष्ट डेटा सेट के लिए टकरावों की वास्तविक संख्या अलग-अलग हो सकती है।

इस लेख के पहली बार प्रकाशित होने के बाद, यवेस ऑर्टन ने पाया , कि पहला t1ha1() हमेशा सख्त हिमस्खलन से नहीं मिलता है । यह खामी t1ha1() लक्षित अनुप्रयोगों के लिए महत्वहीन है और व्यावहारिक दृष्टिकोण से ध्यान देने योग्य नहीं है। हालांकि, यह नुकसान अगले t1ha2() स्तर / संस्करण में समाप्त हो गया है, जिसे मूल रूप से थोड़ा उच्च गुणवत्ता प्रदान करने की योजना बनाई गई थी। नए प्रोसेसर पर, जो संकलक के वर्तमान संस्करणों का उपयोग करते हैं, t1ha2() की तुलना में औसत एक चक्र तेज है, और बाकी मामलों में यह एक चक्र धीमा हो सकता है। यह ध्यान देने योग्य है कि t1ha2() अतिरिक्त रूप से स्ट्रीम हैशिंग मोड और 128-बिट परिणाम प्रदान करता है।

पाठक निश्चित रूप से t1ha की गुणवत्ता और / या शक्ति के गहन और गहन विश्लेषण की सराहना करेंगे। हालाँकि, लक्ष्य t1ha अनुप्रयोग क्षेत्रों के आधार पर, यह बेमानी लगता है। सीधे शब्दों में कहें तो स्पीड हमारे लिए ज्यादा महत्वपूर्ण थी, यहां तक ​​कि शॉर्ट कीज के लिए भी। इसलिए, बहु-गोल मिश्रण पर विचार नहीं किया गया था। वर्तमान t1ha संस्करण साइकिल पर बचाता है और 64-बिट परिणाम देता है - यह सांख्यिकीय रूप से के अलावा किसी भी तरह से पाया गया समझौता मापने के लिए व्यावहारिक रूप से व्यर्थ है, और इसके परिणाम बस अच्छे हैं।

मानक

" सबसे तेज " होने के दावे के बारे में। यह ध्यान रखना महत्वपूर्ण है कि यह स्पष्ट रूप से संभावना नहीं है कि एक हैश फ़ंक्शन है जो एक ही समय में उपयोगी है और सभी प्लेटफार्मों / आर्किटेक्चर पर सबसे तेज़ है। अलग-अलग प्रोसेसरों में अलग-अलग निर्देशों के सेट उपलब्ध होते हैं और अलग-अलग क्षमता वाले समान निर्देशों को निष्पादित करते हैं। जाहिर है, " सार्वभौमिक रूप से सबसे तेज " फ़ंक्शन सबसे अधिक संभावना नहीं बनाया जा सकता है। हालांकि, यह शब्द "का उपयोग करने के लिए स्वीकार्य है
एक फ़ंक्शन के लिए सबसे तेज़ »जो पोर्टेबल है और एक ही समय में सबसे तेज़, कम से कम सबसे सामान्य प्लेटफ़ॉर्म (x86_64) पर है, जबकि एक सभ्य अनुकूलन कंपाइलर के साथ किसी भी आधुनिक प्रोसेसर पर खोने का कम मौका है।

परियोजना के स्रोत कोड में एक परीक्षण शामिल है जो परिणाम की शुद्धता दोनों की जांच करता है और प्रत्येक कार्यान्वित संस्करण की गति को मापता है। उसी समय, x86 पर, प्रोसेसर (और संकलक) की क्षमताओं के आधार पर, कार्यों के अतिरिक्त वेरिएंट की जांच की जा सकती है, और प्रोसेसर चक्र में माप किए जाते हैं।

इसके अलावा, प्रोजेक्ट वेबसाइट में रीनी अर्बन के SMHasher के एक संशोधित संस्करण के माध्यम से प्रदर्शन माप के परिणामों के साथ तालिकाएं हैं। एक सभी संकलक का उपयोग करके एक विशिष्ट प्रोसेसर पर सभी आंकड़े और / या परिणाम को दोहरा सकते हैं।

यहां आप अपने कुछ निकटतम प्रतियोगियों के साथ t1ha की तुलना कर सकते हैं।

छोटी कुंजियों को हाशिल करना (औसत 1..31 बाइट्स के लिए)।
सही कॉलम "चक्र / हैश" को देखें (छोटा बेहतर है) :

लंबी चाबियाँ (256 Kb) को हिट करना ।
मध्य स्तंभ "मिब / सेकंड" को देखें (बड़ा बेहतर है) :

T1ha के वेरिएंट

T1ha का विकास इस तरह के लक्ष्यों में से पहला हैश तालिकाओं के निर्माण के लिए पर्याप्त रूप से उच्च गुणवत्ता का तेजी से पोर्टेबल कार्य प्राप्त करना था।

तब हम हैश फ़ंक्शन का सबसे तेज़ संस्करण चाहते थे जो तुलनीय गुणवत्ता का परिणाम देगा लेकिन जितना संभव हो सके लक्ष्य प्लेटफ़ॉर्म के लिए अनुकूलित किया गया था। उदाहरण के लिए, मूल t1ha संस्करण छोटे-एंडियन बाइट ऑर्डर के साथ काम करता है, जिसके कारण प्रदर्शन के अपरिहार्य नुकसान के साथ बड़े-एंडियन आर्किटेक्चर के लिए रूपांतरण आवश्यक है। तो एक विशिष्ट लक्ष्य मंच पर अनावश्यक संचालन से छुटकारा क्यों नहीं? इस तरह, कई और विकल्प जोड़े गए:

• 32-बिट प्लेटफार्मों के लिए सरलीकृत संस्करण, दोनों छोटे और बड़े-एंडियन।
• एईएस-एनआई निर्देशों का उपयोग कर वेरिएंट, लेकिन एवीएक्स के बिना।
• एईएस-एनआई और एवीएक्स निर्देशों का उपयोग करते हुए दो वेरिएंट।

बाद में यह स्पष्ट हो गया कि विभिन्न अनुप्रयोगों के लिए डिज़ाइन किए गए अधिक विकल्पों की आवश्यकता होगी, जिसमें विभिन्न बिट चौड़ाई परिणाम, गुणवत्ता और स्थायित्व आवश्यकताएं शामिल हैं। इस तरह की विविधता को उचित व्यवस्थितकरण की आवश्यकता थी। यह नामकरण योजना को बदलकर प्राप्त किया गया था, जिसमें संख्यात्मक प्रत्यय फ़ंक्शन के "स्तर" को इंगित करता है:

• t1ha0() - वर्तमान प्रोसेसर के लिए सबसे तेज़ विकल्प है।
• t1ha1() - t1ha1() का मूल पोर्टेबल 64-बिट संस्करण है।
• t1ha2() - गुणवत्ता के लिए थोड़ी अधिक चिंता के साथ एक पोर्टेबल 64-बिट संस्करण है।
• t1ha3() - फिंगरप्रिंटिंग के लिए एक तेज़ पोर्टेबल 128-बिट संस्करण है।
• आदि

इस योजना में, यह माना जाता है कि t1ha0() एक डिस्पैचर है जो वर्तमान प्रोसेसर के प्लेटफॉर्म और क्षमताओं के आधार पर पुनर्निर्देशन को लागू करता है। इसके अलावा, छोटे-एंडियन और बड़े-एंडियन वेरिएंट के बीच स्पष्ट विकल्प के लिए प्रत्यय "_le" और "_be" का उपयोग पेश किया जा सकता है। इस प्रकार, "t1ha" साइनबोर्ड के तहत अब कई हैश फ़ंक्शंस हैं, और यह परिवार मैं भविष्य में बढ़ेगा, जिसमें रूसी E2K "एल्ब्रस" के लिए अनुकूलित संस्करण भी शामिल है।

कार्यों के वर्तमान सेट और उनके गुणों का एक सामान्य विचार अंतर्निहित परीक्षण आउटपुट ( make check ) को देखकर समझा जा सकता है। यह ध्यान देने योग्य है कि सभी फ़ंक्शन सभी एसएम हैशर परीक्षण पास करते हैं, और एईएस-एनआई वेरिएंट का प्रदर्शन प्रोसेसर मॉडल के आधार पर बहुत भिन्न होता है:

 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 

आप अधिक जानकारी और स्रोत कोड यहां पा सकते हैं।

पढ़ने के लिए धन्यवाद!