गेम प्रोग्रामर के लिए डेटा संरचनाएं: थोक डेटा

किसी भी प्रोग्रामर को विभिन्न डेटा संरचनाओं की समझ और उनके प्रदर्शन का विश्लेषण करने के तरीके से लाभ होगा। लेकिन व्यवहार में, मैं एवीएल पेड़ , लाल-काले पेड़ , उपसर्ग पेड़ , स्किप सूची , आदि के लिए कभी काम नहीं आया। मैं केवल एक विशिष्ट एल्गोरिथ्म के लिए और कुछ और नहीं (उदाहरण के लिए, ए * पथ खोज एल्गोरिथ्म में प्राथमिकता कतार को लागू करने के लिए ढेर) के लिए कुछ डेटा संरचनाओं का उपयोग करता हूं।

रोजमर्रा के काम में, मैं आमतौर पर आश्चर्यजनक रूप से कुछ डेटा संरचनाओं के साथ करता हूं। सबसे अधिक, वे मेरे लिए काम में आते हैं:

• साझा डेटा सरणियाँ (बल्क डेटा) - प्रभावी ढंग से बड़ी संख्या में वस्तुओं को संग्रहीत करने का एक तरीका।
• कमजोर संदर्भ (या हैंडल ) - ऑब्जेक्ट को हटाए जाने पर प्रोग्राम क्रैश के बिना बल्क डेटा में ऑब्जेक्ट तक पहुंचने का एक तरीका।
• इंडेक्स बल्क डेटा में व्यक्तिगत सबसेट को जल्दी से एक्सेस करने का एक तरीका है।
• सरणियों के एरेस गतिशील आकारों के साथ थोक डेटा ऑब्जेक्ट्स को संग्रहीत करने का एक तरीका है।

मैं कई लेखों को समर्पित करूंगा कि कैसे मैं आमतौर पर इन सभी संरचनाओं को लागू करता हूं। चलो सबसे सरल और सबसे उपयोगी - बल्क डेटा के साथ शुरू करते हैं।

बल्क डेटा

इस अवधारणा के लिए कोई सामान्य शब्द नहीं है (या मुझे इसके बारे में पता नहीं है)। मैं समान वस्तुओं के किसी भी बड़े संग्रह को " बल्क डेटा " कहता हूं। उदाहरण के लिए, यह हो सकता है:

• खेल में सभी गोलियां।
• खेल के सभी पेड़।
• खेल में सभी सिक्के।

या, यदि आप अमूर्तता के उच्च स्तर पर कोड लिख रहे हैं, तो यह हो सकता है:

• खेल में सभी संस्थाओं।
• खेल में सभी जाल।
• खेल में सब लगता है।

आमतौर पर, एक गेम में प्रत्येक सिस्टम (रेंडरिंग, साउंड, एनिमेशन, फिजिक्स आदि) में विभिन्न प्रकार के ऑब्जेक्ट्स होते हैं, जिन्हें ट्रैक करना होता है। उदाहरण के लिए, ध्वनि प्रणाली के लिए, यह हो सकता है:

• सभी ध्वनि संसाधन जिन्हें बजाया जा सकता है ।
• वर्तमान में सभी ध्वनियाँ बज रही हैं।
• सभी प्रभाव (क्षीणन, स्वर परिवर्तन, आदि) ध्वनियों पर लागू होते हैं।

बल्क डेटा के मामले में, मैं निम्नलिखित मानूंगा:

• वस्तुओं का भंडारण क्रम महत्वपूर्ण नहीं है। यानी हम सरणी को कई वस्तुओं के रूप में देखते हैं।
• प्रत्येक ऑब्जेक्ट को एक निश्चित आकार के एक साधारण डेटा संरचना (पीओडी-संरचना) के रूप में दर्शाया जाता है जिसे memcpy() का उपयोग करके स्थानांतरित या दोहराया जा सकता है।

बेशक, आप उन स्थितियों के साथ आ सकते हैं जिनमें क्रम महत्वपूर्ण है । उदाहरण के लिए, यदि ऑब्जेक्ट रेंडरिंग के लिए तत्वों को निरूपित करते हैं, तो रेंडर करने से पहले हमें रिड्राऊंडिंग की मात्रा को कम करने के लिए उन्हें आगे से पीछे की ओर छाँटना पड़ सकता है।

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

