Moteur Peredvizhnikov : un moteur de jeu lock-free écrit en C++20

 (github.com/eduard-permyakov)
4 points par GN⁺ 2023-09-11 | 1 commentaires | Partager sur WhatsApp
  • Un moteur de jeu entièrement lock-free écrit en C++20, qui implémente le modèle d’acteurs pour le calcul concurrent au-dessus des primitives de coroutines du langage
  • Grâce à l’abstraction du modèle d’acteurs, il est possible de développer une logique parallèle complexe tout en restant isolé des détails de synchronisation entre threads
  • Son implémentation entièrement lock-free garantit la progression même en cas d’arrêt arbitraire d’un thread, évite les interblocages, offre une latence prévisible pour la réaction aux événements critiques et assure une tolérance aux pannes
  • Le moteur garantit de continuer à fonctionner même si l’un des threads de travail s’arrête de manière asynchrone
  • L’implémentation comprend notamment la Software Transactional Memory, des files lock-free, des primitives de sérialisation lock-free, std::atomic_shared_ptr, un ordonnanceur lock-free, un allocateur mémoire lock-free et un DAG au moment de la compilation
  • Les algorithmes lock-free, les choix de conception et les benchmarks sont présentés dans le document Peredvizhnikov Engine: Design and Implementation of a Completely Lock-Free Scheduler
  • Pour faciliter la conception orientée données, le moteur implémente une base de données en mémoire optimisée pour l’accès par composant et capable de prendre en charge de grands ensembles de données
  • Cette base de données en mémoire repose sur les structures de données Flat Hash Map et Bitwise Trie with Bitmap
  • La seule plateforme actuellement prise en charge est Linux, et la compilation depuis les sources nécessite Clang++ 16
  • Le code source est fourni sous licence GPLv3, et l’autorisation d’utiliser tout ou partie du code sous une autre licence peut être accordée au cas par cas

À lire aussi

