Simuler 20 millions de particules en JavaScript

 (dgerrells.com)
4 points par GN⁺ 2024-07-09 | 1 commentaires | Partager sur WhatsApp
  • En partant d’une simulation de particules JavaScript utilisant uniquement le CPU, l’auteur a atteint l’objectif de 1 million de particules à 60 fps sur mobile et a finalement poussé l’exemple jusqu’à 20 millions de particules
  • La clé des performances a été d’éviter les tableaux d’objets et de placer les données des particules en mémoire contiguë avec TypedArray et SharedArrayBuffer, tout en répartissant le travail entre les cœurs CPU via des Web Workers
  • Le véritable goulot d’étranglement s’est davantage manifesté dans le rendu à l’écran et l’accès mémoire que dans le calcul des positions, les écritures aléatoires dans le buffer de pixels provoquant des défauts de cache CPU
  • Les goulots ont été réduits progressivement via des buffers de pixels par Worker, la synchronisation avec postMessage, le double buffering, une grille du nombre de particules par pixel et un rendu GPU par texture
  • L’architecture finale fait tourner la simulation sur CPU et le rendu d’une texture de grille à la résolution de l’écran sur GPU, avec environ 20 fps pour 20 millions de particules sur un Mac M1

Objectif et approche de base

  • Le défi consistait à simuler 1 million de particules à 60 fps sur mobile avec du JavaScript pur et uniquement le CPU, sans WebAssembly
  • Considérant qu’un simple tableau d’objets JavaScript atteignait ses limites en performances mono-cœur sur mobile et en disposition mémoire, l’auteur a choisi de manipuler les données sous forme de tableaux contigus
  • Pour les calculs massifs, il est important d’avoir des tableaux en mémoire contiguë et dense afin de placer un maximum de données dans le cache CPU
  • Il est difficile de garantir que les tableaux et objets JavaScript classiques soient organisés de manière aussi compacte que des tableaux ou des struct dans des langages de bas niveau
  • TypedArray permet de créer des tableaux contigus de taille fixe en octets, ce qui rend possible une gestion mémoire relativement bas niveau en JavaScript

Première implémentation : SharedArrayBuffer et Web Worker

  • Les données des particules sont stockées dans une vue Float32Array posée sur un SharedArrayBuffer
    • Une particule est représentée par quatre valeurs flottantes 32 bits : x, y, dx, dy
    • Le buffer plat est indexé avec stride = 4 et byte_stride = stride * 4
  • La simulation commence par une simple mise à jour de position à chaque frame : x += dx, y += dy
  • Le multithreading repose sur des Web Workers et SharedArrayBuffer
    • Le thread principal découpe les particules en chunks et les distribue aux Workers
    • Chaque Worker ne lit et n’écrit que son chunk, ce qui évite que plusieurs threads écrivent au même endroit en mémoire
  • Pour utiliser SharedArrayBuffer dans le navigateur, les en-têtes suivants sont nécessaires
    • Cross-Origin-Embedder-Policy: require-corp
    • Cross-Origin-Opener-Policy: same-origin
  • La synchronisation initiale utilise un SharedArrayBuffer dédié au signalement
    • Le thread principal écrit un signal d’exécution pour les Workers
    • Les Workers vérifient ce signal avec setInterval(..., 1) et, une fois le travail terminé, marquent leur état comme prêt
  • Le rendu s’appuie sur ImageData, comme dans un rasterizer CPU
    • Chaque particule est dessinée comme un pixel à l’écran
    • Les particules hors écran sont ignorées afin d’éviter les accès hors limites
    • Le résultat est affiché dans le Canvas avec putImageData
  • Le profilage initial a montré que le travail des Workers prenait quelques ms, tandis que la majeure partie du temps était consacrée au rendu sur le thread principal
  • La mémoire était allouée une seule fois au démarrage et aucun nouvel objet n’était créé dans la boucle de simulation, donc presque aucun garbage n’était produit

