هياكل البيانات لمبرمجي اللعبة: بيانات مجمعة

سيستفيد أي مبرمج من فهم هياكل البيانات المختلفة وكيفية تحليل أدائها. لكن في الممارسة العملية ، لم أتمكن أبدًا من الاستفادة من أشجار AVL ، أو الأشجار ذات اللون الأحمر - الأسود ، أو أشجار البادئة ، أو قوائم التخطي ، إلخ. يمكنني استخدام بعض بنيات البيانات لخوارزمية محددة واحدة ولا شيء آخر (على سبيل المثال ، أكوام لتطبيق قائمة انتظار أولوية في خوارزمية البحث عن مسار A * ).

في العمل اليومي ، أفعل عادةً مع عدد قليل جدًا من هياكل البيانات. في كثير من الأحيان ، فإنها تأتي في متناول يدي بالنسبة لي:

• صفائف البيانات المشتركة (البيانات المجمعة) - طريقة لتخزين عدد كبير من الكائنات بشكل فعال.
• مراجع ضعيفة (أو مقابض ) - طريقة للوصول إلى الكائنات في البيانات المجمعة دون تعطل البرنامج في حالة حذف الكائن.
• الفهارس هي وسيلة للوصول بسرعة إلى مجموعات فرعية فردية في بيانات مجمعة.
• صفائف المصفوفات هي طريقة لتخزين كائنات بيانات مجمعة ذات أحجام ديناميكية.

سأخصص عدة مقالات لكيفية تنفيذ كل هذه الهياكل عادةً. لنبدأ بأبسط البيانات وأكثرها فائدة.

بيانات مجمعة

لا يوجد مصطلح شائع لهذا المفهوم (أو لا أعرف ذلك). أدعو " البيانات المجمعة " أي مجموعة كبيرة من الكائنات المماثلة. على سبيل المثال ، يمكن أن يكون:

• كل الرصاص في اللعبة.
• كل الأشجار في اللعبة.
• جميع القطع النقدية في اللعبة.

أو ، إذا كنت تكتب الشفرة بمستوى أعلى من التجريد ، فقد تكون:

• جميع الكيانات في اللعبة.
• جميع تنسجم في اللعبة.
• كل الأصوات في اللعبة.

عادةً ما يكون لكل نظام (التقديم ، الصوت ، الرسوم المتحركة ، الفيزياء ، إلخ) في لعبة عدة أنواع مختلفة من الكائنات التي يحتاجها التتبع. على سبيل المثال ، بالنسبة لنظام الصوت ، يمكن أن يكون:

• جميع موارد الصوت التي يمكن لعبها.
• جميع الأصوات تلعب حاليا .
• جميع الآثار (التوهين ، وتغييرات النغمة ، وما إلى ذلك) المطبقة على الأصوات.

في حالة البيانات المجمّعة ، سأفترض ما يلي:

• ترتيب تخزين الكائنات غير مهم. أي نحن نتصور الصفيف كما العديد من الكائنات.
• يتم تمثيل كل كائن على أنه بنية بيانات بسيطة (POD-struct) ذات حجم ثابت يمكن نقلها أو تكرارها باستخدام memcpy() .

بالطبع ، يمكنك الخروج بمواقف ذات ترتيب مهم . على سبيل المثال ، إذا كانت الكائنات تشير إلى عناصر للتجسيد ، فقبل التقديم ، قد نحتاج إلى فرزها من الأمام إلى الخلف لتقليل مقدار إعادة الرسم .

ومع ذلك ، أعتقد أنه من الأفضل في معظم الحالات فرز البيانات كما يتم استخدامها ، بدلاً من تخزين البيانات في حاوية مفروزة ، مثل الأشجار ذات اللون الأحمر الداكن أو الأشجار B. على سبيل المثال ، يمكننا فرز الكائنات المقدمة من الأمام إلى الخلف قبل نقلها إلى العارض ، أو فرز الملفات أبجديًا قبل عرضها على الشاشة كقائمة. قد يبدو فرز البيانات في كل إطار مكلفًا ، ولكن في كثير من الحالات يتم ذلك في O (n) باستخدام فرز الجذر .

بما أنني أستخدم هياكل بيانات بسيطة فقط ، فإنني أفضل كائنات 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; 

