Allocation dynamique de mémoire – Exemple

Notez que les équations dans ce document sont affichées à l'aide de MathJax.

Il est difficile d'enseigner convenablement et à l'aide d'exemples concrets comment il est possible de remplacer les mécanismes standards d'allocation et de libération dynamique de mémoire en C++, du fait que :

J'ai donc décidé de mettre en place une sorte de lieu pour expérimenter avec ces mécanismes. Il y a du travail à faire pour qui souhaitera utiliser ce qui suit, mais bon, j'ose espérer que cela rende service malgré tout.

Pour lire cet article, il est préférable que vous ayez quelques a priori, soit :

D'autres exemples de programmes remplaçant les mécanismes standards de gestion de la mémoire allouée dynamiquement sont disponibles sur ce site, donc Detection-Fuites--Observateur.html, allocateur_arenafixe.html, ArenaFixe.html et Detection-Fuites.html. Si vous êtes curieuse/ curieux...

Idée générale

Quelques mots sur l'approche générale suivie dans ce qui suit :

Le reste de cet article présente d'abord quelques outils généraux, réutilisables sans problème dans des programmes complètement différents de celui mis de l'avant ici, puis décrit les différentes entités plus spécifiquement associées au problème qui nous intéresse ici, soit celui de la spécialisation des outils de gestion de la mémoire allouée dynamiquement.

Outils généraux

Les outils présentés ici sont des structures de données réutilisables et des extensions à des en-têtes standards qui, pour mes fins, enrichissent l'offre de service standard et facilitent mon travail. Comme je l'indique souvent dans mes cours, (a) quand on peut nommer un problème ou une solution, il est souvent sage d'en faire une classe, et (b) quand on commence à écrire du code pour des cas particuliers, il est souvent plus simple d'écrire une solution générale propre et de voir par la suite s'il y a réellement lieu de donner dans le particulier – il est fréquent, dans les cas que je rencontre personnellement, que la solution générale propre fasse en fait très bien le travail.

Parfois, on a le visage tellement collé sur un problème qu'on le voit plus gros qu'il ne l'est réellement. Prendre un peu de recul et généraliser, plutôt que de coûter temps et énergie, tend à en épargner. Du moins, c'est mon petit vécu personnel.

J'ai rédigé static_stack<T,N> et static_queue<T,N> pour avoir en mains des structures de données simples et propres sans avoir à recourir à de l'allocation dynamique de mémoire, ce mécanisme étant celui que je souhaite spécialiser. Si sizeof(T)*N est gros, pensez allouer ces objets avec std::malloc() et utiliser la version positionnelle de new (le placement new) pour les initialiser correctement.

Pile de capacité statique – classe static_stack

Une static_stack<T,N> gère au maximum N instances de T dans une structure qui ne requiert pas d'allocation dynamique de mémoire.

Le code proposé ici est perfectible. en particulier, il serait possible d'éviter les affectations pour les remplacer par des appels au new positionnel. Cela dit, cette implémentation nous suffira.

 
#ifndef STATIC_STACK_H
#define STATIC_STACK_H
template <class T, int N>
   class static_stack {
   public:
      using value_type = T;
      using size_type = int;
      class Empty {};
      class Full {};
   private:
      value_type elems[N];
      size_type nelems {};
   public:
      static_stack() = default;
      constexpr bool empty() const noexcept {
         return !nelems;
      }
      bool full() const noexcept {
         return nelems == capacity();
      }
      static constexpr size_type capacity() noexcept {
         return N;
      }
      void push(const value_type &val) {
         if (full()) throw Full{};
         elems[nelems] = val;
         ++nelems;
      }
      value_type &top() {
         if (empty()) throw Empty{};
         return elems[nelems-1];
      }
      void pop() {
         if (empty()) throw Empty{};
         --nelems;
      }
   };
#endif

File de capacité statique – classe static_queue

Tout comme static_stack<T,N>, une static_queue<T,N> gère au maximum N instances de T dans une structure qui ne requiert pas d'allocation dynamique de mémoire.

Les remarques faites pour static_stack<T,N> sont aussi valides dans ce cas-ci. Le problème récurrent des files statiques est la distinction entre file vide et file pleine; plusieurs options sont possibles, et j'ai choisi l'une d'elle, qui me semblait plus simple à implémenter que les alternatives, soit celle de compter le nombre d'éléments insérés. Il n'était pas clair à mes yeux qu'en général, par exemple, insérer un noeud sentinelle entre le point d'écriture et le point de lecture serait preageux.

Notez que j'ai conservé les noms push(), pop() et top() par souci de conformité avec la pile; il aurait sans doute été plus sage de trouver des noms plus généraux, mais bon, j'ai commencé avec la pile et le reste fut mécanique.

 
#ifndef STATIC_QUEUE_H
#define STATIC_QUEUE_H
template <class T, int N>
   class static_queue {
   public:
      using value_type = T;
      using size_type = int;
      class Empty {};
      class Full {};
   private:
      value_type elems[N] {};
      size_type write{}, read{}, fillcount{};
      static constexpr size_type next(size_type n) noexcept {
         return (n + 1) % N;
      }
   public:
      static_queue() = default;
      constexpr bool empty() const noexcept {
         return !fillcount;
      }
      constexpr bool full() const noexcept {
         return fillcount == capacity();
      }
      static constexpr size_type capacity() noexcept {
         return N;
      }
      void push(const value_type &val) {
         if (full()) throw Full{};
         elems[write] = val;
         write = next(write);
         ++fillcount;
      }
      value_type &top() {
         if (empty()) throw Empty{};
         return elems[read];
      }
      void pop() {
         if (empty()) throw Empty{};
         read = next(read);
         --fillcount;
      }
   };
#endif

Extension à <new> – fichier new_ext.h et classe bad_alloc_of

Une allocation échouée lève traditionnellement std::bad_alloc en C++. Le standard C++ 11 permet toutefois de lever autre chose si nous le jugeons pertinent.

J'ai simplement ajouté une nouvelle classe, bad_alloc_of, capable d'entreposer le nombre de bytes demandé lors de l'échec d'une allocation dynamique de mémoire. Ainsi, il sera plus facile de produire de l'information signifiante lors des tests dans nos programmes.

 
#ifndef NEW_EXT_H
#define NEW_EXT_H
#include <cstddef>
struct bad_alloc_of {
   std::size_t value;
   bad_alloc_of(std::size_t n) noexcept : value{ n } {
   }
};
#endif

Extension à <algorithm> – fichier algorithm_ext.h

La plupart de mes projets incluent une extension ou une autre à ce superbement utile en-tête qu'est <algorithm>. Ce projet ne fera pas exception.

Pour mes fins dans ce projet, deux algorithmes généraux semblaient particulièrement pertinents, soit :

  • L'algorithme circular_distance(from, to, sz) qui retourne le nombre de pas dans présumant que le calcul se fasse sur des entiers modulo sz, et
  • L'algorithme largest_sequence_length(debut, fin, val), qui retourne la longueur de la plus longue séquence dans faite entièrement d'élément de valeur val

Ces deux algorithmes seront très utiles dans la recherche d'espace disponible dans la mémoire de nos programmes.

 

 
#ifndef ALGORITHM_EXT_H
#define ALGORITHM_EXT_H

