फास्ट सी / सी ++ कैश, थ्रेड सेफ्टी

C / C ++ में कार्यान्वित मल्टीथ्रेडेड कैश का तुलनात्मक परीक्षण और O (n) कैश ** RU श्रृंखला के LRU / MRU कैश की व्यवस्था कैसे की जाती है इसका विवरण

दशकों से, कई कैशिंग एल्गोरिदम विकसित किए गए हैं: एलआरयू, एमआरयू, एआरसी, और अन्य ... हालांकि, जब बहु-थ्रेडेड कार्य के लिए कैश की आवश्यकता होती है, तो इस विषय पर Google ने डेढ़ विकल्प दिए और आमतौर पर StackOverflow पर सवाल अनुत्तरित रहा। मुझे फेसबुक से एक समाधान मिला जो इंटेल टीबीबी भंडार से थ्रेड-सुरक्षित कंटेनरों पर निर्भर करता है । उत्तरार्द्ध में एक बहु-थ्रेडेड LRU कैश अभी भी बीटा परीक्षण में है और इसलिए, इसका उपयोग करने के लिए, आपको प्रोजेक्ट में स्पष्ट रूप से निर्दिष्ट करना होगा:

#define TBB_PREVIEW_CONCURRENT_LRU_CACHE true 

अन्यथा, संकलक त्रुटि दिखाएगा क्योंकि इंटेल टीबीबी कोड में एक जांच है:

 #if ! TBB_PREVIEW_CONCURRENT_LRU_CACHE #error Set TBB_PREVIEW_CONCURRENT_LRU_CACHE to include concurrent_lru_cache.h #endif 

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

 class IAlgorithmTester { public: IAlgorithmTester() = default; virtual ~IAlgorithmTester() { } virtual void onStart(std::shared_ptr<IConfig> &cfg) = 0; virtual void onStop() = 0; virtual void insert(void *elem) = 0; virtual bool exist(void *elem) = 0; virtual const char * get_algorithm_name() = 0; private: IAlgorithmTester(const IAlgorithmTester&) = delete; IAlgorithmTester& operator=(const IAlgorithmTester&) = delete; }; 

इसी तरह, इंटरफेस लिपटे हुए हैं: ऑपरेटिंग सिस्टम के साथ काम करना, सेटिंग्स प्राप्त करना, परीक्षण के मामले आदि। स्रोत भंडार में रखे गए हैं । स्टैंड पर दो परीक्षण मामले हैं: यादृच्छिक रूप से उत्पन्न संख्याओं से एक कुंजी के साथ 1,000,000 तत्वों को सम्मिलित करें / खोजें और एक स्ट्रिंग कुंजी के साथ 100,000 तत्वों तक (wiki.train.tokens लाइनों के 10Mb से लिया गया)। निष्पादन समय का मूल्यांकन करने के लिए, प्रत्येक परीक्षण कैश को पहले समय माप के बिना लक्ष्य मात्रा में गर्म किया जाता है, फिर डेटा को जोड़ने और खोज करने के लिए सेमाफोर श्रृंखला से प्रवाह को अनलोड करता है। थ्रेड्स और टेस्ट केस सेटिंग्स की संख्या संपत्ति / सेटिंग्स में सेट की गई हैं । चरण-दर-चरण संकलन निर्देश और JSON सेटिंग्स का विवरण वाईकेआई रिपॉजिटरी में वर्णित है । समय को उस क्षण से ट्रैक किया जाता है जब अंतिम धागा बंद होने तक अर्धकुंभ जारी किया जाता है। यहाँ क्या हुआ:

टेस्ट केस 1 - यादृच्छिक संख्याओं के एक सरणी के रूप में एक कुंजी uint64_t keyArray [3]:

टेस्ट case2 - एक स्ट्रिंग के रूप में कुंजी:

कृपया ध्यान दें कि परीक्षण मामले के प्रत्येक चरण पर सम्मिलित / खोजा गया डेटा की मात्रा 10 गुना बढ़ जाती है। फिर, जो समय अगली मात्रा को संसाधित करने पर खर्च किया गया था, मैं क्रमशः 10, 100, 1000 से विभाजित करता हूं ... यदि एल्गोरिथ्म समय जटिलता में ओ (एन) की तरह व्यवहार करता है, तो समय एक्स अक्ष के लगभग समानांतर रहेगा। अगला, मैं पवित्र ज्ञान प्रकट करूंगा, जैसा कि मैंने प्रबंधित किया। ओ (एन) कैश ** आरयू श्रृंखला एल्गोरिदम में फेसबुक कैश पर 3-5 गुना श्रेष्ठता प्राप्त करें जब एक स्ट्रिंग कुंजी के साथ काम कर रहे हों:

1. हैश फ़ंक्शन, स्ट्रिंग के प्रत्येक अक्षर को पढ़ने के बजाय, स्ट्रिंग डेटा के लिए एक सूचक को uint64_t keyArray [3] में डालता है और पूर्णांकों के योग को गिनता है। यही है, यह प्रोग्राम की तरह काम करता है "अनुमान लगाओ" - और मुझे लगता है कि 3 नोटों द्वारा राग ... 3 * 8 = 24 अक्षर अगर यह लैटिन है, और यह पहले से ही हैश बास्केट में आपको लाइनों को अच्छी तरह से बिखरने की अनुमति देता है। हां, हैश बास्केट में बहुत सारी लाइनें एकत्र की जा सकती हैं, और यहां एल्गोरिथ्म तेज होने लगता है:
2. प्रत्येक टोकरी में छोड़ें सूची आपको अलग-अलग हैश में जल्दी से कूदने की अनुमति देती है (बास्केट आईडी = हैश% बास्केट की संख्या, इसलिए अलग-अलग हैश एक टोकरी में दिखाई दे सकते हैं), फिर कोने के साथ एक ही हैश में:
   
3. वे नोड्स जिनमें कुंजी और डेटा संग्रहीत हैं, नोड्स के पहले से आवंटित सरणी से लिए गए हैं, नोड्स की संख्या कैश क्षमता के साथ मेल खाती है। परमाणु पहचानकर्ता इंगित करता है कि किस नोड को अगला ले जाना है - यदि यह नोड पूल के अंत तक पहुंचता है, तो यह 0 = से शुरू होता है, इसलिए आवंटनकर्ता पुराने नोड्स ( ऑनकेचेएमएलआरयू में LRU कैश ) को अधिलेखित करने वाले एक सर्कल में जाता है।

मामले के लिए जब यह आवश्यक है कि खोज प्रश्नों में सबसे लोकप्रिय तत्वों को कैश में संग्रहीत किया जाता है, तो दूसरा OnCacheMMRU वर्ग बनाया जाता है , एल्गोरिथ्म निम्नानुसार है: कैश क्षमता के अलावा, क्लास का निर्माता भी दूसरे पैरामीटर uint32_t बेकार से गुजरता है, लोकप्रियता की सीमा है अगर cyc से वर्तमान नोड की इच्छा है कि खोज की संख्या की इच्छा है। यदि सीमाएं बेकार हैं, तो नोड को अगले सम्मिलित ऑपरेशन के लिए पुन: उपयोग किया जाता है (इसे बेदखल किया जाएगा)। यदि इस वृत्त पर नोड की लोकप्रियता (std :: atomic <uint32_t> प्रयुक्त {0}) अधिक है, तो चक्रीय पूल से आवंटनकर्ता के अनुरोध के समय, नोड जीवित रह सकेगा, लेकिन लोकप्रियता काउंटर 0. पर रीसेट हो जाएगा, इसलिए आवंटनकर्ता के पास का एक और चक्र होगा नोड्स के एक पूल पर और मौजूद रहने के लिए लोकप्रियता हासिल करने का मौका मिलेगा। यही है, यह एमआरयू एल्गोरिदम (जहां सबसे लोकप्रिय हमेशा कैश में लटका रहता है) और एमक्यू (जहां जीवनकाल ट्रैक किया जाता है) का मिश्रण है। कैश को लगातार अपडेट किया जाता है और एक ही समय में यह बहुत तेज़ी से काम करता है - 10 सर्वरों के बजाय आप 1 डाल सकते हैं।

द्वारा और कैशिंग एल्गोरिथ्म निम्नलिखित पर समय बिताता है:

1. कैश इन्फ्रास्ट्रक्चर को बनाए रखना (कंटेनर, एलोकेटर, जीवनकाल और तत्वों की लोकप्रियता पर नज़र रखना)
2. डेटा जोड़ते / खोजते समय हैश गणना और प्रमुख तुलना संचालन
3. खोज एल्गोरिदम: रेड-ब्लैक ट्री, हैश टेबल, छोड़ें सूची, ...

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

टेस्ट केस 1 - यादृच्छिक संख्याओं के एक सरणी के रूप में एक कुंजी uint64_t keyArray [3]:

टेस्ट case2 - एक स्ट्रिंग के रूप में कुंजी:

अंत में, मैं आपको यह बताना चाहता हूं कि परीक्षण बेंच के स्रोतों से और क्या दिलचस्प निकाला जा सकता है:

