मैं अपनी परियोजनाओं में से एक में एक कस्टम ढेर कार्यान्वयन का उपयोग करता हूं। यह दो प्रमुख हिस्से होते हैं:हीप एकल-थ्रेडेड उपयोग के लिए अनुकूलित (लेकिन इस तक सीमित नहीं है)
फिक्स्ड आकार-ब्लॉक ढेर। अर्थात। एक ढेर जो केवल एक विशिष्ट आकार के ब्लॉक आवंटित करता है। यह बड़े मेमोरी ब्लॉक (या तो वर्चुअल मेमोरी पेज या किसी अन्य ढेर से) आवंटित करता है, और फिर उन्हें परमाणु आवंटन इकाइयों में विभाजित करता है।
यह आवंटन/तेजी से मुक्त करता है (ओ (1) में) और बाहरी ढेर द्वारा लगाई गई चीजों को ध्यान में रखते हुए कोई मेमोरी उपयोग ओवरहेड नहीं होता है।
वैश्विक सामान्य उद्देश्य ढेर। इसमें उपरोक्त (निश्चित आकार) ढेर की बाल्टी होती है। अनुरोधित आवंटन आकार डब्लूआरटी उचित बाल्टी चुनता है, और इसके माध्यम से आवंटन करता है।
चूंकि पूरा आवेदन (भारी) बहु थ्रेडेड है - वैश्विक ढेर ताले इसके संचालन के दौरान उपयुक्त बाल्टी।
नोट: पारंपरिक ढेर के विपरीत, इस ढेर को न केवल आवंटन के लिए आवंटन आकार की आवश्यकता होती है, बल्कि मुक्त करने के लिए भी आवंटन आकार की आवश्यकता होती है। यह खोजों या अतिरिक्त मेमोरी ओवरहेड के बिना उपयुक्त बाल्टी की पहचान करने की अनुमति देता है (जैसे आवंटित ब्लॉक से पहले ब्लॉक आकार को सहेजना)। हालांकि कुछ हद तक कम सुविधाजनक, यह मेरे मामले में ठीक है। इसके अलावा, चूंकि "बाल्टी कॉन्फ़िगरेशन" संकलन-समय पर ज्ञात है (सी ++ टेम्पलेट वूडू के माध्यम से कार्यान्वित) - उचित बाल्टी संकलन समय पर निर्धारित की जाती है।
अब तक सबकुछ अच्छा दिखता है (और काम करता है)।
हाल ही में मैंने एक एल्गोरिदम पर काम किया जो ढेर परिचालनों को भारी रूप से करता है, और ढेर प्रदर्शन से स्वाभाविक रूप से प्रभावित होता है। प्रोफाइलिंग से पता चला कि इसका प्रदर्शन लॉकिंग द्वारा काफी प्रभावित हुआ है। यही है, ढेर स्वयं बहुत तेज़ काम करता है (सामान्य आवंटन में केवल कुछ मेमोरी डिफ्रेंसिंग निर्देश शामिल होते हैं), लेकिन चूंकि पूरा एप्लिकेशन बहु-थ्रेडेड है - उचित बाल्टी महत्वपूर्ण अनुभाग द्वारा संरक्षित है, जो पर निर्भर करता है निर्देशों को इंटरलॉक करता है, जो बहुत भारी हैं।
मैंने इस एल्गोरिदम को अपना समर्पित ढेर देकर इस समय तय किया है, जो एक महत्वपूर्ण खंड द्वारा संरक्षित नहीं है। लेकिन यह कोड स्तर पर कई समस्याएं/प्रतिबंध लगाता है। जहां ढेर के भीतर गहराई से संदर्भ जानकारी को पारित करने की आवश्यकता हो, जहां भी ढेर आवश्यक हो। इससे बचने के लिए कोई भी टीएलएस का उपयोग कर सकता है, लेकिन इससे मेरे विशिष्ट मामले में पुनः प्रवेश के साथ कुछ समस्याएं हो सकती हैं।
इससे मुझे आश्चर्य होता है: क्या एकल-थ्रेडेड उपयोग के लिए ढेर को अनुकूलित करने के लिए कोई ज्ञात तकनीक है?
संपादित करें: गूगल के tcmalloc बाहर की जाँच के सुझाव देने के लिए @Voo को
विशेष धन्यवाद।
ऐसा लगता है कि मैंने कम-से-कम (कम से कम छोटी वस्तुओं के लिए) किया था। लेकिन इसके अलावा वे प्रति-थ्रेड कैशिंग को बनाए रखते हुए, मेरे पास सटीक समस्या का समाधान करते हैं।
मैंने भी इस दिशा में सोचा, लेकिन मैंने प्रति-थ्रेड ढेर को बनाए रखने के बारे में सोचा। फिर किसी अन्य धागे से संबंधित ढेर से आवंटित एक मेमोरी ब्लॉक को खाली करना कुछ हद तक मुश्किल है: इसे किसी लॉक कतार में डालना चाहिए, और अन्य धागे को अधिसूचित किया जाना चाहिए, और लंबित आवंटन को अतुल्यकालिक रूप से मुक्त करना चाहिए। असिंक्रोनस डेलोकेशन समस्याएं पैदा कर सकता है: यदि वह धागा किसी कारण से व्यस्त है (उदाहरण के लिए आक्रामक गणना करता है) - वास्तव में कोई स्मृति विलोपन नहीं होता है। बहु-थ्रेडेड परिदृश्य में प्लस डीलोकेशन की लागत काफी अधिक है।
ओटीओएच कैशिंग के साथ विचार बहुत आसान और अधिक कुशल लगता है। मैं इसे काम करने की कोशिश करूंगा।
बहुत बहुत धन्यवाद।
पी.एस .:
दरअसल गूगल के tcmalloc महान है। मेरा मानना है कि यह मेरे द्वारा किए गए कार्यों (कम से कम निश्चित आकार के भाग) के समान ही लागू किया गया है।
लेकिन, पैडेंटिक होने के लिए, एक बात है जहां मेरा ढेर बेहतर है। दस्तावेज़ों के मुताबिक, टीसीएमएलओसी एक ओवरहेड लगभग 1% (असम्बद्ध रूप से) लगाता है, जबकि मेरा ओवरहेड 0.0061% है। यह सटीक होने के लिए 4/64K है।
:)
यह मेरा परीक्षण करने के लिए मैं साल पहले किया है याद रखता है। आमतौर पर इस्तेमाल किया जाने वाला "खराब" मानक तंत्र एक अच्छा "कस्टम" कार्यान्वयन के 100 गुना से अधिक समय लेता है। –
मुझे यह देखना अच्छा लगेगा कि मानक स्मृति आवंटक से तेज़ होने पर आपने क्या किया है। चूंकि अधिकांश मानक कार्यान्वयन पहले से ही करते हैं जो आपके दावों (और बहुत कुछ) करने का दावा करते हैं। मुझे ओ (1) उत्सुकता का दावा है, खासकर जब आप कोई ओवरहेड का दावा नहीं करते हैं (मुझे यकीन है कि जब आप इसके पेटेंट के माध्यम से जाते हैं तो आप एक सुंदर पैसा कमाएंगे)। –
संपूर्ण बाल्टी विचार मूल रूप से Google का tcmalloc है (हालांकि यह एक सामान्य आवंटक है क्योंकि इसे गतिशील रूप से तय करना है कि किस बाल्टी का उपयोग करना है)। tcmalloc आपकी समस्या से बचने के लिए थ्रेड स्थानीय भंडारण का उपयोग करता है और केवल सामान्य ढेर से ही आवंटित करता है और इसलिए ताले से बचाता है। – Voo