लॉक-फ्री डेटा स्ट्रक्चर्स। बाहर से: libcds का एक परिचय

इस लेख में, मैं libcds डेटा संरचनाओं के लॉक-फ्री लाइब्रेरी का उपयोग करने का एक संक्षिप्त विवरण देता हूं। मैं यहाँ कार्यान्वयन में नहीं जाऊँगा, यह बस बाहर से एक नज़र है, पुस्तकालय उपयोगकर्ता की तरफ से एक नज़र है।

कई प्रसिद्ध डेटा संरचनाओं पर libcds लाइब्रेरी का अपना दृष्टिकोण है। यह लक्ष्य क्षेत्र द्वारा आंशिक रूप से समझाया गया है - लॉक-मुक्त डेटा संरचनाएं प्रदान की गई विधियों के सेट के मामले में न्यूनतम हैं - आंशिक रूप से मानक एसटीएल पुस्तकालय की सीमाओं और समाधानों से परे जाने की इच्छा से। इसका क्या हुआ यह उपयोगकर्ताओं को तय करने के लिए करना है।

कौन परवाह करता है - बिल्ली में आपका स्वागत है

Libcds लॉक-फ्री डेटा संरचनाओं के लिए C ++ लाइब्रेरी ऑफ लॉक-फ्री डेटा स्ट्रक्चर और सुरक्षित मेमोरी रिक्लेमेशन (SMR) मेथड है। यह लगभग हेडर-केवल है - सभी डेटा संरचनाएं हेडर .h फ़ाइलों में परिभाषित की जाती हैं, और केवल कोर एसएमआर एल्गोरिदम के कार्यान्वयन को एक छोटे गतिशील पुस्तकालय में स्थानांतरित किया जाता है।

एक नज़र में एस.एम.आर.

लॉक-फ्री डेटा संरचना विकसित करते समय शायद सबसे पतला बिंदु यह निर्धारित करना है कि आप किस समय किसी कंटेनर तत्व को सुरक्षित रूप से हटा सकते हैं। एक तत्व को निकालना हमेशा एक दो-चरण ऑपरेशन होता है: सबसे पहले, हम कंटेनर से तत्व को बाहर करते हैं, फिर हम तत्व के लिए आवंटित मेमोरी को हटाते हैं (डीलॉक करते हैं)। लॉक-फ्री दृष्टिकोण के साथ, दूसरे चरण - भौतिक विलोपन - की आवश्यकता है कि पूरी निश्चितता है कि कोई भी (समानांतर धागे में से कोई भी) लिंक, वैश्विक या स्थानीय नहीं है, हटाए गए आइटम के लिए।
सुरक्षित हटाने के लिए, एसएमआर एल्गोरिदम जिम्मेदार हैं, जिन्हें विशेष कचरा संग्राहक (जीसी) माना जा सकता है। इस लेख में मैं एक विशेष SMR एल्गोरिथ्म के कार्यान्वयन के आंतरिक विवरणों पर ध्यान केंद्रित नहीं करूंगा, मैं केवल एक सामान्य विवरण दूंगा, जो कि libcds के साथ काम करना शुरू करने के लिए पर्याप्त है। मुझे भविष्य के लेखों में सभी एल्गोरिदम पर विस्तार से चर्चा करने की उम्मीद है।

निम्नलिखित SMR एल्गोरिदम libcds में कार्यान्वित किए जाते हैं:

