IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C Discussion :

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


Sujet :

C

  1. #1
    Expert confirmé
    Avatar de Aspic
    Homme Profil pro
    Étudiant
    Inscrit en
    août 2005
    Messages
    3 905
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hauts de Seine (Île de France)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Électronique et micro-électronique

    Informations forums :
    Inscription : août 2005
    Messages : 3 905
    Points : 4 453
    Points
    4 453
    Par défaut Malloc semble allouer plus de mémoire que nécessaire
    Bonjour,

    Je souhaite essayer de comprendre comment la mémoire est allouée par malloc en C :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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
    Qui ne tente rien n'a rien !
    Ce qui ne nous tue pas nous rends plus fort !!
    Mon projet ZELDA en C++/Allegro
    http://www.tutoworld.com - Le Forum -
    Mes ressources Dotnet (cours, sources, tutos)
    --------------------------------------------
    + + =

    Ne pas oublier le Tag !

  2. #2
    Membre expérimenté
    Avatar de sambia39
    Homme Profil pro
    No Comment
    Inscrit en
    mai 2010
    Messages
    530
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Loiret (Centre)

    Informations professionnelles :
    Activité : No Comment
    Secteur : High Tech - Matériel informatique

    Informations forums :
    Inscription : mai 2010
    Messages : 530
    Points : 1 658
    Points
    1 658
    Par défaut
    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 ?
    y a-t-il pas écrasement d'adresse d'allocation à chacun itération ?

    Citation Envoyé par Aspic Voir le message
    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 : 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
     
    #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
    Celui qui peut, agit. Celui qui ne peut pas, enseigne.
    Il y a deux sortes de savants: les spécialistes, qui connaissent tout sur rien,
    et les philosophes, qui ne connaissent rien sur tout.
    George Bernard Shaw

  3. #3
    Membre émérite
    Homme Profil pro
    sans emploi
    Inscrit en
    janvier 2014
    Messages
    539
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 49
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : sans emploi
    Secteur : Conseil

    Informations forums :
    Inscription : janvier 2014
    Messages : 539
    Points : 2 601
    Points
    2 601
    Par défaut
    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.

  4. #4
    Membre expérimenté
    Avatar de sambia39
    Homme Profil pro
    No Comment
    Inscrit en
    mai 2010
    Messages
    530
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Loiret (Centre)

    Informations professionnelles :
    Activité : No Comment
    Secteur : High Tech - Matériel informatique

    Informations forums :
    Inscription : mai 2010
    Messages : 530
    Points : 1 658
    Points
    1 658
    Par défaut
    En complément regardez également du coté Windows
    à bientôt
    Celui qui peut, agit. Celui qui ne peut pas, enseigne.
    Il y a deux sortes de savants: les spécialistes, qui connaissent tout sur rien,
    et les philosophes, qui ne connaissent rien sur tout.
    George Bernard Shaw

  5. #5
    Membre éclairé
    Inscrit en
    juillet 2012
    Messages
    231
    Détails du profil
    Informations forums :
    Inscription : juillet 2012
    Messages : 231
    Points : 869
    Points
    869
    Par défaut
    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.

  6. #6
    Expert confirmé
    Avatar de Aspic
    Homme Profil pro
    Étudiant
    Inscrit en
    août 2005
    Messages
    3 905
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hauts de Seine (Île de France)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Électronique et micro-électronique

    Informations forums :
    Inscription : août 2005
    Messages : 3 905
    Points : 4 453
    Points
    4 453
    Par défaut
    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) !
    Qui ne tente rien n'a rien !
    Ce qui ne nous tue pas nous rends plus fort !!
    Mon projet ZELDA en C++/Allegro
    http://www.tutoworld.com - Le Forum -
    Mes ressources Dotnet (cours, sources, tutos)
    --------------------------------------------
    + + =

    Ne pas oublier le Tag !

  7. #7
    Modérateur

    Avatar de Bktero
    Homme Profil pro
    Développeur en systèmes embarqués
    Inscrit en
    juin 2009
    Messages
    4 382
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 34
    Localisation : France, Loire Atlantique (Pays de la Loire)

    Informations professionnelles :
    Activité : Développeur en systèmes embarqués

    Informations forums :
    Inscription : juin 2009
    Messages : 4 382
    Points : 13 199
    Points
    13 199
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par sambia39 Voir le message
    En complément regardez également du coté Windows
    à bientôt
    Extraction de la substantifique moelle de ton lien :
    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.

  8. #8
    Membre expérimenté
    Avatar de sambia39
    Homme Profil pro
    No Comment
    Inscrit en
    mai 2010
    Messages
    530
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Loiret (Centre)

    Informations professionnelles :
    Activité : No Comment
    Secteur : High Tech - Matériel informatique

    Informations forums :
    Inscription : mai 2010
    Messages : 530
    Points : 1 658
    Points
    1 658
    Par défaut
    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
    à bientôt
    Celui qui peut, agit. Celui qui ne peut pas, enseigne.
    Il y a deux sortes de savants: les spécialistes, qui connaissent tout sur rien,
    et les philosophes, qui ne connaissent rien sur tout.
    George Bernard Shaw

  9. #9
    Expert confirmé
    Avatar de Aspic
    Homme Profil pro
    Étudiant
    Inscrit en
    août 2005
    Messages
    3 905
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hauts de Seine (Île de France)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Électronique et micro-électronique

    Informations forums :
    Inscription : août 2005
    Messages : 3 905
    Points : 4 453
    Points
    4 453
    Par défaut
    Citation Envoyé par Bktero Voir le message
    Extraction de la substantifique moelle de ton lien :

    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.
    Qui ne tente rien n'a rien !
    Ce qui ne nous tue pas nous rends plus fort !!
    Mon projet ZELDA en C++/Allegro
    http://www.tutoworld.com - Le Forum -
    Mes ressources Dotnet (cours, sources, tutos)
    --------------------------------------------
    + + =

    Ne pas oublier le Tag !

  10. #10
    Membre expérimenté
    Avatar de sambia39
    Homme Profil pro
    No Comment
    Inscrit en
    mai 2010
    Messages
    530
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Loiret (Centre)

    Informations professionnelles :
    Activité : No Comment
    Secteur : High Tech - Matériel informatique

    Informations forums :
    Inscription : mai 2010
    Messages : 530
    Points : 1 658
    Points
    1 658
    Par défaut
    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
    Celui qui peut, agit. Celui qui ne peut pas, enseigne.
    Il y a deux sortes de savants: les spécialistes, qui connaissent tout sur rien,
    et les philosophes, qui ne connaissent rien sur tout.
    George Bernard Shaw

  11. #11
    Membre émérite
    Homme Profil pro
    sans emploi
    Inscrit en
    janvier 2014
    Messages
    539
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 49
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : sans emploi
    Secteur : Conseil

    Informations forums :
    Inscription : janvier 2014
    Messages : 539
    Points : 2 601
    Points
    2 601
    Par défaut
    Citation Envoyé par Aspic Voir le message
    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.

  12. #12
    Membre éclairé
    Inscrit en
    juillet 2012
    Messages
    231
    Détails du profil
    Informations forums :
    Inscription : juillet 2012
    Messages : 231
    Points : 869
    Points
    869
    Par défaut
    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).

  13. #13
    Expert confirmé
    Avatar de Aspic
    Homme Profil pro
    Étudiant
    Inscrit en
    août 2005
    Messages
    3 905
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hauts de Seine (Île de France)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Électronique et micro-électronique

    Informations forums :
    Inscription : août 2005
    Messages : 3 905
    Points : 4 453
    Points
    4 453
    Par défaut
    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
    Qui ne tente rien n'a rien !
    Ce qui ne nous tue pas nous rends plus fort !!
    Mon projet ZELDA en C++/Allegro
    http://www.tutoworld.com - Le Forum -
    Mes ressources Dotnet (cours, sources, tutos)
    --------------------------------------------
    + + =

    Ne pas oublier le Tag !

  14. #14
    Membre éclairé
    Inscrit en
    juillet 2012
    Messages
    231
    Détails du profil
    Informations forums :
    Inscription : juillet 2012
    Messages : 231
    Points : 869
    Points
    869
    Par défaut
    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
    De rien

  15. #15
    Expert confirmé
    Avatar de Aspic
    Homme Profil pro
    Étudiant
    Inscrit en
    août 2005
    Messages
    3 905
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hauts de Seine (Île de France)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Électronique et micro-électronique

    Informations forums :
    Inscription : août 2005
    Messages : 3 905
    Points : 4 453
    Points
    4 453
    Par défaut
    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 : 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
    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
    Qui ne tente rien n'a rien !
    Ce qui ne nous tue pas nous rends plus fort !!
    Mon projet ZELDA en C++/Allegro
    http://www.tutoworld.com - Le Forum -
    Mes ressources Dotnet (cours, sources, tutos)
    --------------------------------------------
    + + =

    Ne pas oublier le Tag !

  16. #16
    Membre éclairé
    Inscrit en
    juillet 2012
    Messages
    231
    Détails du profil
    Informations forums :
    Inscription : juillet 2012
    Messages : 231
    Points : 869
    Points
    869
    Par défaut
    Citation Envoyé par Aspic
    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...
    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 : 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
    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.

  17. #17
    Membre émérite
    Homme Profil pro
    sans emploi
    Inscrit en
    janvier 2014
    Messages
    539
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 49
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : sans emploi
    Secteur : Conseil

    Informations forums :
    Inscription : janvier 2014
    Messages : 539
    Points : 2 601
    Points
    2 601
    Par défaut
    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.

  18. #18
    Membre éclairé
    Inscrit en
    juillet 2012
    Messages
    231
    Détails du profil
    Informations forums :
    Inscription : juillet 2012
    Messages : 231
    Points : 869
    Points
    869
    Par défaut
    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

    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.

  19. #19
    Expert confirmé
    Avatar de Aspic
    Homme Profil pro
    Étudiant
    Inscrit en
    août 2005
    Messages
    3 905
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hauts de Seine (Île de France)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Électronique et micro-électronique

    Informations forums :
    Inscription : août 2005
    Messages : 3 905
    Points : 4 453
    Points
    4 453
    Par défaut
    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
    Qui ne tente rien n'a rien !
    Ce qui ne nous tue pas nous rends plus fort !!
    Mon projet ZELDA en C++/Allegro
    http://www.tutoworld.com - Le Forum -
    Mes ressources Dotnet (cours, sources, tutos)
    --------------------------------------------
    + + =

    Ne pas oublier le Tag !

  20. #20
    Modérateur
    Avatar de Obsidian
    Homme Profil pro
    Développeur en systèmes embarqués
    Inscrit en
    septembre 2007
    Messages
    7 280
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 45
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Développeur en systèmes embarqués
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : septembre 2007
    Messages : 7 280
    Points : 23 334
    Points
    23 334
    Par défaut
    Citation Envoyé par picodev Voir le message
    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 Voir le message
    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.

+ Répondre à la discussion
Cette discussion est résolue.
Page 1 sur 2 12 DernièreDernière

Discussions similaires

  1. Réponses: 126
    Dernier message: 11/03/2010, 08h12
  2. Allouer plus de mémoire pour les mises à jour.
    Par Empty_body dans le forum PostgreSQL
    Réponses: 0
    Dernier message: 14/03/2008, 15h29
  3. [C#]Comment allouer plus de mémoire à mon prog
    Par Yotho dans le forum Windows Forms
    Réponses: 2
    Dernier message: 04/04/2007, 11h39
  4. allouer plus de mémoire
    Par fontaigo dans le forum Eclipse Java
    Réponses: 5
    Dernier message: 05/02/2007, 16h54
  5. [DOS][Mémoire] Allouer plus de 64 Ko
    Par Pascool dans le forum C
    Réponses: 3
    Dernier message: 11/02/2003, 10h26

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo