Go मा बिटम्याप अनुक्रमणिकाहरू: जंगली गतिमा खोज्नुहोस्

परिचय

मैले यो रिपोर्ट मस्कोमा गोफरकन रूस 2019 सम्मेलनमा अंग्रेजीमा र निज्नी नोभगोरोडमा भएको बैठकमा रूसीमा दिएँ। हामी बिटम्याप सूचकांकको बारेमा कुरा गर्दैछौं - बी-ट्री भन्दा कम सामान्य, तर कम रोचक छैन। बाढ्नु रेकर्डिङ सम्मेलनमा अंग्रेजीमा भाषण र रूसीमा पाठ ट्रान्सक्रिप्ट।

हामी हेर्नेछौं कि बिटम्याप अनुक्रमणिका कसरी काम गर्दछ, यो कहिले राम्रो हुन्छ, कहिले यो अन्य अनुक्रमणिकाहरू भन्दा खराब हुन्छ, र कुन अवस्थामा यो तिनीहरू भन्दा धेरै छिटो हुन्छ; कुन लोकप्रिय DBMS हरू पहिले नै बिटम्याप अनुक्रमणिकाहरू छन् हेरौं; Go मा हाम्रो आफ्नै लेख्ने प्रयास गरौं। र "मिठाईको लागि" हामी हाम्रो आफ्नै सुपर-फास्ट विशेष डाटाबेस सिर्जना गर्न तयार पुस्तकालयहरू प्रयोग गर्नेछौं।

म साँच्चै आशा गर्छु कि मेरो कामहरू तपाईका लागि उपयोगी र रोचक हुनेछ। जाउ!

परिचय

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

नमस्ते सबै! साँझको छ बजेको छ र हामी सबै थकित छौं। बोरिङ डाटाबेस सूचकांक सिद्धान्तको बारेमा कुरा गर्न राम्रो समय, हैन? चिन्ता नगर्नुहोस्, मसँग यहाँ र त्यहाँ स्रोत कोडको दुई लाइनहरू हुनेछन्। 🙂

सबै चुटकुलेहरू एकै ठाउँमा, रिपोर्ट जानकारीले भरिएको छ, र हामीसँग धेरै समय छैन। त्यसैले सुरु गरौं।

आज म निम्न बारे कुरा गर्नेछु:

• सूचकांक के हो;
• बिटमैप सूचकांक के हो;
• कहाँ प्रयोग गरिन्छ र कहाँ प्रयोग हुँदैन र किन;
• गो मा सरल कार्यान्वयन र कम्पाइलर संग एक सानो संघर्ष;
• थोरै कम सरल, तर गो एसेम्बलरमा धेरै उत्पादक कार्यान्वयन;
• बिटमैप अनुक्रमणिकाको "समस्याहरू";
• अवस्थित कार्यान्वयनहरू।

त्यसैले अनुक्रमणिकाहरू के हुन्?

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

यो अत्यन्तै जटिल विषय हो, सूक्ष्मता र ट्रेड-अफले भरिएको छ, तर दशकौंको डाटाबेस विकास र अनुसन्धानलाई हेरेपछि, म भन्न चाहन्छु कि डाटाबेस अनुक्रमणिकाहरू सिर्जना गर्नका लागि केही व्यापक रूपमा प्रयोग गरिएका दृष्टिकोणहरू मात्र छन्।

पहिलो दृष्टिकोण पदानुक्रमित रूपमा खोज स्थान कम गर्न, खोज स्थानलाई साना भागहरूमा विभाजन गर्न हो।

हामी सामान्यतया यो विभिन्न प्रकारका रूखहरू प्रयोग गरेर गर्छौं। एउटा उदाहरण तपाईंको कोठरीमा सामग्रीहरूको ठूलो बाकस हुनेछ जुन विभिन्न विषयहरूमा विभाजित सामग्रीहरूको साना बक्सहरू समावेश गर्दछ। यदि तपाईंलाई सामग्रीहरू चाहिन्छ भने, तपाईंले तिनीहरूलाई "कुकीहरू" भन्नुको सट्टा "सामग्री" भन्ने बाकसमा खोज्नुहुनेछ, हैन?

दोस्रो दृष्टिकोण तुरुन्तै इच्छित तत्व वा तत्वहरूको समूह चयन गर्न हो। हामी यसलाई ह्यास नक्सा वा उल्टो अनुक्रमणिकामा गर्छौं। ह्यास नक्साहरू प्रयोग गर्नु अघिल्लो उदाहरणसँग धेरै मिल्दोजुल्दो छ, तर बक्सहरूको बक्सको सट्टा, तपाईंको कोठरीमा अन्तिम वस्तुहरूको सानो बक्सहरूको गुच्छा छ।

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

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

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

