JeMalloc के अंदर। कोर डेटा स्ट्रक्चर्स: पेयरिंग हीप और बिटमैप ट्री

एलोकेटर की थीम अक्सर इंटरनेट पर पॉप अप होती है: वास्तव में, एक एलोकेटर एक तरह की आधारशिला है, जो किसी भी एप्लिकेशन का दिल है। इस पोस्ट की श्रृंखला में मैं एक बहुत ही मनोरंजक और प्रख्यात आवंटनकर्ता के बारे में विस्तार से बात करना चाहता हूं - JeMalloc , फेसबुक द्वारा समर्थित और विकसित, उदाहरण के लिए, बायोनिक [एंड्रॉइड] लिबास सी में।

नेटवर्क पर, मुझे कोई भी विवरण नहीं मिला जो इस आवंटनकर्ता की आत्मा को पूरी तरह से प्रकट करता है, जिसने अंततः किसी विशेष समस्या को हल करने में JeMalloc की प्रयोज्यता के बारे में कोई निष्कर्ष निकालने की असंभवता को प्रभावित किया। बहुत सारी सामग्री निकली और यह पढ़ने के लिए कि वह थका नहीं था, मैं मूल बातों के साथ शुरू करने का प्रस्ताव करता हूं: मूल डेटा संरचनाएं जिसका उपयोग JeMalloc में किया जाता है।

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

बिटमैप_ एक पेड़ जैसी डेटा संरचना है जो आपको निम्नलिखित की अनुमति देती है:

• किसी दिए गए अनुक्रम में पहले सेट / परेशान बिट को जल्दी से खोजें।
• बिट के दिए गए अनुक्रम में सूचकांक I के साथ बिट का मूल्य बदलें और प्राप्त करें।
• पेड़ n बिट्स के अनुक्रम के अनुसार बनाया गया है और इसमें निम्नलिखित गुण हैं:
• पेड़ की आधार इकाई नोड है, और नोड की आधार इकाई बिट है। प्रत्येक नोड में बिल्कुल कश्मीर बिट्स होते हैं। एक नोड की बिटनेस का चयन किया जाता है ताकि बिट्स की एक चयनित सीमा पर तार्किक संचालन की गणना किसी दिए गए कंप्यूटर पर जल्दी और कुशलता से की जाए। JeMalloc में, एक नोड का अहस्ताक्षरित लंबे प्रकार द्वारा प्रतिनिधित्व किया जाता है।
• पेड़ की ऊंचाई को स्तरों में मापा जाता है और n बिट्स के अनुक्रम के लिए H = होता है $$$\ log_ {k} {n} log k (n)$स्तरों।
• पेड़ के प्रत्येक स्तर को एक अनुक्रम द्वारा दर्शाया गया है $$$countOfNodesOnLevel = पूर्णांकसील (\ frac {n} {{k} ^ {H - currentLevel + 1}})$नोड्स, जो के एक अनुक्रम के बराबर है $$$countOfBitsOnLevel = countOfNodesOnLevel * k$बिट।
• पेड़ के उच्चतम (मूल) स्तर में k बिट्स होते हैं, और सबसे कम - n बिट्स के।
• स्तर L का प्रत्येक बिट, L के स्तर के बच्चे के सभी बिट्स की स्थिति को निर्धारित करता है L - 1: यदि थोड़ा सा व्यस्त है, तो एक बच्चे के नोड के सभी बिट्स भी व्यस्त हैं, अन्यथा, एक बच्चे के नोड के बिट्स हो सकते हैं 'व्यस्त' और 'मुक्त' अवस्था।

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

एक उदाहरण के रूप में, 92 बिट्स और के = 32 मन का अनुक्रम लें। हम मानते हैं कि राज्य 'मुक्त' है - एक बिट द्वारा निरूपित, और राज्य 'व्यस्त' - शून्य। यह भी मान लें कि मूल बिट अनुक्रम में, इंडेक्स 1 के साथ बिट (शून्य से गिनती, आंकड़ा में दाएं से बाएं की ओर) व्यस्त अवस्था में सेट है। तो ऐसे बिट अनुक्रम के लिए बिटमैप_ नीचे की छवि की तरह दिखेगा:



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