• हैज़र्ड पॉइंटर संभवतः एसएमआर एल्गोरिदम का पहला और सबसे प्रसिद्ध है। 2002 में माइकल द्वारा आविष्कार किया गया (यह अंतिम नाम है) [Mic02, Mic03, Mic04]। यह सापेक्ष सादगी और अच्छी गति से अलग है, यह कंटेनर तत्वों के लिए स्थानीय लिंक के "संरक्षण" के लिए है। नुकसान - एक साथ चलने वाले थ्रेड्स की अधिकतम संख्या के संकेत की आवश्यकता होती है। हैडर फ़ाइल <cds/gc/hp.h> , वर्ग cds::gc::HP
• पास-द-बक - वैचारिक रूप से हेज़र्ड पॉइंटर के समान है, लेकिन थ्रेड्स की संख्या पर निर्भर नहीं करता है। 2002 में हेरलहि, वी। लुचांग्को और एम। मोइर द्वारा निर्देशित [Her02, Her05]। थ्रेड्स की संख्या की स्वतंत्रता के कारण, यह हेज़र्ड पॉइंटर की तुलना में थोड़ा भारी है। हैडर फ़ाइल <cds/gc/ptb.h> , वर्ग cds::gc::PTB
• हेजर्ड पॉइंटर विथ रेफरेंस काउंटिंग हैज़र्ड पॉइंटर एल्गोरिथम का एक रूपांतर है, जो कि Håkan Sundell - Gidenstam et al। [Gid05, Gid06] के नेतृत्व में स्वीडिश स्कूल के प्रतिनिधियों द्वारा प्रस्तावित है। हैज़र्ड पॉइंटर की तरह, यह थ्रेड्स की संख्या पर निर्भर करता है। एक विशिष्ट विशेषता यह है कि यह कंटेनर तत्वों के वैश्विक संदर्भों की रक्षा कर सकता है, अर्थात, इसे लागू किया जा सकता है। खराब प्रदर्शन और दुर्लभ चमक के कारण उपयोग के लिए अनुशंसित नहीं (मैं इसे अंत तक डिबग नहीं कर सकता)। हेडर फ़ाइल <cds/gc/hrc.h> , वर्ग cds::gc::HRC
• आरसीयू (रीड-कॉपी अपडेट) - उपरोक्त के विपरीत, यह एल्गोरिथ्म सिंक्रोनाइज़ेशन एल्गोरिदम को संदर्भित करता है, अर्थात, यह तत्वों को हटाते समय थ्रेड्स के निष्पादन को निलंबित करता है, लेकिन अन्य ऑपरेशनों को समानांतर - पेस्ट, खोज में निष्पादित करने की अनुमति देता है - इसलिए यह दुर्लभ विलोपन के साथ डेटा संरचनाओं के लिए अच्छा है, नक्शा टाइप करें, सेट करें। पॉल मैककेनी द्वारा प्रस्तावित और लिनक्स कर्नेल में सक्रिय रूप से उपयोग किया जाता है; मूल RCU केवल OS के कर्नेल में लागू किया जा सकता है, लेकिन 2009 में Desnoyers ने आवेदन के लिए RCU (उपयोगकर्ता-स्पेस RCU, URCU) [Des09, Des11] का एक संस्करण प्रस्तावित किया, जो कि परिवादों में लागू किया गया है। पुस्तकालय URCU के पांच कार्यान्वयन प्रदान करता है, सबसे प्रभावी URCU है। हेडर फ़ाइल <cds/urcu/general_buffered.h> , वर्ग cds::urcu::gc< cds::urcu::general_buffered<> > । Libcds में, URCU केवल मानचित्र और सेट पर लागू होता है

सभी एसएमआर एल्गोरिदम को जीसी का प्रतिनिधित्व करने वाली एकल वस्तु की आवश्यकता होती है, अर्थात जीसी एक सिंगलटन है। गतिशील पुस्तकालय - libcds कोर - में मूल SMR एल्गोरिदम का कार्यान्वयन है।

एक नियम के रूप में, आपके एप्लिकेशन को केवल एक एसएमआर एल्गोरिथ्म का उपयोग करना चाहिए (हालांकि libcds आपको कई अलग-अलग जीसी एल्गोरिदम का उपयोग करने की अनुमति देता है - यह है कि सभी परीक्षण कैसे बनाए जाते हैं? लेकिन आप एक ही जीसी की दो वस्तुओं का उपयोग नहीं कर सकते हैं)। इसलिए, पहली बात यह है कि एसएमआर एल्गोरिदम चुनना है। Libcds में डेटा संरचनाओं के अधिकांश वर्गों में जीसी उनके पहले टेम्पलेट तर्क, स्मृति प्रबंधन एल्गोरिथ्म के रूप में है। इसके अलावा, प्रत्येक GC वर्ग में कंटेनर वर्ग के टेम्पलेट का अपना विशेषज्ञता है, इसलिए विभिन्न GCs के लिए, एक नियम के रूप में, आपको कंटेनर वर्ग के विभिन्न हेडर फ़ाइलों को शामिल (शामिल) करना चाहिए।

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

