Comment implémenter la récupération de place en C ++

Question

J'ai lu des articles sur l'implémentation de GC en C et certaines personnes ont dit qu'il était impossible de le faire car C était faiblement typé. Je veux savoir comment implémenter GC en C ++.

Je veux une idée générale sur la façon de le faire. Merci beaucoup!

Ceci est une question de Bloomberg interview que mon ami m'a dit. Il a mal fait à ce moment-là. Nous voulons connaître vos idées à ce sujet.

Answer 1

La collecte des ordures dans le C et le C++ sont deux sujets difficiles pour plusieurs raisons:

1. Les pointeurs peuvent être transtypé en nombres entiers et vice-versa. Cela signifie que je pourrais avoir un bloc de mémoire qui est accessible uniquement en prenant un entier, typecasting à un pointeur, puis déréférencement il. Un garbage collector doit être prudent de ne pas penser à un bloc est inaccessible lorsque, en effet, il peut encore être atteint.

2. Les pointeurs ne sont pas opaques. De nombreux ramasseurs d'ordures, comme le stop-and-copie collectionneurs, comme pour déplacer les blocs de mémoire autour ou compact pour économiser de l'espace. Puisque vous pouvez explicitement regarder les valeurs de pointeur en C et C++, ce qui peut être difficile à mettre en œuvre correctement. Vous devez être sûr que si quelqu'un était en train de faire quelque chose de délicat avec typecasting de nombres entiers que vous avez correctement mis à jour le entier si vous avez déplacé un bloc de mémoire autour de.

3. Gestion de la mémoire peut être fait de manière explicite. Tout garbage collector aurez besoin de prendre en compte le fait que l'utilisateur est en mesure explicitement blocs libres de la mémoire à tout moment.

4. En C++, il y a une séparation entre l'allocation/libération de la mémoire et de l'objet de la construction/destruction. Un bloc de mémoire peut être fourni avec suffisamment d'espace pour contenir un objet sans objet réellement construits. Une bonne garbage collector aurait besoin de savoir, quand il libère de la mémoire, de savoir si ou de ne pas appeler le destructeur de tous les objets qui pourraient être alloués là. Cela est particulièrement vrai pour les conteneurs de la bibliothèque standard, qui font souvent appel à de la std::allocator utiliser cette astuce pour des raisons d'efficacité.

5. La mémoire peut être attribuée à partir de différents domaines. Le C et le C++ peut obtenir la mémoire, soit à partir de l'intégré dans le freestore (malloc/free ou de new/delete), ou à partir de l'OS via mmap ou d'autres appels système, et, dans le cas de C++, à partir d' get_temporary_buffer ou return_temporary_buffer. Les programmes peuvent également obtenir la mémoire à partir d'une bibliothèque tierce. Une bonne garbage collector doit être en mesure de suivre les références à la mémoire de ces autres piscines et (éventuellement) devrait être responsable pour le nettoyage en place.

