Malloc semble allouer plus de mémoire que nécessaire

Version imprimable

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

Bonjour,

Je souhaite essayer de comprendre comment la mémoire est allouée par malloc en C :
Code:

1 2 3 4 5 6 7 8 9 10 11 int c; system("pause"); for(c=0; c<1024; c++) { char* tmp = malloc(8); //char* tmp = calloc(8, sizeof(char)); //printf("%d\n", _msize(tmp)); tmp[0] = '\0'; } system("pause"); exit(-1);
Soit le programme suivant dans le main. Normalement je devrais allouer 1024*8 octets = 8192 octets = 8 Ko
Or dans le gestionnaire de mémoire de Windows 7, mon programme alloue 16 Ko de mémoire entre mes deux system("pause").

J'ai d'abord pensé aux alignements mémoire mais 8 étant un multiple de 8, normalement, il ne devrait pas y avoir d'alignement.

Je voudrais comprendre pourquoi j'ai deux fois plus de mémoire allouée sachant que j'ai besoin d'optimiser la mémoire de mon programme.

PS : J'ai testé aussi avec 45 000 000 d'itérations dans la boucle for, même problème, j'ai deux fois plus de mémoire allouée au final.

Merci d'avance :)

Bonjour
Il me semble que c'est normal et cela est peut-être dû aux données d'alignement essayer de faire un cast sur la valeur de retour et tester éventuellement si l'allocation est correcte.
Cependant, je ne comprends pas trop l'intérêt d'effectuer une allocation avec une valeur constante dans une boucle ? :weird:
y a-t-il pas écrasement d'adresse d'allocation à chacun itération ?

Citation:

Envoyé par Aspic

for(c=0; c<1024; c++)
{
char* tmp = malloc(8);
//char* tmp = calloc(8, sizeof(char));
//printf("%d\n", _msize(tmp));
tmp[0] = '\0';
}

Il est plutôt préférable d'effectuer une seule allocation et ainsi utiliser cette adresse autrement exemple:
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 #include <stdio.h> #include <stdlib.h> int main( void ){ char *ptr = NULL; unsigned int i = 0; const size_t size = 127; ptr = (char*)malloc( size * sizeof(char) ); if( (NULL) == ptr ){ perror("Erreur Allocation mémoire\n"); exit( EXIT_FAILURE ); } for( i = 0; i < size; i++ ) *(ptr+i) = (char)i; for( i = 0; i < size; i++ ) printf( "(%d)\t:%c\n", i, *(ptr+i) ); free( ptr ); ptr = NULL; return( EXIT_SUCCESS ); }
à bientôt

07/04/2015, 14h53
picodev

Bonjour,

Il n'y a pas un malloc en C. Il y a différentes stratégies d'allocation de mémoire suivant la plateforme et la libc utilisée. Pour avoir plus d'infos, comme tu sembles utiliser windows, il faudrait creuser sur MSDN si tu trouves tes réponses, wikipedia ne présentant que les differentes stratégies sur quelques unix.
07/04/2015, 15h00
sambia39

En complément regardez également du coté Windows
à bientôt
07/04/2015, 15h19
grim7reaper

Salut,

Comme dit plus haut, impossible de te répondre avec exactitude sans avoir plus d’info.

De manière générale, un allocateur alloue toujours des métadonnées (leur localisation et leur taille dépend de l’allocateur utilisé) en plus de la mémoire que tu lui demandes.
Ici tu alloues des blocs de 8 octets, si l’allocateur alloue 8 octets de métadonnées pour chaque allocation, ça pourrait expliquer ton x2 en taille.
Est-ce que tu as toujours ce facteur de x2 en allouant des blocs de 64Ko ?

Je te donne une explication parmi d’autres (elle est peut être fausse), il faut lire la documentation de l’allocateur utilisé (je ne connais pas trop le monde Windows…) pour savoir exactement ce qu‘il se passe.
07/04/2015, 17h00
Aspic

Bonjour à tous,

Voilà plus d'informations :

Je compile mon programme sous GCC version 4.7.2 avec MinGW avec CodeBlocks pour être exact ;)
Je compile en Release avec l'option -O2 pour l'optimisation.

Je ne travaille donc pas avec Visual studio et son compilateur propriétaire.

En testant avec 1024 malloc de blocs mémoire de taille 64, je devrais en théorie avoir 1024*64 = 65536 octets = 64 Ko et j'ai en mémoire en réel : 76 Ko soit une différence de 12 Ko

