Optimiser l'utilisation des pointeurs

Version imprimable

Voir 40 message(s) de cette discussion en une page

08/03/2006, 21h01
Emmanuel Delahaye

Citation:

Envoyé par progman

Ca me parait juste lent de marquer les n blocks occupés.

Quels n blocks ? Il y a 1 bloc à marquer par malloc(), c'est tout. La recherche du premier bloc libre peut être un peu lente si il n'y a des milliers de blocks, mais on en est pas là.

Si la question se pose, on peut faire 2 des listes chainées : une libre, une occupée. C'est un peu plus compliqué...

Bon, j'ai codé, c'est sûrement nettement améliorable, mais ça a l'air de fonctionner :

Code:

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
 
#include "mem.h"
#include <stdio.h>
 
struct block
{
	void *p;
	int libre;
};
 
static struct data
{
   void *p_mem;
   size_t block_nb;
   size_t block_size;
 
   struct block *G_a_blocs;
}G;
 
/*Initialise un bloc mémoire de block_nb blocs de taille size bits*/
int mem_init(size_t block_nb, size_t block_size) {
	if ((G.p_mem=malloc(block_nb*block_size)) != NULL) {
		G.G_a_blocs = malloc (sizeof *G.G_a_blocs * block_nb);
		G.block_nb=block_nb;
		G.block_size=block_size>>3;
		return 1;
	}
	else {
		return 0;
	}
}
 
void mem_trace(void) {
	int scan_bloc=0;
	while (scan_bloc<G.block_nb) {
		printf("%d\t%d\n", G.G_a_blocs[scan_bloc].p, G.G_a_blocs[scan_bloc].libre);
		scan_bloc++;
	}
}
 
void mem_end(void) {
	free(G.p_mem);
}
 
void *mem_malloc(size_t size) {
	int find_libre=0, scan_bloc=0;
	void *temp;
	if ((size <= G.block_size*G.block_nb) && (size > 0)) {
		while ((!find_libre) || (scan_bloc<G.block_nb)) {
			if (!(G.G_a_blocs[scan_bloc].libre)) {
				/* Bloc libre trouvé */
				temp=(scan_bloc!=0)?(G.G_a_blocs[scan_bloc-1].p):(G.p_mem);
				if ((temp+size/G.block_size) <= (G.p_mem+G.block_nb)) {
					G.G_a_blocs[scan_bloc].p=temp+(size/G.block_size);
					G.G_a_blocs[scan_bloc].libre=1;
					find_libre=1;
					return G.G_a_blocs[scan_bloc].p;
				} else {
					return NULL;
				}
			} else {
				/*On reboucle */
				scan_bloc++;
			}
		}
	} else {
		return NULL;
	}
}
 
void mem_free (void *p) {
	int scan_bloc=0, find_occupe=0;
	while (!find_occupe) {
		if (G.G_a_blocs[scan_bloc].p==p) {
			/* Bloc occupé trouvé */
			G.G_a_blocs[scan_bloc].libre=0;
			find_occupe=1;
		} else {
			/*On reboucle */
			scan_bloc++;
		}
	}
}

Edit: le code de mem_free c'était n'importe quoi, je l'ai recodé, mais il ne me satisfait qu'à moitié.

Ouais, ben en fait, il me manque encore quelque chose !
Si j'alloue comme ça :
Code:

1 2 3 4 5 6 7 8 9 10 11 int *p = mem_malloc(sizeof(*p) * 3); int *p2 = mem_malloc(sizeof(*p2) * 120); int *p3 = mem_malloc(sizeof(*p3) * 3); if (p2 != NULL) { mem_free (p2), p2 = NULL; } int *p4 = mem_malloc(sizeof(*p4) * 119);
Le p4 ne passe pas, il ne se met pas à la place de p2, alors qu'il a la place.
J'ai essayé de coder ça, mais ça m'alourdit le code et ça ne fonctionne pas plus.