العمل مع صفيف بسيط للغاية ، ويمكن أن يعمل بشكل جيد بالنسبة لك إذا كنت تعرف بالضبط عدد الكائنات المطلوبة في التطبيق. إذا كنت لا تعرف ذلك ، فإما أن تهدر ذاكرتك أو نفدت الأشياء.

يعتبر vector std::vector حلًا بسيطًا جدًا وبسيطًا ، ولكن عليك هنا التفكير في بعض الجوانب:

• تطبيق قياسي std::vector من Visual Studio بطيء في وضع التصحيح بسبب تكرار التكرارات. يجب تعيينهم على _ITERATOR_DEBUG_LEVEL = 0 .
• لإنشاء الكائنات وتدميرها ، يستخدم std::vector memcpy() ، وفي بعض الحالات يمكن أن تكون أبطأ بكثير من memcpy() .
• std::vector أكثر صعوبة في التحليل من تطبيق "بسط عازل" بسيط.

بالإضافة إلى ذلك ، بدون تدابير إضافية ، لا تدعم المصفوفات المنتظمة أو المتجهات الإشارات إلى الكائنات الفردية. دعونا نلقي نظرة على هذا الموضوع ، وكذلك قرارات التصميم الهامة الأخرى المشاركة في إنشاء نظام البيانات بالجملة.

استراتيجية إزالة

أول قرار مهم: ما الذي يجب القيام به عند حذف الكائن a[i] . فيما يلي ثلاثة خيارات رئيسية:

• يمكنك تحويل جميع العناصر التالية a[i+1] → a[i] ، a[i+2] → a[i+1] ، إلخ ، لإغلاق فتحة فارغة.
• يمكنك نقل العنصر الأخير للصفيف إلى فتحة فارغة: a[i] = a[n-1] .
• أو يمكنك ترك الفتحة فارغة عن طريق إنشاء ثقب في المصفوفة. يمكن استخدام هذا الثقب فيما بعد لوضع كائن جديد.

الخيار الأول فظيع - O (ن) ينفق على حركة كل هذه العناصر. الفائدة الوحيدة للطريقة الأولى هي أنه إذا تم فرز المصفوفة ، فسيتم الاحتفاظ بالترتيب فيها. ولكن كما ذكر أعلاه ، فإن النظام لا يزعجنا. لاحظ أنه إذا كنت تستخدم a.erase() لإزالة العنصر std::vector ، فهذا بالضبط ما سيحدث!

غالبًا ما يطلق على الخيار الثاني "المبادلة والبوب". لماذا؟ لأنه في حالة استخدام متجه C ++ ، يتم تنفيذ هذا الخيار عادةً عن طريق استبدال (استبدال) العنصر الذي تريد حذفه بالعنصر الأخير ، متبوعًا بإزالة العنصر الأخير أو ظهوره:

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

لماذا كل هذا ضروري؟ في C ++ ، إذا قمنا بتعيين a[i] = a[n-1] ، يجب أولاً إزالة a[i] عن طريق استدعاء destructor الخاص به ، ثم استدعاء مُنشئ النسخ لإنشاء نسخة من a[n-1] في الموضع i و أخيرًا ، نحن نسمي المدمر a[n-1] عند نقل المتجه. إذا قام مُنشئ النسخ بتخصيص الذاكرة ونسخ البيانات ، فقد يكون ذلك سيئًا للغاية. إذا استخدمنا std::swap بدلاً من التعيين ، فيمكننا القيام بذلك فقط مع تحرك المُنشئات ويجب عدم تخصيص الذاكرة.

مرة أخرى ، هذا هو السبب وراء تفضيل C ++ لهيئات البيانات البسيطة والعمليات C. تحتوي C ++ على العديد من عيوب الأداء التي يمكنك الوقوع فيها إذا كنت لا تعرف ما يحدث في الداخل. في C ، ستكون عملية محو المبادلة بسيطة للغاية:

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

عند استخدام swap-and-pop ، تظل الكائنات معبأة بإحكام. لوضع كائن جديد ، ما عليك سوى إرفاقه بنهاية المصفوفة.

