Spice: técnica de paralelismo fino en Zig con sobrecarga subnanosegundo

• Spice es un proyecto de investigación que busca usar heartbeat scheduling en Zig para agregar posibilidad de ejecución paralela a funciones manteniendo la sobrecarga por debajo de 1 ns
• El diseño central consiste en marcar con fork trabajo que otros hilos pueden procesar, pero si ningún hilo lo toma, en join el hilo actual lo ejecuta directamente mediante una estructura de fallback
• En un benchmark de suma de un árbol binario de 100 millones de nodos, Rayon tuvo una sobrecarga de 1 hilo de unos 15 ns y con 16 hilos fue unas 4.5 veces más rápido que el baseline, mientras que Spice obtuvo con 16 hilos casi toda su mejora de velocidad de unas 11 veces frente al baseline
• En tareas de ejecución muy corta, como 1000 nodos, hubo casos en que Rayon se volvió 60 veces más lento en total con 32 hilos, mientras que Spice no inicia el multithreading y deja dormir los hilos adicionales si determina que no hace falta procesamiento paralelo
• La implementación actual carece de pruebas, documentación, soporte para arrays y slices, y benchmarks adicionales; usa mucho @panic, y el autor señala que hay que tener presentes muchas limitaciones antes de usarla en producción

---

El problema que Spice intenta resolver

• Spice es un proyecto para implementar paralelismo muy fino en Zig con baja sobrecarga
• El objetivo es que los usuarios no tengan que preocuparse constantemente por si agregar paralelización hará más lento el programa
• Para maximizar el rendimiento se necesitan benchmarks sofisticados, pero en general Spice está diseñado para que agregar paralelismo casi no tenga sobrecarga práctica
• El proyecto es principalmente un proyecto de investigación, y si se considera su uso en producción, primero hay que revisar sus limitaciones
• En una actualización de septiembre de 2024 se presentó Chili, un port de esta idea a Rust

Forma de uso y API principal

• Las funciones paralelas de Spice reciben *spice.Task como parámetro para coordinar el trabajo
• Las llamadas recursivas o llamadas a funciones paralelizables no deben hacerse directamente, sino a través de t.call
• fork configura una tarea que otro hilo puede ejecutar
• Después de fork, la función también debe realizar trabajo útil directamente
• join espera a que otro hilo complete la tarea, pero puede devolver null
  • null indica que ningún otro hilo tomó esa tarea
  • En ese caso, el hilo actual debe ejecutar esa tarea directamente

El diseño de que “no todo trabajo viene de una cola”

• La idea central de Spice es que no todo trabajo empieza en una cola
• fork avisa que hay trabajo que otro hilo puede ejecutar, pero si los demás hilos están ocupados, el hilo actual lo procesa como en una ejecución secuencial normal
• Cuando no hay posibilidad de ejecución paralela, lo que Spice hace en el hot path se limita a algo parecido a hacer push/pop en una cola, sin inspeccionar realmente los elementos de la cola
• La coordinación real con otros hilos ocurre en un heartbeat fijo
  • Aproximadamente cada 100 microsegundos, un hilo revisa su cola de trabajo actual
  • Entrega la tarea del tope de la cola a otro hilo que esté esperando
  • Como la frecuencia del heartbeat es baja, aunque se gasten cientos de ns, la sobrecarga total sigue siendo pequeña

Comparación con benchmarks de Rayon

• La suma de un árbol binario de 100 millones de nodos es un caso donde la operación real es muy rápida y la sobrecarga del framework paralelo se hace muy visible
• Rayon de Rust y Spice se comparan con APIs de tipo fork/join, fáciles de leer y razonar
• En el benchmark de Rayon, la sobrecarga se midió en unos 15 ns
  • Aumentó de 7.48 ns a 22.99 ns
  • Con 4 hilos volvió a un nivel similar al rendimiento secuencial, pero usando 4 veces más CPU
  • Con 16 hilos, Rayon logró unas 14 veces de mejora respecto de sí mismo, y unas 4.5 veces respecto del baseline
• Spice muestra una mejora de velocidad de unas 11 veces al pasar de 1 a 16 hilos
  • Su escalado es algo peor que el de Rayon, pero gracias a su baja sobrecarga, la mejora frente al baseline se conserva casi por completo
