ENIB LANG-C 06_Alloc - Allocation dynamique

Mise en place du programme d'expérimentation

Ce chapitre s'appuiera fortement sur l'expérimentation ; veuillez donc suivre précisément les recommandations afin d'être en mesure d'observer ce qui doit l'être.

Ouvrez un terminal et grâce à la ligne de commande du shell, placez-vous dans le répertoire de travail choisi pour ce sujet.
Saisissez par exemple : $ mkdir LANG_C_06_Alloc ↵ $ cd LANG_C_06_Alloc ↵ Placez dans ce répertoire le fichier GNUmakefile générique mis à votre disposition.
Nous suivrons en effet la démarche de programmation modulaire présentée précédemment.

Nous utilisons comme prétexte un ensemble de fonctionnalités autour des nombres premiers.
Vous devrez dans un premier temps réaliser la fonction isPrime() suivante.
Elle sera déclarée dans le fichier d'en-tête primes.h

#ifndef PRIMES_H
#define PRIMES_H

#include <stdbool.h>

bool // tested is a prime number
isPrime(const int *primes,
        int primeCount,
        int tested);

#endif // PRIMES_H

et définie dans le fichier primes.c.

#include "primes.h"

bool // tested is a prime number
isPrime(const int *primes,
        int primeCount,
        int tested)
{
  if(tested==2)
  {
    return true; // 2 is a prime numer
  }
  if((tested<2)||(tested%2==0))
  {
    return false; // 0, 1 and even numbers are not prime numbers
  }
  for(int i=0; i<primeCount; ++i)
  {
    int div=primes[i];
    if(div*div>tested) // no need to search further and not
    {
      return true;     //   multiple of anything so far, thus prime number
    }
    if(tested%div==0)  // multiple of a previous prime number,
    {
      return false;    //   thus not a prime number
    }
  }
  int lastDiv=primeCount>1 ? primes[primeCount-1] : 3;
  for(int div=lastDiv; div*div<=tested; div+=2) // go on with odd numbers
  {
    if(tested%div==0)  // multiple of an odd number
    {
      return false;    //   thus not a prime number
    }
  }
  return true; // not multiple of anything so far, thus prime number
}

La fonction isPrime() utilise un procédé simple pour effectuer le test de primalité d'un nombre entier.
Elle s'appuie sur le fait que les nombres premiers commencent à deux et donc que les suivants ne peuvent pas être pairs, d'où l'énumération de deux en deux à partir de trois.
Elle cherche alors à déterminer si le nombre à tester est divisible par un des entiers énumérés.
Si après avoir atteint la racine carrée du nombre testé aucune division ne tombe juste, c'est que le nombre testé est premier.
Toutefois, pour accélérer la recherche, si des nombres premiers sont déjà connus et transmis dans un tableau alors la recherche d'un diviseur entier commence par ceux-ci.

Le programme principal sera rédigé dans le fichier prog06.c et invoquera une fonction test_isPrime() de ce même fichier :

#include <stdio.h>
#include "primes.h"

void
test_isPrime(void)
{
  printf("\n~~~~ %s() ~~~~\n", __func__);
  int primes[]={2, 3, 5, 7, 11, 13, 17, 19};
  int primeCount=(int)(sizeof(primes)/sizeof(primes[0]));
  for(int i=0; i<100; ++i)
  {
    if(isPrime(primes, primeCount, i))
    {
      printf("%d ", i);
    }
  }
  printf("\n");
}

int
main(void)
{
  test_isPrime();
  return 0;
}