إذا استخدمنا الخيار "مع الثقوب" ، فعند وضع كائن جديد ، نحتاج أولاً إلى التحقق مما إذا كان هناك "ثقوب" مجانية يمكن استخدامها. يجدر زيادة حجم المصفوفة فقط عند عدم وجود "فتحات" مجانية. خلاف ذلك ، في عملية حذف وإنشاء الكائنات ، وسوف تنمو إلى أجل غير مسمى.

يمكنك استخدام std::vector<uint32_t> منفصلة 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 مع ثقوب ، كما هو موضح أعلاه (الخيار الثاني أسرع). ولكن مهما كان الأمر ، سنحتاج إلى ذاكرة إضافية لهذا الجدول وخطوة إضافية غير مباشرة للمعرفات.

اختيار الخيار الأفضل يعتمد على مشروعك.

يمكنك القول إن تخزين صفيف مكتظ بشكل كثيف أمر أفضل ، لأن التكرارات على جميع العناصر (لتحديث النظام) تحدث أكثر من مطابقة الروابط الخارجية. من ناحية أخرى ، يمكننا أن نقول أن أداء "صفيف مع ثقوب" هو أسوأ فقط في حالة وجود عدد كبير من الثقوب ، وفي تطوير اللعبة عادة ما نهتم بالأداء في أسوأ الحالات (نريد أن يكون معدل الإطارات 60 هرتز ، حتى عندما يتم تنفيذ الحد الأقصى للعمليات في اللعبة) . في أسوأ الحالات ، لدينا الحد الأقصى لعدد الكائنات الحقيقية ، وفي هذه الحالة لن تكون هناك ثقوب في الصفيف. تحدث الثقوب فقط عندما ينخفض ​​عدد الكائنات ، وعندما نحذف بعض هذه الكائنات.

هناك أيضًا استراتيجيات يمكن استخدامها لتسريع معالجة المصفوفات مع العديد من الثقوب. على سبيل المثال ، يمكننا تتبع أطوال التسلسلات المستمرة للثقوب لتخطي تسلسلات الثقوب بأكملها في وقت واحد ، بدلاً من عنصر عنصر. نظرًا لأن هذه البيانات مطلوبة فقط لـ "الثقوب" وليس للعناصر العادية ، يمكنك تخزينها مع مؤشر قائمة الإصدار في الذاكرة غير المخصصة للكائنات وليس إضاعة ذاكرة إضافية.

في رأيي ، إذا لم تكن بحاجة إلى تحسين الشفرة للتكرار السريع ، فمن الأفضل استخدام خيار "الصفيف مع الثقوب". إنه أبسط ولا يحتاج إلى هياكل بحث إضافية ، ويمكنك استخدام فهرس الكائن كمعرّف له ، وهو مريح للغاية. بالإضافة إلى ذلك ، يؤدي عدم وجود كائنات متحركة إلى إزالة الأخطاء المحتملة.


استراتيجيات إزالة البيانات بالجملة.

مؤشرات ضعيفة

كملاحظة ، سأقول أنه من السهل تنفيذ دعم "المؤشرات الضعيفة" أو "الواصفات" لكائنات البيانات الكبيرة.

يمثل المؤشر الضعيف إشارة إلى كائن يمكنه بطريقة ما تحديد أن الكائن الذي يشير إليه قد تم حذفه. مريحة في المؤشرات الضعيفة هي أنها تسمح لك بحذف الكائنات دون القلق بشأن من يمكنه الرجوع إليها. بدون مؤشرات ضعيفة لإزالة كائن ما ، سنحتاج إلى البحث عن كل رابط فردي وإعلانه غير صالح. قد يكون هذا أمرًا صعبًا بشكل خاص إذا تم تخزين الروابط في رمز البرنامج النصي أو على أجهزة كمبيوتر أخرى على الشبكة ، إلخ.

تذكر أن لدينا بالفعل معرف يحدد الكائنات الموجودة بشكل فريد. في خيار "مع الثقوب" ، هذا المعرف هو ببساطة فهرس العنصر (لأن العناصر لا تتحرك أبدًا). في حالة المصفوفات كثيفة الحزم ، يعد فهرس الكائن هذا سجلاً في صفيف البحث .

لا يمكن استخدام المعرف نفسه كمؤشر ضعيف ، لأنه يمكن إعادة استخدام المعرفات. إذا تم حذف عنصر وتم إنشاء عنصر جديد في نفس الفتحة ، فلن نتمكن من معرفة الرقم التعريفي وحده. للحصول على مؤشر ضعيف ، تحتاج إلى دمج المعرف مع حقل generation :

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

