20 Millionen Partikel mit JavaScript simulieren

 (dgerrells.com)
4 Punkte von GN⁺ 2024-07-09 | 1 Kommentare | Auf WhatsApp teilen
  • Ausgehend von einer JavaScript-Partikelsimulation, die nur die CPU nutzt, wurde das Ziel von 1 Million Partikeln bei 60 fps auf dem Smartphone erreicht, und das finale Beispiel wurde bis auf 20 Millionen Partikel skaliert
  • Der Schlüssel zur Performance war, Arrays von Objekten zu vermeiden und die Partikeldaten mit TypedArray und SharedArrayBuffer in zusammenhängendem Speicher zu halten sowie die Arbeit mit Web Workern auf CPU-Kerne zu verteilen
  • Der eigentliche Flaschenhals zeigte sich stärker beim Zeichnen auf dem Bildschirm und beim Speicherzugriff als bei der Berechnung der Partikelpositionen; zufällige Schreibzugriffe in den Pixelpuffer verursachten CPU-Cache-Misses
  • Mit Pixelpuffern pro Worker, Synchronisierung per postMessage, Double Buffering, einem Grid für Partikel pro Pixel und GPU-Textur-Rendering wurden die Engpässe schrittweise reduziert
  • Die finale Architektur lässt die CPU simulieren und die GPU ein Grid-Texture in Bildschirmauflösung rendern; auf einem M1 Mac werden 20 Millionen Partikel mit etwa 20 fps verarbeitet

Ziel und grundlegender Ansatz

  • Die Herausforderung bestand darin, ohne WebAssembly nur mit reinem JavaScript und der CPU 1 Million Partikel auf einem Smartphone mit 60 fps zu simulieren
  • Da einfache JavaScript-Objektarrays sowohl bei der Single-Core-Leistung auf Mobilgeräten als auch beim Speicherlayout Grenzen haben, fiel die Wahl auf einen Ansatz mit zusammenhängenden Arrays
  • Bei großen Rechenmengen sind dichte, zusammenhängende Speicherarrays wichtig, damit möglichst viele Daten im CPU-Cache liegen können
  • Bei normalen JavaScript-Arrays und -Objekten ist schwer zu garantieren, dass sie so dicht angeordnet sind wie Arrays oder struct in Low-Level-Sprachen
  • TypedArray kann ein zusammenhängendes Byte-Array fester Größe erzeugen und ermöglicht damit in JavaScript eine vergleichsweise Low-Level-nahe Speicherverwaltung

Erste Implementierung: SharedArrayBuffer und Web Worker

  • Die Partikeldaten wurden in einer Float32Array-View auf einem SharedArrayBuffer gespeichert
    • Ein Partikel wird durch vier 32-Bit-Gleitkommazahlen dargestellt: x, y, dx, dy
    • Ein flacher Puffer wird mit stride = 4 und byte_stride = stride * 4 indiziert
  • Die Simulation begann mit einem einfachen Positionsupdate pro Frame: x += dx, y += dy
  • Multithreading wurde mit Web Workern und SharedArrayBuffer umgesetzt
    • Der Main Thread teilt den Workern jeweils Chunks von Partikeln zu
    • Jeder Worker liest und schreibt nur den ihm zugewiesenen Chunk, damit nicht mehrere Threads dieselbe Speicherstelle beschreiben
  • Um SharedArrayBuffer im Browser zu verwenden, sind folgende Header nötig
    • Cross-Origin-Embedder-Policy: require-corp
    • Cross-Origin-Opener-Policy: same-origin
  • Die anfängliche Synchronisierung nutzte einen separaten SharedArrayBuffer für Signale
    • Der Main Thread schreibt ein Startsignal für die Worker
    • Die Worker prüfen das Signal mit setInterval(..., 1) und markieren nach Abschluss ihre Bereitschaft
  • Das Rendering wurde mit ImageData wie ein CPU-basierter Rasterizer umgesetzt
    • Jedes Partikel wird als ein Pixel auf dem Bildschirm gezeichnet
    • Partikel außerhalb des Bildschirms werden übersprungen, um Zugriffe außerhalb der Array-Grenzen zu vermeiden
    • Mit putImageData wird das Ergebnis auf das Canvas gezeichnet
  • Frühes Profiling zeigte, dass die Worker-Arbeit nur wenige ms dauerte und der Großteil der Zeit für das Rendering im Main Thread draufging
  • Der Speicher wurde nur einmal beim Start allokiert, und in der Simulationsschleife wurden keine neuen Objekte erzeugt, wodurch kaum Garbage entstand