परिवादों का प्रारंभ

पुस्तकालय को आरम्भ करना एक जीसी वस्तु घोषित करना है। यह ऑब्जेक्ट आपके प्रोग्राम में केवल एक होना चाहिए। एक जीसी ऑब्जेक्ट बस एक वस्तु-उन्मुख ऐड-ऑन है जो एसएमआर एल्गोरिथ्म के आंतरिक कार्यान्वयन पर है। एक नियम के रूप में, आपके कार्यक्रम को जीसी-ऑब्जेक्ट के तरीकों तक पहुंचने की आवश्यकता नहीं है, - जीसी के साथ सभी इंटरैक्शन लॉक-फ्री डेटा संरचना के अंदर छिपा हुआ है, - इसलिए, जीसी-ऑब्जेक्ट स्थानीय हो सकता है।
Libcds में, सभी अलग-अलग प्रकार के GC - cds::gc::HP , cds::gc::PTB , cds::urcu::gc< cds::urcu::general_buffered<> > , इत्यादि - समान रूप से आरंभीकृत होते हैं। किसी विशेष GC के मापदंडों को निर्दिष्ट करने के लिए विभिन्न तर्क हो सकते हैं। जीसी कंस्ट्रक्टर्स के सभी तर्कों में डिफ़ॉल्ट मान हैं; इस परिचयात्मक लेख में, मैं रचनाकारों को बिना किसी तर्क के, डिफ़ॉल्ट मानों पर भरोसा करने वाला कहूंगा।

हैज़र्ड पॉइंटर मेमोरी मैनेजमेंट एल्गोरिथ्म के लिए इनिशियलाइज़ेशन कोड इस तरह दिखता है:

 #include <cds/init.h> //cds::Initialize  cds::Terminate #include <cds/gc/hp.h> //cds::gc::HP (Hazard Pointer) int main(int argc, char** argv) { //  libcds cds::Initialize() ; { //  Hazard Pointer  cds::gc::HP hpGC ; //  main thread  lock-free  // main thread    //   libcds cds::threading::Manager::attachThread() ; // , libcds    //     ... } //  libcds cds::Terminate() ; } 

सीडीएस cds::Initialize() फ़ंक्शन कुछ वैश्विक आंतरिक libcds डेटा को आरंभ करता है और सिस्टम टोपोलॉजी को निर्धारित करता है। इसके बाद जीसी-ऑब्जेक्ट का निर्माण होता है, इस उदाहरण में - हैज़र्ड पॉइंटर, क्लास cds::gc::HP , ऑब्जेक्ट को डिफॉल्ट तर्कों के साथ बनाया गया है।
main के अंत में, cds::Terminate कॉल करें cds::Terminate लाइब्रेरी टर्मिनेटर फ़ंक्शन को समाप्त करें, जो आंतरिक संरचनाओं को मुक्त करेगा।

धागा आरंभीकरण

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

Libcds से एक कंटेनर के साथ काम करने वाले प्रत्येक धागे को निम्नानुसार आरंभीकृत किया जाना चाहिए:

 // cds::threading::Manager #include <cds/threading/model.h> int myThreadEntryPoint(void *) { //     libcds cds::threading::Manager::attachThread() ; //        // lock-free  libcds ... //    libcds cds::threading::Manager::detachThread() ; return 0; } 