• El benchmark se ejecutó en una instancia c4-standard-16 de Google Cloud, en un entorno de 16 núcleos
• No está claro por qué el baseline de Zig es aproximadamente 2 veces más rápido que el baseline de Rust
  • Según el assembly compilado, Rust guarda 5 registros en la pila y Zig guarda 3

Comportamiento en trabajos pequeños

• La suma de un árbol binario de 1000 nodos es una tarea muy corta, con un tiempo total de ejecución de apenas unos microsegundos
• En este caso, Rayon mostró una sobrecarga más alta, de unos 19 ns, y el rendimiento empeoró a medida que se agregaban más hilos
• Al usar 32 hilos en una máquina de 16 núcleos, el tiempo total de ejecución se volvió 60 veces más lento
  • No se puede afirmar que la misma desaceleración aparezca también en una máquina de 32 núcleos
  • Aun así, este comportamiento de escalado se considera preocupante
• El criterio tradicional para el procesamiento paralelo queda en la forma de “solo vale la pena cuando hay suficiente trabajo”
  • Puede ser necesario determinar el umbral de “suficiente trabajo” con benchmarks para cada entrada
  • En entradas como árboles binarios, donde no se puede conocer el tamaño total mirando solo la raíz, es difícil saber si el trabajo será pequeño
  • Si el 90% de la carga corresponde a entradas pequeñas, una desaceleración extrema puede convertirse en un problema
  • A medida que el programa evoluciona, también cambia el umbral de trabajo suficiente
• En el mismo caso de 1000 nodos, Spice determina que la ejecución es demasiado corta y no inicia el multithreading
  • Los hilos adicionales permanecen dormidos
  • Los núcleos pueden usarse para ejecutar otros programas

Diferencias entre work-stealing y Spice

• Spice ofrece un modelo fork/join, que normalmente se implementa con work-stealing
• En el work-stealing común, cada hilo tiene una cola de trabajo local, y cuando la cola queda vacía roba trabajo del extremo de la cola de otro hilo
• Las ineficiencias del work-stealing se resumen en tres puntos
  • Todo trabajo se convierte en una forma genérica de “llamada dinámica a función”, lo que introduce costo de despacho dinámico
  • La cola local es, en la práctica, una cola de la que todos los hilos pueden robar, por lo que requiere operaciones atómicas
  • Cuando hay contención en la cola aparece spinning, y bajo ciertas condiciones puede volverse entre 10 y 100 veces más lento
• Spice reduce directamente estas ineficiencias
  • El despacho dinámico de la cola de trabajo solo se usa cuando se envía trabajo a otro hilo
  • El trabajo que se realiza dentro de un solo hilo usa llamadas normales a funciones
  • El push en la cola de trabajo se procesa guardando el stack pointer, el stack frame actual y los registros, sin sincronizar con otros hilos
  • No hay spinning porque no hay bucles while que corran sin una llamada a wait()

Detalles de implementación

• Optimización de despacho estático

  • Spice asume que la mayoría de las tareas iniciadas con fork no serán tomadas por otros hilos, por lo que duplica dentro de la función la ruta de ejecución de ese código
  • Si la tarea no es ejecutada por otro hilo, el programa se comporta como una versión secuencial con solo unas pocas ramas predecibles adicionales
  • Esta estructura favorece optimizaciones de código como inlining y también la ejecución en CPU

• Señal heartbeat de baja sobrecarga

  • Heartbeat scheduling realiza la planificación localmente y con baja frecuencia
  • Aproximadamente cada 100 microsegundos, un hilo revisa su cola de trabajo local y envía una tarea a otro hilo
  • Si se gastan 100 ns cada 100 microsegundos, la sobrecarga total queda alrededor del 0.1%
  • En lugar de señales del sistema operativo, se llama a tick() de forma cooperativa
    • Al usar el helper t.call, tick() se invoca automáticamente
    • Un hilo de heartbeat separado cambia periódicamente el valor atomic heartbeat de cada hilo de false a true
    • tick() lee ese valor y, cuando es true, ejecuta el código de heartbeat
  • La función de heartbeat debe marcarse como cold; de lo contrario, la sobrecarga aumenta mucho

• Mutex global sin contención

  • El thread pool de Spice tiene un único mutex que se bloquea en varios lugares
  • Un mutex global se vuelve problemático cuando los hilos realmente se bloquean
  • En Spice, debido al heartbeat, normalmente solo un hilo ejecuta el heartbeat
  • No se ejecuta código de usuario mientras se sostiene el lock, y solo se protegen lecturas y escrituras simples de memoria que terminan en tiempo constante