Avec 1024 malloc de blocs mémoire de taille 128 => 1024*128 = 131072 octets = 128 Ko. En vrai, j'ai 156 Ko d'alloué soit une différence de 28 Ko.

Je ne sais pas si on peut établir une "loi" en fonction de la taille du bloc mémoire mais en tout cas, il semble bel et bien y avoir des métadonnées allouées. Y'a t-il un moyen d'en savoir plus au niveau du code ?

Ca m'embête un peu sachant que je dois allouer 45 000 000 de chaines de caractères de taille 21 (20 octets utiles + '\0'). Je ne sais pas comment optimiser cela pour prendre le moins de mémoire possible avec GCC...

Merci

EDIT: Je viens de tester avec mes 45 000 000 de chaines de 21 octets, en théorie : 922 851Ko de mémoire et en vrai : 1 410 556 Ko, ca fait quand même une différence énorme de 487 704 Ko (476 Mo) !
07/04/2015, 17h13
Bktero

Citation:

Envoyé par sambia39

En complément regardez également du coté Windows
à bientôt

Extraction de la substantifique moelle de ton lien :

Citation:

La fonction malloc alloue un bloc de mémoire d'au moins size octets. Le bloc peut être plus grand que size octets en raison de l'espace requis pour les informations d'alignement et de maintenance.

:plusser:
07/04/2015, 17h27
sambia39

D'accord !
C'est donc normale ?
j'avais des doutes sur mon tout premier poste. Encore un cas qui donne raison au cast de la fonction malloc :aie:
à bientôt
07/04/2015, 17h37
Aspic

Citation:

Envoyé par Bktero

Extraction de la substantifique moelle de ton lien :
:plusser:
La fonction malloc alloue un bloc de mémoire d'au moins size octets. Le bloc peut être plus grand que size octets en raison de l'espace requis pour les informations d'alignement et de maintenance.

Ouais j'avais déjà lu cela donc au final c'est mort, on ne peut rien y faire ? y'a pas une option/flag de GCC pour réduire cela ?

Citation:

Envoyé par sambia39

j'avais des doutes sur mon tout premier poste. Encore un cas qui donne raison au cast de la fonction malloc

Je n'ai pas compris, que l'on cast ou pas le retour de malloc, la quantité mémoire est la même.
07/04/2015, 17h44
sambia39

Quand je parlais du cast c'est par rapport à l'alignement des informations.
extrait de la doc :Pour rétablir un pointeur sur un type autre qu'un void, utilisez un cast de type sur la valeur de retour. L'espace de stockage sur lequel pointe la valeur de retour est obligatoirement aligné pour le stockage de tout type d'objet qui a une spécification d'alignement inférieure ou égale à celui de l'alignement simple.
à bientôt
07/04/2015, 18h37
picodev
Citation:

Envoyé par Aspic

Bonjour à tous,

Voilà plus d'informations :

Je compile mon programme sous GCC version 4.7.2 avec MinGW avec CodeBlocks pour être exact ;)
Je compile en Release avec l'option -O2 pour l'optimisation.

Je ne travaille donc pas avec Visual studio et son compilateur propriétaire.

malloc est une fonction définie par le standard C11 qui doit remplir ces conditions :
- le prototype doit être présent dans stdlib.h et doit être void *malloc(size_t size);
- elle doit allouer de l'espace pour un objet dont la taille est spécifiée par l'argument size, la valeur de l'objet est indéterminée.
- elle retourne soit NULL soit un pointeur valide vers l'espace alloué.
La norme n'indiquera jamais comment la programmer et cela reste à la discrétion de l'implémentation de la libc et non du compilateur ou de l'EDI.

Tu es sous windows et il me semble, mais cela est à vérifier, que MinGW utilise la libc de microsoft (MSVCRT.dll). En ce sens il faut faire avec. Il existe peut-être des moyens pour changer de libc, à vérifier, mais cela me semble dangereux.
07/04/2015, 20h54
grim7reaper

Citation:

Envoyé par Aspic

Je ne sais pas si on peut établir une "loi" en fonction de la taille du bloc mémoire

En connaissant le code, on pourrait éventuellement.
Les allocateurs ont souvent plusieurs stratégies parmi lesquelles ils choisissent selon la taille du bloc demandé (entre autre paramètres).

Citation:

Envoyé par Aspic

Y'a t-il un moyen d'en savoir plus au niveau du code ?