Deuxième implémentation : entrées et interaction de type gravité

  • Les données d’entrée ont été ajoutées au SharedArrayBuffer déjà utilisé pour l’état de la simulation
    • On y stocke le delta de temps, les coordonnées x/y de la souris, l’état du toucher et la largeur/hauteur de l’écran
    • L’état du toucher se comporte comme un booléen, mais utilise 4 octets
  • En appuyant sur l’écran, les particules sont attirées vers le point de contact
    • L’auteur s’est inspiré de la forme 1 / r² d’une vraie formule gravitationnelle, mais l’a adaptée pour privilégier une interaction amusante plutôt qu’une simulation physique exacte
    • Un amortissement assimilable à de la friction a été ajouté pour éviter que les particules accélèrent indéfiniment et sortent de l’écran
  • La couleur de rendu a été modifiée pour varier selon la position des particules
    • Les valeurs des canaux RGB sont ajustées à partir de x / width et y / height
    • Stocker une couleur par particule aurait augmenté leur taille, donc une coloration basée sur la position a été choisie pour réduire le volume de données
  • Il a été possible d’expérimenter jusqu’à 2 millions de particules, et le paramètre de requête count dans l’URL permet de modifier leur nombre
  • À 10 millions de particules, le framerate chutait, et le profilage montrait que l’écriture des pixels dans ImageData était plus lente que le travail des Workers
  • En n’écrivant plus que le canal bleu et l’alpha au lieu du RGB complet, le temps de rendu est tombé d’environ 80–90 ms à 16–18 ms sur certains environnements
    • Cet écart dépendait du CPU et était plus marqué sur un Ryzen desktop que sur un MacBook Air M1

Troisième implémentation : écriture du buffer de pixels dans les Workers

  • Pour exploiter davantage de cœurs CPU, les Workers ont pris en charge non seulement la simulation, mais aussi le dessin des pixels
  • Un buffer de pixels par Worker a été mis en place pour éviter que plusieurs Workers écrivent simultanément dans le même buffer
    • Un SharedArrayBuffer de taille CPU_CORES * window.innerWidth * window.innerHeight * 3 est utilisé
    • Chaque Worker dispose de son propre buffer RGB pour l’ensemble de l’écran
  • Le thread principal additionne ensuite tous les buffers de pixels des Workers avant d’écrire dans ImageData
  • Cette version provoquait un scintillement à l’écran
    • Le thread principal lisait un buffer pendant qu’un Worker le remettait à zéro avec fill(0)
    • Les rendus précédents pouvaient déjà lire des données obsolètes, mais la différence d’une frame à l’autre était peu visible ; ici, l’effacement par le Worker se traduisait par un scintillement partiel
  • Les pistes envisagées étaient une synchronisation via Atomics, l’attente de la fin des Workers avec postMessage, ou le double buffering

Quatrième implémentation : synchronisation via postMessage

  • Pour supprimer le scintillement, le tableau de signaux a été abandonné au profit de postMessage pour notifier la fin du travail des Workers
  • Le thread principal gère une valeur activeWorkers
    • Chaque Worker envoie un message lorsqu’il a terminé, ce qui décrémente activeWorkers
    • Une fois tous les Workers terminés, le rendu est effectué et le prochain requestAnimationFrame est demandé
  • Cette approche a supprimé le scintillement
  • Le temps par frame ne s’est pas vraiment amélioré, et pouvait même empirer
    • Le thread principal ne fait rien pendant qu’il attend la fin des Workers
    • Pour 2 millions de particules, il existait des cas où laisser les Workers ne pas attendre le rendu du thread principal permettait d’économiser environ 7 ms
  • Pour réduire ce goulot, l’auteur a appliqué le double buffering, fréquent dans les pilotes graphiques

Cinquième implémentation : double buffering et goulot d’étranglement du cache

  • Le double buffering consiste à créer deux buffers de pixels et à alterner le buffer actif à chaque frame
    • Pendant que le thread principal affiche un buffer, les Workers préparent la frame suivante dans l’autre
  • Après cette modification, les Workers n’avaient plus besoin d’attendre le rendu du thread principal, et certaines frames qui dépassaient auparavant 50 ms se rapprochaient de 16 ms
  • Le code qui restait lent correspondait aux trois lignes ajoutant des valeurs aux canaux RGB du buffer de pixels
  • La cause tenait au fait que, même si les données sont stockées de façon contiguë, l’ordre d’accès ne l’est pas
    • Le pixelIndex calculé à partir de x et y n’est pas aligné avec l’ordre du tableau de particules
    • À chaque boucle, le code saute vers un emplacement arbitraire du buffer de pixels, produisant un motif proche de l’accès aléatoire
  • Ce schéma d’accès provoque des défauts de cache lorsque les données des particules et celles des pixels ne tiennent pas toutes dans le cache
  • L’exemple de calcul pour un iPhone est le suivant
    • Formule : screen width * screen height * bytes per pixel + bytes per particle * total particles / number of workers
    • 2532 * 1170 * 3 + 16 * 2,000,000 / 5
    • Le résultat dépasse 15 Mo, bien trop pour tenir dans le cache L1
  • Dans cette version, sur une puce M1, la simulation de 2 millions de particules prenait environ 4 ms, l’accès aux données de pixels environ 3,5 ms et l’écriture dans le buffer de pixels environ 7 ms
  • Sur mobile, 1 million de particules pouvait être maintenu à 60 fps, mais sur un desktop disposant de plus de 20 threads, le thread principal passait 30 ms par frame à additionner plus de 20 buffers de pixels

