एक झपट्टा में, 100 मिलियन हत्यारे गिर गए। या लॉक-फ्री मेमोरी एलोकेटर

समस्या का बयान

स्मृति के साथ काम करते समय मेरे द्वारा लागू किए गए एल्गोरिदम में से एक में दिलचस्प विशेषताएं थीं:

• एक बड़ी संख्या एक ही प्रकार की दसियों और करोड़ों छोटी-छोटी वस्तुओं तक पहुँच सकती है।
• ऑब्जेक्ट POD प्रकार थे।
  
  पॉड

  C ++ में एक सादा पुराना डेटा संरचना एक समग्र वर्ग है जिसमें केवल PODS सदस्य होते हैं, जिसमें कोई उपयोगकर्ता-परिभाषित विध्वंसक नहीं होता है, कोई उपयोगकर्ता-निर्धारित प्रतिलिपि असाइनमेंट ऑपरेटर नहीं होता है, और पॉइंटर-टू-मेंबर प्रकार का कोई भी गैर-सदस्य सदस्य नहीं होता है।
• यह पहले से ज्ञात नहीं था कि कितनी वस्तुओं की आवश्यकता होगी, ऐसा हो सकता है कि इसमें सौ या शायद सौ मिलियन लगेंगे।
• वस्तुओं को एक बार में एक बार नष्ट नहीं किया जाता है, कुछ बिंदु पर वे एक ही बार में अनावश्यक हो जाते हैं।
• एल्गोरिथ्म को अच्छी तरह से समानांतर किया गया है, इसलिए प्रोसेसर कोर (एस) की संख्या के अनुसार एक ही समय में कई थ्रेड ऑब्जेक्ट आवंटन में शामिल हैं।

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

अतिरिक्त सुविधाएँ

मेरे मामले में, ऑब्जेक्ट एक दूसरे को संदर्भित कर सकते हैं, और मेमोरी को बचाने के लिए, एक छोटी सी हैक का आविष्कार किया गया था: सूचक के बजाय, ऑब्जेक्ट की संख्या संग्रहीत की जाती है, और ऑब्जेक्ट को स्टोरेज के लिए अनुरोध द्वारा प्राप्त किया जाता है। वस्तुओं की संख्या चार बिलियन से कम होने की गारंटी है, इसलिए 64-बिट पॉइंटर के बजाय 32-बिट इंडेक्स का उपयोग किया गया था, जो 4 बाइट्स बचाता है। इसलिए मैं मेमोरी की खपत को लगभग 12% कम कर पाया।
यह एक अच्छा बोनस निकला कि पुनरावृत्तियाँ आसानी से मानक पुस्तकालय के एल्गोरिदम का उपयोग करने के लिए बनाई जा सकती हैं, उदाहरण के लिए std :: सॉर्ट।

कार्यान्वयन

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

template <typename T> typename MassAllocator<T>::reference MassAllocator<T>::operator[](size_type index) { size_t indexOfBlock = index / elementsInBlockCount_; size_t indexInBlock = index % elementsInBlockCount_; return blocks_[indexOfBlock][indexInBlock]; } 

एक नई वस्तु हाइलाइट करें

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

  std::atomic<uint64_t> curAtomicIndex_ 

प्रत्येक मेमोरी ब्लॉक में, तत्वों की समान संख्या आवंटित की जाती है, उदाहरण के लिए, 100000। काउंटर को बढ़ाने के बाद, ब्लॉक में तत्व काउंटर के लिए तीन अलग-अलग परिस्थितियां हो सकती हैं:

• 1 से 99999 तक की संख्या प्राप्त हुई थी। इस स्थिति का मतलब है कि ब्लॉक में पर्याप्त जगह है, और हमने प्राप्त संख्या के साथ एक तत्व आरक्षित किया है।
• एक सूचकांक प्राप्त किया गया था जो ब्लॉक आकार - 100000 के साथ मेल खाता था। इसका मतलब है कि धागा "भाग्यशाली" था, और यह इस पर था कि ब्लॉक समाप्त हो गया। इस मामले में, एक नया मेमोरी ब्लॉक आवंटित करना आवश्यक है, इसमें से शून्य तत्व लें, उच्चतम ब्लॉक काउंटर को बढ़ाएं, सबसे कम काउंटर को पहले मुक्त तत्व - 1 में सेट करें, और परमाणु चर पर नया मान लिखें।
• ब्लॉक आकार से अधिक संख्या वाला एक सूचकांक प्राप्त हुआ था। इसका मतलब यह है कि इस समय थ्रेड्स में से एक मेमोरी आवंटित कर रहा है, और हम तब तक इंतजार करने के लिए मजबूर हैं जब तक कि यह सबसे कम काउंटर को 1. सेट न कर दे। इस मामले में, आपको जल्दबाज़ी नहीं करनी चाहिए, और आप कॉल करके अन्य थ्रेड्स को प्रोसेसर का समय दे सकते हैं
  

   std::this_thread::yield(); 

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

 //   ! uint32_t itemIndex = atomicIndex++; uint32_t blockIndx = atomicBlock.load(); 

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

 template <typename T> typename MassAllocator<T>::pointer MassAllocator<T>::createElement(size_type *returningIndex) { // union       32  64   union { uint64_t index; struct HiLoParts { uint32_t itemIndex; uint32_t blockIndx; } parts; }; //    index = curAtomicIndex_++; //        ,          if(parts.itemIndex < elementsInBlockCount_) { if (returningIndex != nullptr) *returningIndex = parts.blockIndx * elementsInBlockCount_ + parts.itemIndex; return &(blocks_[parts.blockIndx][parts.itemIndex]); } if (parts.itemIndex == elementsInBlockCount_) { //              auto bufferSize = elementsInBlockCount_ * sizeof(T); T* buffer = (T*)malloc(bufferSize); memset(buffer, 0, bufferSize); blocks_.push_back(buffer); //       parts.blockIndx = (unsigned int)(blocks_.size() - 1); parts.itemIndex = 0; if (returningIndex != nullptr) *returningIndex = parts.blockIndx * elementsInBlockCount_ + parts.itemIndex; //       setIndex(parts.blockIndx, 1); return &(blocks_[parts.blockIndx][parts.itemIndex]); } //,        while(true) { //    index = curAtomicIndex_++; if (parts.itemIndex == 0xffffffff) //     ,    throw std::string("Atomic index overflow"); if (parts.itemIndex >= elementsInBlockCount_) { //   ,   std::this_thread::yield(); continue; } //    ,         if (returningIndex != nullptr) *returningIndex = parts.blockIndx * elementsInBlockCount_ + parts.itemIndex; return &(blocks_[parts.blockIndx][parts.itemIndex]); } } 

उत्पादकता

X64 प्लेटफॉर्म के तहत, MassAllocator का उपयोग करते हुए 8 थ्रेड्स में 80 मिलियन तत्वों का आवंटन लगभग 2000 एमएस में i5 2500K पर किया जाता है, 70 ms में रिलीज़ होता है। नए का उपयोग करते हुए अलगाव लगभग 1350 एमएस में होता है, लेकिन डिलीट के माध्यम से विलोपन 17400 एमएस में किया जाता है! डिबगर के तहत, भले ही प्रोजेक्ट रिलीज़ कॉन्फ़िगरेशन में बनाया गया था, मैं कभी भी परीक्षण पूरा होने का इंतजार नहीं कर सकता था।
X86 प्लेटफ़ॉर्म पर परीक्षण के लिए, मुझे आवंटित वस्तुओं की संख्या को आधा करना पड़ा, क्योंकि नए-डिलीट में एक बड़ा ओवरहेड है और 80 मिलियन ऑब्जेक्ट के लिए पर्याप्त पता स्थान नहीं है। 40 मिलियन ऑब्जेक्ट्स MassAllocator द्वारा 2400 ms में आवंटित किए गए हैं, 35 ms में मुक्त किए गए हैं, जबकि नया 750 ms में अपना काम करता है, और 6430 ms में हटाता है।
जैसा कि अपेक्षित था, प्रोफाइलिंग एक अड़चन को दर्शाता है - परमाणु काउंटर को बढ़ाना, विशेष रूप से x86 के तहत। अभी तक इस टुकड़े को तेज करने के बारे में मेरे पास कोई कट्टरपंथी विचार नहीं है।

निष्कर्ष

लॉक-फ्री एल्गोरिदम मेरे लिए एक नया क्षेत्र है, इसलिए कोड को तेज करने के लिए एल्गोरिथ्म और / या सुझावों की शुद्धता के बारे में विचार सुनने के लिए मुझे खुशी होगी।

Update1

जैसा कि प्रोफाइलिंग द्वारा दिखाया गया है, ज्यादातर समय 64-बिट काउंटर क्यूरेटोमाइक्लेक्स_ के परमाणु वृद्धि पर खर्च किया जाता है। X64 में, यह एक एकल कोडांतरक कमांड lock xadd QWORD PTR में अनुवाद करता है, x86 मोड में पूरी कविता में अनुवाद करता है

 $again$158: ; 2424 : again: ; 2425 : mov ecx, edx; mov ecx, edx ; 2426 : mov ebx, eax; mov ebx, eax ; 2427 : add ebx, dword ptr _Value; add ebx, DWORD PTR $T7[ebp] ; 2428 : adc ecx, dword ptr _Value[4]; adc ecx, DWORD PTR $T7[ebp+4] ; 2429 : lock cmpxchg8b [esi]; lock cmpxchg8b QWORD PTR [esi] ; 2430 : jnz again; jne SHORT $again$158 

इसलिए, 64 बिट मोड में एक तत्व का चयन बहुत तेज है।
मेमोरी को फ्री करना x64 और x86 दोनों में तेज है।

boost::object_pool लिए एक विकल्प होगा boost::object_pool , जो वैचारिक रूप से अनुकूल है, लेकिन यह मल्टीथ्रेडेड नहीं है और कई थ्रेड्स के साथ काम कर सकता है।
नए-डिलीट को बदलने के लिए, आप boost::fast_pool_allocator प्रयास कर सकते हैं boost::fast_pool_allocator , यह नए-डिलीट की तुलना में बेहतर गति दिखाता है, और 32 बिट मोड में यह तेजी से आवंटन के कारण MassAlloc के साथ समग्र वर्गीकरण (आवंटन + रिलीज) में भी बराबर है।
मेमोरी दक्षता के संदर्भ में, सभी विकल्प मासअलोक से नीच हैं, इसलिए 32-बिट मोड में न तो नए-डिलीट और न ही बढ़ावा :: fast_pool_allocator में 80 मिलियन ऑब्जेक्ट्स को समायोजित करने के लिए पर्याप्त पता स्थान है, जबकि MassAllocator 1570 एमबी की खपत करता है।