आज म यी मध्ये सबैभन्दा कम ज्ञात दृष्टिकोणको बारेमा कुरा गर्नेछु - बिटम्याप अनुक्रमणिकाहरू।

यो विषयमा बोल्ने म को हुँ ?

म Badoo मा टोली नेतृत्वको रूपमा काम गर्छु (सायद तपाईं हाम्रो अर्को उत्पादन, बम्बलसँग बढी परिचित हुनुहुन्छ)। हामीसँग पहिले नै संसारभरि 400 मिलियन भन्दा बढी प्रयोगकर्ताहरू छन् र धेरै सुविधाहरू छन् जसले उनीहरूका लागि उत्तम मिल्दो चयन गर्दछ। हामी बिटम्याप अनुक्रमणिकाहरू सहित अनुकूलन सेवाहरू प्रयोग गरेर यो गर्छौं।

त्यसोभए बिटम्याप सूचकांक के हो?

बिटम्याप अनुक्रमणिकाहरू, नामले सुझाव दिए जस्तै, खोज अनुक्रमणिका लागू गर्न बिटम्याप वा बिटसेटहरू प्रयोग गर्नुहोस्। चराको आँखाको दृश्यबाट, यो अनुक्रमणिकाले कुनै पनि निकायहरू (जस्तै मानिसहरू) र तिनीहरूको गुण वा प्यारामिटरहरू (उमेर, आँखाको रङ, आदि) को प्रतिनिधित्व गर्ने एक वा बढी त्यस्ता बिटम्यापहरू समावेश गर्दछ, र बिट अपरेशनहरू (AND, OR, NOT) प्रयोग गरेर एल्गोरिदम समावेश गर्दछ। ) खोज प्रश्नको जवाफ दिन।

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

बिटमैप सूचकांकको सरल उदाहरण हेरौं।

कल्पना गर्नुहोस् कि हामीसँग मस्को रेस्टुरेन्टहरूको सूची छ जसमा बाइनरी गुणहरू छन्:

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

प्रत्येक रेस्टुरेन्टलाई ० बाट सुरु हुने क्रम संख्या दिऔं र ६ बिटम्यापका लागि मेमोरी आवंटित गरौं (प्रत्येक विशेषताको लागि एक)। रेस्टुरेन्टमा यो सम्पत्ति छ वा छैन भन्ने आधारमा हामी यी बिटम्यापहरू भर्नेछौं। यदि रेस्टुरेन्ट 0 मा बरामदा छ भने, बिट नम्बर 6 मा "एक बरामदा छ" बिटम्याप 4 मा सेट गरिनेछ (यदि त्यहाँ कुनै बरामदा छैन भने, त्यसपछि 4)।

अब हामीसँग सम्भव भएसम्म सरल बिटम्याप अनुक्रमणिका छ, र हामी यसलाई प्रश्नहरूको जवाफ दिन प्रयोग गर्न सक्छौं:

• "मलाई शाकाहारी-अनुकूल रेस्टुरेन्टहरू देखाउनुहोस्";
• "मलाई एउटा बरामदा भएको सस्तो रेस्टुरेन्टहरू देखाउनुहोस् जहाँ तपाइँ टेबल रिजर्भ गर्न सक्नुहुन्छ।"

कसरी? हेरौं। पहिलो अनुरोध धेरै सरल छ। हामीले के गर्नु पर्छ "शाकाहारी मैत्री" बिटम्याप लिनुहोस् र यसलाई रेस्टुरेन्टहरूको सूचीमा परिणत गर्नुहोस् जसको बिटहरू खुला छन्।


दोस्रो अनुरोध अलि बढी जटिल छ। हामीले सस्तो रेस्टुरेन्टहरूको सूची प्राप्त गर्न "महंगा" बिटम्यापमा NOT बिटम्याप प्रयोग गर्न आवश्यक छ, त्यसपछि र यसलाई "के म टेबल बुक गर्न सक्छु" बिटम्याप र र परिणाम "त्यहाँ एउटा बरामदा छ" बिटम्यापको साथ। परिणामस्वरूप बिटम्यापले हाम्रा सबै मापदण्डहरू पूरा गर्ने प्रतिष्ठानहरूको सूची समावेश गर्दछ। यस उदाहरणमा, यो युनोस्ट रेस्टुरेन्ट मात्र हो।


त्यहाँ धेरै सिद्धान्तहरू समावेश छन्, तर चिन्ता नगर्नुहोस्, हामी छिट्टै कोड देख्नेछौं।

