.. _11-allocdyn: Allocation dynamique ==================== L'exécution d'un programme nécessite l'utilisation de la mémoire vive de la machine. Comme on l'a déjà vu dans le chapitre :ref:`07-fonctions` cette dernière peut être décomposée (de façon simplifiée) en plusieurs zones (ou segments) comme le montre la figure ci dessous. | .. image:: ../images/07-memory-layout.drawio.png :scale: 80% :align: center | Les zones mémoire utilisées pour manipuler les variables sont : - la *stack* placée dans les adresses hautes de la mémoire et allouée en progressant vers les adresses basses ; - et le *heap* placée dans les adresses plus basses de la mémoire et allouée en progressant vers les adresses hautes ; Les programmes que l'on a écrit jusqu'à présent ont utilisé 2 zones de mémoire : - la mémoire statique, qui contient le code source de notre programme et les variables globales ; - et la *stack*. La *stack* ---------- Jusqu'à présent, la mémoire nécessaire à l'exécution des programmes a été allouée statiquement à la compilation (pour les variables globales), ou automatiquement durant l'exécution du programme, puis libérée à la fin de l'exécution du programme. La mémoire nécessaire était réservée dans une zone appelée la pile ou *stack*. La *stack* est une zone mémoire intéressante pour les raisons suivantes : - elle est gérée par le CPU ; - la réservation de la mémoire est faite automatiquement ; - la mémoire est automatiquement libérée lorsqu'on sort de la fonction. mais elle a aussi des inconvénients : - le compilateur a besoin de connaître l'encombrement mémoire avant l'exécution du programme. Ceci a généralement pour conséquence de surdimensionner la place réservée ; - la taille est limitée par le système d'exploitation (généralement 8 Mb). On obtient la taille (en Kb) avec :: $ ulimit -s 8192 Pour illustrer son fonctionnement, on considère le programme suivant. .. code-block:: c #include int addOne(int x) { return x+1; } int main(){ int x = 3; printf("before main(), x = %d\n", x); x = addOne(x); printf("after main(), x = %d\n", x); } La mémoire est utilisée de la façon suivante : - le code machine est placé dans la partie basse de la mémoire ; - la fonction :func:`addOne` et sa variable locale ``x`` sont placées dans la *stack* ; - la fonction :func:`main` et sa variable locale ``x`` sont placées dans la *stack* ; .. image:: ../images/addone-stack.png On compile et on exécute :: $ gcc -std=c99 -Wall -Wextra addone.c -o addone $ ./addone before main(), x = 3 after main(), x = 4 Le programme utilise séquentiellement la *stack* de la façon suivante. - a : avant l'exécution la *stack* est vide ; - b : une zone est réservée lorsque la fonction :func:`main` est lancée. La variable locale ``x`` y est déclarée et initialisée ; - c : une autre zone est réservée lors de l'appel à :func:`addOne`. La variable locale ``x`` y est déclarée et initialisée ; - d : cette zone est libérée après l'instruction ``return`` de :func:`addOne`. La variable locale ``x`` est détruite ; - e : la *stack* est totalement libérée après l'instruction ``return`` de :func:`main`. La variable locale ``x`` est détruite . .. image:: ../images/stack.png :width: 50% :align: center | L'étape (d) explique que les variables locales à une fonction secondaire sont détruites lorsque l'on sort de la fonction, et par conséquent ne sont plus accessibles. Le recours à la *stack* imposant de fortes contraintes, C permet l'utilisation d'une zone mémoire plus étendue : le tas ou *heap*. Le *heap* --------- Contrairement à la *stack*, le *heap* possède les caractéristiques suivantes: #. sa taille n'est pas fixée a priori. Elle n'est limitée que par la taille de la mémoire physique de la machine ; #. l'allocation (et la désallocation) doit se faire manuellement ; #. les variables doivent être manipulées avec des pointeurs. Les langages modernes tels que Python gèrent automatiquement l'allocation et la désallocation mémoire, avec un dispositif appelé *garbage collector*. L'interpréteur contrôle cycliquement l'utilisation de la mémoire et libère les zones qui ne sont plus utilisées. La gestion manuelle de la mémoire est une des forces, mais également une des difficultés de la programmation en langage C : - on évite le recours au *garbage collector* de Python qui est (un peu) coûteux en temps de calcul ; - mais il faut toujours penser à libérer la mémoire non utilisé sous peine de fuites mémoire (*memory leak*) qui affectent tout le système d'exploitation. L'allocation de mémoire ....................... L'allocation de mémoire est réalisée avec l'une ou l'autre des fonctions suivantes: - :func:`malloc` réserve de la mémoire sans initialisation ; - :func:`calloc` réserve de la mémoire avec initialisation à 0. Le prototype de chacune de ces deux fonctions est déclaré dans :file:``. Les prototypes (simplifiés) : .. code-block:: c void* malloc( int memorySize ); void* calloc( int elementCount, int elementSize ); Chacune des deux fonctions retourne un type ``void*`` qui est un pointeur sur n'importe quel type. Ca fonctionnera donc pour des pointeurs vers des zones mémoire contenant des ``char``, des ``int``, des ``double``, etc. Les deux fonctions poursuivent le même objectif mais différent dans la façon de dimensionner la mémoire à réserver : - :func:`malloc` nécessite en argument **la taille totale** du bloc mémoire à réserver ; - :func:`calloc` nécessite en argument **le nombre d'éléments** et **la taille individuelle** de chacun des éléments. Un exemple d'appel pour réserver de la mémoire pour un tableau de 10 entiers avec :func:`malloc` : .. code-block:: c int *ptr; ptr = malloc(10 * sizeof(int)); La même opération avec :func:`calloc` : .. code-block:: c int *ptr; ptr = calloc(10, sizeof(int)); Si le système d'exploitation dispose de mémoire disponible :func:`malloc` et :func:`calloc` retournent l'adresse de début du bloc mémoire réservé sous forme de pointeur. S'il n'y a plus de mémoire disponible, chacune des deux fonctions retourne ``NULL``. Il conviendra donc de contrôler le bon déroulement de l'opération de réservation de mémoire en testant la valeur de retour : .. code-block:: c if (ptr == NULL) { printf("Memory allocation failed, exiting...\n"); exit(-1); } Un premier exemple pour réserver de la mémoire pour un tableau d'entier : .. code-block:: c :linenos: // malloc1.c #include #include #define SIZE 5 int main() { int *ptr; ptr = malloc(SIZE * sizeof(int)); if (ptr == NULL) { printf("Memory allocation failed, exiting...\n"); exit(-1); } printf("Memory allocation succeed, continuing...\n"); // Initialisation for (int i = 0; i < SIZE; i++) *(ptr + i) = rand() % 100; // Display for (int i = 0; i < SIZE; i++) printf("%p : %d\n", ptr+i, *(ptr+i)); return 0; } La compilation et l'exécution de ce programme :: $ gcc -std=c99 -Wall -Wextra malloc1.c -o malloc1 $ ./malloc1 Memory allocation succeed, continuing... 0x7fffded032a0 : 83 0x7fffded032a4 : 86 0x7fffded032a8 : 77 0x7fffded032ac : 15 0x7fffded032b0 : 93 .. image:: ../images/malloc1.png :width: 50% .. quiz:: quizz-01 :title: Allocation dynamique - Le bloc mémoire réservé comporte :quiz:`{"type":"FB","answer":"5", "size":5}` éléments - Le bloc mémoire réservé comporte :quiz:`{"type":"FB","answer":"20", "size":5}` octets - Le bloc mémoire réservé débute à l'adresse :quiz:`{"type":"FB","answer":"d032a0", "size":5}` - Le bloc mémoire réservé se termine à l'adresse :quiz:`{"type":"FB","answer":"d032b3", "size":5}` - Le pointeur ptr a pour valeur :quiz:`{"type":"FB","answer":"d032a0", "size":5}` - Le pointeur ptr a pour adresse :quiz:`{"type":"FB","answer":"ab6550", "size":5}` - La valeur du 3ième élément du tableau est :quiz:`{"type":"FB","answer":"77", "size":5}` - Avec l'opérateur d'indexation, la valeur du 3ième élément du tableau s'obtient avec :quiz:`{"type":"FB","answer":"ptr[2]", "size":5}` - Avec l'opérateur d'indirection, la valeur du 3ième élément du tableau s'obtient avec :quiz:`{"type":"FB","answer":"*(ptr+2)", "size":5}` .. admonition:: A expérimenter Remplacer ``SIZE`` sur la ligne 12 par une valeur supérieure à la taille de la mémoire vive de votre machine. Compiler et exécuter. Que se passe t-il ? Libération de la mémoire ........................ La mémoire réservée avec :func:`malloc` ou :func:`calloc` n'est pas automatiquement libérée. C'est de la responsabilité du programmeur de le faire. Pour cela on utilise la fonction :func:`free` dont le prototype est déclaré dans :file:``. Le prototype (simplifié) : .. code-block:: c void free(void *ptr) La fonction prend en argument un pointeur de n'importe quel type, libère la mémoire correspondante et ne retourne rien. L'exemple précédent ne met pas en oeuvre cette opération, ce qui n'est pas une bonne pratique. A la fin du programme, un programmeur consciencieux aurait écrit : .. code-block:: c free(ptr); L'impact était cependant limité puisque la mémoire est de toutes façons restituée au système d'exploitation lorsque le programme se termine. Exercice d'application ---------------------- Dans un précédent :ref:`exercice de manipulation de tableaux `, les opérations ont été faites sur des variables stockées dans la *stack*. Ceci est parfaitement fonctionnel pour des tableaux de taille réduite mais poserait des problèmes de mémoire pour des tableaux de plus grande taille. Adapter la fonction :func:`main` ................................ Il faut modifier la fonction :func:`main` écrite précédemment en utilisant l'allocation dynamique. .. admonition:: Information Grâce à l'équivalence tableau-pointeur, les fonctions secondaires n'ont pas à être modifiées. S'assurer que la signature de :func:`main` permet l'utilisation des arguments passés en ligne de commande. On utilisera deux arguments : - la taille du tableau à générer ; - la borne haute de l'intervalle dans lequel on va choisir aléatoirement les données pour le remplissage. Contrôler le nombre d'arguments ``argc`` passés sur la ligne de commande. S'il n'est pas conforme, afficher un message d'aide, puis interrompre le programme. Un exemple:: $ ./tab-heap 10000 20000 30000 Error : Invalid number of arguments Usage : $ ./tab-heap size ubound build a random array of integers and return basic stats size : size of the array ubound : values randomly choosen between 0 and ubound-1 En observant la signature de :func:`main` décrite dans le paragraphe :ref:`09-passage-arguments-ligne-commande`, quel est le type des arguments récupérés à partir de la ligne de commande ? Les fonctions de conversion n'ont pas été abordées dans ce cours. Utiliser `cette référence `_ pour identifier la fonction qui permet de convertir un argument de la ligne de commande en entier. Les arguments seront affecté à - une variable ``size`` pour la taille du tableau ; - et une variable ``ubound`` pour la borne haute des éléments choisis aléatoirement. Déclarer un pointeur ``p`` vers un tableau d'entiers. Réserver la mémoire nécessaire pour y stocker ``size`` éléments. Contrôler que la réservation de la mémoire a été correctement effectuée, sinon quitter le programme. Initialiser le générateur de nombres aléatoires avec :func:`srand` pour obtenir des tirages différents à chaque exécution. Initialiser le tableau avec des valeurs aléatoires comprises entre ``0`` et ``ubound-1``. .. admonition:: Information Grâce à l'équivalence tableau-pointeur, l'appel des fonctions précédentes doit se faire sans modification. .. warning:: Pour certaines combinaisons de ``size`` et ``ubound``, la fonction :func:`sum` peut produire des entiers qui dépassent la limite (relire la note sur les :ref:`long int `). Pour éviter ce problème, il est nécessaire de modifier la fonction :func:`sum` pour qu'elle utilise et retourne un ``long int``. Dans la fonction :func:`main`, il ne faudra pas oublier de modifier la place réservée dans la chaine de formatage de :func:`printf` pour afficher un ``long int``. Ne pas oublier de libérer la mémoire lorsque l'on n'a plus besoin du tableau. Comptage ........ Ecrire une fonction :func:`compte` de signature ``int compte(int t[], int size, int lowest, int highest)`` qui retourne le nombre d'éléments de ``t`` compris entre ``lowest`` et ``highest``. Utiliser cette fonction pour afficher le nombre d'éléments de ``t`` dans chacun des déciles. Exécution ......... Tester le bon fonctionnement sur un tableau de taille réduite. Puis tester le fonctionnement sur un tableau de taille 1000, 10000, 10000, 100000. Utiliser la commande :command:`time` aperçue lors du :ref:`comptage des nombres premiers ` pour mesurer le temps d'exécution. Quelques exemples d'exécution sur une machine Intel(R) Core(TM) i7-6700 CPU @ 3.40GHz, 16 Go de RAM, Windows 10 64 bits, WSL2/Ubuntu:: $ time ./tab-heap 10000000 5000000 minimum : 0 maximum : 4999999 somme : 24989041416836 moyenne : 2498904.141684 2821704 valeurs de t comprises entre 3587687 et 6534492 real 0m0.283s user 0m0.234s sys 0m0.063s $ time ./tab-heap 100000000 50000000 minimum : 0 maximum : 49999999 somme : 2497004259257321 moyenne : 24970042.592573 23168126 valeurs de t comprises entre 38369048 et 62675080 real 0m2.686s user 0m2.375s sys 0m0.313s $ time ./tab-heap 1000000000 500000000 minimum : 0 maximum : 499999999 somme : 237895079061676856 moyenne : 237895079.061677 191481773 valeurs de t comprises entre 397195504 et 616803879 real 0m26.801s user 0m23.250s sys 0m3.547s