#include <iterator>
#include <algorithm>
template <class T>
   constexpr T circular_distance(T from, T to, T sz) {
      return from <= to? to - from : sz - from + to;
   }
template <class It, class T>
   auto largest_sequence_length(It debut, It fin, const T &val) {
      using namespace std;
      using difference_type = typename
         iterator_traits<It>::difference_type;
      difference_type n{};
      for(debut = find(debut, fin, val);
          debut != fin;
          debut = find(debut, fin, val)) {
         auto p = find_if(debut, fin, [&val](const T &e){
            return e != val;
         });
         n = max(n, distance(debut, p));
         debut = p;
         if (debut != fin) ++debut;  
      }
      return n;
   }

#endif

Représenter la mémoire – classe memory_pool

Tel que mentionné plus haut, j'ai représenté la mémoire par un objet. Cela me donne plus de latitude pour mes tests, sans changer réellement ce qui concerne les stratégies d'allocation dynamique de mémoire et leur validation.

Fichier memory_pool.h

Pour refléter des conditions réelles de gestion de mémoire, j'ai défini ma classe memory_pool de manière à ce qu'il soit possible :

  • D'itérer sur de la mémoire brute (types memory_iterator et const_memory_iterator, qui correspondent à char* et à const char* pour itérer sur des bytes), et
  • De gérer des questions d'alignement en mémoire (car la plupart des ordinateurs imposent des règles pointues sur l'alignement en mémoire des objets; une simulation ne tenant pas compte de cette réalité serait d'une utilité restreinte)

Ici La méthode est_aligne(n) est vraie seulement pour des n qui sont un multiple de la taille du mot mémoire. Notez que pour gérer l'alignement des données en mémoire, C++ 11 offre des opérateurs nommés alignof() et alignas() que je vous invite à explorer pour faire mieux que cet exemple académique.

 
#ifndef MEMORY_POOL_H
#define MEMORY_POOL_H
#include <cstdlib>
#include <new>
#include <vector>
#include <algorithm>
#include <cassert>
#include <iosfwd>
class NotAvailable {};
class NotTaken {};
class NotAllocated {};
class InvalidCapacity {};
class memory_pool {
public:
   memory_pool(const memory_pool&) = delete;
   memory_pool& operator=(const memory_pool&) = delete;
   enum { TAILLE_MOT_MEMOIRE = 4 }; // +/- exact
   using memory_iterator = char*;
   using const_memory_iterator = const char*;
   using size_type = std::size_t;
   template <class T>
      constexpr bool est_aligne(T n) const {
         return n % TAILLE_MOT_MEMOIRE == 0;
      }

Pour comptabiliser les espaces alloués ou non, j'utiliserai :

  • Un tableau de booléens, où chaque élément true indique une adresse prise
  • La mémoire elle-même, mem_, de taille capacity_, et
  • Une liste de noeuds pris, pointée par tete_, pour faciliter la bonne gestion de la libération de la mémoire. Notez les fonctions creer() et detruire() qui passent par std::malloc() et std::free() pour éviter la récurrence à l'infini sur new et delete, et qui utilisent le new positionnel à l'interne pour initialiser de finaliser des instances de taken_node

La liste des noeuds utilisés repose sur une liste simplement chaînée.

J'utilise des outils primitifs pour gérer les ressources (listes chaînées programmées manuellement, tableaux dynamiques gérés « à bras ») parce que je souhaite éviter d'utiliser new, new[], delete et delete[], cherchant à éviter les interférences avec le code que je teste.

 
private:
   size_type cap;
   void *mem;
   bool *pris;
   struct taken_node {
      taken_node *next;
      char *debut;
      char *fin;
      taken_node(char *debut, char *fin) : debut{ debut }, fin{ fin }, next{} {
      }
   };
   taken_node *creer(memory_iterator debut, memory_iterator fin) {
      using namespace std;
      void *p = malloc(sizeof(taken_node));
      if (!p) throw bad_alloc{};
      return new (p) taken_node(debut, fin);
   }
   void detruire(taken_node *p) {
      assert(p);
      p->~taken_node(); // ICI
      free(p);
   }
   void clear_taken_nodes_list() {
      while (tete) {
         auto p = tete->next;
         detruire(tete);
         tete = p;
      }
   }
   taken_node *tete;

Certaines opérations de base sont implémentées pour un memory_pool. Notez que j'en ai fait un type incopiable mais déplaçable, sur lequel il est possibe d'itérer à la fois pour la mémoire brute et pour les adresses allouées.

La plupart des méthodes listées ici sont banales.

Notez qu'avec les versions contemporaines du langage C à tout le moins, free(nullptr) est sans effet.é

 
public:
   using iterator = bool*;
   using const_iterator = const bool*;
   memory_pool(size_type capacity) : cap{ capacity }, pris{}, tete{} {
      using namespace std;
      if (!est_aligne(cap)) throw InvalidCapacity{};
      mem = malloc(cap);
      if (!mem) throw bad_alloc{};
      pris = static_cast<bool*>(malloc(cap * sizeof(bool)));
      if (!pris) {
         free(mem);
         throw bad_alloc{};
      }
   }
   memory_pool(memory_pool && other)
      : cap{ std::exchange(other.cap, 0) },
        mem{ std::exchange(other.mem, nullptr) },
        tete{ std::exchange(other.tete, nullptr) },
        pris{ std::exchange(other.pris, nullptr) } {
   }
   void swap(memory_pool &other) {
      using std::swap;
      swap(cap, other.cap);
      swap(mem, other.mem);
      swap(tete, other.tete);
      swap(pris, other.pris);
   }
   memory_pool& operator=(memory_pool && other) {
      using std::exchange;
      if(this == &other) return *this;
      cap = exchange(other.cap, 0);
      mem = exchange(other.mem, nullptr);
      tete = exchange(other.tete, nullptr);
      pris = exchange(other.pris, nullptr);
      return *this;
   }
   ~memory_pool() {
      using std::free;
      free(mem);
      free(pris);
      clear_taken_nodes_list();
   }
   size_type size() const {
      return cap;
   }
   memory_iterator memory_begin() noexcept {
      return reinterpret_cast<memory_iterator>(mem);
   }
   const_memory_iterator memory_begin() const noexcept {
      return reinterpret_cast<const_memory_iterator>(const_cast<const void*>(mem));
   }
   memory_iterator memory_end() noexcept {
      return memory_begin() + size();
   }
   const_memory_iterator memory_end() const noexcept {
      return memory_begin() + size();
   }
   iterator begin() noexcept {
      return pris;
   }
   const_iterator begin() const noexcept {
      return pris;
   }
   iterator end() noexcept {
      return begin() + size();
   }
   const_iterator end() const noexcept {
      return begin() + size();
   }

Pour les fins de notre problème, les méthodes clés sont :