चूंकि मैं केवल सरल डेटा संरचनाओं का उपयोग करता हूं, इसलिए मैं C ++ ऑब्जेक्ट्स से C ++ ऑब्जेक्ट्स को प्राथमिकता देता हूं, क्योंकि यह समझना आसान है कि मेमोरी में क्या हो रहा है और आपके प्रदर्शन का मूल्यांकन करता है। हालांकि, ऐसी परिस्थितियां हैं जब आपको बल्क डेटा में कुछ स्टोर करने की आवश्यकता होती है जिसमें एक निश्चित आकार नहीं होता है। उदाहरण के लिए, बाल वस्तुओं का नाम या सूची। मैं इन मामलों के बारे में एक अलग पोस्ट में बात करूंगा, जहां हम "सरणियों के सरणियों" को देखते हैं। अभी के लिए, मान लेते हैं कि सभी ऑब्जेक्ट सरल, निश्चित आकार की डेटा संरचनाएँ हैं।

उदाहरण के लिए, हमारी काल्पनिक ध्वनि प्रणाली के लिए बल्क डेटा संरचनाएं यहां दी गई हैं:

 typedef struct { resource_t *resource; // Resource manager data uint64_t bytes; // Size of data uint64_t format; // Data format identifier } sound_resource_t; typedef struct { sound_resource_t *resource; // Resource that's playing uint64_t samples_played; // Number of samples played float volume; // Volume of playing sound } playing_sound_t; typedef struct { playing_sound_t *sound; // Faded sound float fade_from; // Volume to fade from float fade_to; // Volume to fade to double fade_from_ts; // Time to start fade double fade_to_ts; // Time to end fade } playing_fade_t; 

बल्क डेटा स्टोर करने के तरीकों पर विचार करते समय, हमें कुछ लक्ष्यों पर विचार करने की आवश्यकता है:

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

बल्क डेटा का प्रतिनिधित्व करने के दो सबसे आसान तरीके एक स्थिर सरणी या C ++ वेक्टर हैं:

 // Static array #define MAX_PLAYING_SOUNDS 1024 uint32_t num_playing_sounds; playing_sound_t playing_sounds[MAX_PLAYING_SOUNDS]; // C++ vector std::vector<playing_sound_t> playing_sounds; 

एक सरणी के साथ काम करना बेहद सरल है, और यह आपके लिए ठीक काम कर सकता है यदि आप जानते हैं कि आवेदन में कितनी वस्तुओं की आवश्यकता है। यदि आप यह नहीं जानते हैं , तो या तो अपनी स्मृति को बर्बाद कर दें या आप वस्तुओं से बाहर भाग जाएंगे।

वेक्टर std::vector भी एक बहुत ही योग्य और सरल उपाय है, लेकिन यहां आपको कुछ पहलुओं पर विचार करने की आवश्यकता है:

• डिबगिंग iterators के कारण डीबग मोड में Visual Studio से std::vector का मानक कार्यान्वयन धीमा है। उन्हें _ITERATOR_DEBUG_LEVEL = 0 पर सेट किया जाना चाहिए।
• ऑब्जेक्ट बनाने और नष्ट करने के लिए, std::vector कंस्ट्रक्टर्स और डिस्ट्रक्टर्स का उपयोग करता है, और कुछ मामलों में वे memcpy() की तुलना में बहुत धीमा हो सकते हैं।
• std::vector एक साधारण "स्ट्रेरी बफर" को लागू करने की तुलना में अधिक कठिन है।

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

हटाने की रणनीति

पहला महत्वपूर्ण निर्णय: a[i] वस्तु को हटाते समय क्या किया जाना चाहिए। यहाँ तीन मुख्य विकल्प हैं:

• खाली स्लॉट को बंद करने के लिए आप बाद के सभी तत्वों a[i+1] → a[i] , a[i+2] → a[i+1] आदि में शिफ्ट कर सकते हैं।
• आप सरणी के अंतिम तत्व को खाली स्लॉट में स्थानांतरित कर सकते हैं: a[i] = a[n-1] ।
• या आप ऐरे में छेद बनाकर स्लॉट को खाली छोड़ सकते हैं। इस छेद का उपयोग बाद में एक नई वस्तु को रखने के लिए किया जा सकता है।

पहला विकल्प भयानक है - इन सभी तत्वों के आंदोलन पर ओ (एन) खर्च किया जाता है। पहली विधि का एकमात्र लाभ यह है कि यदि सरणी को सॉर्ट किया जाता है, तो इसमें ऑर्डर संरक्षित है। लेकिन जैसा कि ऊपर उल्लेख किया गया है, आदेश हमें परेशान नहीं करता है। ध्यान दें कि यदि आप a.erase() std::vector तत्व को हटाने के लिए a.erase() का उपयोग करते हैं, तो ठीक यही होगा!

दूसरे विकल्प को अक्सर "स्वैप-एंड-पॉप" कहा जाता है। क्यों? क्योंकि यदि आप C ++ वेक्टर का उपयोग करते हैं, तो यह विकल्प आमतौर पर उस तत्व को प्रतिस्थापित करने (स्वैप करने) द्वारा लागू किया जाता है जिसे आप पिछले एक के साथ हटाना चाहते हैं, अंतिम तत्व को हटाकर या पॉप करके।

 std::swap(a[i], a[a.size() - 1]); a.pop_back(); 

यह सब क्यों जरूरी है? C ++ में, अगर हम a[i] = a[n-1] असाइन करते हैं , तो हमें सबसे पहले a[i] को उसके डिस्ट्रक्टर को हटाकर, और उसके बाद कॉपी कंस्ट्रक्टर को कॉल करना चाहिए, ताकि i स्थिति में a[n-1] कॉपी बना i और अंत में, हम वेक्टर को शिफ्ट करते समय डिस्ट्रक्टर a[n-1] । यदि कॉपी कंस्ट्रक्टर मेमोरी आवंटित करता है और डेटा कॉपी करता है, तो यह बहुत बुरा हो सकता है। यदि हम असाइनमेंट के बजाय std::swap उपयोग करते हैं, तो हम केवल कंस्ट्रक्टर्स मूव के साथ कर सकते हैं और मेमोरी को आवंटित नहीं करना चाहिए।

फिर, यही कारण है कि सी ++ मैं सरल डेटा संरचनाओं और सी ऑपरेशन्स को पसंद करता हूं। सी ++ में कई प्रदर्शन नुकसान हैं जो आप अंदर गिर सकते हैं यदि आप नहीं जानते कि अंदर क्या चल रहा है। सी में, स्वैप-मिटा ऑपरेशन बहुत सरल होगा:

 a.data[i] = a.data[--an]; 

स्वैप-एंड-पॉप का उपयोग करते समय, वस्तुओं को कसकर पैक किया जाता है। एक नई वस्तु रखने के लिए, बस इसे सरणी के अंत में संलग्न करें।

यदि हम "छेद वाले" विकल्प I का उपयोग करते हैं, तो एक नई वस्तु रखते समय हमें पहले यह जांचने की आवश्यकता है कि क्या कोई मुफ्त "छेद" है जिसका उपयोग किया जा सकता है। यह सरणी के आकार को केवल तब बढ़ाने के लायक है जब कोई मुफ्त "छेद" न हो। अन्यथा, वस्तुओं को हटाने और बनाने की प्रक्रिया में, यह अनिश्चित काल तक बढ़ेगा।

आप छेद पदों को ट्रैक करने के लिए एक अलग std::vector<uint32_t> का उपयोग कर सकते हैं, लेकिन एक बेहतर उपाय है जो अतिरिक्त मेमोरी नहीं करता है।

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

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

एक पारंपरिक लिंक्ड सूची में, एक विशेष सूची हेडर तत्व सूची में पहले नोड को इंगित करता है, और अंतिम सूची तत्व NULL को इंगित करता है, जिसका अर्थ सूची का अंत है। इसके बजाय, मैं एक गोलाकार लिंक्ड सूची का उपयोग करना पसंद करता हूं, जिसमें हेडिंग केवल एक विशेष सूची आइटम है, और अंतिम सूची आइटम हेडिंग सामग्री पर इंगित करता है:


पारंपरिक और अंगूठी जुड़ी हुई सूची।

इस दृष्टिकोण का लाभ यह है कि सूची की शुरुआत और अंत में विशेष मामलों की संख्या को कम करके कोड बहुत सरल हो जाता है।

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

आप हमेशा सूची स्लॉट 0 में संग्रहीत करके सूची शीर्षक के एक विशेष तत्व के लिए स्थान आवंटित कर सकते हैं।

कोड कुछ इस तरह दिखेगा:

 // The objects that we want to store: typedef struct {...} object_t; // An item in the free list points to the next one. typedef struct { uint32_t next_free; } freelist_item_t; // Each item holds either the object data or the free list pointer. typedef union { object_t; freelist_item_t; } item_t; typedef struct { std::vector<item_t> items; } bulk_data_t; void delete_item(bulk_data_t *bd, uint32_t i) { // Add to the freelist, which is stored in slot 0. bd->items[i].next = bd->items[0].next; bd->items[0].next = i; } uint32_t allocate_slot(bulk_data_t *bd) { const uint32_t slot = bd->items[0].next; bd->items[0].next = bd->items[slot].next; // If the freelist is empty, slot will be 0, because the header // item will point to itself. if (slot) return slot; bd->items.resize(bd->items.size() + 1); return bd->items.size() - 1; } 

हटाने की सबसे अच्छी रणनीति क्या है? अंतिम तत्व को एक खाली स्लॉट में ले जाना, सरणी की तंग पैकिंग सुनिश्चित करना या हटाए गए तत्व के स्थान पर सरणी में "छेद" के निर्माण के साथ सभी तत्वों को अपने स्थानों पर रखना?

निर्णय लेते समय, दो पहलुओं को ध्यान में रखा जाना चाहिए:

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

सबसे अच्छा विकल्प चुनना आपकी परियोजना पर निर्भर करता है।

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

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

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


थोक डेटा हटाने की रणनीतियाँ।

कमजोर संकेत

एक नोट के रूप में, मेरा कहना है कि बल्क डेटा ऑब्जेक्ट के लिए "कमजोर पॉइंटर्स" या "डिस्क्रिप्टर" के लिए समर्थन लागू करना आसान है।

एक कमजोर सूचक एक वस्तु का संदर्भ है जो किसी तरह से यह निर्धारित कर सकता है कि जिस वस्तु को संदर्भित करता है उसे हटा दिया गया है। कमजोर बिंदुओं में सुविधाजनक यह है कि वे आपको इस बात की परवाह किए बिना वस्तुओं को हटाने की अनुमति देते हैं कि कौन उन्हें संदर्भित कर सकता है। किसी ऑब्जेक्ट को हटाने के लिए कमजोर बिंदुओं के बिना, हमें प्रत्येक व्यक्तिगत लिंक की खोज करने और इसे अमान्य घोषित करने की आवश्यकता होगी। यह विशेष रूप से मुश्किल हो सकता है यदि लिंक स्क्रिप्ट कोड में संग्रहीत हैं, नेटवर्क पर अन्य कंप्यूटरों पर, आदि।

याद रखें कि हमारे पास पहले से ही एक आईडी है जो विशिष्ट वस्तुओं की विशिष्ट पहचान करता है। "छेद वाले" विकल्प में, यह आईडी केवल तत्व का सूचकांक है (क्योंकि तत्व कभी भी नहीं चलते हैं)। सघन रूप से पैक किए गए सरणियों के मामले में, यह ऑब्जेक्ट इंडेक्स खोज सरणी में एक रिकॉर्ड है।

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

 typedef struct { uint32_t id; uint32_t generation; } weak_pointer_t; 

generation फ़ील्ड ऑब्जेक्ट की संरचना में एक फ़ील्ड है जो यह ट्रैक करता है कि बल्क डेटा ऐरे में स्लॉट कितनी बार पुन: उपयोग किया गया है। (तंग पैकिंग के मामले में, यह ट्रैक रखता है कि खोज सरणी में स्लॉट को कितनी बार पुन: उपयोग किया गया है।)

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

ध्यान रखें कि चूंकि generation क्षेत्र छेद और मौजूदा वस्तुओं दोनों के लिए आवश्यक है, इसलिए आपको इसे संघ के बाहर संग्रहीत करने की आवश्यकता है:

 typedef struct { uint32_t generation; union { object_t; freelist_item_t; }; } item_t; 

वितरण की रणनीति

यदि आप तत्व डेटा को संग्रहीत करने के लिए std::vector का उपयोग करते हैं, तो जब सरणी पूरी हो जाती है और उसे बढ़ाना पड़ता है, तो तत्वों के पूरे सरणी को पुनर्वितरित किया जाएगा। मौजूदा आइटम नए सरणी में कॉपी किए गए हैं।

std::vector ज्यामितीय रूप से बढ़ता है । इसका मतलब है कि हर बार एक वेक्टर को बढ़ाने की आवश्यकता होती है, वितरित तत्वों की संख्या कुछ कारक (आमतौर पर × 2) से गुणा होती है। जियोमेट्रिक (घातीय) वृद्धि महत्वपूर्ण है क्योंकि यह सरणी को बढ़ाने की लागत को स्थिर रखता है।

सरणी को पुनर्वितरित करते समय, हमें सभी तत्वों को स्थानांतरित करने की आवश्यकता होती है, जिसके लिए ओ (एन) की आवश्यकता होती है। हालाँकि, जैसे-जैसे सरणी बढ़ती है, हम दूसरे n तत्वों के लिए स्थान जोड़ते हैं, क्योंकि हम आकार को दोगुना करते हैं। इसका मतलब है कि जब तक हम इसमें और अधिक तत्व नहीं जोड़ते हैं, तब तक हमें फिर से सरणी बढ़ाने की आवश्यकता नहीं होगी। यही है, वृद्धि की लागत O (n) के बराबर है, लेकिन हम केवल सरणी के लिए लिखने के nth समय के लिए उन्हें * O (n) * निष्पादित करते हैं, अर्थात, औसतन एक तत्व लिखने की लागत O (n) / O (n) = है ओ (१) ।

किसी आइटम को रिकॉर्ड करने की लागत को परिशोधन स्थिर कहा जाता है , क्योंकि यदि आप निष्पादित किए जाने वाले सभी रिकॉर्डों को औसत करते हैं, तो लागत तय हो जाएगी। हालांकि, हमें यह नहीं भूलना चाहिए कि औसत से पहले, लागत बहुत स्पैस्मोडिक हो जाती है। हर O (n) रिकॉर्ड के बाद, हमें O (n) की ऊँचाई का एक शिखर मिलता है:


std::vector लिखने की लागत std::vector ।

आइए यह भी देखें कि अगर हम ज्यामितीय विकास का उपयोग नहीं करते हैं तो क्या होगा। मान लीजिए, विकास के दौरान मेमोरी को दोगुना करने के बजाय, हम बस एक और 128 स्लॉट जोड़ देंगे। पुराने डेटा को स्थानांतरित करने में अभी भी O (n) का खर्च आता है, लेकिन अब हमें इसे प्रत्येक 128 आइटम को जोड़ने की आवश्यकता है, जो कि, औसत लागत अब O (n) / O (128) = O (n) होगी । किसी सरणी में एक तत्व लिखने की लागत सरणी के आकार के लिए आनुपातिक है, इसलिए जब सरणी बड़ी हो जाती है, तो यह कछुए की गति से काम करना शुरू कर देती है। ऊप्स!

std::vector वितरण रणनीति एक अच्छा मानक विकल्प है, ज्यादातर मामलों में अच्छा काम करता है, लेकिन इसमें कुछ समस्याएं हैं:

• Amortized Constant वास्तविक समय के सॉफ़्टवेयर के लिए अच्छी तरह से अनुकूल नहीं है। यदि आपके पास एक बहुत बड़ा सरणी है, तो कहो, सैकड़ों लाखों तत्व हैं, फिर इस सरणी को बढ़ाना और सभी तत्वों को स्थानांतरित करना फ्रेम दर के ध्यान देने योग्य मंदी का कारण बन सकता है। यह उसी कारण से समस्याग्रस्त है क्योंकि कचरा संग्रह खेलों में समस्याग्रस्त है। इससे कोई फर्क नहीं पड़ता कि औसत लागत कितनी कम है, अगर कुछ फ्रेम में लागत कूद सकती है, जिससे खेल गड़बड़ हो सकता है।
• इसी तरह, बड़े सरणियों के मामले में यह आवंटन रणनीति बहुत सारी स्मृति को बर्बाद कर सकती है। मान लें कि हमारे पास 16 मिलियन तत्वों की एक सरणी है और हमें इसमें एक और लिखना होगा। यह सरणी को 32 मिलियन तक बढ़ा देगा। अब हमारे पास सरणी में 16 मिलियन तत्व हैं जो हम उपयोग नहीं कर रहे हैं। कम मेमोरी वाले प्लेटफॉर्म के लिए, यह बहुत कुछ है।
• अंत में, पुनः प्राप्ति सभी ऑब्जेक्ट को ऑब्जेक्ट में अमान्य करते हुए, मेमोरी में ऑब्जेक्ट ले जाती है। यह बग्स का एक स्रोत हो सकता है जिन्हें ट्रैक करना मुश्किल है।

नीचे दिया गया कोड उन बगों का एक उदाहरण है जो वस्तुओं को ले जाने पर हो सकते हैं:

 // Create two items and return the sum of their costs. float f(bulk_data_t *bd) { const uint32_t slot_1 = allocate_slot(bd); item_t *item_1 = &bd->items[slot_1]; const uint32_t slot_2 = allocate_slot(bd); item_t *item_2 = &bd->items[slot_2]; return item_1->cost + item_2->cost; } 

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

इस तरह की स्थिति इस तथ्य से पूरी तरह से स्पष्ट है कि बग केवल तभी बाहर आएगा जब सरणी को बिल्कुल slot_2 में पुनर्वितरित slot_2 । कार्यक्रम लंबे समय तक सही ढंग से काम कर सकता है जब तक कि कुछ वितरण पैटर्न को नहीं बदलता है, जिसके बाद बग काम करेगा।

इन सभी समस्याओं को एक अलग वितरण रणनीति का उपयोग करके हल किया जा सकता है। यहाँ कुछ विकल्प दिए गए हैं:

• : 16, 32, 64, …, . , 16 , 32 , .… , std::vector .
• , . , . . , O(n) push() , .
• , , , , .

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

, — ? , . , 16 , 16 , . , , 50 %. .

, , , . *16 K * n*, n — bulk data , , ( ).

. -, , blocks\[i / elements_per_block\][i % elements_per_block] . -, , (heap allocator), .

, « », - std::vector , , . , , .

, , ID . , , . , 64 , 32 (4 — ).

(Array of Structures, AoS) (Structure of Arrays, SoA). . , , , , :

 typedef struct { float t; vec3_t pos; vec3_t vel; vec3_t col; } particle_t; 

struct . « ». :

 uint32_t num_particles; particle_t *particles; 

, .

(SoA) struct:

 uint32_t num_particles; typedef struct { float *t; vec3_t *pos; vec3_t *vel; vec3_t *col; } particles; 

वास्तव में, हम आगे भी जा सकते हैं, क्योंकि vec3_tअपने आप में एक संरचना है:

 uint32_t num_particles; typedef struct { float *t; float *pos_x; float *pos_y; float *pos_z; float *vel_x; float *vel_y; float *vel_z; float *col_r; float *col_g; float *col_b; } particles; 

यह हमारी मूल एओएस योजना की तुलना में बहुत अधिक जटिल है, इसलिए यह वास्तव में आवश्यक क्यों है? इस दृष्टिकोण के समर्थन में दो तर्क हैं:

• कुछ एल्गोरिदम केवल खेतों के एक सबसेट के साथ काम करते हैं। उदाहरण के लिए, एक एल्गोरिथ्म tick()केवल एक क्षेत्र को प्रभावित करता है t। एल्गोरिथम simulate_physics()केवल फ़ील्ड्स को प्रभावित करता है posऔर vel। SoA योजना में, किसी संरचना के केवल कुछ हिस्सों को मेमोरी में लोड किया जाता है। यदि हम मेमोरी (जो कि आधुनिक प्रोसेसर के साथ अक्सर होता है) तक सीमित हैं , तो यह एक बड़ा प्रभाव डाल सकता है। उदाहरण के लिए, एक फ़ंक्शन tick()मेमोरी के केवल 1/10 भाग को प्रभावित करेगा, जिसका अर्थ है कि इसे 10 बार त्वरण प्राप्त होता है।
• SoA SIMD . , FPU . AVX float , 8 .

, tick() 80 ? नहीं। 10 , , , SIMD .

SoA:

• .
• , .
• particle_t * , . .
• ,
• ( ), . , .

, , struct , VM ( ). - 10 struct . 8- -, , . !

— SIMD. :

 uint32_t num_particles; typedef struct { float t[8]; float position_x[8]; float position_y[8]; float position_z[8]; float velocity_x[8]; float velocity_y[8]; float velocity_z[8]; float color_r[8]; float color_g[8]; float color_b[8]; } eight_particles_t; eight_particles_t *particles; 

- SIMD- , -, . , .

tick() 32 , 288 , 32 .. , 10- , t . -, - 64 , , , 5 . , , -, 100% .

, . , [16] , float - . , , , :


AoS SoA.

, SoA — « », SIMD , ( «»).

SIMD- «» , , , «» . , , , . next , SIMD- . struct.

, , , struct . , , .

AoS SoA, , . «» AoS SoA , SIMD-, , . .

— AoS SoA - . , AoS SoA, , AoS ( ). , , .

, « ». 16- , SoA, . scratch buffer 16 .

निष्कर्ष

, « » bulk data :

«» , VM ( ), ( 16 , ).

, :

, 8 SIMD VM .

.