Simular 20 millones de partículas con JavaScript

 (dgerrells.com)
4 puntos por GN⁺ 2024-07-09 | 1 comentarios | Compartir por WhatsApp
  • Partiendo de una simulación de partículas en JavaScript que usa solo CPU, se logró el objetivo de 1 millón de partículas a 60 fps en un teléfono, y el ejemplo final se escaló hasta 20 millones de partículas
  • La clave del rendimiento fue evitar arreglos de objetos y mantener los datos de las partículas en memoria contigua con TypedArray y SharedArrayBuffer, dividiendo el trabajo por núcleo de CPU con Web Workers
  • El verdadero cuello de botella apareció más en el dibujo en pantalla y el acceso a memoria que en el cálculo de posición de las partículas, y las escrituras aleatorias en el búfer de píxeles provocaban fallos de caché de CPU
  • Se fueron reduciendo los cuellos de botella por etapas con búferes de píxeles por Worker, sincronización con postMessage, doble buffering, una grilla de partículas por píxel y renderizado de texturas en GPU
  • La arquitectura final hace que la CPU simule y la GPU renderice una textura de grilla del tamaño de la resolución de pantalla; en una Mac M1 procesa 20 millones de partículas a unos 20 fps

Objetivo y enfoque básico

  • El desafío era simular 1 millón de partículas a 60 fps en un teléfono usando solo JavaScript puro y CPU, sin WebAssembly
  • Considerando que un simple arreglo de objetos JavaScript tiene límites en rendimiento de un solo núcleo móvil y en disposición de memoria, se eligió tratar los datos como arreglos contiguos
  • En cálculos masivos, son importantes los arreglos densos de memoria contigua que permiten cargar la mayor cantidad posible de datos en la caché de la CPU
  • Es difícil garantizar que los arreglos y objetos comunes de JavaScript estén ubicados de forma compacta como los arreglos o struct de lenguajes de bajo nivel
  • TypedArray permite crear arreglos de bytes contiguos de tamaño fijo, lo que habilita una gestión de memoria relativamente de bajo nivel en JavaScript

Primera implementación: SharedArrayBuffer y Web Worker

  • Los datos de las partículas se almacenan aplicando una vista Float32Array sobre un SharedArrayBuffer
    • Una partícula se representa con cuatro valores de punto flotante de 32 bits: x, y, dx, dy
    • Se indexa el búfer plano con stride = 4 y byte_stride = stride * 4
  • La simulación empieza con una simple actualización de posición en cada frame: x += dx, y += dy
  • El multithreading se construye con Web Worker y SharedArrayBuffer
    • El hilo principal divide y entrega chunks de partículas a cada Worker
    • Cada Worker solo lee y escribe el chunk que tiene asignado, evitando que varios hilos escriban en la misma posición de memoria
  • Para usar SharedArrayBuffer en el navegador se requieren los siguientes headers
    • Cross-Origin-Embedder-Policy: require-corp
    • Cross-Origin-Opener-Policy: same-origin
  • La sincronización inicial usa un SharedArrayBuffer de señalización separado
    • El hilo principal escribe una señal de ejecución para los Workers
    • El Worker revisa la señal con setInterval(..., 1) y, al terminar el trabajo, registra su estado listo
  • El renderizado se procesa como un rasterizador basado en CPU usando ImageData
    • Cada partícula se dibuja como un píxel en pantalla
    • Las partículas fuera de pantalla se omiten para evitar accesos fuera del rango del arreglo
    • El resultado se dibuja en el Canvas con putImageData
  • En el profiling inicial, el trabajo de los Workers tomaba unos pocos ms, y la mayor parte del tiempo se usaba en el renderizado del hilo principal
  • La memoria se asignaba una sola vez al inicio y no se creaban objetos nuevos dentro del loop de simulación, por lo que casi no se generaba basura

