C ++ में बहुपरत सहयोगी कंटेनर। यैंडेक्स रिपोर्ट

वरिष्ठ डेवलपर सर्गेई मूरिलोव की रिपोर्ट से, आप मानक पुस्तकालय के लिए बहु-थ्रेडेड साहचर्य कंटेनर के बारे में जान सकते हैं, जिसे WG21 के हिस्से के रूप में विकसित किया जा रहा है। सर्गेई ने इस समस्या और डेवलपर्स द्वारा चुने गए मार्ग के लोकप्रिय समाधानों के पेशेवरों और विपक्षों के बारे में बात की।


- आपने शायद पहले ही शीर्षक से अनुमान लगाया था कि आज की रिपोर्ट इस बारे में होगी कि वर्किंग ग्रुप 21 के ढांचे के भीतर, हमने अपने कंटेनर को std :: unordered_map के समान बनाया है, लेकिन एक बहु-थ्रेडेड वातावरण के लिए।

कई प्रोग्रामिंग भाषाओं में - जावा, सी #, पायथन - यह पहले से मौजूद है और इसका व्यापक रूप से उपयोग किया जाता है। लेकिन हमारे प्यारे, सबसे तेज और सबसे उत्पादक C ++ में, ऐसा नहीं हुआ। लेकिन हमने सलाह की और ऐसा काम करने का फैसला किया।



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

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

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

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

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

इस स्लाइड पर अंतिम विकल्प सांख्यिकी है। वास्तविक जीवन अनुप्रयोगों से, फेसबुक से वर्चुअल मशीन में उपयोग का एक उदाहरण दिया जा सकता है। उन्होंने PHP को अनुकूलित करने के लिए एक पूरी वर्चुअल मशीन बनाई और अपने वर्चुअल मशीन में वे उन तर्कों को लिखने की कोशिश करते हैं जिनके साथ उन्हें सभी निर्मित कार्यों के लिए एक बहु-थ्रेडेड हैश तालिका में बुलाया गया था। और अगर उनके पास कैश का परिणाम है, तो वे इसे तुरंत दूर देने की कोशिश करते हैं और कुछ भी नहीं गिनते हैं।

^{_{स्लाइड से लिंक करें}}

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

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

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

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

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



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

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

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

^{_{स्लाइड से लिंक करें}}

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

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

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

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

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

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

^{_{स्लाइड से लिंक करें}}

हवाई में इस बैठक में, हमारे खिलाफ एक पूरा प्रस्ताव लिखा गया था। :) हमें बताया गया था कि ऐसी चीजों का मानक में कोई स्थान नहीं है, क्योंकि आपके बहु-थ्रेडेड सहयोगी कंटेनर बनाने के कई तरीके हैं।

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

इस प्रस्ताव का दूसरा बिंदु यह था कि हमारा इंटरफ़ेस इस तथ्य के अनुकूल नहीं है कि फेसबुक ने अपने मानक पुस्तकालय से गिटहब पर पोस्ट किया है।

वास्तव में, वहाँ कोई विशेष समस्याएं नहीं थीं। बस "मैं पढ़ा नहीं है, लेकिन निंदा" की श्रेणी से एक सवाल था। उन्होंने बस देखा - इंटरफ़ेस अलग है, जिसका अर्थ है कि यह संगत नहीं है।

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



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



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

पहले वाला। बहुत से लोग चाहते थे कि हमारे संदर्भ कार्यान्वयन के पक्ष में बिना किसी ताले को पढ़े समर्थन करने के लिए। ताकि हमारे पास पूरी तरह से गैर-अवरुद्ध पठन हो। यह वास्तव में समझ में आता है: एक नियम के रूप में, सबसे लोकप्रिय उपयोगकर्ता मामला कैशिंग है। और हमारे लिए यह बहुत फायदेमंद है कि हम जल्दी पढ़ें।

दूसरा क्षण। सभी ने पिछले मित्र से बहुत कुछ सुना जो नीति आधारित डिजाइन के बारे में बात करते थे। हर किसी को एक विचार था - लेकिन क्या, मुझे अपने विचार के बारे में भी बताने दें! और सभी ने नीति आधारित डिज़ाइन के लिए मतदान किया। हालाँकि मुझे कहना होगा, यह पूरी कहानी काफी समय से चल रही है, और हमसे पहले इंटेल, आर्क रॉबिन्सन और एंटोन मालाखोव के हमारे सहयोगी ऐसा कर रहे थे। और उनके पास पहले से ही इस विषय पर कई प्रस्ताव थे। उन्होंने बस SeepOrderedList एल्गोरिथ्म के आधार पर एक लॉक मुक्त कार्यान्वयन को जोड़ने की पेशकश की। और उनके पास मेमोरी शिकायत के साथ एक नीति आधारित डिजाइन भी था।

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

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