Oui, il faut le trouver (ou trouver sa doc), puis lire.
Est-ce que MinGW vient avec sa propre libc (auquel cas, l’implémentation de malloc sera dedans) ou est-ce qu’il utilise celle fournit par Windows ?

Citation:

Envoyé par Aspic

Ca m'embête un peu sachant que je dois allouer 45 000 000 de chaines de caractères de taille 21 (20 octets utiles + '\0'). Je ne sais pas comment optimiser cela pour prendre le moins de mémoire possible avec GCC...

Comme souvent en informatique, les plus gros gains (de vitesse ou de mémoire) viennent d’un choix judicieux de structures de données et algorithmes adaptés au problème.
Sans plus d’info sur ton cas d’usage, mon premier reflexe serait de t’orienter vers les structures de la famille des trie.
Ces structures sont spécialisées dans le traitement de chaînes de caractères (et peuvent économiser de l’espace en factorisant les parties communes de ces chaînes).
Il existe plusieurs variantes, chacune proposant un compromis entre vitesse, occupation mémoire et facilité d’implémentation.

Une autre approche, si tes chaînes font toutes 21 octets, serait d’utiliser un allocateur optimisé pour ce genre de choses (type memory pool : pas de métadonnées (donc gain d’espace très intéressant pour les petites allocations) et très performant).

Citation:

Envoyé par sambia39

j'avais des doutes sur mon tout premier poste. Encore un cas qui donne raison au cast de la fonction malloc

Nope, caster le type de retour ne changera rien à la quantité de mémoire allouée…
malloc renvoie un void* et n’a pas connaissance de ton cast donc il va toujours renvoyer un pointeur vers de la mémoire correctement alignée pour n’importe quel type.
Pour spécifier l’alignement, il faut passer par aligned_alloc du C11 (ou alors utiliser des fonctions spécifiques à ton système).
08/04/2015, 14h48
Aspic

D'accord je vais regarder où est défini malloc pour MinGW.

Pour les structures en trie, ca à l'air pas mal mais j'ai besoin d'une recherche en O(1) et à mon avis ce n'est pas possible avec les tries. C'est pour cela que j'utilise déjà une table de hashage mais contre partie, ca prend de la place mémoire !! C'est toujours le compromis vitesse/place mémoire inhérent à tout programme informatique ;)

Dans mon cas, je voulais juste essayer de réduire la place mémoire en jouant sur l'alignement ou autre meta données mais si c'est trop galère tant pis, car je ne peux pas sacrifier la vitesse de recherche dans ma table de hash pour gagner de la mémoire, le jeu n'en vaut pas la chandelle dans mon application.

Merci en tout cas pour vos aides :ccool:
08/04/2015, 16h22
grim7reaper

Citation:

Envoyé par Aspic

Pour les structures en trie, ca à l'air pas mal mais j'ai besoin d'une recherche en O(1) et à mon avis ce n'est pas possible avec les tries. C'est pour cela que j'utilise déjà une table de hashage mais contre partie, ca prend de la place mémoire !! C'est toujours le compromis vitesse/place mémoire inhérent à tout programme informatique ;)

O(1) c’est le cas moyen, ça peut vite être moins bon (selon ta fonction de hash (très important d’avoir une bonne fonction de hash), le nombre de collisions et comment tu gères ces collisions).
De plus, c’est pas dit que le trie soit plus lent que ta table de hash.
Ça dépend de l’implémentation de chacune des structures évidemment, mais en théorie :

Citation:

Envoyé par https://en.wikipedia.org/wiki/Trie#As_a_replacement_for_other_data_structures

Looking up data in a trie is faster in the worst case, O(m) time (where m is the length of a search string), compared to an imperfect hash table. An imperfect hash table can have key collisions. A key collision is the hash function mapping of different keys to the same position in a hash table. The worst-case lookup speed in an imperfect hash table is O(N) time, but far more typically is O(1), with O(m) time spent evaluating the hash.

Ok, tu as O(1) dans le plupart des cas, mais il va bien falloir calculer un hash (hop, O(m)) pour faire ton lookup. Avec le trie, tu fais ton lookup au fur et à mesure que tu parcoures ta chaîne (O(m)) et c’est garanti sans collision.
À tester cela dit, ce genre de truc dépend vachement de l’implémentation.

Citation:

Envoyé par Aspic