Sixième implémentation : force de rappel vers la position de départ

  • Le nouvel effet consistait à faire revenir les particules d’autant plus fortement qu’elles s’éloignaient de leur position initiale
  • Pour cela, deux valeurs supplémentaires sx et sy ont été ajoutées à chaque particule
    • Une particule possède désormais six floats : x, y, dx, dy, sx, sy
    • particleStride passe à 6
  • Le code des Workers a reçu une fonction de calcul des forces, avec un objet de cache pour éviter la production de garbage
  • Le résultat produisait des effets visuels rappelant de la gelée ou un fluide, avec des tourbillons évoquant du papier froissé ou du tissu
  • C’est au cours de cette étape qu’est née l’idée de ne plus stocker un buffer de pixels par Worker, mais une grille ne comptant que le nombre de particules par pixel

Septième implémentation : grille du nombre de particules par pixel

  • En stockant uniquement le nombre de particules à chaque pixel au lieu de valeurs RGB, la mémoire peut être réduite d’un tiers
  • Comme la couleur est calculée à partir de la position x, y et non des données de chaque particule, ce simple compteur par pixel suffit pour le rendu
  • Tous les Workers ont été modifiés pour partager une seule grille du nombre de particules
    • Le travail d’agrégation des buffers par Worker sur le thread principal disparaît
    • Le problème de l’augmentation du coût d’agrégation avec le nombre de Workers est ainsi résolu
  • La nouvelle formule de calcul du cache est la suivante
    • screen width * screen height + bytes per particle * total particles / number of workers
    • Pour un iPhone : 2532 * 1170 + 16 * 2,000,000 / 5
    • On obtient environ 9,3 Mo, soit environ 30 % de moins qu’avant, mais toujours trop pour le cache L1
  • Le rendu parcourt tous les pixels, lit le nombre de particules du pixel concerné, calcule les valeurs RGB, puis réinitialise la grille avec fill(0)
  • Après la simulation, chaque Worker calcule le pCountIndex des particules visibles et exécute activeGrid[pCountIndex]++
  • Ce changement a été particulièrement utile quand le nombre de Workers était élevé, et a permis d’utiliser les 24 threads complets sur desktop
  • Malgré cela, il arrivait que le MacBook Air M1 soit plus rapide qu’un desktop Ryzen 9 3900X
    • Le Ryzen 9 3900X dispose de 64 Mo de cache L3, mais seulement 64 Ko de L1
    • Le M1 de première génération possède 320 Ko de cache L1, dont 128 Ko pour les données et 192 Ko pour les instructions
    • L’auteur estime qu’un cache de données L1 plus grand a contribué à réduire la latence mémoire

Limites des optimisations CPU-only

  • L’ensemble des optimisations a permis d’obtenir environ 2x de gain par rapport à la première version multithread
  • L’objectif consistant à traiter 1 million de particules sur mobile à 60 fps avec un rendu CPU en JavaScript a été atteint
  • Le résultat global n’a rien de particulièrement impressionnant, et l’auteur estime qu’un langage compilé irait 10x plus vite
  • Il resterait encore de la marge si des instructions SIMD pouvaient être utilisées dans les tight loops
  • L’étape suivante a consisté à conserver la simulation sur CPU tout en déplaçant uniquement le rendu vers un pipeline GPU traditionnel pour comparer

