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 Les 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.

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.

#include <stdio.h>

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 addOne() et sa variable locale x sont placées dans la stack ;
la fonction main() et sa variable locale x sont placées dans la stack ;

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 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 à 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 addOne(). La variable locale x est détruite ;
e : la stack est totalement libérée après l’instruction return de main(). La variable locale x est détruite .

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:

malloc() réserve de la mémoire sans initialisation ;
calloc() réserve de la mémoire avec initialisation à 0.

Le prototype de chacune de ces deux fonctions est déclaré dans <stdlib.h>. Les prototypes (simplifiés) :

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 :

malloc() nécessite en argument la taille totale du bloc mémoire à réserver ;
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 malloc() :

int *ptr;
ptr = malloc(10 * sizeof(int));

La même opération avec calloc() :

int *ptr;
ptr = calloc(10, sizeof(int));

Si le système d’exploitation dispose de mémoire disponible malloc() et 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 :

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 :

// malloc1.c

#include <stdio.h>
#include <stdlib.h>

#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

Le bloc mémoire réservé comporte éléments
Le bloc mémoire réservé comporte octets
Le bloc mémoire réservé débute à l’adresse
Le bloc mémoire réservé se termine à l’adresse
Le pointeur ptr a pour valeur
Le pointeur ptr a pour adresse
La valeur du 3ième élément du tableau est
Avec l’opérateur d’indexation, la valeur du 3ième élément du tableau s’obtient avec
Avec l’opérateur d’indirection, la valeur du 3ième élément du tableau s’obtient avec

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 malloc() ou calloc() n’est pas automatiquement libérée. C’est de la responsabilité du programmeur de le faire. Pour cela on utilise la fonction free() dont le prototype est déclaré dans <stdlib.h>. Le prototype (simplifié) :

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 :

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 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 `main()`

Il faut modifier la fonction main() écrite précédemment en utilisant l’allocation dynamique.

Information

Grâce à l’équivalence tableau-pointeur, les fonctions secondaires n’ont pas à être modifiées.

S’assurer que la signature de 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 main() décrite dans le paragraphe Passage des arguments en ligne de 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 srand() pour obtenir des tirages différents à chaque exécution.

Initialiser le tableau avec des valeurs aléatoires comprises entre 0 et ubound-1.

Information

Grâce à l’équivalence tableau-pointeur, l’appel des fonctions précédentes doit se faire sans modification.

Avertissement

Pour certaines combinaisons de size et ubound, la fonction sum() peut produire des entiers qui dépassent la limite (relire la note sur les long int). Pour éviter ce problème, il est nécessaire de modifier la fonction sum() pour qu’elle utilise et retourne un long int.

Dans la fonction main(), il ne faudra pas oublier de modifier la place réservée dans la chaine de formatage de 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 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 time aperçue lors du 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