Discussion :

[Matt Kline]

Le ramasse-miettes (garbage collector) pour les programmeurs de systèmes

Parlons de l'un des programmes les plus sensibles aux performances que vous exécutez tous les jours : votre système d'exploitation. Étant donné que chaque accélération vous donne plus de calculateur pour calculer, un système d'exploitation n'est jamais assez rapide, de sorte que vous trouverez toujours des développeurs de noyaux et de pilotes qui optimisent leur code à outrance.

Les systèmes d'exploitation doivent également être massivement concurrents. Non seulement votre système d'exploitation planifie tous les processus et threads de l'espace utilisateur, mais un noyau a de nombreux threads propres, ainsi que des gestionnaires d'interruption pour interagir avec votre matériel. Vous voulez minimiser le temps d'attente, parce que, encore une fois, vous volez vos utilisateurs à chaque fois que vous le faites.

Mettez ces deux objectifs ensemble et vous trouverez de nombreuses méthodes étranges et magiques pour partager des données sans verrouillage entre les threads. Parlons de l'une d'entre elles. Parlons de la RCU.


RCU

Supposons que nous ayons des données qui sont lues en permanence mais écrites rarement - quelque chose comme l'ensemble des périphériques USB actuellement branchés. En années informatiques, cet ensemble change une fois par millénaire, mais il peut changer. Et lorsqu'il le fait, il doit changer de manière atomique, sans bloquer les lecteurs qui se trouvent être en train de prendre un pic.

Une solution étonnamment simple consiste à demander à l'auteur de lire les données existantes à partir d'un pointeur :

1. Lire les données existantes à partir d'un pointeur.
   
   
2. Les copier et appliquer les modifications nécessaires à l'élaboration de la version suivante.
   
   
3. Mettre à jour le pointeur de manière atomique afin qu'il pointe vers la nouvelle version.

Nous pourrions appeler cette stratégie, euh, Lire, Copier, Mettre à jour. En tant que code, elle ressemble à quelque chose comme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// Some big ball of state...
struct Foo {
    int lots;
    string o;
    big_hash_map fields;
};

// ...is shared between readers and writer by this pointer.
atomic<Foo*> sharedFoo;

// Readers just... read the pointer.
const Foo* readFoo() { return shared_foo.load(); }

// The writer calls this to atomically update our shared state.
// (Wrap this in a mutex to make it multi-producer, multi-consumer,
// but let's assume the common single-producer scenario here.)
void updateFoo() {
    const Foo* old = shared_foo.load(); // Read
    const Foo* updated = makeNewVersion(old); // Copy
    sharedFoo.store(updated); // Update
}

Génial ! C'est facile à utiliser, c'est sans attente et ça fuit comme une passoire.

Eh bien, c'est mauvais. Pourrions-nous simplement supprimer les données ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
void updateFoo() {
    const Foo* old = shared_foo.load(); // Read
    const Foo* updated = makeNewVersion(old); // Copy
    sharedFoo.store(updated); // Update
    delete old; // DANGER WILL ROBINSON
}

Non, en fait. Non, à moins que vous n'aimiez les bugs sans utilisation ultérieure. Tout cela se passe sans verrouillage, alors comment savoir s'il n'y a pas encore des lecteurs qui consultent l'ancienne version ?

Ici, un lecteur (R2 en vert) utilise toujours l'ancienne version après que l'auteur (en violet) a mis à jour le pointeur partagé. Les lecteurs suivants (comme R3) verront la nouvelle version, mais l'auteur ne sait pas quand R2 aura terminé !

Les lecteurs pourraient-ils nous le dire ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
void someReader() {
    // Tell the writer that someone is reading.
    rcu_read_lock();

    const Foo* f = readFoo();
    doThings(f);

    // Tell the writer we're done.
    rcu_read_unlock();
}

Ceci définit une sorte de section critique côté lecture - les lecteurs ne bloquent toujours pas, mais ils peuvent faire attendre l'auteur pour couper les données qu'ils sont encore en train de regarder.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
void updateFoo() {
    const Foo* old = shared_foo.load(); // Read
    const Foo* updated = makeNewVersion(old); // Copy
    sharedFoo.store(updated); // Update

    // Wait for current readers to "unlock"
    // and leave their critical sections.
    rcu_synchronize();

    delete old;
}

Et ainsi de suite,

Remarquez que nous n'attendons pas qu'il n'y ait plus aucun lecteur - une fois de plus, R3 reçoit la nouvelle version des données, et ne se soucie donc pas du sort de ce qui l'a précédé. rcu_synchronize() a juste besoin d'attendre que les lecteurs précédents - ceux qui pourraient être en train de regarder de vieilles données - aient terminé.