20 millions de particules et rendu GPU

  • La première comparaison côté GPU utilisait l’instancing GPU de threejs pour dessiner un plane/quad par particule
  • Cette approche s’est révélée moins performante qu’attendu
    • L’instancing de threejs impose de mettre à jour une matrice pour chaque position de particule, et ce travail se fait sur un seul thread CPU
    • Les données de transformation des particules doivent être envoyées au GPU à chaque frame, et ce transfert est lent
  • Sur une puce M1, lors de la simulation de 4 millions de particules, 80 % du temps par frame était consacré à l’envoi des données au GPU
  • Sur desktop, cette part tombait à 30 %, mais restait malgré tout le plus gros goulot d’étranglement
  • L’alternative a été d’utiliser comme texture la grille du nombre de particules créée précédemment et de rendre un quad plein écran
    • Le volume de données envoyé au GPU devient alors fixe, lié à la résolution de l’écran et non au nombre de particules
    • C’est un compromis : les grosses simulations transfèrent moins de données, mais les petites peuvent en transférer davantage
  • Une implémentation rapide avec threejs et un pixel shader personnalisé a montré que le rendu sur le thread principal restait de l’ordre de quelques ms, indépendamment de la taille de la simulation
  • Dans cette architecture, les Workers tournent aussi vite que possible, et la simulation dépend directement du nombre de cœurs CPU, quelle que soit l’échelle
  • Chaque Worker passe environ 50 % de son temps à faire des calculs numériques et 50 % à mettre à jour les compteurs de la grille de particules
  • Les performances de la version finale sont les suivantes
    • Sur Mac M1 sur batterie, 20 millions de particules tournent à environ 20 fps
    • Sur desktop, environ 30 millions de particules sont traitées pour un fps similaire
    • D’après un test réalisé par un ami équipé d’un CPU 32 cœurs, le système monte à environ 40 millions de particules
  • Démonstrations associées :

En résumé

  • Les CPU et GPU peuvent traiter très rapidement les calculs numériques
  • Les parties lentes sont le déplacement des données et surtout les accès mémoire aléatoires
  • Pour écrire du code rapide, il faut comprendre comment le matériel met les données en cache et les déplace
  • SharedArrayBuffer et les Web Workers se sont révélés utiles pour expérimenter l’utilisation de plusieurs cœurs en JavaScript
  • L’auteur prévoit d’essayer des compute shaders lorsque WebGPU sera plus largement adopté

À lire aussi

