JavaScript ile 20 milyon parçacık simüle etmek

 (dgerrells.com)
4 puan yazan GN⁺ 2024-07-09 | 1 yorum | WhatsApp'ta paylaş
  • Yalnızca CPU kullanan bir JavaScript parçacık simülasyonundan başlayıp, telefonda 1 milyon parçacığı 60fps hedefini yakaladı ve son örnek 20 milyon parçacığa kadar ölçeklendi
  • Performansın anahtarı, nesne dizilerinden kaçınarak parçacık verilerini TypedArray ve SharedArrayBuffer ile bitişik bellekte tutmak ve Web Worker ile işi CPU çekirdeklerine bölmekti
  • Asıl darboğaz, parçacık konumlarını hesaplamaktan çok ekran çizimi ve bellek erişiminde ortaya çıktı; piksel arabelleğine rastgele yazmalar CPU cache miss’lerine yol açtı
  • Worker başına piksel arabelleği, postMessage senkronizasyonu, çift arabellekleme, piksel başına parçacık sayısı grid’i ve GPU texture rendering ile darboğazlar adım adım azaltıldı
  • Nihai yapıda CPU simülasyonu yapıyor, GPU ise ekran çözünürlüğü boyutunda bir grid texture’ını render ediyor; M1 Mac’te 20 milyon parçacık yaklaşık 20fps ile işleniyor

Hedef ve temel yaklaşım

  • Zorluk, WebAssembly olmadan saf JavaScript ve yalnızca CPU ile 1 milyon parçacığı telefonda 60fps ile simüle etmekti
  • Basit bir JavaScript nesne dizisinin mobilde tek çekirdek performansı ve bellek yerleşimi açısından sınırlı olduğunu düşünerek, verileri bitişik diziler olarak ele alma yaklaşımı seçildi
  • Büyük ölçekli hesaplamalarda CPU önbelleğine mümkün olduğunca çok veri sığdırabilen sıkı, bitişik bellek dizileri önemlidir
  • JavaScript’in normal dizileri ve nesnelerinin, düşük seviyeli dillerdeki diziler veya struct’lar gibi yoğun biçimde yerleştirildiğini garanti etmek zordur
  • TypedArray, sabit boyutlu bitişik bayt dizileri oluşturabildiği için JavaScript’te nispeten düşük seviyeli bellek yönetimini mümkün kılar

İlk uygulama: SharedArrayBuffer ve Web Worker

  • Parçacık verileri, SharedArrayBuffer üzerine bir Float32Array görünümü geçirilerek saklandı
    • Bir parçacık x, y, dx, dy olmak üzere dört adet 32 bit kayan nokta değeriyle temsil edildi
    • Düz arabelleği indekslemek için stride = 4, byte_stride = stride * 4 kullanıldı
  • Simülasyon, her karede x += dx, y += dy yapan basit bir konum güncellemesiyle başladı
  • Çok iş parçacıklılık Web Worker ve SharedArrayBuffer ile kuruldu
    • Ana thread, parçacık chunk’larını Worker’lara böldü
    • Worker’ların yalnızca kendilerine ayrılan chunk’ı okuyup yazması sağlanarak birden fazla thread’in aynı bellek konumuna yazması önlendi
  • SharedArrayBuffer’ı tarayıcıda kullanmak için şu header’lar gerekir
    • Cross-Origin-Embedder-Policy: require-corp
    • Cross-Origin-Opener-Policy: same-origin
  • İlk senkronizasyon için ayrı bir sinyal SharedArrayBuffer kullanıldı
    • Ana thread Worker’a çalıştırma sinyali yazdı
    • Worker, setInterval(..., 1) ile sinyali kontrol etti ve iş bitince hazır durumunu kaydetti
  • Rendering, CPU tabanlı bir rasterizer gibi ImageData kullanılarak işlendi
    • Her parçacık ekranda tek bir piksel olarak çizildi
    • Ekran dışındaki parçacıklar atlanarak dizi sınırı dışına erişim önlendi
    • Sonuç Canvas’a putImageData ile çizildi
  • İlk profillemede Worker işi birkaç ms düzeyindeydi; zamanın çoğu ana thread rendering için harcanıyordu
  • Bellek başlangıçta bir kez ayrıldı ve simülasyon döngüsünde yeni nesne oluşturulmadığı için neredeyse hiç garbage oluşmadı