حقل generation هو حقل في بنية الكائن يتتبع عدد مرات إعادة استخدام الفتحة في صفيف البيانات المجمعة. (في حالة التغليف المحكم ، يتتبع عدد المرات التي أعيد فيها استخدام الفتحة في صفيف البحث .)

عندما تقوم بحذف عنصر ، فإننا نزيد رقم التوليد في الفتحة الخاصة به. للتحقق مما إذا كان المؤشر الضعيف لا يزال صالحًا ، فإننا نتحقق مما إذا كان generation في بنية المؤشر الضعيف يطابق توليد الفاصل المشار إليه بواسطة id . إذا كانت متطابقة ، فلا يزال الكائن المصدر الذي نشير إليه موجودًا. إذا لم يكن الأمر كذلك ، فهذا يعني أنه قد تم حذفه ، وتكون الفتحة إما في قائمة الإصدار ، أو تم إعادة استخدامها.

ضع في اعتبارك أنه نظرًا لأن حقل generation ضروري لكل من الثقوب والكائنات الموجودة ، فيجب تخزينه خارج الاتحاد:

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

استراتيجية التوزيع

إذا كنت تستخدم std::vector لتخزين بيانات العناصر ، فعند امتلاء المصفوفة وتحتاج إلى زيادتها ، سيتم إعادة توزيع مجموعة العناصر بالكامل. يتم نسخ العناصر الموجودة إلى الصفيف الجديد.

std::vector ينمو هندسيا . هذا يعني أنه في كل مرة يحتاج فيها المتجه إلى الزيادة ، يتم ضرب عدد العناصر الموزعة بعامل ما (عادة × 2). النمو الهندسي (الأسي) مهم لأنه يحافظ على تكاليف زيادة المصفوفة الثابتة.

عند إعادة توزيع المصفوفة ، نحتاج إلى نقل جميع العناصر ، والتي تتطلب O (n) . ومع ذلك ، مع نمو الصفيف ، نضيف مساحة لعناصر n أخرى ، لأننا نضاعف الحجم. هذا يعني أننا لن نحتاج إلى زيادة الصفيف مرة أخرى حتى نضيف إليها المزيد من العناصر. بمعنى أن تكاليف الزيادة تساوي O (n) ، لكننا ننفذها فقط * O (n) * للمرة التاسعة من الكتابة إلى الصفيف ، أي في المتوسط ​​، تكلفة كتابة عنصر واحد هي O (n) / O (n) = يا (1) .

تسمى تكلفة تسجيل عنصر ثابت ثابت ، لأنه إذا قمت بمتوسط ​​جميع السجلات التي يتم تنفيذها ، فسيتم تحديد التكاليف. ومع ذلك ، لا ينبغي لنا أن ننسى أنه قبل أن نكون في المتوسط ​​، فإن التكاليف ستكون متقلبة للغاية. بعد كل سجلات O (n) ، نحصل على ذروة الارتفاع O (n) :


تكلفة الكتابة إلى std::vector .

لنرى أيضًا ما يحدث إذا لم نستخدم النمو الهندسي. لنفترض أنه بدلاً من مضاعفة الذاكرة أثناء النمو ، سنضيف 128 فتحة أخرى. لا يزال نقل البيانات القديمة يكلفنا O (n) ، لكننا نحتاج الآن إلى القيام بذلك كل 128 عنصرًا نضيفه ، أي أن متوسط ​​التكاليف سيكون الآن O (n) / O (128) = O (n) . تتناسب تكلفة كتابة عنصر إلى صفيف مع حجم المصفوفة ، لذلك عندما تصبح المصفوفة كبيرة ، تبدأ في العمل بسرعة سلحفاة. عفوا!

استراتيجية توزيع std::vector هي خيار قياسي جيد ، تعمل بشكل جيد في معظم الحالات ، لكن لديها بعض المشاكل:

• ليست "المطفأة الثابتة" مناسبة تمامًا للبرامج في الوقت الفعلي. إذا كان لديك مجموعة كبيرة جدًا ، على سبيل المثال ، مئات الملايين من العناصر ، فإن زيادة هذه المجموعة ونقل جميع العناصر يمكن أن يسبب تباطؤًا ملحوظًا في معدل الإطارات. هذا هو مشكلة لنفس السبب جمع القمامة مشكلة في الألعاب. لا يهم مدى انخفاض متوسط ​​التكاليف ، إذا كانت التكاليف في بعض الإطارات يمكن أن ترتفع ، مما تسبب في خلل في اللعبة.
• وبالمثل ، فإن إستراتيجية التخصيص هذه في حالة الصفائف الكبيرة يمكن أن تهدر الكثير من الذاكرة. لنفترض أن لدينا مجموعة مكونة من 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 . يمكن للبرنامج العمل بشكل صحيح لفترة طويلة حتى يغير شيء نمط التوزيع ، وبعد ذلك سوف يعمل الخطأ.

كل هذه المشاكل يمكن حلها باستخدام استراتيجية توزيع مختلفة. فيما يلي بعض الخيارات:

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

أكرر ، كل طريقة لها مزاياها وعيوبها. هذا الأخير جيد لأن العناصر لا تزال مخزنة في الذاكرة بجانب بعضها البعض ، ونحن بحاجة إلى تتبع مخزن مؤقت واحد ، لذلك ليست هناك حاجة إلى ناقلات أو قوائم إضافية. يتطلب ضبط الحد الأقصى لحجم المصفوفة ، لكن مساحة العناوين الافتراضية كبيرة للغاية بحيث يمكنك عادة تحديد أي عدد كبير دون أدنى مشكلة.

إذا لم تتمكن من استخدام حل مع الذاكرة الظاهرية ، فما النهج الذي سيكون أفضل - حجم ثابت أو كتل مع نمو هندسي؟ إذا كانت المصفوفة صغيرة جدًا ، فإن الحجم الثابت ينفق الكثير من الذاكرة الإضافية. على سبيل المثال ، إذا كان حجم الكتلة يبلغ 16 ألف عنصر ، فإنك تستخدم كل هذه العناصر البالغ عددها 16 ألف عنصر ، حتى إذا كان هناك عنصر واحد فقط في المصفوفة. من ناحية أخرى ، مع النمو الهندسي ، سوف تهدر الذاكرة بمصفوفة كبيرة جدًا ، لأنه في المتوسط ​​ستكون الكتلة الموزعة الأخيرة ممتلئة بنسبة 50٪. لمجموعة كبيرة ، يمكن أن يكون هذا العديد من ميغابايت.

سأقول مرة أخرى أنه من المهم في تطوير الألعاب تحسين الكود في أسوأ الحالات، لذلك لست قلقًا جدًا من إضاعة الذاكرة على المصفوفات الصغيرة ، إذا كانت المصفوفات الكبيرة تظهر دائمًا أداءً جيدًا. لن يتجاوز إجمالي حجم الذاكرة المهدرة أبدًا * 16 K * n * ، حيث يمثل n عدد صفائف البيانات المجمعة المنفصلة في المشروع ، ولا أعتقد أنه سيكون لدينا العديد من المصفوفات المختلفة (بضع قطع فقط لكل نظام).

الكتل ذات الحجم الثابت لها ميزتان أخريان. أولاً ، العمليات الحسابية للعثور على عنصر من خلال فهرسه أبسط ، إنها فقط blocks\[i / elements_per_block\][i % elements_per_block]. ثانياً ، يكون تخصيص الذاكرة مباشرة من الذاكرة الظاهرية أكثر فعالية من الوصول إلى مخصص ديناميكي (مخصص الكومة) ، بسبب عدم وجود تجزئة.

في الختام ، أريد أن أقول إنه إذا استخدمت خيار "مع ثقوب" لتخزين البيانات ، فأعتقد أنه يجدر الابتعاد عن استراتيجية التوزيع std::vectorحتى تحصل الكائنات على مؤشرات ثابتة لا تتغير أبدًا. على الأرجح ، ستكون مجموعة كبيرة من الذاكرة الظاهرية هي الحل الأفضل ، ولكن إذا لم تتمكن من تنفيذها ، فإن الخيار الأفضل الثاني هو تسلسل كتل ذات حجم ثابت.