Dans mon cas, je voulais juste essayer de réduire la place mémoire en jouant sur l'alignement ou autre meta données mais si c'est trop galère tant pis, car je ne peux pas sacrifier la vitesse de recherche dans ma table de hash pour gagner de la mémoire, le jeu n'en vaut pas la chandelle dans mon application.

Je pense que le plus gros gain que tu puisses avoir, si toutes tes chaînes font 21 octets, c’est d’utiliser un memory pool. Tu devrais gagner en perf (allocation/libération plus rapide + meilleure localité spatiale) et en espace (pas de métadonnées).

Citation:

Envoyé par Aspic

Merci en tout cas pour vos aides :ccool:

De rien :)

C'est vrai que l'histoire de la memory pool a l'air pas mal, je me suis renseigné et ça semble correspondre à mes besoins puisque mes chaines font bien toutes 21 octets.

Par contre, j'ai trouvé pas mal d'implémentations en C++ :( et vu que je suis en C, je dois en coder une et ça risque de prendre du temps vu que je ne maitrise pas très bien ce concept...

Cependant, en fouillant bien j'ai trouvé un code en C qui a l'air pas trop mal mais je ne sais pas ce qu'il vaut :

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
/*  mempool.c
**
**  A simple fast memory allocation package.
**
**  By Steve Hill in Graphics Gems III, David Kirk (ed.),
**    Academic Press, Boston, MA, 1992
**
**  Modified by Lew Rossman, 8/13/94.
**
**  AllocInit()     - create an alloc pool, returns the old pool handle
**  Alloc()         - allocate memory
**  AllocReset()    - reset the current pool
**  AllocSetPool()  - set the current pool
**  AllocFree()     - free the memory used by the current pool.
**
*/
 
#include <stdlib.h>
#include <malloc.h>
#include "mempool.h"
 
/*
**  ALLOC_BLOCK_SIZE - adjust this size to suit your installation - it
**  should be reasonably large otherwise you will be mallocing a lot.
*/
 
#define ALLOC_BLOCK_SIZE   64000       /*(62*1024)*/
 
/*
**  alloc_hdr_t - Header for each block of memory.
*/
 
typedef struct alloc_hdr_s
{
    struct alloc_hdr_s *next;   /* Next Block          */
    char               *block,  /* Start of block      */
                       *free,   /* Next free in block  */
                       *end;    /* block + block size  */
}  alloc_hdr_t;
 
/*
**  alloc_root_t - Header for the whole pool.
*/
 
typedef struct alloc_root_s
{
    alloc_hdr_t *first,    /* First header in pool */
                *current;  /* Current header       */
}  alloc_root_t;
 
/*
**  root - Pointer to the current pool.
*/
 
static alloc_root_t *root;
 
 
/*
**  AllocHdr()
**
**  Private routine to allocate a header and memory block.
*/
 
static alloc_hdr_t *AllocHdr(void);
 
static alloc_hdr_t * AllocHdr()
{
    alloc_hdr_t     *hdr;
    char            *block;
 
    block = (char *) malloc(ALLOC_BLOCK_SIZE);
    hdr   = (alloc_hdr_t *) malloc(sizeof(alloc_hdr_t));
 
    if (hdr == NULL || block == NULL) return(NULL);
    hdr->block = block;
    hdr->free  = block;
    hdr->next  = NULL;
    hdr->end   = block + ALLOC_BLOCK_SIZE;
 
    return(hdr);
}
 
 
/*
**  AllocInit()
**
**  Create a new memory pool with one block.
**  Returns pointer to the new pool.
*/
 
alloc_handle_t * AllocInit()
{
    alloc_handle_t *newpool;
 
    root = (alloc_root_t *) malloc(sizeof(alloc_root_t));
    if (root == NULL) return(NULL);
    if ( (root->first = AllocHdr()) == NULL) return(NULL);
    root->current = root->first;
    newpool = (alloc_handle_t *) root;
    return(newpool);
}
 
 
/*
**  Alloc()
**
**  Use as a direct replacement for malloc().  Allocates
**  memory from the current pool.
*/
 
char * Alloc(long size)
{
    alloc_hdr_t  *hdr = root->current;
    char         *ptr;
 
    /*
    **  Align to 4 byte boundary - should be ok for most machines.
    **  Change this if your machine has weird alignment requirements.
    */
    size = (size + 3) & 0xfffffffc;
 
    ptr = hdr->free;
    hdr->free += size;
 
    /* Check if the current block is exhausted. */
 
    if (hdr->free >= hdr->end)
    {
        /* Is the next block already allocated? */
 
        if (hdr->next != NULL)
        {
            /* re-use block */
            hdr->next->free = hdr->next->block;
            root->current = hdr->next;
        }
        else
        {
            /* extend the pool with a new block */
            if ( (hdr->next = AllocHdr()) == NULL) return(NULL);
            root->current = hdr->next;
        }
 
        /* set ptr to the first location in the next block */
        ptr = root->current->free;
        root->current->free += size;
    }
 
    /* Return pointer to allocated memory. */
 
    return(ptr);
}
 
 
/*
**  AllocSetPool()
**
**  Change the current pool.  Return the old pool.
*/
 
alloc_handle_t * AllocSetPool(alloc_handle_t *newpool)
{
    alloc_handle_t *old = (alloc_handle_t *) root;
    root = (alloc_root_t *) newpool;
    return(old);
}
 
 
/*
**  AllocReset()
**
**  Reset the current pool for re-use.  No memory is freed,
**  so this is very fast.
*/
 
void  AllocReset()
{
    root->current = root->first;
    root->current->free = root->current->block;
}
 
 
/*
**  AllocFreePool()
**
**  Free the memory used by the current pool.
**  Don't use where AllocReset() could be used.
*/
 
void  AllocFreePool()
{
    alloc_hdr_t  *tmp,
                 *hdr = root->first;
 
    while (hdr != NULL)
    {
        tmp = hdr->next;
        free((char *) hdr->block);
        free((char *) hdr);
        hdr = tmp;
    }
    free((char *) root);
    root = NULL;
}

Si quelqu'un peut me dire ce que vaut ce code ?

Merci :)

