Double Headed Stack Allocator: O‘yinlarda Yangi Xotira Boshqaruvi

Yuqori unumli o‘yinlar va real‑vaqt ilovalari xotira boshqaruviga juda katta eʼtibor qaratadi. Kichik kechikishlar ham kadrlar sonini pasaytirishi, foydalanuvchi tajribasini yomonlashtirishi mumkin. Ushbu maqolada biz double headed stack allocator deb nomlangan xotira boshqaruv usulini, uning yaratilish tarixini, texnik asoslarini va amalda qanday natija berishini batafsil ko‘rib chiqamiz.

Kirish: Nega Xotira Boshqaruvi Muhim?

O‘yin motorlari har bir kadrda yuzlab, ba’zan millionlab obyektlarni yaratadi, yangilaydi va yo‘q qiladi. Bu jarayonlar ko‘pincha vaqtinchalik (transient) xotira talab qiladi – ya’ni, ma’lum bir kadr ichida ishlatiladi, keyin darhol bo‘shatiladi. An’anaviy dinamik xotira ajratish (malloc / new) bu holatda sekin bo‘lib, fragmentatsiya muammosiga olib keladi. Shuning uchun ishlab chiquvchilar bump allocator yoki stack allocator kabi yengil usullarni qo‘llashadi.

Stack Allocator Asoslari

Oddiy stack allocator xotira blokini oldindan ajratib, unga tos (top of stack) ko‘rsatkichini bir butun son qo‘shish orqali ajratadi. Xotira olish – tos += size, bo‘shatish – tos = 0 (yoki oldingi nuqtaga qaytarish). Bu operatsiyalar CPU da bir necha tsiklni egallaydi, demak profilingda deyarli “zero” vaqt ko‘rsatiladi.

• Tezlik: Ajratish faqat integer qo‘shish, bo‘shatish – bitta tayinlash.
• Oddiylik: Destruktorlar chaqirilmaydi, shuning uchun faqat POD (plain old data) yoki placement new bilan yaratilgan obyektlar ishlatiladi.
• Ko‘p ipli muhit: tos atomik qo‘shish bilan bir nechta iplar bir vaqtning o‘zida ajratish qilishi mumkin.

Bu yondashuv Surreal Software’da “This is Vegas” o‘yinida animatsiya blendlarini optimallashtirishda qo‘llanilgan. Natijada profilerdagi “allocation” bo‘limi deyarli yo‘q bo‘ldi.

Double Headed Stack Allocator Nima?

Oddiy stack allocator bir tomonli bo‘lib, xotira blokining bir uchidan boshlanadi. Ammo o‘yinlarda bir nechta mustaqil tizimlar (masalan, darajalar va qahramon modellari) bir vaqtning o‘zida dinamik xotira talab qilishi mumkin. Bu holatda fragmentatsiya tezda yuzaga keladi: bo‘sh joylar kichik bo‘laklarga bo‘linadi, katta bloklar uchun yetarli bo‘sh joy topilmaydi.

Double headed stack allocator bu muammoni ikki “tos” ko‘rsatkichini bir-biriga qarshi yo‘nalishda harakatlantirish orqali hal qiladi:

• Bir “tos” (levelTos) xotira boshidan yuqoriga qarab o‘sadi – daraja ma’lumotlari uchun.
• Ikkinchi “tos” (characterTos) xotira oxiridan pastga qarab o‘sadi – qahramon modellari uchun.
• Ular bir-biriga to‘qnashganda xotira tugagan deb hisoblanadi.

Bu usul fragmentatsiyani de‑faktom minimal darajaga tushiradi, chunki har bir tizim o‘z segmentida birlashtirilgan bo‘laklarni ishlatadi.

uint8_t* StackAllocate(uint8_t* mem, size_t& tos, size_t size){  uint8_t* ret = &mem[tos];  tos += size;  return ret;}

Amalda Qo‘llanilishi va Natijalar