1 commentaires

 
GN⁺ 2023-09-11
Avis sur Hacker News

  • Dans mon framework Actor, j’utilise un simple std::deque comme file de pointeurs de méthodes, et lorsque j’ajoute des messages à la file, je verrouille selon l’approche Benaphore.
    À l’origine, comme Futex, cela combine des opérations atomiques et des primitives de verrouillage ; dans mon cas, la primitive de verrouillage fonctionne comme une combinaison spinlock/mutex selon le nombre de tentatives. D’après les benchmarks, il est très rare que la fonction de push des messages se bloque, et la probabilité d’un changement de contexte par le système d’exploitation est faible ; même si, de temps à autre, un thread verrouillé est swappé, cela n’arrive pas assez souvent pour justifier le coût d’un algorithme lock-free.
    En résumé, une file non lock-free est bien plus rapide qu’une file lock-free, mais il faut accepter de très rares longues latences dues à des changements de contexte où personne ne parvient à acquérir le verrou. Sur du matériel moderne, on peut mettre en file 10 millions de messages par seconde par thread worker.

    • Tu dis « à l’origine, Futex », mais Benaphore est une idée assez ancienne, et Futex n’est pas simplement un « Benaphore à la Linux ».
      Le point essentiel est qu’un objet noyau, c’est-à-dire une primitive de verrouillage séparée, n’est pas réellement nécessaire. C’est là que l’idée passe de « une méthode que tout le monde connaît » à « une fonctionnalité à intégrer immédiatement dans le système d’exploitation ».
      Dans la conception de Futex, au lieu d’un objet de synchronisation du système d’exploitation pour gérer les collisions, l’OS maintient une liste de correspondances adresse→thread. Si le thread T s’endort sur le futex à l’adresse X, la liste enregistre que X pointe vers T ; lorsqu’une demande de réveil du futex X arrive, l’OS parcourt la liste et réveille T.
      La différence apparaît dans les limites. Un Benaphore et assimilé sont des ressources globales coûteuses ; il me semble que BeOS n’en autorisait qu’environ 65 536 par machine. Mais un Futex n’est que de la mémoire, donc il n’y a aucune raison d’imposer une limite.
    • Pour un article aussi intéressant, il faudrait mettre un lien vers le code. Cela étayerait les affirmations, et les gens comme moi, intrigués par l’idée, auraient tout de suite envie de regarder l’implémentation.
    • Cela dépend énormément des détails du cas. S’il y a beaucoup de contention, les performances chutent brutalement, et même les instructions atomiques peuvent devenir un goulot d’étranglement (https://stackoverflow.com/q/2538070).
      Je pense que l’observation selon laquelle, dans beaucoup de cas, on peut simplement utiliser des verrous sans s’en inquiéter est correcte. Mais il existe aussi des applications ou des situations où l’on peut faire mieux. Si le consommateur retire tous les éléments de la file avec une seule opération de verrouillage, et que les producteurs signalent le consommateur, on peut améliorer l’efficacité de la file et le débit en faisant attention. Par exemple, il ne faut pas envoyer un signal à chaque insertion, mais seulement lorsque la file passe de vide à non vide.
    • Les structures de données lock-free ne servent-elles pas davantage à réduire l’impact de la contention qu’à augmenter le débit en faible contention ?
    • Le fait que ce « coût soit acceptable » a une exception : les personnes ayant des exigences fortes pour lesquelles les longues latences imprévisibles et rares mentionnées ne doivent absolument jamais se produire.

  • Le scheduler lock-free a clairement l’air intéressant, et la linéarisabilité de la diffusion d’événements ressort particulièrement. Cela dit, dans les benchmarks de l’article, le meilleur résultat avec 12 paires d’actors (et 12 cœurs ?) est de 43 500 messages par seconde, et le graphe monocœur tourne aussi autour de 5 000 messages par seconde, ce qui est étonnamment bas pour ce type de benchmark.
    Comme le moteur exige Linux et, plus important encore, x86 (à cause des instructions assembleur), je n’ai pas encore pu reproduire, mais j’attendrais au moins environ 1 million de requêtes par seconde par paire d’actors. Si l’on pense à un cas comme Erlang, en dessous de cela l’overhead devient prohibitif.
    Ce moteur se concentre sur le passage de messages, mais d’expérience cette approche est très difficile à manier. Les machines à états sont difficiles, et le deviennent encore plus lorsqu’on travaille avec plusieurs sous-actors. Fondamentalement, je vois les actors moins comme du passage de messages que comme un moyen d’isoler l’état sans verrou. Je pense que les actors Swift ont fait les choses correctement : utiliser des appels de méthodes plutôt que des messages rend non seulement le raisonnement plus simple, mais indique aussi les points supplémentaires où le contexte peut changer à l’exécution, sans forcément faire intervenir le scheduler. L’état partagé est lent et nuit à la scalabilité.
    J’ai récemment créé une bibliothèque header-only qui implémente quelque chose de similaire aux actors Swift avec les coroutines C++20. Si cela vous intéresse, cherchez « coroactors ». Sans contention, j’obtenais environ 10 millions de requêtes par seconde, et avec contention et dépendance au scheduler, je trouvais déjà que 1 à 3 millions de requêtes par seconde représentaient un overhead trop élevé. Surtout en comparaison avec un appel de méthode ordinaire sur un état partagé protégé par mutex. Les coroutines ont tendance à se propager : de plus en plus de fonctions deviennent des coroutines async, et dans une base de code non triviale, les appels de coroutines ou le passage de messages se multiplient. L’overhead doit donc être aussi faible que possible ; sinon, on passe plus de temps à changer de tâche qu’à faire du travail utile.

  • Il est présenté comme basé sur des actors, et il est expliqué qu’envoyer un message à un actor équivaut à exécuter la fonction de l’actor sous un mutex. Autrement dit, même si N threads envoient des messages, un seul thread exécute le code de l’actor, donc c’est sérialisé comme avec un mutex
    Donc, même si techniquement cela peut être « entièrement lock-free », dès lors qu’on utilise des actors, il n’y a pas d’amélioration de la parallélisation

    • Pas forcément. Dans un actor basé sur un mutex, si le thread de l’actor est interrompu, ce mutex — donc le code de l’actor — reste verrouillé jusqu’à ce que le thread d’origine reprenne. Comme le mutex possédé par le thread interrompu est verrouillé, même avec davantage de parallélisme, il est impossible de « redémarrer » ou de « reprendre » ce code d’actor
      Cette implémentation s’appuie fortement sur des fonctions redémarrables, afin qu’une tâche d’actor déjà en cours mais interrompue puisse être reprise et poursuivie par un autre thread parallèle. Voir la page 3 de l’excellent document de conception : https://github.com/eduard-permyakov/peredvizhnikov-engine/bl...
      Donc, au sens strict, ce n’est peut-être pas « plus parallèle » (puisque le nombre d’actors est le même), mais cela semble mieux exploiter davantage de parallélisme pour terminer le même ensemble de tâches
    • Où est-il dit qu’« envoyer un message à un actor équivaut à exécuter la fonction de l’actor sous un mutex » ? Si je comprends bien, le modèle actor implique le passage de messages et l’exécution asynchrone. Au contraire, s’il y a N actors, N threads peuvent s’exécuter en parallèle
    • C’est vrai qu’il n’y a pas d’amélioration de la parallélisation, mais cela ne réduit pas non plus le parallélisme. C’est une autre façon de penser la concurrence, et à mon avis une façon plus simple
      Quand il est plus facile de raisonner, on voit aussi mieux où les contentions apparaissent sur les mêmes ressources, et cela aide réellement à améliorer le parallélisme potentiel. Si l’on repère une occasion précise où le SMP peut accélérer les choses, on peut s’écarter un peu du modèle actor et faire en sorte que plusieurs threads consomment une file de messages ; si ce n’est pas possible, il suffit d’ajouter davantage d’actors pour mieux partitionner les données

  • Quelqu’un a-t-il déjà débogué ou profilé les sections critiques à forte contention de STM par rapport à une implémentation traditionnelle à base de mutex ? Au bout du compte, il faut bien quelque chose pour arbitrer les accès concurrents à la mémoire partagée, et il n’y a pas de repas gratuit. Les mutex sont très bien optimisés, profilés et compris
    En revanche, je ne sais pas si STM en est au même niveau. Une transaction ne peut-elle pas être retentée indéfiniment (?) ?

    • Dans ce cas, l’arbitre est le scheduler. C’est lui qui appelle effectivement les blocs asynchrones et, en cas d’échec, les relance potentiellement. Dans le code de l’article d’origine, il y a des blocs atomiques, une exécution séquentielle des blocs et des blocs avec état pour garantir un seul accès à la fois
      Le cœur est scheduler.cpp, qui utilise std::coroutines
      C’est similaire à async/await dans d’autres langages. Le scheduler dispose d’une file de tâches (coroutines) et d’un pool de threads (N>0) pour les exécuter
      Ici, les tâches contenant les données s’échangent des messages. En contrepartie d’une consommation mémoire plus élevée, aucun verrou n’est nécessaire
    • En pratique, dans les STM sans famine, le nombre de nouvelles tentatives d’une transaction est limité. Un exemple est 2PLSF, et il existe plusieurs autres approches https://zenodo.org/record/7886718

  • Ça fait penser à BEAM, non ?
    https://youtu.be/bo5WL5IQAd0?feature=shared

  • Je n’ai pas vu mentionner à quel point il est difficile de déboguer un tel moteur

  • Je n’ai pas le temps de lire l’implémentation, mais rien qu’avec le README, cela ressemble à un système distribué classique entre threads de jeu. Des motifs comme retry-backoff doivent être fréquents

  • « Lock-free » sonne bien, mais à mon avis, tout code qui utilise des opérations atomiques de façon significative devrait être accompagné d’une preuve formelle, et si possible vérifiée par machine. Il est trop difficile d’utiliser correctement des ordres atomiques qui ne sont pas séquentiellement cohérents. J’ai vu plusieurs fois du code incorrect, et les bugs qui en résultent sont les pires

  • Où est la démo de jeu ? De nos jours, pour considérer quelque chose comme un moteur de jeu, il faut aussi de vrais outils, des exporteurs pour Maya ou 3DSMax, ainsi que des outils de collaboration, des métriques, des notifications, etc.

    • Je ne suis pas d’accord. « Moteur de jeu » ne signifie pas nécessairement « quelque chose qui peut remplacer Unity ou Unreal »

  • Ils disent « lock-free », mais on dirait que ce n’est pas encore le cas
    export std::mutex iolock{};
    export std::mutex errlock{};
    SDL_PollEvent