Pourquoi la collecte des ordures ne fait-elle que balayer le tas?

Fondamentalement, j'ai appris jusqu'à présent que la récupération de place efface à jamais toute structure de données qui n'est pas actuellement pointée. Mais cela ne vérifie que le tas pour de telles conditions.

Pourquoi ne vérifie-t-il pas également la section des données (globales, constantes, etc.) ou la pile? Qu'en est-il du tas que c'est la seule chose que nous voulons ramasser?

Le garbage collector ne balayer la pile - pour voir ce que les choses dans le tas sont actuellement utilisés (pointu) par les choses sur la pile.

Cela n'a aucun sens pour le garbage collector d'envisager de collecter la mémoire de la pile car la pile n'est pas gérée de cette façon: tout ce qui se trouve sur la pile est considéré comme "en cours d'utilisation". Et la mémoire utilisée par la pile est automatiquement récupérée lorsque vous revenez des appels de méthode. La gestion de la mémoire de l'espace de pile est si simple, bon marché et facile que vous ne voudriez pas que la collecte des ordures soit impliquée.

(Il existe des systèmes, tels que smalltalk, où les cadres de pile sont des objets de première classe stockés dans le tas et des déchets collectés comme tous les autres objets. Mais ce n'est pas l'approche populaire de nos jours. La JVM de Java et le CLR de Microsoft utilisent la pile matérielle et la mémoire contiguë .)

Tournez votre question. La vraie question motivante est dans quelles circonstances pouvons-nous éviter les coûts de collecte des ordures?

Eh bien, tout d'abord, quels sont les coûts de la collecte des ordures? Il y a deux coûts principaux. D'abord, vous devez déterminer ce qui est vivant ; cela nécessite potentiellement beaucoup de travail. Deuxièmement, vous devez compacter les trous qui se forment lorsque vous libérez quelque chose qui a été alloué entre deux choses encore en vie. Ces trous sont inutiles. Mais les compacter coûte cher aussi.

Comment éviter ces coûts?

De toute évidence, si vous pouvez trouver un modèle d'utilisation du stockage dans lequel vous n'allouez jamais quelque chose de longue durée, puis allouez quelque chose de courte durée, puis allouez quelque chose de longue durée, vous pouvez éliminer le coût des trous. Si vous pouvez garantir que pour un sous-ensemble de votre stockage, chaque allocation suivante est de plus courte durée que la précédente dans ce stockage, il n'y aura jamais de trous dans ce stockage.

Mais si nous avons résolu le problème des trous, nous avons également résolu le problème de la collecte des ordures . Avez-vous quelque chose dans ce stockage qui est toujours vivant? Oui. Tout a-t-il été alloué avant de durer plus longtemps? Oui - cette hypothèse est de savoir comment nous avons éliminé la possibilité de trous. Par conséquent, tout ce que vous devez faire est de dire "la dernière allocation est-elle en vie?" et vous savez que tout est vivant dans ce stockage.

Avons-nous un ensemble d'allocations de stockage où nous savons que chaque allocation suivante a une durée de vie plus courte que l'allocation précédente? Oui! Les cadres d'activation des méthodes sont toujours détruits dans l'ordre inverse de leur création car ils ont toujours une durée de vie plus courte que l'activation qui les a créés.

Par conséquent, nous pouvons stocker des trames d'activation sur la pile et savoir qu'elles n'ont jamais besoin d'être collectées. S'il y a une image sur la pile, l'ensemble des images en dessous est de plus longue durée, donc elles n'ont pas besoin d'être collectées. Et ils seront détruits dans l'ordre inverse de leur création. Le coût de la collecte des ordures est ainsi éliminé pour les trames d'activation.

C'est pourquoi nous avons le pool temporaire sur la pile en premier lieu: car c'est un moyen facile d'implémenter l'activation de la méthode sans encourir de pénalité de gestion de la mémoire.