cds::threading::Manager वर्ग आंतरिक प्रवाह नियंत्रण बुनियादी ढांचे के लिए एक एडेप्टर वर्ग है। आपको इसे केवल libcds अवसंरचना के लिए एक धारा को जोड़ने / डिस्कनेक्ट करने की आवश्यकता हो सकती है।
उपरोक्त थ्रेड आरंभीकरण कोड अपवादों के संदर्भ में सुरक्षित नहीं है। एक अधिक सही दृष्टिकोण एक ऐसी वस्तु का उपयोग करना है जिसका निर्माता स्ट्रीम को बुनियादी ढांचे में जोड़ता है, और विध्वंसक इसे काट देता है। इसके लिए, प्रत्येक GC वर्ग में एक आंतरिक thread_gc वर्ग होता है। इसके साथ, धारा का आरंभ इस तरह दिखता है:

 #include <cds/gc/hp.h> int myThreadEntryPoint(void *) { //     libcds cds::gc::HP::thread_gc threadGC ; //        // lock-free  libcds ... return 0; } 

कंटेनर

पुस्तकालय को शुरू करने के बाद, आप लॉक-फ्री डेटा संरचनाओं का उपयोग कर सकते हैं। Libcds में, कंटेनरों को दो बड़े वर्गों में विभाजित किया जाता है - नियमित और असामान्य घुसपैठ।
नियमित एसटीएल-शैली के कंटेनर होते हैं, वे डेटा की एक प्रति संग्रहीत करते हैं। ऐसे सभी कंटेनरों को cds::container में घोषित किया जाता है cds::container नेमस्पेस।
घुसपैठ करने वाले कंटेनर वास्तविक डेटा संग्रहीत करते हैं, न कि उनकी प्रतियां। विचार को बढ़ावा से लिया गया है :: घुसपैठ । घुसपैठ करने वाले कंटेनरों का लाभ यह है कि आपको डेटा की एक प्रति बनाने के लिए एक आवंटनकर्ता को कॉल करने की आवश्यकता नहीं है। यह माना जाता है, और बिना कारण के नहीं, कि एक मानक आवंटनकर्ता के उपयोग से लॉक-फ्री के विचार को नकार दिया जाता है, क्योंकि आवंटनकर्ता में स्वयं सिंक्रनाइज़ेशन प्राइमेटिव होते हैं। सामान्य स्थिति में, यह सही है, लेकिन आधुनिक उन्नत आबंटक इसके कारण आंतरिक सिंक्रनाइज़ेशन को समाप्त करके मेमोरी आवंटन का अनुकूलन कर सकते हैं, उदाहरण के लिए, प्रत्येक थ्रेड के लिए मेमोरी पूल की उपस्थिति।
इस लेख में मैं घुसपैठ करने वाले कंटेनरों पर विस्तार से ध्यान नहीं दूंगा - उन्हें मेमोरी से मुक्त करने के लिए विशेष तकनीकों की आवश्यकता होती है जब एक तत्व को कंटेनर से बाहर रखा जाता है, यह एक और चर्चा का विषय है। यहां मैं सिर्फ यह ध्यान देता हूं कि साधारण कंटेनरों के अधिकांश वर्ग घुसपैठ पर आधारित हैं, अर्थात्, एक नियम के रूप में, सभी दिलचस्प लॉक-फ्री कोड घुसपैठ वाले कंटेनर की कक्षा में हैं। घुसपैठ के कंटेनर cds::intrusive में घोषित किए जाते हैं cds::intrusive ।

Libcds में सभी डेटा संरचनाएं एक समान टेम्पलेट इंटरफ़ेस के साथ टेम्पलेट कक्षाएं हैं। दो प्रकार के टेम्पलेट इंटरफेस को प्रतिष्ठित किया जा सकता है:

• वैरेडिक टेम्पलेट पर आधारित है
• लक्षणों के आधार पर

वैरिएडिक टेम्प्लेट-आधारित विज्ञापन सरल कंटेनरों के लिए उपयोग किए जाते हैं - ढेर और कतारें। सामान्य पैटर्न निम्नानुसार है:

 template <typename GC, typename T, typename… Options> class queue { … }; 