  • La méthode take(from, to), qui alloue la plage exprimés sous forme de positions, pas sous forme d'adresses. Notez que from doit être aligné sur le début d'un mémoire, et
  • La méthode give_back(from), qui libère la mémoire débutant à from exprimé en positions

J'ai aussi défini find_end_from(from) pour identifier la taille d'un bloc de mémoire allouée dynamiquement et débutant à la position from, pour que ce service (qui demande de connaître la structure de liste simplement chaînée d'instances de taken_node) soit implémenté à l'intérieur de la classe, évitant ainsi de la laisser percoler vers le code client.

 
   size_type find_end_from(size_type from) const {
      using it_type = memory_pool::const_memory_iterator;
      using std::distance;
      for (auto p = tete; p; p = p->next)
         if (distance(memory_begin(), const_cast<it_type>(p->debut)) == from)
            return distance(memory_begin(), const_cast<it_type>(p->fin));
      return size();
   }
   void* take(size_type from, size_type to) {
      using namespace std;
      assert(est_aligne(from));
      assert(all_of(next(begin(), from), next(begin(), to), [](bool taken) {
         return !taken;
      }));
      auto p = creer(next(memory_begin(), from), next(memory_begin(), to));
      p->next = tete;
      tete = p;
      fill(next(begin(), from), next(begin(), to), true);
      return p->debut;
   }
   void give_back(size_type from) {
      using namespace std;
      size_type to;
      if (distance(memory_begin(), tete->debut) == from) {
         to = distance(memory_begin(), tete->fin);
         auto p = tete;
         tete = tete->next;
         detruire(p);
      } else {
         auto p = tete;
         while (p->next && distance(memory_begin(), p->next->debut) != from)
            p = p->next;
         if (!p->next) throw NotAllocated{};
         to = distance(memory_begin(), p->next->fin);
         auto q = p->next;
         p->next = p->next->next;
         detruire(q);
      }
      assert(all_of(next(begin(), from), next(begin(), to), [](bool taken) {
         return taken;
      }));
      fill(next(begin(), from), next(begin(), to), false);
   }
   bool is_free(size_type n) const {
      return !pris[n];
   }
   size_type next_from(size_type n) const {
      return ++n, n == size() ? size_type() : n;
   }
   void reset() noexcept;
   friend void print_stats(const memory_pool&, std::ostream&);
};

#endif

Fichier memory_pool.cpp

L'implémentation de memory_pool a quelques particularités intéressantes :

  • La méthode reset() remet à neuf une zone mémoire, sans faire quelque finalisation que ce soit. Cela convient à notre environnement de test mais ne serait pas raisonnable en temps normal
  • La fonction somme_blocs_libres(), qui utilise la nouvelle syntaxe unifiée pour les fonctions sous C++ 11 et fait la somme des tailles des blocs de mémoire libre, et
  • La fonction print_stats(), qui envoie sur un flux des informations sur l'état de la mémoire allouée dynamiquement. J'ai pris le calcul du taux de fragmentation sur le Wiki portant sur ce sujet

J'ai utilisé quelques particularités intéressantes de C++ 11 au passage, dont les déclarations auto et les λ-expressions.

 
#include "memory_pool.h"
#include "algorithm_ext.h"
#include <algorithm>
#include <cassert>
#include <ostream>
using namespace std;
void memory_pool::reset() noexcept {
   fill(begin(), end(), false);
   fill(memory_begin(), memory_end(), 0);
   clear_taken_nodes_list();
}
auto somme_blocs_libres(const memory_pool &pool) {
   using difference_type = iterator_traits<
      memory_pool::const_iterator
   >::difference_type;
   difference_type n{};
   for (auto p = find(pool.begin(), pool.end(), false);
        p != pool.end();
        p = find(p, pool.end(), false))
   {
      auto q = find(p, pool.end(), true);
      n += distance(p, q);
      p = q;
   }
   return n;
};
void print_stats(const memory_pool &pool, ostream &os) {
   //
   os << "Espace occupe : ";
   const auto noccupes = count(pool.begin(), pool.end(), true);
   os << noccupes << '/' << pool.size() << " (taux : "
      << static_cast<double>(noccupes) / static_cast<double>(pool.size())
      << ")" << endl;
   //
   os << "Etat de la memoire ('*' si pris, '.' si disponible) :\n";
   for(auto pris : pool)
      os << (pris? '*' : '.');
   os << endl;
   //
   auto plus_gros_bloc_libre = largest_sequence_length(pool.begin(), pool.end(), false);
   os << "Plus gros espace contigu disponible : " << plus_gros_bloc_libre << "  bytes" << endl;
   //
   os << "Taux de fragmentation : "
      << (1.0 - static_cast<double>(plus_gros_bloc_libre) /
                static_cast<double>(somme_blocs_libres(pool)))
      << endl;
}

Fichier memory_pool_algorithms.h

Certains algorithmes s'appliquent de manière générale à mes zones de mémoire.

Ces algorithmes sont :

