Prise en charge de l'allocation dynamique – Aréna aux paramètres fixes

Il peut arriver que, dans des applications spécialisées, on connaisse a priori la taille des blocs de mémoire à allouer et le nombre maximal de blocs à allouer pour un type donné.

Un cas possible serait celui d'un jeu vidéo où une guerre épouvantable entre deux tribus d'orques surviendrait en cours de route. Si les paramètres (sizeof(Orque) et nombre maximal d'orques défini par le scénario) sont connus, il est possible de faire aussi bien que les mécanismes standard de gestion de la mémoire allouée dynamiquement avec des algorithmes naïfs (par exemple avec les techniques proposées ici), ce qui implique qu'on pourrait faire mieux en travaillant un peu plus fort (ce que je vous laisse faire par vous-mêmes).

S'il s'avère nécessaire de contrôler la mécanique d'allocation dynamique de mémoire pour un type X donné, alors on voudra définir les opérateurs new et delete sur ce type.

L'opérateur new sera invoqué pour déléguer à l'objet la tâche de se réserver lui-même un bloc de mémoire, donc avant l'appel du constructeur. L'opérateur delete sera quant à lui invoqué pour procéder à la libération du bloc de mémoire dans lequel réside l'objet, donc après le destructeur.

Clairement, dans les deux cas, il serait malsain d'utiliser un membre d'instance pour mettre en place la mécanique d'attribution dynamique de la mémoire, car ces membres n'existent alors pas encore. Il est légal en C++ de ne définir que l'opérateur new ou que l'opérateur delete sur un objet, par exemple pour insérer le code requis pour faire une trace de ces opérations.

Habituellement, toutefois, on voudra implémenter ces opérateurs par paire (souvent même par quartet, du fait qu'il soit probable qu'on veuille appliquer aux tableaux une stratégie semblable à celle appliquée aux scalaires).

En effet, s'il est décidé d'appliquer une stratégie spéciale d'allocation dynamique de mémoire pour un type donné, alors il est peu probable qu'on souhaite laisser la mécanique normale de C++ se charger de l'opération correspondante de libération dynamique de mémoire-ce serait presque nécessairement voué à l'échec.

Quatre opérateurs peuvent donc être surchargés pour une classe donnée dans l'optique de contrôler la mécanique d'attribution dynamique de la mémoire.

class X {
   // ...
public:
   // ...
   void* operator new(size_t);
   void operator delete(void *p);
   void* operator new[](size_t);
   void operator delete[](void *p);
   // ...
};

Exemple – Une armée d'orques

Imaginons que nous oeuvrions à un jeu vidéo de type médiéval fantastique et que nous sachions d'avance que nous aurons à gérer, fréquemment, des armées d'orques (aussi nommées des hordes). Imaginons aussi que nous pensions être capables de profiter du fait que la taille d'un Orque est connue à la compilation (après tout, tout Orque occupe sizeof(Orque) bytes en mémoire!).

Nous mettrons ici en place un programme de test qui crée plusieurs instances de la classe Orque, les utilise (de manière fictive) puis les détruit à la pièce. Nous utiliserons aussi une allocation en bloc d'un tableau d'instances d'Orque (des renforts pour ceux déjà créés!) pour vérifier la qualité de l'implémentation de l'opérateur new[].

En contrepartie, nous utiliserons l'opérateur delete[] pour nettoyer les renforts, puis nous appellerons massivement l'opérateur delete pour éliminer les instances de Orque créées à la pièce en début de programme.

Une fois des mesures faites pour les versions standard des opérateurs new, new[], delete et delete[], nous implémenterons notre propre petit mécanisme maison pour gérer la mémoire allouée dynamiquement et nous mesurerons le programme résultant. Ceci nous permettra de voir l'impact de nos choix d'implémentation.

Mesurer la vitesse d'exécution des mécanismes de gestion de la mémoire

Pour mesurer la vitesse des mécanismes de gestion de la mémoire allouée dynamiquement dans leurs déclinaisons par défaut et maison, nous passerons par une fonction tester() comme celle décrite dans cet article. Par exemple, nous mesurerons le temps d'exécution d'une fonction f() quelconque comme suit.

// ...
template <class F, class ... Args>
   auto tester(F f, Args &&... args) {
      auto pre = high_resolution_clock::now();
      auto res = f(std::forward<Args>(args)...);
      auto post = high_resolution_clock::now();
      return pair{ res, post - pre };
   }
int main() {
   auto [dt,res] = tester([] {
      f();
   });
   // afficher le temps écoulé, logé dans dt
   // ...
}

Le Structured Binding [dt,res] déconstruit lau std::pair contenant le résultat du calcul réalisé par f() et le temps écoulé pendant son exécution. Ce temps écoulé sera typiquement converti pas un duration_cast dans l'unité de mesure souhaitée par le code client.

Décrire un Orque

Décrire un Orque est une chose simple en soi. Nous pourrions insérer un nom (une std::string), des points de vie et quelques attributs décoratifs et nous en tenir là.

Par principe, je vous proposerai ici une classe Orque légèrement plus complète et plus sérieuse, mais notez tout de suite que, pour nos fins, une version naïve aurait suffi-après tout, nous sommes intéressé(e)s par les mécanismes d'allocation dynamique de mémoire, pas par la représentation correcte d'une créature hideuse et agressive.

Tout Orque sera Frappable. Nous entendrons par là que chaque Orque sera voué à une existence violente et sera une créature de conflits, sujette à blesser et à être blessée.

#include <cassert>
#include <random>
mt19937& rand_();
/* Dans un .cpp :
mt19937& rand_() {
   using namespace std;
   static random_device rd;
   static mt19937 prng { rd() }; // not thread safe once constructed
   return prng;
}
*/
class Frappable {
public:
   using vie_t = short;
private:
   vie_t vie_;
public:
   static vie_t generer_points_vie() {
      std::uniform_int_distribution<int> de{ 5,20 }; // vie min,max
      return de(rand_());
   }
public:
   Frappable(vie_t vie = generer_points_vie()) : vie_{ vie } {
   }
   vie_t vie() const noexcept {
      return vie_;
   }
   bool est_decede() const noexcept {
      return vie() <= 0;
   }
   void endommager(vie_t degats) noexcept {
      assert(degats > 0);
      vie_ -= degats;
   }
   void guerir(vie_t soins) noexcept {
      assert(soins > 0);
      vie_ += soins;
   }
   virtual void frapper(Frappable&) = 0;
   virtual ~Frappable() = default;
};

sizeof(Frappable) +
   sizeof(short) +
      sizeof(std::string)

class Orque : public Frappable {
   enum {
      MECHANCETE_DEFAUT = 5
   };
   std::string nom_;
   short mechancete_;
   vie_t generer_degats() const noexcept {
      std::uniform_int_distribution<int> de{ 0,mechancete_ };
      return de(rand_());
   }
public:
   Orque(const std::string &nom = "Euh...") : nom_{ nom }, mechancete_{ MECHANCETE_DEFAUT } {
   }
   void frapper(Frappable &f) override {
      f.endommager(generer_degats());
   }
};

Ceci nous donne une classe Orque qui a au moins un minimum d'intérêt et dont chaque instance, en pratique, occupe probablement entre 30 et 40 bytes en mémoire, selon la plateforme et le compilateur.

Il nous faut maintenant un programme de test pour vérifier la vitesse à laquelle s'exécuteront les opérateurs d'allocation et de libération dynamique de mémoire dans leur déclinaison standard comme dans leur déclinaison maison.

#include "MesureDeTemps.h"
#include "Orque.h"
#include <iostream>
#include <list>
#include <string>
#include <algorithm>

int main() {
   using namespace std;
   uniform_int_distribution<int> de{ 0,1 };
   auto p = new Orque{ "Urg" };
   delete p;
   enum { N = 100'000 };
   list<Orque *> HordeNefaste;
   list<Orque *> HordeHorrible;

   auto r0 = tester([&]{
      for (int i = 0; i < N; ++i)
         if (de(rand_()))
            HordeNefaste.push_back(
               new Orque{ "Urg " + to_string(i) }
            );
         else
            HordeHorrible.push_back(
               new Orque{ "Arg " + to_string(i) }
            );
   });
   // ... affichage du temps écoulé...

Un combat s'ensuit. J'ai censuré ce tronçon pour les âmes sensibles, mais sachez qu'aucun Orque ne sera retiré de son conteneur pendant le combat (pour éviter de fausser les données lorsque nous mesurerons la performance de delete).

   Orque *pMoton = {};
   auto r1 = tester([&] {
      pMoton = new Orque[1000];
      // ...
   });
   // ... affichage du temps écoulé...

   auto r2 = tester([&] {
      delete[] pMoton;
      // ...
   });
   // ... affichage du temps écoulé...

// ...
   auto r3 = tester([&] {
      for(auto p : HordeHorrible) delete p;
      for(auto p : HordeNefaste) delete p;
   });
   // ... affichage du temps écoulé...
}

Tester le programme dans sa version actuelle permettra de connaître la vitesse d'exécution des quatre opérateurs standards de gestion de la mémoire allouée dynamiquement. Armés du résultat de ces tests, nous pourrons voir si nos propres opérateurs se comportent à la hauteur des attentes.

Implémenter les méthodes new, new[], delete et delete[] pour Orque

Nous allons maintenant implémenter des versions naïves (j'insiste!) des opérateurs de gestion de la mémoire allouée dynamiquement pour la classe Orque.

Étonnamment, nous obtiendrons des performances très similaires à celles obtenues par les opérateurs standard, ce qui suggère que nous pourrions faire beaucoup mieux si nous y investissions un peu plus d'énergie.

#ifndef ORQUE_H
#define ORQUE_H
#include <string>
#include <vector>
#include <algorithm>
#include <cassert>
template <class T>
   class Tribu {
      std::string nom_;
      std::vector<T *> membres_;
   public:
      void enregistrer(T *p) {
         assert(p);
         membres_.push_back(p);
      }
      void desenregistrer(T *) {
      }
      Tribu(const std::string &nom) : nom_{ nom } {
      }
   };
#include <cstdlib>
//
// class Frappable (omise; voir plus haut)
//
class Orque : public Frappable {
   //
   // seul ce qui a changé apparaît ici; voir
   // plus haut pour le reste
   //
   static Tribu<Orque> tribu;
public:
   Orque(const std::string &nom = "Euh...") : nom_{nom}, mechancete_{MECHANCETE_DEFAUT} {
      tribu.enregistrer(this);
   }
   ~Orque() {
      tribu.desenregistrer(this);
   }
   // ...
   void* operator new(size_t);
   void* operator new[](size_t);
   void operator delete(void *);
   void operator delete[](void *);
};

#endif

En pratique, il souvent est plus sage de spécialiser ces opérateurs en fonction d'un patron d'utilisation qu'en fonction de blocs de taille fixe. Cela dit, pour nos fins, travailler en fonction de blocs de taille sizeof(Orque) sera instructif.

L'implémentation de ces méthodes sera, elle aussi, relativement simple. Cette simplicité cache toutefois un effort de programmation un peu plus grand.

Tout d'abord, remarquons que toutes les stratégies d'allocation de mémoire reposant sur des blocs de taille fixe ont la particularité de reposer sur une mémoire à répartir dont la taille sera un multiple de la taille d'un seul bloc.

Nous utiliserons donc une classe générique spécialisée en ce sens, que nous nommerons ArenaFixe, et nous ferons en sorte que la classe Orque pige sa mémoire dans une ArenaOrque, un singleton spécialisant ArenaFixe pour des blocs de taille sizeof(Orque).

#include "Orque.h"
#include "ArenaFixe.h"
#include "Incopiable.h"

Tribu<Orque> Orque::tribu("Les garnements");
namespace {
   enum { POPULATION_MAX = 200'000 };
}
class ArenaOrque : public ArenaFixe<sizeof(Orque), ::POPULATION_MAX>, Incopiable {
   ArenaOrque() = default;
public:
   static ArenaOrque &get() {
      static ArenaOrque singleton;
      return singleton;
   }
};
void* Orque::operator new(size_t qte) {
   return ArenaOrque::get().allouer_un();
}
void* Orque::operator new[](size_t qte) {
   return ArenaOrque::get().allouer_n(qte / sizeof(Orque));
}
void Orque::operator delete(void *p) {
   ArenaOrque::get().liberer_un(p);
}
void Orque::operator delete[](void *p) {
   ArenaOrque::get().liberer_n(p);
}

La grande (et un peu plus complexe) question est donc : comment pourrait-on implémenter ArenaFixe? Une réponse simpliste mais opérationnelle suit.

Implémenter ArenaFixe – une approche possible

Nous mettrons en place une classe générique ArenaFixe basée sur deux paramètres :

• La taille d'un individu (d'un bloc de mémoire), et
• La population attendue (le nombre maximum de blocs prévus par le code client)

Cette stratégie est naïve pour plusieurs raisons, mais en partie du fait que nous ne mettrons aucun mécanisme en place pour réagir si la population réelle dépasse les prévisions du code client. Notre ArenaFixe manquera simplement de mémoire et lèvera un std::bad_alloc si cela se produit.

Dans une instance de la classe ArenaFixe proposée ici, on trouvera un bassin de mémoire disponible (bêtement : un bloc d'octets dont la taille est le produit de la population par la taille d'un individu). Nos blocs ne seront donc pas nécessairement alignés sur la taille d'un mot mémoire, ce qui peut ralentir l'utilisation que le code client fera d'eux.

Pour simplifier la recherche de blocs alloués, nous utiliserons une séquence de bits (un std::bitset) qui contiendra, de manière compacte, un bit par individu. Nous considérerons qu'un bit à zéro signifie que le bloc correspondant dans le bassin est libre.

Pour accélérer l'allocation de blocs en moyenne, nous conserverons la position du dernier bloc alloué dans un attribut (nommé plus_recent). Cette stratégie n'est pas sans faille (loin de là!) mais tend à accélérer l'allocation de mémoire en comparaison avec une stratégie qui chercherait toujours des blocs libres à partir du tout premier bloc du bassin.

La recherche d'un bloc libre se fera de manière cyclique à partir du plus récent bloc alloué. L'opération prochain() facilitera le passage d'un bloc à l'autre.

#ifndef ARENA_FIXE_H
#define ARENA_FIXE_H
#include <bitset>
#include <new>
template <size_t TailleBloc, size_t NBlocs> // discutable
   class ArenaFixe {
      static constexpr size_t TAILLE_BLOC = TailleBloc;
      static constexpr size_t NBLOCS = NBlocs;
      char bassin[TAILLE_BLOC * NBLOCS]; // discutable
      std::bitset<NBLOCS> pris;
      size_t tailles[NBLOCS]; // discutable
   public:
      using position_t = size_t;
   private:
      position_t plus_recent{};

Un std::bitset représente de manière compacte un nombre de bits fixé à la déclaration. Ici, le nombre de bits à représenter correspond, tel qu'annoncé, au nombre de blocs dans le bassin de mémoire disponible.

      static constexpr position_t prochain(position_t n) {
         return (n + 1) % NBLOCS;
      }

      size_t compter_disponibles(position_t base, position_t max_pas) {
         using std::bad_alloc;
         if (base + max_pas >= NB_BLOCS) throw bad_alloc{};
         auto cpt_pas = max_pas;
         while (!pris.test(base) && cpt_pas) {
            base = prochain(base);
            --cpt_pas;
         }
         return max_pas - cpt_pas;
      }

Remarquez le caractère potentiellement naïf de cette stratégie : si la recherche commence avec une base trop haute, il est possible que compter_disponibles() approche de la fin du bassin et lève un std::bad_alloc alors que le début du bassin contient peut-être assez de blocs disponibles pour servir une requête d'allocation.

Le throw ici est probablement trop hâtif; je doute qu'un try ... catch dans la méthode appelante soit acceptable étant donné le caractère fondamental et critique d'un mécanisme d'allocation de mémoire.

   public:
      void* allouer_un() {
         using std::bad_alloc;
         position_t i = prochain(plus_recent);
         while (pris.test(i) && i != plus_recent)
            i = prochain(i);
         if (i == plus_recent) throw bad_alloc{};
         pris.set(i);
         plus_recent = i;
         return bassin + i * TAILLE_BLOC;
      }

Le std::bitset permet de vérifier si un bloc est pris (méthode test()) et d'indiquer qu'un bloc a été pris (méthode set()).

      void* allouer_n(size_t n) {
         position_t i = 0;
         size_t nb_dispo = compter_disponibles(i, n);
         while (nb_dispo < n) {
            i += nb_dispo + 1;
            nb_dispo = compter_disponibles(i, n);
         }
         for (auto j = i, cpt = 0; cpt < n; j = prochain(j), ++cpt)
            pris.set(j);
         tailles[i] = n;
         plus_recent = i;
         return bassin + i * TAILLE_BLOC;
      }

L'une des difficultés de l'implémentation de stratégies d'allocation dynamique de mémoire est qu'elles doivent être à la fois sans failles et très efficaces. Un raffinement à la stratégie ci-dessus qui ralentirait un peu la recherche de blocs pourrait avoir un effet catastrophique sur la performance d'ensemble d'un programme.

      void liberer_un(const void *p) {
         position_t lequel = deduire_position(p);
         pris.set(lequel, false);
      }

      constexpr position_t deduire_position(const void *p) const {
         return static_cast<position_t>(
            static_cast<const char*>(p) - bassin
         ) / TAILLE_BLOC;
      }

      void liberer_n(const void *p) {
         auto lequel = deduire_position(p);
         const auto FIN = lequel + tailles[lequel];
         for (auto j = lequel; j < FIN; ++j)
            pris.set(j, false);
      }

      ArenaFixe() = default;
   };
#endif