Les gens normaux se contenteraient de cette solution, mais les développeurs du noyau ne sont pas des gens normaux. Nous avons maintenant un écrivain bloquant, et même si nous n'avons pas optimisé le côté écrivain, le blocage les rend toujours très tristes.

Supposons que nous n'attendions pas dans notre fonction de mise à jour pour libérer les anciennes données. Notre code est correct tant que cela se produit éventuellement, n'est-ce pas ? Et si nous "différons" cela ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
void updateFoo() {
    const Foo* old = shared_foo.load(); // Read
    const Foo* updated = makeNewVersion(old); // Copy
    sharedFoo.store(updated); // Update

    // Our cool library can free `old` any time after
    // current readers leave their critical sections.
    rcu_defer(old);
}

Tout va bien si nous libérons les anciennes données n'importe où dans le temps. Nous pourrions même avoir un thread dédié qui balayerait occasionnellement toutes les anciennes versions non référencées des données et...

...attendez, est-ce que nous venons de construire un ramasse-miettes (garbage collection) générationnel ? Pour des structures de données immuables, rien de moins ?


Wat

Il ne s'agit pas d'une expérience de pensée : le RCU est bien réel et très utile. Linux l'utilise des dizaines de milliers de fois. Il est fourni dans la bibliothèque C++ Folly de Facebook. Et en Rust, il est connu sous le nom de crossbeam-epoch et est à la base de l'une des bibliothèques de concurrence les plus populaires.

Thérapeute : Le ramasse-miettes du noyau n'est pas réel et ne peut pas vous faire de mal.

À ce stade, certains répliquent avec des non-arguments sur le fait qu'il ne s'agit pas d'un "vrai" ramasse-miettes. Par exemple, parce que vous marquez manuellement les miettes ! Je ne suis pas là pour discuter de taxonomie - quel que soit le nom qu'on lui donne, le RCU a la même forme que le GC (Garbage Collection) : la mémoire est nettoyée un jour ou l'autre, selon qu'elle est toujours utilisée ou non. Et c'est un exemple intéressant qui va à l'encontre de l'idée reçue selon laquelle le ramasse-miettes est :

1. plus lent que la gestion manuelle de la mémoire
   
   
2. Supprime le contrôle fin dont vous avez besoin lorsque vous écrivez des logiciels de systèmes.

Ces arguments sont clairement des conneries pour la RCU, qui est motivée par des exigences de performance et de latence, et non pas utilisée comme une commodité en dépit de ses coûts. Et nous ne faisons pas de travail supplémentaire, nous le déplaçons simplement hors du chemin critique.

...Ces arguments ne sont-ils pas tout simplement des conneries en général ?


Le GC n'est pas magiquement lent, OU : malloc() n'est pas magiquement rapide

L'idée reçue selon laquelle les ramasse-miettes sont intrinsèquement moins efficaces que la gestion traditionnelle/manuelle de la mémoire s'effondre assez rapidement lorsque l'on se penche sur les détails de leur fonctionnement. Prenons un exemple :

• free() n'est pas libre. Un allocateur de mémoire polyvalent doit maintenir un grand nombre d'états internes et globaux. Quelles pages avons-nous obtenues du noyau ? Comment avons-nous divisé ces pages en godets pour des allocations de tailles différentes ? Lesquelles sont utilisées ? Il en résulte des conflits fréquents entre les threads qui tentent de verrouiller l'état de l'allocateur, ou bien vous faites comme jemalloc et conservez des pools locaux aux threads qui doivent être synchronisés avec encore plus de code.
  
  Les outils permettant d'automatiser la partie "libération de la mémoire", comme les durées de vie en Rust et RAII en C++, ne résolvent pas ces problèmes. Ils aident absolument à la correction, ce dont vous devriez vous soucier, mais ils ne font rien pour simplifier toute cette machinerie. De nombreux scénarios vous obligent également à vous rabattre sur shared_ptr/Arc, et ceux-ci exigent à leur tour encore plus de métadonnées (comptes de références) qui rebondissent entre les cœurs et les caches. De plus, ces méthodes font fuir des cycles dans votre graphe de longévité.
  
  
• Le ramasse-miettes moderne offre des optimisations que les alternatives ne peuvent pas offrir. Un GC générationnel mobile recompacte périodiquement le tas. Cela permet d'obtenir un débit incroyable, puisque l'allocation n'est rien de plus qu'un pointeur ! Il confère également aux allocations séquentielles une grande localité, ce qui favorise les performances du cache.

L'illusion du contrôle