ऐसे कंपाइलर जो वैरेडिक टेम्प्लेट का समर्थन नहीं करते हैं, एमुलेशन का उपयोग किया जाता है।
कंटेनर वर्ग के अंदर, Options एक Traits संरचना में पैक किए जाते हैं।

वैरिएडिक टेम्प्लेट दृष्टिकोण जटिल विरासत के लिए बहुत सुविधाजनक नहीं था, इसलिए लक्षण घोषणाओं का उपयोग अधिक जटिल कंटेनरों जैसे set , map , आदि के लिए किया जाता है।

 template <typename GC, typename T, typename Traits> class set { … }; 

ऐसे प्रत्येक वर्ग के लिए, make_traits मेटाफ़ंक्शन होता है जो वैरिएड टेम्प्लेट को लक्षणों में परिवर्तित करता है:

 template <typename… Options> struct make_traits { typedef typename pack<Options…>::type type ; }; 

make_traits का उपयोग करते make_traits कंटेनर ऑब्जेक्ट make_traits घोषणा फार्म लेता है:

 struct Foo { … }; cds::container::SkipListSet< cds::gc::HP, Foo, typename cds::container::skip_list::make_traits< Opt1, Opt2, Opt3 >::type > theSkipListSet ; 

इस तरह की घोषणा, ज़ाहिर है, शांत दिखती है, लेकिन यह डिबगिंग के समय समस्याएं पैदा कर सकती है - वर्ग का नाम कई दसियों लाइनें ले सकता है। डिबगिंग के लिए लक्षण अधिक कॉम्पैक्ट हैं:

 struct Foo { … }; struct skipListSetTraits: public cds::container::skip_list::make_traits< Opt1, Opt2, Opt3 >::type {}; cds::container::SkipListSet< cds::gc::HP, Foo, skipListSetTraits > theSkipListSet ; 

डेटा संरचना वर्ग के लिए टेम्पलेट तर्क हैं:

• GC - एसएमआर एल्गोरिथ्म का इस्तेमाल किया
• T - कंटेनर में संग्रहीत डेटा का प्रकार
• Options… या Traits - कंटेनर के विकल्प (नीतियाँ, रणनीतियाँ)

विकल्पों पर अलग से चर्चा की जानी चाहिए।

विकल्प

प्रत्येक कंटेनर वर्ग, डेटा प्रकार और SMR एल्गोरिथ्म के अलावा, इसमें या उस व्यवहार को निर्दिष्ट करने वाली विविध सेटिंग्स हो सकती हैं। उदाहरण के लिए, ऑर्डर किए गए कंटेनरों (मानचित्र, सेट) के लिए, आपको तत्वों की तुलना करने के लिए द्विआधारी विधेय को निर्दिष्ट करने की आवश्यकता है std::less<T> । या समानांतर काम (बैक-ऑफ रणनीति) का पता लगाने पर कार्रवाई की इस या उस रणनीति को निर्धारित करने के लिए। या कंटेनर तत्वों को बनाने के लिए उपयोग किए जाने वाले आवंटनकर्ता को स्थापित करें।
प्रत्येक कंटेनर वर्ग में कई (एक दर्जन तक) होते हैं जैसे, एक नियम के रूप में, वैकल्पिक सेटिंग्स, जिसे मैं विकल्प कहता हूं। एसटीएल में उपयोग किया जाने वाला दृष्टिकोण जब प्रत्येक सेटिंग एक क्लास टेम्पलेट का टेम्पलेट तर्क होता है, तो मुझे वास्तव में पसंद नहीं है: डिफ़ॉल्ट मान वाले ऐसे स्थिति-निर्भर तर्क वर्ग के उपयोग को जटिल करते हैं। यदि कक्षा में डिफ़ॉल्ट मानों के साथ 10 टेम्पलेट तर्क हैं, तो आठवें तर्क को बदलने के लिए, हमें आठवें से पहले के सभी सात तर्कों के डिफ़ॉल्ट मूल्यों को निर्दिष्ट करने की आवश्यकता है। यह बहुत असुविधाजनक है। इसलिए, libcds में मैं एक स्थिति-स्वतंत्र दृष्टिकोण का उपयोग करता हूं।
इस दृष्टिकोण के साथ, प्रत्येक विकल्प का अपना प्रकार है; उदाहरण के लिए, "आवंटनकर्ता" विकल्प में निम्नलिखित घोषणा है:

 template <typename Alloc> struct allocator { template <typename Base> struct pack: public Base { typedef Alloc allocator ; }; }; 