İkinci uygulama: girdi ve yerçekimine benzer etkileşim

  • Girdi verileri, mevcut simülasyon durumu için kullanılan SharedArrayBuffer’a eklendi
    • Delta time, fare x/y, dokunma durumu, ekran genişliği/yüksekliği saklandı
    • Dokunma durumu boolean’a yakın bir değer olsa da 4 bayt kullandı
  • Ekrana basıldığında parçacıkların dokunma noktasına çekilmesi efekti eklendi
    • Gerçek yerçekimi formülündeki 1 / r² biçimi referans alındı, ancak doğru fizik simülasyonundan çok eğlenceli bir etkileşim hedeflenerek değiştirildi
    • Sürtünmeye karşılık gelen sönümleme eklenerek parçacıkların sonsuza dek hızlanıp ekran dışına fırlaması engellendi
  • Rendering rengi, parçacık konumuna göre değişecek şekilde düzenlendi
    • RGB kanal değerleri x / width, y / height değerleri kullanılarak ayarlandı
    • Parçacık başına renk ayrıca saklanırsa parçacık boyutu büyüyeceğinden, veri boyutunu azaltmak için konum tabanlı renk kullanıldı
  • 2 milyon parçacığa kadar deneme yapılabildi ve URL’deki count query parametresiyle parçacık sayısının değiştirilebilmesi sağlandı
  • 10 milyon parçacıkta kare hızı düştü; profilleme sonucu Worker’dan çok ImageData piksel yazma işleminin yavaş kısım olduğu görüldü
  • RGB’nin tamamını yazmak yerine yalnızca mavi ve alfa kanallarını yazacak şekilde değiştirince, bazı ortamlarda render süresi yaklaşık 80~90ms’den 16~18ms’ye düştü
    • Bu fark CPU’ya göre değişiyordu ve M1 MacBook Air’e kıyasla masaüstü Ryzen’da daha belirgindi

Üçüncü uygulama: Worker’da piksel arabelleği yazma

  • Daha fazla CPU çekirdeğinden yararlanmak için Worker’ların yalnızca simülasyonu değil, piksel çizimini de üstlenmesi sağlandı
  • Birden fazla Worker’ın aynı piksel arabelleğine aynı anda yazmaması için Worker başına piksel arabelleği kullanıldı
    • CPU_CORES * window.innerWidth * window.innerHeight * 3 boyutunda bir SharedArrayBuffer kullanıldı
    • Her Worker, ekranın tamamı için bir RGB arabelleğine sahipti
  • Ana thread, Worker başına piksel arabelleklerinin tümünü topladıktan sonra ImageData’ya yazdı
  • Bu sürümde ekranda titreme oluştu
    • Worker kendi piksel arabelleğini fill(0) ile temizlerken ana thread aynı arabelleği okuyordu
    • Önceki rendering de eski verileri okuyabiliyordu, ancak kareler arası fark göze çarpmıyordu; bu kez Worker’ın temizleme işlemi ekranın bazı kısımlarında titreme olarak ortaya çıktı
  • Çözüm adayları Atomics tabanlı senkronizasyon, Worker’ın bitmesini postMessage ile bekleme ve çift arabellekleme idi

Dördüncü uygulama: postMessage tabanlı senkronizasyon

  • Titremeyi gidermek için sinyal dizisi bırakıldı ve Worker’ın bitişini postMessage ile bildirmesi sağlandı
  • Ana thread activeWorkers değerini yönetti
    • Her Worker bittiğinde mesaj gönderdi ve activeWorkers azaltıldı
    • Tüm Worker’lar bitince render edildi ve bir sonraki requestAnimationFrame istendi
  • Bu yöntemle titreme çözüldü
  • Kare süresi belirgin biçimde iyileşmedi, hatta kötüleşebiliyordu
    • Çünkü ana thread Worker’ın bitmesini beklerken hiçbir iş yapmıyordu
    • 2 milyon parçacık için Worker ana thread rendering’i beklemezse yaklaşık 7ms kazanılabilecek durumlar vardı
  • Bu darboğazı azaltmak için grafik sürücülerinde yaygın olan çift arabellekleme uygulandı