यह मानकर कि बिटमैप_ को दो सरणियों (डेटा सरणी और डेटा सरणी में ट्री लेवल ऑफ़सेट्स की एक सरणी) द्वारा दर्शाया गया है, हम दिए गए बिटमैप_ टी में पहले कम से कम महत्वपूर्ण बिट के लिए खोज के संचालन का वर्णन करते हैं:

• रूट नोड से शुरू, हम नोड के पहले कम से कम महत्वपूर्ण बिट के लिए खोज ऑपरेशन करते हैं: इस समस्या को हल करने के लिए, आधुनिक प्रोसेसर विशेष निर्देश प्रदान करते हैं जो खोज समय को काफी कम कर सकते हैं। हम FirstSetedBit चर में पाया परिणाम बचाएंगे ।
• एल्गोरिथ्म के प्रत्येक पुनरावृत्ति पर, हम पाए गए बिट्स के पदों का योग बनाए रखेंगे: countOfSettedBits + = FirstSetedBit
• पिछले चरण के परिणाम का उपयोग करते हुए, हम नोड के पहले कम से कम महत्वपूर्ण इकाई के बच्चे के नोड पर जाते हैं और पिछले चरण को दोहराते हैं। संक्रमण निम्नलिखित सरल सूत्र के अनुसार किया जाता है: $$$currentNode = bitmapData [levelOffsetArray [currentLevel] + sumOfBits]$
• प्रक्रिया तब तक जारी रहती है जब तक कि पेड़ का निम्नतम स्तर नहीं पहुंच जाता। countOfSettedBits - इनपुट बिट अनुक्रम में वांछित बिट की संख्या।

पेयरिंग हीप एक ढेर जैसा पेड़ डेटा संरचना है जो आपको इसकी अनुमति देता है:

• कार्यान्वयन के आधार पर, O (1) की निरंतर समय जटिलता और O (लॉग एन) या O (1) की निरंतर लागत के साथ एक तत्व डालें।
• कम से कम निरंतर समय पर खोजें - O (1)
• निरंतर समय जटिलता के साथ दो जोड़ी ढेर को मिलाएं - O (1) और परिशोधन लागत O (लॉग एन) या O (1) - कार्यान्वयन के आधार पर
• O (N) में अस्थायी जटिलता अनुमान और O (लॉग एन) में अनुमानित जटिलता अनुमान के साथ एक मनमाना तत्व (विशेष रूप से, एक न्यूनतम एक) हटाएं

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



कंप्यूटर की मेमोरी में, पेयरिंग-हीप, एक नियम के रूप में, पूरी तरह से अलग तरीके से प्रस्तुत किया जाता है: ट्री नोड के प्रत्येक नोड में 3 पॉइंट होते हैं:

• वर्तमान नोड के सबसे बाईं ओर के बच्चे को इंगित करें
• नोड के बाएं भाई को इंगित करें
• नोड के दाहिने भाई को इंगित करें

यदि संकेतित नोड्स में से कोई भी गायब है, तो संबंधित नोड पॉइंटर को शून्य कर दिया गया है।
ऊपर चित्र में प्रस्तुत ढेर के लिए, हमें निम्नलिखित प्रतिनिधित्व मिलता है:



यहां, बाईं ओर के बच्चे के नोड के लिए सूचक को लाल बिंदीदार तीर द्वारा इंगित किया गया है, नोड के दाहिने भाई को सूचक नीला है, और बाएं भाई को सूचक ग्रे है। ठोस तीर एक पेड़ के समान रूप में पेयरिंग हीप प्रतिनिधित्व को दर्शाता है जो किसी व्यक्ति के लिए सामान्य है।

कृपया निम्नलिखित दो तथ्यों पर ध्यान दें:

• ढेर की जड़ में हमेशा दाएं और बाएं भाई नहीं होते हैं।
• यदि किसी भी नोड यू में बाएं-सबसे अधिक बच्चे के नोड के लिए एक शून्य-शून्य सूचक है, तो यह नोड यू के सभी बच्चे नोड्स की दोगुनी लिंक की गई सूची का 'हेड' होगा। इस सूची को सिबलिंगलिस्ट कहा जाता है।