Segunda implementación: entrada e interacción parecida a la gravedad

  • Los datos de entrada se agregan al SharedArrayBuffer existente para el estado de simulación
    • Se almacenan delta time, x/y del mouse, estado táctil y ancho/alto de la pantalla
    • El estado táctil es un valor cercano a boolean, pero usa 4 bytes
  • Al tocar la pantalla, se agrega un efecto que atrae las partículas hacia el punto de contacto
    • Se tomó como referencia la forma 1 / r² de la fórmula de gravedad real, pero se modificó con el objetivo de lograr una interacción divertida más que una simulación física exacta
    • Se agregó una atenuación equivalente a fricción para evitar que las partículas aceleren indefinidamente y salgan disparadas fuera de la pantalla
  • El color de renderizado se modificó para cambiar según la posición de la partícula
    • Se ajustan los valores de los canales RGB usando x / width y y / height
    • Como guardar el color de cada partícula aumentaría su tamaño, se usa color basado en posición para reducir el tamaño de los datos
  • Se pudo experimentar hasta con 2 millones de partículas, y se permitió cambiar la cantidad de partículas con el parámetro de query count de la URL
  • Con 10 millones de partículas bajó el framerate, y el profiling mostró que la escritura de píxeles en ImageData era más lenta que los Workers
  • Al cambiar para escribir solo el canal azul y alfa en lugar de todo RGB, el tiempo de renderizado bajó de unos 80–90 ms a 16–18 ms en algunos entornos
    • Esta diferencia variaba según la CPU y fue más grande en una desktop Ryzen que en una MacBook Air M1

Tercera implementación: escritura del búfer de píxeles en los Workers

  • Para aprovechar más núcleos de CPU, se cambió para que los Workers se encargaran no solo de la simulación sino también del dibujo de píxeles
  • Para que varios Workers no escribieran simultáneamente en el mismo búfer de píxeles, se creó un búfer de píxeles por Worker
    • Se usa un SharedArrayBuffer de tamaño CPU_CORES * window.innerWidth * window.innerHeight * 3
    • Cada Worker tiene un búfer RGB de pantalla completa
  • El hilo principal suma todos los búferes de píxeles por Worker y luego los escribe en ImageData
  • En esta versión aparece parpadeo en la pantalla
    • El hilo principal estaba leyendo el mismo búfer mientras el Worker borraba su búfer de píxeles con fill(0)
    • En renderizados anteriores también podía leerse datos viejos, pero la diferencia entre frames no era notoria; esta vez el borrado del Worker se manifestaba como parpadeo en partes de la pantalla
  • Las posibles soluciones eran sincronización basada en Atomics, esperar a que terminen los Workers con postMessage, y doble buffering

Cuarta implementación: sincronización basada en postMessage

  • Para eliminar el parpadeo, se descartó el arreglo de señales y se cambió a notificar la finalización de los Workers con postMessage
  • El hilo principal administra el valor activeWorkers
    • Cada Worker envía un mensaje al terminar y se decrementa activeWorkers
    • Cuando todos los Workers terminan, se renderiza y se solicita el siguiente requestAnimationFrame
  • Con este método se solucionó el parpadeo
  • El tiempo por frame no mejoró mucho y, de hecho, podía empeorar
    • Porque el hilo principal no hace nada mientras espera que terminen los Workers
    • Con 2 millones de partículas, había situaciones donde se podían ahorrar unos 7 ms si los Workers no esperaban el renderizado del hilo principal
  • Para reducir este cuello de botella se aplicó el doble buffering, común en drivers gráficos

Quinta implementación: doble buffering y cuello de botella de caché

  • El doble buffering consiste en crear dos búferes de píxeles y cambiar el búfer activo en cada frame
    • Mientras el hilo principal dibuja un búfer, los Workers preparan el siguiente frame en el otro búfer
  • Tras aplicarlo, los Workers dejaron de esperar el renderizado del hilo principal, y algunos frames que antes superaban los 50 ms se acercaron más a 16 ms
  • El código que seguía siendo lento eran las tres líneas que sumaban valores a los canales RGB del búfer de píxeles
  • La causa era que, aunque los datos estuvieran almacenados de forma contigua, el orden de acceso no era contiguo
    • El pixelIndex calculado a partir de x, y de la partícula no está alineado con el orden del arreglo de partículas
    • En cada iteración del loop se salta a una posición arbitraria del búfer de píxeles, generando un patrón cercano al acceso aleatorio
  • Este patrón de acceso provoca fallos de caché cuando los datos de partículas y píxeles no caben juntos en la caché
  • Un cálculo de ejemplo para iPhone es el siguiente
    • Fórmula: screen width * screen height * bytes per pixel + bytes per particle * total particles / number of workers
    • 2532 * 1170 * 3 + 16 * 2,000,000 / 5
    • El resultado supera los 15 MB, demasiado grande para entrar en la caché L1
  • En esta versión, en un chip M1, la simulación de 2 millones de partículas toma unos 4 ms, el acceso a datos de píxeles unos 3.5 ms y la escritura del búfer de píxeles unos 7 ms
  • En teléfonos se podía mantener 1 millón de partículas a 60 fps, pero en desktops con más de 20 hilos el hilo principal tardaba 30 ms por frame en sumar más de 20 búferes de píxeles

