🤴🏿 🐑 🧑🏾‍🤝‍🧑🏼 विंडोज के लिए लॉक-फ्री स्टैक 👨🏾‍🎨 🐬 🙍🏻

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

इस लेख में, हम लॉक-फ्री स्टैक के ओएस कार्यान्वयन के बारे में बात करेंगे और क्रॉस-प्लेटफॉर्म समकक्षों के साथ इसके प्रदर्शन की तुलना करेंगे।

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

गैर-अवरुद्ध बस कनेक्टेड सूचियों को स्वतंत्र रूप से लागू किया जा सकता है, और मैक्सिम खिजिन्स्की ( खिजमैक्स ) ने इस बारे में बहुत कुछ लिखा है कि हेबे पर लॉक-फ्री एल्गोरिदम पर लेखों की उनकी स्मारकीय श्रृंखला में विस्तार से लिखा गया है। हालांकि, विंडोज 8 से पहले, 128-बिट कैस ऑपरेशन नहीं था, जो कभी-कभी 64-बिट अनुप्रयोगों में समान एल्गोरिदम को लागू करते समय समस्याएं पैदा करता था। इस प्रकार, स्लिस्ट इस समस्या को हल करने में मदद करता है।

कार्यान्वयन

SList कार्यान्वयन की ख़ासियतों में MEMORY_ALLOCATION_ALIGNER सीमा के साथ सूची आइटम के लिए मेमोरी संरेखण की आवश्यकता शामिल है। हालाँकि, WinAPI में अन्य इंटरलॉक किए गए कार्यों के लिए समान आवश्यकताओं को लगाया जाता है। हमारे लिए, इसका मतलब है सूची वस्तुओं की स्मृति के साथ काम करते समय align_malloc / align_free का उपयोग करना।

एक अन्य विशेषता यह है कि SLIST_ENTRY प्रकार की अगली सूची तत्व के लिए सूचक संरचना के बहुत शुरुआत में स्थित होना चाहिए : हमारे अपने क्षेत्रों के लिए।

निम्नलिखित एक C ++ टेम्पलेट का कार्यान्वयन है, जो SList के साथ काम करने के लिए देशी WinAPI फ़ंक्शन को लपेटता है:

C ++ टेम्पलेट कोड

