आज हम ओपन सोर् कोड साा कर रहे हैं जो संख्याओं की सरणियों को C++ std::sort की तुलना में लगभग दस गुना तेज़ी से सॉर्ट कर सकता है, और अत्याधुनिक आर्किटेक्चर-विशिष्ट एल्गोरिदम से बेहतर प्रदर्शन करता है, जबकि सभी आधुनिक CPU आर्किटेक्चर में पोर्टेबल है। नीचे हम चर्चा करते हैं कि हमने यह कैसे हासिल किया।

पहले, कुछ पृष्ठभूमि। हाल ही में कॉलमनर डेटाबेस की ओर एक प्रवृत्ति है जो किसी विशेष कॉलम के सभी मानों को लगातार संग्रहीत करती है, बजाय एक रिकॉर्ड या "पंक्ति" के सभी फ़ील्ड को अगले रिकॉर्ड से पहले संग्रहीत करने के। यह फ़िल्टर या सॉर्ट करने में तेज़ हो सकता है, जो SQL क्वेरी के लिए प्रमुख बिल्डिंग ब्लॉक हैं; इसलिए हम इस डेटा लेआउट पर ध्यान केंद्रित करते हैं।

चूंकि सॉर्टिंग का भारी अध्ययन किया गया है, हम 10 गुना गति वृद्धि कैसे पा सकते हैं? इसका उत्तर SIMD/वेक्टर निर्देशों में है। ये एक ही निर्देश में कई स्वतंत्र तत्वों पर संचालन करते हैं—उदाहरण के लिए, AVX-512 निर्देश सेट का उपयोग करते समय एक साथ 16 float32 पर संचालन, या Arm NEON पर चार।

यदि आप पहले से ही SIMD से परिचित हैं, तो आपने सुना होगा कि इसका उपयोग सुपर कंप्यूटर, मशीन लर्निंग अनुप्रयोगों के लिए रैखिक बीजगणित, वीडियो प्रोसेसिंग, या JPEG XL जैसे छवि कोडेक में किया जाता है। लेकिन अगर SIMD संचालन में केवल स्वतंत्र तत्व शामिल हैं, तो हम उन्हें कैसे सॉर्ट कर सकते हैं, जिसमें आसन्न सरणी तत्वों को पुनर्व्यवस्थित करना शामिल है? कल्पना करें कि हमारे पास सॉर्ट करने का कुछ विशेष तरीका है, उदाहरण के लिए 256 तत्व सरणियाँ। फिर, बड़ी सरणी को सॉर्ट करने के लिए क्विकसॉर्ट एल्गोरिदम में इसे दो उप-सरणियों में विभाजित करना शामिल है: वे जो "पिवट" मान (आदर्श रूप से माध्यिका) से कम हैं, और अन्य सभी; फिर पुनरावृत्ति करना जब तक कि एक उप-सरणी अधिकतम 256 तत्वों की न हो, और इन्हें सॉर्ट करने के लिए हमारी विशेष विि का उपयोग करना। विाजन अधिकांश CPU समय का हिस्सा है, इसलिए यदि हम SIMD का उपयोग करके इसे गति दे सकते हैं, तो हमारे पास एक तेज़ सॉर्ट है।

सौभाग्य से, आधुनिक निर्देश सेट (Arm SVE, RISC-V V, x86 AVX-512) में विभाजन के लिए उपयुक्त एक विेष निर्देश शामिल है। हाँ/नहीं मानों के एक अलग इनपुट को देखते हुए (क्या कोई तत्व पिवट से कम है), यह "कंप्रेस-स्टोर" निर्देश केवल उन तत्वों को लगातार मेमोरी में संग्रहीत करता है जिनका संबंधित इनपुट "हाँ" है। फिर हम हाँ/नहीं मानों को तार्किक रूप से नकार सकते हैं और तत्वों को अन्य विभाजन में लिने के लिए निर्देश को फिर से लागू कर सकते हैं। यह रणनीति AVX-512-विशिष्ट क्विकसॉर्ट में उपयोग की गई है। लेकिन अन्य निर्देश सेट जैसे AVX2 के बारे में क्या जिनमें कंप्रेस-स्टोर नहीं है? पिछले काम ने दिखाया है कि परम्यूट निर्देशों का उपयोग करके इस निर्देश का अनुकरण कैसे किया जाए। हम इन तकनीकों पर निर्माण करते हैं ताकि पहला वेक्टराइज़्ड क्विकसॉर्ट प्राप्त किया जा सके जो तीन आर्किटेक्चर में छह निर्देश सेटों के लिए पोर्ेबल है, और वास्तव में पूर्व आर्किटेक्चर-विशिष्ट सॉर्ट से बेहतर प्रदर्शन करता है।

हमारा कार्यान्वयन Highway के पोर्टेबल SIMD फ़ंक्न का उपयोग करता है, इसलिए हमें प्रत्येक प्लेटफ़ॉर्म के लिए लगभग 3,000 पंक्तियों के C++ को फिर से लागू नहीं करना पड़ता है। Highway उपलब्ध होने पर कंप्रेस-स्टोर का उपयोग करता है और अन्यथा समकक्ष परम्यूट निर्देशों का। पिछले अत्याधुनिक—जो 32-बिट पूर्णांकों के लिए भी वििष्ट था—के विपरीत, हम 16-128 बिट इनपुट की पूरी श्रृंखला का समर्थन करते हैं। हमारे एकल पोर्टेबल कार्यान्वयन के बावजूद, हम AVX2, AVX-512 (Intel Skylake) और Arm NEON (Apple M1) दोनों पर रिकॉर्ड-सेटिंग गति तक पहुँचते हैं। दस लाख 32/64/128-बिट संख्याओं के लिए, Apple M1 पर चलने वाला हमारा कोड 499/471/466 MB/s की दर से सॉर्ट किया गया आउटपुट उत्पन्न कर सकता है। AVX-512 के साथ 3 GHz Skylake पर, गति 1123/1119/1120 MB/s है। दिलचस्प बात यह है कि AVX-512, AVX2 से 1.4-1.6 गुना तेज़ है—शून्य अतिरिक्त प्रयास के लिए एक सार्थक गति वृद्धि (Highway जाँचता है कि CPU पर कौन से निर्देश उपलब्ध हैं और सर्वोत्तम उपलब्ध का उपयोग करता है)। AVX2 पर चलने पर, हम 798 MB/s मापते हैं, जबकि AVX2 के लिए अनुकूलित पूर्व अत्याधुनिक केवल 699 MB/s प्रबंधित करता है। तुलना में, मानक पुस्तकालय उसी CPU पर 58/128/117 MB/s तक पहुँचता है, इसलिए हमने संख्याओं के प्रकार के आधार पर 9-19 गुना गति वृद्धि हासिल की है।

पहले, सॉर्टिंग को महंगा माना जाता था। हम यह देखने में रुचि रखते हैं कि एकल CPU कोर पर 1 GB/s पर सॉर् करने में सक्षम होने से कौन से नए अनुप्रयोग और क्षमताएँ अनलॉक होंगी। Apache2-लाइसेंस प्राप्त स्रोत ...