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

28

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?

Templier noir
la source
21
"balayer le tas" est plus sûr que "casser la pile" ... :-)
Brian Knoblauch

Réponses:

62

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ë .)

Jeff Grigg
la source
7
+1 la pile est toujours entièrement accessible, donc pas de sens de la balayer
ratchet freak
2
+1 merci, a pris 4 messages pour frapper la bonne réponse. Je ne sais pas pourquoi vous avez dû dire que tout sur la pile est "considéré" comme étant utilisé, il est au moins aussi fort que les objets de tas encore utilisés sont en cours d'utilisation - mais c'est une très bonne réponse.
psr
@psr il signifie que tout sur la pile est fortement accessible et n'a pas besoin d'être collecté jusqu'à ce que la méthode revienne, mais que (RAII) est déjà explicitement géré
ratchet freak
@ratchetfreak - Je sais. Et je voulais juste dire que le mot "considéré" n'est probablement pas nécessaire, c'est OK de faire une déclaration plus forte sans lui.
psr
5
@psr: Je ne suis pas d'accord. " considéré comme étant en cours d'utilisation" est plus correct à la fois pour la pile et le tas, pour des raisons très importantes. Ce que vous voulez, c'est jeter ce qui ne sera plus utilisé; ce que vous faites, c'est que vous jetez ce qui n'est pas accessible . Vous pourriez bien avoir des données accessibles dont vous n'aurez jamais besoin; lorsque ces données augmentent, vous avez une fuite de mémoire (oui, elles sont possibles même dans les langages GC, contrairement à ce que beaucoup de gens pensent). Et on pourrait soutenir que des fuites de pile se produisent également, l'exemple le plus courant étant les trames de pile inutiles dans les programmes récursifs de queue exécutés sans élimination des appels de queue (par exemple sur la JVM).
Blaisorblade
19

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.

Eric Lippert
la source
13

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.

tchad
la source
5
Mais le tas n'est pas l'emplacement des «données d'instance». Ils peuvent aussi être sur la pile.
svick
@svick Cela dépend de la langue, bien sûr. Java ne prend en charge que les objets alloués en tas, et Vala fait une distinction très explicite entre l'allocation en tas (classe) et l'allocation en pile (struct).
moelleux
1
@fluffy: ce sont des langues très limitées, vous ne pouvez pas supposer que cela vaut en général car aucune langue n'a été précisée.
Matthieu M.
@MatthieuM. C'était en quelque sorte mon point.
moelleux
@fluffy: alors pourquoi les classes sont-elles allouées dans le tas, alors que les structures sont allouées dans la pile?
Dark Templar
10

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.

Jason Baker
la source
1
Non seulement il sera désaffecté «éventuellement», mais il sera désalloué au bon moment.
Boris Yankov
3
  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.


la source
"En Python, il n'y a tout simplement pas de section de données". Ce n'est pas à vrai dire vrai. Aucun, Vrai et Faux sont alloués dans la section des données si je comprends bien: stackoverflow.com/questions/7681786/how-is-hashnone-calculated
Jason Baker
@JasonBaker: trouvaille intéressante! Cela n'a cependant aucun effet. C'est un détail d'implémentation et limité aux objets intégrés. Cela ne veut pas dire que ces objets ne devraient pas être désalloués de toute façon pendant la durée de vie du programme, ne le sont pas, et sont également de petite taille (moins de 32 octets chacun, je suppose).
@delnan Comme Eric Lippert aime le souligner, pour la plupart des langues, l'existence de régions de mémoire distinctes pour la pile et le tas est un détail d'implémentation. Vous pouvez implémenter la plupart des langues sans utiliser de pile du tout (bien que les performances puissent en souffrir) et être toujours conforme à leurs spécifications
Jules
2

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 .

Ryan Culpepper
la source
Serait intéressant de savoir. La première pensée est que la suppression des espaces est la plus réaliste. Traverser un arbre de zones exclues peut prendre plus de temps que de simplement parcourir des valeurs nulles. De toute évidence, toute tentative de compactage de la pile est lourde de dangers! Faire fonctionner cela ressemble à un processus époustouflant / sujet aux erreurs.
Brian Knoblauch
@Brian, En fait, en y réfléchissant un peu plus, pour une machine virtuelle typée, vous avez besoin de quelque chose comme ça de toute façon, afin que vous puissiez déterminer quels emplacements sont des références par opposition aux entiers, flottants, etc. En outre, en ce qui concerne le compactage de la pile, voir Non CONS Ses arguments "par Henry Baker.
Ryan Culpepper
La détermination des types d'emplacement et la vérification de leur utilisation appropriée peuvent et sont généralement effectuées de manière statique, soit au moment de la compilation (pour les machines virtuelles utilisant un bytecode approuvé) ou au moment du chargement (lorsque le bytecode provient d'une source non fiable, par exemple Java).
Jules
1

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 .

rurban
la source
La question semble concerner davantage les parties de la mémoire qui sont récupérées, plutôt que les algorithmes spécifiques de collecte. La dernière phrase implique en particulier que l'OP utilise "sweep" comme synonyme générique de "garbage collect", plutôt qu'un mécanisme spécifique pour implémenter le garbage collection. Compte tenu de cela, votre réponse apparaît comme disant que seuls les garbage collector les plus simples garbage collectent le tas, et les garbage collector rapides au lieu de cela garbage collectent la pile et la mémoire statique, laissant le tas grandir et grandir jusqu'à ce qu'il manque de mémoire.
8bittree
Non, la question était très précise et intelligente. Les réponses ne le sont pas. Les GC de marquage et de balayage lents ont deux phases, l'étape de marquage balayant les racines sur la pile et la phase de balayage balayant le tas. Les CPG à copie rapide n'ont qu'une seule phase, balayant la pile. Aussi simple que ça. Puisqu'apparemment personne ne connaît ici les bons ramasseurs de déchets, il faut répondre à la question. Votre interprétation est extrêmement fausse.
rurban
0

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 .

nalply
la source