गो बिटमैप इंडेक्स: वाइल्ड सर्च

उद्घाटन टिप्पणी

मैंने यह रिपोर्ट मॉस्को में गोफरकोन रूस 2019 सम्मेलन में और रूसी में निज़नी नोवगोरोड में बैठक में की। यह बिटमैप इंडेक्स के बारे में है - बी-ट्री की तुलना में कम आम है, लेकिन कम दिलचस्प नहीं है। मैं अंग्रेजी में सम्मेलन में भाषण की रिकॉर्डिंग और रूसी में पाठ प्रतिलेख साझा करता हूं।

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

मुझे वास्तव में उम्मीद है कि मेरा काम आपके लिए उपयोगी और दिलचस्प होगा। चलो चलते हैं!

परिचय

http://bit.ly/bitmapindexes
https://github.com/mkevac/gopherconrussia2019

सभी को नमस्कार! शाम के छह बज रहे हैं, हम सब सुपर थके हुए हैं। डेटाबेस इंडेक्स के उबाऊ सिद्धांत के बारे में बात करने के लिए बहुत अच्छा समय है, है ना? चिंता न करें, मेरे पास स्रोत कोड की कुछ पंक्तियाँ यहाँ और वहाँ होंगी। :-)

अगर मजाक के बिना, तो रिपोर्ट जानकारी से भरी है, और हमारे पास ज्यादा समय नहीं है। तो चलिए शुरू करते हैं।

आज मैं निम्नलिखित के बारे में बात करूंगा:

• अनुक्रमित क्या हैं;
  
• बिटमैप इंडेक्स क्या है;
  
• इसका उपयोग कहां किया गया है और कहां इसका उपयोग नहीं किया गया है और क्यों;
  
• गो पर सरल कार्यान्वयन और संकलक के साथ थोड़ा संघर्ष;
  
• गो-असेंबलर में थोड़ा कम सरल, लेकिन बहुत अधिक उत्पादक कार्यान्वयन;
  
• बिटमैप इंडेक्स की "समस्याएं";
  
• मौजूदा कार्यान्वयन।
  

तो अनुक्रमित क्या हैं?

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

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



पहला तरीका खोज क्षेत्र को छोटे भागों में विभाजित करते हुए खोज क्षेत्र को कम करना है।

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



दूसरा दृष्टिकोण तुरंत वांछित तत्व या तत्वों के समूह का चयन करना है। हम इसे हैश मैप्स में या रिवर्स इंडेक्स में करते हैं। हैश मैप का उपयोग करना पिछले उदाहरण के समान है, केवल आपकी अलमारी में बक्से के साथ बॉक्स के बजाय अंतिम आइटम के साथ बहुत से छोटे बॉक्स हैं।



तीसरा तरीका खोज की आवश्यकता से छुटकारा पाना है। हम ब्लूम फिल्टर या कोयल फिल्टर का उपयोग करते हैं। पूर्व खोज करने की आवश्यकता को समाप्त करते हुए, तुरंत एक उत्तर प्रदान करता है।



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

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

आज मैं इनमें से सबसे कम ज्ञात दृष्टिकोण के बारे में बात करूंगा - बिटमैप इंडेक्स के बारे में।

मैं कौन हूँ इस बारे में बात करने के लिए?

मैं एक टीम लीडर के रूप में काम करता हूं (शायद आप हमारे अन्य उत्पाद, भौंरा को बेहतर जानते हैं)। हमारे पास पहले से ही दुनिया भर में 400 मिलियन से अधिक उपयोगकर्ता हैं और कई विशेषताएं हैं जो उनके लिए सबसे अच्छी जोड़ी का चयन करने में लगे हुए हैं। हम कस्टम सेवाओं का उपयोग करके ऐसा करते हैं जो बिटमैप इंडेक्स का भी उपयोग करते हैं।

तो बिटमैप इंडेक्स क्या है?

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

हमें बताया गया है कि बिटमैप इंडेक्स उन मामलों के लिए सबसे उपयुक्त और बहुत उत्पादक होते हैं जहां एक खोज होती है जो कई स्तंभों में प्रश्नों को जोड़ती है जिनकी थोड़ी कार्डिनैलिटी होती है (कल्पना करें कि "आंखों का रंग" या "वैवाहिक स्थिति" जैसे "शहर के केंद्र से दूरी" )। लेकिन बाद में मैं दिखाऊंगा कि वे उच्च हृदयता वाले स्तंभों के मामले में पूरी तरह से काम करते हैं।