Sexta implementación: fuerza para volver a la posición inicial

  • El nuevo efecto hace que las partículas sean atraídas de vuelta con más fuerza cuanto más se alejan de su posición inicial
  • Para eso se agregan a la partícula dos valores de posición inicial: sx, sy
    • Una partícula tiene seis floats: x, y, dx, dy, sx, sy
    • particleStride = 6
  • En el código de los Workers se agregó una función de cálculo de fuerza, y se usa un objeto de caché para evitar generar basura
  • El resultado produjo un efecto visual parecido a gelatina o fluido, con partículas mostrando remolinos como papel o tela arrugada
  • En este proceso surgió la idea de no guardar un búfer de píxeles por Worker, sino cambiarlo por una grilla que solo cuente la cantidad de partículas por píxel

Séptima implementación: grilla de cantidad de partículas por píxel

  • Si en lugar de guardar valores RGB se guarda solo la cantidad de partículas en cada posición de píxel, la memoria puede reducirse a 1/3
  • Como el color se calcula a partir de la posición x, y, no a partir de datos por partícula, se puede renderizar solo con el conteo por píxel
  • Se cambió para que todos los Workers compartan una única grilla de cantidad de partículas
    • Desaparece el trabajo del hilo principal de sumar búferes por Worker
    • Se resuelve el problema de que el costo de combinación para render crezca al aumentar la cantidad de Workers
  • El nuevo cálculo de caché es el siguiente
    • screen width * screen height + bytes per particle * total particles / number of workers
    • Para iPhone: 2532 * 1170 + 16 * 2,000,000 / 5
    • Aproximadamente 9.3 MB, cerca de 30% menos que antes, pero todavía grande para la caché L1
  • El renderizado recorre todos los píxeles, lee la cantidad de partículas de ese píxel, calcula el valor RGB y luego inicializa la grilla con fill(0)
  • Después de la simulación, el Worker calcula el pCountIndex de las partículas que están dentro de pantalla y ejecuta activeGrid[pCountIndex]++
  • Este cambio ayudó especialmente cuando había muchos Workers, y permitió usar los 24 hilos en la desktop
  • Aun así, hubo casos donde la MacBook Air M1 era más rápida que una desktop Ryzen 9 3900X
    • El Ryzen 9 3900X tiene 64 MB de caché L3, pero la L1 es de 64 KB
    • El M1 de primera generación tiene 320 KB de caché L1, de los cuales 128 KB son para datos y 192 KB para instrucciones
    • Se considera que la caché L1 de datos más grande ayudó a reducir la latencia de memoria

Límites de la optimización solo con CPU

  • Como resultado de varias optimizaciones, se obtuvo una mejora de velocidad de aproximadamente 2× frente a la primera versión multithread
  • Se cumplió el objetivo de procesar 1 millón de partículas basadas en CPU a 60 fps en un teléfono usando solo JavaScript
  • El resultado general no es particularmente impresionante, y se espera que un lenguaje compilado sea 10 veces más rápido
  • Si se pudieran usar instrucciones SIMD en el tight loop, habría margen para acelerar más
  • En el siguiente paso, se deja la simulación en CPU y se mueve solo el renderizado a un pipeline tradicional de GPU para comparar