Beşinci uygulama: çift arabellekleme ve cache darboğazı

  • Çift arabellekleme, iki piksel arabelleği oluşturup her karede aktif arabelleği değiştirme yöntemidir
    • Ana thread bir arabelleği çizerken Worker diğer arabellekte sonraki kareyi hazırlar
  • Uygulamadan sonra Worker ana thread rendering’ini beklemez oldu ve daha önce 50ms’yi aşan bazı kareler 16ms’ye daha yakın hale geldi
  • Hâlâ yavaş olan kod, piksel arabelleğinin RGB kanallarına değer ekleyen üç satırdı
  • Nedeni, veri bitişik saklansa bile erişim sırasının bitişik olmamasıydı
    • Parçacığın x, y değerlerinden hesaplanan pixelIndex, parçacık dizisinin sırasıyla hizalı değildi
    • Her döngüde piksel arabelleğinde rastgele bir konuma atlanıyor, rastgele erişime yakın bir desen oluşuyordu
  • Bu erişim deseni, parçacık verileri ve piksel verileri önbelleğe birlikte sığmadığında cache miss’e yol açar
  • iPhone için örnek hesaplama şöyleydi
    • Formül: screen width * screen height * bytes per pixel + bytes per particle * total particles / number of workers
    • 2532 * 1170 * 3 + 16 * 2,000,000 / 5
    • Sonuç 15MB’yi aşıyor ve L1 cache’e sığmak için fazla büyük
  • Bu sürümde M1 çipte 2 milyon parçacık simülasyonu yaklaşık 4ms, piksel verilerine erişim yaklaşık 3,5ms, piksel arabelleğine yazma yaklaşık 7ms sürdü
  • Telefonda 1 milyon parçacık 60fps’te tutulabildi; ancak 20’den fazla thread’i olan masaüstünde ana thread her karede 20’den fazla piksel arabelleğini topladığı için 30ms harcıyordu

Altıncı uygulama: başlangıç konumuna geri çeken kuvvet

  • Yeni efekt, parçacıkların başlangıç konumundan uzaklaştıkça daha güçlü biçimde geri çekilmesini sağlamaktı
  • Bunun için parçacığa başlangıç konumu olarak sx, sy değerleri eklendi
    • Bir parçacık x, y, dx, dy, sx, sy olmak üzere altı float’a sahip oldu
    • particleStride = 6 değerine çıkarıldı
  • Worker koduna kuvvet hesaplama fonksiyonu eklendi ve garbage oluşmasını önlemek için cache nesnesi kullanıldı
  • Sonuç, jöle veya akışkan benzeri bir görsel efekt üretti; parçacıklar buruşmuş kâğıt ya da kumaş gibi girdaplar gösterdi
  • Bu süreçte piksel arabelleğini Worker başına saklamak yerine, yalnızca piksel başına parçacık sayısını tutan bir grid’e geçme fikri ortaya çıktı

