गैर-कचरा एकत्रित संदर्भ में समरूपता के लिए अभी भी कार्यात्मक/अपरिवर्तनीय डेटा संरचनाएं उपयोगी हो सकती हैं?

अपरिवर्तनीय डेटा संरचनाओं के विक्रय बिंदुओं में से एक यह है कि वे स्वचालित रूप से समानांतर होते हैं। यदि कोई उत्परिवर्तन नहीं चल रहा है, तो किसी कार्यात्मक डेटा संरचना के संदर्भ किसी भी लॉकिंग के बिना धागे के बीच पारित किए जा सकते हैं।गैर-कचरा एकत्रित संदर्भ में समरूपता के लिए अभी भी कार्यात्मक/अपरिवर्तनीय डेटा संरचनाएं उपयोगी हो सकती हैं?

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

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

क्या सी ++ (और अन्य गैर-कचरा एकत्रित वातावरण) में समवर्ती अपरिवर्तनीय डेटा संरचनाएं काम करने का कोई तरीका है?

स्रोत

2011-08-31 Rob Lachlan

मैं इसमें कोई विशेषज्ञ नहीं हूं, लेकिन आप प्रति-थ्रेड संदर्भ संख्या संग्रहीत कर सकते हैं, और केवल उन पर एक ताला लगा सकते हैं ताकि सभी धागे नोड पर शून्य संदर्भ तक पहुंच गए हों। लेकिन मुझे यकीन है कि इस से अधिक सुरुचिपूर्ण समाधान हैं या शायद सामान्य रूप से संदर्भ गणना। – sinelaw

यहाँ सी के लिए एक लोकप्रिय अपरिवर्तनीय डेटा संरचना ++ http://www.sgi.com/tech/stl/Rope.html – ybungalobill

आप 'shared_ptr' के कार्यान्वयन पर दिखाई दे सकता है, कि ठीक उसी मुद्दा एक कुशल thread- की आवश्यकता होगी, के साथ सामना कर रहा है सुरक्षित संदर्भ गिनती। –

ताला मुक्त संदर्भ गिनती एल्गोरिदम, देखते हैं, जैसे हैं Lock-Free Reference Counting, Atomic Reference Counting Pointers।

यह भी ध्यान दें कि सी ++ 0x (जो शायद जल्द ही सी ++ 11 बन जाएगा) परमाणु पूर्णांक प्रकार शामिल हैं, खासकर इस तरह के उद्देश्यों के लिए।

स्रोत

2011-08-31 06:56:50

मुझे यकीन है कि मैं यहां नहीं कर रहा हूँ, लेकिन हे (एन) के हे (लॉग एन) से संदर्भ गिनती नीचा प्रदर्शन का उपयोग नहीं कर सकता है, क्योंकि आप सभी नोड्स अपने नव निर्मित "वंश" की refcounts अद्यतन करने के लिए होगा संग्रह का पुन: उपयोग? यह मुझे लगता है कि ज्यादातर उपयोग मामलों के लिए एक अपरिवर्तनीय संग्रह के उद्देश्य को हरा देता है। लेकिन अगर मैं गलत हूं तो कृपया मुझे सही करें! –

@le_me मुझे नहीं पता कि रॉब किस डेटा संरचना की कोशिश कर रहा था, इसलिए मैं इसकी समय विशेषताओं के बारे में कुछ भी नहीं कह सकता। ओ (लॉग एन) हो सकता है, ओ (एन^3) हो सकता है, ओ (एक्स (एक्स)) या कुछ और हो सकता है।उपयोग पैटर्न के आधार पर संदर्भ गणना के प्रभाव को दूसरे विश्लेषण की आवश्यकता होगी। इसके अलावा, संदर्भ गणना होने का उनका विचार था, मेरा नहीं। मैंने निश्चित रूप से एक एक्सवाई समस्या के गलत हिस्से का जवाब दिया होगा, लेकिन मुझे अभी भी लगता है कि आपकी टिप्पणी प्रश्न पर बेहतर होगी, जहां संदर्भ गिनती का सुझाव दिया गया था। –

मैं बस आपके द्वारा प्रस्तुत विशिष्ट समाधान में जानकारी जोड़ना चाहता था। मुझे लगता है कि यह ध्यान रखना महत्वपूर्ण है कि संदर्भ गिनती में संग्रह की तुलना में संभवतः उच्च समय की जटिलता के साथ प्रदर्शन जुर्माना है। उदाहरण के लिए। [माइक्रोसॉफ्ट अपरिवर्तनीय संग्रह हे (लॉग एन) जटिलता है लगता है] (https://blogs.msdn.microsoft.com/bclteam/2012/12/18/preview-of-immutable-collections-released-on-nuget/) या किसी भी ऑपरेशन के लिए कम। तो उस मामले में संदर्भ गिनती बड़े डेटा सेट के लिए गंभीर रूप से प्रदर्शन को प्रभावित करेगी। –

खैर, कचरा एकत्रित भाषाओं में बहु-थ्रेडेड वातावरण का मुद्दा भी होता है (और यह परिवर्तनीय संरचनाओं के लिए आसान नहीं है)।

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

स्रोत

2011-08-31 06:48:22

मैला काउंटर देखें (http://www.usenix.org/events/osdi10/tech/full_papers/Boyd-Wickizer.pdf) एक तरह से संदर्भ काउंटरों कि के रूप में ज्यादा कैश विवाद का कारण नहीं है को लागू करने के रूप में। संदर्भित पेपर को देखने के लिए कई अन्य दृष्टिकोण भी शामिल हैं। – Karmastan

@ कर्मस्तान: लेख के लिए धन्यवाद! मुझे यकीन नहीं है कि यह काम करेगा हालांकि लेख के अनुसार "यह ऑपरेशन महंगा है, इसलिए मैला काउंटरों का उपयोग केवल उन ऑब्जेक्ट्स के लिए किया जाना चाहिए जो अपेक्षाकृत कम आवंटित हैं।", लेकिन विचार स्वयं दिलचस्प है। एक अन्य तकनीक जिसे मैंने पढ़ा था, काउंटरों को वस्तुओं से अलग बनाए रखने के लिए है, और टीएलएस कतारों के साथ इंक/डीसी ऑपरेशंस बफर करने के लिए एक थ्रेड अपडेट किया गया है। –

गैर-कचरा एकत्रित संदर्भ में समरूपता के लिए अभी भी कार्यात्मक/अपरिवर्तनीय डेटा संरचनाएं उपयोगी हो सकती हैं?

उत्तर

संबंधित मुद्दे