Un ramasse miette en C

**Fused** · 21/11/2008, 21h59

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** · 21/11/2008, 22h13

Envoyé par Fused

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** · 21/11/2008, 22h36

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** · 23/11/2008, 15h11

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

**Fused** · 24/11/2008, 19h52

Envoyé par 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...

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 !

Envoyé par Emmanuel Delahaye

[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...