  • find_free_stride_from(pool, pos, n) qui retourne la position où commence une séquence de n bytes libres dans pool, cette recherche étant entreprise à partir de pos, et
  • find_next_free_from(pool, pos), qui retourne la prochaine position libre (et alignée sur un mot mémoire) dans pool
 
#ifndef MEMORY_POOL_ALGORITHMS_H
#define MEMORY_POOL_ALGORITHMS_H
#include "memory_pool.h"
#include <cstddef>
class NoRoom {};
memory_pool::size_type find_free_stride_from(
   const memory_pool&, memory_pool::size_type pos, std::size_t n
);
memory_pool::size_type find_next_free_from(
   const memory_pool&, memory_pool::size_type pos
);
#endif

Fichier bounded_accumulator.h

Fouiller en mémoire pour trouver un espace disponible demandait beaucoup de comptabilité à mes yeux, surtout considérant que j'aie utilisé une recherche circulaire (une fois la fin de la mémoire rencontrée, on poursuit au début). En conséquence, il importe de surveiller les débordements (une recherche cyclique revenant à son point de départ) pour éviter la recherche à l'infini d'espaces disponibles en mémoire.

Puisque je cherchais à découpler cette logique, lourde à mes yeux, du reste du code, j'ai défini bounded_accumulator, un accumulateur (entité « incrémentable ») dont la valeur plafond est identifiée à la construction.

Ce faisant, un dépassement de capacité (ou une boucle dépassant la taille de l'espace à explorer) lèvera une exception. Pour mes fins, le type de l'exception éventuellement levée est suppléé à la compilation.

 
#ifndef BOUNDED_ACCUMULATOR_H
#define BOUNDED_ACCUMULATOR_H
class HorsBornes {};
template <class T, class E = HorsBornes>
   class bounded_accumulator {
   public:
      using value_type = T;
   private:
      value_type cur, ubound;
      E excep;
   public:
      bounded_accumulator(const value_type &upper_bound, E excep = {}, const value_type &init = {})
         : cur{init}, ubound{upper_bound}, excep{excep}
      {
      }
      value_type upper_bound() const {
         return ubound;
      }
      value_type remaining() const {
         return upper_bound() - value();
      }
      bounded_accumulator& operator+=(const value_type &n) {
         if (remaining() < n) throw excep;
         cur += n;
         return *this;
      }
      bounded_accumulator& operator++() {
         if (!remaining()) throw excep;
         ++cur;
         return *this;
      }
      bounded_accumulator operator++(int) {
         bounded_accumulator temp{*this};
         operator++();
         return temp;
      }
      value_type value() const {
         return cur;
      }
      bool operator==(const bounded_accumulator &ba) const {
         return value() == ba.value();
      }
      bool operator!=(const bounded_accumulator &ba) const {
         return !(*this == ba);
      }
   };
#endif

Fichier memory_pool_algorithms.cpp

Les algorithmes vont un peu de soi, et peuvent être réutilisés et enrichis au besoin. Si vous avez des questions, n'hésitez pas à les poser à votre chic prof.

Il est probable que vous ayez des idées pour d'autres algorithmes de recherche dans de la mémoire disponible pour allocation dynamique. Amusez-vous! 

#include "memory_pool_algorithms.h"
#include "memory_pool.h"
#include "bounded_accumulator.h"
#include "new_ext.h"
#include "algorithm_ext.h"
#include <new>
#include <cstdlib>
#include <algorithm>
using namespace std;
memory_pool::size_type find_next_free_from(
   const memory_pool &pool, memory_pool::size_type pos
)
{
   if (pool.is_free(pos) && pool.est_aligne(pos)) return pos;
   auto p = pool.next_from(pos);
   while((!pool.is_free(p) && p != pos) || !pool.est_aligne(p))
      p = pool.next_from(p);
   if (!pool.is_free(p)) throw NoRoom();
   return p;
}
memory_pool::size_type find_free_stride_from(
   const memory_pool &pool, memory_pool::size_type pos, size_t n
)
{
   if (pos >= pool.size()) throw bad_alloc{};
   if (n >= pool.size()) throw bad_alloc{};
   auto might_fit = [](const memory_pool &pool, memory_pool::size_type p, size_t n) {
      return n <= pool.size() - p;
   };
   auto cur = find_next_free_from(pool, pos);
   bounded_accumulator<memory_pool::size_type, bad_alloc_of>
      nchecked (pool.size(), bad_alloc_of(n), circular_distance(pos, cur, pool.size()));
   auto circular_progress = [&](memory_pool::size_type curpos) -> memory_pool::size_type {
      while (!might_fit(pool, curpos, n) || !pool.est_aligne(curpos)) {
         pos = pool.next_from(curpos);
         curpos = find_next_free_from(pool, pos);
         nchecked += circular_distance(pos, curpos, pool.size()) + 1;
      }
      return curpos;
   };
   cur = circular_progress(cur);
   while (any_of(pool.begin() + cur, pool.begin() + cur + n, [](bool taken) { return taken; }))
      cur = circular_progress(pool.next_from(cur));
   return cur;
}

Encadrer les stratégies d'allocation – classe alloc_strategy

Pour « installer » et « désinstaller » des stratégies d'allocation, il nous faut pouvoir les entreposer en un lieu commun, donc leur donner un type en commun. La manière typique de faire cela est de dériver les diverses stratégies d'une stratégie plus abstraite, soit une interface – ici, j'irai un peu plus loin et j'utiliserai une classe abstraite, nommée alloc_strategy.

Fichier alloc_strategy.h

Pour cumuler des statistiques d'utilisation et de performance sur mes outils de gestion de mémoire, j'ai appliqué l'idiome NVI par lequel :

  • Le parent implémente des versions non-polymorphiques et publiques des services destinés au code client
  • Le parent déclare virtuelles (ici, abstraites) et protégées des méthodes qui seront implémentées par les enfants
  • Le parent encadre, à travers les méthodes publiques concrètes, l'utilisation des méthodes protégées. Ceci permet au parent de tirer des statistiques d'utilisation, par exemple, ou encore d'assurer le respect des préconditions et des postconditions des méthodes d'une interface pour les enfants

Je cumule des statistiques d'utilisation à l'aide de la classe interne et privée Stats. Pour mes fins, je conserve le nombre d'appels à new, new[], delete et delete[], de même que le temps écoulé pour chacun de ces appels.

 
#ifndef ALLOCSTRATEGY_H
#define ALLOCSTRATEGY_H
#include "memory_pool.h"
#include "memory_pool_algorithms.h"
#include <new>
#include <cstdlib>
#include <algorithm>
#include <iosfwd>
#include <chrono>
class alloc_strategy {
   memory_pool *pool_{};
   struct Stats {
      enum { NEW, NEWT, DEL, DELT, N };
      int nb[N];
      int qte[N];
      std::chrono::high_resolution_clock::duration elaps[N];
      constexpr Stats() : nb{ {} }, qte{ {} }, elaps{ {} } {
      }
   };
   Stats stats;


Chaque stratégie d'allocation connaît, dans mon implémentation, la mémoire avec laquelle elle transige. J'aurais pu valider que ce pointeur soit non-nul, mais pour une raison technique (j'ai au moins un cas de stratégie en tête qui n'a pas besoin de ce pointeur, et il s'agit du cas par défaut) je ne l'ai pas fait.

 
protected:
   memory_pool &pool() noexcept {
      return *pool_;
   }
public:
   alloc_strategy() = default;
   constexpr alloc_strategy(memory_pool *pool) : pool_{ pool } {
   }


Les services à implémenter pour chaque classe enfant sont les suivants :

  • allocate_one_impl(size_t) pour operator new(size_t)
  • allocate_block_impl(size_t) pour operator new[](size_t)
  • deallocate_one_impl(void*) pour operator delete(void*), et
  • deallocate_block_impl(void*) pour operator delete[](void*)

Dans chaque cas, la méthode non-polymorphique que le code client utilisera portera un nom plus simple (allocate_one() plutôt qu'allocate_one_impl(), par exemple) et encadrera l'appel de la version polymorphique par du code de collecte de données statistiques.

Le code se répète un peu; vous pouvez le retravailler pour réduire la redondance si le coeur vous en dit.

J'ai fait de print_stats() une fonction amie de cette classe pour qu'elle (et elle seule) puisse fouiller dans les statistiques accumulées. Ceci me permet de garder ces statistiques à l'interne, cachées, et de ne pas faire d'elles une partie de l'interface visible de la stratégie d'allocation. À mon avis, c'est la chose à faire.0

 
   void* allocate_one(std::size_t n) {
      using namespace std::chrono;
      auto pre = high_resolution_clock::now();
      void *p = allocate_one_impl(n);
      auto post = high_resolution_clock::now();
      ++stats.nb[Stats::NEW];
      stats.qte[Stats::NEW] += n;
      stats.elaps[Stats::NEW] += post - pre;
      return p;
   }
   void* allocate_one(std::size_t n, std::nothrow_t nt) noexcept {
      using namespace std::chrono;
      auto pre = high_resolution_clock::now();
      void *p = allocate_one_impl(n, nt);
      auto post = high_resolution_clock::now();
      ++stats.nb[Stats::NEW];
      stats.qte[Stats::NEW] += n;
      stats.elaps[Stats::NEW] += post - pre;
      return p;
   }
   void* allocate_block(std::size_t n) {
      using namespace std::chrono;
      auto pre = high_resolution_clock::now();
      void *p = allocate_block_impl(n);
      auto post = high_resolution_clock::now();
      ++stats.nb[Stats::NEWT];
      stats.qte[Stats::NEWT] += n;
      stats.elaps[Stats::NEWT] += post - pre;
      return p;
   }
   void* allocate_block(std::size_t n, std::nothrow_t nt) noexcept {
      using namespace std::chrono;
      auto pre = high_resolution_clock::now();
      void *p = allocate_block_impl(n, nt);
      auto post = high_resolution_clock::now();
      ++stats.nb[Stats::NEWT];
      stats.qte[Stats::NEWT] += n;
      stats.elaps[Stats::NEWT] += post - pre;
      return p;
   }
   void deallocate_one(void *p) noexcept {
      using namespace std;
      using namespace std::chrono;
      auto pre = high_resolution_clock::now();
      deallocate_one_impl(p);
      auto post = high_resolution_clock::now();
      ++stats.nb[Stats::DEL];
      stats.qte[Stats::DEL] -= pool().find_end_from(
         distance(
            pool().memory_begin(),
            static_cast<decltype(pool().memory_begin())>(p)
         )
      );
      stats.elaps[Stats::DEL] += post - pre;
   }
   void deallocate_one(void *p, std::nothrow_t nt) noexcept {
      using namespace std;
      using namespace std::chrono;
      auto pre = high_resolution_clock::now();
      deallocate_one_impl(p, nt);
      auto post = high_resolution_clock::now();
      ++stats.nb[Stats::DEL];
      stats.qte[Stats::DEL] -= pool().find_end_from(
         distance(
            pool().memory_begin(),
            static_cast<decltype(pool().memory_begin())>(p)
         )
      );
      stats.elaps[Stats::DEL] += post - pre;
   }
   void deallocate_block(void *p) noexcept {
      using namespace std;
      using namespace std::chrono;
      auto pre = high_resolution_clock::now();
      deallocate_block_impl(p);
      auto post = high_resolution_clock::now();
      ++stats.nb[Stats::DELT];
      stats.qte[Stats::DELT] -= pool().find_end_from(
         distance(
            pool().memory_begin(),
            static_cast<decltype(pool().memory_begin())>(p)
         )
      );
      stats.elaps[Stats::DELT] += post - pre;
   }
   void deallocate_block(void *p, std::nothrow_t nt) noexcept {
      using namespace std;
      using namespace std::chrono;
      auto pre = high_resolution_clock::now();
      deallocate_block_impl(p, nt);
      auto post = high_resolution_clock::now();
      ++stats.nb[Stats::DELT];
      stats.qte[Stats::DELT] -= pool().find_end_from(
         distance(
            pool().memory_begin(),
            static_cast<decltype(pool().memory_begin())>(p)
         )
      );
      stats.elaps[Stats::DELT] += post - pre;
   }
   virtual ~alloc_strategy() = default;
   friend void print_stats(const alloc_strategy &, std::ostream &);

Les fonctions que devront implémenter les enfants sont abstraites et respectent les signatures des opérateurs auxquelles elles correspondent. Notez que, conformément aux usages de l'idiome NVI, les noms les plus « jolis » ont été conservés pour les méthodes publiques, accessibles au code client.

 
protected:
   virtual void * allocate_one_impl(std::size_t) = 0;
   virtual void * allocate_one_impl(std::size_t, std::nothrow_t) noexcept = 0;
   virtual void * allocate_block_impl(std::size_t) = 0;
   virtual void * allocate_block_impl(std::size_t, std::nothrow_t) noexcept = 0;
   virtual void deallocate_one_impl(void *) noexcept = 0;
   virtual void deallocate_one_impl(void *, std::nothrow_t) noexcept = 0;
   virtual void deallocate_block_impl(void *) noexcept = 0;
   virtual void deallocate_block_impl(void *, std::nothrow_t) noexcept = 0;
};
#endif

Fichier alloc_strategy.cpp

La définition de print_stats() est présentée à droite. C'est une fonction somme toute banale.

 
#include "alloc_strategy.h"
#include <ostream>
#include <cassert>
#include <chrono>
using namespace std;
using namespace std::chrono;
void print_stats(const alloc_strategy &as, ostream &os) {
   os << "Nb. appels a new : " << as.stats.nb[alloc_strategy::Stats::NEW] << '\n'
      << "Nb. appels a new[] : " << as.stats.nb[alloc_strategy::Stats::NEWT] << '\n'
      << "Nb. appels a delete : " << as.stats.nb[alloc_strategy::Stats::DEL] << '\n'
      << "Nb. appels a delete[] : " << as.stats.nb[alloc_strategy::Stats::DELT] << '\n'
      << "Qte memoire allouee avec new : " << as.stats.qte[alloc_strategy::Stats::NEW] << " bytes\n"
      << "Qte memoire allouee avec new[] : " << as.stats.qte[alloc_strategy::Stats::NEWT] << " bytes\n";
   os << "Temps passe dans new : " 
      << duration_cast<milliseconds>(as.stats.elaps[alloc_strategy::Stats::NEW]).count() << " ms.\n"
      << "Temps passe dans new[] : " 
      << duration_cast<milliseconds>(as.stats.elaps[alloc_strategy::Stats::NEWT]).count() << " ms.\n"
      << "Temps passe dans delete : "
      << duration_cast<milliseconds>(as.stats.elaps[alloc_strategy::Stats::DEL]).count() << " ms.\n"
      << "Temps passe dans delete[] : "
      << duration_cast<milliseconds>(as.stats.elaps[alloc_strategy::Stats::DELT]).count() << " ms.";
}

Stratégie d'allocation spécifique – classe continuous_alloc_strategy

Pour démontrer une implémentation possible d'une stratégie d'allocation dynamique de mémoire, j'ai implémenté continuous_alloc_strategy. L'idée est simple : une instance de ce type se souvient de l'indice en mémoire où s'est terminée la dernière allocation de mémoire qu'elle a prise en charge. C'est de cet endroit que la prochaine tentative allocation sera entreprise. C'est une stratégie un peu naïve, rien d'optimal, mais ça fonctionne.

Fichier continuous_alloc_strategy.h

Comme vous pouvez le constater, dans l'infrastructure proposée ici, implémenter une stratégie d'allocation implique dériver d'alloc_strategy et implémenter les services qui y sont abstraits.

Notez que puisque les appels aux services polymorphiques sont faits dans le code de la classe parent, et puisque c'est la visibilité (public, protégé, privé) au point d'appel qui compte, les implémentations des diverses méthodes dans notre classe représentant une stratégie particulière peuvent être privées – et elles le sont.

 
#ifndef CONTINUOUS_ALLOC_STRATEGY_H
#define CONTINUOUS_ALLOC_STRATEGY_H
#include "alloc_strategy.h"
#include "memory_pool.h"
#include <cstddef>
#include <new>
class continuous_alloc_strategy : public alloc_strategy {
   memory_pool::size_type cur;
   void* allocate_one_impl(std::size_t);
   void* allocate_one_impl(std::size_t n, std::nothrow_t) noexcept;
   void* allocate_block_impl(std::size_t n);
   void* allocate_block_impl(std::size_t n, std::nothrow_t) noexcept;
   void deallocate_one_impl(void *p) noexcept;
   void deallocate_one_impl(void *p, std::nothrow_t) noexcept;
   void deallocate_block_impl(void *p) noexcept;
   void deallocate_block_impl(void *p, std::nothrow_t) noexcept;
public:
   continuous_alloc_strategy(memory_pool &pool) : alloc_strategy(&pool), cur{} {
   }
};
#endif

Fichier continuous_alloc_strategy.cpp

Les méthodes implémentant les divers services d'allocation et de libération dynamique de mémoire sont proposées à droite. La simplicité de la stratégie appliquée ici fait en sorte que le code soit chaque fois plutôt simple, et que je ne fais pas de distinction, avec cette implémentation, entre l'allocation de tableaux et l'allocation de scalaires.

Mes méthodes ne sont pas Exception-Neutral; elles ne laissent filtrer que des std::bad_alloc lors d'un problème d'allocation. Cependant, les exceptions sous-jacentes (p. ex. : NoRoom) servent à usage interne seulement, donc c'est un moindre mal.

Notez que j'utilise à l'occasion l'opérateur statique decltype de C++ 11, qui est charmant et exprime le type d'une expression sans évaluer la valeur de cette expression. C'est un outil franchement sympathique et qui permet d'épargner un effort considérable de confection de traits.

 
#include "continuous_alloc_strategy.h"
#include "memory_pool.h"
#include "memory_pool_algorithms.h"
#include <algorithm>
#include <iterator>
using namespace std;
void* continuous_alloc_strategy::allocate_one_impl(size_t n)
   try {
      auto pos = find_free_stride_from(pool(), cur, n);
      auto end = pos + n;
      cur = (end != pool().size())? end : memory_pool::size_type{};
      return pool().take(pos, end);
   } catch (NoRoom) {
      throw bad_alloc{};
   }

void* continuous_alloc_strategy::allocate_one_impl(size_t n, nothrow_t) noexcept
   try {
      return allocate_one_impl(n);
   } catch (...) {
      return nullptr;
   }

void* continuous_alloc_strategy::allocate_block_impl(size_t n)
   try {
      auto pos= find_free_stride_from(pool(), cur, n);
      auto end = pos + n;
      cur = (end != pool().size())? end : memory_pool::size_type{};
      return pool().take(pos, end);
   } catch (NoRoom) {
      throw bad_alloc{};
   }

void* continuous_alloc_strategy::allocate_block_impl(size_t n, nothrow_t) noexcept
   try {
      return allocate_block_impl(n);
   } catch (...) {
      return nullptr;
   }

void continuous_alloc_strategy::deallocate_one_impl(void *p) noexcept {
   pool().give_back(
      distance(
         pool().memory_begin(),
         static_cast<decltype(pool().memory_begin())>(p)
      )
   );
}

void continuous_alloc_strategy::deallocate_one_impl(void *p, nothrow_t) noexcept {
   pool().give_back(
      distance(
         pool().memory_begin(),
         static_cast<decltype(pool().memory_begin())>(p)
      )
   );
}

void continuous_alloc_strategy::deallocate_block_impl(void *p) noexcept {
   pool().give_back(
      distance(
         pool().memory_begin(),
         static_cast<decltype(pool().memory_begin())>(p)
      )
   );
}
void continuous_alloc_strategy::deallocate_block_impl(void *p, nothrow_t) noexcept {
   pool().give_back(
      distance(
         pool().memory_begin(),
         static_cast<decltype(pool().memory_begin())>(p)
      )
   );
}

Un dépôt de stratégies d'allocation – classe alloc_strategy

Tel que mentionné précédemment, j'utilise un Singleton nommé alloc_strategy pour gérer l'installation d'une stratégie X remplaçant une stratégie Y et la remise en place éventuelle de la stratégie Y lorsque l'utilisation de la stratégie X sera terminée.

Fichier alloc_strategy_depot.h

Le dépôt de stratégies d'allocation conserve un pointeur sur la stratégie d'allocation actuelle.

Étant donné qu'une approche RAII est appliquée (voir la classe interne switcher<S> pour installer la stratégie S, plus bas), il n'est pas nécessaire de tenir à jour une pile explicite de stratégies. C'est la beauté de cette technique dans un cas comme celui-ci.

 
#ifndef ALLOC_STRATEGY_DEPOT_H
#define ALLOC_STRATEGY_DEPOT_H
#include "alloc_strategy.h"
#include "new_ext.h"
#include <new>
#include <cstdlib>
#include <algorithm>
class NoStrategy {};
class alloc_strategy_depot {
   alloc_strategy *current{};

De manière cachée, j'utilise une stratégie par défaut, qui se limite à des appels à std::malloc() et à std::free() sur l'espace mémoire « normal », utilisant un pointeur nul en tant que memory_pool dans lequel puiser. À bien y penser, j'aurais probablement dû implémenter un memory_pool par défaut qui serait un Null Object plutôt que d'avoir recours à un pointeur nul.

 
   class DefaultStrategy : public alloc_strategy {
      void* allocate_one_impl(std::size_t n) {
         void *p = allocate_one_impl(n, std::nothrow);
         if (!p) throw bad_alloc_of{n};
         return p;
      }
      void* allocate_one_impl(std::size_t n, std::nothrow_t) noexcept {
         return std::malloc(n);
      }
      void* allocate_block_impl(std::size_t n) {
         void *p = allocate_block_impl(n, std::nothrow);
         if (!p) throw bad_alloc_of{n};
         return p;
      }
      void* allocate_block_impl(std::size_t n, std::nothrow_t) noexcept {
         return std::malloc(n);
      }
      void deallocate_one_impl(void *p) noexcept {
         std::free(p);
      }
      void deallocate_one_impl(void *p, std::nothrow_t) noexcept {
         std::free(p);
      }
      void deallocate_block_impl(void *p) noexcept {
         std::free(p);
      }
      void deallocate_block_impl(void *p, std::nothrow_t) noexcept {
         std::free(p);
      }
   public:
      DefaultStrategy() = default;
   };

La stratégie par défaut est installée à la construction du singleton. Par la suite, les appels aux méthodes du singleton délèguent leur implémentation vers les services de la stratégie d'allocation courante.

La méthode use() installe une stratégie d'allocation et retourne la précédente. Un switcher<S> installe une stratégie de type S (dérivée d'alloc_strategy, évidemment) et capture la précédente, pour la remettre en place lors de sa finalisation.

 
   static alloc_strategy_depot singleton;
   DefaultStrategy default_strategy;
   alloc_strategy_depot() {
      // placed here to avoid depending on initialization order
      current = &default_strategy;
   }
public:
   alloc_strategy_depot(const alloc_strategy_depot&) = delete;
   alloc_strategy_depot& operator=(const alloc_strategy_depot&) = delete;
   void* allocate_one(std::size_t n) {
      return current->allocate_one(n);
   }
   void* allocate_one(std::size_t n, std::nothrow_t nt) {
      return current->allocate_one(n, nt);
   }
   void* allocate_block(std::size_t n) {
      return current->allocate_block(n);
   }
   void* allocate_block(std::size_t n, std::nothrow_t nt) {
      return current->allocate_block(n, nt);
   }
   void deallocate_one(void *p) noexcept {
      current->deallocate_one(p);
   }
   void deallocate_one(void *p, std::nothrow_t nt) noexcept {
      current->deallocate_one(p, nt);
   }
   void deallocate_block(void *p) noexcept {
      current->deallocate_block(p);
   }
   void deallocate_block(void *p, std::nothrow_t nt) noexcept {
      current->deallocate_block(p, nt);
   }
   static alloc_strategy_depot &get() noexcept {
      return singleton;
   }
   alloc_strategy* use(alloc_strategy *p) {
      using std::swap;
      if (!p) throw NoStrategy{};
      swap(p, current);
      return p;
   }
   template <class S>
      class switcher {
         alloc_strategy *old;
      public:
         switcher(const switcher&) = delete;
         switcher& operator=(const switcher&) = delete;
         switcher(S &strat) : old(alloc_strategy_depot::get().use(&strat)) {
         }
         ~switcher() {
            alloc_strategy_depot::get().use(old);
         }
      };
};
#endif

Fichier alloc_strategy_depot.cpp

Enfin, le singleton déclaré dans le fichier d'en-tête reste à définir, ce que je fais ici dans un fichier source. D'autres approches sont possibles, bien sûr (voir pouvez consulter cet article sur les singletons statiques en C++ pour en savoir plus).

 
#include "alloc_strategy_depot.h"
alloc_strategy_depot alloc_strategy_depot::singleton;

Programme de test

Le programme de test se présente trois blocs, soit :

La surcharge des opérateurs est intimement liée à l'architecture qui les sous-tend. Dans mon cas, on parle de délégation des opérations aux services du singleton jouant le rôle de dépôt de stratégies.

Étant donné qu'un appel à operator delete ou à operator delete[] doit être inoffensif sur un pointeur nul, le code présenté à droite prend soin de traiter ce cas convenablement.

De même, un appel à new[] pour allouer un bloc de taille nulle est légal en C++, dans la mesure où chaque adresse retournée est distincte des autres. Conséquemment, nous faisons en sorte que toutes les allocations de tableaux, même sur une taille nulle, résulte en l'allocation d'au moins un byte.

 
#include "algorithm_ext.h"
#include "memory_pool.h"
#include "alloc_strategy_depot.h"
#include "continuous_alloc_strategy.h"
#include <new>
#include <iostream>
#include <algorithm>
#include <cstdlib>
using namespace std;

void* operator new(size_t n) {
   return alloc_strategy_depot::get().allocate_one(n);
}
void* operator new(size_t n, nothrow_t) {
   return alloc_strategy_depot::get().allocate_one(n, nothrow);
}
void* operator new[](size_t n) {
   return alloc_strategy_depot::get().allocate_block(max(static_cast<size_t>(1),n));
}
void* operator new[](size_t n, nothrow_t) {
   return alloc_strategy_depot::get().allocate_block(max(static_cast<size_t>(1),n), nothrow);
}
void operator delete(void *p) {
   if (!p) return;
   alloc_strategy_depot::get().deallocate_one(p);
}
void operator delete(void *p, nothrow_t) {
   if (!p) return;
   alloc_strategy_depot::get().deallocate_one(p, nothrow);
}
void operator delete[](void *p) {
   if (!p) return;
   alloc_strategy_depot::get().deallocate_block(p);
}
void operator delete[](void *p, nothrow_t) {
   if (!p) return;
   alloc_strategy_depot::get().deallocate_block(p, nothrow);
}

La stratégie de test impliquait beaucoup de code répétitif, alors je me suis permis le développement de quelques outils auxiliaires :

  • Pour afficher les noms des modèles comportementaux utilisés pour simuler un code client, j'ai utilisé des traits non pas sur des types, mais sur des templates. La syntaxe est particulière, mais je présume que si vous lisez ceci, c'est le genre de truc qui peut vous amuser
  • Puisque je cherche à valider le bon fonctionnement des mécaniques d'allocation dynamique de mémoire, et puisque je souhaite évaluer leurs performances, j'ai fait en sorte que les exceptions banales qui pourraient survenir dû à la nature des tests mais n'auraient pas trait au problème qui nous préoccupe soient « avalés » silencieusement. Ainsi, j'ai écrit de petits services génériques pour ajouter un scalaire ou un tableau à une structure comportementale et pour les enlever de ces structures. Ceci allège beaucoup le code de test
 
#include "static_stack.h"
#include "static_queue.h"
#include <cstdlib>
#include <string_view>

template <template <class, int> class>
   struct modele_allocation_traits;
template <>
   struct modele_allocation_traits<static_stack> {
      static constexpr auto nom() noexcept {
         using std::literals;
         return "Pile"sv;
      }
   };
template <>
   struct modele_allocation_traits<static_queue> {
      static constexpr auto nom() noexcept
         using std::literals;
         return "File"sv;
      }
   };

template <class T, int N, template <class, int> class M>
   void push_one(M<T*,N> &st, T val) {
      if (st.full()) return;
      st.push(new T{val});
   }
template <class T, int N, template <class, int> class M>
   void push_one_tab(M<T*,N> &st, int n) {
      if (st.full()) return;
      st.push(new T[n]);
   }
template <class T, int N, template <class, int> class M>
   void pop_one(M<T*,N> &st) {
      if (st.empty()) return;
      delete st.top();
      st.pop();
   }
template <class T, int N, template <class, int> class M>
   void pop_one_tab(M<T*,N> &st) {
      if (st.empty()) return;
      delete[] st.top();
      st.pop();
   }

Les tests en tant que tels vont comme suit :

  • Je nettoie tout d'abord la mémoire, pour faire en sorte que les tests soient tous faits sur un espace mémoire vierge
  • J'initialise le générateur de nombres pseudo-aléatoires à une valeur fixe. Ceci peut sembler étrange, mais l'idée ici est non pas d'avoir des nombres imprévisibles mais bien d'avoir un comportement « aléatoire » qui soit identique pour tous les tests, question de comparer des pommes avec des pommes et des oranges avec des oranges
  • J'instancie ensuite une stratégie applicable sur une mémoire particulière, et je l'installe de manière RAII (pour qu'elle soit automatiquement désinstallée en fin de parcours)
  • Pour le reste, de manière équiprobable, j'alloue ou je libère dynamiquement de la mémoire, que ce soit pour des scalaires ou pour des tableaux de taille variable. J'ai choisi d'utiliser des types primitifs pour que la finalisation ne soit pas un problème (pour que « nettoyer » la mémoire n'implique que la remplir de zéros, pas identifier les destructeurs les plus appropriés; nous testons une mécanique d'allocation, après tout)
  • Le nombre de tests utilisé ici est arbitraire. À partir de quelques tests maison, j'ai pu constater qu'une exception résultant d'une fragmentation excessive de la mémoire disponible survenait pre ce seuil dans chaque cas. Un for ever (exprimé typiquement sur la forme for(;;)) aurait aussi fait le boulot

Les nombres pseudoaléatoires utilisés dans cet exemple ne sont pas rigoureux, mais cela n'importe pas vraiment ici. Cependant, vous êtes invité(e)s à raffiner le tout à l'aide des outils plus contemporains et de meilleure qualité que vous trouverez dans <random>.

 
template <class S, template <class, int> class M>
   void test_strategy(memory_pool &pool, std::ostream &os) {
      os << "\n-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-\n\n"
         << "Test d'allocation dynamique memoire.\nModele comportemental : "
         << modele_allocation_traits<M>::nom() << endl;
      pool.reset();
      srand(0); // volontaire
      S strategy{pool};
      alloc_strategy_depot::switcher<S> asw(strategy);
      int i;
      try {
         M<int*, 100> ints;
         M<short*, 100> shorts;
         M<char*, 100> chars;
         M<int*, 100> tints;
         M<short*, 100> tshorts;
         M<char*, 100> tchars;
         for (i = 0; i < 300; ++i) {
            if (rand() % 2)
               switch(rand() % 6) {
               case 0:
                  push_one(ints, 3);
                  break;
               case 1:
                  push_one(shorts, short(-2));
                  break;
               case 2:
                  push_one(chars, 'A');
                  break;
               case 3:
                  push_one_tab(tints, rand() % 20 + 10);
                  break;
               case 4:
                  push_one_tab(tshorts, rand() % 20 + 10);
                  break;
               case 5:
                  push_one_tab(tchars, rand() % 20 + 10);
                  break;
               }
            else
               switch(rand() % 6) {
               case 0:
                  pop_one(ints);
                  break;
               case 1:
                  pop_one(shorts);
                  break;
               case 2:
                  pop_one(chars);
                  break;
               case 3:
                  pop_one_tab(tints);
                  break;
               case 4:
                  pop_one_tab(tshorts);
                  break;
               case 5:
                  pop_one_tab(tchars);
                  break;
               }
         }
      } catch (bad_alloc_of &bao) {
         os << "Echec d'allocation, iteration " << i
            << " pour une tentative d'allocation de "
            << bao.value << " bytes\n";
      } catch (...) {
         os << "Echec d'allocation, iteration " << i
            << " pour une tentative d'allocation de ??? bytes\n";
      }
      print_stats(pool, os);
      print_stats(strategy, os);
      os << endl;
   }

Enfin, le programme principal réalise les tests. J'ai utilisé chaque fois le même espace mémoire, d'une petite capacité (1000 bytes) pour que l'affichage soit plus utile pédagogiquement, mais je vous invite à modifier ce paramètre pour expérimenter.

 
int main() {
   enum { CAPACITE = 1000 };
   memory_pool pool(CAPACITE);
   test_strategy<continuous_alloc_strategy, static_stack>(pool, std::cout);
   test_strategy<continuous_alloc_strategy, static_queue>(pool, std::cout);
}

Les résultats affichés à la sortie standard sur mon petit ordinateur portatif vont comme suit. En mode Debug :

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

Test d'allocation dynamique memoire.
Modele comportemental : Pile
Echec d'allocation, iteration 171 pour une tentative d'allocation de 92 bytes
Espace occupe : 609/1000 (taux : 0.609)
Etat de la memoire ('*' si pris, '.' si disponible) :
........................******************************************..**..********
********************************************************************************
************................**..............................**..****************
**********......................**......**************************..**..........
....................*...........................................................
*****.......................................................................****
*********...********************************************************************
************************....................................................****
************************************************************************........
................................**********************************************..
**..**..******************************************..**********************..****
******************************************************......********************
**************************..............
Plus gros espace contigu disponible : 71  bytes
Taux de fragmentation : 0.818414
Nb. appels a new : 34
Nb. appels a new[] : 46
Nb. appels a delete : 24
Nb. appels a delete[] : 32
Qte memoire allouee avec new : 79 bytes
Qte memoire allouee avec new[] : 2041 bytes
Temps passe dans new : 4.02495 ms.
Temps passe dans new[] : 44.3591 ms.
Temps passe dans delete : 1.52107 ms.
Temps passe dans delete[] : 9.10346 ms.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

Test d'allocation dynamique memoire.
Modele comportemental : File
Echec d'allocation, iteration 225 pour une tentative d'allocation de 108 bytes
Espace occupe : 690/1000 (taux : 0.69)
Etat de la memoire ('*' si pris, '.' si disponible) :
................................................********************************
******************......................****************************************
****************........................****************************************
********************************************************************************
****************************************************............................
........................******************************************************..
**********************************************..********************************
**********************..********************************************************
***************************************************************.**..............
**..............*...******..**..........**************************..............
........**......**************************..**..**..****************************
********************................................******..................****
**********..............................
Plus gros espace contigu disponible : 52  bytes
Taux de fragmentation : 0.832258
Nb. appels a new : 46
Nb. appels a new[] : 60
Nb. appels a delete : 33
Nb. appels a delete[] : 43
Qte memoire allouee avec new : 107 bytes
Qte memoire allouee avec new[] : 2624 bytes
Temps passe dans new : 5.40474 ms.
Temps passe dans new[] : 41.639 ms.
Temps passe dans delete : 2.02421 ms.
Temps passe dans delete[] : 11.6965 ms.

En mode Release, maintenant :

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

Test d'allocation dynamique memoire.
Modele comportemental : Pile
Echec d'allocation, iteration 171 pour une tentative d'allocation de 92 bytes
Espace occupe : 609/1000 (taux : 0.609)
Etat de la memoire ('*' si pris, '.' si disponible) :
........................******************************************..**..********
********************************************************************************
************................**..............................**..****************
**********......................**......**************************..**..........
....................*...........................................................
*****.......................................................................****
*********...********************************************************************
************************....................................................****
************************************************************************........
................................**********************************************..
**..**..******************************************..**********************..****
******************************************************......********************
**************************..............
Plus gros espace contigu disponible : 71  bytes
Taux de fragmentation : 0.818414
Nb. appels a new : 34
Nb. appels a new[] : 46
Nb. appels a delete : 24
Nb. appels a delete[] : 32
Qte memoire allouee avec new : 79 bytes
Qte memoire allouee avec new[] : 2041 bytes
Temps passe dans new : 0.0870921 ms.
Temps passe dans new[] : 0.215949 ms.
Temps passe dans delete : 0.0570603 ms.
Temps passe dans delete[] : 0.0901651 ms.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

Test d'allocation dynamique memoire.
Modele comportemental : File
Echec d'allocation, iteration 225 pour une tentative d'allocation de 108 bytes
Espace occupe : 690/1000 (taux : 0.69)
Etat de la memoire ('*' si pris, '.' si disponible) :
................................................********************************
******************......................****************************************
****************........................****************************************
********************************************************************************
****************************************************............................
........................******************************************************..
**********************************************..********************************
**********************..********************************************************
***************************************************************.**..............
**..............*...******..**..........**************************..............
........**......**************************..**..**..****************************
********************................................******..................****
**********..............................
Plus gros espace contigu disponible : 52  bytes
Taux de fragmentation : 0.832258
Nb. appels a new : 46
Nb. appels a new[] : 60
Nb. appels a delete : 33
Nb. appels a delete[] : 43
Qte memoire allouee avec new : 107 bytes
Qte memoire allouee avec new[] : 2624 bytes
Temps passe dans new : 0.175232 ms.
Temps passe dans new[] : 0.309816 ms.
Temps passe dans delete : 0.0771746 ms.
Temps passe dans delete[] : 0.24633 ms.

Et voilà!

Valid XHTML 1.0 Transitional

CSS Valide !