Zweite Implementierung: Eingabe und gravitationsähnliche Interaktion

  • Die Eingabedaten wurden in den bestehenden SharedArrayBuffer für den Simulationszustand integriert
    • Gespeichert wurden Delta-Zeit, Maus-x/y, Touch-Status sowie Bildschirmbreite/-höhe
    • Der Touch-Status ist zwar boolean-ähnlich, belegt aber 4 Byte
  • Beim Tippen auf den Bildschirm wurde ein Effekt hinzugefügt, bei dem die Partikel zum Berührungspunkt gezogen werden
    • Als Vorlage diente die reale Gravitationsformel 1 / r², sie wurde aber für eine interessante Interaktion statt für physikalische Genauigkeit angepasst
    • Zusätzlich wurde eine Dämpfung als Reibung eingebaut, damit die Partikel nicht unendlich beschleunigen und aus dem Bildschirm fliegen
  • Die Renderfarbe wurde so geändert, dass sie sich je nach Partikelposition verändert
    • Die RGB-Kanalwerte werden über x / width und y / height angepasst
    • Würde man Farben pro Partikel speichern, würden die Partikeldaten größer; deshalb wurde positionsbasierte Färbung gewählt
  • Es konnte mit bis zu 2 Millionen Partikeln experimentiert werden, und über den URL-Query-Parameter count ließ sich die Partikelzahl verändern
  • Bei 10 Millionen Partikeln fiel die Framerate deutlich ab, und Profiling zeigte, dass ImageData-Pixelschreiben langsamer war als die Worker
  • Statt vollständigem RGB wurden nur noch Blau- und Alpha-Kanal geschrieben; dadurch sank die Renderzeit in manchen Umgebungen von etwa 80–90 ms auf 16–18 ms
    • Dieser Unterschied hing von der CPU ab und war auf einem Desktop-Ryzen größer als auf einem M1 MacBook Air

Dritte Implementierung: Pixelpuffer in Workern schreiben

  • Um mehr CPU-Kerne zu nutzen, übernahmen die Worker nicht nur die Simulation, sondern auch das Zeichnen der Pixel
  • Damit nicht mehrere Worker gleichzeitig in denselben Pixelpuffer schreiben, bekam jeder Worker einen eigenen Pixelpuffer
    • Verwendet wurde ein SharedArrayBuffer der Größe CPU_CORES * window.innerWidth * window.innerHeight * 3
    • Jeder Worker besitzt einen vollständigen RGB-Puffer für den gesamten Bildschirm
  • Der Main Thread summiert anschließend alle Pixelpuffer der Worker und schreibt sie in ImageData
  • In dieser Version trat Bildschirmflackern auf
    • Während ein Worker seinen Pixelpuffer mit fill(0) löschte, las der Main Thread denselben Puffer
    • Auch das frühere Rendering konnte veraltete Daten lesen, aber die Unterschiede zwischen Frames fielen kaum auf; hier wurde das Löschen der Worker als partielles Flackern sichtbar
  • Als mögliche Lösungen kamen Synchronisierung per Atomics, Warten auf Worker-Abschluss per postMessage oder Double Buffering infrage

Vierte Implementierung: Synchronisierung per postMessage

  • Um das Flackern zu beseitigen, wurde das Signal-Array verworfen und stattdessen per postMessage gemeldet, wenn ein Worker fertig ist
  • Der Main Thread verwaltet dabei einen Wert activeWorkers
    • Jeder Worker sendet nach Abschluss eine Nachricht, wodurch activeWorkers dekrementiert wird
    • Wenn alle Worker fertig sind, wird gerendert und das nächste requestAnimationFrame angefordert
  • Damit war das Flackern gelöst
  • Die Frametimes verbesserten sich aber nicht deutlich und konnten sogar schlechter werden
    • Der Grund ist, dass der Main Thread während des Wartens auf die Worker nichts tut
    • Bei 2 Millionen Partikeln gab es Situationen, in denen sich etwa 7 ms sparen ließen, wenn die Worker nicht auf das Rendering des Main Threads warten müssten
  • Um diesen Flaschenhals zu reduzieren, wurde das in Grafiktreibern übliche Double Buffering eingeführt

