हल्के कंटेनर कार्यान्वयन वेक्टर

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



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



//

template < class TEntry, class TAllocator > class TArrayBase

{

//

TEntry* GetStart() const { return m_Start; }

// ( , )

TEntry* GetFinish() const { return m_Finish; }

// ( , )

TEntry* GetEndAllocated() const { return m_Storage._M_data; }

//

TEntry* m_Start;

TEntry* m_Finish;

// ,

//

_STLP_alloc_proxy<TEntry*, TEntry, allocator_type> m_Storage;

};







32-बिट x86 कोड के लिए, जहां एक पॉइंटर को 4 बाइट्स की आवश्यकता होती है, ऐसी वस्तु 12 बाइट्स लेगी। यदि डेटा फ़ील्ड्स और वर्चुअल फ़ंक्शंस के बिना मेमोरी एलोकेटर का उपयोग किया जाता है (मानक एलोकेटर बस यही है), तो यह एक सफल कार्यान्वयन में जगह नहीं लेगा, कम से कम STLPort कार्यान्वयन में। VS2005 के लिए पुस्तकालय में, कार्यान्वयन कम सफल है और आवंटनकर्ता एक और 4 बाइट्स जोड़ देगा। इस प्रकार, एक नियमित सरणी के लिए एक सूचक की तुलना में न्यूनतम 8 अतिरिक्त बाइट्स की आवश्यकता होती है।



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



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



पहला समाधान ऑटो_प्ट्र <वेक्टर> पॉइंटर को स्टोर करना था। पॉइंटर समान 4 बाइट्स पर कब्जा कर लेता है, एक शून्य पॉइंटर का मतलब है कि सरणी खाली है, एक गैर-रिक्त एक ढेर पर वेक्टर ऑब्जेक्ट को संदर्भित करता है। लेकिन इस समाधान में कई नुकसान हैं:

1. एक गैर-खाली सरणी के लिए, इसके लिए एक पॉइंटर (4 बाइट्स) के लिए अतिरिक्त मेमोरी की आवश्यकता होती है और हीप पर ब्लॉक के लिए (प्रयुक्त हीप कार्यान्वयन 4 ब्लॉक बाइट्स प्रति ब्लॉक जोड़ता है);
2. अतिरिक्त अप्रत्यक्षता दिखाई देती है, क्योंकि वेक्टर ढेर के एक अलग ब्लॉक में स्थित है, जो कैश के लिए भी खराब है;
3. उपयोग के दौरान, आपको लगातार सूचक की जांच करनी चाहिए, जो त्रुटियों की ओर जाता है।

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



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



कोड के निम्नलिखित अनुभाग में, पहले की तरह ही कार्यक्षमता लागू की जाती है, लेकिन उपसर्ग में डेटा के भाग के भंडारण के साथ:



// ( )

template < class TAllocator >

class TTinyArrayStorage

{

//

char *Finish;

//

_STLP_alloc_proxy< char *, char , allocator_type> Storage;

//

static TTinyArrayStorage<TAllocator> EmptyStorage;

};



//

template < class TEntry, class TAllocator >

class TTinyArrayBase

{

//

TEntry* GetStart() const { return m_Data; }

// ( , )

TEntry* GetFinish() const { return (TEntry*)GetStorage()->Finish; }

// ( , )

TEntry* GetEndAllocated() const

{ return (TEntry*)GetStorage()->Storage._M_data; }

//

TTinyArrayStorage<TAllocator> *GetStorage() const

{ return (TTinyArrayStorage<TAllocator>*)((( char *)m_Data) -

sizeof (TTinyArrayStorage<TAllocator>)); }

//

TEntry *m_Data;

};







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



for (vector<TFoo>::iterator i = in_data.begin(), e = in_data.end(); i != e; ++i)

i->Process();







VS2005 संकलक एक मानक वेक्टर के लिए निम्नलिखित कोड बनाता है:

 00401340 8B 44 24 04 mov eax,dword ptr [esp+4] 00401344 56 push esi 00401345 8B 30 mov esi,dword ptr [eax] 00401347 57 push edi 00401348 8B 78 04 mov edi,dword ptr [eax+4] 0040134B 3B F7 cmp esi,edi 0040134D 74 0F je Test+1Eh (40135Eh) 0040134F 90 nop 00401350 8B CE mov ecx,esi 00401352 E8 D9 FF FF FF call TFoo::Process (401330h) 00401357 83 C6 04 add esi,4 0040135A 3B F7 cmp esi,edi 0040135C 75 F2 jne Test+10h (401350h) 0040135E 5F pop edi 0040135F 5E pop esi 00401360 C3 ret
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

और "लाइट" वेक्टर के लिए:

 00401370 8B 44 24 04 mov eax,dword ptr [esp+4] 00401374 56 push esi 00401375 8B 30 mov esi,dword ptr [eax] 00401377 57 push edi 00401378 8B 7E F8 mov edi,dword ptr [esi-8] 0040137B 3B F7 cmp esi,edi 0040137D 74 0F je Test+1Eh (40138Eh) 0040137F 90 nop 00401380 8B CE mov ecx,esi 00401382 E8 A9 FF FF FF call TFoo::Process (401330h) 00401387 83 C6 04 add esi,4 0040138A 3B F7 cmp esi,edi 0040138C 75 F2 jne Test+10h (401380h) 0040138E 5F pop edi 0040138F 5E pop esi 00401390 C3 ret
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

जैसा कि आप देख सकते हैं, कोड लगभग समान बनाया गया था, पांचवीं पंक्ति को छोड़कर, पहले मामले में सूचक को सरणी के अंत में वेक्टर ऑब्जेक्ट ([eax + 4]) के सापेक्ष ले जाया जाता है, और दूसरे में सरणी के पहले तत्व के सापेक्ष ([एसआईआई -8]; )।



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



निष्कर्ष के रूप में, मैं एक वास्तविक परियोजना के आंकड़ों का हवाला दूंगा जिसमें इस तरह के कंटेनर का सक्रिय रूप से उपयोग किया जाता है। लगभग 270 हजार वेक्टर ऑब्जेक्ट्स की कुल संख्या के साथ, लगभग 170 हजार खाली रहते हैं, जिसका अर्थ है एक मेगाबाइट से अधिक मेमोरी को सहेजना। मानक वेक्टर कंटेनर का उपयोग करके कोड की तुलना में, कोड आकार में बेहिसाब वृद्धि हुई है - 48 केबी तक, लगभग 10 एमबी की कुल मात्रा के साथ। उत्पादकता थोड़ी बढ़ गई, लगभग 1%।