template<typename T> class SList { public: SList() { // Let Windows initialize an SList head m_stack_head = (PSLIST_HEADER)_aligned_malloc(sizeof(SLIST_HEADER), MEMORY_ALLOCATION_ALIGNMENT); InitializeSListHead(m_stack_head); //UPD: 22.05.2014, thx to @gridem } ~SList() { clear(); _aligned_free(m_stack_head); } bool push(const T& obj) { // Allocate an SList node node* pNode = alloc_node(); if (!pNode) return false; // Call the object's copy constructor init_obj(&pNode->m_obj, obj); // Push the node into the stack InterlockedPushEntrySList(m_stack_head, &pNode->m_slist_entry); return true; } bool pop(T& obj) { // Pop an SList node from the stack node* pNode = (node*)InterlockedPopEntrySList(m_stack_head); if (!pNode) return false; // Retrieve the node's data obj = pNode->m_obj; // Call the destructor free_obj(&pNode->m_obj); // Free the node's memory free_node(pNode); return true; } void clear() { for (;;) { // Pop every SList node from the stack node* pNode = (node*)InterlockedPopEntrySList(m_stack_head); if (!pNode) break; // Call the destructor free_obj(&pNode->m_obj); // Free the node's memory free_node(pNode); } } private: PSLIST_HEADER m_stack_head; struct node { // The SList entry must be the first field SLIST_ENTRY m_slist_entry; // User type follows T m_obj; }; node* alloc_node() { return (node*)_aligned_malloc(sizeof(node), MEMORY_ALLOCATION_ALIGNMENT); } void free_node(node* pNode) { _aligned_free(pNode); } T* init_obj(T* p, const T& init) { return new (static_cast<void*>(p)) T(init); } void free_obj(T* p) { p->~T(); } };

प्रदर्शन परीक्षण

एल्गोरिथ्म का परीक्षण करने के लिए, "उत्पादकों" और "उपभोक्ताओं" के साथ एक मानक परीक्षण का उपयोग किया गया था। हालाँकि, इसके अलावा, प्रत्येक परीक्षण रन पर, हम टाइप उपभोक्ता और टाइप प्रोड्यूसर के थ्रेड की संख्या में विविधता लाते हैं। इसी समय, कार्यों की कुल संख्या भी बदल गई, क्योंकि परीक्षण स्थितियों के अनुसार प्रत्येक "निर्माता" हमेशा इस मामले में 1 मिलियन के बराबर कार्यों (पुनरावृत्तियों) का उत्पादन करता है। इस प्रकार, एन के बराबर उत्पादक धागे की संख्या के साथ, नौकरियों की कुल संख्या एन * 1 एम थी।

SList टेस्ट कोड

 class test { private: static UMS::SList<int64_t> stack; public: static const char* get_name() { return "MS SList"; } static void producer(void) { for (int i = 0; i != iterations; ++i) { if (!stack.push(++producer_count)) return; } } static void consumer(void) { int64_t value; while (WaitForSingleObject(hEvtDone, 10) != WAIT_OBJECT_0) { while (stack.pop(value)) { ++consumer_count; } } while (stack.pop(value)) { ++consumer_count; } } };

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

नीचे एक फ़ंक्शन है जो आवश्यक संख्या के साथ हमारे परीक्षण को कॉल करता है:

इसलिए हम परीक्षण कहते हैं

 template<typename T> void run_test(int producers, // Number of producer threads int consumers // Number of consumer threads ) { using namespace std; boost::thread_group producer_threads, consumer_threads; // Initiate a timer to measure performance boost::timer::cpu_timer timer; cout << T::get_name() << "\t" << producers << "\t" << consumers << "\t"; // Reset the counters after the previous test producer_count = consumer_count = 0; done = false; ResetEvent(hEvtDone); // Start all the producer threads with a given thread proc for (int i = 0; i != producers; ++i) producer_threads.create_thread(T::producer); // Start all the consumer threads with a given thread proc for (int i = 0; i != consumers; ++i) consumer_threads.create_thread(T::consumer); // Waiting for the producers to complete producer_threads.join_all(); done = true; SetEvent(hEvtDone); // Waiting for the consumers to complete consumer_threads.join_all(); // Report the time of execution auto nanoseconds = boost::chrono::nanoseconds(timer.elapsed().user + timer.elapsed().system); auto seconds = boost::chrono::duration_cast<boost::chrono::milliseconds>(nanoseconds); auto time_per_item = nanoseconds.count() / producer_count; cout << time_per_item << "\t" << seconds.count() << endl; }

परीक्षण निम्नलिखित परिस्थितियों में चलाया गया था:

ओएस: विंडोज 8 64-बिट
सीपीयू: 4x इंटेल कोर i7-3667U @ 2.00GHz
रैम: 8 जीबी
कंपाइलर: Microsoft C / C ++ कंपाइलिंग कंपाइलर संस्करण 18.00.21005.1
कॉन्फ़िगरेशन: रिलीज़, स्टेटिक रनटाइम (/ MT), ऑप्टिमाइज़ स्पीड (/ ऑक्स), x64 आर्किटेक्चर
बूस्ट: संस्करण 1.55
libcds: संस्करण 1.5.0

दो आयामों में मापदंडों के भिन्नताएं (उपभोक्ता, निर्माता) हमें फ़ंक्शन टी (पी, सी) देते हैं, जिसका ग्राफ बाईं ओर की छवि में दिखाया गया है।

हमारी आंखों के साथ परिणामों में शून्य की संख्या की गणना नहीं करने के लिए, हम प्रति सेकंड कार्यों की संख्या को गिनने के बजाय, हम नैनोसेकंड में एक कार्य को पूरा करने के लिए समय देते हैं, जो कुल परीक्षण कार्यों के कुल संख्या से विभाजित समय के रूप में गणना की जाती है। यह मान जितना कम होता है, उतनी ही तेजी से एल्गोरिथ्म काम करता है।

प्रत्येक प्रकार के धागे की संख्या क्रम में बदल गई:

 int NumThreads[] = { 2, 4, 8, 12, 16, 20, 24, 32, 36, 48, 56, 64, 72 };

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

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

यह देखना खुशी की बात है कि लॉक-फ्री एप्रोच यहां अपनी चमक में चमकता है: 72 (+72) धागे की कल्पना करना मुश्किल है, जिसमें 1 मिलियन टास्क लॉक में लटकाए गए हैं। हालांकि, लॉक-फ्री लेख आमतौर पर इसके साथ शुरू होते हैं।

तुलना

निम्न लूप में जाने-माने पुस्तकालयों से लिए गए गैर-अवरुद्ध कंटेनरों के दो अन्य कार्यान्वयनों के लिए एक ही कंप्यूटर पर एक समान परीक्षण चलाया गया था:

  int NumThreads[] = { 2, 4, 8, 12, 16, 20, 24, 32, 36, 48, 56, 64, 72 }; for (int p : NumThreads) for (int c : NumThreads) { run_test<lf::boost::test>(p, c); run_test<lf::slist::test>(p, c); run_test<lf::libcds::test>(p, c); }

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

Boost.Lockfree लाइब्रेरी

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

नीचे बढ़ावा :: स्टैक का उपयोग करके समान परीक्षण के लिए कोड है।

बूस्ट टेस्ट

 class test { private: static ::boost::lockfree::stack<int64_t> stack; public: static const char* get_name() { return "boost::lockfree"; } static void producer(void) { for (int i = 0; i != iterations; ++i) { while (!stack.push(++producer_count)); } } static void consumer(void) { int64_t value; while (WaitForSingleObject(hEvtDone, 10)!=WAIT_OBJECT_0) { while (stack.pop(value)) { ++consumer_count; } } while (stack.pop(value)) { ++consumer_count; } } };

हम इस परीक्षा के परिणामों को रेखांकन के रूप में प्रस्तुत करते हैं:

लिबकस लाइब्रेरी

इस पुस्तकालय को अक्सर अपने लेखों में khizmax द्वारा संदर्भित किया जाता है। अपने उपभोक्ता गुणों के बावजूद, यह हमें कुछ बोझिल और खराब दस्तावेज लगता था (अधिकांश जानकारी हम यहां पर पाने में कामयाब रहे)। इसके अलावा, प्रत्येक थ्रेड में जहां उनके लॉक-फ्री कंटेनरों का उपयोग किया जाता है, आपको अपने थ्रेड को उनके "इंजन" (शायद TLS?) में संलग्न करने की आवश्यकता है, फिर इसे अलग करें और अभी भी कहीं-कहीं हेज़र्ड पॉइंटर सिंगलटन को इनिशियलाइज़ करने की आवश्यकता है।

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

नीचे सीडी के समान टेस्ट के लिए कोड दिया गया है :: कंटेनर :: TreiberStack:

Libcds परीक्षण

 class xxxstack : public cds::container::TreiberStack<cds::gc::HP, int64_t> { public: cds::gc::HP hzpGC; xxxstack() { cds::Initialize(0); } }; class test { private: static xxxstack stack; public: static const char* get_name() { return "libcds tb"; } static void producer(void) { // Attach the thread to libcds infrastructure cds::threading::Manager::attachThread(); for (int i = 0; i != iterations; ++i) { //int value = ++producer_count; while (!stack.push(++producer_count)); } // Detach thread when terminating cds::threading::Manager::detachThread(); } static void consumer(void) { // Attach the thread to libcds infrastructure cds::threading::Manager::attachThread(); int64_t value; while (WaitForSingleObject(hEvtDone, 10) != WAIT_OBJECT_0) { while (stack.pop(value)) { ++consumer_count; } } while (stack.pop(value)) { ++consumer_count; } // Detach thread when terminating cds::threading::Manager::detachThread(); } };

हम इस परीक्षा के परिणामों को रेखांकन के रूप में प्रस्तुत करते हैं:

प्रदर्शन की तुलना

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

परीक्षण में कार्यों की संख्या में रैखिक वृद्धि के कारण धागे की संख्या बढ़ जाती है, सभी विकल्पों के पूर्ण कार्यान्वयन में एक सभ्य राशि लगती है। परिणाम को स्थिर करने के लिए तीन पास किए गए थे, इसलिए ऊपर प्रस्तुत किए गए परिणाम तीन प्रारंभों के बीच औसत हैं।

उपरोक्त तीन-आयामी ग्राफ के अनुसार, यह ध्यान देने योग्य है कि विकर्ण (तर्कों के मान {p = c}) लगभग एक सीधी रेखा लगती है, इसलिए तीन पुस्तकालयों की दृश्य तुलना के लिए, हमने इस मानदंड के अनुसार परिणामों का चयन किया।

बाईं ओर जो हमें मिला है।

यह देखा जा सकता है कि अन्य दो कार्यान्वयनों को बढ़ावा देता है, हालांकि यह बदलते इनपुट मापदंडों के लिए अधिक प्रतिरोध प्रदर्शित करता है।

Libcds और SList पर कार्यान्वयन इतना अधिक नहीं है, लेकिन पूरे इनपुट अंतराल में।

निष्कर्ष

यह माना जाना चाहिए कि इस बार Microsoft ने एक बहुत अच्छा कार्यान्वयन (केवल एक कंटेनर) बनाया है, जो कि अच्छी तरह से ज्ञात पुस्तकालयों से एल्गोरिदम का सफलतापूर्वक मुकाबला कर सकता है। यद्यपि वर्णित कार्यान्वयन क्रॉस-प्लेटफ़ॉर्म नहीं है, यह विंडोज एप्लिकेशन डेवलपर्स के लिए उपयोगी हो सकता है।

यहां श्रव्य दृश्य परियोजना के स्रोत कोड के साथ संग्रह डाउनलोड करें

सामग्री का इस्तेमाल किया

लेख की शुरुआत में तस्वीर

MSDN slist विवरण

Boost.lockfree पुस्तकालय

लिबकस लाइब्रेरी

लॉक-फ्री डेटा स्ट्रक्चर्स। ढेर का विकास

एसएलस्ट के कार्यान्वयन विवरण के बारे में जानकारी

युपीडी:

Mickey99 के अनुरोध पर , हमने एक और परीक्षण किया: इस बार हमने एक साधारण एसटीडी :: स्टैक लिया, जिसका उपयोग सामान्य एसटीडी द्वारा अवरुद्ध किया गया था :: म्यूटेक्स।

म्यूटेक्स टेस्ट

 class test { private: static std::stack<int64_t> stack; static std::mutex lock; public: static const char* get_name() { return "mutex"; } static void producer(void) { for (int i = 0; i != iterations; ++i) { lock.lock(); stack.push(++producer_count); lock.unlock(); } } static void consumer(void) { int64_t value; while (WaitForSingleObject(hEvtDone, 10) != WAIT_OBJECT_0) { lock.lock(); if (!stack.empty()) { value = stack.top(); stack.pop(); ++consumer_count; } lock.unlock(); } bool isEmpty = false; while (!isEmpty) { lock.lock(); if (!(isEmpty = stack.empty())) { value = stack.top(); stack.pop(); ++consumer_count; } lock.unlock(); } } };

चलो ठीक है: मुझे एक लंबा इंतजार करना पड़ा, एक बहुत लंबा समय। तब प्रति स्ट्रीम कार्यों की संख्या 1 मिलियन से घटाकर 100K कर दी गई थी, जिससे निश्चित रूप से इतने सटीक परिणाम नहीं आए (इस तरह की संख्याओं के साथ इसकी आवश्यकता नहीं है), और इनपुट धाराओं की संख्या के लिए सेट को बदल दिया गया था ताकि गणना के लिए कम अंक आए :

 int NumThreads[] = { 2, 4, 8, 16, 32, 64};

यहाँ परिणाम हैं:

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

विंडोज के लिए लॉक-फ्री स्टैक