Discussion :

[Crisanar]

Bonjour à tous,
Je suis en train de développer une applic qui utilise une liste liée dynamique dont chaque élément est une structure de type :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
DL_element struct
   Val      DWORD ?
   pNext DWORD ?
DL_element ends

Pour créer dynamiquement chaque élément j'utilise VirtualAlloc. Mais j'ai cru lire que VirtualAlloc arrondi chaque allocation à la taille d'une page.
Or ma liste peut contenir énormément d'éléments donc si a chaque élément j'utilise 4096 bytes (taille d'une page sur mon ordi si je ne me suis pas trompé), j'aurais vite rempli la mémoire.
Que me conseillez-vous d'utiliser?

Merci d'avance,
Crisanar

[Aurelien.Regat-Barrel]

Oui il vaut mieux passer par le tas.
http://msdn.microsoft.com/library/en-us/dngenlib/html/msdn_virtmm.asp
mais dans un tel cas, il faudrait créer ton propre allocateur qui gère un pool d'éléments. Les langages de haut niveau gèrent très bien les listes chainées...

[Crisanar]

Merci pour ta réponse
Je sais que je devrais arreter l'ASM mais je n'arrive pas à m'en séparer

[camboui]

GlobalAlloc, le plus simple.
HeapAlloc, un peu plus compliqué, mais probablement plus performant.

Sinon, tu peux te faire ta propre gestion de mémoire. Voici un début pour t'inspirer.
H:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
struct SVarBlock {
	SVarBlock *s_next;
	//char strBuf[];
	};

inline void InitBlocks(SVarBlock & vb)
	{ vb.s_next=(SVarBlock *)0; }

void * NewBlock(SVarBlock & vb,unsigned blockSize);

void DestroyBlocks(SVarBlock & vb);

int DeleteBlock(SVarBlock & vb,void *block);

CPP:

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
33
34
35
36
void * NewBlock(SVarBlock & vb,unsigned blockSize)
{
SVarBlock *pb=(SVarBlock *)malloc(sizeof(SVarBlock)+blockSize);
if (pb) {
	pb->s_next=vb.s_next;
	vb.s_next=pb;
	return pb+1;
	}
return 0;
}

void DestroyBlocks(SVarBlock & vb)
{
SVarBlock *pb=vb.s_next;
while (pb!=(SVarBlock *)0) {
	SVarBlock *temp=pb->s_next;
	free(pb);
	pb=temp;
	}
vb.s_next=NULL;
}

int DeleteBlock(SVarBlock & vb,void *block)
{
SVarBlock **ppb=&vb.s_next;
SVarBlock *bl=((SVarBlock *)block)-1;
while (*ppb!=(SVarBlock *)0) {
	if (*ppb==bl) {
		*ppb=bl->s_next;
		free(bl);
		return 1;
		}
	ppb=&(*ppb)->s_next;
	}
return 0;
}

[Crisanar]

Salut camboui,
Merci pour ta réponse
Lorsque tu dis faire ma propre gestion mémoire, je ne comprend pas très bien, malloc et free sont des fonctions du CPP mais elles appellent des fonctions de Windows, donc mis à part le fait de ne pas me tracasser des APIs à utiliser je ne vois pas trop l'intéret d'utiliser ces fonctions.

Au fait, quel avantage à utiliser un malloc par rapport à un new?

Aurelien.Regat-Barrel : je viens de relire ton post

il faudrait créer ton propre allocateur qui gère un pool d'éléments

Je ne comprends pas ce que tu veux dire, tu peux m'en dire un peu plus?

Merci à tous
Crisanar

[camboui]

Faut lire entre les lignes...
J'avais déjà remarqué le pragmatisme excessif du forum

Tu peux/devrais bien sûr remplacer malloc() et free() par GlobalAlloc(GMEM_FIXED,) et GlobalFree().

new fait un appel à malloc en interne.

Aurélien a été assez clair je pense. Voici un exemple de pool, en complément du précédant code.
H:

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
33
34
35
36
37
38
39
40
41
class MemoryCollection
{
	struct SCell
	{
		SCell *s_next;
		//char s_data[dataSize !!! -sizeof(SCell *)];
	};
	SVarBlock f_vb;
	SCell *f_freeCells;
	unsigned f_cellsPerBlock,f_cellsUsedCount,f_cellSize;

	void Destroy();
	int AllocCells();
public:
	MemoryCollection();
	MemoryCollection(unsigned cpBlock,unsigned dataSize);
	~MemoryCollection();
	int Init(unsigned cpBlock,unsigned dataSize);
	unsigned Count()
		{ return f_cellsUsedCount; }
	void *NewMem();
	void DeleteMem(void *data);
};


template <class T> class MemoryCollectionTpl&#58; protected MemoryCollection
&#123;
public&#58;
	MemoryCollectionTpl&#40;&#41;
		&#58;MemoryCollection&#40;&#41; &#123;&#125;
	MemoryCollectionTpl&#40;unsigned cpBlock&#41;
		&#58;MemoryCollection&#40;cpBlock,sizeof&#40;T&#41;&#41; &#123;&#125;
	int Init&#40;unsigned cpBlock&#41;
		&#123; return MemoryCollection&#58;&#58;Init&#40;cpBlock,sizeof&#40;T&#41;&#41;; &#125;
	unsigned Count&#40;&#41;
		&#123; return MemoryCollection&#58;&#58;Count&#40;&#41;; &#125;
	T *NewMem&#40;&#41;
		&#123; return &#40;T *&#41;MemoryCollection&#58;&#58;NewMem&#40;&#41;; &#125;
	void DeleteMem&#40;T *data&#41;
		&#123; MemoryCollection&#58;&#58;DeleteMem&#40;data&#41;; &#125;
&#125;;

CPP:

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
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
MemoryCollection::MemoryCollection()
:f_freeCells(NULL)
,f_cellsPerBlock(0u)
,f_cellsUsedCount(0u)
,f_cellSize(sizeof(SCell))
{
InitBlocks(f_vb);
}

MemoryCollection::MemoryCollection(unsigned cpBlock,unsigned dataSize)
:f_freeCells(NULL)
,f_cellsPerBlock(cpBlock)
,f_cellsUsedCount(0u)
,f_cellSize(dataSize>sizeof(SCell)?dataSize:sizeof(SCell))
{
f_cellSize=(f_cellSize+7u) & ~7u;
InitBlocks(f_vb);
AllocCells();
}

MemoryCollection::~MemoryCollection()
{
Destroy();
}

void MemoryCollection::Destroy()
{
DestroyBlocks(f_vb);
}

int MemoryCollection::AllocCells()
{
SCell *cell=(SCell *)NewBlock(f_vb,f_cellsPerBlock*f_cellSize);
if (!cell) return 0;
((char *&)cell)+=(f_cellsPerBlock-1)*f_cellSize;
for(int i=f_cellsPerBlock-1;i>=0;i--) {
	cell->s_next=f_freeCells;
	f_freeCells=cell;
	((char *&)cell)-=f_cellSize;
	}
return 1;
}

int MemoryCollection::Init(unsigned cpBlock,unsigned dataSize)
{
Destroy();
f_freeCells=NULL;
f_cellsPerBlock=cpBlock;
f_cellsUsedCount=0u;
f_cellSize=dataSize>sizeof(SCell)?dataSize:sizeof(SCell);
f_cellSize=(f_cellSize+7u) & ~7u;
InitBlocks(f_vb);
return AllocCells();
}

void *MemoryCollection::NewMem()
{
if (f_freeCells==(SCell *)0)
	if (!AllocCells())
		return NULL;
register SCell *newCell=f_freeCells;
f_freeCells=newCell->s_next;
f_cellsUsedCount++;
return newCell;
}

void MemoryCollection::DeleteMem(void *data)
{
if (data==NULL)
	return;
f_cellsUsedCount--;
register SCell *cell=(SCell *)data;
cell->s_next=f_freeCells;
f_freeCells=cell;
}

Voilà, l'ensemble de ce code permet de gérer de nombreuses petites allocations en allouant peu de gros blocks auprès du système. Je n'ai rien inventé, il est extrait/inspiré de MFC

C'est du code assez bas niveau, à utiliser si on le comprend. Par exemple, il faut savoir que la mémoire n'est libérée auprès du système qu'en une fois, lors de la destruction de MemoryCollection. Mais les petites allocations/libérations au sein de MemoryCollection sont bien gérées (et très rapides).

[camboui]

Lorsque tu dis faire ma propre gestion mémoire, je ne comprend pas très bien, malloc et free sont des fonctions du CPP mais elles appellent des fonctions de Windows, donc mis à part le fait de ne pas me tracasser des APIs à utiliser je ne vois pas trop l'intéret d'utiliser ces fonctions.

Je te rappelle que le C est un langage sensé être indépendant du système. malloc et free existent depuis plus de 25 ans, l'API Windows est plus récente...
Ensuite, on ne sait pas toujours ce qu'il y a derrière l'API de Windows. Fais un programme qui utilise et abuse des GlobalAlloc/FreeAlloc et fais-le tourner sous 95/98/Me, tu auras des performances catastrophiques... Il ira beaucoup mieux sous NT.
Je sais, je sais, de nos jours nous sommes sous XP qui n'est pas trop mal foutu, mais on ne s'amuse pas à réécrire du code sous prétexte que l'OS s'est amélioré. D'autant que 98/Me est encore très répandu.

[Crisanar]

Salut camboui,
Merci pour ce complément d'informations
Je dois t'avouer que je n'ai pas compris ton code en CPP, j'ai qqes notions mais celà reste très basique.

Lorsque je demandais des explications à Aurelien, je voulais en fait demander ce que voulait dire un 'pool d'éléments', je connais les 2 mots mais mis ensemble, je ne sais pas à quoi celà correspond

Si je n'utilise pas les fonctions malloc, free, new, delete, c'est parce que je programme en ASM et que donc elles n'existent pas (à moins de les coder moi-même ou de les trouver, mais bon).
Ma liste chainée étant déja créée, j'ai seulement remplcé les APIs VirtualAlloc et VirtualFree par HeapAlloc et HeapFree.

Crisanar

[Aurelien.Regat-Barrel]

Je pensais au concept du pool comme (bien) expliqué ici (c'est pour du C++):
http://www.boost.org/libs/pool/doc/concepts.html
en gros, c'est un malloc maison spécilisé pour ton besoin. Il tient compte des spécificités de tes allocations, comme par exemple du fait que c'est toujours des objets de la même taille. C'est une couche supérieure à malloc/GlobalAlloc. En gros, ton pool alloue un gros bloc de mémoire avec malloc(), et il se le gère en interne de manière optimisée à ton besoin.
D'ailleurs c'est ce que fait malloc vis à vis de HeapAlloc, et c'est ce que fait HeapAlloc vis à vis de VirtalAlloc...

[Crisanar]

Merci beaucoup pour le lien, j'aurais encore appris quelque chose aujourd'hui

[camboui]

Salut camboui,
Merci pour ce complément d'informations
Je dois t'avouer que je n'ai pas compris ton code en CPP, j'ai qqes notions mais celà reste très basique.

Oops, désolé.
Je comprend que ce genre de code puisse être rébarbatif, même pour les plus chevronnés du 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
int DeleteBlock(SVarBlock & vb,void *block) 
{ 
SVarBlock **ppb=&vb.s_next; 
SVarBlock *bl=((SVarBlock *)block)-1; 
while (*ppb!=(SVarBlock *)0) { 
   if (*ppb==bl) { 
      *ppb=bl->s_next; 
      free(bl); 
      return 1; 
      } 
   ppb=&(*ppb)->s_next; 
   } 
return 0; 
}

Mais ce n'est rien à coté de Perl ou XSLT