• JSON पार्सिंग लाइब्रेरी, जिसमें एक एकलjjson.h फ़ाइल होती है, उन लोगों के लिए एक छोटा सा सरल तेज़ एल्गोरिथम है, जो सेटिंग फ़ाइल या आने वाले JSON को किसी ज्ञात प्रारूप को पार्स करने के लिए किसी और के कोड के किसी मेगाबाइट को अपनी परियोजना में नहीं खींचना चाहते हैं।
• प्लेटफ़ॉर्म-विशिष्ट परिचालनों के कार्यान्वयन के रूप में एक दृष्टिकोण पारंपरिक (#ifdef _WIN32) के बजाय (वर्ग LinuxSystem: public ISystem {...})। यह लपेटने के लिए अधिक सुविधाजनक है, उदाहरण के लिए, अर्धचालक, गतिशील रूप से जुड़े पुस्तकालयों, सेवाओं के साथ काम - कक्षाओं में केवल एक विशिष्ट ऑपरेटिंग सिस्टम से कोड और हेडर हैं। यदि आपको किसी अन्य ऑपरेटिंग सिस्टम की आवश्यकता है, तो आप एक और कार्यान्वयन (वर्ग WindowsSystem: public ISystem {...}) इंजेक्ट करें।
• स्टैंड CMake में जा रहा है - Qt Creator या Microsoft Visual Studio 2017 में CMakeLists.txt प्रोजेक्ट को खोलना सुविधाजनक है। CmakeLists.txt के माध्यम से प्रोजेक्ट के साथ काम करने से आप कुछ तैयारी ऑपरेशनों को स्वचालित कर सकते हैं - उदाहरण के लिए, इंस्टालेशन डायरेक्टरी में टेस्ट केस फाइल और कॉन्फिगरेशन फाइल कॉपी करें:

  # Coping assets (TODO any change&rerun CMake to copy): FILE(MAKE_DIRECTORY ${CMAKE_RUNTIME_OUTPUT_DIRECTORY}/assets) FILE(GLOB_RECURSE SpecAssets ${CMAKE_CURRENT_SOURCE_DIR}/assets/*.* ${CMAKE_CURRENT_SOURCE_DIR}/assets/* ) FOREACH(file ${SpecAssets}) FILE(RELATIVE_PATH ITEM_PATH_REL ${CMAKE_CURRENT_SOURCE_DIR}/assets ${file} ) GET_FILENAME_COMPONENT(dirname ${ITEM_PATH_REL} DIRECTORY) FILE(MAKE_DIRECTORY ${CMAKE_RUNTIME_OUTPUT_DIRECTORY}/assets/${dirname}) FILE(COPY ${file} DESTINATION ${CMAKE_RUNTIME_OUTPUT_DIRECTORY}/assets/${dirname}) ENDFOREACH() 

• उन लोगों के लिए जो C ++ 17 की नई विशेषताओं में महारत हासिल कर रहे हैं, यह std :: साझा_mutex, std :: आवंटितकर्ता <std :: साझा_mutex>, टेम्पलेट्स में स्टेटिक थ्रेड_लोक के साथ काम करने का एक उदाहरण है (वहाँ बारीकियाँ हैं - जहां आवंटित करने के लिए?), बड़ी संख्या में परीक्षण शुरू करना। निष्पादन समय को मापने के साथ विभिन्न तरीकों से धागे:

  //Prepare insert threads: for (i = cnt_insert_threads; i; --i) { std::promise<InsertResults> prom; fut_insert_results.emplace_back(prom.get_future()); threads.emplace_back(std::thread (&TestCase2::insert_in_thread, this, curSize, std::move(prom), p_tester)); } // for insert //Prepare find threads: for (i = cnt_find_threads; i; --i) { std::packaged_task<FindResults(TestCase2 *i, int, IAlgorithmTester *)> ta( [](TestCase2 *i, int count, IAlgorithmTester *p_tester){ return i->find_in_thread(count, p_tester); }); fut_find_results.emplace_back(ta.get_future()); threads.emplace_back( std::thread (std::move(ta), this, curSize, p_tester)); } // for find //Banzai!!! auto start = std::chrono::high_resolution_clock::now(); l_cur_system.get()->signal_semaphore(cnt_find_threads + cnt_insert_threads); std::for_each(threads.begin(), threads.end(), std::mem_fn(&std::thread::join)); auto end = std::chrono::high_resolution_clock::now(); 

• इस परीक्षण बेंच को कैसे संकलित, कॉन्फ़िगर और चलाने के लिए चरण-दर-चरण निर्देश - वाईकेआई ।
  यदि आपके पास सुविधाजनक ऑपरेटिंग सिस्टम के लिए अभी तक चरण-दर-चरण निर्देश नहीं हैं, तो मैं ISystem और चरण-दर-चरण संकलन निर्देशों (WiKi के लिए) को लागू करने के लिए रिपॉजिटरी में योगदान के लिए आभारी रहूंगा ... या बस मुझे लिखें - मैं वर्चुअल मशीन को बढ़ाने और विधानसभा के चरणों का वर्णन करने के लिए समय खोजने की कोशिश करूंगा।