क्या यह सी ++

Question

में लॉक फ्री मैप को लागू करने के लिए संभव है। हम नेटवर्क अनुप्रयोग आधारित सी/एस विकसित कर रहे हैं, हम पाते हैं कि std :: map में बहुत सारे ताले जोड़े गए हैं जो सर्वर का प्रदर्शन खराब हो गया है।

मुझे आश्चर्य है कि लॉक-फ्री मानचित्र को लागू करना संभव है, यदि हां, तो कैसे? क्या वहां कोई ओपन सोर्स कोड है?

संपादित करें: असल में हम std :: मानचित्र का उपयोग सॉकेट जानकारी स्टोर करने के लिए, हम सॉकेट फ़ाइल वर्णन के आधार पर कैप्सूलीकरण था इस तरह के आईपी पता, पोर्ट, सॉकेट प्रकार, TCP या UDP, आदि के रूप में कुछ अन्य आवश्यक जानकारी शामिल करने के लिए ।

सारांश करने के लिए

, हम एक वैश्विक मानचित्र कहते हैं कि यह

map<int fileDescriptor, socketInfor*> SocketsMap, 

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

समवर्ती स्तर की समस्या से बचने के लिए, हमारे पास दो समाधान हैं: 1. प्रत्येक सॉकेट को * अलग से स्टोर करें 2. किसी प्रकार का लॉक-फ्री मानचित्र का उपयोग करें।

मैं, ताला मुक्त नक्शे के कुछ प्रकार प्राप्त करना चाहते हैं, क्योंकि कोड इस समाधान के अनुसार आवश्यक बदलावों समाधान की तुलना में काफी कम कर रहे हैं 1.

Answer 1

असल में वहाँ एक रास्ता है, हालांकि मैं इसे अपने आप लागू नहीं किया है प्रतिष्ठित सी ++ विशेषज्ञ आंद्रेई अलेक्जेंड्रेसकू से lock free map using hazard pointers पर एक पेपर है।

Answer 2

आप optimistic design या transactional memory का उपयोग कर मानचित्र को लागू कर सकते हैं।

यह दृष्टिकोण विशेष रूप से प्रभावी होता है यदि दो परिचालनों का एक साथ नक्शा को संबोधित करने का मौका होता है और एक इसकी संरचना बदल रहा है अपेक्षाकृत छोटा है - और आप हर बार लॉकिंग के ऊपरी हिस्से को नहीं चाहते हैं।

हालांकि, समय-समय पर टक्कर होगी, और आपको इसे किसी भी तरह से परिणाम देना होगा (आमतौर पर अंतिम स्थिर स्थिति में वापस रोल करके और संचालन को पुनः प्रयास करके)।

अपने हार्डवेयर समर्थन काफी अच्छा परमाणु आपरेशन है - यह आसानी से Compare And Swap (CAS) के साथ किया जा सकता है - जहां संदर्भ अकेले बदल (और जब भी तुम नक्शा बदलने के लिए, आप नक्शे की एक प्रति पर काम करते हैं, और मूल नहीं है, और जब आप प्रतिबद्ध करते हैं तो इसे प्राथमिक के रूप में सेट करें)।

Answer 3

हैश मैप उपयुक्त होगा? Intel Threading Building Blocks पर एक नज़र डालें, उनके पास एक दिलचस्प समवर्ती नक्शा है। मुझे यकीन नहीं है कि यह लॉक-फ्री है, लेकिन उम्मीद है कि आप अच्छे मल्टीथ्रेडिंग प्रदर्शन में दिलचस्पी रखते हैं, खासकर लॉक-फ़िरनेस में नहीं।इसके अलावा, आप lib CityHash जांच कर सकते हैं

संपादित करें:

असल TBB के हैश नक्शा ताला मुक्त नहीं है

Answer 4

मैं हैरान कोई भी यह उल्लेख किया गया है, लेकिन क्लिक करें क्लिफ लागू किया गया है एक प्रतीक्षा मुक्त hashmap in Java, जो मेरा मानना ​​है कि, सी ++ में पोर्ट किया जा सकता है

Answer 5

आप सी ++ 11 का उपयोग करते हैं, तो आप facebook/folly

Answer 6

की AtomicHashMap पर एक नज़र हाँ, मैं लागू कर दिया है हो सकता है एक Lock-Free Unordered Map (docs) "स्प्लिट-ऑर्डरर्ड लिस्ट" अवधारणा का उपयोग कर सी ++ में। यह एक ऑटो-विस्तारित कंटेनर है और एबीए मुद्दों के बिना 64-बिट सीएएस पर लाखों तत्वों का समर्थन करता है। प्रदर्शन के अनुसार, यह beast है (पृष्ठ 5 देखें)। लाखों यादृच्छिक ओप के साथ यह extensively tested रहा है।