La fonction test_isPrime() affiche les nombres premiers qui sont inférieurs à 100.
Pour ceci, elle repose sur la fonction isPrime() qui s'appuie sur quelques nombres premiers déjà connus qui lui sont transmis dans un tableau et poursuit en testant les nombres impairs.
Remarquez que, puisque nous avons découvert les chaînes de caractères dans un chapitre précédent, nous pouvons utiliser la variable prédéfinie __func__ afin d'afficher le nom de la fonction courante sans avoir à le saisir explicitement.
(https://en.cppreference.com/w/c/language/function_definition#func)

Fabriquez ce programme et exécutez-le afin de vérifier que tout est en place. $ make ↵ $ ./prog06 ↵ En l'état, il ne fait qu'afficher le nom de la fonction test_isPrime() et la liste des nombres premiers inférieurs à 100.

{} Limite de la pile d'exécution

Nous utilisons le prétexte des nombres premiers pour remplir des tableaux afin d'en explorer les limites.
Vous devez pour cela déclarer dans primes.h et définir dans primes.c la fonction populatePrimes() :

static // only for internal use in this module
int // next prime number (after last of primes)
nextPrime(const int *primes,
          int primeCount)
{
  if(primeCount<2)
  {
    return primeCount+2; // start with 2 and 3
  }
  int tested=primes[primeCount-1];
  do
  {
    tested+=2; // go on with odd numbers
  } while(!isPrime(primes, primeCount, tested));
  return tested;
}

void
populatePrimes(int *primes,
               int primeCount)
{
  for(int i=0; i<primeCount; ++i)
  {
    primes[i]=nextPrime(primes, i);
  }
}

Pour déterminer chaque nouvel élément du tableau primes, la fonction populatePrimes() se contente d'appeler la fonction utilitaire nextPrime().
Remarquez que cette dernière est précédée du mot-clef static✍ ; cela signifie qu'elle n'est visible que dans cette unité de compilation.
En effet, cette fonction ne nous sera utile que dans populatePrimes() et d'autres fonctions du même module mais n'a aucune raison d'être invoquée depuis les autres modules de l'application.
Elle n'est donc pas déclarée dans le fichier d'en-tête et son qualificatif static indique à l'éditeur de liens que, si par hasard une autre fonction a le même nom dans un autre module, alors il faudra la considérer comme une fonction distincte✍.
Puisque cette fonction n'est pas déclarée, sa définition doit précéder celle de la fonction populatePrimes() qui en fait usage.

Une fonction test_populatePrimes() sera réalisée dans le fichier prog06.c et sera appelée par le programme principal.
Elle s'appuie sur une fonction utilitaire displayPrimes() qui affiche le contenu d'un tableau de nombres premiers en limitant toutefois la longueur de l'affichage lorsque ces nombres sont très nombreux.

void
displayPrimes(const int *primes,
              int primeCount,
              int limit)
{
  if(limit>0)
  {
    for(int i=0; i<limit; ++i)
    {
      printf("%d%c", primes[i], (i%10)==9 ? '\n' : '\t');
    }
    if(primeCount>limit)
    {
      printf("...\n");
    }
    else if(limit%10)
    {
      printf("\n");
    }
  }
  printf("last of %d primes: %d\n",
         primeCount, primeCount ? primes[primeCount-1] : 0);
}

void
test_populatePrimes(void)
{
  printf("\n~~~~ %s() ~~~~\n", __func__);
  int primes[1000];
  int primeCount=(int)(sizeof(primes)/sizeof(primes[0]));
  populatePrimes(primes, primeCount);
  displayPrimes(primes, primeCount, 100);
}

Fabriquez à nouveau ce programme et exécutez-le afin de vérifier qu'il produit bien la séquence de valeurs attendue (le millième nombre premier est 7919).

Dans le but d'expérimenter autour des limites des tableaux, reprenez ensuite cette expérience avec 100000 (cent-mille) éléments puis 1000000 (un-million), 2000000 (deux-millions), 3000000 (trois-millions), etc.
Au delà du temps de calcul qui devient de plus en plus long, l'augmentation de la taille du tableau finira par provoquer un plantage du programme !

La zone mémoire utilisée par les appels de fonctions est la pile d'exécution.
Elle contient notamment les paramètres et les variables de classe de stockage automatique de chaque fonction appelée.
Le tableau que nous manipulons dans la fonction test_populatePrimes() est bien une variable automatique, il est donc placé dans la pile d'exécution.
La taille de cette dernière peut être très variable d'une plateforme d'exécution à une autre (de quelques kilo-octets à quelques méga-octets) mais dans tous les cas elle est limitée.
Par conséquent, il n'est pas raisonnable de placer dans la pile d'exécution des données exagérément volumineuses.
Cela implique qu'en pratique nous nous interdisons la déclaration de tableaux ayant plus que quelques dizaines, voire quelques centaines, d'éléments✍.

{} Allocation dynamique de mémoire

Lorsqu'il est question de manipuler un volume de données conséquent, il devient nécessaire de recourir à une nouvelle classe de stockage : l'allocation dynamique.
Il s'agit de réclamer au système d'exploitation un bloc d'octets d'une taille choisie afin que le programme en fasse l'usage qui lui convient.
La zone de l'espace d'adressage dans laquelle le système d'exploitation puise pour fournir ces blocs est dénommée le tas (heap).

Contrairement aux variables de classe de stockage automatique, un tel bloc de données reste accessible au programme, quelles que soient les entrées et les sorties dans les fonctions du programme, sans limitation de durée.
Toutefois, si le programme estime qu'à partir d'un instant il n'a plus besoin d'un tel bloc de données, il doit le libérer explicitement afin que celui-ci redevienne disponible pour un autre usage dans le système d'exploitation.
L'oubli d'une telle libération est dénommée une fuite mémoire.
Si un programme produit de manière répétée des fuites mémoire, cette situation peut conduire à un extrême ralentissement de tout le système d'exploitation.
Bien entendu, les blocs de données alloués par un programme seront automatiquement libérés lorsque ce dernier se terminera✍.

{} Allocation et libération

Une nouvelle fonction test_allocatePrimes() attendant un paramètre primeCount de type entier sera réalisée dans le fichier prog06.c et sera appelée par le programme principal en utilisant 1000 (mille) comme paramètre effectif.
Le corps de cette fonction sera très semblable à celui de la fonction test_populatePrimes().

Elle doit commencer par afficher son nom et son paramètre puis remplacer la déclaration du tableau d'entiers primes par un pointeur sur des entiers.
Ce pointeur doit être initialisé par le résultat de l'appel à la fonction standard malloc().

  ...
  int *primes=(int *)malloc(primeCount*sizeof(int));
  ...

Pour cela il vous faudra inclure le fichier d'en-tête standard

<stdlib.h>

comme précisé dans la documentation.
(https://en.cppreference.com/w/c/memory/malloc)
Le paramètre de malloc() représente la taille en octets du bloc de données réclamé.
Ici, ce bloc devra contenir primeCount éléments de type int ; nous en déduisons la taille en octets nécessaire.
Puisqu'elle donne accès à une portion de la mémoire, la fonction standard malloc() renvoie une adresse.
Seulement, ses concepteurs n'ont aucune connaissance préalable de l'usage qui en sera fait ; il s'agit certes d'une adresse, mais celle d'une donnée de quel type ?
C'est pour cette raison que le type de retour est void * : un pointeur vers un type indéterminé.
Il vous faudra donc utiliser un cast pour convertir le type de l'adresse renvoyée vers le type de primes✍.
Désormais, le bloc de données désigné par le pointeur primes peut être considéré comme un tableau d'entiers obtenu dynamiquement.
Il peut être utilisé comme l'était le tableau de la fonction test_populatePrimes() : nous le remplissons avec populatePrimes() et en affichons le contenu avec displayPrimes().

Fabriquez à nouveau ce programme et exécutez-le afin de vérifier qu'il produit toujours la séquence de valeurs attendue (le millième nombre premier est 7919).
Toutefois, si sur votre plateforme le fichier GNUmakefile invoque le compilateur avec l'option -fsanitize=address, des vérifications sont insérées dans le code exécutable du programme afin de détecter des incohérences dans l'utilisation de la mémoire (cela sera présenté dans cette section).
Cet outil doit justement signaler, lors de la terminaison du programme, que le bloc d'octets alloué dynamiquement dans la fonction test_allocatePrimes() n'a jamais été libéré.
En effet, lorsque cette fonction se termine, la variable primes qui désigne ce bloc mémoire disparaît ce qui rend désormais ce dernier inaccessible bien que toujours existant !

Pour corriger ce défaut, nous devons nous interroger sur la durée pendant laquelle ce bloc de données obtenu dynamiquement est nécessaire.
Après que l'affichage (à l'aide de displayPrimes()) ait eu lieu, la fonction test_allocatePrimes() n'en a plus besoin ; il nous faut alors le libérer avec la fonction standard free().
La documentation de cette dernière nous indique qu'elle est déclarée dans le fichier d'en-tête déjà inclus pour la fonction d'allocation.
(https://en.cppreference.com/w/c/memory/free)
Son paramètre représente l'adresse du bloc mémoire dont nous n'avons plus l'usage.
Il n'est pas question de fournir ici une adresse quelconque : cela produirait probablement un plantage.
Au contraire, les seules adresses qui soient autorisées pour un appel à free() sont exactement celles qui ont été obtenues par les fonctions d'allocation dynamique✍ (malloc() ici).
Bien entendu, la libération d'un même bloc mémoire ne peut avoir lieu qu'une seule fois.
Nous fournirons alors le pointeur primes comme paramètre à la fonction free().

  ...
  free(primes);
  ...

Remarquez que, bien que le type attendu soit void *, il n'est pas nécessaire d'utiliser un cast.
En effet, l'adresse d'une donnée de type spécifique peut être vue comme une adresse quelconque, alors que l'inverse nécessite l'explicitation du type attendu.

Fabriquez à nouveau ce programme et exécutez-le afin de vérifier que la fuite mémoire a bien été éliminée et que le fonctionnement est toujours correct.
Reprenez ensuite cette expérimentation avec 100000 (cent-mille) éléments puis 1000000 (un-million), 2000000 (deux-millions), 3000000 (trois-millions), etc.
Bien que le temps de calcul devienne de plus en plus long (toujours plus de nombres premiers à déterminer), le tableau d'entiers obtenu dynamiquement semble pouvoir atteindre une taille quelconque.

{} Controle de l'échec

À lire la documentation de la fonction malloc(), nous en déduisons qu'il est prudent de contrôler la valeur du pointeur obtenu.
Il est précisément annoncé que cette fonction renvoie un pointeur nul lorsque l'allocation échoue.
(https://en.cppreference.com/w/c/memory/malloc)

La première interrogation que la détection d'un tel événement soulève concerne le comportement à adopter lorsqu'il survient.
S'il n'est effectivement pas possible d'obtenir du système d'exploitation le bloc mémoire dont le programme à besoin, que peut on faire d'autre que de terminer brutalement ce programme ?
Toute action plus élaborée, comme afficher un message ou le consigner dans un journal d'activité, n'offre aucune garantie quant à son accomplissement puisqu'elle n'obtiendra peut-être pas la quantité de mémoire nécessaire à son propre fonctionnement !
La fonction standard abort(), sans paramètre ni résultat, déclarée dans le même fichier d'en-tête que les fonctions d'allocation, provoque à cet effet une terminaison anormale du programme qui peut être facilement détectée dans un débogueur✍.
(https://en.cppreference.com/w/c/program/abort)
Nous pouvons alors compléter l'allocation dynamique de cette façon :

  ...
  int *primes=(int *)malloc(primeCount*sizeof(int));
  if(primes==NULL)
  {
    abort();
  }
  ...

La terminaison du programme permettra certainement au système d'exploitation de regagner une quantité de mémoire qui lui faisait défaut ; cela sera d'autant plus significatif dans le cas où ce programme serait responsable d'une fuite mémoire causant l'épuisement constaté.

Il est cependant légitime de s'interroger sur le réel bénéfice d'une telle vérification.
Si nous n'avions pas contrôlé la nullité du pointeur obtenu, et poursuivi le traitement de manière optimiste, alors à la toute première tentative de déréférencement de ce pointeur nous aurions provoqué un plantage du programme à cause d'un accès à une zone mémoire non autorisée (l'adresse nulle ici en l'occurrence) : une erreur de segmentation.
Dans les faits, cela provoque une terminaison du programme tout aussi anormale qu'avec l'utilisation de abort() !
C'est pour cette raison qu'il existe des partisans des deux stratégies suivantes :

détecter le pointeur nul et terminer explicitement avec abort(),
ou bien ne pas alourdir l'écriture du code avec un contrôle inutile et laisser le programme se terminer tout seul.

Pour compliquer la situation, il faut savoir que la plupart des systèmes d'exploitation distinguent la mémoire virtuelle de la mémoire physique✍.
Pour des raisons liées à l'optimisation des systèmes d'exploitation, lorsqu'une fonction d'allocation réclame un bloc de mémoire, il ne s'agit que de mémoire virtuelle.
Ce n'est qu'à l'écriture dans cette zone mémoire que le système d'exploitation se préoccupe de la mémoire physique qu'il devra mobiliser pour rendre cette opération possible.
Seulement, cette dernière vérification n'a lieu que bien après être sorti de la fonction malloc() (à l'utilisation du pointeur obtenu), et en cas d'échec de la mobilisation de la mémoire physique, une erreur de segmentation provoquera la terminaison anormale du programme.
Cela fait que dans la pratique il est quasiment impossible que malloc() renvoie un pointeur nul✍ : en cas d'épuisement de la mémoire physique le programme se plantera de toutes façons au déréférencement du pointeur.

Néanmoins, il peut arriver que sur quelques systèmes embarqués, équipés d'un système d'exploitation rudimentaire, la gestion de la mémoire soit bien plus simple et autorise un accès direct à la mémoire physique✍.
Si suite à l'épuisement de cette dernière, la fonction d'allocation renvoie un pointeur nul, et que nous l'utilisons sans précaution, alors nous risquons d'écraser les données qui sont situées dans la partie basse de l'espace d'adressage et donc de perturber fortement le système dans sa globalité (pas uniquement notre programme).
C'est finalement dans l'éventualité de la réutilisation de notre code sur une telle plateforme d'exécution que nous nous imposons de vérifier systématiquement la nullité du résultat de la fonction d'allocation pour, le cas échéant, terminer explicitement et brutalement le programme par la fonction standard abort().

{} Intégration à un module

{} Ré-allocation de la mémoire dynamique

Imaginons maintenant que nous ayons besoin de connaître toujours plus de nombres premiers au cours de l'exécution du programme.
Si la fonction allocatePrimes() nous en a déjà fourni et que plus tard nous en voulons plus, nous pourrions simplement libérer le premier tableau obtenu dynamiquement et invoquer une nouvelle fois allocatePrimes() avec un paramètre primeCount plus élevé.
Seulement, cette opération nécessiterait un nouveau calcul des nombres premiers que nous connaissions déjà, ce qui représente une perte de temps.

{} Nouvelle allocation, recopie et libération explicites

Pour répondre à ce nouveau besoin, il nous faut réaliser une fonction extendPrimes() dont le rôle consiste à étendre un tableau de nombres premiers obtenu dynamiquement.
Elle doit être déclarée dans le fichier d'en-tête primes.h et définie dans le fichier primes.c.

void
extendPrimes(int **inout_primes,
             int *inout_primeCount,
             int nextPrimeCount)
{
  //-- load inout-parameters --
  int *primes=*inout_primes;
  int primeCount=*inout_primeCount;
  //-- obtain new storage --
  int *tmp=(int *)malloc(nextPrimeCount*sizeof(int));
  if(tmp==NULL)
  {
    abort();
  }
  //-- duplicate previous prime numbers --
  int limit=primeCount<nextPrimeCount ? primeCount : nextPrimeCount;
  for(int i=0; i<limit; ++i)
  {
    tmp[i]=primes[i];
  }
  //-- give back previous storage and substitute with the new one --
  free(primes);
  primes=tmp;
  //-- compute new prime numbers --
  for(int i=primeCount; i<nextPrimeCount; ++i)
  {
    primes[i]=nextPrime(primes, i);
  }
  //-- store out-parameters --
  *inout_primes=primes;
  *inout_primeCount=nextPrimeCount;
}

Un tel tableau est désigné par un pointeur et un entier qu'il faudra modifier ; cette fonction reçoit donc en premier paramètre l'adresse d'un pointeur sur entiers nommée inout_primes, et en deuxième paramètre l'adresse d'un entier nommée inout_primeCount.
Son troisième paramètre nommé nextPrimeCount est un simple entier indiquant le prochain nombre d'éléments de ce tableau.
Remarquons tout d'abord que, puisque les deux premiers paramètres servent à manipuler des variables du contexte appelant, nous commençons cette fonction en obtenant une copie de ces variables (grâce à l'opération de déréférencement *) et nous finissons de la même façon en les mettant à jour ; ainsi l'essentiel de la fonction travaille sur des variables locales, ce qui facilite l'écriture et évite de multiples déréférencements.
Comme l'indiquent les commentaires, les étapes de ce traitement consistent à :

obtenir dynamiquement un tableau d'entiers suffisamment grand pour contenir tous les nombres premiers désirés,
recopier vers ce nouvel emplacement les nombres premiers déjà connus du tableau dynamique précédent,
se débarrasser du tableau dynamique précédent✍
La documentation de free() précise que si le pointeur est initialement nul, sa libération ne pose aucun problème.
et considérer le nouveau pour la suite,
compléter le nouveau tableau dynamique avec les nombres premiers qui n'étaient pas connus du précédent.

Une fonction test_extendPrimes() sera réalisée dans le fichier prog06.c et sera appelée par le programme principal en utilisant 100000 (cent-mille) et 10 (dix) comme paramètres effectifs.

void
test_extendPrimes(int extentStep,
                  int extentCount)
{
  printf("\n~~~~ %s(%d, %d) ~~~~\n", __func__, extentStep, extentCount);
  int primeCount=0;
  int *primes=NULL;
  for(int i=0; i<extentCount; ++i)
  {
    extendPrimes(&primes, &primeCount, (i+1)*extentStep);
    displayPrimes(primes, primeCount, 10);
  }
  free(primes);
}

Cette fonction part d'un tableau dynamique inexistant (pointeur nul et donc aucun élément) et à chacune des extentCount itérations demande à l'étendre de extentStep éléments supplémentaires.
Remarquez notamment que, conformément au prototype de la fonction extendPrimes(), les variables primes et primeCount sont passées par adresse (opération de référencement &) ; elles doivent en effet être modifiées par cette fonction.
À la toute fin de cette fonction de test, l'état final du tableau dynamique primes peut enfin être libéré✍.
Fabriquez à nouveau ce programme et exécutez-le afin de vérifier qu'il produit bien la séquence de valeurs attendue (le millionième nombre premier est 15485863).

Le redimensionnement du tableau obtenu dynamiquement repose ici sur une boucle de recopie des anciennes données vers le nouveau tableau.
La fonction standard memcpy() est très couramment utilisée pour la copie d'un grand volume de données.
(https://en.cppreference.com/w/c/string/byte/memcpy)
Elle reçoit en paramètres les adresses des zones mémoire destination et source, ainsi que le nombre d'octets à recopier.
Après avoir inclus le fichier d'en-tête standard

<string.h>

, remplacez la boucle de recopie de la fonction extendPrimes() par une invocation de memcpy().

{
  ...
  memcpy(tmp, primes, limit*sizeof(int));
  ...
}

Fabriquez à nouveau ce programme et reprenez l'expérimentation précédente afin de vous assurer du fait que son comportement est identique.

Bien que la fonction extendPrimes(), en l'état, semble répondre à nos attentes, elle comporte tout de même un défaut : une recopie du précédent contenu est systématiquement nécessaire à chacun des redimensionnements.

{} Fonction standard de ré-allocation

La démarche qui consiste à allouer un nouvel espace mémoire, y recopier les données d'un précédent et libérer ce dernier correspond à un besoin assez courant.
C'est pour cette raison qu'il existe la fonction standard de ré-allocation realloc().
(https://en.cppreference.com/w/c/memory/realloc)
Elle reçoit en paramètres l'ancien pointeur et la taille en octets désirée pour le nouvel espace afin d'effectuer l'équivalent des étapes successives de notre réalisation précédente et renvoyer la nouvelle adresse obtenue.
Comme pour la fonction free(), il n'est pas question de fournir à la fonction realloc() autre chose qu'exactement une adresse préalablement obtenue par allocation dynamique✍ (malloc() ou realloc() ici).

Au-delà de la simple économie d'écriture, elle offre un autre avantage bien plus intéressant : si l'ancien espace alloué est immédiatement suivi d'une zone de mémoire inutilisée qui est suffisamment grande, il est simplement redimensionné sur place sans nécessiter la moindre recopie (son adresse de début reste donc inchangée).
Dans la pratique il n'est pas rare qu'il en soit ainsi, ce qui permet d'économiser assez souvent la longue opération de recopie évoquée à la fin de la section précédente.
Remplacez alors, dans la fonction extendPrimes(), les étapes d'allocation, recopie et libération par un appel à realloc() en prenant soin de réaffecter son résultat dans primes✍.

{
  ...
  //-- extend storage --
  primes=(int *)realloc(primes, nextPrimeCount*sizeof(int));
  if(primes==NULL)
  {
    abort();
  }
  ...
}

Puisqu'il s'agit d'une fonction d'allocation dynamique de mémoire, nous nous imposons, comme dans le cas de malloc(), de tester la nullité de son résultat pour invoquer abort() le cas échéant.
Fabriquez à nouveau ce programme et reprenez l'expérimentation précédente afin de vous assurer du fait que son comportement est bien resté identique.

{} Allocation spéculative

Tous les exemples précédents avaient en commun le fait que nous connaissions exactement à l'avance le nombre d'entiers nécessaires au stockage des informations utiles.
Il nous suffisait de réserver l'espace nécessaire (dans la pile ou dynamiquement) avant d'initialiser chacune des valeurs.
Toutefois, il n'en est pas toujours ainsi : pour certains traitements il n'est pas aisé de déterminer à l'avance la quantité de données qui devront être mémorisées.
C'est le cas par exemple si nous recherchons les nombres premiers jusqu'à un entier choisi : nous ne savons pas a priori combien de nombres premiers existent jusqu'à cette limite.

Nous pourrions envisager d'étendre le tableau d'un seul élément à la fois jusqu'à atteindre ou dépasser la limite recherchée, mais ces multiples ré-allocations seraient largement sous-optimales en temps d'exécution.
La solution alternative consiste à procéder de manière spéculative en allouant une quantité jugée probablement satisfaisante pour les prochains nombres premiers rencontrés et à ré-allouer de la même façon lorsque cette quantité n'est plus suffisante.
Seulement, il n'est pas aisé d'estimer un pas de progression convenable pour ces multiples ré-allocations.
Si nous choisissons un petit incrément (trente-deux éléments par exemple) mais que nous devons rechercher beaucoup de nombres premiers (jusqu'à dix-millions par exemple), il faudra recourir à énormément de ré-allocations.
Or, les opérations d'allocation de mémoire sont très coûteuses en temps d'exécution ; il faut éviter de les invoquer de manière incessante.
À l'opposé, si l'incrément est très grand (un-million d'éléments par exemple) alors que nous ne recherchons que quelques nombres premiers (jusqu'à mille par exemple), nous consommerons beaucoup de mémoire inutilement✍.

Une démarche courante consiste à utiliser une progression géométrique de l'incrément afin qu'il soit de plus en plus grand.
Il est généralement inutile de partir d'une quantité ridiculement petite ; nous pouvons fixer le premier incrément à trente-deux éléments par exemple.
Une progression simple consiste à doubler cette quantité à chaque fois qu'une ré-allocation est nécessaire.
Cependant les incréments risquent de devenir démesurément grands ; il convient donc de se fixer une limite, 1024*1024 éléments par exemple, au-delà de laquelle l'incrément ne sera plus doublé.

Pour expérimenter cette démarche, nous réalisons une fonction allocatePrimesUntil() dont le rôle consiste à allouer dynamiquement un tableau contenant les nombres premiers jusqu'à une limite choisie.
Elle doit être déclarée dans le fichier d'en-tête primes.h et définie dans le fichier primes.c.

void
allocatePrimesUntil(int **out_primes,
                    int *out_primeCount,
                    int lastTested)
{
  int *primes=NULL;
  int primeCount=0;
  for(int capacity=primeCount; ; ++primeCount)
  {
    int prime=nextPrime(primes, primeCount);
    if(prime>lastTested)
    {
      break;
    }
    if(primeCount==capacity) // no space left
    {
      //-- determine new capacity --
      int minChunk=32, maxChunk=1024*1024;
      if(capacity<minChunk)
      {
        capacity=minChunk;
      }
      else if(capacity<maxChunk)
      {
        capacity*=2;
      }
      else
      {
        capacity+=maxChunk;
      }
      //-- extend storage --
      primes=(int *)realloc(primes, capacity*sizeof(int));
      if(primes==NULL)
      {
        abort();
      }
    }
    primes[primeCount]=prime;
  }
  //-- store out-parameters --
  *out_primes=primes;
  *out_primeCount=primeCount;
}

Un tel tableau est désigné par un pointeur et un entier qu'il faudra renseigner ; cette fonction reçoit donc en premier paramètre l'adresse d'un pointeur sur entiers nommée out_primes, et en deuxième paramètre l'adresse d'un entier nommée out_primeCount.
Son troisième paramètre nommé lastTested est un simple entier indiquant le dernier nombre pour lequel nous cherchons à déterminer s'il est premier.
Nous constatons qu'au delà de primeCount qui compte les nombres premiers au fur et à mesure que nous les découvrons, il nous faut tenir trace dans capacity du nombre d'entiers que nous sommes en mesure de mémoriser dans le tableau dynamique courant.
À chaque fois que cette capacité vient à être atteinte✍, une ré-allocation est nécessaire (selon la démarche progressive explicitée juste avant), ce qui autorisera la mémorisation des quelques prochains nombres premiers.

Une fonction test_allocatePrimesUntil() sera réalisée dans le fichier prog06.c et sera appelée par le programme principal en utilisant 1000000 (un-million) comme paramètre effectif.

void
test_allocatePrimesUntil(int lastTested)
{
  printf("\n~~~~ %s(%d) ~~~~\n", __func__, lastTested);
  int primeCount;
  int *primes=NULL;
  allocatePrimesUntil(&primes, &primeCount, lastTested);
  displayPrimes(primes, primeCount, 100);
  free(primes);
}

Fabriquez à nouveau ce programme et exécutez-le afin de vérifier qu'il produit la séquence de valeurs attendue (il y a 78498 nombres premiers avant un-million ; le dernier d'entre eux est 999983).

Complément : étude d'un algorithme au débogueur

À ce stade, vous devez être en mesure de réaliser une fonction extentPrimesUntil() qui repose sur les mêmes principes que allocatePrimesUntil() et extendPrimes() (la capacité initiale du tableau sera supposée correspondre au nombre de ces éléments).
Remarquez que l'algorithme de cette nouvelle fonction est très similaire à celui de allocatePrimesUntil() et que cette dernière peut être réécrite comme un simple appel à la nouvelle.

void
allocatePrimesUntil(int **out_primes,
                    int *out_primeCount,
                    int lastTested)
{
  int *primes=NULL;
  int primeCount=0;
  extendPrimesUntil(&primes, &primeCount, lastTested);
  //-- store out-parameters --
  *out_primes=primes;
  *out_primeCount=primeCount;
}

La fonction test_extendPrimesUntil() sera similaire à test_extendPrimes() et sera invoquée pour effectuer dix pas cherchant à atteindre le prochain million.
Fabriquez à nouveau ce programme et exécutez-le afin de vérifier qu'il produit la séquence de valeurs attendue (il y a 664579 nombres premiers avant dix-millions ; le dernier d'entre-eux est 9999991).

Code source de l'expérimentation

Si chaque étape a été respectée scrupuleusement, vous devez obtenir des fichiers de code source et semblables à ceux-ci :

Fichier primes.h✎

Fichier primes.c✎

Contenu du fichier primes.c

//----------------------------------------------------------------------------

#include "primes.h"
#include <stdlib.h>
#include <string.h>

#define USE_REALLOC 1
#define USE_MEMCPY  1

bool // tested is a prime number
isPrime(const int *primes,
        int primeCount,
        int tested)
{
  if(tested==2)
  {
    return true; // 2 is a prime numer
  }
  if((tested<2)||(tested%2==0))
  {
    return false; // 0, 1 and even numbers are not prime numbers
  }
  for(int i=0; i<primeCount; ++i)
  {
    int div=primes[i];
    if(div*div>tested) // no need to search further and not
    {
      return true;     //   multiple of anything so far, thus prime number
    }
    if(tested%div==0)  // multiple of a previous prime number,
    {
      return false;    //   thus not a prime number
    }
  }
  int lastDiv=primeCount>1 ? primes[primeCount-1] : 3;
  for(int div=lastDiv; div*div<=tested; div+=2) // go on with odd numbers
  {
    if(tested%div==0)  // multiple of an odd number
    {
      return false;    //   thus not a prime number
    }
  }
  return true; // not multiple of anything so far, thus prime number
}

static // only for internal use in this module
int // next prime number (after last of primes)
nextPrime(const int *primes,
          int primeCount)
{
  if(primeCount<2)
  {
    return primeCount+2; // start with 2 and 3
  }
  int tested=primes[primeCount-1];
  do
  {
    tested+=2;  // go on with odd numbers
  } while(!isPrime(primes, primeCount, tested));
  return tested;
}

void
populatePrimes(int *primes,
               int primeCount)
{
  for(int i=0; i<primeCount; ++i)
  {
    primes[i]=nextPrime(primes, i);
  }
}

int * // allocated prime numbers
allocatePrimes(int primeCount)
{
  int *primes=(int *)malloc(primeCount*sizeof(int));
  if(primes==NULL)
  {
    abort();
  }
  populatePrimes(primes, primeCount);
  return primes;
}

void
extendPrimes(int **inout_primes,
             int *inout_primeCount,
             int nextPrimeCount)
{
  //-- load inout-parameters --
  int *primes=*inout_primes;
  int primeCount=*inout_primeCount;
#if USE_REALLOC
    //-- extend storage --
    primes=(int *)realloc(primes, nextPrimeCount*sizeof(int));
    if(primes==NULL)
    {
      abort();
    }
#else
    //-- obtain new storage --
    int *tmp=(int *)malloc(nextPrimeCount*sizeof(int));
    if(tmp==NULL)
    {
      abort();
    }
    //-- duplicate previous prime numbers --
    int limit=primeCount<nextPrimeCount ? primeCount : nextPrimeCount;
# if USE_MEMCPY
      memcpy(tmp, primes, limit*sizeof(int));
# else
      for(int i=0; i<limit; ++i)
      {
        tmp[i]=primes[i];
      }
# endif
    //-- give back previous storage and substitute with the new one --
    free(primes);
    primes=tmp;
#endif
  //-- compute new prime numbers --
  for(int i=primeCount; i<nextPrimeCount; ++i)
  {
    primes[i]=nextPrime(primes, i);
  }
  //-- store out-parameters --
  *inout_primes=primes;
  *inout_primeCount=nextPrimeCount;
}


void
allocatePrimesUntil(int **out_primes,
                    int *out_primeCount,
                    int lastTested)
{
  int *primes=NULL;
  int primeCount=0;
#if 0 // first version
  for(int capacity=primeCount; ; ++primeCount)
  {
    int prime=nextPrime(primes, primeCount);
    if(prime>lastTested)
    {
      break;
    }
    if(primeCount==capacity) // no space left
    {
      //-- determine new capacity --
      int minChunk=32, maxChunk=1024*1024;
      if(capacity<minChunk)
      {
        capacity=minChunk;
      }
      else if(capacity<maxChunk)
      {
        capacity*=2;
      }
      else
      {
        capacity+=maxChunk;
      }
      //-- extend storage --
      primes=(int *)realloc(primes, capacity*sizeof(int));
      if(primes==NULL)
      {
        abort();
      }
    }
    primes[primeCount]=prime;
  }
#else // second version
  extendPrimesUntil(&primes, &primeCount, lastTested);
#endif
  //-- store out-parameters --
  *out_primes=primes;
  *out_primeCount=primeCount;
}

void
extendPrimesUntil(int **inout_primes,
                  int *inout_primeCount,
                  int lastTested)
{
  //-- load inout-parameters --
  int *primes=*inout_primes;
  int primeCount=*inout_primeCount;
  //-- perform work --
  for(int capacity=primeCount; ;++primeCount)
  {
    int prime=nextPrime(primes, primeCount);
    if(prime>lastTested)
    {
      break;
    }
    if(primeCount==capacity) // no space left
    {
      //-- determine new capacity --
      int minChunk=32, maxChunk=1024*1024;
      if(capacity<minChunk)
      {
        capacity=minChunk;
      }
      else if(capacity<maxChunk)
      {
        capacity*=2;
      }
      else
      {
        capacity+=maxChunk;
      }
      //-- extend storage --
      primes=(int *)realloc(primes, capacity*sizeof(int));
      if(primes==NULL)
      {
        abort();
      }
    }
    primes[primeCount]=prime;
  }
  //-- store out-parameters --
  *inout_primes=primes;
  *inout_primeCount=primeCount;
}

//----------------------------------------------------------------------------

Fichier prog06.c✎

Contenu du fichier prog06.c

//----------------------------------------------------------------------------

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

void
displayPrimes(const int *primes,
              int primeCount,
              int limit)
{
  if(limit>0)
  {
    for(int i=0; i<limit; ++i)
    {
      printf("%d%c", primes[i], (i%10)==9 ? '\n' : '\t');
    }
    if(primeCount>limit)
    {
      printf("...\n");
    }
    else if(limit%10)
    {
      printf("\n");
    }
  }
  printf("last of %d primes: %d\n",
         primeCount, primeCount ? primes[primeCount-1] : 0);
}

void
test_isPrime(void)
{
  printf("\n~~~~ %s() ~~~~\n", __func__);
  int primes[]={2, 3, 5, 7, 11, 13, 17, 19};
  int primeCount=(int)(sizeof(primes)/sizeof(primes[0]));
  for(int i=0; i<100; ++i)
  {
    if(isPrime(primes, primeCount, i))
    {
      printf("%d ", i);
    }
  }
  printf("\n");
}

void
test_populatePrimes(void)
{
  printf("\n~~~~ %s() ~~~~\n", __func__);
  int primes[1000];
  int primeCount=(int)(sizeof(primes)/sizeof(primes[0]));
  populatePrimes(primes, primeCount);
  displayPrimes(primes, primeCount, 100);
}

void
test_allocatePrimes(int primeCount)
{
  printf("\n~~~~ %s(%d) ~~~~\n", __func__, primeCount);
#if 0 // first version
  int *primes=(int *)malloc(primeCount*sizeof(int));
  populatePrimes(primes, primeCount);
#else // second version
  int *primes=allocatePrimes(primeCount);
#endif
  displayPrimes(primes, primeCount, 100);
  free(primes);
}

void
test_extendPrimes(int extentStep,
                  int extentCount)
{
  printf("\n~~~~ %s(%d, %d) ~~~~\n", __func__, extentStep, extentCount);
  int primeCount=0;
  int *primes=NULL;
  for(int i=0; i<extentCount; ++i)
  {
    extendPrimes(&primes, &primeCount, (i+1)*extentStep);
    displayPrimes(primes, primeCount, 10);
  }
  free(primes);
}

void
test_allocatePrimesUntil(int lastTested)
{
  printf("\n~~~~ %s(%d) ~~~~\n", __func__, lastTested);
  int primeCount;
  int *primes=NULL;
  allocatePrimesUntil(&primes, &primeCount, lastTested);
  displayPrimes(primes, primeCount, 100);
  free(primes);
}

void
test_extendPrimesUntil(int extentStep,
                       int extentCount)
{
  printf("\n~~~~ %s(%d, %d) ~~~~\n", __func__, extentStep, extentCount);
  int primeCount=0;
  int *primes=NULL;
  for(int i=0; i<extentCount; ++i)
  {
    extendPrimesUntil(&primes, &primeCount, (i+1)*extentStep);
    displayPrimes(primes, primeCount, 10);
  }
  free(primes);
}

int
main(void)
{
  test_isPrime();
  test_populatePrimes();
  test_allocatePrimes(1000);
  test_extendPrimes(100000, 10);
  test_allocatePrimesUntil(1000000);
  test_extendPrimesUntil(1000000, 10);
  return 0;
}

//----------------------------------------------------------------------------