لاحظ أنه نظرًا لأن هذا الأسلوب يجعل المؤشرات إلى الكائنات دائمة ، بالإضافة إلى معرفات الآن ، يمكننا استخدام المؤشرات إلى الكائنات للإشارة إلى الكائنات. ميزة ذلك هي أنه يمكننا الوصول إلى الكائنات مباشرةً ، دون إجراء عمليات بحث في الفهرس. من ناحية أخرى ، يحتاج المؤشر إلى 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; 

الطريقة المعتادة لتخزينه هي وضع العديد من هذه الهياكل في صفيف. لهذا السبب نسميها "مجموعة من الهياكل". هذا هو:

 uint32_t num_particles; particle_t *particles; 

بالطبع ، بدلاً من المصفوفة المعتادة ، يمكنك استخدام أي من الاستراتيجيات المذكورة أعلاه.

في متغير بنية الصفيف (SoA) ، نستخدم صفيفًا منفصلًا لكل مجال من مجالات البنية:

 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; 

يبدو هذا أكثر تعقيدًا من مخطط AoS الأصلي ، فلماذا يعد ضروريًا حقًا؟ هناك حجة اثنين لدعم هذا النهج:

• تعمل بعض الخوارزميات فقط مع مجموعة فرعية من الحقول. على سبيل المثال ، tick()تؤثر الخوارزمية على حقل فقط t. الخوارزمية simulate_physics()تؤثر فقط على الحقول posو vel. في مخطط SoA ، يتم تحميل أجزاء معينة فقط من البنية في الذاكرة. إذا كنا مقيدين بالذاكرة (التي غالباً ما تكون مع المعالجات الحديثة) ، فإن هذا قد يكون له تأثير كبير. على سبيل المثال ، tick()ستؤثر الوظيفة على 1/10 فقط من الذاكرة ، مما يعني أنها تحصل على تسارع 10 مرات.
• يسمح لنا مخطط SoA بتحميل البيانات مباشرة إلى سجلات SIMD للمعالجة. يمكن أن يكون لهذا تأثير كبير إذا اقتصرنا على FPUs . باستخدام AVX ، يمكننا معالجة ثمانية أرقام تعويم في وقت واحد ، مما يعطي تسارع 8 مرات.

هل هذا يعني أنه مع هذه التسارع tick()سوف يصبح 80 أسرع؟ لا.سنحصل على التسارع الأول 10 مرات فقط إذا كانت الذاكرة محدودة تمامًا ، وإذا كانت الذاكرة محدودة تمامًا ، فلن تتمكن SIMD من السماح لنا بالعمل بشكل أسرع.

عيوب نهج الخدمية:

• الرمز يزداد صعوبة.
• مزيد من الضغط على الموزع ، لأننا بحاجة إلى توزيع صفيفات منفصلة بدلاً من نقطة واحدة.
• particle_t * , . .
• ,
• ( ), . , .

كمثال على أي نوع من المشاكل يمكن أن تنشأ مع ذاكرة التخزين المؤقت ، تذكر جزيئات البنية الموضحة أعلاه وتخيل أننا خصصنا جميع المصفوفات باستخدام VM (أي أنها محاذاة على حدود صفحة من أربعة كيلوبايت). وبسبب هذا المحاذاة ، سيتم ربط جميع الحقول العشرة للجسيمات الهيكلية بكتلة ذاكرة تخزين مؤقت واحدة. إذا كانت ذاكرة التخزين المؤقت متعددة القنوات 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 بايت ، إلخ. هذا يعني أننا لن نحصل على تسارع كامل 10x ، كما في حالة مجموعة منفصلةt. أولاً ، عادة ما يكون حجم خطوط ذاكرة التخزين المؤقت 64 بايت ، وبما أننا نستخدم نصف فقط ، فلا يمكننا تسريع أكثر من 5 مرات. أيضًا ، قد تحدث التكاليف المرتبطة بتخطي وحدات البايت ، حتى لو عالجنا خطوط ذاكرة التخزين المؤقت الكاملة ، لكنني لست متأكدًا بنسبة 100٪ من ذلك.

