Les allocateurs depuis C++ 11

Les allocateurs ont été introduits dans C++ pour permettre au code client d'utiliser un conteneur tel que std::list<T> ou std::vector<T> tout en contrôlant les mécanismes d'allocation (et de libération) dynamique de mémoire.

Écrire un allocateur pour un conteneur avec C++ 03 est une tâche relativement complexe. Outre un ensemble d'alias (pour les types internes et publics que sont value_type, pointer, reference, const_pointer, const_reference, etc.), il faut écrire plusieurs méthodes dont :

ServiceRôle
void construct(pointer p,const_reference r)

Initialise la mémoire pointée par p avec une copie de l'objet auquel r réfère (typiquement : new(static_cast<void*>(p))T(r))

void destroy(pointer p)

Finalise l'objet pointé par p (typiquement : p->~T())

pointer allocate(size_type n,pointer p = {})

Alloue l'espace pour n éléments contigus en mémoire (n'appelle aucun constructeur). Le paramètre p est un indice pour que le conteneur puisse suggérer à l'allocateur un endroit où commencer à chercher, ce qui peut être utile pour une pile par exemple. Implémentation possible :

auto p = malloc(n * sizeof(T));
if (!p) throw bad_alloc{};
return static_cast<T*>(p);
void deallocate(pointer p,size_type n)