(Bien sûr, le coût de la récupération de la mémoire à laquelle font référence les références sur les trames d'activation est toujours là.)

Considérons maintenant un système de flux de contrôle dans lequel les trames d'activation ne sont pas détruites dans un ordre prévisible. Que se passe-t-il si une activation de courte durée peut donner lieu à une activation de longue durée? Comme vous pouvez l'imaginer, dans ce monde, vous ne pouvez plus utiliser la pile pour optimiser la nécessité de collecter des activations. L'ensemble d'activations peut à nouveau contenir des trous.

C # 2.0 a cette fonctionnalité sous la forme de yield return. Une méthode qui fait un rendement va être réactivée ultérieurement - la prochaine fois que MoveNext sera appelée - et quand cela se produit n'est pas prévisible. Par conséquent, les informations qui se trouveraient normalement sur la pile pour la trame d'activation du bloc d'itérateur sont stockées à la place sur le tas, où elles sont récupérées lors de la collecte de l'énumérateur.

De même, la fonctionnalité "async / attente" à venir dans les prochaines versions de C # et VB vous permettra de créer des méthodes dont les activations "céderont" et "reprendront" à des points bien définis lors de l'action de la méthode. Étant donné que les trames d'activation ne sont plus créées et détruites de manière prévisible, toutes les informations qui étaient auparavant stockées dans la pile devront être stockées dans le tas.

Ce n'est qu'un accident de l'histoire que nous avons décidé pendant quelques décennies que les langues avec des cadres d'activation créés et détruits de manière strictement ordonnée étaient à la mode. Étant donné que les langues modernes manquent de plus en plus de cette propriété, attendez-vous à voir de plus en plus de langues réifier les continuations sur le tas récupéré, plutôt que sur la pile.

La réponse la plus évidente, et peut-être pas la plus complète, est que le tas est l'emplacement des données d'instance. Par données d'instance, nous entendons les données représentant les instances de classes, alias objets, qui sont créées au moment de l'exécution. Ces données sont intrinsèquement dynamiques et le nombre de ces objets, et donc la quantité de mémoire qu'ils occupent, n'est connu qu'au moment de l'exécution. Il DOIT y avoir un peu de récupération de cette mémoire ou des programmes de longue durée consommeraient toute sa mémoire au fil du temps.

La mémoire consommée par les définitions de classe, les constantes et autres structures de données statiques est intrinsèquement peu susceptible d'augmenter sans contrôle. Puisqu'il n'y a qu'une seule définition de classe en mémoire pour un nombre inconnu d'instances d'exécution de cette classe, il est logique que ce type de structure ne constitue pas une menace pour l'utilisation de la mémoire.

Il convient de garder à l'esprit la raison pour laquelle nous avons la collecte des ordures: car il est parfois difficile de savoir quand désallouer la mémoire. Vous n'avez vraiment ce problème qu'avec le tas. Les données allouées sur la pile seront finalement désallouées, il n'y a donc pas vraiment besoin de faire de récupération de place. Les éléments de la section des données sont généralement supposés être alloués pour la durée de vie du programme.

1. La taille de ceux-ci est prévisible (constante sauf pour la pile, et la pile est généralement limitée à quelques Mo) et généralement très petite (au moins par rapport aux centaines de Mo de grandes applications peuvent allouer).

2. Les objets alloués dynamiquement ont généralement un petit laps de temps dans lequel ils sont accessibles. Après cela, il ne sera plus possible de les référencer. Comparez cela avec les entrées de la section des données, les variables globales et autres: fréquemment, il y a un morceau de code qui les référence directement (pensez const char *foo() { return "foo"; }). Normalement, le code ne change pas, donc la référence est là pour rester et une autre référence sera créée chaque fois que la fonction est invoquée (ce qui peut être à tout moment pour autant que l'ordinateur le sache - sauf si vous résolvez le problème d'arrêt, c'est-à-dire ). Ainsi, vous ne pouviez pas libérer la plupart de cette mémoire de toute façon, car elle serait toujours accessible.

3. Dans de nombreux langages récupérés, tout ce qui appartient au programme en cours d'exécution est alloué en tas. En Python, il n'y a tout simplement pas de section de données et pas de valeurs allouées à la pile (il y a les références que sont les variables locales, et il y a la pile des appels, mais aucune n'est la même dans le même sens que intdans C). Chaque objet est sur le tas.

Comme plusieurs autres répondants l'ont dit, la pile fait partie de l'ensemble racine, elle est donc analysée pour les références mais pas "collectée" en soi.

Je veux juste répondre à certains des commentaires qui impliquent que les ordures sur la pile n'ont pas d'importance; il le fait, car il peut être considéré comme accessible plus de déchets sur le tas. Les écrivains consciencieux de VM et de compilateur annulent ou excluent autrement les parties mortes de la pile de l'analyse. IIRC, certaines machines virtuelles ont des tables mappant les plages de PC aux bitmaps de vie de pile-emplacement et d'autres annulent simplement les emplacements. Je ne sais pas quelle technique est actuellement préférée.

Un terme utilisé pour décrire cette considération particulière est le coffre-fort pour l'espace .

Permettez-moi de souligner quelques idées fausses fondamentales que vous et beaucoup d'autres vous êtes trompées:

"Pourquoi la collecte des ordures ne fait-elle que balayer le tas?" C'est l'inverse. Seuls les ramasseurs de déchets les plus simples, les plus conservateurs et les plus lents balaient le tas. Voilà pourquoi ils sont si lents.

Les ramasse-miettes rapides balayent uniquement la pile (et éventuellement d'autres racines, comme certains globaux pour les pointeurs FFI et les registres pour les pointeurs actifs), et copient uniquement les pointeurs accessibles par les objets de la pile. Le reste est jeté (c.-à-d. Ignoré), ne balayant pas du tout le tas.

Étant donné que le tas est environ 1000 fois plus grand que la ou les piles, un tel GC de numérisation de pile est généralement beaucoup plus rapide. ~ 15 ms contre 250 ms sur des tas de taille normale. Comme il copie (déplace) les objets d'un espace à un autre, il est principalement appelé un collecteur de copie semi-spatial, il a besoin de 2x mémoire et donc surtout pas utilisable sur de très petits appareils comme les téléphones avec peu de mémoire. Il est compact, donc il est très convivial pour le cache, contrairement aux simples scanners de tas de marquage et de balayage.

Puisqu'il s'agit de pointeurs mobiles, FFI, l'identité et les références sont délicates. L'identité est généralement résolue avec des identifiants aléatoires, des références via des pointeurs de transfert. FFI est délicat, car les objets étrangers ne peuvent pas retenir les pointeurs vers l'ancien espace. Les pointeurs FFI sont généralement conservés dans une arène de tas séparée, par exemple avec une marque et un balayage lents, un collecteur statique. Ou malloc trivial avec refcounting. Notez que malloc a un énorme surcoût, et recompte encore plus.

Mark & ​​sweep est trivial à implémenter mais il ne doit pas être utilisé dans de vrais programmes, et surtout ne pas être enseigné comme le collecteur standard. Le plus célèbre de ces collecteurs de copie à balayage de pile rapide est appelé le collecteur à deux doigts Cheney .

Qu'est-ce qui est alloué sur la pile? Variables locales et adresses de retour (en C). Lorsqu'une fonction revient, ses variables locales sont ignorées. Il n'est pas nécessaire, voire préjudiciable, de balayer la pile.

De nombreux langages dynamiques, ainsi que Java ou C #, sont implémentés dans un langage de programmation système, souvent en C. Vous pourriez dire que Java est implémenté avec des fonctions C et utilise des variables locales C et donc que le garbage collector de Java n'a pas besoin de balayer la pile.

Il existe une exception intéressante: le garbage collector de Chicken Scheme balaie la pile (d'une certaine manière), car son implémentation utilise la pile comme un espace de première génération de collecte de déchets: voir Chicken Scheme Design Wikipedia .