Fünfte Implementierung: Double Buffering und Cache-Flaschenhälse

  • Double Buffering bedeutet, zwei Pixelpuffer anzulegen und pro Frame zwischen ihnen zu wechseln
    • Während der Main Thread einen Puffer rendert, bereiten die Worker im anderen den nächsten Frame vor
  • Danach mussten die Worker nicht mehr auf das Rendering des Main Threads warten, und manche Frames, die zuvor über 50 ms brauchten, lagen nun näher bei 16 ms
  • Der weiterhin langsame Code waren drei Zeilen, die Werte zu den RGB-Kanälen des Pixelpuffers addierten
  • Die Ursache war, dass die Daten zwar zusammenhängend gespeichert sind, aber nicht in zusammenhängender Reihenfolge angesprochen werden
    • Der aus x und y berechnete pixelIndex ist nicht an die Reihenfolge des Partikelarrays gebunden
    • Dadurch springt die Schleife fast zufällig zu verschiedenen Positionen im Pixelpuffer, also in einem Muster nahe Zufallszugriff
  • Dieses Zugriffsmuster führt zu Cache-Misses, wenn Partikeldaten und Pixeldaten nicht gleichzeitig in den Cache passen
  • Die Beispielrechnung für ein iPhone lautet
    • Formel: screen width * screen height * bytes per pixel + bytes per particle * total particles / number of workers
    • 2532 * 1170 * 3 + 16 * 2,000,000 / 5
    • Das Ergebnis liegt über 15 MB und ist damit viel zu groß für den L1-Cache
  • In dieser Version dauerte auf dem M1-Chip die Simulation von 2 Millionen Partikeln etwa 4 ms, der Zugriff auf Pixeldaten etwa 3,5 ms und das Schreiben in den Pixelpuffer etwa 7 ms
  • Auf Smartphones ließen sich 1 Million Partikel mit 60 fps halten, aber auf Desktops mit mehr als 20 Threads verbrachte der Main Thread 30 ms pro Frame damit, über 20 Pixelpuffer zusammenzurechnen

Sechste Implementierung: Rückstellkraft zur Startposition

  • Der neue Effekt sorgt dafür, dass Partikel umso stärker zurückgezogen werden, je weiter sie sich von ihrer Startposition entfernen
  • Dafür wurden jedem Partikel zwei Startpositionswerte sx und sy hinzugefügt
    • Ein Partikel besitzt nun sechs Floats: x, y, dx, dy, sx, sy
    • particleStride steigt auf 6
  • Im Worker-Code wurde eine Funktion zur Kraftberechnung ergänzt, und um Garbage zu vermeiden, kam ein Cache-Objekt zum Einsatz
  • Das Ergebnis erzeugte visuelle Effekte wie Gel oder Flüssigkeit; die Partikel bildeten Wirbel, die an zerknittertes Papier oder Stoff erinnerten
  • Dabei entstand die Idee, statt Pixelpuffern pro Worker nur noch ein Grid zu speichern, das die Anzahl der Partikel pro Pixel zählt