Citation:

Envoyé par Aspic

En fait, comme tes blocs ont une taille constante et que tu sais à l‘avance de combien de blocs tu vas avoir besoins (45 000 000), l’implémentation est enfantine : une liste simplement chaînée peut faire l’affaire.

Un exemple de code (fait à la va-vite, sur un coin de table entre deux portes, donc il y a potentiellement des erreurs ridicules…)

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
 
#include <assert.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
 
/* A block of memory for 20-bytes string (+ nul byte). */
typedef struct mem_block {
    struct mem_block* next;
    char data[21];
} mem_block;
 
/* A memory pool. */
typedef struct mem_pool {
    mem_block* pool;
    mem_block* free_list;
} mem_pool;
 
void init_pool(mem_pool* pool, size_t nb_block);
void* alloc(mem_pool* pool);
void dealloc(mem_pool* pool, void* data);
void destroy_pool(mem_pool* pool);
 
/* Create a pool of `nb_block` objects. */
void init_pool(mem_pool* pool, size_t nb_block)
{
    mem_block* blk;
    mem_block* end;
    mem_block* last;
 
    assert (nb_block > 0);
    /* Allocate the pool. */
    pool->pool = malloc(nb_block * sizeof(mem_block));
    pool->free_list = pool->pool;
    end  = pool->free_list + nb_block;
    last = end - 1;
 
    /* Put all the blocks in the free list. */
    for (blk = pool->free_list; blk < last; ++blk) {
        blk->next = blk + 1;
    }
    last->next = NULL;
}
 
/* Return memory for one object, or NULL if the pool is exhausted. */
void* alloc(mem_pool *pool)
{
    mem_block* blk;
 
    assert (pool);
    /* Pool exhausted. */
    if (pool->free_list == NULL) {
        return NULL;
    }
    /* Take the first free block. */
    blk = pool->free_list;
    pool->free_list = pool->free_list->next;
 
    return blk->data;
}
 
/* Free one object. */
void dealloc(mem_pool *pool, void* data)
{
    assert (pool);
    if (data) {
        /* Add the block in the free list. */
        mem_block* blk = ((mem_block*)((char*)(data) - offsetof(mem_block, data)));
 
        blk->next = pool->free_list;
        pool->free_list = blk;
    }
}
/* Destroy the pool and free the underlying memory. */
void destroy_pool(mem_pool* pool)
{
    assert (pool);
    if (pool->pool != NULL) {
        /* Free the whole pool. */
        free(pool->pool);
        pool->pool = NULL;
        pool->free_list = NULL;
    }
}
 