Yedinci uygulama: piksel başına parçacık sayısı grid’i

  • RGB değerleri saklamak yerine her piksel konumundaki parçacık sayısını saklamak belleği 1/3’e düşürebilir
  • Renk, parçacık başına veri olarak değil x, y konumundan hesaplandığı için piksel başına count ile render edilebilir
  • Tüm Worker’ların tek bir parçacık sayısı grid’ini paylaşması sağlandı
    • Worker başına arabellekleri toplayan ana thread işi ortadan kalktı
    • Worker sayısı arttığında render toplama maliyetinin büyümesi sorunu çözüldü
  • Yeni cache hesaplama formülü şöyleydi
    • screen width * screen height + bytes per particle * total particles / number of workers
    • iPhone için 2532 * 1170 + 16 * 2,000,000 / 5
    • Yaklaşık 9,3MB; önceki yaklaşımdan yaklaşık %30 daha az, ancak L1 cache için hâlâ büyük
  • Rendering, tüm pikselleri dolaşıp ilgili pikselin parçacık sayısını okuyor, RGB değerini hesaplıyor ve ardından grid’i fill(0) ile sıfırlıyordu
  • Worker simülasyondan sonra ekran içindeki parçacığın pCountIndex değerini hesapladı ve activeGrid[pCountIndex]++ yaptı
  • Bu değişiklik özellikle Worker sayısı çok olduğunda yardımcı oldu ve masaüstünde 24 thread’in tamamı kullanılabilir hale geldi
  • Yine de M1 MacBook Air’in Ryzen 9 3900X masaüstünden hızlı olduğu durumlar vardı
    • Ryzen 9 3900X’in L3 cache’i 64MB, ancak L1’i 64KB’dir
      1. nesil M1’in L1 cache’i 320KB’dir; bunun 128KB’si veri, 192KB’si komutlar içindir
    • Daha büyük L1 veri cache’inin bellek bekleme süresini azaltmada avantaj sağladığı düşünülüyor

Yalnızca CPU optimizasyonunun sınırı

  • Çeşitli optimizasyonlar sonucunda, ilk çok thread’li sürüme kıyasla yaklaşık 2 kat hız artışı elde edildi
  • Telefonda CPU tabanlı 1 milyon parçacığı 60fps ile yalnızca JavaScript kullanarak işleme hedefi başarıldı
  • Genel sonuçlar özellikle etkileyici bir düzeyde değil; derlenen bir dilde 10 kat daha hızlı olması beklenir
  • Tight loop’larda SIMD komutları kullanılabilse daha da hızlanma payı var
  • Sonraki adımda simülasyon CPU’da bırakılıp yalnızca rendering geleneksel GPU pipeline’ına taşınarak karşılaştırıldı

20 milyon parçacık ve GPU rendering

  • İlk GPU rendering karşılaştırması, threejs’in GPU instancing özelliğiyle her parçacık için plane/quad çizme yöntemiydi
  • Bu yöntem beklenenden düşük performans gösterdi
    • threejs instancing, her parçacık konumu için matris güncellemeyi gerektiriyor ve bu iş CPU’da tek thread’de yapılıyor
    • Parçacık dönüşüm verilerinin her karede GPU’ya yüklenmesi gerekiyor ve bu aktarım yavaş
  • M1 çipte 4 milyon parçacık simüle edilirken kare süresinin %80’i verileri GPU’ya göndermeye harcandı
  • Masaüstünde veri aktarımının payı %30’du, ancak hâlâ en büyük darboğazdı
  • Alternatif, daha önce oluşturulan parçacık sayısı grid’ini texture olarak kullanıp tam ekran quad render etmekti
    • GPU’ya gönderilen veri miktarı parçacık sayısına değil, ekran çözünürlüğüne sabitlenir
    • Büyük simülasyonlarda aktarım miktarı azalır, ancak küçük simülasyonlarda daha fazla veri gönderilebilmesi bir ödünleşmedir
  • threejs ve özel bir pixel shader ile hızlıca uygulandığında, ana thread rendering’i simülasyon boyutundan bağımsız olarak birkaç ms düzeyine indi
  • Bu yapıda Worker olabildiğince hızlı çalışıyor ve simülasyon hem büyük hem küçük ölçekte doğrudan CPU çekirdeği sayısına bağlı kalıyor
  • Her Worker zamanının yaklaşık %50’sini sayısal hesaplamaya, yaklaşık %50’sini parçacık grid count güncellemesine harcıyor
  • Nihai sürümün performansı şöyle
    • M1 Mac pildeyken 20 milyon parçacığı yaklaşık 20fps ile çalıştırıyor
    • Masaüstü benzer fps’te yaklaşık 30 milyon parçacığı işliyor
    • 32 çekirdekli CPU’ya sahip bir arkadaşın testinde yaklaşık 40 milyon parçacığa ulaşıldı
  • İlgili demolar:

Özet

  • CPU ve GPU sayısal hesaplamaları çok hızlı işleyebilir
  • Yavaş kısım veriyi taşımak ve özellikle rastgele bellek erişimidir
  • Hızlı kod yazmak için donanımın verileri nasıl cache’lediğini ve taşıdığını bilmek gerekir
  • SharedArrayBuffer ve Web Worker, JavaScript’te birden fazla çekirdekten yararlanma denemeleri için kullanışlıydı
  • WebGPU daha yaygın benimsendiğinde compute shader denemeyi planlıyor

İlgili okumalar

1 yorum

 
GN⁺ 2024-07-09
Hacker News yorumları

  • Blogun içine simülasyonu doğrudan gömmek iyi olurdu
    Gerçek simülasyon bağlantısını bulana kadar epey yukarı aşağı kaydırmak zorunda kaldım
    Eski telefonlarda bile makul çalışan değerler seçilebilir, kare hızına göre ayarlanabilir hale getirilebilir ya da yazının üst kısmına birkaç bağlantı konabilir
    https://ciechanow.ski/ yazının içine simülasyon koymanın ne kadar harika olabileceğini gösteren dünya çapında bir örnek
    Eskiden bütün web siteleri böyle harika etkileşimli öğeler gömerdi
    Ayrıca WebGPU olmadan da GPU üzerinde parçacık simülasyonu çalıştırılabileceğini düşünüyorum
    Örnek: https://news.ycombinator.com/item?id=19963640

    • Şimdiye kadar gördüğüm açıklayıcı bloglar arasında en üst düzey örneklerden biri
      Keşke bilgi paylaşımının standardı böyle olsa. Paylaşmaya değiyorsa, anlaşılır hale getirmeye de değer
    • Şu akışkan simülasyonu gerçekten şaşırtıcı
    • Gömmenin iyi olduğu konusunda katılıyorum
      Her sürümü gömmeyi düşündüm ama aynı anda çok fazla worker çalışmasından endişelendim
      Yazının sonuna nihai sürümü gömecek şekilde güncelleyeceğim
      O blogda her örnek inanılmaz derecede özenli ve gerçekten iyi
      Düzenleme: Gömülü sürüm eklemeyi denedim ama gereken header’lar diğer embed’lerle pek uyumlu olmadı ve eski sürümler hâlâ codesandbox’a bağlı
    • “Nihai uygulamayla oynamak için sona atlayın” diye yönlendirmek yeterli

  • Mobil demoda [0] bizzat deneyince oldukça şaşırtıcı
    [0] https://dgerrells.com/sabby

    • Birden fazla parmakla da çalışıyor
      Saf JavaScript ile bu seviyede olması şaşırtıcı; parmak sayısı arttıkça gecikmenin büyümesine bakılırsa thread’ler arasında gidip gelen veri de artıyor gibi
    • Garip biçimde organik görünüyor; ilkel çorba içindeki lipit yapılar gibi
    • Telefonumda Firefox’un Chrome’dan daha iyi çalışması hoşuma gitti

  • Tamamen meraktan soruyorum: Her parçacığı x, y, dx, dy şeklinde dört 32 bit kayan noktalı sayı olarak temsil etmek yerine bu veriyi tek bir JS sayısına kodlamak mümkün olur mu acaba
    JS’in güvenli tamsayı aralığı 2^53 - 1 = 9,007,199,254,740,991, yazıda kullanılan Float32Array aralığı ise -3.4e38 ile 3.4e38 arası
    Örneğin ekran konumu 1000x1000 bir canvas ise 0~1.000.000 arası sayıyla ifade edilebilir; buna 10 kademeli alt piksel hassasiyeti ekleseniz bile 100.000.000 sayı eder ve JS aralığına rahatça sığar
    dx, dy hızları da (Math.random()*2-1)*10 ile -10 ile +10 arasında rastgele ondalık olarak hesaplanıyor; ama bir ondalık basamakla sınırlamak yeterliyse -100~+100 tamsayı aralığına dönüştürülebilir ve olası değerler için 10.000 sayı yeter
    İkisini birleştirince 10,000 * 100,000,000 = 1,000,000,000,000, yani 1 trilyon sayı ile bir parçacık temsil edilebilir; bu da JS’in MAX_SAFE_INTEGER sınırı içinde kalır
    Bu yüzden tek bir parçacık verisini bir MAX_SAFE_INTEGER içine ya da tek bir Float32Array öğesine sığdırmak mümkün gibi; böylece stride gerekmez ve veri tutarlılığı da daha kesin olabilir
    Yine de kodlama/kod çözme maliyeti bellek tasarrufundan büyük olup performans açısından hiç değmeyebilir

  • Gerçekten harika, ama şu kısmı merak ettim
    Javascript does support an Atomics API but it uses promises which are gross. Eww sick.
    waitAsync[1] dışında Atomics API promise kullanmıyor gibi görünüyor
    Daha önce Atomics kullanmıştım ama asenkron/promise koduyla uğraşmam gerekmemişti
    İçeride promise kullanıp kullanmadığını, yoksa kaçırdığım bir nokta mı olduğunu merak ediyorum
    [1] https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...

  • Neredeyse 20 milyon parçacığı ele alan bir simülasyon da var
    Çalıştırıp programlayabilirsiniz: https://tinlizzie.org/~ohshima/shadama2/
    https://tinlizzie.org/~ohshima/shadama2/live2017/
    https://www.youtube.com/watch?v=tqBO_5GMfWw

  • Video harika, ancak try it out here içindeki codesandbox bağlantıları MacOS Chrome masaüstünde çalışmıyor
    Uncaught ReferenceError: SharedArrayBuffer is not defined ve ERR_BLOCKED_BY_RESPONSE.NotSameOriginAfterDefaultedToSameOriginByCoep gibi CORS hataları çıkıyor

    • codesandbox’un satır içi düzenleyicisi header ayarlarını engellediği için önizlemeyi ayrı bir sekmede açmak gerekiyor
      Gizlilik odaklı bir tarayıcı kullanıyorsanız engellenebilir
      İleride gömülü örnekleri de eklemeyi deneyeceğim
      Son sürümü burada deneyebilirsiniz: https://dgerrells.com/sabby

  • Harika
    Kodu anlamak ve kurcalamak için bir saat harcadım; burada canlı bir uygulama oluşturdum: https://particules.kapochamo.com/index.html

    • İlk açtığımda şaşırıp kaldım
      Gerçekten çok güzel ve JS’te bu kadar çok parçacığı simüle etmek inanması zor bir şey
    • Güzel
      Koda bu kadar derinlemesine dalman etkileyici

  • chrome://tracingin daha fazla içgörü sağlayıp sağlamadığını kontrol etmeye değer
    Bunu buradan öğrendim: https://youtu.be/easvMCCBFkQ?t=114

  • Bunu yavaş React uygulamaları yapan UI ekibine hemen göndermek istiyorum
    JS gerçekten hızlı; özellikle iyi yazıldığında inanılmaz hızlı

    • Sorun şu ki, deyimsel JS ile hızlı JS pratikte neredeyse birbirinin tam tersi
      Hızlı JS kötü bir C lehçesi gibi görünüyor ve çöp toplayıcılı nesne tahsisi yapmamak gerekiyor; dilde ise tahsis gerektirmeyen iyi alternatifler eksik
      Karmaşık JS uygulamalarında tüm bellek tahsislerini dev bir ArrayBuffer içindeki pointer’larla yönetecek çok az kişi vardır; bunu yapacaksanız WebAssembly’ye geçmek daha kolay
    • JavaScript, çeşitli motor optimizasyonlarına harcanmış insan saati muhtemelen en fazla olan dil
      Üzücü olan, yalnızca JS’e güvenemeyip bolca DOM manipülasyonu karıştırmak zorunda kalmamız; yaptığımız UI’larda genellikle yavaş olan kısım da bu DOM manipülasyonu