Peredvizhnikov motoru: C++20 ile yazılmış lock-free oyun motoru

 (github.com/eduard-permyakov)
4 puan yazan GN⁺ 2023-09-11 | 1 yorum | WhatsApp'ta paylaş
  • C++20 ile yazılmış tamamen lock-free bir oyun motoru olup, dilin coroutine primitive'leri üzerinde eşzamanlı hesaplama için aktör modelini uygular
  • Aktör modeli soyutlamasını kullanarak, thread'ler arası senkronizasyonun ayrıntılarından yalıtılmış şekilde karmaşık paralel mantık geliştirilebilir
  • Tamamen lock-free uygulama, rastgele bir thread sonlanması durumunda bile ilerleme garantisi, deadlock önleme, kritik olaylara öngörülebilir gecikmeyle tepki verme ve hata toleransı sağlar
  • Worker thread'lerinden biri asenkron olarak sonlansa bile motorun çalışmaya devam edeceğine dair garanti sunar
  • Uygulama; Software Transactional Memory, lock-free queue'lar, lock-free serialization primitive'leri, std::atomic_shared_ptr, lock-free scheduler, lock-free memory allocator ve derleme zamanı DAG gibi bileşenleri içerir
  • Lock-free algoritmalar, tasarım gerekçeleri ve benchmark'lar Peredvizhnikov Engine: Design and Implementation of a Completely Lock-Free Scheduler belgesinde ele alınıyor
  • Veri odaklı tasarımı desteklemek için, bileşen bazlı erişime optimize edilmiş ve büyük veri kümelerini destekleyen bir bellek içi veritabanı uygular
  • Bellek içi veritabanı, Flat Hash Map ve Bitwise Trie with Bitmap veri yapıları temel alınarak oluşturulmuştur
  • Şu anda yalnızca Linux platformu destekleniyor ve kaynaktan derleme için Clang++ 16 gerekiyor
  • Kaynak kodu GPLv3 lisansı altında sunuluyor; kodun bir kısmını veya tamamını farklı bir lisansla kullanma izni duruma göre verilebilir

İlgili okumalar