De nombreux développeurs opposés au ramasse-miettes construisent des systèmes temps réel "souples". Ils veulent aller aussi vite que possible - plus de FPS dans mon jeu vidéo ! Une meilleure compression dans mon codec de streaming ! Mais ils n'ont pas d'exigences strictes en matière de latence. Rien ne se cassera et personne ne mourra si le système prend occasionnellement une milliseconde de plus.

Mais même si nous ne faisons pas partie de la Garde de nuit, nous ne voulons pas arrêter le monde au hasard pour un quelconque ramasse-miettes, n'est-ce pas ?

Les mensonges sur la gestion de la mémoire

• Le programmeur peut décider quand la gestion de la mémoire a lieu. Ce qui est merveilleux avec un système d'exploitation, c'est qu'il fait abstraction de nos interactions avec le matériel. Ce qui est terrible avec un système d'exploitation, c'est qu'il fait abstraction des interactions avec le matériel. Linux, par défaut, ne fait presque rien lorsqu'on lui demande de la mémoire, et ne la distribue qu'une fois que l'on essaie de l'utiliser. Dans notre monde loufoque de madvise(), d'E/S en mémoire et de caches de systèmes de fichiers, il n'y a pas de réponse simple à la question "qu'est-ce qui est alloué et quand ?". Nous ne pouvons qu'indiquer nos intentions, puis laisser le système d'exploitation faire de son mieux. En général, il fait du bon travail, mais dans les mauvais jours, un simple accès par pointeur peut se transformer en entrées/sorties sur disque !
  
  
• Le programmeur connaît les meilleurs moments pour faire une pause dans la gestion de la mémoire. Parfois, les réponses sont évidentes, par exemple sur l'écran de chargement d'un jeu vidéo. Mais pour beaucoup d'autres logiciels, la seule réponse évidente est tout simplement "chaque fois que nous ne sommes pas occupés par un travail plus critique". Nos amis shared_ptr et Arc obscurcissent notre raisonnement ici aussi - les morceaux de code individuels qui détiennent un pointeur comptabilisé par référence ne peuvent pas savoir à priori s'ils vont être le dernier propriétaire coincé avec le nettoyage. (S'ils pouvaient le savoir, nous n'aurions pas besoin de compter les références ici !)
  
  
• L'appel à free() rend la mémoire au système d'exploitation. La mémoire est allouée par le système d'exploitation sous forme de pages, et l'allocateur conserve souvent ces pages jusqu'à la fin du programme. Il essaie de les réutiliser pour éviter d'embêter le système d'exploitation plus que nécessaire. Cela ne veut pas dire que le système d'exploitation ne peut pas récupérer les pages en les échangeant...

À retenir

Je ne veux pas dire que tous les logiciels bénéficieraient du ramasse-miettes. Certains ne le feront certainement pas. Mais nous sommes presque en 2024, et toute mention du GC - en particulier dans mon milieu de programmeurs de systèmes - est encore noyée dans de fausses dichotomies et dans le FUD. Le GC est réservé aux nuls, trop paresseux ou incompétents pour écrire une version "manifestement" plus rapide dans un langage à gestion manuelle de la mémoire.

Ce n'est tout simplement pas vrai. C'est de l'idéologie. J'y ai cru pendant plus de dix ans, jusqu'à ce que je rejoigne une équipe qui construit des systèmes - des systèmes sur lesquels des gens parient leur vie - qui offrent une latence inférieure à la microseconde, en utilisant un langage à base de ramasse-miettes qui alloue sur presque chaque ligne. Il s'avère que les GC modernes offrent un débit incroyable et qu'il n'est pas nécessaire de les remplacer par une gestion manuelle de la mémoire simplement parce qu'une partie de votre système doit absolument fonctionner en n cycles d'horloge. (Ces parties spécifiques peuvent être reléguées à du code non GC, ou même à du matériel !)

Le ramasse-miettes n'est pas une solution miracle. Nous n'en avons pas. Mais c'est un autre outil dans la boîte à outils que nous ne devrions pas avoir peur d'utiliser.

Source : "Garbage Collection for Systems Programmers" (Matt Kline)

Et vous ?

Quel est votre avis sur le sujet ?

Voir aussi :

Pourquoi Chrome a activé par défaut le Garbage Collection de WebAssembly ? Avec WasmGC, le ramasse-miettes du langage de programmation n'a plus besoin de faire partie du portage vers Wasm

Un coprocesseur pour accélérer les ramasse-miettes. On pourrait gagner un facteur 4 en temps d'exécution sur les opérations de gestion de la mémoire

[boboss123]

Merci, article très intéressant.
Peut-on faire un vrai Garbage Collector en langage C ?
... je ne vois pas trop comment faire pour détecter qu'un objet n'est plus alloué.