यहां, Alloc टेम्प्लेट तर्क विशिष्ट Alloc वर्ग है, और allocator संरचना स्वयं विकल्प का नाम है। यहां बताया गया है कि असाइनमेंट कार्य विकल्प के माध्यम से कैसा दिखता है:

 cds::opt::allocator< std::allocator<int> > 

इन विकल्प घोषणाओं का उपयोग करना, एक मेटाफ़ंक्शन का निर्माण करना काफी आसान है जो विकल्पों में से एक traits संरचना एकत्र करता है। इस प्रक्रिया को पैकिंग कहा जाता है।
Libcds में दो प्रकार के विकल्प हैं:

• सामान्य विकल्प - कई कंटेनरों पर लागू होते हैं। ऐसे विकल्पों की घोषणा cds::opt नाम स्थान का cds::opt , और मान्य विकल्प मानों के नामस्थान cds::opt::v
• विशेष विकल्प - केवल एक विशिष्ट कंटेनर वर्ग पर लागू होते हैं। उनकी घोषणाएं एक विशिष्ट कंटेनर के नाम स्थान में स्थित हैं, उदाहरण के लिए, cds::container::skip_list

प्रत्येक कंटेनर वर्ग के विवरण में वैध विकल्पों की एक सूची है।

तुलना भविष्यवाणी करती है

कई कंटेनरों में जैसे नक्शा, सेट, तत्वों की तुलना के लिए एक विधेय निर्दिष्ट किया जाना चाहिए। STL में, इसके लिए std::less<T> का उपयोग किया जाता है, जो केवल T तत्वों की तुलना कर सकते हैं T लेकिन बहुत बार यह असुविधाजनक और महंगा है। उदाहरण के लिए, std::string प्रकार की तुलना char const * मान के साथ की जा सकती है, और ऐसी तुलना के लिए एक अस्थायी std::string ऑब्जेक्ट बनाने की कोई आवश्यकता नहीं है। सेट कंटेनरों के लिए, T स्टोर किए गए टाइप T में अक्सर तुलना के लिए आवश्यक फ़ील्ड होते हैं, और "लोड" स्वयं डेटा होता है, जो किसी भी तरह से खोज में भाग नहीं लेता है।
कहा कि सभी के साथ, libcds उन्नत विधेय का उपयोग करता है जो विभिन्न प्रकारों के मूल्यों की तुलना कर सकता है। विधेय विकल्प द्वारा निर्दिष्ट किए जाते हैं। इसके अलावा, आप विस्तारित कम के रूप में विस्तारित कम (विकल्प cds::opt::less< typename Less > ) या विस्तारित तुलना (विकल्प cds::opt::compare< typename Comparator > ) का उपयोग कर सकते हैं। रिटर्न की तुलना पूर्णांक मान से करें:

• cmp(a, b) < 0 यदि a < b
• cmp(a, b) == 0 अगर a == b
• cmp(a, b) > 0 अगर a > b

विधि समारोह std::string::compare भी काम करती है।
विस्तारित लेखन भविष्यवाणी करता है ( cds::opt::less< typename Less > लिए Less cds::opt::less< typename Less > विकल्प या cds::opt::compare< typename Comparator > लिए cds::opt::compare< typename Comparator > विकल्प) आप पर निर्भर है। यहाँ Comparator स्ट्रिंग तुलना के लिए कैसा दिख सकता है:

 struct string_cmp { int operator()(std::string const& s1, std::string const& s2) const { return s1.compare( s2 ); } int operator()(std::string const& s1, char const* s2) const { return s1.compare( s2 ); } int operator()(char const* s1, std::string const& s2) const { return –s2.compare( s1 ); } }; 

