Çift uçlu stack allocator'lar: Oyun geliştirmeden hızlı ve parçalanmaya karşı bağışık bellek

Tek tam sayıyla bir stack allocator

3 Ekim'de Hacker News ana sayfasına çıkan demofox.org yazısı, stack allocator'ları ve çift uçlu varyantlarını ele alıyor — belleği bağımsız zamanlamalarla geri dönüştüren iki sistem arasındaki parçalanmayı ortadan kaldıran ve tahsis işlemini tek bir tam sayı toplamına indirgeyen, sahaya çıkmış oyunlardan bir bellek tekniği bu.

Yazar, tekniği gerçek projelere dayandırıyor. 2010 civarında, Midway Seattle bünyesindeki Surreal Software'de açık dünya oyunu This is Vegas — Midway iflas edince iptal edilen bir oyun — üzerinde animasyon programlama yaparken profilleyicide bir sıcak noktayla karşılaşmışlar. Animasyon, kemik kümelerini yönlendiren durum makineleri olarak çalışıyordu; her durum, harmanlanmış animasyonlardan oluşan bir ağaçla ve durumlar arasındaki sürekliliği koruyan cross-fade'lerle temsil ediliyordu. Hangi karakterlerin canlandırılacağı, kamera frustum'unun içine ne düştüğüne bağlı olarak kareden kareye kökten değişebiliyordu; bu yüzden harmanlama kodu her karede çok sayıda dinamik tahsis yapıyor, hepsi de geçiciydi.

Çözüm, bump allocator da denen bir stack allocator'dı — gerçek program stack'inden bellek çeken alloca ile karıştırılmamalı. En kötü durum için boyutlandırılmış tek bir blok ayırıyorsunuz, örneğin 1MB, ve tek bir tam sayıyı takip ediyorsunuz: stack'in tepesi. Tahsis etmek, mevcut tepe noktasındaki belleği döndürmek ve istenen bayt sayısını o tam sayıya eklemek demek. Her şeyi serbest bırakmaksa sayacı sıfıra döndüren tek bir atama. Yazıya göre değişiklikten sonra tahsis işlemi profilleyiciden kaybolmuş; harmanlama sonuçları skinning için vertex shader'a bağlanan tamponlara kopyalandıktan sonra sayaç her karede bir kez sıfırlanıyormuş.

Gerçek bir uygulamanın ayrıca sayacın bloğun sonunu aşıp aşmadığını tespit edebilmesi için blok boyutunu bilmesi gerekir; bu, null döndürerek ya da assert ile yapılabilir. Yazı temel sınırlamaya dikkat çekiyor: hiçbir şey otomatik olarak yıkıma (destructor) sokulmuyor. Placement new ile kurucular ucuzca çalıştırılabilir, ama yıkıcıların elle çağrılması gerekir ki bu hataya açıktır; bu yüzden bu allocator'lar daha basit tipler için uygundur. İki özellik daha öne çıkıyor: sayaç atomik bir toplama kullanıyorsa birden çok iş parçacığı aynı allocator'dan tahsis yapabilir; bu, CPU'daki fork/join iş yükleri veya GPU'daki karmaşık algoritmalar için faydalıdır. Ayrıca özyineleme düzeyinin başında, örneğin, sayacı kaydedip o düzey bitince geri yükleyerek kısmi serbest bırakma da mümkündür.

Parçalanma sorunu

Yazının ikinci yarısı, yazarın Blizzard'da StarCraft 2 ekibinde geçirdiği zamandan geliyor; müdürü James Anhalt çift uçlu biçimi parçalanmaya bir çözüm olarak tanımlamış. İtici senaryo şu: oyuncu hareket ettikçe eski seviye geometrisi serbest bırakılan ve yeni geometri diskten akan bir streaming dünya oyunu; şekil değiştiren bir karakter de benzer şekilde form değişikliklerinde veriyi serbest bırakıp yeniden yüklüyor.

Başarısızlık kipi çok net. Seviye verisi ile karakter verisi arasında paylaşılan 100MB'lık bellekte tahsisler iç içe geçer: seviye 20MB alır, karakter 30MB alır, seviye bir 20MB daha alır, karakter son 30MB'ı alır. Seviyenin 40MB'ını serbest bıraktığınızda 40MB boş belleğiniz olur — ama iki 20MB'lık deliğe bölünmüş olarak; yani toplam boş bellek yeterli olsa da yeni bir 30MB'lık seviye tahsisi başarısız olur.

Tek blokta iki stack

Çift uçlu tasarım, her iki sistemi de tek bir bellek bölgesine yerleştirir. Seviye verisi sıfırdan yukarı büyüyen bir stack tepesi tutar; karakter verisi ise belleğin sonundan aşağı büyüyen bir tane. Belleğin tükenmesi tam olarak iki sayaç kesiştiğinde olur. Sistemlerden biri işini bitirdiğinde kendi sayacını başlangıcına döndürür — seviye için sıfır, karakter için belleğin sonu — ve diğer tarafın tahsislerinden etkilenmeyen bitişik bir bölgeden yeniden tahsis yapar. Parçalanma yok.

Yaklaşım çok iş parçacıklı kullanıma da uygun kalır: belirli bir iş parçacığı iki taraftan da tahsis yapsa bile, her sayaca atomik toplamalar yeterlidir. Yazı ayrıca neden basitçe iki ayrı stack allocator kullanmadıkları sorusunu da yanıtlıyor: fayda, bellek kısıtlı olduğunda ve tek bir blok iki sisteme de hizmet edebolirken aralarındaki bölünme esnek kaldığında ortaya çıkar — bazı seviyeler daha fazla belleğe ihtiyaç duyabilir, karakter daha azıyla idare eder.

Yazı, sabit bir bölgede değişken sayıda ve değişken boyutlu nesne depolamak ve dizine göre rastgele erişim sağlamakla ilgili ilgili bir varyasyonla kapanıyor — örneğin ağ komutlarını sabit boyutlu paketlere paketlemek — ancak sendikaya giden alıntı bu ayrıntılardan önce kesiliyor.

Neden önemli

Genel amaçlı allocator'lar defter tutmada ve zamanla parçalanmada gerçek maliyetler taşır. Kaynak kısıtlı ve gerçek zamanlı yazılımlar için çift uçlu stack allocator her ikisine de kompakt bir yanıt: tahsis aritmetiğe dönüşür, tüm sistemi serbest bırakmak tek bir atamaya iner ve farklı yaşam sürelerine sahip iki bileşen tek bir bütçeyi kullanılamayacak kadar küçük deliklere bölmeden paylaşabilir. Fikir, bir tam sayı ve bir bayt aralığından başka bağımlılık gerektirmez, çok iş parçacıklılığa doğal biçimde genişler ve oyunların ötesine de iyi uygulanır — sunucularda kare başına ya da istek başına geçici işler, ayrıştırma tamponları ve GPU komut üretimi hep doğal adaylardır.