08/03/2006, 22h07
Emmanuel Delahaye

Citation:

Envoyé par progman

Bon, j'ai codé, c'est sûrement nettement améliorable, mais ça a l'air de fonctionner :

Dans mem_init(), il faut initialiser le tableau de blocs avec les adresse des blocs et 'libre'.

Rien de nouveau :

Citation:

Envoyé par -ed-

Ensuite, il faut remplir le tableau de blocs avec les adresses précalculées et c'est là que ça devient interessant. (Penser aussi à affirmer le flag 'libre')

J'ai pas compris le >> 3 ...

Le >>3 était là pour ramener la taille, passée en bits, en une taille en octets.
L'init, j'avais pas capté le truc de mettre toutes les adresses de tous les blocs.
Du coup, le malloc, il lui faut faire une boucle, il va falloir mettre le flag libre à 0 entre le premier bloc libre et ce même bloc+size.
Non ?
Du coup, ça me parait consommer pas mal.
Ou alors, j'ai encore une fois mal lu, vite lu, je sais pas.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 int mem_init(size_t block_nb, size_t block_size) { int i; if ((G.p_mem=malloc(block_nb*block_size)) != NULL) { G.G_a_blocs = malloc (sizeof *G.G_a_blocs * block_nb); G.block_nb=block_nb; G.block_size=block_size>>3; for (i=0 ; i<block_nb ; i++) { G.G_a_blocs[i].p=G.p_mem+i*(block_size>>3); G.G_a_blocs[i].libre=1; } return 1; } else { return 0; } }
Auquel cas, j'ai des adresses de 4 octets en 4 octets (dans le cas de l'exemple). Si j'enlève le block_size, je le fais sur des blocs au niveau bits, si je le mets seul, je le fais sur des blocs beaucoup trop gros.
Soit j'ai encore rien compris, soit ya un truc qui m'échappe :fou:

Merci d'aider un :boulet: comme moi, Emmanuel.

Citation:

Envoyé par progman

Le >>3 était là pour ramener la taille, passée en bits, en une taille en octets.

Quelle complication. Qui t'as dis de passer la taille en bits ?

On passe toujours la taille en char (byte) c'est standard et ça marche à tout les coups. C'est ce que retourne suzeof.

Citation:

L'init, j'avais pas capté le truc de mettre toutes les adresses de tous les blocs.

C'est pas faute de l'avoir expliqué...

Citation:

Du coup, le malloc, il lui faut faire une boucle,

Oui, il doit trouver le premier bloc libre. à moins de le gérer...et de de le précacluler... J'ai peur que ce soit un peu compliqué...

Citation:

il va falloir mettre le flag libre à 0 entre le premier bloc libre et ce même bloc+size.

Comment ça 'entre' ? Tu n'as pas compris l'algo, il faut que je le répète.
MARQUER LE PREMIER BLOC LIBRE. Ou est le problème ?

Citation:

Du coup, ça me parait consommer pas mal.

Il y a un peu d'itération, oui. On fera des mesures...

On peut prévoir une complexité O(n) pour malloc() (recherche linéaire) et O(log(n)) pour free() si on utilise bsearch() (les pointeurs sont triés).

Des listes seront peut être plus efficace...

Je commente :
Code:

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 33 34 35 36 37 38 39 /* block_size est exprime en byte. */ int mem_init(size_t block_nb, size_t block_size) { int i; /* la taille allouee est donc de block_nb x block_size bytes. OK */ if ((G.p_mem=malloc(block_nb*block_size)) != NULL) { /* le tableau de gestion des blocs. OK */ G.G_a_blocs = malloc (sizeof *G.G_a_blocs * block_nb); /* malloc peut echouer. Manque un test... */ G.block_nb=block_nb; /* G.block_size=block_size>>3; NON. il n'y a rien a bricoler. On est deja en bytes : */ G.block_size=block_size; for (i=0 ; i<block_nb ; i++) { /* G.G_a_blocs[i].p=G.p_mem+i*(block_size>>3); que de complications... */ G.G_a_blocs[i].p=G.p_mem + (i * block_size); G.G_a_blocs[i].libre=1; } return 1; } else { return 0; } }
Voilà, c'est laborieux, mais on y arrive à peu près. L'important c'est que soit toi qui ait écrit le code.

