Garbage Collector Stop & Copy

Bonjour, je me présente Romain Calascibetta. Je suis actuellement dans un projet qui n'est pas critique mais sur lequel je voudrais avoir une gestion de la mémoire sans faille. En effet, j'ai déjà fait certaines optimisations qui font que j'ai divisé par 2 la mémoire que j'ai alloué. Cependant, j'ai encore des éléments névralgiques à mon programme qui sont alloués dynamiquement.

Je me dis alors, et si le malloc foire ? La politique utilisé jusqu'à présent était de dire: si le malloc foire, on signale l'erreur et on fait comme-ci l'utilisateur n'aurait pas ajouter cette élément. Bien entendu, on peut pas ignorer tout ce que rentre l'utilisateur.

J'opte donc pour la mise en place d'un GC Stop & Copy où l'espace se situera sur la Stack (entant que global) et rulz ... Mais j'ai certaines questions par rapport à ce GC mais plus généralement, je vais vous poser sur la table mes problèmes de mémoire.

Grosso-modo, J'ai 2 types de données que j'alloue (3 en réalité mais la troisième n'est pas si grave). C'est un arbre n-aires ainsi qu'une liste doublement chaînée circulaire - le troisième élément est une chaîne de caractère. Ces deux éléments sont indispensable et requiert par leurs structures obligatoirement une allocation dynamique. L'idée est donc de, au-lieu d'utiliser directement la mémoire vive, faire une abstraction de la mémoire à l'aide d'un GC pour que le programme soit un peu près indépendant de tout système.

J'ai bien compris le système du Stop & Copy. Une zone coupé en 2 où l'on mets nos données dans l'une jusqu'à qu'elle soit pleine et ensuite, on « flip » vers l'autre en ne copiant que ce qui est « en vie ». Cependant, comment savoir si une donnée est en vie ou pas ? Dans les différents PDFs que j'ai, on me parle de racine qui serait un arbre contenant les pointeurs vers les données. Ma question est véritablement là. Cette racine, elle est où dans la mémoire (dans le GC, dans le heap ?), comment est-elle (la structure de l'arbre) ? Bref, des questions déterminantes pour le projet. Le problème c'est que je vois comment fonctionne de façon général le GC mais j'arrive pas à l'implémenter en C.

Sinon, la solution du GC est celle que j'ai trouvé mais si vous avez une autre solution plus prometteuse, je suis preneur ! Il s'agit surtout d'être près pour toutes les situations. De plus, j'ai essayé de limité la mémoire de mon programme avec rlimit mais cela ne marche pas - enfin ça fonctionne quand je lancer valgrind ./mon_programme ... Et puis la solution ulimit (en ligne de commande) n'est pas super viable. Faut-il mettre en place la limite de mémoire virtuelle et forker le programme ?

Merci d'avance.

Sans me prétendre spécialiste de la gestion optimisée de la mémoire, j'ai l'impression que tu ne te poses pas les questions les plus judicieuses et que n'y apportent pas les bonnes réponses ;)

Vouloir une gestion sans faille de la mémoire est l'objectif de tout programmeur motivé et consciencieux travaillant sur un projet important. C'est donc une démarche irréprochable !

Il y a 2 objectifs distincts à mon sens :

• réduire l'empreinte mémoire
• ne pas avoir de "fuite" de mémoire

Tu as déjà visiblement bien travaillé à atteindre le premier objectif ; et tu te poses des questions sur le deuxième. Pour moi, ces 2 objectifs sont presque indépendants. Tu peux avoir beaucoup de mémoire allouée mais garantir qu'elle est stable. En revanche, le deuxième aide grandement à la réalisation du premier. Dur de rester avec une mémoire faible si on en paume régulièrement.