बिटमैप इंडेक्स के सबसे सरल उदाहरण पर विचार करें।

कल्पना कीजिए कि हमारे पास मॉस्को रेस्तरां की सूची है जैसे कि द्विआधारी गुण इन जैसे हैं:

• मेट्रो के पास (मेट्रो के पास);
  
• एक निजी पार्किंग है (निजी पार्किंग है);
  
• एक बरामदा है (छत है);
  
• आप एक मेज आरक्षित कर सकते हैं (आरक्षण स्वीकार करता है);
  
• शाकाहारियों के लिए उपयुक्त (शाकाहारी के अनुकूल);
  
• महंगा (महंगा)।
  

आइए प्रत्येक रेस्तरां को 0 से शुरू होने वाले सीरियल नंबर दें और 6 बिटमैप (प्रत्येक विशेषता के लिए एक) के लिए मेमोरी आवंटित करें। फिर हम इन बिटमैप को भरते हैं, इस पर निर्भर करता है कि रेस्तरां के पास यह संपत्ति है या नहीं। यदि रेस्तरां 4 में एक बरामदा है, तो बिटमैप में बिट नंबर 4 "एक बरामदा है" को 1 पर सेट किया जाएगा (यदि कोई बरामदा नहीं है, तो 0 पर)।

अब हमारे पास सबसे सरल बिटमैप इंडेक्स संभव है, और हम इसका उपयोग प्रश्नों का उत्तर देने के लिए कर सकते हैं जैसे:

• "मुझे शाकाहारियों के लिए उपयुक्त रेस्तरां दिखाएं";
  
• "मुझे एक बरामदे के साथ सस्ते रेस्तरां दिखाएं जहाँ आप एक मेज आरक्षित कर सकते हैं।"
  

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


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


बहुत सिद्धांत है, लेकिन चिंता मत करो, हम बहुत जल्द कोड देखेंगे।

बिटमैप इंडेक्स कहाँ उपयोग किए जाते हैं?

यदि आप "google" बिटमैप इंडेक्स बनाते हैं, तो 90% उत्तर किसी तरह Oracle DB से संबंधित होंगे। लेकिन बाकी के डीबीएमएस भी शायद इस तरह की शांत चीज का समर्थन करते हैं, है ना? वास्तव में नहीं।

मुख्य संदिग्धों की सूची के माध्यम से चलते हैं।