Libère l'espace pour n éléments débutant à l'adresse p (n'appelle aucun destructeur). Implémentation possible :

free(p);
typename rebind<U>::other

Permet de cloner un type d'allocateur donné, dans la mesure où ce type est sans états (Stateless)

pointer address(reference r)
const_pointer address(const_reference r)

Retournent un « pointeur » (ou ce qui tient lieu de pointeur pour cet allocateur) sur r (typiquement : return &r;)

Notez que si les fonctions de bas niveau (::operator new, std::malloc()) calculent l'espace en bytes, les allocateurs sont typés et calculent l'espace en nombre d'éléments.

Un allocateur complet (mais simpliste, déléguant ses tâches vers std::malloc() et std::free()) pour C++ 03 (mais écrit pour C++ 11, pour alléger le tout) serait :

// ... inclusions et using ...
template <class T>
   struct tit_allocateur {
      using value_type = T;
      using pointer = T*;
      using const_pointer = const T*;
      using reference = T&;
      using const_reference = const T&;
      using size_type = std::size_t;
      using difference_type = std::ptrdiff_t;
      constexpr size_type max_size() const {
         return std::numeric_limits<size_type>::max(); // bof
      }
      template <class U>
         struct rebind {
            using other = tit_allocateur<U>;
         };
      constexpr pointer address(reference r) const {
         return &r;
      }
      constexpr const_pointer address(const_reference r) const {
         return &r;
      }
      pointer allocate(size_type n) {
         auto p = static_cast<pointer>(malloc(n * sizeof(value_type)));
         if (!p) throw std::bad_alloc{};
         return p;
      }
      void deallocate(pointer p, size_type) {
         free(p);
      }
      void construct(pointer p, const_reference r) {
         new (static_cast<void*>(p)) value_type{r};
      }
      void destroy(const_pointer p) {
         p->~value_type();
      }
   };

template <class T, class U>
   constexpr bool operator==(const tit_allocateur<T>&, const tit_allocateur<U>&) {
      return true;
   }
template <class T, class U>
   constexpr bool operator!=(const tit_allocateur<T>&, const tit_allocateur<U>&) {
      return false;
   }

Depuis C++ 11, écrire un allocateur est plus simple, du moins de prime abord. Pour atteindre un résultat équivalent à ce qui précède, le code minimal requis est :

template <class T>
   struct allocateur_minimaliste {
      using value_type = T;
      allocateur_minimaliste(/*ctor args*/) = default;
      template <class U>
         allocateur_minimaliste(const allocateur_minimaliste<U> &) {
         }
      value_type* allocate(std::size_t n) {
         auto p = static_cast<value_type*>(std::malloc(n * sizeof(T)));
         if (!p) throw std::bad_alloc{};
         return p;
      }
      void deallocate(value_type *p, std::size_t) {
         free(p);
      }
   };

template <class T, class U>
   constexpr bool operator==(const allocateur_minimaliste<T>&, const allocateur_minimaliste<U>&) {
      return true;
   }
template <class T, class U>
   constexpr bool operator!=(const allocateur_minimaliste<T>&, const allocateur_minimaliste<U>&) {
      return false;
   }

Le reste de la classe est déduit par des traits (type std::allocator_traits<T>).

Exemple plus complet – allocateur séquentiel sur un tampon

Le code qui suit est un exemple « niché », qui utilise un allocateur pour administrer une zone placée délibérément sur la pile d'exécution du thread client. Vous remarquerez qu'il est incomplet, au sens où la copie d'un tel allocateur causerait des dégâts, et au sens où plusieurs cas d'utilisation envisageables (par exemple, utiliser un allocateur pour un conteneur utilisant des noeuds comme une list<T> ou un set<T>) ne fonctionneraient pas (essayez de comprendre pourquoi, et contactez-moi si vous n'y parvenez pas).

Vous remarquerez entre autres que le code de test fait un reserve() avant de procéder à des insertions dans le conteneur. Ceci est dû au fait que le code de test remplit complètement le tampon réservé pour cette fin, et au fait que des insertions successives dans un conteneur où la mémoire n'a pas été allouée d'avance peut entraîner plusieurs réallocations. En contrepartie, ce code de test simpliste ne met pas en valeur la vitesse de la fonction allocate(), qui n'est appelée qu'une seule fois.

Enfin, si vous souhaitez utiliser cet allocateur avec Visual Studio, sachez que par défaut, en mode Debug, leur compilateur utilise des objets proxy sous la couverture, et n'alloue pas vraiment le type que vous souhaitez allouer, ce qui brise la stratégie utilisée ici (qui dépend d'une connaissance de la taille des objets alloués). Ce comportement ne survient pas en mode Release. Si vous souhaitez appliquer une technique de ce genre en mode Debug (pour fins de test est de mise au point, par exemple), prenez soin d'ajouter la macro suivante à votre programme :

#define _ITERATOR_DEBUG_LEVEL 0

Ceci évitera le recours aux itérateurs proxy que la bibliothèque standard proposée par Microsoft préconise.

Pour mieux comprendre le fonctionnement des allocateurs depuis C++ 11, et pour voir les avantages d'une spécialisation des allocateurs pour un programme donné, examinons le cas d'un allocateur séquentiel sur un tampon. Ses caractéristiques sont :

Une implémentation possible serait :

template <class T>
   struct buffered_sequential_allocator {
      char *buf, *cur;
      std::size_t size;
      using value_type = T;
      buffered_sequential_allocator(const buffered_sequential_allocator&) = default;
      buffered_sequential_allocator(buffered_sequential_allocator&&) = default;
      buffered_sequential_allocator(char *buf, std::size_t size) : buf{ buf }, cur{ buf }, size{ size } {
      }
      template <class U>
      buffered_sequential_allocator(const buffered_sequential_allocator<U> &other) {
         cout << "T : " << typeid(T).name() << ", U : " << typeid(U).name() << endl;
         buf = other.buf;
         cur = other.cur;
         size = other.size;
      }
      value_type* allocate(std::size_t n) {
         if (cur + n * sizeof(value_type) > buf + size)
            return static_cast<value_type*>(::operator new(n)); // ICI: fuite volontaire
         auto p = cur;
         cur += n * sizeof(value_type);
         return reinterpret_cast<value_type*>(p);
      }
      void deallocate(value_type *, std::size_t) {
         // no-op
      }
   };

Je pense que vous conviendrez que c'est relativement simple. Comparons maintenant trois allocateurs :

Notre programme de test sera :

template <class C, class ... Args>
   void test(C & cont, int n, Args && ... args) {
      for (int i = 0; i < n; ++i)
         cont.emplace_back(std::forward<Args>(args)...);
   }

int main() {
   enum { N = 50'000 };
   enum : size_t { BUFSIZE = N * sizeof(double) };
   alignas (double) char buffer[BUFSIZE];
   buffered_sequential_allocator<double> ze_alloc(&buffer[0], BUFSIZE);

   auto avant = high_resolution_clock::now();
   {
      vector<double> v; // standard
      v.reserve(N);
      test(v, N, 3.5);
   }
   auto apres = high_resolution_clock::now();
   auto temps = apres - avant;
   cout << "Vanille. Ecoule: " << duration_cast<microseconds>(temps).count() << " us." << endl;
   //
   //
   //
   avant = high_resolution_clock::now();
   {
      vector<double, tit_allocateur<double>> v; // devrait être plus lent, mais c'est une démo
      v.reserve(N);
      test(v, N, 3.5);
   }
   apres = high_resolution_clock::now();
   temps = apres - avant;
   cout << "Tit allocateur. Ecoule: " << duration_cast<microseconds>(temps).count() << " us." << endl;
   //
   //
   //
   avant = high_resolution_clock::now();
   {
      vector<double, allocateur_minimaliste<double>> v; // devrait être plus lent, mais c'est une démo
      v.reserve(N);
      test(v, N, 3.5);
   }
   apres = high_resolution_clock::now();
   temps = apres - avant;
   cout << "Minimaliste. Ecoule: " << duration_cast<microseconds>(temps).count() << " us." << endl;
   //
   //
   //
   avant = high_resolution_clock::now();
   {
      vector<double, buffered_sequential_allocator<double>> v{ ze_alloc }; // ICI
      v.reserve(N);
      test(v, N, 3.5);
   }
   apres = high_resolution_clock::now();
   temps = apres - avant;
   cout << "Buffered-sequential. Ecoule: " << duration_cast<microseconds>(temps).count() << " us." << endl;
}

Pour chacun des trois types d'allocateurs, nous réalisons les mêmes opérations :

À l'exécution, nous obtiendrons :

Vanille. Ecoule: 213 us.
Tit allocateur. Ecoule: 151 us.
Minimaliste. Ecoule: 152 us.
Buffered-sequential. Ecoule: 164 us.

Le code de test ne met pas en valeur notre allocateur sur la pile, du fait qu'il fait un seul reserve() (je n'ai pas pris soin de réserver suffisamment d'espace sur la pile pour accepter plusieurs appels à allocate() dû à la réallocation provoquée par de multiples appels à emplace_back()), mais montre ce qu'il est possible de faire.

Pour vous faciliter la vie, le programme entier suit (ceci est un exemple, pas du code de production!) :

#include <vector>
#include <chrono>
#include <iostream>
#include <cassert>
#include <typeinfo>
using namespace std;
using namespace std::chrono;

template <class T>
   struct tit_allocateur {
      using value_type = T;
      using pointer = T*;
      using const_pointer = const T*;
      using reference = T&;
      using const_reference = const T&;
      using size_type = std::size_t;
      using difference_type = std::ptrdiff_t;
      constexpr size_type max_size() const {
         return std::numeric_limits<size_type>::max(); // bof
      }
      template <class U>
      struct rebind {
         using other = tit_allocateur<U>;
      };
      constexpr pointer address(reference r) const {
         return &r;
      }
      constexpr const_pointer address(const_reference r) const {
         return &r;
      }
      pointer allocate(size_type n) {
         auto p = static_cast<pointer>(malloc(n * sizeof(value_type)));
         if (!p) throw std::bad_alloc{};
         return p;
      }
      void deallocate(pointer p, size_type) {
         free(p);
      }
      void construct(pointer p, const_reference r) {
         new (static_cast<void*>(p)) value_type{ r };
      }
      void destroy(const_pointer p) {
         p->~value_type();
      }
   };

template <class T, class U>
   constexpr bool operator==(const tit_allocateur<T>&, const tit_allocateur<U>&) {
      return true;
   }
template <class T, class U>
   constexpr bool operator!=(const tit_allocateur<T>&, const tit_allocateur<U>&) {
      return false;
   }

template <class T>
   struct allocateur_minimaliste {
      using value_type = T;
      allocateur_minimaliste(/*ctor args*/) = default;
      template <class U>
      allocateur_minimaliste(const allocateur_minimaliste<U> &) {
      }
      value_type* allocate(std::size_t n) {
         auto p = static_cast<value_type*>(std::malloc(n * sizeof(T)));
         if (!p) throw std::bad_alloc{};
         return p;
      }
      void deallocate(value_type *p, std::size_t) {
         free(p);
      }
   };

template <class T, class U>
   constexpr bool operator==(const allocateur_minimaliste<T>&, const allocateur_minimaliste<U>&) {
      return true;
   }
template <class T, class U>
   constexpr bool operator!=(const allocateur_minimaliste<T>&, const allocateur_minimaliste<U>&) {
      return false;
   }

template <class T>
   struct buffered_sequential_allocator {
      char *buf, *cur;
      std::size_t size;
      using value_type = T;
      buffered_sequential_allocator(const buffered_sequential_allocator&) = default;
      buffered_sequential_allocator(buffered_sequential_allocator&&) = default;
      buffered_sequential_allocator(char *buf, std::size_t size) : buf{ buf }, cur{ buf }, size{ size } {
      }
      template <class U>
      buffered_sequential_allocator(const buffered_sequential_allocator<U> &other) {
         cout << "T : " << typeid(T).name() << ", U : " << typeid(U).name() << endl;
         buf = other.buf;
         cur = other.cur;
         size = other.size;
      }
      value_type* allocate(std::size_t n) {
         if (cur + n * sizeof(value_type) > buf + size)
            return static_cast<value_type*>(::operator new(n)); // ICI: fuite volontaire
         auto p = cur;
         cur += n * sizeof(value_type);
         return reinterpret_cast<value_type*>(p);
      }
      void deallocate(value_type *, std::size_t) {
         // no-op
      }
   };

template <class C, class ... Args>
   void test(C & cont, int n, Args && ... args) {
      for (int i = 0; i < n; ++i)
         cont.emplace_back(std::forward<Args>(args)...);
   }

int main() {
   enum { N = 50'000 };
   enum : size_t { BUFSIZE = N * sizeof(double) };
   alignas (double) char buffer[BUFSIZE];
   buffered_sequential_allocator<double> ze_alloc(&buffer[0], BUFSIZE);

   auto avant = high_resolution_clock::now();
   {
      vector<double> v; // standard
      v.reserve(N);
      test(v, N, 3.5);
   }
   auto apres = high_resolution_clock::now();
   auto temps = apres - avant;
   cout << "Vanille. Ecoule: " << duration_cast<microseconds>(temps).count() << " us." << endl;
   //
   //
   //
   avant = high_resolution_clock::now();
   {
      vector<double, tit_allocateur<double>> v; // devrait être plus lent, mais c'est une démo
      v.reserve(N);
      test(v, N, 3.5);
   }
   apres = high_resolution_clock::now();
   temps = apres - avant;
   cout << "Tit allocateur. Ecoule: " << duration_cast<microseconds>(temps).count() << " us." << endl;
   //
   //
   //
   avant = high_resolution_clock::now();
   {
      vector<double, allocateur_minimaliste<double>> v; // devrait être plus lent, mais c'est une démo
      v.reserve(N);
      test(v, N, 3.5);
   }
   apres = high_resolution_clock::now();
   temps = apres - avant;
   cout << "Minimaliste. Ecoule: " << duration_cast<microseconds>(temps).count() << " us." << endl;
   //
   //
   //
   avant = high_resolution_clock::now();
   {
      vector<double, buffered_sequential_allocator<double>> v{ ze_alloc }; // ICI
      v.reserve(N);
      test(v, N, 3.5);
   }
   apres = high_resolution_clock::now();
   temps = apres - avant;
   cout << "Buffered-sequential. Ecoule: " << duration_cast<microseconds>(temps).count() << " us." << endl;
}

Lectures complémentaires

Quelques liens pour enrichir votre compréhension.


Valid XHTML 1.0 Transitional

CSS Valide !