Le ramasse-miettes pour les programmeurs système (2023)

Introduction à RCU

• Un système d’exploitation fait partie, au quotidien, des programmes les plus sensibles aux performances.
• Un système d’exploitation peut toujours être plus rapide, et les développeurs de noyaux et de pilotes s’emploient à optimiser le code.
• Un système d’exploitation exige une concurrence massive, planifie les processus et threads en espace utilisateur, et dispose de ses propres threads ainsi que de gestionnaires d’interruptions qui interagissent avec le matériel.

Principe de fonctionnement de RCU

• Lorsqu’il faut modifier de façon atomique des données souvent lues mais rarement écrites (par exemple les périphériques USB actuellement connectés), on utilise la stratégie RCU (Read, Copy, Update).
• On lit les données, on les copie pour les modifier, puis on met à jour de façon atomique le pointeur vers la nouvelle version.
• Cette méthode est facile à utiliser et sans attente, mais elle peut entraîner des fuites mémoire.

Résoudre le problème des fuites mémoire

• Pour éviter les fuites mémoire, au lieu de supprimer les anciennes données dans la fonction de mise à jour, on peut différer leur suppression jusqu’à ce qu’il n’y ait plus de lecteur en train de les lire.
• Pendant que les lecteurs lisent les données, l’auteur de l’écriture attend la suppression des données afin de gérer la mémoire en toute sécurité.

Utilisation concrète de RCU

• RCU est utilisé des dizaines de milliers de fois dans Linux, ainsi que dans la bibliothèque C++ Folly de Facebook et dans crossbeam-epoch en Rust.
• RCU est motivé par des exigences de performance et de latence, et fournit une méthode de gestion mémoire semblable au ramasse-miettes.

Idées reçues sur le ramasse-miettes

• L’idée reçue selon laquelle le ramasse-miettes serait plus lent que la gestion manuelle de la mémoire s’effondre vite dès qu’on examine les détails.
• La fonction free() n’est pas gratuite, et l’allocateur mémoire doit conserver en interne beaucoup d’état.
• Les ramasse-miettes modernes offrent des optimisations par déplacement et par générations, avec un débit élevé et de bonnes performances de cache.

L’illusion du contrôle

• Les développeurs veulent parfois construire des systèmes temps réel, mais en pratique ils n’ont pas un contrôle total sur la gestion de la mémoire.
• Le système d’exploitation ne fait que deviner les intentions du développeur en matière d’allocation mémoire, et il arrive qu’un simple accès à un pointeur se transforme en E/S disque.

Conclusion

• Tous les logiciels ne tirent pas profit du ramasse-miettes, mais c’est un outil utile qui ne devrait plus inspirer de crainte, même chez les programmeurs système.

L’avis de GN⁺

• RCU est une technique efficace pour accroître la concurrence tout en maintenant la cohérence des données dans un environnement multithread. C’est un élément très important dans le calcul haute performance et les systèmes temps réel.
• L’exemple de RCU, qui bouscule les idées reçues sur le ramasse-miettes, offre aux développeurs une nouvelle perspective sur la gestion de la mémoire. C’est d’autant plus vrai dans le domaine de la programmation système, où la gestion mémoire est essentielle.
• Parmi les autres projets offrant des fonctionnalités proches de RCU, on peut citer ConcurrentLinkedQueue de Java ou ConcurrentBag de .NET, qui fournissent eux aussi des structures de données lock-free.
• Lorsqu’on adopte la technologie RCU, il faut prendre en compte les exigences du système et les objectifs de performance, et comprendre les bénéfices comme les coûts potentiels de son utilisation.
• Cet article peut aider les développeurs à mieux comprendre la gestion de la mémoire et la concurrence, à remettre en question leurs hypothèses existantes et à explorer de nouvelles solutions.

[GN⁺]

Avis Hacker News

• Suggestion de jeter un œil aux techniques innovantes de garbage collection (GC) parallèle de MPL et MaPLe

  • Récompensées par le Distinguished Paper Award à POPL 2024 et l’ACM SIGPLAN 2023 Paper Award
  • Principales propositions :
    • le « disentanglement » fondé sur une garbage collection parallèle à l’efficacité démontrable
    • un contrôle automatique de la granularité à l’efficacité démontrable

• L’utilisation de RCU comme mécanisme de synchronisation pour la garbage collection est intéressante

  • Il est pertinent de transférer la responsabilité de libération mémoire du writer vers le dernier reader
  • Il pourrait être utile, pour améliorer les performances, d’envisager de déplacer la libération mémoire vers un processus batch dédié plutôt que vers les readers

• Idées reçues générales sur la gestion mémoire

  • Croire que les programmeurs connaissent le temps de pause optimal pour la gestion mémoire
  • Dans les jeux et les programmes de trading crypto, les programmeurs peuvent effectivement connaître le temps de pause optimal

• Le cas d’usage de RCU est convaincant, mais l’expérience de la garbage collection dans d’autres contextes est médiocre

  • Cela se lit comme l’affirmation qu’une solution de gestion mémoire sur mesure peut offrir les meilleures performances
  • Discussion autour de l’idée fausse selon laquelle l’appel à free() rend la mémoire au système d’exploitation

• Avec la garbage collection, les nouvelles allocations se font en RAM plutôt que dans le cache

  • Cela peut avoir un impact important sur les performances
  • Exemple de benchmark fourni avec le langage Julia

• Une bonne garbage collection par traçage dépasse depuis longtemps la gestion mémoire manuelle en termes de débit

  • Plus récemment, la latence est acceptable pour la plupart des applications
  • L’utilisation mémoire reste le principal facteur à considérer

• L’un des éléments qui se marient bien avec la garbage collection est async/await

  • En Rust, l’usage de async/await combiné à la gestion mémoire pose problème

• Il est quelque peu surprenant de passer d’une motivation autour de RCU à une discussion sur la garbage collection générale

• En développement logiciel, deux cas sont pris en compte

  • Pour les hot paths, on utilise un allocateur sur mesure, et ailleurs la garbage collection est pratique

• Le passage de RCU à une garbage collection par traçage générale ressemble à une stratégie habile

  • La gestion mémoire manuelle ne se résume pas à de simples appels à malloc/free

• Il est difficile pour les programmeurs système d’identifier quand un objet peut être garbage collecté

• Les outils de gestion du cycle de vie en Rust et en C++ aident à automatiser la libération mémoire, mais ne simplifient pas la complexité