/* Little test. */
int main(void)
{
    mem_pool pool;
    char* s1;
    char* s2;
    char* s3;
    char* s4;
 
    /* Create a pool for 3 strings */
    init_pool(&pool, 3);
 
    /* The first 3 allocations should success. */
    s1 = alloc(&pool);
    s2 = alloc(&pool);
    s3 = alloc(&pool);
    assert (s1 != NULL);
    assert (s2 != NULL);
    assert (s3 != NULL);
    strcpy(s1, "Hello");
    strcpy(s2, "World");
    strcpy(s3, "!");
    assert (strcmp(s1, "Hello") == 0);
    assert (strcmp(s2, "World") == 0);
    assert (strcmp(s3, "!") == 0);
 
    /* The 4th allocation should fail. */
    s4 = alloc(&pool);
    assert (s4 == NULL);
 
    /* Free s3, the allocation of s4 is now possible. */
    dealloc(&pool, s3);
    s4 = alloc(&pool);
    assert (s4 != NULL);
    strcpy(s4, "?");
    assert (strcmp(s4, "?") == 0);
 
    /* Wipe the whole pool, don't need to wipe string by string. */
    destroy_pool(&pool);
    assert (pool.pool == NULL);
    assert (pool.free_list== NULL);
 
    return 0;
}

Alors bien sûr, c’est pas utilisable comme ça (il faudrait au moins rajouter une gestion des erreurs…), mais ça donne l’idée.
Note : on pourrait avoir un truc encore mieux (moins de conso mémoire, plus de localité) en utiliser un bitset au lieu d’une liste chaînée pour les blocs libres, mais ça demande un petit peu plus de code.

10/04/2015, 12h56
picodev

Si on sait qu'il y a exactement 45000000 de chaînes de longueur 21 autant directement déclarer un tableau statique ... l'espace sera contigu sans métadonnées et la gestion simplifiée. Si on veut gagner de l'espace et que ces chaînes sont à 0 terminal on peut carrément oublier le 0 terminal et utiliser les versions à longueur constante des primitives de manipulations des chaînes, par exemple.

Mais bon sans savoir ce que tu fais de ces chaînes, ni ce qu'elles représentent difficile de t'aiguiller plus.
10/04/2015, 13h46
grim7reaper

Citation:

Envoyé par picodev

Si on sait qu'il y a exactement 45000000 de chaînes de longueur 21 autant directement déclarer un tableau statique

Si les chaînes sont présentent pendant tout la durée de vie du programmes, c’est en effet une solution

Citation:

Mais bon sans savoir ce que tu fais de ces chaînes, ni ce qu'elles représentent difficile de t'aiguiller plus.

Yep, on est d’accord.
11/04/2015, 13h51
Aspic

Ouais le tableau statique j'y ai pensé et vu que j'en besoin sur la durée de vie du programme, c'est vrai que c'est une solution ;)
Mais l'histoire de la memory pool me plait bien avec en plus la possibilité de la libérer au runtime.
En fait ce sont des chaines qui contiennent un hash de positions appelées "deadlock" dans le cas de résolution du jeu Sokoban. Le principe est de faire une recherche parmi toutes ces chaines et s'il y a une correspondance alors on a un "deadlock" et la position en question est ignorée des états du graphe. Cette opération doit être très très rapide c'est pour cela que j'avais envisagé la table de hachage pour stocker ces chaines.

Merci à vous pour vos aides :)
11/04/2015, 19h45
Obsidian

Citation:

Envoyé par picodev

Si on sait qu'il y a exactement 45000000 de chaînes de longueur 21 autant directement déclarer un tableau statique ... l'espace sera contigu sans métadonnées et la gestion simplifiée. Si on veut gagner de l'espace et que ces chaînes sont à 0 terminal on peut carrément oublier le 0 terminal et utiliser les versions à longueur constante des primitives de manipulations des chaînes, par exemple.

Citation:

Envoyé par grim7reaper

Si les chaînes sont présentent pendant tout la durée de vie du programmes, c’est en effet une solution

C'est aussi ce que je voulais suggérer, en effet, mais à bien y relire, 45000000 chaînes de 21 octets chacune, ça occupe environ 900 Mio. Hors de question de déclarer cela dans la pile, donc. En temps normal, un simple malloc() dans un pointeur suffirait pour indexer cela comme un tableau, mais une quantité de données qui approche du gigaoctet, c'est quand même assez audacieux de vouloir la faire tenir en mémoire. Surtout qu'à ce stade, la moindre modification prend des proportions dramatiques. Rien que stocker les index des différentes chaînes risque d'être un vrai travail à lui seul.

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