• Lista doblemente enlazada sin ramas

  • Spice usa una lista doblemente enlazada para rastrear la cola de trabajo
  • fork() hace append al final, join() hace pop desde el final si todavía queda ahí, y al enviar a un worker de fondo se hace pop desde el frente
  • Un append típico necesita una condición para revisar si la lista está vacía
  • Spice mantiene un nodo head sentinel que siempre existe para que la lista nunca esté vacía, y realiza push/pop sin ramas

• Minimización del uso de pila

  • Future tiene estado queued o executing
  • El heartbeat convierte un future queued en executing
  • El estado adicional necesario para executing se coloca en una estructura asignada desde un pool separado, reduciendo el uso de pila de los future queued
  • Se usa una forma manual de tagged union que distingue queued/executing según si el primer campo prev_or_null es null

• Paso de valores por registros

  • Task contiene un puntero al worker propietario y un puntero a la cola de trabajo tail
  • LLVM muchas veces pasa structs por la pila, por lo que Spice define callWithContext, que recibe worker y job_tail como parámetros de función separados
  • Esta función se llama de modo que siempre se inlinee, permitiendo que los parámetros puntero se pasen por registros

Base de investigación y trabajos relacionados

• Spice se creó sobre la base de la investigación en heartbeat scheduling
• “The best multicore-parallelization refactoring you've never heard of” es un paper que introduce brevemente el concepto de heartbeat scheduling; se centra en un solo caso de uso, pero lo explica de forma generalizable
  • La solución de ese paper transforma el código a continuation-passing style para alternar entre ejecución secuencial y paralela
  • Spice empezó como un experimento con este enfoque, pero se observó que la sobrecarga superaba los 10 ns
• “Heartbeat scheduling: provable efficiency for nested parallelism” es el paper que presentó por primera vez heartbeat scheduling
  • Contiene mucha información conceptual, pero la implementación se basa en integración con un intérprete y está más enfocada en garantías teóricas
• “Task parallel assembly language for uncompromising parallelism” es un trabajo posterior que mejoró el rendimiento de heartbeat con un lenguaje assembly personalizado y signaling del sistema operativo
  • Se considera difícil integrarlo en lenguajes existentes

Limitaciones actuales

• Spice puede tener comportamientos bruscos si se usa incorrectamente
  • Es especialmente sensible a la forma en que se usan fork y join
  • Debe mejorarse con verificaciones en compile-time, assertions en debug-mode y cambios de API
• Hay mucho código de concurrencia, pero la cobertura de pruebas es 0
• No hay soporte nativo para procesar cada elemento de arrays o slices, un caso de uso común del paralelismo fino
• Faltan buenos documentos que expliquen cómo usarlo
• Por ahora solo se probó principalmente con un pequeño benchmark
  • Se considera que ese benchmark debería ser representativo, pero hacen falta benchmarks adicionales para validar los resultados
• Usa mucho @panic para manejo de errores
  • Para considerarse una biblioteca Zig adecuada, debería contemplar más el manejo de casos de error
• Se necesitan más benchmarks y pruebas sobre qué tan bien funciona en ReleaseSafe de Zig
• La base de código completa tiene unas 500 líneas, y actualmente el autor no tiene planes de desarrollo activo para mejorar Spice por falta de tiempo
• Se recomiendan mejoras mediante forks o reimplementaciones en otros lenguajes

[GN⁺]

Opiniones de Hacker News

• Esta implementación se basa en heartbeat scheduling, una corriente de investigación reciente, y logra una especie de control dinámico automático de granularidad de tareas amortizando el costo de crear paralelismo.
  Artículos relacionados:
  (2018) Heartbeat Scheduling: Provable Efficiency for Nested Parallelism. https://www.andrew.cmu.edu/user/mrainey/papers/heartbeat.pdf
  (2021) Task Parallel Assembly Language for Uncompromising Parallelism. https://users.cs.northwestern.edu/~simonec/files/Research/pa...
  (2024) Compiling Loop-Based Nested Parallelism for Irregular Workloads. https://users.cs.northwestern.edu/~simonec/files/Research/pa...
  (2024) Automatic Parallelism Management. https://www.cs.cmu.edu/~swestric/24/popl24-par-manage.pdf

  • Esto es realmente interesante; cuando escribí Spice solo conocía los dos primeros artículos.
    Sin duda voy a revisar también los dos últimos.