20 millones de partículas y renderizado en GPU

  • La primera comparación de renderizado en GPU fue dibujar un plane/quad por partícula usando GPU instancing de threejs
  • Este método tuvo un rendimiento más bajo de lo esperado
    • El instancing de threejs debe actualizar una matriz por cada posición de partícula, y este trabajo se realiza en un solo hilo de CPU
    • Los datos de transformación de las partículas deben subirse a la GPU en cada frame, y esta transferencia es lenta
  • Al simular 4 millones de partículas en un chip M1, el 80% del tiempo de frame se usaba para enviar datos a la GPU
  • En desktop, la proporción de transferencia de datos era 30%, pero seguía siendo el cuello de botella más grande
  • La alternativa es usar la grilla de cantidad de partículas creada antes como textura y renderizar un quad de pantalla completa
    • La cantidad de datos enviados a la GPU queda fija según la resolución de pantalla, no según la cantidad de partículas
    • Es un trade-off: en simulaciones grandes se reduce la transferencia, pero en simulaciones pequeñas se pueden enviar más datos
  • Tras una implementación rápida con threejs y un pixel shader personalizado, el renderizado del hilo principal quedó en unos pocos ms sin importar el tamaño de la simulación
  • En esta estructura, los Workers se ejecutan lo más rápido posible, y la simulación queda directamente ligada a la cantidad de núcleos de CPU tanto en escalas grandes como pequeñas
  • Cada Worker usa aproximadamente 50% del tiempo en cálculos numéricos y 50% en actualizar el conteo de la grilla de partículas
  • El rendimiento de la versión final es el siguiente
    • En una Mac M1 con batería, ejecuta 20 millones de partículas a unos 20 fps
    • La desktop procesa unos 30 millones de partículas con fps similares
    • En la prueba de un amigo con una CPU de 32 núcleos, llegó a unos 40 millones de partículas
  • Demos relacionados:

Resumen

  • La CPU y la GPU pueden procesar cálculos numéricos muy rápido
  • Lo lento es mover datos y, en especial, el acceso aleatorio a memoria
  • Para escribir código rápido hay que saber cómo el hardware cachea y mueve los datos
  • SharedArrayBuffer y Web Worker fueron útiles para experimentar con el uso de múltiples núcleos en JavaScript
  • Cuando WebGPU tenga una adopción más amplia, se planea probar compute shaders

Lecturas relacionadas