1 commentaires

 
GN⁺ 2024-07-09
Avis sur Hacker News

  • Ce serait bien d’intégrer directement la simulation dans le blog
    J’ai dû faire défiler longtemps vers le haut et le bas avant de trouver le lien vers la simulation elle-même
    On pourrait choisir des valeurs qui tournent correctement même sur de vieux téléphones, ou les ajuster en fonction du framerate, ou simplement mettre quelques liens en haut de l’article
    https://ciechanow.ski/ est un exemple de tout premier ordre de ce que peut donner l’intégration de simulations dans un article
    Avant, tous les sites web intégraient ce genre d’éléments interactifs géniaux
    Et je pense qu’on peut faire tourner une simulation de particules sur le GPU même sans WebGPU
    Exemple : https://news.ycombinator.com/item?id=19963640

    • C’est l’un des meilleurs exemples de blog explicatif que j’aie vus jusqu’ici
      J’aimerais que cela devienne la norme pour partager de l’information. Si quelque chose vaut la peine d’être partagé, cela vaut aussi la peine de le rendre facile à comprendre
    • Cette simulation de fluide est vraiment stupéfiante
    • Je suis d’accord, l’intégration est une bonne idée
      J’ai envisagé d’intégrer chaque version, mais je craignais qu’il y ait trop de workers qui tournent en même temps
      Je prévois de mettre à jour l’article pour intégrer la version finale à la fin
      Ce blog est excellent, avec un niveau de finition incroyable pour chaque exemple
      Édit : j’ai essayé d’ajouter une version intégrée, mais les en-têtes nécessaires ne cohabitaient pas bien avec les autres intégrations, et les anciennes versions restent liées à codesandbox
    • Il suffit d’indiquer : « Passez à la fin pour jouer avec l’application finale »

  • Je viens de tester la démo mobile [0], c’est assez impressionnant
    [0] https://dgerrells.com/sabby

    • Ça fonctionne aussi avec plusieurs doigts
      C’est étonnant d’obtenir ça en pur JavaScript, et comme la latence augmente avec le nombre de doigts, j’imagine qu’il y a davantage de données qui transitent entre les threads
    • Ça a un aspect étrangement organique, comme des structures lipidiques dans une soupe primitive
    • Sur mon téléphone, Firefox tourne mieux que Chrome, ce qui est satisfaisant

  • Simple curiosité : je me demande si, au lieu de représenter chaque particule avec quatre nombres flottants 32 bits x, y, dx, dy, on pourrait encoder ces données dans un seul nombre JS
    La plage des entiers sûrs en JS est 2^53 - 1 = 9,007,199,254,740,991, tandis que la plage du Float32Array utilisé dans l’article va de -3.4e38 à 3.4e38
    Par exemple, si la position à l’écran est sur un canvas 1000x1000, on peut l’exprimer avec des nombres de 0 à 1 000 000 ; même en ajoutant 10 niveaux de sous-pixels, on arrive à 100 000 000, largement dans la plage de JS
    Les vitesses dx et dy sont aussi calculées comme des décimaux aléatoires entre -10 et +10 avec (Math.random()*2-1)*10, mais si les limiter à une décimale suffit, on peut les convertir en entiers de -100 à +100, ce qui ne nécessite que 10 000 valeurs possibles
    En combinant les deux, 10,000 * 100,000,000 = 1,000,000,000,000, soit mille milliards de nombres pour représenter une particule, ce qui reste dans MAX_SAFE_INTEGER de JS
    On pourrait donc mettre les données d’une particule entière dans un seul MAX_SAFE_INTEGER ou un seul élément de Float32Array, ce qui supprimerait le besoin de stride et pourrait rendre la cohérence des données plus solide
    Cela dit, le coût d’encodage/décodage peut dépasser les économies de mémoire et ne présenter aucun intérêt côté performances

  • Vraiment génial, mais je m’interroge sur ce passage
    Javascript does support an Atomics API but it uses promises which are gross. Eww sick.
    À part waitAsync[1], l’API Atomics ne semble pas utiliser de promesses
    J’ai déjà utilisé Atomics par le passé, mais je n’ai jamais eu besoin de gérer du code asynchrone/des promesses
    Je me demande si elle utilise des promesses en interne, ou si quelque chose m’a échappé
    [1] https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...

  • Il existe aussi une simulation qui gère près de 20 millions de particules
    On peut l’exécuter et la programmer : https://tinlizzie.org/~ohshima/shadama2/
    https://tinlizzie.org/~ohshima/shadama2/live2017/
    https://www.youtube.com/watch?v=tqBO_5GMfWw

  • La vidéo est chouette, mais les liens CodeSandbox de try it out here ne fonctionnent pas sur Chrome desktop sous macOS
    J’obtiens des erreurs CORS comme Uncaught ReferenceError: SharedArrayBuffer is not defined et ERR_BLOCKED_BY_RESPONSE.NotSameOriginAfterDefaultedToSameOriginByCoep

    • Comme l’éditeur inline de CodeSandbox empêche de configurer les en-têtes, il faut ouvrir l’aperçu dans un onglet dédié
      Ça peut aussi être bloqué si vous utilisez un navigateur axé sur la protection de la vie privée
      À l’avenir, j’essaierai d’inclure des exemples intégrés
      Vous pouvez essayer la version finale ici : https://dgerrells.com/sabby

  • Excellent
    J’ai passé une heure à comprendre le code et à jouer avec, et j’ai créé ici une implémentation en temps réel : https://particules.kapochamo.com/index.html

    • J’ai été bluffé à la première ouverture
      C’est vraiment beau, et il est difficile de croire qu’autant de particules soient simulées en JS
    • Super
      C’est impressionnant que tu sois allé aussi loin dans le code

  • Ça vaut le coup de vérifier si chrome://tracing apporte davantage d’enseignements
    Je l’ai appris ici : https://youtu.be/easvMCCBFkQ?t=114

  • J’ai très envie d’envoyer ça à notre équipe UI qui fabrique une appli React lente
    JS est vraiment rapide, et surtout, quand il est bien écrit, il est extrêmement rapide

    • Le problème, c’est que le JS idiomatique et le JS rapide sont en pratique presque à l’opposé
      Le JS rapide ressemble à un mauvais dialecte de C, et il ne faut pas faire d’allocations d’objets soumises au garbage collector, alors que le langage manque de bonnes alternatives sans allocation
      Dans une appli JS complexe, presque personne ne va gérer toutes les allocations mémoire avec des pointeurs dans un énorme ArrayBuffer, et à ce compte-là il est plus simple de passer à WebAssembly
    • JavaScript est probablement le langage dans lequel on a investi le plus d’heures humaines en optimisations de moteurs
      Ce qui est dommage, c’est qu’on ne peut pas miser uniquement sur JS et qu’il faut beaucoup y mêler des manipulations du DOM ; or, dans les UI que nous construisons, c’est généralement cette manipulation du DOM qui est lente