• Aunque no leí el código en detalle, la expresión sobrecarga de menos de 1 nanosegundo parece una frase de marketing engañosa.
  A primera vista, parece una medición compleja de “tiempo por tarea” calculada en una situación donde la cantidad de hilos es mucho menor que la cantidad de “tareas”.

  • Soy el autor.
    Sabía que algunos reaccionarían negativamente a esa frase, pero la intención es ayudar a entender mejor cuándo y cómo conviene usar Spice y Rayon.
    Recomiendo leer el documento de benchmarks: https://github.com/judofyr/spice/blob/main/bench/README.md
    Normalmente, al comparar código paralelo, solo se compara una implementación secuencial/de referencia contra una implementación paralela que usa todos los hilos (16). En el caso de 100M, los números de Rayon fueron 7.48 ns para la versión secuencial y 1.64 ns para Rayon, y con eso es fácil concluir: “Rayon fue 4.5 veces más rápido en este problema, pero usó 16 hilos, así que no escala tan bien”. Eso es cierto, pero es difícil aprender cómo aplicarlo a otros tipos de problemas.
    Si se corre el mismo benchmark con distintas cantidades de hilos, aparecen cosas más interesantes. El scheduler de Rayon es bastante bueno para repartir trabajo entre hilos separados, pero el mecanismo completo de ejecución de tareas tiene una sobrecarga de unos 15 ns. Aunque este programa sea un ejemplo totalmente inútil, aprendemos un hecho que se puede aplicar después: si vas a usar Rayon, probablemente la unidad mínima de trabajo debería ser de alrededor de más de 7 ns. La excepción es si te importa más reducir la latencia total aun sacrificando throughput total.
    La documentación de Rayon no da cifras; solo dice que “conceptualmente, una llamada a join() es similar a crear dos hilos y ejecutar un closure en cada uno, pero la implementación es bastante diferente y tiene una sobrecarga muy baja”: https://docs.rs/rayon/latest/rayon/fn.join.html
    Si hubiera querido ser engañoso, habría dicho: “Spice acelera 10 veces y Rayon 4.5 veces, así que Spice es el doble de rápido que Rayon”.
  • Para que “sobrecarga de menos de 1 nanosegundo” fuera una frase de marketing engañosa, Spice con 1 hilo - implementación de referencia no paralela tendría que ser mayor que 1 ns.
    Los resultados de las pruebas respaldan la afirmación: https://github.com/judofyr/spice/tree/main/bench
  • Creo que esto también es parecido al lugar ecológico de Rayon que se cita.
    Es una estructura en la que hay que procesar miles o millones de tareas, se quiere paralelizar al máximo dentro de decenas de núcleos, y no se quiere que la sobrecarga de scheduling se coma el rendimiento; por eso se mira la sobrecarga por tarea.
  • Ayer, cuando apareció en Reddit, expresé mis dudas sobre el benchmark.
    El benchmark afirma una sobrecarga de 0.36 ns por llamada, pero solo incluye la función de cálculo. Hay un segundo hilo haciendo scheduling que no entra en la cifra de sobrecarga. Parece que se corrió en una máquina de 8 núcleos con hyperthreading, es decir, 16 hilos; si asumimos 3 GHz, literalmente es una sobrecarga de un ciclo.
    Con cada hilo adicional, la sobrecarga aumenta por la contención de locks. Con 16 hilos sube a 3.6 ns, un aumento de 10 veces. Es una suposición, pero si fuera así, significaría que esos 0.36 ns de sobrecarga incluyen un lock sin contención, lo cual es imposible. También hay otras cosas raras en los datos del benchmark. O no entiendo qué se está midiendo realmente, o puede haber un bug en el código del benchmark.
    Si multiplicas todos los valores, parece que el tiempo se mide en milisegundos. Cuando se calcula el tiempo de ejecución y se convierte a milisegundos, queda redondeado a enteros. ¿No suelen los benchmarkers usar mejor precisión que eso? Puede que hayan usado simplemente time prog y los datos sean muy ruidosos, o que hayan elegido una métrica completamente inútil para este propósito.
  • Leyendo el README, creo que explica con mucha precisión qué significa exactamente la afirmación del título.
    No existe un título sin ninguna posibilidad de malentendido, y este título me parece razonable. Yo lo interpreté como que la biblioteca tiene una latencia extremadamente baja bajo cierto criterio de medición, y bastaba con revisar el README para confirmar cuál era ese criterio. Está bastante claro.