Le principe est acquis. Je veux voir la suite.

OK, j'ai corrigé le mem_init. Si l'on a des blocs de 32 octets, on ne pourra allouer, via mem_malloc() que des blocs de taille inférieure ou égale à 32 octets. On n'allouera donc pas directement 128 octets ou plus si besoin ?
Car c'est ça, que j'essaie de dire avec :

Citation:

il va falloir mettre le flag libre à 0 entre le premier bloc libre et ce même bloc+size.

Voici le nouveau code :

Code:

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
 
#include "mem.h"
#include <stdio.h>
 
struct block
{
	void *p;
	int libre;
};
 
static struct data
{
   void *p_mem;
   size_t block_nb;
   size_t block_size;
 
   struct block *G_a_blocs;
}G;
 
/*Initialise un bloc mémoire de block_nb blocs de taille size bits*/
int mem_init(size_t block_nb, size_t block_size) {
	int i;
	if ((G.p_mem=malloc(block_nb*block_size)) != NULL) {
		if((G.G_a_blocs = malloc (sizeof *G.G_a_blocs * block_nb))!=NULL) {
			G.block_nb=block_nb;
			G.block_size=block_size;
			for (i=0 ; i<block_nb ; i++) {
				G.G_a_blocs[i].p=G.p_mem+i*block_size;
				G.G_a_blocs[i].libre=1;
			}
			return 1;
		} else {
			return 0;
		}
	}
	else {
		return 0;
	}
}
 
void mem_trace(void) {
	int scan_bloc=0;
	while (scan_bloc<G.block_nb) {
		printf("%d\t%d\n", G.G_a_blocs[scan_bloc].p, G.G_a_blocs[scan_bloc].libre);
		scan_bloc++;
	}
}
 
void mem_end(void) {
	free(G.p_mem);
}
 
void *mem_malloc(size_t size) {
	int find_libre=0, scan_bloc=0;
	if ((size <= G.block_size) && (size > 0)) {
		while ((!find_libre) && (scan_bloc < G.block_nb)) {
			if (G.G_a_blocs[scan_bloc].libre) {
				/* Un bloc libre trouvé */
				G.G_a_blocs[scan_bloc].libre=0;
				return G.G_a_blocs[scan_bloc].p;
			}
			else {
				scan_bloc++;
			}
		}
		if (scan_bloc == G.block_nb) {
			return NULL;
		}
	} else {
		return NULL;
	}
 
}
 
void mem_free (void *p) {
	int scan_bloc=0, find_p=0;
	while (!find_p) {
		if(G.G_a_blocs[scan_bloc].p==p) {
			if (!(G.G_a_blocs[scan_bloc].libre))
				G.G_a_blocs[scan_bloc].libre=1;
			find_p=1;			
		} else {
			scan_bloc++;
		}
	}
}

Citation:

Envoyé par progman

OK, j'ai corrigé le mem_init. Si l'on a des blocs de 32 octets, on ne pourra allouer, via mem_malloc() que des blocs de taille inférieure ou égale à 32 octets.

Oui, tu as demandé un allocateur rapide.

Citation:

On n'allouera donc pas directement 128 octets ou plus si besoin ?
Car c'est ça, que j'essaie de dire avec :

Citation:

il va falloir mettre le flag libre à 0 entre le premier bloc libre et ce même bloc+size.