अगला, हम मिन पेयरिंग-हीप में मुख्य संचालन के एल्गोरिथ्म को सूचीबद्ध करते हैं:

• जोड़ी को ढेर में डालें:
  
  बता दें कि एक रूट के साथ एक पेयरिंग हीप दिया जाता है और इसमें एक मान {R, V_1} , साथ ही एक नोड {U, V_2} दिया जाता है । फिर, जब एक दिए गए युग्मन ढेर में U नोड डालें:
  
  • यदि स्थिति V_2 <V_1 संतुष्ट है: U ढेर का नया रूट नोड बन जाता है, तो रूट R को उसके बाएं चाइल्ड नोड की स्थिति में 'क्राउडिंग आउट' कर दिया जाता है। उसी समय, नोड आर का दाहिना भाई इसका सबसे पुराना बाएं-सबसे नोड होता है, और नोड आर के बाएं-सबसे नोड के लिए सूचक शून्य हो जाता है।
  • अन्यथा: U, R की जड़ का बायाँ-सबसे अधिक बाल नोड बनता है, और इसका सबसे पुराना भाई R की जड़ का बायाँ-सबसे नोड है।
• दो जोड़ी ढेर में विलय:
  
  जड़ों और मानों के साथ दो जोड़ी युग्मन {R_1, V_1} , {R_2, V_2}, क्रमशः दिए जाएं। हम ऐसे ढेर को विलय करने के लिए एल्गोरिदम में से एक का वर्णन करते हैं, जिसके परिणामस्वरूप पैपिंग हीप:
  
  • जड़ में सबसे कम मूल्य के साथ ढेर चुनें। इसे {R_1, V_1} का एक गुच्छा बनाएं।
  • चयनित Heap से रूट R_1 को 'अलग करें': इसके लिए, हम बस इसके पॉइंटर को बायीं ओर के सबसे ज्यादा बच्चे के नोड पर रखते हैं।
  • रूट R_1 के सबसे बाएं चाइल्ड नोड के लिए नए पॉइंटर के साथ, रूट R_2 बनाएं। ध्यान दें कि अब से, R_2 रूट स्थिति खो देता है और परिणामस्वरूप ढेर में एक सामान्य नोड है।
  • हम नोड R_2 के दाहिने भाई को सेट करते हैं: नए मान के साथ हम पुराने बच्चे को रूट R_1 के सबसे निचले बच्चे नोड के लिए (शून्य से पहले) पॉइंटर बनाते हैं, और क्रमशः R_1 के लिए, बाएं भाई को पॉइंटर अपडेट करते हैं।

विशिष्ट उदाहरण का उपयोग करके मर्ज एल्गोरिथ्म पर विचार करें:



यहाँ, रूट '4' के साथ ढेर, '1' (1 <4) रूट के साथ ढेर में जुड़ जाता है, जो कि उसका सबसे बाईं ओर का नोड बन जाता है। नोड '4' के दाहिने भाई को पॉइंटर - अद्यतन किया जाता है, साथ ही नोड के बाएं भाई को पॉइंटर '8' कहा जाता है।

• रूट को निकालना (न्यूनतम मान के साथ नोड) जोड़ी का ढेर:
  
  एक जोड़ी ढेर से एक नोड को हटाने के लिए कई एल्गोरिदम हैं, ओ (लॉग इन) में एक amortized जटिलता अनुमान देने की गारंटी है। हम उनमें से एक का वर्णन करते हैं, जिसे मल्टीप्लास एल्गोरिथ्म कहा जाता है और जेमलॉक में उपयोग किया जाता है:
  
  
  • हम दिए गए हीप की जड़ को हटाते हैं, जिससे उसका केवल सबसे बाईं ओर का नोड होता है।
  • बाईं ओर का बच्चा नोड मूल नोड के सभी बच्चे नोड्स की एक दोहरी लिंक की गई सूची बनाता है, और हमारे मामले में, पहले हटाए गए रूट। हम लगातार इस सूची के अंत तक जाएंगे और नोड्स को स्वतंत्र पेयरिंग हीप की जड़ों के रूप में देखते हुए, सूची के वर्तमान तत्व को अगले के साथ विलय करने का कार्य करेंगे, जिसके परिणामस्वरूप पूर्व-तैयार फीफो कतार में परिणाम होगा।
  • अब जब FIFO कतार को आरंभ किया गया है, तो हम कतार के वर्तमान तत्व को अगले के साथ विलय करने की क्रिया को पूरा करते हुए इस पर पुनरावृत्ति करेंगे। विलय का परिणाम कतार के अंत में रखा गया है।
  • हम पिछले चरण को तब तक दोहराते हैं जब तक कि एक तत्व कतार में नहीं रहता: परिणामी पेयरिंग हीप।