6. Les pointeurs peuvent pointer dans le milieu des objets ou des tableaux. Dans de nombreux garbage collector de Java, les références de l'objet toujours le point de départ de l'objet. En C et C++ les pointeurs peuvent point dans le milieu de tableaux, et en C++ dans le milieu des objets (si l'héritage multiple est utilisé). Cela peut grandement compliquer la logique de détection de ce qui est toujours accessible.

Donc, en résumé, il est extrêmement difficile de construire un garbage collector pour le C ou le C++. La plupart des bibliothèques qui ne collecte des ordures en C et C++ sont très conservateurs dans leur approche et sont techniquement boiteuse - ils supposent que vous n'aurez pas, par exemple, prendre un pointeur, jette à un nombre entier, de l'écrire sur le disque, puis le charger de retour dans quelque temps plus tard. Ils supposent aussi que n'importe quelle valeur dans la mémoire de la taille d'un pointeur pourrait être un pointeur, et donc parfois refuser de libre inaccessible de la mémoire car il n'y a nulle chance qu'il y a un pointeur vers elle.

Comme d'autres l'ont souligné, le GC de Boehm ne ne collecte des ordures pour le C et le C++, mais sous réserve des restrictions susmentionnées.

Il est intéressant de noter, C++11 inclut quelques nouvelles de la bibliothèque de fonctions qui permettent au programmeur pour marquer les régions de la mémoire comme accessible et inaccessible en prévision de l'avenir, la collecte des ordures efforts. Il peut être possible dans l'avenir pour construire une très bonne C++11 garbage collector avec ce genre d'information. Dans l'intervalle, cependant, vous devez être extrêmement prudent de ne pas briser les règles susmentionnées.

Answer 2

C n'est pas le C++, mais les deux ont le même "faiblement typé" questions de. Ce n'est pas l'implicite typecasts qui cause un problème, cependant, mais la tendance à "beaucoup les jeux de mots" (à subvertir le système de type), en particulier dans la structure de données des bibliothèques.

Il y sont des ramasseurs d'ordures là-bas pour C et/ou C++. L'Boehm conservateur collecteur est probablement le mieux connu. Il est conservateur car, si elle voit un motif de bits qui ressemble à un pointeur vers un objet, il ne recueille que de l'objet. Cette valeur peut être un autre type de valeur complètement, de sorte que l'objet pourrait être collectées, mais "conservateur", c'est jouer en sécurité.

Même un conservateur collecteur peut être dupe, même si, si vous utilisez calculé pointeurs. Il y a une structure de données, par exemple, où chaque noeud de liste a un champ indiquant la différence entre les nœuds et précédent-nœud adresses. L'idée est de donner à double liste chaînée comportement avec un seul lien par nœud, au détriment de la plus complexe des itérateurs. Depuis il n'y a pas explicite pointeur n'importe où à la plupart des nœuds, ils peuvent être perçus indûment.

Bien sûr, cela est très exceptionnels cas particulier.

Plus important, vous pouvez soit fiable destructeurs ou la collecte des ordures, pas les deux. Lorsqu'un garbage cycle est recueillie, le collectionneur ne décide pas de qui destructeur d'appeler d'abord.

Depuis le RAII modèle est omniprésente en C++, et qui s'appuie sur des destructeurs, il y est IMO un conflit. Il peut y avoir des exceptions valides, mais mon avis est que si vous voulez la collecte des ordures, vous devez utiliser une langue qui est conçu à partir du sol en place pour la collecte des ordures (Java, C#, ...).

Answer 3

Regardez dans le récupérateur de déchets Boehm .

Answer 4

Vous pouvez soit utiliser des pointeurs intelligents ou créer votre propre conteneur de l'objet qui permettra de suivre les références et gérer l'allocation de la mémoire etc. Pointeurs intelligents seraient probablement préférable. La plupart du temps vous pouvez éviter dynamique d'allocation de tas tout à fait.

Par exemple:

char* pCharArray = new char[128];
// do some stuff with characters
delete [] pCharArray;

Le danger avec le ci-dessus étant si quoi que ce soit jette entre les nouveaux et les supprimer de votre supprimer ne sera pas exécuté. Quelque chose comme ci-dessus pourrait facilement être remplacé par des plus sûrs "garbage collector" code:

std::vector<char> charArray;
// do some stuff with characters

Bloomberg a notoirement hors de propos de questions d'entrevue à partir d'une pratique de codage point de vue. Comme la plupart des enquêteurs, ils sont principalement préoccupés par la façon dont vous pensez et vos aptitudes à la communication que de la solution réelle cependant.

Answer 5

L'affirmation que vous avez vue est fausse; le collecteur Boehm prend en charge C et C ++. Je suggère de lire la documentation du collectionneur Boehm (en particulier cette page ) pour avoir un bon aperçu de la manière dont on pourrait écrire un garbage collector en C ou C ++.