1 comentarios

 
GN⁺ 2024-07-09
Comentarios de Hacker News

  • Estaría bien incrustar la simulación directamente dentro del blog
    Tuve que hacer bastante scroll hacia arriba y abajo hasta encontrar el enlace a la simulación real
    También se podría elegir un valor que corra razonablemente incluso en teléfonos viejos, o hacer que se ajuste según la tasa de cuadros, o simplemente poner unos cuantos enlaces al inicio del artículo
    https://ciechanow.ski/ es un ejemplo de primer nivel mundial de lo increíble que puede verse una simulación dentro de un artículo
    Antes todos los sitios web incrustaban este tipo de elementos interactivos tan geniales
    Y creo que también se puede ejecutar una simulación de partículas en la GPU sin WebGPU
    Ej.: https://news.ycombinator.com/item?id=19963640

    • Es uno de los mejores ejemplos de blog explicativo que he visto hasta ahora
      Ojalá este fuera el estándar para compartir información. Si vale la pena compartir algo, también vale la pena hacerlo fácil de entender
    • Esa simulación de fluidos es realmente asombrosa
    • Coincido en que la incrustación es buena
      Pensé en incrustar cada versión, pero me preocupaba que hubiera demasiados workers ejecutándose al mismo tiempo
      Voy a actualizarlo para incrustar la versión final al final del artículo
      Ese blog tiene un nivel de acabado increíble en cada ejemplo y es realmente muy bueno
      Edit: intenté agregar una versión incrustada, pero los headers necesarios no se llevaban bien con otras incrustaciones, y las versiones anteriores siguen atadas a codesandbox
    • Basta con indicar: “si quieres jugar con la app final, salta al final”

  • Probé el demo móvil [0] directamente y está bastante impresionante
    [0] https://dgerrells.com/sabby

    • También funciona con varios dedos
      Sorprende que llegue a este nivel en JavaScript puro, y como la latencia aumenta cuando hay más dedos, parece que hay más datos moviéndose entre hilos
    • Se ve extrañamente orgánico, como estructuras lipídicas en una sopa primordial
    • Me alegra que en mi teléfono Firefox funcione mejor que Chrome

  • Es pura curiosidad, pero me pregunto si en vez de representar cada partícula con cuatro números de punto flotante de 32 bits —x, y, dx, dy— sería posible codificar esos datos dentro de un solo número de JS
    El rango de enteros seguros en JS es 2^53 - 1 = 9,007,199,254,740,991, y el rango de Float32Array usado en el artículo es de -3.4e38 a 3.4e38
    Por ejemplo, si la posición en pantalla fuera un canvas de 1000x1000, se podría representar con números de 0 a 1,000,000, y aun agregando 10 niveles de subpíxel serían 100,000,000, así que entra con holgura en el rango de JS
    Las velocidades dx, dy también se calculan como decimales aleatorios entre -10 y +10 con (Math.random()*2-1)*10, pero si bastara con limitarlo a un decimal, podría convertirse en un rango entero de -100 a +100, y con 10,000 valores posibles alcanzaría
    Si se combinan ambos, 10,000 * 100,000,000 = 1,000,000,000,000, es decir, 1 billón de números para representar una partícula, lo cual sigue estando dentro de MAX_SAFE_INTEGER de JS
    Así que parece que los datos de una sola partícula podrían meterse en un único MAX_SAFE_INTEGER o en un solo elemento de Float32Array, lo que eliminaría la necesidad de stride y quizá haría más consistente la integridad de los datos
    Pero también puede que el costo de codificar/decodificar supere el ahorro de memoria y no valga nada en términos de rendimiento

  • Está muy bueno, pero me da curiosidad esta parte
    Javascript does support an Atomics API but it uses promises which are gross. Eww sick.
    Excepto por waitAsync[1], la API de Atomics no parece usar promesas
    He usado Atomics antes, pero no tuve que lidiar con código asíncrono/promesas
    Me pregunto si internamente usa promesas, o si se me está escapando algo
    [1] https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...

  • También hay una simulación que maneja casi 20 millones de partículas
    Se puede ejecutar y programar aquí: https://tinlizzie.org/~ohshima/shadama2/
    https://tinlizzie.org/~ohshima/shadama2/live2017/
    https://www.youtube.com/watch?v=tqBO_5GMfWw

  • El video está genial, pero los links de codesandbox en try it out here no funcionan en Chrome de escritorio en macOS
    Aparecen errores de CORS como Uncaught ReferenceError: SharedArrayBuffer is not defined y ERR_BLOCKED_BY_RESPONSE.NotSameOriginAfterDefaultedToSameOriginByCoep

    • Como el editor inline de codesandbox impide configurar headers, hay que abrir la vista previa en una pestaña dedicada
      Si usas un navegador centrado en la privacidad, también podría bloquearse
      Más adelante voy a intentar incluir ejemplos embebidos
      La versión final se puede probar aquí: https://dgerrells.com/sabby

  • Excelente
    Pasé una hora entendiendo el código y jugando con él, y dejé aquí una implementación en tiempo real: https://particules.kapochamo.com/index.html

    • Me sorprendió cuando lo abrí por primera vez
      Se ve realmente hermoso, y cuesta creer que JS pueda simular tantas partículas
    • Genial
      Impresiona que te hayas metido tan a fondo en el código

  • Vale la pena revisar si chrome://tracing da más información
    Lo conocí aquí: https://youtu.be/easvMCCBFkQ?t=114

  • Quiero enviar esto ya mismo al equipo de UI que hace apps lentas en React
    JS es realmente rápido y, sobre todo si está bien escrito, ridículamente rápido

    • El problema es que el JS idiomático y el JS rápido en la práctica están casi en extremos opuestos
      El JS rápido se ve como un mal dialecto de C, y no deberías hacer asignaciones de objetos para el recolector de basura, pero al lenguaje le faltan buenas alternativas sin asignación
      Casi nadie va a manejar todas las asignaciones de memoria en una app compleja de JS con punteros dentro de un enorme ArrayBuffer, y llegado ese punto es más fácil pasarse a WebAssembly
    • JavaScript probablemente sea el lenguaje al que más horas humanas se le han dedicado en optimización de motores
      Lo lamentable es que no puedes depender solo de JS y tienes que mezclar mucha manipulación del DOM, y en las UI que hacemos esa manipulación del DOM suele ser la parte lenta