1 yorum

 
GN⁺ 2023-09-11
Hacker News yorumları

  • Actor framework’ünde metot işaretçileri kuyruğu için sıradan bir std::deque kullanılıyor; iletileri kuyruğa eklerken de Benaphore yöntemiyle kilitleme yapılıyor.
    Aslında Futex gibi atomik işlemlerle kilitleme ilkelini birlikte kullanıyor; ancak benim kilitleme ilkelim, yeniden deneme sayısına bağlı olarak spinlock/mutex kombinasyonu gibi çalışıyor. Benchmark’lara göre ileti push fonksiyonunun bloke olması çok nadir; işletim sistemi bağlam değişimi olasılığı da düşük olduğundan, ara sıra kilitli bir thread swap out edilse bile bu, lock-free algoritmaların maliyetini haklı çıkaracak kadar sık gerçekleşmiyor.
    Özetle lock-free olmayan kuyruk, lock-free kuyruktan çok daha hızlı; fakat kimsenin kilidi alamadığı bağlam değişimleri nedeniyle çok nadiren uzun gecikmeler yaşanabileceğini kabul etmek gerekiyor. Modern donanımda worker thread başına saniyede 10 milyon ileti kuyruğa eklenebiliyor.

    • “Aslında Futex” denmiş ama Benaphore oldukça eski bir fikir; Futex de basitçe “Linux tarzı Benaphore” değil.
      Esas nokta, bir kernel nesnesine, yani ayrı bir kilitleme ilkelinin gerçekten gerekli olmaması. Bu fikir, “herkesin bildiği yöntem” olmaktan çıkıp “işletim sistemine hemen eklenmesi gereken özellik” hâline burada geliyor.
      Futex tasarımında, çakışma yönetimi için işletim sistemi senkronizasyon nesnesi yerine, işletim sistemi adres→thread eşleme listesini tutar. T thread’i X adresindeki futex üzerinde uykuya geçerse, listeye X’in T’yi göstereceği şekilde girer; X futex’ini uyandırma isteği gelirse işletim sistemi listeyi tarayıp T’yi uyandırır.
      Fark kısıtlamalarda ortaya çıkar. Benaphore gibi şeyler pahalı sistem geneli kaynaklardı; hatırladığım kadarıyla BeOS makine başına yalnızca 65536 civarı izin veriyordu. Futex ise sadece bellek olduğundan bir sınır koymak için neden yoktur.
    • Böyle ilginç bir yazıda kod bağlantısı olmalı. Hem iddialar kanıtlanır hem de benim gibi insanlar fikri ilginç bulup hemen implementasyonu görmek ister.
    • Ayrıntılı koşullara göre çok değişir. Çekişme yüksekse performans hızla düşer; atomik komutlar bile darboğaz hâline gelebilir (https://stackoverflow.com/q/2538070).
      Çoğu durumda sadece kilit kullanıp endişelenmemek gerektiği gözleminin doğru olduğunu düşünüyorum. Ama daha iyisinin yapılabileceği uygulamalar veya durumlar da var. Tüketicinin tek bir kilit işlemiyle kuyruktaki tüm öğeleri çıkarması, üreticilerin de tüketiciye sinyal göndermesi dikkatli uygulanırsa kuyruk verimliliğini ve throughput’u artırabilir. Örneğin her öğe eklendiğinde sinyal göndermek yerine, yalnızca kuyruk boşken dolu hâle geldiğinde göndermek gerekir.
    • Lock-free veri yapıları, düşük çekişmede throughput’u artırmaktan çok çekişmenin etkisini azaltmak için daha anlamlı değil mi?
    • O “maliyeti kabul edilebilir” ifadesi, bahsedilen öngörülemez ve nadir uzun gecikmelerin asla gerçekleşmemesi gereken katı gereksinimleri olan kişiler için istisnadır.

  • Lock-free scheduler kesinlikle ilginç görünüyor; özellikle event broadcast’in linearizability özelliği dikkat çekici. Ancak makaledeki benchmark’ta 12 actor çifti (ve 12 çekirdek?) için en iyi değer saniyede 43.500 ileti; tek çekirdek grafiği de saniyede yaklaşık 5.000 ileti gösteriyor. Bu tür bir benchmark için şaşırtıcı derecede düşük.
    Motor Linux’u ve daha önemlisi x86’yı gerektirdiği için (assembly komutları nedeniyle) henüz yeniden üretemedim; ama actor çifti başına en az saniyede yaklaşık 1 milyon istek beklerim. Erlang gibi örnekleri düşününce bunun altındaki değerlerde overhead yasaklayıcı düzeyde büyür.
    Bu motor ileti aktarımına odaklanıyor; ancak deneyimlerime göre bu yaklaşımın yönetilmesi çok zor. Durum makineleri zordur; birden çok alt actor ile çalışırken daha da zorlaşır. Özünde actor’ların ileti aktarımından çok, durumu kilitsiz biçimde izole etmekle ilgili olduğunu düşünüyorum. Swift actors bunu doğru yaptı bence: ileti yerine metot çağrısı kullanmak yalnızca akıl yürütmeyi kolaylaştırmakla kalmıyor, runtime’da bağlamın değişebileceği noktaları da ayrıca gösteriyor ve scheduler’ın mutlaka araya girmesini gerektirmiyor. Paylaşılan durum yavaştır ve ölçeklenebilirliği bozar.
    Yakın zamanda C++20 coroutine’leriyle Swift actors’a benzer bir şey uygulayan header-only bir kütüphane yazdım. İlgilenirseniz “coroactors” diye aratabilirsiniz. Çekişme yokken saniyede yaklaşık 10 milyon istek, çekişme varken ve scheduler’a dayanıldığında saniyede 1 milyon–3 milyon istek bile overhead’in fazla büyük olduğunu düşündürdü. Özellikle mutex ile korunan paylaşılan durum üzerindeki sıradan metot çağrılarıyla karşılaştırınca böyle. Coroutine’ler bulaşıcı olmaya yatkın; giderek daha fazla fonksiyon async coroutine hâline geliyor ve önemsiz olmayan kod tabanlarında coroutine çağrıları veya ileti aktarımı çoğalıyor. Bu yüzden overhead mümkün olduğunca düşük olmalı; aksi hâlde yararlı iş yapmaktan çok görev değiştirmeye zaman harcanır.

  • Actor tabanlı olduğu belirtiliyor ve bir actor’a mesaj göndermenin, actor işlevini bir mutex altında çalıştırmaya eşdeğer olduğu açıklanıyor. Yani N iş parçacığı mesaj gönderse bile actor kodunu çalıştıran iş parçacığı 1 tane olduğundan, mutex gibi seri hâle getiriliyor.
    Bu yüzden teknik olarak “tamamen lock-free” olabilir, ama actor kullandığınız sürece paralelleştirme iyileşmesi yok

    • Mutlaka öyle değil. Mutex tabanlı bir actor’da actor iş parçacığı duraklatılırsa, özgün iş parçacığı devam edene kadar o mutex, yani actor kodu kilitli kalır. Duraklatılmış iş parçacığının sahip olduğu mutex kilitli olduğundan, daha fazla paralellik olsa bile o actor kodu “yeniden başlatılamaz” ya da “sürdürülemez”.
      Bu implementasyon, hâlihazırda ilerlemekte olan ama duraklatılmış bir actor’ın işini başka bir paralel iş parçacığının alıp sürdürebilmesi için büyük ölçüde yeniden başlatılabilir işlevlere dayanıyor. Harika tasarım belgesinin 3. sayfasına bakılabilir: https://github.com/eduard-permyakov/peredvizhnikov-engine/bl...
      Bu yüzden katı anlamda “daha paralel” olmayabilir (actor sayısı aynı olduğundan), ama aynı iş kümesini tamamlamak için mevcut paralelliği daha iyi kullanıyor gibi görünüyor.
    • “Actor’a mesaj göndermek, actor işlevini bir mutex altında çalıştırmaya eşdeğerdir” ifadesi nerede geçiyor? Benim anladığım kadarıyla actor modeli mesaj iletimi ve asenkron yürütme anlamına geliyor. Aksine, N actor varsa N iş parçacığı paralel çalışabilir.
    • Paralelleştirme iyileşmesi olmadığı doğru, ama paralelliği azalttığı da yok. Eşzamanlılığı düşünmenin başka bir yolu ve bana göre daha kolay bir yolu.
      Düşünmesi kolaysa aynı kaynaklarda nerede çekişme oluşacağını da daha iyi görürsünüz ve bu, pratikte potansiyel paralelliği iyileştirmeye yardımcı olur. SMP’nin hızı artırabileceği belirli bir fırsatı fark ederseniz actor modelinden biraz sapıp mesaj kuyruğunu birden çok iş parçacığının almasını sağlayabilirsiniz; bu mümkün değilse daha fazla actor ekleyip veriyi daha iyi bölersiniz.

  • STM’nin yoğun çekişmeli kritik bölgelerini geleneksel bir mutex implementasyonuyla karşılaştırarak debug veya profil etmiş olan var mı? Sonuçta paylaşımlı belleğe eşzamanlı erişimi arabulacak bir şeye ihtiyaç var ve bedava öğle yemeği yok. Mutex’ler optimizasyonu, profillemesi ve anlaşılması çok iyi yapılmış şeyler.
    Buna karşılık STM’nin de aynı seviyede olup olmadığından emin değilim. Transaction’lar sonsuza kadar(?) yeniden denenebilir değil mi?

    • Bu durumda arabulucu scheduler. Aslında asenkron bloğu çağıran ve başarısız olursa potansiyel olarak yeniden deneyen taraf o. Orijinal koddaki atomic bloklar, blokların sıralı yürütülmesi, durum taşıyan bloklar vb. tek seferde tek erişimi garanti etmek için var.
      Kilit nokta scheduler.cpp ve std::coroutines kullanıyor.
      Diğer dillerdeki async/awaite benziyor. Scheduler’da bir iş (coroutine) kuyruğu ve bunları çalıştıran bir iş parçacığı havuzu (N>0) var.
      Burada veri taşıyan işler birbirine mesaj gönderiyor. Bellek kullanımının artması pahasına kilide ihtiyaç yok.
    • Aslında aç kalma olmayan STM’lerde transaction yeniden deneme sayısı sınırlıdır. Bir örnek 2PLSF; başka birçok yöntem de var: https://zenodo.org/record/7886718

  • BEAM havası var gibi?
    https://youtu.be/bo5WL5IQAd0?feature=shared

  • Böyle bir motoru debug etmenin ne kadar zor olduğundan bahsedildiğini görmedim.

  • Implementasyonu okumaya zamanım yok ama yalnızca README’ye bakınca, oyun iş parçacıkları arasında klasik bir dağıtık sistem gibi duruyor. Retry-backoff gibi kalıplar yaygın olacakmış gibi.

  • Lock-free kulağa havalı geliyor ama bence anlamlı ölçüde atomic operations kullanan kodun, biçimsel ve mümkünse makineyle doğrulanmış bir kanıtla birlikte gelmesi gerekir. Sequential consistency olmayan atomic ordering’i doğru kullanmak fazla zor. Yanlış yazılmış kodu defalarca gördüm ve bundan doğan bug’lar en kötüsü.

  • Oyun demosu nerede? Günümüzde buna game engine diyebilmek için gerçek araçlar, Maya veya 3DSMax gibi exporter’lar ve iş birliği araçları, metrikler, bildirimler gibi şeyler de gerekiyor.

    • Katılmıyorum. “Game engine” ille de “Unity veya Unreal’ın yerine geçebilecek şey” demek değildir.

  • “Lock-free” deniyor ama henüz öyle değil gibi.
    export std::mutex iolock{};
    export std::mutex errlock{};
    SDL_PollEvent