لحل هذه المشكلة ، يمكنك تجربة حجم المجموعة. على سبيل المثال ، يمكنك تغيير حجم مجموعة [16]إلى حقل تعويم واحد يملأ سطر ذاكرة التخزين المؤقت بالكامل. أو ، إذا كنت تستخدم طريقة تخصيص الكتلة ، يمكنك ببساطة تعيين أي حجم يناسب الكتلة لحجم المجموعة:


الخدمات الإدارية و الخدمية.

بالنسبة لاستراتيجية الحذف ، فإن SoA ليس الخيار الأفضل لخيار "with holes" ، لأنه إذا استخدمنا SIMD لمعالجة ثمانية عناصر في نفس الوقت ، فلن نكون قادرين على تفويت الثقوب بأي طريقة (ما لم تكن العناصر الثمانية "ثقوب") .

نظرًا لأن تعليمات SIMD تعالج "الثقوب" بنفس طريقة معالجة البيانات الحقيقية ، نحتاج إلى التأكد من احتواء الثقوب على بيانات "آمنة". على سبيل المثال ، لا نريد أن تسبب عمليات الفتحات استثناءات في عمليات الفاصلة العائمة أو لإنشاء أرقام دون طبيعية تقلل من الأداء. أيضا ، لا ينبغي لنا أن نحتفظ المؤشرnextقائمة إصدار باستخدام الاتحاد لأن عمليات SIMD ستحل محله. بدلاً من ذلك ، استخدم حقل البنية.

إذا استخدمنا الخيار المكتظ بكثافة ، فسيكون الحذف أعلى تكلفة بعض الشيء ، لأنه يتعين عليك نقل كل حقل على حدة ، وليس بنية كاملة في وقت واحد. ولكن نظرًا لأن الإزالة أصعب بكثير من التحديثات ، فلن تكون هذه مشكلة كبيرة.

مقارنة AoS و SoA ، أستطيع أن أقول أنه في معظم الحالات ، فإن تحسين الأداء لا يستحق عناء كتابة رمز أكثر تعقيدًا. أود استخدامه كتنسيق تخزين "قياسي" لأنظمة AoS والتحول إلى SoA للأنظمة التي تتطلب سرعات حوسبة SIMD ، مثل أنظمة القطع والجزيئات. في مثل هذه الحالات ، لسرعة قصوى ، ربما اخترت صفائف معبأة بشكل كثيف.

يجدر النظر في خيار آخر - تخزين البيانات في AoS وإنشاء بيانات SOA مؤقتة للمعالجة بواسطة بعض الخوارزميات. على سبيل المثال ، أود أن أقوم بتمرير واحد على بيانات AoS وأن أكتبها إلى مخزن مؤقت مؤقت لـ SOA ، وقم بمعالجة هذا المخزن المؤقت ، ثم أعد كتابة النتائج مرة أخرى على أنها AoS (عند الضرورة). بما أنني في هذه الحالة أعرف بالتأكيد الخوارزمية التي ستقوم بمعالجة هذه البيانات ، يمكنني تحسين تنسيق التخزين لها.

ضع في اعتبارك أن هذا النهج يعمل بشكل جيد مع خيار "تخزين البلوكات". يمكنك معالجة كتلة 16000 في وقت واحد ، وتحويلها إلى الخدمية ، وتنفيذ الخوارزمية ، وكتابة النتائج مرة أخرى. لتخزين البيانات المؤقتة ، تحتاج فقط إلى مخزن مؤقت للخدش يحتوي على 16 ألف عنصر.

استنتاج

أي نهج له مزاياه وعيوبه ، ولكن "افتراضيا" أوصي بتخزين البيانات المجمعة للنظام الجديد على النحو التالي:

مجموعة من الهياكل ذات "فتحات" ومؤشرات ثابتة ، إما موزعة كوحدة تخزين كبيرة محجوزة في VM (إن أمكن) ، أو كصفيف من الكتل ذات الحجم الثابت (16 ألف لكل منها أو بحجم مثالي لبياناتك).

للحالات التي تحتاج فيها إلى حسابات سريعة جدًا لقيم البيانات:

هيكل مصفوفات الأجسام المحزومة بإحكام ، مجمعةً بـ 8 للمعالجة SIMD وتوزع كوحدة تخزين كبيرة محجوزة في VM أو كمجموعة من الكتل ذات الحجم الثابت.

في المرة القادمة سوف ننظر في موضوع فهرسة هذه البيانات.