Spice : une technique de parallélisme fin en Zig avec une surcharge inférieure à la nanoseconde
(github.com/judofyr)- Spice est un projet de recherche qui vise à ajouter des possibilités d’exécution parallèle aux fonctions en Zig via le heartbeat scheduling, tout en maintenant la surcharge sous 1 ns
- La conception centrale repose sur
fork, qui signale un travail pouvant être pris en charge par un autre thread, avec une structure de repli où, si aucun thread ne le récupère, le thread courant l’exécute lui-même au moment dujoin - Dans un benchmark de somme sur un arbre binaire de 100 millions de nœuds, Rayon affichait une surcharge d’environ 15 ns sur 1 thread et un gain d’environ 4,5x par rapport à la baseline sur 16 threads, tandis que Spice obtenait presque intact un gain d’environ 11x par rapport à la baseline sur 16 threads
- Sur des tâches très courtes, comme avec 1000 nœuds, Rayon présentait un cas où l’exécution totale devenait 60 fois plus lente avec 32 threads, tandis que Spice n’amorce pas le multithreading s’il estime que le parallélisme n’est pas nécessaire et laisse les threads supplémentaires en veille
- L’implémentation actuelle manque de tests, de documentation, de prise en charge des tableaux et slices, ainsi que de benchmarks supplémentaires, utilise souvent
@panic, et l’auteur précise qu’il faut bien comprendre ses nombreuses limites avant tout usage en production
Le problème que Spice cherche à résoudre
- Spice est un projet visant à implémenter un parallélisme très fin en Zig avec une faible surcharge
- L’objectif est d’éviter que les utilisateurs aient à se demander en permanence si l’ajout de parallélisme va ralentir leur programme
- Des benchmarks précis restent nécessaires pour maximiser les performances, mais Spice est conçu pour que l’ajout de parallélisme n’entraîne généralement presque aucun surcoût réel
- Le projet est avant tout un projet de recherche et, pour un usage en production, il faut d’abord en vérifier les limitations
- Dans une mise à jour de septembre 2024, Chili, un portage de cette idée en Rust, a été présenté
Mode d’utilisation et API principale
- Les fonctions parallèles de Spice prennent
*spice.Tasken paramètre afin de coordonner le travail - Les appels récursifs ou les appels de fonctions pouvant être parallélisés ne doivent pas être invoqués directement, mais via
t.call forkdéfinit une tâche pouvant être exécutée par un autre thread- Après
fork, la fonction doit aussi effectuer elle-même un travail utile joinattend qu’un autre thread ait terminé la tâche, mais peut retournernullnullsignale qu’aucun autre thread n’a pris cette tâche- Dans ce cas, le thread courant doit exécuter lui-même cette tâche
Une conception où « tous les travaux ne viennent pas de la file »
- L’idée centrale de Spice est que tous les travaux ne commencent pas dans une file
forkindique qu’il existe du travail qu’un autre thread pourrait exécuter, mais si les autres threads sont occupés, le thread courant le traite comme dans une exécution séquentielle classique- Lorsqu’il n’y a pas de possibilité réelle d’exécution parallèle, sur le hot path Spice se contente essentiellement de push/pop dans une file, sans examiner réellement les éléments de cette file
- La coordination réelle avec les autres threads n’a lieu qu’à des heartbeats fixes
- Environ toutes les 100 microsecondes, un thread vérifie sa file de tâches courante
- Il transmet la tâche située en haut de la file à un autre thread en attente
- Comme la fréquence des heartbeats est faible, même quelques centaines de ns ne représentent qu’une faible surcharge globale
Comparaison avec les benchmarks de Rayon
- La somme sur un arbre binaire de 100 millions de nœuds est un cas où le calcul réel est très rapide, ce qui rend la surcharge des frameworks parallèles particulièrement visible
- Rayon en Rust et Spice sont comparés sous la forme d’une API fork/join facile à lire et à raisonner
- Dans le benchmark de Rayon, la surcharge mesurée est d’environ 15 ns
- Elle passe de 7,48 ns à 22,99 ns
- Avec 4 threads, les performances reviennent à peu près au niveau séquentiel, mais avec une utilisation CPU multipliée par 4
- Avec 16 threads, Rayon obtient un gain d’environ 14x selon sa propre référence, mais d’environ 4,5x par rapport à la baseline
- Spice montre un gain d’environ 11x en passant de 1 à 16 threads
- Le scaling est légèrement moins bon que Rayon, mais grâce à sa faible surcharge, le gain par rapport à la baseline est presque entièrement conservé
- Le benchmark a été exécuté sur une instance Google Cloud
c4-standard-16, dans un environnement à 16 cœurs - La raison pour laquelle la baseline Zig est environ 2 fois plus rapide que la baseline Rust n’est pas claire
- D’après l’assembly compilé, Rust sauvegarde 5 registres sur la pile, contre 3 pour Zig
Comportement sur les petites tâches
- La somme d’un arbre binaire de 1000 nœuds est une tâche très courte, dont le temps total d’exécution se mesure en quelques microsecondes
- Dans ce cas, Rayon affiche une surcharge encore plus élevée, d’environ 19 ns, et les performances se dégradent à mesure qu’on ajoute des threads
- Sur une machine à 16 cœurs, avec 32 threads, le temps total d’exécution devient 60 fois plus lent
- Cela ne signifie pas forcément que le même ralentissement se produirait sur une machine à 32 cœurs
- Mais ce comportement de scaling est jugé préoccupant
- En traitement parallèle traditionnel, on en vient souvent à conclure que cela ne vaut la peine que s’il y a « suffisamment de travail »
- Le seuil de « suffisamment de travail » peut devoir être déterminé par des benchmarks selon les entrées
- Avec des entrées comme un arbre binaire, où l’on ne peut pas connaître toute la taille en regardant seulement la racine, il est difficile de savoir si la tâche est petite
- Si 90 % de la charge correspond à de petites entrées, un ralentissement extrême peut devenir problématique
- À mesure que le programme évolue, le seuil de travail suffisant peut lui aussi changer
- Dans ce même cas à 1000 nœuds, Spice estime que le temps d’exécution est trop court et ne lance pas le multithreading
- Les threads supplémentaires restent en veille
- Les cœurs peuvent donc être utilisés pour exécuter d’autres programmes
Différences entre le work-stealing et Spice
- Spice propose un modèle fork/join, généralement implémenté via le work-stealing
- Dans une implémentation classique du work-stealing, chaque thread possède une file de tâches locale et, lorsqu’elle est vide, vole des tâches à l’extrémité de la file d’un autre thread
- Les inefficacités du work-stealing sont résumées en trois points
- Toutes les tâches deviennent des « appels de fonction dynamiques » génériques, ce qui introduit un coût de dispatch dynamique
- La file locale est en pratique une file dont tous les threads peuvent voler des éléments, ce qui impose des opérations atomiques
- En cas de contention sur la file, du spinning peut apparaître et, dans certaines conditions, ralentir l’exécution de 10 à 100 fois
- Spice réduit directement ces inefficacités
- Le dispatch dynamique de la file de tâches n’est utilisé que lorsqu’une tâche est envoyée à un autre thread
- Les tâches exécutées au sein d’un seul thread utilisent des appels de fonction ordinaires
- Les push dans la file de tâches se font via le pointeur de pile, la stack frame courante et la sauvegarde des registres, sans synchronisation avec les autres threads
- Il n’y a pas de boucle
whilequi tourne sans appel àwait(), donc pas de spinning
Détails d’implémentation
-
Optimisation par dispatch statique
- Spice part du principe que la plupart des tâches
forkne seront pas récupérées par d’autres threads, et duplique donc dans la fonction les chemins d’exécution correspondants - Si la tâche n’est pas exécutée par un autre thread, le programme se comporte comme une version séquentielle à laquelle on a simplement ajouté quelques branches prévisibles
- Cette structure favorise l’inlining, les optimisations de code et l’exécution CPU
- Spice part du principe que la plupart des tâches
-
Signal heartbeat à faible surcharge
- Le heartbeat scheduling effectue l’ordonnancement localement et à basse fréquence
- Environ toutes les 100 microsecondes, un thread inspecte sa file de tâches locale et envoie du travail à un autre thread
- Si l’on dépense 100 ns toutes les 100 microsecondes, la surcharge totale reste de l’ordre de 0,1 %
- Au lieu de signaux du système d’exploitation, Spice utilise une approche coopérative via
tick()- Lors de l’usage du helper
t.call,tick()est appelé automatiquement - Un thread heartbeat dédié bascule périodiquement la valeur heartbeat atomique de chaque thread de
falseàtrue tick()lit cette valeur et, si elle vauttrue, exécute le code heartbeat
- Lors de l’usage du helper
- La fonction heartbeat doit être marquée cold, faute de quoi la surcharge devient bien plus importante
-
Mutex global sans contention
- Le pool de threads de Spice utilise un unique mutex verrouillé depuis plusieurs endroits
- Un mutex global devient problématique lorsqu’un thread se retrouve réellement bloqué
- Dans Spice, à cause du heartbeat, un seul thread exécute généralement le heartbeat à la fois
- Aucun code utilisateur n’est exécuté sous verrou, qui ne protège que de simples lectures/écritures mémoire en temps constant
-
Liste doublement chaînée sans branchement
- Spice utilise une liste doublement chaînée pour suivre la file de tâches
fork()fait un append en fin de liste,join()pop depuis la fin si l’élément est encore présent, et l’envoi à un worker d’arrière-plan pop depuis le début- Un append classique nécessite en général une condition pour savoir si la liste est vide
- Spice utilise un nœud sentinelle de tête toujours présent, ce qui garantit qu’elle n’est jamais vide et permet des push/pop sans branchement
-
Utilisation minimale de la pile
Futurepeut être dans l’état queued ou executing- Le heartbeat convertit un future queued en future executing
- L’état supplémentaire nécessaire à l’état executing est stocké dans une structure distincte allouée dans un pool, afin de réduire l’utilisation de pile du future en file
- Une forme manuelle de tagged union est utilisée, en distinguant l’état queued/executing selon que le premier champ
prev_or_nullvautnullou non
-
Passage des valeurs par registres
Taskcontient un pointeur vers le worker propriétaire et un pointeur vers la queue tail des tâches- LLVM a souvent tendance à passer les structs via la pile, donc Spice définit
callWithContext, qui reçoitworkeretjob_tailcomme paramètres de fonction séparés - Cette fonction est toujours appelée de manière à être inlinée, afin que les pointeurs soient passés dans des registres
Fondements de recherche et travaux liés
- Spice est basé sur des recherches autour du heartbeat scheduling
- “The best multicore-parallelization refactoring you've never heard of” est un article qui présente brièvement le concept de heartbeat scheduling, en se concentrant sur un cas d’usage unique mais avec une explication généralisable
- La solution proposée dans cet article transforme le code en continuation-passing style pour basculer entre exécution séquentielle et parallèle
- Spice est parti d’une expérimentation de cette approche, mais la surcharge dépassait alors 10 ns
- “Heartbeat scheduling: provable efficiency for nested parallelism” est l’article qui a introduit le heartbeat scheduling
- Il est riche en informations conceptuelles, mais son implémentation repose sur une intégration à un interpréteur et met davantage l’accent sur les garanties théoriques
- “Task parallel assembly language for uncompromising parallelism” est un travail ultérieur qui améliore les performances du heartbeat à l’aide d’un langage assembleur personnalisé et de la signalisation de l’OS
- Cette approche est jugée difficile à intégrer dans des langages existants
Limitations actuelles
- Spice peut avoir des comportements abrupts en cas de mauvaise utilisation
- En particulier, son fonctionnement est sensible à la manière d’utiliser
forketjoin - Cela devrait être amélioré via des vérifications à la compilation, des assertions en mode debug et des changements d’API
- En particulier, son fonctionnement est sensible à la manière d’utiliser
- Le code concurrent est abondant, mais la couverture de tests est de 0
- Il n’existe pas de prise en charge native du traitement de chaque élément d’un tableau ou d’une slice, pourtant fréquent en parallélisme fin
- La documentation expliquant l’usage reste insuffisante
- Les tests actuels reposent essentiellement sur un seul petit benchmark
- Ce benchmark est considéré comme représentatif, mais des benchmarks supplémentaires sont nécessaires pour valider les résultats
- La gestion des erreurs utilise souvent
@panic- Pour être considérée comme une bibliothèque Zig correcte, la gestion des cas d’erreur devrait être bien davantage prise en compte
- Des benchmarks et tests supplémentaires sont nécessaires pour savoir dans quelle mesure Spice fonctionne bien avec
ReleaseSafede Zig - L’ensemble du code représente environ 500 lignes, et l’auteur n’a actuellement pas de plan de développement actif pour améliorer Spice par manque de temps
- Les améliorations via des forks ou des réimplémentations dans d’autres langages sont encouragées
1 commentaires
Commentaires sur Hacker News
Cette implémentation repose sur le heartbeat scheduling, un courant de recherche récent, et amortit le coût de création du parallélisme afin d’atteindre une sorte de contrôle dynamique automatique de la granularité des tâches
Articles associés :
(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
Je compte absolument regarder aussi les deux suivants
Je n’ai pas lu le code en détail, mais l’expression overhead inférieur à 1 nanoseconde ressemble à une formule marketing trompeuse
Au premier abord, cela semble être une mesure complexe du « temps par tâche » calculée dans une situation où le nombre de threads est bien inférieur au nombre de « tâches »
Je savais que certains réagiraient négativement à cette formulation, mais l’objectif était d’aider à mieux comprendre quand et comment utiliser Spice et Rayon de manière pertinente
Je recommande de lire la documentation des benchmarks : https://github.com/judofyr/spice/blob/main/bench/README.md
En général, pour comparer du code parallèle, on compare uniquement une implémentation séquentielle/de référence à une implémentation parallèle utilisant tous les threads (16). Dans le cas 100M, les chiffres de Rayon étaient de 7.48ns pour la version séquentielle et 1.64ns pour Rayon, et il est alors facile de conclure : « Rayon est 4,5 fois plus rapide sur ce problème, mais comme il utilise 16 threads, ce n’est pas une bonne comparaison. » C’est vrai, mais cela n’aide pas beaucoup à apprendre comment appliquer cela à d’autres types de problèmes
Quand on exécute le même benchmark avec différents nombres de threads, on voit quelque chose de plus intéressant. Le scheduler de Rayon est assez bon pour répartir le travail sur des threads séparés, mais l’ensemble du mécanisme d’exécution des tâches a un overhead d’environ 15ns. Même si ce programme est un exemple totalement inutile, on peut en tirer un enseignement réutilisable ensuite : pour utiliser Rayon, la plus petite unité de travail doit probablement être supérieure à 7ns environ. Sauf si réduire la latence globale est plus important que préserver le débit total
La documentation de Rayon ne donne pas de chiffre et dit seulement : « conceptuellement, un appel à join() ressemble à la création de deux threads exécutant chacun une fermeture, mais l’implémentation est assez différente et présente un overhead très faible » : https://docs.rs/rayon/latest/rayon/fn.join.html
Si j’avais voulu induire les gens en erreur, j’aurais dit : « Spice donne un gain de vitesse de 10x et Rayon de 4,5x, donc Spice est deux fois plus rapide que Rayon »
Les résultats de test confirment cette affirmation : https://github.com/judofyr/spice/tree/main/bench
La structure consiste à devoir traiter des milliers à des millions de tâches, vouloir paralléliser au maximum sur quelques dizaines de cœurs, et ne pas se faire manger par l’overhead de scheduling, d’où l’attention portée à l’overhead par tâche
Les benchmarks revendiquent un overhead de 0.36ns par appel, mais ils n’incluent que la fonction de calcul. Il y a un deuxième thread qui effectue le scheduling, et il n’entre pas dans la valeur d’overhead. Cela semble avoir été exécuté sur une machine 8 cœurs avec hyperthreading, donc 16 threads, et en supposant 3GHz, cela représente littéralement un overhead d’un seul cycle
L’overhead augmente avec chaque thread supplémentaire à cause de la contention sur les verrous. À 16 threads, il passe à 3.6ns, soit une hausse par 10. C’est une supposition, mais si c’est le cas, cela voudrait dire que l’overhead de 0.36ns inclut un verrou sans contention, ce qui est impossible. Il y a aussi d’autres points étranges dans les données de benchmark. Soit je ne comprends pas ce qui est réellement mesuré, soit il peut y avoir un bug dans le code du benchmark
Quand on multiplie toutes les valeurs, on a l’impression que le temps est mesuré en millisecondes. Le temps d’exécution est calculé puis converti en millisecondes, ce qui tombe sur des nombres entiers. En général, les outils de benchmark n’utilisent-ils pas une meilleure précision que ça ? Il est possible qu’ils aient juste utilisé
time prog, ce qui rend les données très bruitées, ou qu’ils aient choisi un indicateur totalement inutile pour cet objectifIl n’existe aucun titre totalement exempt d’ambiguïté, et celui-ci me semble acceptable. Ce que j’en ai retenu, c’est qu’il s’agit d’une bibliothèque avec une latence extrêmement faible selon un certain critère de mesure, et il suffisait de vérifier ce critère dans le README. C’est assez clair
Je ne connais pas très bien ce domaine, mais le modèle de concurrence présenté ici me plaît.
Le README est aussi très bien rédigé, et rien qu’en le lisant on comprend globalement ce qui se passe. Cela dit, quelques points m’ont fait tiquer. Heureusement, le code est assez facile à lire.
zig build, j’ai obtenuBaseline,3.92809172etSpice 1 thread,19.1012624.En mode ReleaseSafe, en compilant avec
zig build --release=safe, j’ai obtenuBaseline,3.264224280000001etSpice 1 thread,3.78043278.Donc Spice subit une dégradation de performances assez importante hors build de release. L’implémentation de référence ne ralentit pas à ce point dans le mode Debug de Zig.
La version utilisée est zig 0.13.0.
C’est un travail de recherche intéressant, et non seulement le code lui-même, mais aussi les éléments qui fondent le jugement sont bons, avec une documentation bien écrite.
L’article de 2018 sur le heartbeat scheduling mérite aussi la lecture : https://www.andrew.cmu.edu/user/mrainey/papers/heartbeat.pdf
Liste des limitations du projet : https://github.com/judofyr/spice?tab=readme-ov-file#limitati...
HN est aussi connu pour ses réactions généralement trop critiques ou pessimistes.
J’apprécie aussi que l’auteur reconnaisse les limites de son propre projet, ce qui désamorce d’avance une bonne partie du cynisme habituel.
Quand il écrit « Tests insuffisants : Spice contient beaucoup de code de concurrence délicat, mais la couverture de tests est nulle. Cela doit être amélioré pour utiliser Spice de manière responsable dans des tâches importantes », je pense qu’indépendamment des tests de correction d’exécution pour les tâches critiques, une bibliothèque qui implémente du code de concurrence délicat devrait au minimum avoir des tests de régression.
Du point de vue de l’utilisateur final, je me demande quelle garantie existe pour qu’une fonctionnalité qui marche aujourd’hui ne soit pas cassée demain par une régression subtile et malveillante.
SQLite a 590 fois plus de code de test et de scripts de test que de code source C pur https://www.sqlite.org/testing.html. En plus de sa stabilité et de sa portabilité, c’est aussi l’une des nombreuses raisons pour lesquelles SQLite est devenu la base de données embarquée de facto standard dans le monde entier.
C’est un exemple un peu forcé, qui compare des pommes et des oranges, mais l’idée générale reste valable. Les tests de régression apportent stabilité et fiabilité à un projet.
Là où je travaille, si on doit absolument repousser des tests de régression de base, on crée en général un ticket de suivi dans la même epic, afin qu’ils soient au moins écrits avant la sortie de la fonctionnalité ou de l’epic.
D’après l’explication, les workers utilisent une attente active pour obtenir une latence de l’ordre de la nanoseconde.
Je me demande à quel point l’attente active est réaliste dans de grosses applications comptant des dizaines de milliers de tâches. Si les tâches sont asynchrones plutôt que basées sur des threads, cela peut peut-être passer, puisqu’il n’y a que N attenteurs, correspondant à la taille N du pool de threads de l’exécuteur. Quoi qu’il en soit, ce genre de structure consommera davantage d’énergie.
À ce sujet, je me demande depuis longtemps s’il existe un moyen pour un producteur de tâches de réveiller les consommateurs plus rapidement sans attente active. Par exemple, je me suis demandé s’il serait possible de faire exécuter le consommateur dans la tranche de temps du producteur.
Toujours sur le même sujet, je me demande aussi si une opération FUTEX_WAKE en espace utilisateur pourrait devenir possible, afin de réduire de moitié le coût du réveil du consommateur, c’est-à-dire au seul coût côté consommateur.
Des articles clairs et de qualité sont aussi liés.
Cela dit, j’aurais préféré que la comparaison se fasse avec des tâches OpenMP. J’ai déjà entendu dire que Rayon avait la réputation d’être un peu lent.
Le scheduling coopératif est à la base de nombreux schémas qui affichent d’excellents chiffres.
Il s’agit surtout de coopérer pour permettre de transférer certaines tâches à d’autres threads, et cela ne se produit pas en permanence, seulement une fois par heartbeat. Comme le scheduling a lieu rarement, son coût amorti est faible.
Le README sous bench vaut aussi le détour : https://github.com/judofyr/spice/blob/main/bench/README.md