On peut toujours faire plus compliqué, mais dès le début, j'ai parlé d'un allocateur de blocs de taille fixe. Tu te plaignais des performances de malloc(), j'ai donc proposé un mécanisme plus simpe (et forcément moins optimisé en mémoire). Ce genre de manip doit être réservée aux cas critiques (et donc parfaitement étudiés et dimensionnés). Pour le tout venant, on continue évidemment d'utiliser malloc()/free().

Citation:

Voici le nouveau code :

Quelques problèmes. Manque <stdlib.h>, puis :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Compiling: ..\mem.c ..\mem.c: In function `mem_init': ..\mem.c:27: warning: comparison between signed and unsigned ..\mem.c:28: warning: pointer of type `void *' used in arithmetic ..\mem.c: In function `mem_trace': ..\mem.c:43: warning: comparison between signed and unsigned ..\mem.c:44: warning: int format, pointer arg (arg 2) ..\mem.c: In function `mem_malloc': ..\mem.c:56: warning: comparison between signed and unsigned ..\mem.c:66: warning: comparison between signed and unsigned ..\mem.c:86:2: warning: no newline at end of file ..\mem.c:73: warning: control reaches end of non-void function Linking console executable: D:\dev\mem\cb\mem.exe Process terminated with status 0 (0 minutes, 1 seconds) 0 errors, 8 warnings
Je fais un simple
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 #include "mem.h" int main (void) { int ok = mem_init (4, 16); if (ok) { mem_end (); } return 0; }
et j'ai déjà
Code:

1 2 3 4 5 6 7 8 SYSALLOC 'M 003D24E0 64 4294967295 29:..\mem.c' SYSALLOC 'M 003D2528 32 4294967295 31:..\mem.c' SYSALLOC 'F 003D24E0 0 4294967295 65:..\mem.c' SYSALLOC 003D24E0 matched <...> SYSALLOC Err: Not-matched list: SYSALLOC Bloc 003D2528 (32 bytes) malloc'ed at line 31 of '..\mem.c' not freed
Je vois que j'ai 2 allocations dans mem_init() (M) et une libération (F) dans mem_end()

L'algo du mem_free() est fragile. Que ce passe-t-il si on passe NULL ou un adresse inconnue ?

C'était mem.c, stdlib.h est dans mem.h :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* mem.h */
#ifndef H_MEM
#define H_MEM
#include <stddef.h>
#include<stdlib.h>
 
int mem_init(size_t block_nb, size_t block_size);
void mem_trace(void);
void mem_end(void);
 
void *mem_malloc(size_t size);
void mem_free (void *p);
 
#endif

09/03/2006, 10h03
Emmanuel Delahaye

Citation:

Envoyé par progman

C'était mem.c, stdlib.h est dans mem.h :

et il n'a rien à y faire. Il doit être dans mem.c.
09/03/2006, 10h09
progfou

OK, c'est modifié.
Et les options de compilation que tu passes, quelles sont-elles, histoire que j'ai les même messages, car j'ai pas tout ça (-Wall chez moi).
Comment as-tu obtenu les appels SYSALLOC ?
J'ai corrigé un certain nombre de problèmes, je pense.
Il me reste l'arithmétique sur le (void *), je vois bien ce qu'est l'instruction, mais je ne sais pas ce que je peux faire pour enlever ce warning.

mem_free() modifié :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
void mem_free (void *p) {
	size_t scan_bloc=0;
	int find_p=0;
	if (p!=NULL) {
		while ((!find_p) || (scan_bloc < G.block_size)) {
			if(G.G_a_blocs[scan_bloc].p==p) {
				if (!(G.G_a_blocs[scan_bloc].libre))
					G.G_a_blocs[scan_bloc].libre=1;
					find_p=1;			
			} else {
				scan_bloc++;
			}
		}
	}
}

J'hésite à lui faire retourner une valeur, pour dire si ça s'est bien passé...

Citation:

Envoyé par progman

Et les options de compilation que tu passes, quelles sont-elles, histoire que j'ai les même messages, car j'ai pas tout ça (-Wall chez moi).
Code:

1 2 3 4 5 6 7 8 9 10 -O2 -DCODEBLOCKS -Wchar-subscripts -Wcomment -Wformat=2 -Wimplicit-int -Werror-implicit-function-declaration -Wmain -Wparentheses -Wsequence-point -Wreturn-type -Wswitch -Wtrigraphs -Wunused -Wuninitialized -Wunknown-pragmas -Wfloat-equal -Wundef -Wshadow -Wpointer-arith -Wbad-function-cast -Wwrite-strings -Wconversion -Wsign-compare -Waggregate-return -Wstrict-prototypes -Wmissing-prototypes -Wmissing-declarations -Wmissing-noreturn -Wformat -Wmissing-format-attribute -Wno-deprecated-declarations -Wpacked -Wredundant-decls -Wnested-externs -Winline -Wlong-long -Wunreachable-code
Citation:

Comment as-tu obtenu les appels SYSALLOC ?

Ma bidouille à moi :

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

mais ne te lances pas là dedans tout de suite. Une chose à la fois...

Citation:

J'ai corrigé un certain nombre de problèmes, je pense.
Il me reste l'arithmétique sur le (void *), je vois bien ce qu'est l'instruction, mais je ne sais pas ce que je peux faire pour enlever ce warning.

Il faut passer par un pointeur sur char.

09/03/2006, 10h44
Emmanuel Delahaye

Citation:

Envoyé par progman

mem_free() modifié :

OK.

Citation:

J'hésite à lui faire retourner une valeur, pour dire si ça s'est bien passé...

free() ne le fait pas, mais ça ne mange pas de pain...

Tout est corrigé :

Code:

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
 
#include "mem.h"
#include <stdio.h>
#include<stdlib.h>
 
struct block
{
	void *p;
	int libre;
};
 
static struct data
{
   void *p_mem;
   size_t block_nb;
   size_t block_size;
 
   struct block *G_a_blocs;
}G;
 
/*Initialise un bloc mémoire de block_nb blocs de taille size bits*/
int mem_init(size_t block_nb, size_t block_size) {
	size_t i;
	if ((G.p_mem=malloc(block_nb*block_size)) != NULL) {
		if((G.G_a_blocs = malloc (sizeof *G.G_a_blocs * block_nb))!=NULL) {
			G.block_nb=block_nb;
			G.block_size=block_size;
			for (i=0 ; i<block_nb ; i++) {
				G.G_a_blocs[i].p=(char *)G.p_mem+i*block_size;
				G.G_a_blocs[i].libre=1;
			}
			return 1;
		} else {
			return 0;
		}
	}
	else {
		return 0;
	}
}
 
void mem_trace(void) {
	size_t scan_bloc=0;
	while (scan_bloc<G.block_nb) {
		printf("%p\t%d\n", G.G_a_blocs[scan_bloc].p, G.G_a_blocs[scan_bloc].libre);
		scan_bloc++;
	}
}
 
void mem_end(void) {
	free(G.p_mem);
	free(G.G_a_blocs);
}
 
void *mem_malloc(size_t size) {
	int find_libre=0;
	size_t scan_bloc=0;
	if ((size <= G.block_size) && (size > 0)) {
		while ((!find_libre) && (scan_bloc < G.block_nb)) {
			if (G.G_a_blocs[scan_bloc].libre) {
				/* Un bloc libre trouvé */
				G.G_a_blocs[scan_bloc].libre=0;
				return G.G_a_blocs[scan_bloc].p;
			}
			else {
				scan_bloc++;
			}
		}
		if (scan_bloc == G.block_nb) {
			return NULL;
		}
	} else {
		return NULL;
	}
 
}
 
void mem_free (void *p) {
	size_t scan_bloc=0;
	int find_p=0;
	if (p!=NULL) {
		while ((!find_p) || (scan_bloc < G.block_size)) {
			if(G.G_a_blocs[scan_bloc].p==p) {
				if (!(G.G_a_blocs[scan_bloc].libre))
					G.G_a_blocs[scan_bloc].libre=1;
					find_p=1;			
			} else {
				scan_bloc++;
			}
		}
	}
}

Citation:

Envoyé par progman

Tout est corrigé :

Avec ce code de test:

Code:

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
 
#include "mem.h"
 
static void aff_ap(int **pp, int n)
{
   int i;
   for (i = 0; i < n; i++)
   {
      printf ("[%d]%p ", i, pp[i]);
   }
   printf ("\n");
}
 
 
int main (void)
{
   int ok = mem_init (4, 16);
 
   if (ok)
   {
      mem_trace();
      {
         int *ap[5] = {
                         0};
         int i;
         for (i = 0; i < 5; i++)
         {
            ap[i] = mem_malloc(2 * (i + 1));
            aff_ap(ap, 5);
            mem_trace();
         }
         mem_free(ap[1]), ap[1] = NULL;
         aff_ap(ap, 5);
         mem_trace();
 
         mem_free(ap[3]), ap[3] = NULL;
         aff_ap(ap, 5);
         mem_trace();
 
         mem_free(ap[0]), ap[0] = NULL;
         aff_ap(ap, 5);
         mem_trace();
 
         mem_free(ap[4]), ap[4] = NULL;
         aff_ap(ap, 5);
         mem_trace();
 
         mem_free(ap[2]), ap[2] = NULL;
         aff_ap(ap, 5);
         mem_trace();
      }
      mem_end ();
   }
 
   return 0;
}

J'ai une boucle infinie...

Code:

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
 
003D2500        1
003D2510        1
003D2520        1
003D2530        1
[0]003D2500 [1]00000000 [2]00000000 [3]00000000 [4]00000000
003D2500        0
003D2510        1
003D2520        1
003D2530        1
[0]003D2500 [1]003D2510 [2]00000000 [3]00000000 [4]00000000
003D2500        0
003D2510        0
003D2520        1
003D2530        1
[0]003D2500 [1]003D2510 [2]003D2520 [3]00000000 [4]00000000
003D2500        0
003D2510        0
003D2520        0
003D2530        1
[0]003D2500 [1]003D2510 [2]003D2520 [3]003D2530 [4]00000000
003D2500        0
003D2510        0
003D2520        0
003D2530        0
[0]003D2500 [1]003D2510 [2]003D2520 [3]003D2530 [4]00000000
003D2500        0
003D2510        0
003D2520        0
003D2530        0
<boucle infinie... >

Ok. C'est un bug dans mem_free() (la condition du while est fausse)

09/03/2006, 11h21
progfou

Oui, c'est un bug dans la condition, mais je ne vois pas mon error, il faut quitter si on a trouvé le bloc, ou si on est arrivé au bout des blocs, c'est bien un ou...
Non ?
09/03/2006, 11h23
fearyourself

Citation:

Envoyé par progman

Oui, c'est un bug dans la condition, mais je ne vois pas mon error, il faut quitter si on a trouvé le bloc, ou si on est arrivé au bout des blocs, c'est bien un ou...
Non ?

Non c'est un ET...

Tant qu'on n'est pas à la fin et tant qu'on n'a pas trouvé l'élément recherché...
09/03/2006, 11h24
Emmanuel Delahaye

Citation:

Envoyé par progman

Oui, c'est un bug dans la condition, mais je ne vois pas mon error, il faut quitter si on a trouvé le bloc, ou si on est arrivé au bout des blocs, c'est bien un ou...
Non ?

La condition du while() c'est pour rester, c'est pas pas pour quitter...

Tu l'as fait ailleurs correctement...
09/03/2006, 11h26
progfou

Merci !
Avec un ET ça tourne.

Voir 40 message(s) de cette discussion en une page