Discussion :

[Fused]

Bonjour,

Je cherche a faire un Garbage Collector en C.

J'ai choisi Mark and Sweep.

J'ai compris l'algo, ce n'est pas bien complique, mais j'ai tout de meme certaines difficultees :

Comment, en recuperant un pointeur, parcourir son arborescence ?

Et pour le sweep, comment parcourir toute la memoire du processus en cours ?

Si vous avez de la doc precise sur comment implementer cet algo, ca m'interesse ! Ca en manque cruellement sur internet, pourtant, j'ai du mal a croire que personne ai jamais voulu implementer un garbage collector pour C.


Merci a vos propositions !

P.S : excusez l'accentuation, je suis sur clavier qwerty canadien avec configuration US...

[nicolas.sitbon]

Ca en manque cruellement sur internet, pourtant, j'ai du mal a croire que personne ai jamais voulu implementer un garbage collector pour C.

http://www.hpl.hp.com/personal/Hans_Boehm/gc/

[Fused]

Ok, j'ai rien dit !

Toujours est-il que je veux faire qq chose de plus petit, seulement du mark and sweep ; voila mon pseudo code pour l'instant, ce qui est en anglais sont les endroits ou je bute pour ecrire en C.

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
22
23
24
25
26
27
28
29
30
31
32
void mark_sweep() {
	// pour chaque racine
	for each root variable r {
		mark (r);
		sweep ();
	}
}
 
void mark (Object p) {
	// si p n'est pas deja marque
	if (!p.marked) {
		p.marked = true;	// on le marque
		for (each Object q referenced by p) {
		// et on parcours son arborescence pour faire de meme
			mark (q);
		}
	}
}
 
void sweep () {
	// parcours du tas
	for each Object p in the heap {
		if (p.marked) {
			// si il etait marque, on le demarque
			p.marked = false;
		}
		else {
			// sinon on efface
			heap.release (p);
		}
	}
}

Neamoins je conserve ton lien, ca me servira surement plus tard

[Médinoc]