allocators

cds::container से कंटेनर cds::container नेमस्पेस डेटा की प्रतियों को स्टोर करते हैं, इसलिए उनके लिए विकल्पों में से एक cds::opt::allocator - डेटा के लिए मेमोरी आवंटित करने के लिए एक आवंटनकर्ता। कुछ कंटेनरों में दो आवंटन विकल्प होते हैं - एक डेटा वितरण के लिए ( cds::opt::node_allocator ), दूसरा ( cds::opt::allocator ) - सहायक कंटेनर संरचनाओं के लिए मेमोरी आवंटित करने के लिए। डिफ़ॉल्ट रूप से, std::allocator<int> एक std::allocator<int> रूप std::allocator<int> उपयोग किया जाता है। यदि आप अपने आवंटनकर्ता का उपयोग करना चाहते हैं, तो इसका इंटरफ़ेस std::allocator के समान होना चाहिए।

पुस्तकालय आवंटनकर्ताओं के दो गुणों पर बहुत निर्भर करता है:

• प्रत्येक आबंटक के पास मेटाफ़ंक्शन template <typename Other> struct rebind , जो आपको एक अलग प्रकार के Other लिए एलोकेटर के पुनर्निर्माण की अनुमति देता है। जैसा कि मैंने पहले ही कहा था, डिफॉल्ट std::allocator<int> , - कंटेनर रिबेट मेटाफ़ंक्शन के माध्यम से int को आवश्यक प्रकार में बदल देता है
• एक वैश्विक वस्तु है। यह आवश्यकता इस तथ्य से उपजी है कि लॉक-फ्री कंटेनर तत्व के भौतिक निष्कासन में देरी हो रही है और कंटेनर ऑब्जेक्ट के विनाश के बाद हो सकता है। इसलिए, एसटीएल के विपरीत, libcds कंटेनर एक एलोकेटर ऑब्जेक्ट के संदर्भ को कभी स्टोर नहीं करते हैं और एक एलोकेटर ऑब्जेक्ट को निर्दिष्ट करने के लिए तरीके नहीं हैं। यदि आपको कंटेनर विधि के अंदर मेमोरी आवंटित करने की आवश्यकता है, तो आवंटनकर्ता को एक अस्थायी ऑब्जेक्ट के माध्यम से बुलाया जाता है: allocator_type().allocate( 1 ) । इसी तरह, मेमोरी को allocator_type().deallocate( p ) कहकर मुक्त किया जाता है। यह एक बार फिर ध्यान देने योग्य है कि रिलीज में देरी हो रही है और पहले से ही हो सकती है जब कंटेनर ऑब्जेक्ट खुद नहीं रह गया है, और इसे एसएमआर एल्गोरिथ्म से कहा जाता है

संक्षिप्त विवरण

समर्थित संकलक:

• जीसीसी 4.3 और उच्चतर
• MS Visual C ++ 2008 और उच्चतर
• Clang 3.0 और उससे ऊपर (GCC मानक लाइब्रेरी libstdc ++ के साथ)

समर्थित ऑपरेटिंग सिस्टम और प्रोसेसर आर्किटेक्चर:

• विंडोज x86, amd64
• लिनक्स x86, amd64, इंटेल इटेनियम, स्पार्क
• सोलारिस स्पार्क
• एचपी-यूएक्स इंटेल इटेनियम

अन्य ऑपरेटिंग सिस्टम या प्रोसेसर आर्किटेक्चर के लिए समर्थन संभव है, लेकिन तुच्छ नहीं, खासकर यदि लक्ष्य संकलक C ++ 11 atomic समर्थन नहीं करता है।

निष्कर्ष

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

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

यदि आप अच्छी सलाह चाहते हैं, तो यह है: साझा डेटा का उपयोग न करने का प्रयास करें । मैंने ऐसी सलाह से अमेरिका की खोज नहीं की, लेकिन रोजमर्रा की जिंदगी में इसका पालन करना मुश्किल हो सकता है।