XXH3: एक नया हैश गति रिकॉर्ड धारक

बेंचमार्क कार्यक्रम कोर 2 डुओ 3.0 गीगाहर्ट्ज पर SMHasher में किए गए

Habré पर बार-बार गैर-क्रिप्टोग्राफ़िक हैश फ़ंक्शन के बारे में बात की गई, जो क्रिप्टोग्राफ़िक लोगों की तुलना में तेज़ी से परिमाण का एक क्रम है। उनका उपयोग किया जाता है जहां गति महत्वपूर्ण है और धीमी एमडी 5 या एसएचए 1 का उपयोग करने का कोई मतलब नहीं है। उदाहरण के लिए, कुंजी-मूल्य जोड़े के भंडारण के साथ हैश तालिकाओं का निर्माण करना या बड़ी फ़ाइलों को स्थानांतरित करते समय जल्दी से चेकसम की जांच करना।

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


इसके बाद, चार्ट क्लिक करने योग्य हैं

कार्यक्रम के लेखक यान कोलेट लिखते हैं कि एल्गोरिथ्म को बेहतर बनाने का विचार ब्लूम फ़िल्टर के कार्यान्वयन के बारे में आया था, जिसमें छोटे चर-लंबाई इनपुट डेटा के आधार पर 64 pseudorandom बिट्स की तेजी से पीढ़ी की आवश्यकता थी। सिद्धांत रूप में, मानक XXH64 इसे संभाल सकता है, लेकिन छोटे इनपुट डेटा को संसाधित करना इसके विकास में प्राथमिकता नहीं थी। दूसरे शब्दों में, अनुकूलन संभव है। इस अनुकूलन के परिणामस्वरूप, एक नया हैश फ़ंक्शन XXH3 दिखाई दिया, जिसमें कुछ अन्य हैश एल्गोरिदम के विचारों को लागू किया गया है। सबसे दिलचस्प बात, XXH3 सभी मौजूदा xxHash वेरिएंट की तुलना में काफी तेज है, न केवल छोटे इनपुट डेटा पर, बल्कि लगभग सभी उपयोग के मामलों में।

XXH64 XXH64 के मुख्य दोष को समाप्त करता है - 64 बिट्स की हैश सीमा। लेखक का कहना है कि इस कारण से उसे अक्सर कम से कम 128-बिट संस्करण जारी करने के लिए कहा जाता था। तो, XXH3 हैश फ़ंक्शन सैद्धांतिक रूप से 256 बिट तक के हैश उत्पन्न करने में सक्षम है।

XXH3 में, एक आंतरिक लूप जो कि वेक्टराइजेशन द्वारा बेहतर तरीके से संभाला जाता है। इसके कारण, फ़ंक्शन SSE2, AVX2 और NEON सेट पर हार्डवेयर समर्थन का उपयोग करता है। प्रदर्शन संकलक पर निर्भर करता है। अप्रत्याशित रूप से, क्लैंग द्वारा संकलित संस्करण बाकी के मुकाबले बहुत बेहतर है। इयान कोले ने भी सोचा था कि यहाँ हैश फ़ंक्शन का प्रदर्शन मेमोरी बैंडविड्थ से अधिक होगा। ग्राफ़ पर यह संस्करण धराशायी लाइन से मेल खाता है।



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

SSE2 निर्देशों के लिए समर्थन नए हैश फ़ंक्शन को 32-बिट अनुप्रयोगों पर XXH32 को काफी कम करने की अनुमति देता है जो अभी भी वास्तविक दुनिया में आम हैं (उदाहरण के लिए, WASM बायटेकोड)।



छोटे इनपुट डेटा (20-30 बाइट्स) पर, XXH3 हैश फ़ंक्शन बहुत अधिक नहीं है, लेकिन फिर भी Google से सिटीहैश को पार करता है, साथ ही साथ फार्महैश, जो स्पष्ट नेता हुआ करते थे।



निम्नलिखित ग्राफ चर लंबाई (1 से एन तक यादृच्छिक चर) के इनपुट डेटा के साथ सबसे यथार्थवादी परीक्षण के परिणाम दिखाता है।



एक और परीक्षण में देरी को ध्यान में रखा गया है: यहाँ हैशिंग एक संकेत पर शुरू होता है। विचार एक वास्तविक कार्यभार का अनुकरण करना है, जहां हैश फ़ंक्शन लगातार काम नहीं करता है, लेकिन एक निश्चित समय पर अन्य प्रक्रियाओं में कहा जाता है।



लेखक लिखता है कि 64 × 64 => 128 बिट के गुणा के साथ यह परीक्षण व्लादिमीर मकरोव से mumv2 एल्गोरिदम और लियो यूरीव से t1ha2 पसंद करता है।



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



XXH3 को xxHash v0.7.0 पैकेज के भाग के रूप में जारी किया गया था। इसमें "प्रयोगात्मक" चिह्न है, और अनलॉक करने के लिए आपको मैक्रो XXH_STATIC_LINKING_ONLY का उपयोग करना XXH_STATIC_LINKING_ONLY । लेखक बताते हैं कि अब तक हैश फ़ंक्शन का उपयोग केवल परीक्षण पंचांग डेटा पर किया जा सकता है, लेकिन हैश के वास्तविक भंडारण के लिए नहीं। प्रयोगात्मक अवधि और उपयोगकर्ता समीक्षाओं के संग्रह के परिणामों के अनुसार, XXH3 फ़ंक्शन को xxHash के अगले संस्करण में एक स्थिर स्थिति प्राप्त होगी।

---