Blizzard’da StarCraft 2 jamoasi double headed stack allocator’ni daraja streaming va qahramon shakl‑o‘zgartirish mexanizmlari uchun qo‘lladi. Misol uchun, 100 MB xotira blokida:

tos = 0; // deallocate all stack allocations

• Daraja ma’lumotlari 20 MB, keyin 20 MB qo‘shildi (levelTos = 40 MB).
• Qahramon ma’lumotlari 30 MB, keyin yana 30 MB (characterTos = 60 MB, oxiridan pastga).
• Daraja o‘zgarganda eski 40 MB bo‘shatildi, lekin bo‘sh joy ikki 20 MB blok sifatida qoladi.
• Yangi daraja 30 MB talab qilganda, bir xil 30 MB bo‘sh joy topilmaydi, chunki bo‘sh joylar birlashtirilmagan.

Double headed stack allocator bu vaziyatda levelTos ni 30 MB ga ko‘taradi, characterTos esa o‘zgarmas qoladi, va bo‘sh joy birlashtiriladi. Natijada fragmentatsiya yo‘qoladi, aloqador kod esa yana integer qo‘shish va tayinlashdan iborat bo‘lib qoladi.

Profilerdagi o‘lchovlar shuni ko‘rsatdiki, ajratish va bo‘shatish vaqtida 0 % CPU yuklanishi kuzatildi, bu esa real‑vaqt o‘yinlarda kadr tezligini sezilarli darajada oshirdi.

Texnik Cheklovlar va Kelajak Yo‘nalishlari

Double headed stack allocator ham o‘z chegaralariga ega:

• Statik hajm: Xotira blokini oldindan belgilash kerak, bu esa o‘yinning maksimal xotira talabini oldindan taxmin qilishni talab qiladi.
• Destruktorlar: Avtomatik destruktor chaqirish yo‘q, shuning uchun murakkab obyektlar uchun qo‘lda tozalash yoki RAII (Resource Acquisition Is Initialization) naqshlari joriy etilishi lozim.
• Ko‘p ipli sinxronizatsiya: Atomik qo‘shishlar ishlaydi, lekin yuqori kontentli iplar orasida “false sharing” muammolari paydo bo‘lishi mumkin.
• Fragmentatsiya xavfi: Agar bir tizim (masalan, daraja) ko‘p xotira iste’mol qilsa, ikkinchi tizim (qahramon) uchun yetarli bo‘sh joy qolmasligi mumkin. Bu holatda dinamik balanslash yoki ikkinchi stackni qayta ajratish strategiyasi kerak bo‘ladi.

Kelajakda bu texnikani yanada rivojlantirish yo‘nalishlari quyidagilar:

• Dynamic resizing – xotira blokini kerak bo‘lganda kengaytirish yoki qisqartirish.
• Hybrid approach – double headed stack bilan ring buffer yoki slab allocator’ni birlashtirish.
• GPU‑da qo‘llash – shaderlar uchun ham double headed stack konseptsiyasini tatbiq etish, ayniqsa compute shaderlarda dinamik alokatsiya muammolarini kamaytiradi.

Xulosa

Double headed stack allocator – bu oddiy, lekin kuchli xotira boshqaruv usuli bo‘lib, fragmentatsiyani kamaytirish, ajratish tezligini maksimal darajaga yetkazish va ko‘p ipli muhitda ham barqaror ishlashni ta’minlaydi. O‘yinlarda daraja streaming va qahramon shakl‑o‘zgartirish kabi ikki mustaqil tizim bir vaqtning o‘zida dinamik xotira talab qilganda bu yondashuv aniq foyda keltiradi. Uning cheklovlari ham mavjud, lekin to‘g‘ri dizayn va qo‘shimcha mexanizmlar bilan bu muammolarni yengish mumkin. Xotira boshqaruvini yanada samarali qilishga intilayotgan har bir dasturchi double headed stack allocator konseptsiyasini o‘z loyihalariga qo‘shishi tavsiya etiladi.

Manba: The Double Headed Stack Allocator

Asl manba: blog.demofox.org