MySQL अभी तक बिटमैप इंडेक्स का समर्थन नहीं करता है, लेकिन इस विकल्प ( https://dev.mysql.com/worklog/task/?id=1524 ) को जोड़ने के प्रस्ताव के साथ प्रस्ताव है।

PostgreSQL बिटमैप इंडेक्स का समर्थन नहीं करता है, लेकिन कई अन्य इंडेक्स में खोज परिणामों को संयोजित करने के लिए सरल बिटमैप और बिट ऑपरेशन का उपयोग करता है।

टारनटूल में बिटसेट इंडेक्स है, यह उन पर एक सरल खोज का समर्थन करता है।

Redis में सरल बिट फ़ील्ड हैं (https://redis.io/commands/bitfield ) उनके माध्यम से खोज करने की क्षमता के बिना।

MongoDB अभी तक बिटमैप इंडेक्स का समर्थन नहीं करता है, लेकिन इस विकल्प को जोड़ने के प्रस्ताव के साथ प्रस्ताव भी है https://jira.mongodb.org/browse/SERVER-1723

इलास्टिक्स खोज बिटमैप्स का उपयोग करता है (https://www.elastic.co/blog/frame-of-reference-and-roaring-bitmaps )।

• लेकिन हमारे घर में एक नया पड़ोसी दिखाई दिया: पिलोसा। यह एक नया गैर-संबंधपरक डेटाबेस है जिसे गो में लिखा गया है। इसमें केवल बिटमैप इंडेक्स होते हैं और उन पर सब कुछ आधारित होता है। हम उसके बारे में थोड़ी देर बाद बात करेंगे।
  

कार्यान्वयन जाओ

लेकिन बिटमैप इंडेक्स का उपयोग शायद ही कभी क्यों किया जाता है? इस प्रश्न का उत्तर देने से पहले, मैं आपको गो पर एक बहुत ही सरल बिटमैप सूचकांक के कार्यान्वयन का प्रदर्शन करना चाहूंगा।

बिटमैप्स अनिवार्य रूप से केवल डेटा के टुकड़े हैं। गो में, इसके लिए बाइट स्लाइस का उपयोग करें।

हमारे पास प्रति रेस्तरां विशेषता में एक बिटमैप है, और बिटमैप में प्रत्येक बिट इंगित करता है कि किसी विशेष रेस्तरां में यह संपत्ति है या नहीं।

हमें दो सहायक कार्यों की आवश्यकता होगी। यादृच्छिक डेटा के साथ हमारे बिटमैप को पॉप्युलेट करने के लिए एक का उपयोग किया जाएगा। यादृच्छिक, लेकिन एक निश्चित संभावना के साथ कि रेस्तरां में प्रत्येक संपत्ति है। उदाहरण के लिए, मेरा मानना ​​है कि मॉस्को में बहुत कम रेस्तरां हैं जहां आप एक टेबल आरक्षित नहीं कर सकते हैं, और यह मुझे लगता है कि लगभग 20% प्रतिष्ठान शाकाहारियों के लिए उपयुक्त हैं।

दूसरा फ़ंक्शन बिटमैप को रेस्तरां की सूची में बदल देगा।


अनुरोध का जवाब देने के लिए "मुझे सस्ते रेस्तरां दिखाएं जिनमें एक बरामदा है और जहां आप एक मेज आरक्षित कर सकते हैं", हमें दो बिट संचालन की आवश्यकता है: नहीं और और।

हम अधिक जटिल और NOT ऑपरेशन का उपयोग करके अपने कोड को थोड़ा सरल बना सकते हैं।

इनमें से प्रत्येक ऑपरेशन के लिए हमारे पास कार्य हैं। दोनों स्लाइस के माध्यम से जाते हैं, प्रत्येक से संबंधित तत्वों को लेते हैं, उन्हें थोड़ा ऑपरेशन के साथ जोड़ते हैं और परिणामी टुकड़ा में डालते हैं।

और अब हम खोज क्वेरी का जवाब देने के लिए अपने बिटमैप और फ़ंक्शन का उपयोग कर सकते हैं।

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

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

तथ्य यह है कि गो संकलक छोरों से बहुत डरता है जो स्लाइस के माध्यम से जाते हैं, और स्पष्ट रूप से इनलाइन कार्यों से इनकार करते हैं जिनमें लूप होते हैं।

लेकिन मुझे डर नहीं है, और मैं अच्छे पुराने दिनों की तरह, लूप के बजाय गोटो का उपयोग करके कंपाइलर को बेवकूफ बना सकता हूं।




और, जैसा कि आप देख सकते हैं, अब कंपाइलर ख़ुशी से हमारे कार्य को रेखांकित करता है! नतीजतन, हम लगभग 2 माइक्रोसेकंड बचाने के लिए प्रबंधन करते हैं। बुरा नहीं है!



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

चलो उसे यह दिखाते हुए संकलक को आश्वस्त करते हैं कि सभी स्लाइस समान आकार हैं। हम अपने फ़ंक्शन की शुरुआत में एक साधारण जांच जोड़कर ऐसा कर सकते हैं।

यह देखकर, कंपाइलर खुशी से परीक्षण छोड़ देता है, और हम अंत में एक और 500 नैनोसेकंड बचाते हैं।

बड़ा चमगादड़

ठीक है, हम अपने सरल कार्यान्वयन से कुछ प्रदर्शन को निचोड़ने में कामयाब रहे, लेकिन यह परिणाम, वास्तव में, वर्तमान हार्डवेयर के साथ संभव से बहुत खराब है।

हम जो कुछ भी करते हैं वह मूल बिट संचालन है, और हमारे प्रोसेसर उन्हें बहुत कुशलता से करते हैं। लेकिन, दुर्भाग्य से, हम अपने प्रोसेसर को बहुत छोटे टुकड़ों के साथ "फीड" करते हैं। हमारे कार्य बाइट द्वारा संचालन करते हैं। हम बहुत आसानी से अपने कोड को ट्यून कर सकते हैं ताकि यह UInt64 स्लाइस का उपयोग करके 8-बाइट विखंडू के साथ काम करे।



जैसा कि आप देख सकते हैं, इस छोटे से परिवर्तन ने आठ बार बैच में वृद्धि के कारण हमारे कार्यक्रम को आठ गुना तेज कर दिया है। लाभ को रेखीय कहा जा सकता है।

असेम्बलर कार्यान्वयन

लेकिन यह अंत नहीं है। हमारे प्रोसेसर 16, 32 और यहां तक ​​कि 64 बाइट्स के टुकड़ों के साथ काम कर सकते हैं। इस तरह के "वाइड" ऑपरेशंस को सिंगल इंस्ट्रक्शन मल्टीपल डेटा (SIMD; एक इंस्ट्रक्शन, ढेर सारा डेटा) कहा जाता है, और कोड को बदलने की प्रक्रिया ताकि वह ऐसे ऑपरेशंस का उपयोग करता है, जिसे वैरिफिकेशन कहा जाता है।

दुर्भाग्य से, गो संकलक वेक्टरकरण में एक उत्कृष्ट छात्र से बहुत दूर है। वर्तमान में, गो पर कोड को वेक्टर करने का एकमात्र तरीका है कि इन असेंबली का उपयोग करते हुए मैन्युअल रूप से इन कार्यों को लेना और लगाना।



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

इसके अलावा, गो असामान्य प्लान 9 प्रारूप का उपयोग करता है, जो सामान्य रूप से मान्यता प्राप्त एटी एंड टी और इंटेल प्रारूपों से भिन्न होता है।

यह कहना सुरक्षित है कि गो असेंबलर को मैन्युअल रूप से लिखना सबसे मजेदार गतिविधि नहीं है।

लेकिन, सौभाग्य से, पहले से ही दो उच्च-स्तरीय उपकरण हैं जो हमें गो असेंबलर लिखने में मदद करते हैं: पीचपे और एवो। दोनों उपयोगिताओं क्रमशः पायथन और गो में लिखे गए उच्च-स्तरीय कोड से गो असेंबलर उत्पन्न करते हैं।

ये उपयोगिताओं रजिस्टर आवंटन, साइकिल लेखन जैसी चीजों को सरल बनाती हैं, और आम तौर पर गो में कोडांतरक प्रोग्रामिंग की दुनिया में प्रवेश करने की प्रक्रिया को सरल बनाती हैं।

हम एवो का उपयोग करेंगे, इसलिए हमारे कार्यक्रम लगभग सामान्य गो कार्यक्रम होंगे।

यह एवो प्रोग्राम का सबसे सरल उदाहरण है। हमारे पास एक मुख्य () फ़ंक्शन है जो ऐड () फ़ंक्शन को अपने अंदर परिभाषित करता है, जिसका अर्थ दो नंबर जोड़ना है। नाम से पैरामीटर प्राप्त करने और मुक्त और उपयुक्त प्रोसेसर रजिस्टरों में से एक प्राप्त करने के लिए सहायक कार्य हैं। प्रत्येक प्रोसेसर ऑपरेशन में एवो पर एक समान कार्य होता है, जैसा कि ADDQ में देखा गया है। अंत में, हम परिणामी मूल्य को संग्रहीत करने के लिए एक सहायक कार्य देखते हैं।

गो जनरेट को कॉल करके, हम एवो पर प्रोग्राम को निष्पादित करेंगे और अंत में दो फाइल जेनरेट होंगी:

• परिणामी गो कोडक कोड के साथ add.s;
  
• stub.go दो दुनिया को जोड़ने के लिए फ़ंक्शन हेडर के साथ: जाओ और कोडांतरक।
  

अब जब हमने देखा है कि एवो क्या और कैसे करता है, तो आइए एक नज़र डालते हैं। मैंने फ़ंक्शंस के स्केलर और वेक्टर (SIMD) दोनों संस्करणों को लागू किया।

सबसे पहले, स्केलर संस्करणों को देखें।

पिछले उदाहरण के रूप में, हम आपसे नि: शुल्क और सही सामान्य-प्रयोजन रजिस्टर प्रदान करने के लिए कहते हैं, हमें तर्कों के लिए ऑफ़सेट्स और आकारों की गणना करने की आवश्यकता नहीं है। यह सब एवो हमारे लिए करता है।

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

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

यह अंतिम कोडांतरक कोड जैसा दिखता है। हमें ऑफ़सेट्स और आकारों (हरे रंग में हाइलाइटेड) या इस्तेमाल किए गए रजिस्टरों का ट्रैक रखने (लाल रंग में हाइलाइट) की आवश्यकता नहीं थी।

यदि हम गो में सर्वश्रेष्ठ कार्यान्वयन के प्रदर्शन के साथ कोडांतरक में कार्यान्वयन के प्रदर्शन की तुलना करते हैं, तो हम देखेंगे कि यह समान है। और यह अपेक्षित है। आखिरकार, हमने कुछ खास नहीं किया - हमने सिर्फ गो कंपाइलर का पुन: उपयोग किया।

दुर्भाग्य से, हम कंपाइलर को असेंबलर में लिखे गए हमारे कार्यों को इनलाइन करने के लिए बाध्य नहीं कर सकते हैं। गो संकलक के पास आज यह सुविधा नहीं है, हालांकि इसे जोड़ने का अनुरोध काफी समय से किया जा रहा है।

यही कारण है कि असेंबलर में छोटे कार्यों से कोई भी लाभ प्राप्त करना असंभव है। हमें या तो बड़े फ़ंक्शन लिखने की ज़रूरत है, या नए गणित / बिट्स पैकेज का उपयोग करना है, या कोडांतरक पक्ष को बायपास करना है।

आइए अब हमारे कार्यों के वेक्टर संस्करणों को देखें।

इस उदाहरण के लिए, मैंने AVX2 का उपयोग करने का फैसला किया है, इसलिए हम 32-बाइट विखंडू के साथ काम करने वाले कार्यों का उपयोग करेंगे। कोड संरचना स्केलर विकल्प के समान है: लोडिंग पैरामीटर, कृपया हमें एक नि: शुल्क सामान्य रजिस्टर प्रदान करें, आदि।

नवाचारों में से एक यह है कि व्यापक वेक्टर ऑपरेशन विशेष विस्तृत रजिस्टरों का उपयोग करते हैं। 32-बाइट विखंडू के मामले में, ये उपसर्ग Y के साथ रजिस्टर हैं। यही कारण है कि आप कोड में YMM () फ़ंक्शन देखते हैं। यदि मैं 64-बिट विखंडू के साथ AVX-512 का उपयोग कर रहा था, तो उपसर्ग Z होगा।

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

खैर, प्रदर्शन के बारे में क्या? वह सुंदर है! गो पर सर्वोत्तम समाधान के साथ तुलना में हमें सात गुना त्वरण मिला। प्रभावशाली, हुह?

लेकिन क्वेरी प्लानर के लिए AVX-512, प्रीफेटिंग या JIT (सिर्फ-इन-टाइम कंपाइलर) का उपयोग करके भी इस क्रियान्वयन में तेजी लाई जा सकती है। लेकिन यह निश्चित रूप से एक अलग रिपोर्ट के लिए एक विषय है।

बिटमैप इंडेक्स जारी करता है

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

पुराने वैज्ञानिक पत्रों में, बिटमैप इंडेक्स की तीन समस्याओं का उल्लेख किया गया है, लेकिन नए वैज्ञानिक कागजात और मेरा तर्क है कि वे अब प्रासंगिक नहीं हैं। हम इन समस्याओं में से प्रत्येक में गहराई से नहीं उतरेंगे, लेकिन हम उन्हें सतही रूप से समझेंगे।

बड़ी कार्डिनैलिटी की समस्या

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


, , . . . , — .

, , , roaring . — , bit runs — , .

roaring . , Go.

, , (binning). , , . — , , , . 185,2 185,3 .

, 1 .

, 50 250 , , , 200 .

, .

bitmap- , .

, . , . , , — lock contention, .

.

— . bitmap- , . lock contention.

— . , , — . - (, 100 500 ) . , , .

: .

bitmap- , , , , « ».

, , AND, OR . . - « 200 300 ».

OR.

. , 50 . 50 .

, . range-encoded bitmaps.

- (, 200), , . 200 . 300: 300 . और इसी तरह।

, , . , 300 , , 199 . हो गया।

, bitmap-. , , . , S2 Google. , . « » ( ).

तैयार समाधान

. - - , , .

, , bitmap- . , SIMD, .

, , .

Roaring

-, roaring bitmaps-, . , , bitmap-.

, Go- SIMD, , Go- , C, .

Pilosa

, , — Pilosa, , , bitmap- . , .

Pilosa roaring , , : , range-encoded bitmaps, . .

Pilosa .

, . Pilosa, , , , .

NOT «expensive», ( AND-) «terrace» «reservations». , .

, MySQL PostgreSQL — bitmap-.

निष्कर्ष

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

बिटमैप इंडेक्स के बारे में जानना अच्छा है, भले ही आपको अभी उनकी आवश्यकता न हो। उन्हें अपने दराज में एक और उपकरण होने दें।

आपने और मैंने गो और उन चीजों के लिए विभिन्न प्रदर्शन चालों की जांच की, जो गो संकलक अब तक बहुत अच्छा नहीं करते हैं। लेकिन यह जानने के लिए हर गो प्रोग्रामर के लिए बिल्कुल उपयोगी है।

वह सब मैं बताना चाहता था। धन्यवाद!