Siebte Implementierung: Grid für Partikelanzahl pro Pixel

  • Wenn statt RGB-Werten nur die Anzahl der Partikel an jeder Pixelposition gespeichert wird, sinkt der Speicherbedarf auf ein Drittel
  • Da die Farbe nicht aus Partikeldaten, sondern aus der Position x, y berechnet wird, reicht für das Rendering ein Zähler pro Pixel aus
  • Alle Worker teilen sich nun ein gemeinsames Grid für die Partikelanzahl
    • Die Arbeit des Main Threads zum Aufsummieren der Worker-Puffer entfällt
    • Das Problem wachsender Renderkosten bei steigender Worker-Zahl ist damit gelöst
  • Die neue Cache-Formel lautet
    • screen width * screen height + bytes per particle * total particles / number of workers
    • Für das iPhone: 2532 * 1170 + 16 * 2,000,000 / 5
    • Das ergibt etwa 9,3 MB, also rund 30 % weniger als zuvor, aber immer noch zu groß für den L1-Cache
  • Beim Rendering wird über alle Pixel iteriert, die Partikelzahl an dieser Stelle gelesen, daraus RGB berechnet und das Grid anschließend mit fill(0) zurückgesetzt
  • Die Worker berechnen nach der Simulation für sichtbare Partikel den pCountIndex und führen activeGrid[pCountIndex]++ aus
  • Diese Änderung half besonders bei vielen Workern und ermöglichte auf dem Desktop die Nutzung aller 24 Threads
  • Trotzdem war ein M1 MacBook Air in manchen Fällen schneller als ein Ryzen 9 3900X Desktop
    • Der Ryzen 9 3900X hat zwar 64 MB L3-Cache, aber nur 64 KB L1
    • Die erste M1-Generation hat 320 KB L1-Cache, davon 128 KB für Daten und 192 KB für Instruktionen
    • Wahrscheinlich wirkte sich der größere L1-Datencache positiv auf die Speicherlatenz aus

Grenzen der CPU-only-Optimierung

  • Nach mehreren Optimierungen wurde gegenüber der ersten Multithreading-Version ungefähr eine Verdopplung der Geschwindigkeit erreicht
  • Das Ziel, auf einem Smartphone rein CPU-basiert 1 Million Partikel in JavaScript mit 60 fps zu verarbeiten, wurde erreicht
  • Insgesamt ist das Ergebnis nicht außergewöhnlich beeindruckend; mit einer kompilierten Sprache wäre vermutlich die 10-fache Geschwindigkeit möglich
  • Wenn SIMD-Instruktionen in engen Loops nutzbar wären, gäbe es weiteres Beschleunigungspotenzial
  • Im nächsten Schritt blieb die Simulation auf der CPU, während nur das Rendering in eine klassische GPU-Pipeline verlagert wurde, um den Unterschied zu vergleichen

20 Millionen Partikel und GPU-Rendering

  • Der erste GPU-Rendering-Vergleich nutzte in threejs GPU Instancing, bei dem für jedes Partikel eine Plane/ein Quad gezeichnet wird
  • Dieser Ansatz war langsamer als erwartet
    • Bei threejs-Instancing müssen Matrizen pro Partikelposition aktualisiert werden, und diese Arbeit läuft auf einem einzelnen CPU-Thread
    • Außerdem müssen die Transformationsdaten der Partikel in jedem Frame zur GPU hochgeladen werden, was langsam ist
  • Auf einem M1-Chip gingen bei der Simulation von 4 Millionen Partikeln 80 % der Framezeit für das Senden der Daten an die GPU drauf
  • Auf dem Desktop lag dieser Anteil bei 30 %, war aber immer noch der größte Flaschenhals
  • Die Alternative war, das zuvor gebaute Partikelanzahl-Grid als Textur zu verwenden und ein Fullscreen-Quad zu rendern
    • Die zur GPU gesendete Datenmenge ist dann nicht mehr von der Partikelzahl abhängig, sondern fix an die Bildschirmauflösung gebunden
    • Bei großen Simulationen reduziert das die Transfermenge, bei kleinen kann es jedoch ein Trade-off sein und sogar mehr Daten bedeuten
  • Mit threejs und einem benutzerdefinierten Pixel-Shader ließ sich das schnell umsetzen; das Rendering im Main Thread blieb unabhängig von der Simulationsgröße bei wenigen ms
  • In dieser Architektur laufen die Worker so schnell wie möglich, und die Simulation hängt sowohl bei kleinen als auch großen Szenarien direkt von der Zahl der CPU-Kerne ab
  • Jeder Worker verbringt etwa 50 % der Zeit mit numerischer Berechnung und etwa 50 % mit der Aktualisierung der Partikelzähler im Grid
  • Die Performance der finalen Version sieht so aus
    • Ein M1 Mac verarbeitet im Akkubetrieb rund 20 Millionen Partikel mit etwa 20 fps
    • Ein Desktop schafft bei ähnlicher fps-Zahl etwa 30 Millionen Partikel
    • In einem Test eines Freundes mit einer 32-Core-CPU wurden etwa 40 Millionen Partikel erreicht
  • Zugehörige Demos:

Fazit

  • CPU und GPU können numerische Berechnungen sehr schnell ausführen
  • Langsam sind das Verschieben von Daten und insbesondere zufällige Speicherzugriffe
  • Wer schnellen Code schreiben will, muss verstehen, wie Hardware Daten cached und bewegt
  • SharedArrayBuffer und Web Worker waren nützliche Werkzeuge für Experimente mit Mehrkernnutzung in JavaScript
  • Sobald WebGPU breiter verfügbar ist, soll als Nächstes ein Compute Shader ausprobiert werden

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-07-09
Meinungen auf Hacker News

  • Es wäre schön, die Simulation direkt in den Blog einzubetten
    Ich musste ziemlich lange nach oben und unten scrollen, bis ich den Link zur eigentlichen Simulation gefunden hatte
    Man könnte einen Wert wählen, der auch auf älteren Smartphones ordentlich läuft, oder ihn je nach Framerate anpassen lassen; alternativ könnte man einfach ein paar Links oben im Artikel platzieren
    https://ciechanow.ski/ ist ein Weltklasse-Beispiel dafür, wie großartig es sein kann, Simulationen in einen Artikel einzubauen
    Früher haben alle Websites solche coolen interaktiven Elemente eingebettet
    Außerdem denke ich, dass man Partikelsimulationen auch ohne WebGPU auf der GPU laufen lassen kann
    Beispiel: https://news.ycombinator.com/item?id=19963640

    • Eines der besten Beispiele für erklärende Blogs, die ich bisher gesehen habe
      Ich wünschte, das wäre der Standard für den Informationsaustausch. Wenn etwas es wert ist, geteilt zu werden, ist es auch wert, verständlich aufbereitet zu werden
    • Diese Fluidsimulation ist wirklich erstaunlich
    • Ich stimme zu, dass Einbettungen gut wären
      Ich hatte überlegt, jede Version einzubetten, hatte aber Sorge, dass dann zu viele Worker gleichzeitig laufen
      Ich werde den Artikel aktualisieren und am Ende die finale Version einbetten
      Dieser Blog ist wirklich gut, und jedes Beispiel ist unglaublich sauber ausgearbeitet
      Edit: Ich habe versucht, eine eingebettete Version hinzuzufügen, aber die benötigten Header passten nicht gut zu anderen Embeds, und die alten Versionen hängen weiterhin an codesandbox
    • Man könnte einfach schreiben: „Springen Sie ans Ende, wenn Sie mit der fertigen App herumspielen möchten“

  • Ich habe die Mobile-Demo [0] selbst ausprobiert, und sie ist ziemlich beeindruckend
    [0] https://dgerrells.com/sabby

    • Sie funktioniert auch mit mehreren Fingern
      Erstaunlich, dass das mit reinem JavaScript möglich ist; weil die Verzögerung mit mehr Fingern zunimmt, scheint mehr Datenverkehr zwischen Threads stattzufinden
    • Sie sieht seltsam organisch aus, fast wie Lipidstrukturen in einer Ursuppe
    • Auf meinem Smartphone läuft Firefox besser als Chrome, was mich freut

  • Aus reiner Neugier: Ich frage mich, ob man diese Daten in eine einzige JS-Zahl codieren könnte, statt jedes Partikel mit vier 32-Bit-Gleitkommazahlen x, y, dx, dy darzustellen
    Der sichere Integer-Bereich von JS ist 2^53 - 1 = 9,007,199,254,740,991, und der im Artikel verwendete Bereich von Float32Array reicht von -3.4e38 bis 3.4e38
    Wenn die Bildschirmposition zum Beispiel eine 1000x1000-Canvas ist, lässt sie sich mit Zahlen von 0 bis 1.000.000 ausdrücken; selbst mit zusätzlich 10 Subpixel-Stufen wären das 100.000.000 Werte und läge locker im JS-Bereich
    Die Geschwindigkeiten dx und dy werden zwar ebenfalls als zufällige Dezimalzahlen zwischen -10 und +10 mit (Math.random()*2-1)*10 berechnet, aber wenn eine Nachkommastelle reicht, könnte man sie in einen Integer-Bereich von -100 bis +100 umwandeln, und 10.000 mögliche Werte würden genügen
    Kombiniert ergibt das 10,000 * 100,000,000 = 1,000,000,000,000, also eine Billion Zahlen, mit denen sich ein Partikel darstellen ließe, und das liegt innerhalb von JS’ MAX_SAFE_INTEGER
    Daher scheint es möglich, die Daten eines einzelnen Partikels in einem einzigen MAX_SAFE_INTEGER oder einem einzigen Float32Array-Element unterzubringen; dann bräuchte man keinen Stride, und die Datenkonsistenz könnte zuverlässiger sein
    Allerdings könnten die Kosten fürs Codieren/Decodieren größer sein als die Speicherersparnis, sodass es sich aus Performance-Sicht überhaupt nicht lohnt

  • Wirklich beeindruckend, aber an dieser Stelle frage ich mich:
    Javascript does support an Atomics API but it uses promises which are gross. Eww sick.
    Abgesehen von waitAsync[1] scheint die Atomics API keine Promises zu verwenden.
    Ich habe früher schon Atomics benutzt, musste dabei aber keinen asynchronen/Promise-Code anfassen.
    Ich frage mich, ob sie intern Promises verwendet oder ob ich etwas übersehen habe.
    [1] https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...

  • Es gibt auch Simulationen mit fast 20 Millionen Partikeln.
    Man kann sie ausführen und programmieren: https://tinlizzie.org/~ohshima/shadama2/
    https://tinlizzie.org/~ohshima/shadama2/live2017/
    https://www.youtube.com/watch?v=tqBO_5GMfWw

  • Das Video ist klasse, aber die CodeSandbox-Links unter try it out here funktionieren auf macOS Chrome Desktop nicht.
    Es erscheinen CORS-Fehler wie Uncaught ReferenceError: SharedArrayBuffer is not defined und ERR_BLOCKED_BY_RESPONSE.NotSameOriginAfterDefaultedToSameOriginByCoep.

    • Da der Inline-Editor von CodeSandbox das Setzen von Headern verhindert, muss man die Vorschau in einem eigenen Tab öffnen.
      Bei Browsern mit Fokus auf Datenschutz kann sie ebenfalls blockiert werden.
      Künftig werde ich versuchen, eingebettete Beispiele einzubauen.
      Die finale Version kann man hier ausprobieren: https://dgerrells.com/sabby

  • Hervorragend.
    Ich habe eine Stunde damit verbracht, den Code zu verstehen und damit herumzuspielen, und hier eine Live-Implementierung gebaut: https://particules.kapochamo.com/index.html

    • Als ich sie zum ersten Mal geöffnet habe, war ich verblüfft.
      Sie ist wirklich schön, und es ist schwer zu glauben, dass man in JS so viele Partikel simulieren kann.
    • Stark.
      Beeindruckend, dass du dich so tief in den Code eingegraben hast.

  • Es könnte sich lohnen zu prüfen, ob chrome://tracing mehr Einblicke liefert.
    Habe ich hier erfahren: https://youtu.be/easvMCCBFkQ?t=114

  • Ich möchte das sofort an das UI-Team schicken, das langsame React-Apps baut.
    JS ist wirklich schnell, und besonders wenn es gut geschrieben ist, extrem schnell.

    • Das Problem ist, dass idiomatisches JS und schnelles JS in der Praxis ziemlich genau Gegensätze sind.
      Schnelles JS sieht aus wie ein schlechter C-Dialekt, und man darf keine Garbage-Collection-Objektallokationen machen, aber der Sprache fehlen gute Alternativen ohne Allokationen.
      In einer komplexen JS-App werden nur wenige sämtliche Speicherallokationen als Pointer in einem riesigen ArrayBuffer behandeln; dann ist es einfacher, gleich zu WebAssembly zu wechseln.
    • JavaScript ist wahrscheinlich die Sprache, in deren Engine-Optimierungen die meisten menschlichen Arbeitsstunden geflossen sind.
      Schade ist, dass man sich nicht allein auf JS verlassen kann und viel DOM-Manipulation dazumischen muss; und in den UIs, die wir bauen, ist genau diese DOM-Manipulation normalerweise der langsame Teil.