je crois que tu ne peux pas parcourir l'arborescence de l'objet dans avoir des informations de type: Typiquement, son nombre de variables, et lesquelles parmi ces variables sont des types références.
Tu peux gagner de la performance en décidant "toi-même" (cad, à la place de l'utilisateur) de la structure en mémoire des objets: Par exemple, mettre toujours les types références avant les types valeur, comme ça les seules informations de type dont tu as besoin sur un objet, c'est le nombre de variables de types références qu'il contient...

[Emmanuel Delahaye]

Je cherche a faire un Garbage Collector en C.

[troll=ON]
Ca sert à quoi un ramasse-miette ? C'est pour les fainéants qui ne savent pas programmer ?
[/troll]

[Obsidian]

[troll=ON]
Ca sert à quoi un ramasse-miette ? C'est pour les fainéants qui ne savent pas programmer ?
[/troll]

Pour une fois, je suis d'accord !

Mais bon, en l'occurence, il essaie d'en coder lui-même, en s'étant penché sur un algorithme. 'faut déja avoir envie de se retrousser les manches.

[Fused]

je crois que tu ne peux pas parcourir l'arborescence de l'objet dans avoir des informations de type: Typiquement, son nombre de variables, et lesquelles parmi ces variables sont des types références.
Tu peux gagner de la performance en décidant "toi-même" (cad, à la place de l'utilisateur) de la structure en mémoire des objets: Par exemple, mettre toujours les types références avant les types valeur, comme ça les seules informations de type dont tu as besoin sur un objet, c'est le nombre de variables de types références qu'il contient...

Oui, en effet, en bidouillant je me suis arrangé, je savais quels types d'objets j'ai à manipuler ici en l'occurence, je ne fais pas un Mark&Sweep générique.

Ca me donne ça :

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
mark_sweep()={   Racines R=Racines;
		 while(R!=NULL) {mark(R->objet); R=R->next;}
		 sweep();
		 if (space_freed<BORNE) printf("abort");}
 
mark(val_t *N)={if (N.v.markbit=0) {N.v.markbit=1;
		 Racines P=Children(N);
		 while(P!=NULL) {mark(P->objet); P=P->next;}}
		}
int spaced_freed=0;
int insert_into_pool(val_t *node) {space_freed=space_freed+sizeof(node);}
 
sweep()={int N=allocbuf;
	 while(N<allocbuf+ALLOCSIZE){
		if(N.v.markbit=0){free(N);
				  insert_into_pool(N);}
		else N.v.markbit=0;}
	 N=N+sizeof(val_t); }

Beau bordel, mais ça à l'air de marcher !

[troll=ON]
Ca sert à quoi un ramasse-miette ? C'est pour les fainéants qui ne savent pas programmer ?
[/troll]

C'est la première fois que je vois un admin d'un gros forum venir critiquer d'une manière si puérile et sans motif...

Je pense que tu sais à quoi sert un ramasse miettes.
Je suppose donc que tu n'utilises aucun langage où la gestion de la mémoire est automatique puisque c'est pour des fainéants qui ne savent pas programmer ?

D'ailleurs, je ne fais pas ça par plaisir, et loin de là, c'est pour un cours sur la gestion de mémoire. Il faut bien apprendre non ?

Et pour finir, oui, ça arrive qu'il y ai des gens qui ne savent pas bien programmer et qui n'en on vraiment rien à faire de comment la mémoire de leur programme s'alloue et se désaloue.

A bon entendeur...

[maxim_um]

salut,

C'est la première fois que je vois un admin d'un gros forum venir critiquer d'une manière si puérile et sans motif...

Il n'est pas admin. Et il a anticipé ta réponse en utilisant le mode troll.

[Fused]

Modérateur, tu m'as compris.
Si le "mode Troll" est un jargon de forum pour autoriser à dire des choses pareil, OK. Je ne suis pas familiarisé avec tout ça.

Mais pas d'importance, il y a des choses mieux à faire que de débattre là dessus ! Passons.

Je continue mes algos que j'aime pas !

[Médinoc]

Les balises "troll" introduisent plutôt un sarcasme, signe qu'on ne pense pas vraiment ce qu'on dit entre ces balises, ou bien que si on l'a pensé, on a grandi depuis.

[Obsidian]

Modérateur, tu m'as compris.
Si le "mode Troll" est un jargon de forum pour autoriser à dire des choses pareil, OK. Je ne suis pas familiarisé avec tout ça.

Un troll, c'est ça : http://uzine.net/article1032.html

Et par extension, ça a fini par désigner le sujet qui fâche en lui-même, soit un commentaire apparement anodin mais bien placé qui va déclencher des cascades de réactions, pour la plupart stériles et hors-sujet. Donc, quand on met les balises, c'est que c'est une remarque sarcastique ou ironique, et qu'il ne faut surtout pas y réagir.

Mais en l'occurence, c'était tout sauf une attaque personnelle. C'est même le contraire, étant donné qu'écrire un garbage collector propre réclame beaucoup de soin.

La remarque était là pour souligner le fait que bon nombre d'étudiants en programmation peinent avec la gestion de la mémoire en C parce qu'ils se mettent dans des impasses au niveau algorithmique. Dès lors, ils ont tendance à se rabattre vers d'autres langages équipés de tels GC, qu'ils qualifient alors de « mieux conçus » ! Et ça fait enrager les puristes car le problème de fond n'est toujours pas résolu.

[Fused]

Merci pour ces éclaircissements, je m'endormirai moins bête

Je n'ai pas tout lu la définition, mais j'ai compris le principe.

[Vincent Rogier]

Ce qui rend aussi compliqué un ramasse miette en C, c'est la gestion des cadences et fréquences de nettoyage...

La plupart des langages qui disposent d'un GC s'appuient sur un GC indépendant de l'appli et qui tourne en parallèle et donc intégré à une VM ou un runtime.

Le C ne proposant pas de gestion de synchronisation/threading, cela revient à déclencher les mécanismes d'un GC manuellement ou lors d'opération d'allocation/désallocation...

C'est pour cela qu'un GC est selon moi pas des masses intéressant en C (qui n'est pas prévu pour) car son intégration intelligente n'est pas portable (lié à la plateforme) et nécessite un élement exterieur à l'appli (runtime ou VM)...

[Fused]

C'est bien ce que j'ai remarqué, on est obligé de bloquer le processus pendant une courte période pour effectuer le GC.

Mais bon c'était pour un devoir sur la gestion de mémoire, pour un programme particulier, pas pour une vraie utilisation de tous les jours !

[Emmanuel Delahaye]

C'est bien ce que j'ai remarqué, on est obligé de bloquer le processus pendant une courte période pour effectuer le GC.

Mais bon c'était pour un devoir sur la gestion de mémoire, pour un programme particulier, pas pour une vraie utilisation de tous les jours !

Dans la vie de tous les jours, on se retrousse les manches et on écrit du code correct avec un gestion de méoire vérifiée. Il est simple de s'écrire un outil de vérification :

http://emmanuel-delahaye.developpez.com/clib.htm
Module SYSALLOC

Pas besoin d'un bazar qui va me piquer la mémoire sans me prévenir... Comment ça se passe un GC sur une application 24/7 ?

[Obsidian]

Comment ça se passe un GC sur une application 24/7 ?

En théorie, c'est la même chose : un taux de RAM à peu près constant, et légèrement surestimé par rapport à la consommation réelle (ce qui reste mal sur un ordinateur). Mais c'est tellement plus simple de réclamer au moment où on en a besoin et ne plus s'en soucier ensuite :-) Ni même au préalable, d'ailleurs. Qu'importe si un « Hello World » prend 20 méga-octets ...

[Emmanuel Delahaye]

En théorie, c'est la même chose : un taux de RAM à peu près constant, et légèrement surestimé par rapport à la consommation réelle (ce qui reste mal sur un ordinateur). Mais c'est tellement plus simple de réclamer au moment où on en a besoin et ne plus s'en soucier ensuite :-) Ni même au préalable, d'ailleurs. Qu'importe si un « Hello World » prend 20 méga-octets ...

Je n'arrive pas à comprendre quel est le critère pour libérer la mémoire automatiquement.

[Obsidian]

Je n'arrive pas à comprendre quel est le critère pour libérer la mémoire automatiquement.

Le critère qui englobe tout est (tout naturellement) « dès lors que le système est sûr que l'objet n'est plus accessible ». Évidemment, ça implique que ledit système dipose de moyens pour le vérifier, et c'est pour cela qu'un GC n'est réellement efficace que si c'est en collaboration avec le système qui l'exploite. C'est donc très contextuel.

Je n'utilise pratiquement jamais les langages à GC, donc je ne suis pas le plus à même de disserter dessus, mais la page consacrée du Wikipédia est assez bien écrite. J'aime particulièrement la citation finale :

« Il est dit que les programmeurs Lisp savent que la gestion de la mémoire est si importante qu'elle ne peut être laissée aux programmeurs, et que les programmeurs C savent que la gestion de la mémoire est si importante qu'elle ne peut être laissée au système » -- Bjarne Stroustrup peut-être tiré d'une source antérieure.

Plus que le simple glanage des « cellules mortes », les avantages d'un système entier de gestion de la mémoire confié au système et d'une couche d'abstration par dessus sont la possibilité de déplacer les objets en mémoire au besoin, et dans certains cas, le recyclage d'objets ou de ressources préalablement allouées.