Parlons du deuxième ici. Le Garbage Collector (GC) semble une solution intéressante : si on oublie une libération mémoire, le GC va s'en occuper pour nous. Sauf que normalement, dans les langages à GC (tel que Java), on ne libère rien : le GC s'occupe de tout. L'utilisation d'un GC est un peu contradictoire avec la réduction maximale de l'empreinte mémoire. En effet, la mémoire n'est pas libérée dés qu'elle n'est plus utilisée, mais quand on s'aperçoit qu'elle n'est plus accessible / utilisable. Globalement, l'empreinte mémoire devrait augmentée (surtout qu'il faudra bien de la mémoire pour implémenter et faire tourner ce GC). Or, tu sembles vouloir limiter cette empreinte (notamment à la fin de ton message).

De plus, dire "Ciel, mon free() ! Je vais utiliser un GC si jamais je l'oublie" me semble être comme installer une système de télésurveillance car on a peur d'oublier de fermer sa porte à clé. Tu utilises valgrind, cela ne te suffit-il pas pour trouver les pertes de mémoire ?

Si tu veux quand même tester la solution du GC, il semble exister des GC pour C, tu devrais les essayer. Ce sera plus simple et sûrement plus fiable que si tu le fais toi même. Voir par exemple :
http://www.linuxjournal.com/article/6679
http://www.hpl.hp.com/personal/Hans_Boehm/gc/

Enfin, une remarque sur le fait que malloc() échoue. En général, cela vient du fait qu'il n'arrive pas à allouer une zone mémoire suffisamment grande et donc..... qu'il n'y a plus de mémoire disponible. Donc si malloc() échoue, ce n'est pas juste "coucou l'utilisateur, ça n'a pas marché, recommence !". Il faudra sûrement mettre en place une stratégie précise dans ce cas. Le GC n'aura aucun effet sur un tel problème.

En espérant t'avoir un peu aidé ;)

Je ne vais pas pouvoir t'aider mais dans ton message tu parles de PDF, est-ce qu'il serait possible de pouvoir partager ces documents car cela m'intéresse beaucoup ?

Citation:

---

Envoyé par Dinoosaure

Je me dis alors, et si le malloc foire ? [...] on signale l'erreur et on fait comme-ci l'utilisateur n'aurait pas ajouter cette élément. Bien entendu, on peut pas ignorer tout ce que rentre l'utilisateur.

J'opte donc pour la mise en place d'un GC Stop & Copy où l'espace se situera sur la Stack (entant que global)

---

Donc si j'ai bien compris, dans le cas ou malloc, qui a a disposition toute la memoire de la machine, et une zone de taille fixe preallouee, tu preferes le second cas....
Comment fais-tu si ta zone alloue (statiquement au debut du programme) est pleine d'objets vivants ?
Sans compter les pertes de performance liees au GC, mais bon, ca c'est encore autre chose.

En réalité, comme vous le souligné, le problème sur lequel je suis face, à savoir, mettre en place une sécurité par rapport au malloc qui peut échouer, ne peut pas être résolu par un GC (et si il y a plus de place dans le GC ?). Malheureusement, la politique adopté pour l'instant (lever l'erreur et laisser passer) ne me convient pas. Le problème du free ne se pose pas, j'ai fait différents tests et, au pire, je pourrais utiliser la méthode de: les mallocs sont enregistrer dans une liste qu'on s'occupe de free après.

Le problème est que les allocations de mémoire dans mon programme sont décisifs et je sais pas réellement qu'elle politique mené face à un environnement hostile. Au final, je voudrais vraiment « encore » réduire l'empreinte mémoire (est ce possible pour un arbre, une liste doublement chaînée circulaire ?) pour au final minimiser au plus bas, la vérification du retour du malloc.

Sinon, d'un point de vue didactique, je souhaite quand même savoir ce qu'il en est de cette racine dont on parle pour les GCs. J'ai toujours pas compris cette notion et où elle se situe réellement dans la mémoire (en réalité, si elle se situe dans le heap, l'implémentation du GC est alors, pour moi, un peu contradictoire). C'est pour ça que je vais omettre l'utilisations des implémentations que propose Bktero.

Je suis ouvert à toutes les solutions, j'ai face à moi, une AST (arbre n-aires) en réalité, un arbre binaire équilibré pour l'environnement (qui peut en contenir d'autres) et des listes doublements chaînées circulaires ainsi que les chaînes de caractères. Si vous ne voyez toujours pas, je suis dans l'implémentation d'un langage fonctionnel :lol: ! Vous comprenez donc bien que je peux pas ignorer le code que rentre l'utilisateur si un malloc échoue et je peux pas non plus ignorer le résultat que peux donner un code aussi. La structure global est donc complexe et je ne sais pas comment réagir (car je ne sais pas non plus comment réagissent les implémentations d'un langage face à un environnement hostile).

Il y a tout de même une solution viable qui est celle de créer un compilateur vers un opcode cible pour ensuite l'exécuter sur une VM contenant un GC. En effet, j'ai pu lire que l'implémentation en C d'un GC n'est pas conseillé sauf dans le cadre d'une VM mais étant donné que j'interprète directement le code, changer le fonctionnement de mon code va prendre un temps fou !

En tout cas, merci de vos réponses.

EDIT: Pour les PDFs, je prépare une tarball.

Faire un GC peut être une bonne chose du point de vue théorique, mais pour une vraie application C, surtout avec ton idée de base d'un tableau statique, me parait inapproprié.

Ensuite, il faut que tu sois capable de retrouver chaque pointeur dans la pile. Et c'est encore pire si tu es en multi-thread...