बिटम्याप अनुक्रमणिकाहरू कहाँ प्रयोग गरिन्छ?

यदि तपाइँ Google बिटम्याप अनुक्रमणिकाहरू गर्नुहुन्छ भने, 90% उत्तरहरू कुनै न कुनै रूपमा Oracle DB सँग सम्बन्धित हुनेछन्। तर अन्य DBMS हरूले पनि यस्तो राम्रो कुरालाई समर्थन गर्दछ, हैन? साँच्चै होइन।

मुख्य संदिग्धहरूको सूची मार्फत जाऔं।

MySQL ले अझै बिटम्याप अनुक्रमणिकाहरूलाई समर्थन गर्दैन, तर त्यहाँ यो विकल्प थप्न सुझाव दिने प्रस्ताव छ (https://dev.mysql.com/worklog/task/?id=1524).

PostgreSQL ले बिटम्याप अनुक्रमणिकाहरूलाई समर्थन गर्दैन, तर धेरै अन्य अनुक्रमणिकाहरूमा खोज परिणामहरू संयोजन गर्न सरल बिटम्याप र बिट अपरेशनहरू प्रयोग गर्दछ।

Tarantool सँग बिटसेट अनुक्रमणिकाहरू छन् र तिनीहरूमा सरल खोजहरूलाई समर्थन गर्दछ।

रेडिससँग साधारण बिटफिल्डहरू छन् (https://redis.io/commands/bitfield) तिनीहरूलाई खोज्ने क्षमता बिना।

MongoDB ले अझै बिटम्याप अनुक्रमणिकाहरूलाई समर्थन गर्दैन, तर यो विकल्प थप्न सुझाव दिने प्रस्ताव पनि छ। https://jira.mongodb.org/browse/SERVER-1723

Elasticsearch आन्तरिक रूपमा बिटम्याप प्रयोग गर्दछ (https://www.elastic.co/blog/frame-of-reference-and-roaring-bitmaps).

• तर हाम्रो घरमा नयाँ छिमेकी देखा पर्‍यो: पिलोसा। यो Go मा लेखिएको नयाँ गैर-सम्बन्धित डाटाबेस हो। यसले केवल बिटम्याप अनुक्रमणिकाहरू समावेश गर्दछ र तिनीहरूमा सबै कुरालाई आधार गर्दछ। हामी यसको बारेमा केहि पछि कुरा गर्नेछौं।

Go मा कार्यान्वयन

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

बिटम्यापहरू अनिवार्य रूपमा डाटाको टुक्रा मात्र हुन्। Go मा, यसको लागि बाइट स्लाइसहरू प्रयोग गरौं।

हामीसँग एउटा रेस्टुरेन्टको विशेषताको लागि एउटा बिटम्याप छ, र बिटम्यापको प्रत्येक बिटले कुनै खास रेस्टुरेन्टमा यो सम्पत्ति छ वा छैन भन्ने संकेत गर्छ।

हामीलाई दुई सहायक कार्यहरू चाहिन्छ। एउटा हाम्रो बिटम्यापहरू अनियमित डाटा भर्न प्रयोग गरिनेछ। अनियमित, तर एक निश्चित सम्भावना संग कि रेस्टुरेन्ट प्रत्येक सम्पत्ति छ। उदाहरणका लागि, म विश्वास गर्छु कि मस्कोमा धेरै थोरै रेस्टुरेन्टहरू छन् जहाँ तपाइँ टेबल आरक्षित गर्न सक्नुहुन्न, र मलाई लाग्छ कि लगभग 20% प्रतिष्ठानहरू शाकाहारीहरूका लागि उपयुक्त छन्।

दोस्रो प्रकार्यले बिटम्यापलाई रेस्टुरेन्टहरूको सूचीमा रूपान्तरण गर्नेछ।


"मलाई आँगन भएका र रिजर्भेसन गर्न सक्ने सस्तो रेस्टुरेन्टहरू देखाउनुहोस्" भन्ने प्रश्नको जवाफ दिन हामीलाई दुईवटा बिट अपरेशनहरू चाहिन्छ: होइन र र।

हामी हाम्रो कोडलाई थप जटिल र होइन अपरेटर प्रयोग गरेर थोरै सरल बनाउन सक्छौं।

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

र अब हामी खोज क्वेरीको जवाफ दिन हाम्रो बिटम्याप र प्रकार्यहरू प्रयोग गर्न सक्छौं।

कार्यहरू धेरै सरल भए तापनि कार्यसम्पादन त्यति उच्च छैन र हामीले प्रत्येक पटक प्रकार्य कल गर्दा नयाँ नतिजाको टुक्रा फिर्ता नगरी धेरै पैसा बचत गर्यौं।

pprof सँग केही प्रोफाइलिङ गरेपछि, मैले गो कम्पाइलरले एउटा धेरै सरल तर धेरै महत्त्वपूर्ण अप्टिमाइजेसन हराइरहेको देखेँ: प्रकार्य इनलाइनिङ।

तथ्य यो हो कि गो कम्पाइलर स्लाइसहरू मार्फत जाने लूपहरूबाट धेरै डराउँछ, र स्पष्ट रूपमा त्यस्ता लूपहरू समावेश गर्ने इनलाइन प्रकार्यहरूलाई अस्वीकार गर्दछ।

तर म डराउँदिन र म लूपको सट्टा गोटो प्रयोग गरेर कम्पाइलरलाई मूर्ख बनाउन सक्छु, जस्तै राम्रो पुरानो दिनहरूमा।

र, तपाईले देख्न सक्नुहुन्छ, अब कम्पाइलरले हाम्रो प्रकार्यलाई खुसीसाथ इनलाइन गर्नेछ! नतिजाको रूपमा, हामी लगभग 2 माइक्रोसेकेन्ड बचत गर्न व्यवस्थापन गर्छौं। खराब छैन!

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

सबै स्लाइसहरू एउटै साइजका छन् भनेर देखाएर कम्पाइलरलाई आश्वस्त गरौं। हामी हाम्रो प्रकार्यको सुरुमा एक साधारण जाँच थपेर यो गर्न सक्छौं।

यो देखेर, कम्पाइलरले खुसीसाथ चेक छोड्छ, र हामीले अर्को 500 नानोसेकेन्डहरू बचत गर्छौं।

ठूला बुचहरू

ठीक छ, हामीले हाम्रो साधारण कार्यान्वयनबाट केही प्रदर्शन निचोड गर्न व्यवस्थित गर्यौं, तर यो नतिजा हालको हार्डवेयरसँग सम्भव भन्दा धेरै खराब छ।

हामीले गर्ने सबै आधारभूत बिट अपरेशनहरू हुन्, र हाम्रा प्रोसेसरहरूले तिनीहरूलाई धेरै कुशलतापूर्वक प्रदर्शन गर्छन्। तर, दुर्भाग्यवश, हामी हाम्रो प्रोसेसरलाई कामको धेरै सानो टुक्राहरूसँग "फिड" गर्छौं। हाम्रा प्रकार्यहरूले बाइट-द्वारा-बाइट आधारमा सञ्चालन गर्दछ। हामी UInt8 स्लाइसहरू प्रयोग गरेर 64-बाइट खण्डहरूसँग काम गर्न हाम्रो कोडलाई सजिलैसँग ट्वीक गर्न सक्छौं।

तपाईले देख्न सक्नुहुने रूपमा, यो सानो परिवर्तनले ब्याच साइजलाई आठ गुणाले बढाएर हाम्रो कार्यक्रमलाई आठ गुणा गति दियो। लाभ लिनियर भन्न सकिन्छ।

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

तर यो अन्त्य होइन। हाम्रा प्रोसेसरहरूले 16, 32 र 64 बाइटको टुक्राहरूसँग काम गर्न सक्छन्। त्यस्ता "ब्रोड" अपरेशनहरूलाई सिंगल इन्स्ट्रक्शन मल्टिपल डाटा (SIMD; एक निर्देशन, धेरै डाटा) भनिन्छ, र कोड रूपान्तरण गर्ने प्रक्रिया जसले त्यस्ता अपरेशनहरू प्रयोग गर्छ त्यसलाई भेक्टोराइजेशन भनिन्छ।

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

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

थप रूपमा, Go ले असामान्य योजना 9 ढाँचा प्रयोग गर्दछ, जुन सामान्यतया स्वीकृत AT&T र Intel ढाँचाहरू भन्दा फरक छ।

यो भन्न सुरक्षित छ कि हातले गो एसेम्बलर लेख्नु सबैभन्दा रमाइलो होइन।

तर, सौभाग्यवश, त्यहाँ पहिले नै दुई उच्च-स्तरीय उपकरणहरू छन् जसले हामीलाई गो एसेम्बलर लेख्न मद्दत गर्दछ: PeachPy र avo। दुबै उपयोगिताहरूले क्रमशः पाइथन र गोमा लेखिएको उच्च-स्तर कोडबाट गो एसेम्बलर उत्पन्न गर्दछ।

यी उपयोगिताहरूले दर्ता आवंटन, लुपहरू लेख्ने जस्ता चीजहरूलाई सरल बनाउँदछ, र सामान्यतया Go मा असेंबली प्रोग्रामिङको संसारमा प्रवेश गर्ने प्रक्रियालाई सरल बनाउँदछ।

हामी avo प्रयोग गर्नेछौं, त्यसैले हाम्रा कार्यक्रमहरू लगभग नियमित Go कार्यक्रमहरू हुनेछन्।

यो एक avo कार्यक्रम को सरल उदाहरण जस्तो देखिन्छ। हामीसँग मुख्य () प्रकार्य छ, जसले आफैंमा Add() प्रकार्य परिभाषित गर्दछ, जसको अर्थ दुई नम्बरहरू थप्नु हो। नामद्वारा प्यारामिटरहरू प्राप्त गर्न र नि:शुल्क र उपयुक्त प्रोसेसर दर्ताहरू प्राप्त गर्न यहाँ सहायक कार्यहरू छन्। ADDQ मा देखिए अनुसार प्रत्येक प्रोसेसर अपरेशनको एभोमा सम्बन्धित प्रकार्य हुन्छ। अन्तमा, हामी परिणामित मान भण्डारण गर्नको लागि एक सहायक प्रकार्य देख्छौं।

go generate लाई कल गरेर, हामी avo मा कार्यक्रम कार्यान्वयन गर्नेछौं र परिणाम स्वरूप, दुई फाइलहरू उत्पन्न हुनेछन्:

• गो एसेम्बलरमा नतिजा कोडको साथ add.s;
• stub.go दुई संसारहरू जडान गर्न प्रकार्य हेडरहरूसँग: जानुहोस् र एसेम्बलर।

अब हामीले avo के गर्छ र कसरी हेर्छौं, हाम्रो कार्यहरू हेरौं। मैले प्रकार्यहरूको स्केलर र भेक्टर (SIMD) संस्करणहरू लागू गरें।

पहिले स्केलर संस्करणहरू हेरौं।

अघिल्लो उदाहरणमा जस्तै, हामीले नि:शुल्क र मान्य सामान्य प्रयोजन दर्ताको लागि सोधिरहेका छौं, हामीले तर्कहरूको लागि अफसेटहरू र साइजहरू गणना गर्न आवश्यक छैन। avo हाम्रो लागि यो सबै गर्छ।

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

बाँकी कोड पहिले नै परिचित र बुझ्न योग्य हुनुपर्छ। हामी लेबलहरू र जम्पहरूको साथ लुपको अनुकरण गर्छौं, हाम्रा दुई स्लाइसहरूबाट डाटाको सानो टुक्रा लिन्छौं, तिनीहरूलाई बिट अपरेशनसँग जोड्छौं (र यस अवस्थामा होइन) र त्यसपछि परिणामलाई नतिजाको टुक्रामा राख्छौं। सबै।

यो अन्तिम एसेम्बलर कोड जस्तो देखिन्छ। हामीले अफसेटहरू र साइजहरू (हरियोमा हाइलाइट गरिएको) वा प्रयोग गरिएका दर्ताहरूको ट्र्याक राख्नु पर्दैन (रातोमा हाइलाइट गरिएको)।

यदि हामीले एसेम्बली भाषा कार्यान्वयनको कार्यसम्पादनलाई Go मा उत्कृष्ट कार्यान्वयनको कार्यसम्पादनसँग तुलना गर्छौं भने, हामी देख्नेछौं कि यो समान छ। र यो अपेक्षित छ। आखिर, हामीले केहि विशेष गरेनौं - हामीले भर्खरै पुन: उत्पादन गर्यौं कि गो कम्पाइलरले के गर्छ।

दुर्भाग्यवश, हामी कम्पाइलरलाई विधानसभा भाषामा लेखिएका हाम्रा कार्यहरू इनलाइन गर्न बाध्य पार्न सक्दैनौं। गो कम्पाइलरमा हाल त्यस्तो सुविधा छैन, यद्यपि त्यहाँ केहि समयको लागि यसलाई थप्न अनुरोध गरिएको छ।

त्यसैले सभाको भाषामा सानातिना कार्यबाट फाइदा लिन असम्भव छ। हामीले या त ठूला प्रकार्यहरू लेख्नुपर्छ, वा नयाँ गणित/बिट्स प्याकेज प्रयोग गर्नुपर्छ, वा एसेम्बलर भाषालाई बाइपास गर्नुपर्छ।

अब हाम्रो प्रकार्यहरूको भेक्टर संस्करणहरू हेरौं।

यस उदाहरणको लागि, मैले AVX2 प्रयोग गर्ने निर्णय गरें, त्यसैले हामी 32-बाइट खण्डहरूमा सञ्चालन गर्ने कार्यहरू प्रयोग गर्नेछौं। कोडको संरचना स्केलर संस्करणसँग धेरै मिल्दोजुल्दो छ: प्यारामिटरहरू लोड गर्दै, नि: शुल्क साझा दर्ताको लागि सोध्ने, आदि।

एउटा नवीनता यो हो कि फराकिलो भेक्टर सञ्चालनहरूले विशेष फराकिलो दर्ताहरू प्रयोग गर्दछ। ३२-बाइट टुक्राहरूको अवस्थामा, यी Y सँग उपसर्ग लगाइएका रेजिस्टरहरू हुन्। यसैले तपाईंले कोडमा YMM() प्रकार्य देख्नुहुन्छ। यदि मैले AVX-32 512-बिट खण्डहरू प्रयोग गरिरहेको थिए भने, उपसर्ग Z हुनेछ।

दोस्रो नवीनता यो हो कि मैले लुप अनरोलिङ भनिने अप्टिमाइजेसन प्रयोग गर्ने निर्णय गरें, जसको अर्थ लूपको सुरुमा जम्प गर्नु अघि म्यानुअल रूपमा आठ लूप अपरेशनहरू गर्ने। यो अप्टिमाइजेसनले कोडमा शाखाहरूको संख्या घटाउँछ, र उपलब्ध निःशुल्क दर्ताहरूको संख्याद्वारा सीमित हुन्छ।

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

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

बिटम्याप अनुक्रमणिकाहरूसँग समस्याहरू

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

पुराना कागजातहरूले बिटम्याप अनुक्रमणिकाहरूसँग तीनवटा समस्याहरू उल्लेख गर्छन्, तर नयाँ कागजातहरू र म तर्क गर्छु कि तिनीहरू अब सान्दर्भिक छैनन्। हामी यी प्रत्येक समस्यामा गहिरो डुब्ने छैनौं, तर तिनीहरूलाई सतही रूपमा हेर्नेछौं।

उच्च कार्डिनलिटीको समस्या

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


कहिलेकाहीँ हामीले फरक प्रतिनिधित्व प्रयोग गर्न सक्छौं, जस्तै हामीले संख्याहरू प्रतिनिधित्व गर्न प्रयोग गर्ने मानक। तर यो कम्प्रेसन एल्गोरिदमको आगमन थियो जसले सबै कुरा परिवर्तन गर्यो। विगतका दशकहरूमा, वैज्ञानिकहरू र अनुसन्धानकर्ताहरूले बिटम्यापहरूको लागि ठूलो संख्यामा कम्प्रेसन एल्गोरिदमहरू लिएर आएका छन्। तिनीहरूको मुख्य फाइदा यो हो कि बिट अपरेशनहरू गर्न बिटम्यापहरू डिकम्प्रेस गर्न आवश्यक पर्दैन - हामी कम्प्रेस गरिएको बिटम्यापहरूमा सीधा बिट अपरेशनहरू गर्न सक्छौं।

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

तपाईंले सबैभन्दा लोकप्रिय अनुप्रयोगहरूमा गर्जन बिटम्यापहरू फेला पार्न सक्नुहुन्छ। Go का लागि तीन भन्दा बढी कार्यान्वयनहरू सहित, प्रोग्रामिङ भाषाहरूको विस्तृत विविधताका लागि पहिले नै ठूलो संख्यामा कार्यान्वयनहरू छन्।

अर्को दृष्टिकोण जसले हामीलाई उच्च कार्डिनलिटीको सामना गर्न मद्दत गर्न सक्छ बिनिङ भनिन्छ। कल्पना गर्नुहोस् कि तपाईंसँग एक व्यक्तिको उचाइ प्रतिनिधित्व गर्ने क्षेत्र छ। उचाइ एक फ्लोटिंग बिन्दु संख्या हो, तर हामी मानवहरूले यसलाई त्यसरी सोच्दैनौं। हाम्रो लागि उचाइ 185,2 सेमी र 185,3 सेमी बीच कुनै भिन्नता छैन।

यो बाहिर जान्छ कि हामी समान मानहरूलाई 1 सेन्टिमिटर भित्र समूहमा समूह बनाउन सक्छौं।

र यदि हामीलाई यो पनि थाहा छ कि धेरै कम व्यक्तिहरू 50 सेन्टीमिटर भन्दा कम र 250 सेन्टिमिटर भन्दा अग्लो छन्, तब हामी अनिवार्य रूपमा असीम कार्डिनलिटी भएको फिल्डलाई लगभग 200 मानहरूको कार्डिनलिटी भएको फिल्डमा बदल्न सक्छौं।

निस्सन्देह, आवश्यक भएमा, हामी पछि थप फिल्टर गर्न सक्छौं।

उच्च ब्यान्डविथ समस्या

बिटम्याप अनुक्रमणिकाहरूसँग अर्को समस्या यो हो कि तिनीहरूलाई अद्यावधिक गर्न धेरै महँगो हुन सक्छ।

डाटाबेसहरूले डाटा अपडेट गर्न सक्षम हुनुपर्दछ जब सम्भावित रूपमा अन्य सयौं प्रश्नहरूले डाटा खोजीरहेका छन्। हामीलाई समवर्ती डेटा पहुँच वा अन्य साझा समस्याहरूको समस्याबाट बच्न लकहरू चाहिन्छ। र जहाँ एउटा ठूलो ताला छ, त्यहाँ समस्या छ - ताला विवाद, जब यो ताला बाधा बन्छ।

यो समस्या शार्डिङ प्रयोग गरेर वा संस्करणित अनुक्रमणिका प्रयोग गरेर समाधान गर्न सकिन्छ।

Sharding एक सरल र परिचित कुरा हो। तपाईले बिटम्याप अनुक्रमणिकालाई अरु कुनै डेटा जस्तै बनाउन सक्नुहुन्छ। एउटा ठूलो तालाको सट्टा, तपाईंले साना लकहरूको गुच्छा पाउनुहुनेछ र यसरी लक विवादबाट छुटकारा पाउनुहुनेछ।

समस्या समाधान गर्ने दोस्रो तरिका संस्करण गरिएको अनुक्रमणिका प्रयोग गर्नु हो। तपाईले खोज्न वा पढ्नको लागि प्रयोग गर्नुहुने अनुक्रमणिकाको एउटा प्रतिलिपि, र तपाईले लेख्न वा अद्यावधिक गर्न प्रयोग गर्नुहुने एउटा प्रतिलिपि हुन सक्छ। र एक पटक निश्चित अवधिमा (उदाहरणका लागि, प्रत्येक १०० ms वा 100 ms मा एक पटक) तपाईंले तिनीहरूलाई डुप्लिकेट गर्नुहोस् र तिनीहरूलाई स्वैप गर्नुहोस्। निस्सन्देह, यो दृष्टिकोण केवल मामिलाहरूमा लागू हुन्छ जहाँ तपाईंको एप्लिकेसनले थोरै ढिलो खोज अनुक्रमणिका ह्यान्डल गर्न सक्छ।

यी दुई दृष्टिकोणहरू एकै साथ प्रयोग गर्न सकिन्छ: तपाईंसँग छर्रे संस्करण गरिएको अनुक्रमणिका हुन सक्छ।

थप जटिल प्रश्नहरू

बिटम्याप अनुक्रमणिकाको साथ अन्तिम समस्या यो हो कि हामीलाई भनिएको छ कि तिनीहरू थप जटिल प्रकारका प्रश्नहरूको लागि उपयुक्त छैनन्, जस्तै स्प्यान क्वेरीहरू।

वास्तवमा, यदि तपाइँ यसको बारेमा सोच्नुहुन्छ भने, AND, OR, आदि जस्ता बिट अपरेसनहरू प्रश्नहरूको लागि धेरै उपयुक्त छैनन् a la "मलाई प्रति रात 200 देखि 300 डलरसम्म कोठा दरहरू भएका होटलहरू देखाउनुहोस्।"

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

एक थोरै राम्रो समाधान समूह प्रयोग गर्न को लागी हुनेछ। उदाहरण को लागी, 50 डलर को समूह मा। यसले हाम्रो प्रक्रियालाई ५० गुणाले गति दिनेछ।

तर यस प्रकारको अनुरोधको लागि विशेष रूपमा सिर्जना गरिएको दृश्य प्रयोग गरेर समस्या पनि सजिलै समाधान हुन्छ। वैज्ञानिक कागजातहरूमा यसलाई दायरा-इन्कोडेड बिटम्याप भनिन्छ।

यस प्रतिनिधित्वमा, हामीले केही मान (उदाहरणका लागि, २००) को लागि एक बिट मात्र सेट गर्दैनौं, तर यो मान र सबै कुरा उच्च सेट गर्छौं। 200 र माथि। 200: 300 र माथिको लागि समान। र यस्तै।

यो प्रतिनिधित्व प्रयोग गरेर, हामी केवल दुई पटक अनुक्रमणिका ट्र्याभर गरेर यस प्रकारको खोज क्वेरीको जवाफ दिन सक्छौं। पहिले, हामीले कोठाको भाडा कम वा $300 हुने होटलहरूको सूची प्राप्त गर्नेछौं, र त्यसपछि कोठाको लागत कम वा $199 छ भने हामी त्यसबाट हटाउनेछौं। तयार।

तपाईं छक्क पर्नुहुनेछ, तर बिटम्याप अनुक्रमणिकाहरू प्रयोग गरेर जियोक्वेरीहरू पनि सम्भव छन्। चाल भनेको ज्यामितीय प्रतिनिधित्व प्रयोग गर्नु हो जसले तपाईंको समन्वयलाई ज्यामितीय आकृतिसँग घेर्छ। उदाहरण को लागी, Google बाट S2। अंकित गर्न सकिने तीन वा बढी प्रतिच्छेदन रेखाहरूको रूपमा चित्रण गर्न सम्भव हुनुपर्छ। यस तरिकाले हामी हाम्रो जियोक्वेरीलाई धेरै प्रश्नहरूमा "अन्ग द ग्याप" (यी संख्यात्मक रेखाहरूसँग) मा बदल्न सक्छौं।

तयार समाधानहरू

मलाई आशा छ कि मैले तपाईलाई थोरै चासो दिएँ र तपाईसँग अब तपाईको शस्त्रागारमा अर्को उपयोगी उपकरण छ। यदि तपाइँ कहिल्यै यस्तो केहि गर्न आवश्यक छ भने, तपाइँ कुन बाटो हेर्ने थाहा पाउनुहुनेछ।

यद्यपि, सबैसँग समय, धैर्य, वा स्रोतहरू स्क्र्याचबाट बिटम्याप अनुक्रमणिकाहरू सिर्जना गर्न हुँदैन। विशेष गरी थप उन्नतहरू, उदाहरणका लागि SIMD प्रयोग गरेर।

सौभाग्य देखि, तपाईंलाई मद्दत गर्न धेरै तयार समाधानहरू छन्।

गर्जन बिटम्यापहरू

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

दुर्भाग्यवश, यस समयमा, कुनै पनि Go कार्यान्वयनले SIMD प्रयोग गर्दैन, जसको मतलब Go कार्यान्वयनहरू C कार्यान्वयनहरू भन्दा कम प्रदर्शनकारी छन्, उदाहरणका लागि।

पिलोसा

अर्को उत्पादन जसले तपाईंलाई मद्दत गर्न सक्छ Pilosa DBMS, जसमा, वास्तवमा, केवल बिटम्याप अनुक्रमणिकाहरू छन्। यो अपेक्षाकृत नयाँ समाधान हो, तर यसले ठूलो गतिमा मन जितिरहेको छ।

Pilosa ले गर्जन बिटम्यापहरू आन्तरिक रूपमा प्रयोग गर्दछ र तपाईंलाई तिनीहरूलाई प्रयोग गर्ने क्षमता दिन्छ, मैले माथि कुरा गरेको सबै चीजहरूलाई सरल बनाउँछ र व्याख्या गर्दछ: समूहीकरण, दायरा-इन्कोडेड बिटम्यापहरू, क्षेत्रको अवधारणा, आदि।

तपाईं पहिले नै परिचित हुनुहुन्छ भन्ने प्रश्नको जवाफ दिन Pilosa प्रयोग गर्ने उदाहरणमा एक पटक हेरौं।

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

त्यस पछि, हामी "महंगा" फिल्डमा NOT प्रयोग गर्छौं, त्यसपछि नतिजा (वा AND it) लाई "टेरेस" फिल्ड र "रिजर्भेसन" फिल्डसँग काट्छौं। र अन्तमा, हामी अन्तिम परिणाम प्राप्त गर्छौं।

मलाई आशा छ कि निकट भविष्यमा यो नयाँ प्रकारको अनुक्रमणिका MySQL र PostgreSQL - bitmap indexes जस्ता DBMSs मा पनि देखा पर्नेछ।

निष्कर्षमा

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

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

हामीले Go को लागि विभिन्न प्रदर्शन चालहरू हेरेका छौं र चीजहरू जुन गो कम्पाइलरले अझै राम्रोसँग ह्यान्डल गर्दैन। तर यो जान्नको लागि प्रत्येक गो प्रोग्रामरको लागि बिल्कुल उपयोगी छ।

मैले तिमीलाई भन्न चाहेको यति मात्र हो। धन्यवाद!

स्रोत: www.habr.com