ऊपर वर्णित प्रक्रिया का एक अच्छा उदाहरण:

• एक मनमाना गैर-रूट नोड निकालना Heap:
  
  हटाए गए नोड को मूल हीप के कुछ उपप्रकार के मूल के रूप में मानें। पहले, हम इस सबट्री की जड़ को हटाते हैं, पेयरिंग हीप की जड़ को हटाने के लिए पहले वर्णित एल्गोरिथ्म का पालन करते हैं, और फिर, परिणामी पेड़ को मूल के साथ विलय करने की प्रक्रिया करते हैं।
• न्यूनतम जोड़ी बनाना तत्व प्राप्त करना:
  
  बस ढेर जड़ का मान लौटाएं।

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

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

• पेयरिंग हीप में आलसी नोड प्रविष्टि:
  
  Pairing हीप { R_1 , V_1 } में निर्दिष्ट U नोड सम्मिलित करते समय, हम इसे सूची में डालते हैं - सूची के प्रमुख के बाद:

• दो जोड़ी ढेर के आलसी विलय:
  
  Lazy Merging दो जोड़ी जोड़ी, Lazy नोड सम्मिलन के समान, जहाँ सम्मिलित नोड ढेर में से एक का मूल (दोगुना जुड़ा हुआ auxList का सिर) होता है।
• आलसी न्यूनतम पेयरिंग हीप तत्व प्राप्त करना:
  
  न्यूनतम अनुरोध करते समय, हम ऑक्लिस्ट के माध्यम से स्वतंत्र पेयरिंग हीप की जड़ों की सूची में जाते हैं, इस सूची के तत्वों को मर्ज ऑपरेशन के साथ जोड़ते हैं, और परिणामी पिंगिंग हीप में से एक को न्यूनतम तत्व वाले रूट का मान लौटाते हैं।
• न्यूनतम युग्मन हीप तत्व का आलसी हटाना:
  
  जब पेयरिंग हीप द्वारा निर्दिष्ट न्यूनतम तत्व को हटाने के लिए कहा जाता है, तो सबसे पहले हम उस नोड को ढूंढते हैं जिसमें न्यूनतम तत्व होता है, और फिर इसे उस पेड़ से हटा दें जिसमें यह जड़ है, इसके उपप्रकार को मुख्य ढेर के औक्सलिस्ट में डालें।
• एक मनमाना गैर-रूट जोड़ी ढेर नोड का आलसी हटाने:
  
  अनियंत्रित नॉन-रूट पेयरिंग हाइप नोड को हटाते समय, नोड को हीप से निकाल दिया जाता है, और इसके चाइल्ड नोड्स को मुख्य हीप के ऑक्लिस्ट में डाला जाता है।

दरअसल, Lazy Pairing Heap के क्रियान्वयन का उपयोग, Pairing Heap में सम्मिलन और मनमाने ढंग से नोड्स को हटाने की लागत को कम करता है: O (log N) से O (1) तक।

यह सब, और नीचे आपको उपयोगी लिंक और संसाधनों की एक सूची मिलेगी:

[०] जेमलॉक गितूब पेज
[१] पेयरिंग हीप्स पर मूल लेख
[२] आलसी इम्प्लीमेंटेशन पेयरिंग हीप्स पर मूल लेख
[३] टेलीग्राम चैनल कोड ऑप्टिमाइज़ेशन के बारे में, C ++, Asm, 'लो लेवल' और इससे ज्यादा कुछ नहीं!

जारी रखने के लिए ...