مدیریت حافظه با تخصیص‌دهنده پشته دوطرفه در کدهای با کارایی بالا

مقدمه

در توسعه نرم‌افزارهای با کارایی بالا (High-Performance Applications) مثل بازی‌های ویدئویی، مدیریت حافظه یکی از حیاتی‌ترین بخش‌هاست. وقتی برنامه‌ای نیاز به تخصیص متغیر حافظه دارد، استفاده از روش‌های سنتی مثل malloc یا new به دلیل سربار بالا و ایجاد تکه‌شدن حافظه (Fragmentation) مناسب نیست. در این مطلب که بر اساس تجربه‌های توسعه‌دهندگان بازی‌هایی مثل StarCraft 2 نوشته شده است، با مفهوم «تخصیص‌دهنده پشته» (Stack Allocator که به آن Bump Allocator هم می‌گویند) و نسخه پیشرفته‌تر آن یعنی نوع «دطرفه» آشنا می‌شویم.

تخصیص‌دهنده پشته یا Bump Allocator چیست؟

فرض کنید یک بلاک حافظه ثابت مثلاً به اندازه ۱ مگابایت رزرو می‌کنید. متغیری به نام tos ( مخفف Top of Stack) دارید که نشان‌دهنده انتهای حافظه تخصیص‌یافته است. وقتی برنامه‌نویس می‌خواهد حافظه بگیرد، فقط کافی است اندازه مورد نظر را با tos جمع ببندد. این کار تنها یک جمع ریاضی ساده است:

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

برای آزادسازی کل حافظه هم نیازی به پاک کردن تک‌تک آیتم‌ها نیست؛ کافی است tos را دوباره صفر کنید (tos = 0). این روش به قدری سریع است که در پروفایلرها عملاً هزینه‌ای صفر دارد. همچنین با استفاده از اتمیک‌اد (Atomic Add) می‌توان از آن در محیط‌های چندرشته‌ای استفاده کرد.

تخصیص‌دهنده پشته دوطرفه (Double-Headed Stack Allocator)

مشکل اصلی پشته‌های تک‌طرفه این است که اگر دو زیرسیستم مختلف با الگوهای حیات متفاوت (مثلاً لود سطح نقشه بازی و اطلاعات کاراکتر) از یک بلاک حافظه استفاده کنند، حافظه به شدت دچار تکه‌شدن می‌شود.

راه حل معرفی‌شده توسط مهندسان بلیزارد در بازی StarCraft 2 این است که یک بلاک حافظه واحد داشته باشیم، اما:

• پشته اول (سطح نقشه): از ابتدای حافظه (0) به سمت جلو رشد می‌کند.
• پشته دوم (اطلاعات کاراکتر): از انتهای بلاک حافظه به سمت عقب رشد می‌کند.

وقتی این دو پشته به یکدیگر می‌رسند، یعنی حافظه تمام شده است. وقتی یکی از سیستم‌ها نیاز به پاکسازی دارد، پشته خودش را ریست می‌کند بدون اینکه به داده‌های سیستم دیگر تداخل یا تکه‌شدن حافظه ایجاد کند. بزرگ‌ترین مزیت این روش انعطاف‌پذیری در نسبت مصرف حافظه بین دو سیستم است؛ اگر نقشه بازی حافظه بیشتری بخواهد، کاراکتر می‌تواند با حافظه کمتری کار کند.

ذخیره اشیاء با اندازه متغیر و جدول آفست

یک کاربرد جالب دیگر این ساختار، ذخیره مجموعه‌ای از داده‌های با اندازه متغیر (Variable-Sized Objects) است که نیاز به دسترسی تصادفی دارند. برای این کار از پشته دوطرفه استفاده می‌شود:

• پشته اول برای داده‌های خام متغیر.
• پشته دوم برای نگهداری آرایه‌ای از اعداد صحیح که آفست (موقعیت) داده‌ها را در پشته اول نشان می‌دهند.

این ساختار به توسعه‌دهنده اجازه می‌دهد پیام‌ها یا دستورات شبکه با طول‌های مختلف را بهینه ذخیره کند و به راحتی از طریق جدول آفست به آن‌ها دسترسی داشته باشد یا آیتم‌ها را جابه‌جا کند.

دیدگاه جامعه توسعه‌دهندگان (Hacker News)

بحث‌های شکل‌گرفته پیرامون این مقاله در Hacker News نکات تکمیلی خوبی ارائه داد:

• برخی به سیستم‌های قدیمی‌تر مثل AmigaOS اشاره کردند که قابلیتی به نام MEMF_REVERSE برای تخصیص حافظه از انتها به ابتدا داشتند تا به کاهش تکه‌شدن کمک کند.
• مهندسان دیگر اشاره کردند که الگوریتم‌های چرخشی (Cyclic Allocators) یا روش‌های نگاشت حافظه مجازی (Virtual Addressing Wrap-around) نیز راه‌حل‌های جایگزینی برای سناریوهای پایپلاین گرافیکی یا استریمینگ هستند.
• منتقدان یادآوری کردند که مدیریت دستی حافظه یک لوکس گران‌قیمت در استودیوهای بزرگ است و توسعه‌دهندگان مستقل ممکن است با چالش‌های پیچیده‌تری در این زمینه روبه‌رو شوند.

چرا این موضوع برای مهندسین نرم‌افزار مهم است؟

برای توسعه‌دهندگانی که با کدهای حیاتیِ عملکردی (Performance-Critical) و منابع محدود (مثل سیستم‌های嵌入ی، موتورهای بازی یا پردازش داده‌های در لحظه) سر و کار دارند، تکیه بر garbage collection یا تخصیص‌دهنده‌های عمومی سیستم‌عامل می‌تواند یک گلوگاه بزرگ باشد. تسلط بر الگوهای حافظه سفارشی مثل Stack Allocator دوطرفه ابزار قدرتمندی برای حذف سربار و جلوگیری از Fragmentation فراهم می‌کند.