• No estoy muy familiarizado con este campo, pero me gusta el modelo de concurrencia que se presenta aquí
  El README también está muy bien escrito, y con solo leerlo uno se da una idea de lo que está pasando. Aunque en algunas partes me hizo arquear una ceja. Por suerte, el código es bastante fácil de leer

  • Al compilar con zig build en modo Debug, obtuve Baseline,3.92809172, Spice 1 thread,19.1012624
    Al compilar con zig build --release=safe en modo ReleaseSafe, obtuve Baseline,3.264224280000001, Spice 1 thread,3.78043278
    Así que Spice sufre una degradación de rendimiento bastante grande si no es un build de release. La implementación de referencia no se vuelve igual de lenta en el modo de build Debug de Zig
    La versión usada fue zig 0.13.0

• Es un trabajo de investigación interesante; no solo el código en sí, sino también los criterios de decisión son buenos y la documentación está bien escrita
  También vale la pena leer el paper de 2018 sobre planificación por latidos: https://www.andrew.cmu.edu/user/mrainey/papers/heartbeat.pdf

• Lista de limitaciones del proyecto: https://github.com/judofyr/spice?tab=readme-ov-file#limitati...

  • Este proyecto es excelente, y hay que reconocer mucho al autor por tomarse el tiempo de hacerlo funcionar y compartirlo con la comunidad de HN
    HN también es un lugar conocido, en general, por reacciones excesivamente críticas o pesimistas
    Me parece bien que el autor reconozca las limitaciones de su proyecto, y con eso evita de antemano la mayor parte del cinismo habitual
    En la parte que dice “Falta de pruebas: Spice tiene mucho código de concurrencia complicado, pero la cobertura de pruebas es 0. Esto debería mejorar antes de usar Spice de forma responsable en trabajos importantes”, dejando aparte probar la exactitud de la ejecución de trabajos importantes, creo que una biblioteca que implementa código de concurrencia complicado debería tener al menos pruebas de regresión
    Como usuario final, me pregunto qué garantía hay de que una funcionalidad que funciona hoy no se rompa mañana por una regresión sutil y maliciosa
    SQLite tiene 590 veces más código de pruebas y scripts de prueba que código fuente C puro https://www.sqlite.org/testing.html. Además de su estabilidad y portabilidad, este también es uno de los varios motivos por los que SQLite se convirtió en la base de datos embebida estándar de facto en todo el mundo
    Es un ejemplo algo forzado de comparar manzanas con naranjas, pero la idea general sigue siendo válida. Las pruebas de regresión generan estabilidad y confianza en un proyecto
    Donde trabajo, si realmente hay que postergar las pruebas de regresión básicas, normalmente creamos un ticket de seguimiento dentro del mismo epic para asegurarnos de que al menos se escriban antes del lanzamiento de la funcionalidad/epic

• Según la explicación, usa espera activa en los workers para lograr latencias del orden de nanosegundos
  Me pregunto qué tan realista es la espera activa en aplicaciones grandes con decenas de miles de trabajos. Si los trabajos no están basados en hilos sino en asincronía, quizá sea viable porque solo hay tantos esperadores como el tamaño N del pool de hilos del ejecutor. En cualquier caso, una estructura así consumirá más energía
  Relacionado con esto, desde hace tiempo me pregunto si hay alguna forma de que el productor de trabajos despierte más rápido al consumidor sin espera activa. Por ejemplo, he pensado si sería posible ejecutar al consumidor dentro del intervalo de tiempo del productor
  También relacionado, me pregunto si una operación FUTEX_WAKE en espacio de usuario podría llegar a ser posible y reducir el costo de despertar al consumidor a la mitad de lo normal, es decir, solo al costo del lado del consumidor

• Está limpio y también enlaza buenos papers
  Aunque me gustaría que la comparación fuera contra tareas de OpenMP. He oído que Rayon tiene fama de ser algo lento

• La planificación cooperativa es la base de muchos patrones que producen excelentes métricas

  • Pero no es planificación cooperativa en el sentido de que los trabajos cedan el control entre sí
    Se trata principalmente de cooperar para poder pasar algunos trabajos a otros hilos, y ni siquiera ocurre siempre, sino solo una vez por cada latido. Como la planificación ocurre con poca frecuencia, el costo amortizado es bajo

• También vale la pena consultar el README bajo bench: https://github.com/judofyr/spice/blob/main/bench/README.md