Implémenter l'optimisation SSO

Une optimisation possible pour l'implémentation de certains conteneurs, en particulier celle des chaînes de caractères, est l'optimisation dite SSO, pour Small String Optimization.

L'idée derrière cette optimisation est relativement simple :

• Avec cette optimisation, on cherchera à éviter d'allouer dynamiquement les chaînes de caractères qui sont « petites »
• Par « petites », on entendra des chaînes qui occupent au pire le même espace que ne le fait l'overhead (faute d'un meilleur terme) des données utilisées pour représenter les « grosses » chaînes de caractères
• Par exemple, si vous avez une chaîne qui demande normalement d'entreposer un pointeur sur son 1^er élément, un entier $32$ bits non-signé pour le nombre d'éléments et un autre entier $32$ bits non-signé pour la capacité, alors l'approche SSO mènerait à représenter la petite chaîne sur $3 \times 4$ bytes – ou peut-être $4 \times 4$ bytes, si le code généré n'est pas compact – et à utiliser le même espace en mémoire pour les données de la petite chaîne et les structures de contrôle de la grosse chaîne
• Ce faisant, nul besoin d'allouer des ressources dynamiquement pour la petite chaîne. Les opérations sur des chaînes de petite taille sont alors bien plus rapides!
• Évidemment, une telle implémentation implique certaines contraintes techniques. Par exemple, à moins de ne pas utiliser de constructeurs pour les types représentant une petite ou une grosse chaîne, on ne pourra pas utiliser d'union. Cependant, on pourra utiliser un bloc de bytes bruts et gérer ce bloc par allocation positionnelle (le placement new). Nous y reviendrons

Un exemple d'organisation possible pour une « grosse chaîne » suit. Ici, uint32_t signifie « entier non-signé sur $32$ bits ». Pour les besoins de l'illustration, supposons qu'un pointeur occupe aussi $32$ bits en mémoire. Ce ne sont que des choix pour fins d'illustration – l'optimisation SSO ne dépend pas de ces valeurs spécifiquement.

Si compilé en 32 bits (quatre bytes par pointeur) :

Si compilé en 64 bits (huit bytes par pointeur) :

Si on utilise un espace équivalent pour une petite chaîne, il est possible d'éviter toute allocation dynamique de mémoire et de conserver les données et le nombre de caractères sur une seule et même Cache Line.

Si compilé en 32 bits (quatre bytes par pointeur) :

Si compilé en 64 bits (huit bytes par pointeur) :

La question, donc : comment coderiez-vous une chaîne correcte implémentant SSO? C'est un exercice amusant, surtout si l'on prend soin de coder push_back().

Ce qui suit propose deux ébauches de solution à ce problème (deux options parmi plusieurs), accompagnées d'une discussion des compromis faits dans chaque cas.

Le programme de test

J'ai testé chaque implémentation avec ce qui suit.

#include "sso_string.h"
#include <string>
#include <iostream>
int main() {
   using namespace std;
   sso_str s = "yo";
   cout << s << endl;
   s = "I like my instructor, he's really sweet and "
       "he barely makes my head hurt on occasion";
   cout << s << endl;
   s = "hey";
   cout << s << endl;
   s = "hey!";
   cout << s << endl;
   s = "heille!";
   cout << s << endl;
   sso_str s2;
   for (int i = 0; i < 26; ++i) {
      s2.push_back(i + 'a');
      s2.push_back(i + 'A');
   }
   cout << s2 << endl;
   wsso_str ws = L"yo";
   wcout << ws << endl;
   ws = L"I like my instructor, he's really sweet and "
        L"he barely makes my head hurt on occasion";
   wcout << ws << endl;
   ws = L"hey";
   wcout << ws << endl;
   ws = L"hey!";
   wcout << ws << endl;
   ws = L"heille!";
   wcout << ws << endl;
   wsso_str ws2;
   for (int i = 0; i < 12; ++i) {
      ws2.push_back(i + L'a');
      ws2.push_back(i + L'A');
   }
   wcout << ws2 << endl;
}

L'affichage attendu serait alors :

yo
I like my instructor, he's really sweet and he barely makes my head hurt on occasion
hey
hey!
heille!
aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ
yo
I like my instructor, he's really sweet and he barely makes my head hurt on occasion
hey
hey!
heille!
aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ

Évidemment, la gamme de tests pourrait être plus riche encore, mais ceci nous permettra d'examiner les conséquences et les ramifications de l'implémentation d'une optimisation SSO sur un type de données.

Implémentations retenue – v0

L'implémentation proposée en exemple expose quelques défis intéressants. J'essaierai dans cette section de mettre en relief les plus importants parmi ceux-ci, dans le but de clarifier votre lecture par la suite.

Choix structurels sous-jacents

J'ai choisi d'utiliser deux classes internes à v0::sso_string, soit une pour les « petites » chaînes et une autre pour les « grosses ». Les « petites » chaînes seront faites d'une séquence de caractères et d'une taille, leur capacité étant fixée à la compilation. Les « grosses » chaînes seront quant à elles faites d'un pointeur sur la séquence de caractères, d'une taille (en nombre de caractères) et d'une capacité (idem).

Le défi sera de représenter les deux chaînes dans le même espace, donc d'entreposer à même cet espace la capacité de déterminer laquelle des deux représentations aura été choisie.

Parce que j'utiliserai des types distincts pour les deux représentations, j'aurai recours à des constructeurs et à des destructeurs dans chaque cas. En effet, les « grosses » chaînes seront responsables de ressources, ayant recours à de l'allocation dynamique de mémoire, et ont un besoin clair de procéder à du nettoyage.

Ce choix d'implémentation entraîne deux conséquences techniques :

• On verra, dans les méthodes de sso_string, un certain nombre d'alternatives (de « if ») permettant de choisir l'opération la plus appropriée pour la représentation sous-jacente utilisée. L'alternative à ces alternatives, pour ainsi dire, serait d'avoir recours à du polymorphisme et de dériver les deux représentations sous-jacentes possibles d'une même abstraction, mais il y aurait alors un coût en espace et il n'est pas clair que ce coût soit approprié dans les circonstances, et
• Nous ferons face à des contraintes structurelles et nous devrons faire des choix techniques particuliers pour nous permettre de déterminer efficacement si la représentation sous-jacente passe par une « petite » ou par une « grosse » chaîne

Superposition des représentations

La méthode classique (dans le langage C, du moins) pour superposer deux données en mémoire est d'avoir recours à un union. Par « superposer », ici, je fais un demi-abus de langage, au sens où les membres d'une instance donnée d'un union débutent tous à la même adresse mais n'occupent pas nécessairement la même plage mémoire (un union ayant pour membres un char et un int serait un bon exemple d'un cas où parler de « superposition » serait quelque peu abusif).

union X {
   alignas(short) char bytes[sizeof(short)];
   short entier;
};
#include <iostream>
int main() {
   using namespace std;
   X x;
   x.entier = 0; // remplit aussi x.bytes_
   x.bytes[0] = 0xff; // modifie aussi x.entier_
   cout << x.entier << endl; 
}

Ce côté éminemment non portable des union réduit leur utilité en général, outre dans quelques situations bien circonscrites. On aurait pu croire que l'implémentation SSO que nous cherchons à faire ici aurait été l'une de ces situations très ciblées, du fait que les manipulations sur une sso_string seront internes à un programme dans un ordinateur donné, or ce n'est pas le cas, du moins pas avec les choix techniques mentionnés plus haut.

En effet, le recours à des constructeurs et à des destructeurs disqualifie d'office le recours à un union. Il suffit d'y penser : dans un union, si au moins un membre a un constructeur, quoi faire lorsqu'une instance de cet union est construite? Donner priorité au membre ayant un constructeur? Mais de quel droit? Et si au moins deux membres ont des constructeurs, alors lequel privilégier? La même question se pose pour les destructeurs, d'ailleurs. Pour qu'un union soit un choix raisonnable, il faut que l'initialisation et la finalisation soient triviales (au sens mathématique du terme), ce qui ne sera pas le cas ici.

J'ai donc eu recours à une gestion manuelle d'un espace circonscrit, à l'aide d'allocation positionnelle (placement new), ce qui me permet d'utiliser à plein les facilités du langage (constructeurs, destructeurs, méthodes de toute sorte) tout en contrôlant le lieu où les objets sont placés, de même que l'espace qu'ils occupent.

Déterminer la représentation choisie

La classe sso_string devra faire des choix, dynamiquement, en fonction du type de représentation sous-jacente.

En effet, règle générale, lors d'un appel d'une de ses méthodes d'instance, il faudra que la classe sso_string identifie la représentation sous-jacente actuelle et délègue à cette dernière la tâche associée au service sollicité. C'est de cette sélection d'un service sur la base d'un type que le polymorphisme nous libère, mais ici, en implémentant SSO, nous souhaitons respecter des contraintes de taille et de disposition binaire extrêmement strictes, et nous portons conséquemment le fardeau de la sélection dynamique des services sur nos épaules.

Prenons par exemple le pseudocode ci-dessous :

// ...
iterator begin() {
   /*
   si la représentation sous-jacente est celle d'une grosse chaine
      - traiter le bloc de bytes brut servant à entreposer les
        représentations sous-jacentes comme une référence sur la
        représentation d'une grosse chaine
      - déléguer le travail à sa méthode begin()
   sinon
      - traiter le bloc de bytes brut servant à entreposer les 
        représentations sous-jacentes comme une référence sur la 
        représentation d'une petite chaine
      - déléguer le travail à sa méthode begin()
   */
}
// ...

Ici, une alternative (un if) est nécessaire pour réaliser le bon transtypage du bloc de bytes où les représentations peuvent se superposer et, par la suite, invoquer le service souhaité à partir de la représentation obtenue.

On peut parfois escamoter ce transtypage, comme le montre un cas patent à même le pseudocode ci-dessus : la méthode permettant de savoir si la représentation sous-jacente est celle d'une grosse ou d'une petite chaîne ne doit pas dépendre d'un transtypage puisque c'est elle qui guide le transtypage à réaliser. L'implémentation de cette méthode est particulièrement importante pour l'ensemble de nos décisions techniques.

Petite ou grosse chaîne?

Comment représenter ce savoir? Plusieurs options sont possibles. La première, peut-être la plus évidente pour la plupart des gens, serait d'utiliser un booléen à même la classe sso_string. Il y a un coût associé à ce choix, cependant : pour des raisons de contraintes d'alignement des objets en mémoire, le booléen pourrait occuper un mot mémoire entier (quatre bytes sur une machine $32$ bits comme celle supposée dans cet exemple), ce qui serait dispendieux pour implémenter un optimisation justement axée sur une plus grande efficacité dans la manipulation des petites chaînes.

On pourrait aussi se baser sur la taille, en termes de nombre de caractères dans la chaîne, pour déterminer s'il s'agit d'une grosse ou d'une petite chaîne. Ceci impliquerait soit de placer cette taille à même la classe sso_string puis de la passer en paramètre aux méthodes des représentations sous-jacentes, ce qui est contestable sur le plan de l'esthétique structurelle, soit de placer au même endroit dans les deux représentations sous-jacentes cette information, de telle sorte que convertir dans l'une ou l'autre des deux représentations donne accès à la taille de la même manière. J'ai utilisé cette deuxième approche longtemps (je le fais encore, d'ailleurs, avec une nuance dont nous reparlerons plus loin), mais elle a un défaut important : elle est fautive!

En effet, ce qui nous préoccupe en pratique pour déterminer la représentation sous-jacente est non pas le nombre de caractères dans la chaîne, mais bien la capacité de la mémoire allouée pour déposer ces caractères – la capacité d'un conteneur est toujours supérieure ou égale à sa taille.

Cela dit, dans le cas de l'implémentation d'une optimisation SSO, il est moins clair que l'on veuille avoir recours à utiliser un attribut d'instance pour représenter la capacité de la chaîne. En effet, pour une petite chaîne, la capacité sera très probablement une constante statique, ne dépendant que de la taille des données servant à représenter une grosse chaîne. Il ne serait alors par nécessaire de l'entreposer dans un attribut. Par contre, la capacité d'une grosse chaîne est quant à elle presque assurément dynamique, nécessitant du même coup un attribut.

Cette dichotomie laisse entendre que si la taille pourrait servir de discriminant entre petite et grosse chaîne, il se trouve que la capacité, quant à elle, s'y prête moins.

Mon approche, vous le verrez, a été de tricher. Plutôt que d'utiliser un mot mémoire entier pour un booléen ou de forcer la représentation de la capacité dans un attribut, même si cela n'est nécessaire que dans l'un des deux cas à couvrir, j'ai choisi de limiter la taille maximale de mes grosses chaînes. Ayant choisi d'utiliser $32$ bits pour cette taille, j'aurais normalement des chaînes d'une taille variant entre $0$ et $2^{32}-1$. J'utilise le bit le plus haut de la taille à titre d'état booléen, pour représenter le choix d'une petite représentation ou non. Ce faisait, la taille maximale d'une grosse chaîne passe de $2^{32}-1$ à $2^{31}-1$. J'ai décidé que je pouvais vivre avec ce choix.

Implémentation

Voyons maintenant comment la classe sso_string (en fait, basic_sso_string<C> pour divers types de caractères C) est implémentée, en procédant un fichier à la fois. Notez que basic_sso_string est une classe générique, donc est essentiellement décrite dans un fichier d'en-tête, mais que nous aurons besoin d'un fichier source pour certaines spécialisations non-génériques d'outils dont dépend notre classe.

Fichier sso_string.h

Maintenant que nos a priori ont été étalés sur la place publique, abordons l'implémentation à proprement dit.

#ifndef SSO_STR_H
#define SSO_STR_H
#include <limits>
#include <utility>
#include <algorithm>
#include <iterator>
#include <cassert>
#include <cstring>
#include <type_traits>
#include <string_view>
template <class C>
   constexpr auto string_length(std::basic_string_view<C> s) {
      return s.size();
   }

namespace v0 {
   template <class C>
   class basic_sso_str {
   public:
      using char_type = C;
      using value_type = C;
      using size_type = std::size_t;

   private:
      class big_data {
         size_type nelems{}, cap{};
         char_type *elems{};
      public:
         using iterator = char_type * ;
         using const_iterator = const char_type*;
         size_type size() const noexcept {
            return nelems;
         }
         size_type capacity() const noexcept {
            return cap;
         }
         bool full() const noexcept {
            return size() == capacity();
         }
         iterator begin() noexcept {
            return elems;
         }
         const_iterator begin() const noexcept {
            return elems;
         }
         iterator end() noexcept {
            return begin() + size();
         }
         const_iterator end() const noexcept {
            return begin() + size();
         }
         big_data() = default;
         template <int N>
         big_data(const char_type(&arr)[N])
            : nelems{ N }, cap{ N }, elems{ new char_type[N] } {
            std::copy(std::begin(arr), std::end(arr), begin());
         }
         template <class It>
         big_data(It b, It e, size_type newcap = {}) {
            nelems = std::distance(b, e);
            cap = std::max(newcap, size());
            elems = new char_type[capacity()];
            std::copy(b, e, begin());
         }
         big_data(const big_data &org)
            : nelems{ org.size() }, cap{ org.size() } {
            elems = new char_type[capacity()];
            std::copy(std::begin(org), std::end(org), begin());
         }
         big_data(big_data &&org) noexcept
            : nelems{ std::exchange(org.nelems, 0) },
            cap{ std::exchange(org.cap, 0) },
            elems{ std::exchange(org.elems, nullptr) } {
         }
         void swap(big_data &other) noexcept {
            using std::swap;
            swap(elems, other.elems);
            swap(nelems, other.nelems);
            swap(cap, other.cap);
         }
         big_data& operator=(const big_data &other) {
            big_data{ other }.swap(*this);
            return *this;
         }
         big_data& operator=(big_data &&other) noexcept {
            if (&other == this) return *this;
            delete[] elems;
            elems = std::exchange(other.elems, nullptr);
            nelems = std::exchange(other.nelems, 0);
            cap = std::exchange(other.cap, 0);
            return *this;
         }
         ~big_data() {
            delete[] elems;
         }
         void add(char_type c) {
            assert(!full());
            elems[size()] = c;
            ++nelems;
         }
      };

      static constexpr auto bits_in_byte =
         std::numeric_limits<unsigned char>::digits;
      static constexpr auto smallness_mark_bit =
         static_cast<std::size_t>(1) << (static_cast<std::size_t>(sizeof(size_type) * bits_in_byte - 1));
      static_assert(
         sizeof(smallness_mark_bit) == sizeof(size_type)
      );

      class small_data {
      public:
         using size_type = std::size_t;
      private:
         char_type data_[sizeof(big_data) / sizeof(char_type)];
         auto to_char_rep() {
            return std::begin(data_);
         }
         auto to_char_rep() const {
            return std::begin(data_);
         }
         decltype(auto) to_size_rep() {
            return *reinterpret_cast<size_type*>(std::begin(data_));
         }
         decltype(auto) to_size_rep() const {
            return *reinterpret_cast<const size_type*>(std::begin(data_));
         }
      public:
         static constexpr auto max_chars =
            sizeof(big_data) - sizeof(size_type);
         using iterator = char_type*;
         using const_iterator = const char_type*;
         iterator begin() noexcept {
            return to_char_rep() + sizeof(size_type);
         }
         const_iterator begin() const noexcept {
            return to_char_rep() + sizeof(size_type);
         }
         iterator end() noexcept {
            return begin() + size();
         }
         const_iterator end() const noexcept {
            return begin() + size();
         }
         size_type size() const noexcept {
            return remove_smallness_mark(to_size_rep());
         }
         constexpr size_type capacity() const noexcept {
            return (sizeof(data_) - sizeof(size_type)) / sizeof(char_type);
         }
         bool full() const noexcept {
            return size() == capacity();
         }
         template <class It>
         small_data(It b, It e, size_type = 0) {
            to_size_rep() =
               add_smallness_mark(std::distance(b, e));
            assert(size() <= max_chars);
            std::copy(b, e, begin());
         }
         small_data() {
            to_size_rep() = add_smallness_mark(0);
         }
         template <int N>
         small_data(const char_type(&arr)[N]) {
            static_assert(N && N - 1 <= max_chars);
            to_size_rep() = add_smallness_mark(N - 1);
            std::copy(std::begin(arr), std::prev(std::end(arr)), begin());
         }
         void add(char_type c) {
            assert(!full());
            *(begin() + size()) = c;
            to_size_rep() = add_smallness_mark(
               remove_smallness_mark(to_size_rep()) + 1
            );
         }
         static bool has_smallness_mark(size_type n) {
            return (n & smallness_mark_bit) != 0;
         }
         static size_type add_smallness_mark(size_type n) {
            return n | smallness_mark_bit;
         }
         static size_type remove_smallness_mark(size_type n) {
            return n & ~smallness_mark_bit;
         }
      };

      static constexpr auto data_size =
         std::max(sizeof(small_data), sizeof(big_data))/* / sizeof(char_type)*/;
      char_type data[data_size]{};
      static constexpr bool is_big(size_type n) noexcept {
         return n > small_data::max_chars / sizeof(char_type);
      }
      bool is_big() const noexcept {
         return !small_data::has_smallness_mark(
            *reinterpret_cast<const size_type*>(data + 0)
         );
      }
      big_data &to_big_data() noexcept {
         return *reinterpret_cast<big_data*>(data);
      }
      const big_data &to_big_data() const noexcept {
         return *reinterpret_cast<const big_data*>(data);
      }
      small_data &to_small_data() noexcept {
         return *reinterpret_cast<small_data*>(data);
      }
      const small_data &to_small_data() const noexcept {
         return *reinterpret_cast<const small_data*>(data);
      }

      size_type capacity() const noexcept {
         return is_big() ? to_big_data().capacity() :
            to_small_data().capacity();
      }
      bool full() const noexcept {
         return size() == capacity();
      }
      template <class Pol>
      void resize(Pol policy) {
         char_type new_data[data_size]{ };
         size_type newcap = policy(capacity());
         assert(newcap >= capacity());
         assert(!small_data::has_smallness_mark(newcap));
         if (is_big(newcap))
            new (new_data) big_data{ begin(), end(), newcap };
         else
            new (new_data) small_data{ begin(), end(), newcap };
         if (is_big())
            to_big_data().~big_data();
         else
            to_small_data().~small_data();
         std::copy(std::begin(new_data), std::end(new_data), std::begin(data));
      }

   public:
      using iterator = char_type * ;
      using const_iterator = const char_type*;
      iterator begin() noexcept {
         return is_big() ? to_big_data().begin() :
            to_small_data().begin();
      }
      const_iterator begin() const noexcept {
         return is_big() ? to_big_data().begin() :
            to_small_data().begin();
      }
      iterator end() noexcept {
         return begin() + size();
      }
      const_iterator end() const noexcept {
         return begin() + size();
      }
      size_type size() const noexcept {
         return is_big() ? to_big_data().size() : to_small_data().size();
      }

      basic_sso_str() {
         new (data) small_data;
      }
      basic_sso_str(const basic_sso_str &other) {
         if (other.is_big())
            new (data) big_data(other.to_big_data());
         else
            new (data) small_data(other.to_small_data());
      }
      basic_sso_str& operator=(const basic_sso_str &other) {
         if (this != &other) {
            char_type new_data[data_size]{ };
            if (other.is_big())
               new (new_data) big_data(other.to_big_data());
            else
               new (new_data) small_data(other.to_small_data());
            if (is_big())
               to_big_data().~big_data();
            else
               to_small_data().~small_data();
            std::copy(std::begin(new_data), std::end(new_data), std::begin(data));
         }
         return *this;
      }
      template <int N>
      basic_sso_str(const char_type(&p)[N]) {
         if constexpr (is_big(N * sizeof(char_type)))
            new (data) big_data(p);
         else
            new (data) small_data(p);
      }
      ~basic_sso_str() {
         if (is_big())
            to_big_data().~big_data();
         else
            to_small_data().~small_data();
      }
      void push_back(char_type c) {
         auto resizer = [](size_type oldcap) {
            static constexpr auto resize_fac = 2;
            return oldcap ? static_cast<size_type>(oldcap * resize_fac) : data_size;
         };
         if (full())
            resize(resizer);
         if (is_big())
            to_big_data().add(c);
         else
            to_small_data().add(c);
      }
   };
}

Implémentations retenues – v1

L'implémentation proposée en exemple expose quelques défis intéressants. J'essaierai dans cette section de mettre en relief les plus importants parmi ceux-ci, dans le but de clarifier votre lecture par la suite.

Le code suit. Explications à venir :

namespace v1 {
   template <class C>
   class basic_sso_str {
   public:
      using char_type = C;
      using value_type = C;
      using size_type = std::size_t;
   private:
      static constexpr auto data_size = 16;
      union {
         value_type small[data_size];
         char_type *ptr;
      } rep;
      size_type nelems{}, cap{ data_size };
   public:
      size_type size() const noexcept {
         return nelems;
      }
      size_type capacity() const noexcept {
         return cap;
      }
      bool full() const noexcept {
         return size() == capacity();
      }
      using iterator = char_type * ;
      using const_iterator = const char_type*;
      iterator begin() noexcept {
         return uses_small_rep() ? std::begin(rep.small) : rep.ptr;
      }
      const_iterator begin() const noexcept {
         return uses_small_rep() ? std::begin(rep.small) : rep.ptr;
      }
      iterator end() noexcept {
         return begin() + size();
      }
      const_iterator end() const noexcept {
         return begin() + size();
      }
   private:
      template <class Pol>
      void resize(Pol policy) {
         using namespace std;
         size_type newcap = policy(capacity());
         assert(newcap >= capacity());
         if (newcap > data_size) {
            auto p = new char_type[newcap];
            copy(begin(), end(), p);
            if (!uses_small_rep()) delete[] rep.ptr;
            rep.ptr = p;
            cap = newcap;
         }
      }
      bool uses_small_rep() const {
         return capacity() == data_size;
      }
   public:
      basic_sso_str() = default;
      basic_sso_str(const basic_sso_str &other)
         : nelems{ other.size() }, cap{ other.uses_small_rep() ? data_size : other.size() } {
         if (!uses_small_rep())
            rep.ptr = new char_type[capacity()];
         std::copy(other.begin(), other.end(), begin());
      }
      void swap(basic_sso_str &other) {
         using std::swap;
         swap(nelems, other.nelems);
         swap(cap, other.cap);
         swap(rep, other.rep);
      }
      basic_sso_str& operator=(const basic_sso_str &other) {
         basic_sso_str{ other }.swap(*this);
         return *this;
      }
      template <int N>
      basic_sso_str(const char_type(&p)[N]) {
         assert(!p[N - 1]);
         if constexpr (N > data_size) {
            rep.ptr = new char_type[N];
            cap = N;
         }
         nelems = N - 1;
         std::copy(std::begin(p), std::end(p) - 1, begin());
      }
      ~basic_sso_str() {
         if (!uses_small_rep()) delete rep.ptr;
      }
      void push_back(char_type c) {
         if (full()) resize([](auto n) { return n * 2; }); // no need for the 0 capacity case
         if (uses_small_rep()) {
            rep.small[size()] = c;
         } else {
            rep.ptr[size()] = c;
         }
         ++nelems;
      }
   };
}

Implémentations retenues – v2

L'implémentation proposée en exemple expose quelques défis intéressants. J'essaierai dans cette section de mettre en relief les plus importants parmi ceux-ci, dans le but de clarifier votre lecture par la suite.

Le code suit. Explications à venir :

namespace v2 {
   template <class C>
   class basic_sso_str {
   public:
      using char_type = C;
      using value_type = C;
      using size_type = std::size_t;
      using iterator = char_type * ;
      using const_iterator = const char_type*;
   private:
      static constexpr auto data_size = 16;
      class small {
         value_type data[data_size / sizeof(value_type)];
         size_type nelems{};
         bool full() const noexcept { return size() == capacity(); }
      public:
         small() = default;
         template <class It>
            small(It debut, It fin) : nelems(std::distance(debut, fin)) {
               assert(size() < capacity());
               std::copy(debut, fin, begin());
            }
         auto size() const noexcept { return nelems; }
         auto capacity() const noexcept { return std::size(data); }
         iterator begin() noexcept { return std::begin(data); }
         const_iterator begin() const noexcept { return std::begin(data); }
         iterator end() noexcept { return begin() + size(); }
         const_iterator end() const noexcept { return begin() + size(); }
         void push_back(value_type c) {
            assert(!full());
            data[size()] = c;
            ++nelems;
         }
      };
      class big {
         value_type *data;
         size_type nelems{}, cap{ };
         bool full() const noexcept { return size() == capacity(); }
      public:
         big(size_type cap) : data{ new value_type[cap] }, cap{ cap } {
         }
         template <class It>
            big(It debut, It fin) : nelems(std::distance(debut, fin)) {
               cap = size();
               data = new value_type[capacity()];
               std::copy(debut, fin, begin());
            }
         // prudence : le choix de dupliquer la capacité est délibéré ici
         big(const big &other)
            : data{ new value_type[other.capacity()] }, nelems{ other.size() }, cap{ other.capacity() } {
            std::copy(other.begin(), other.end(), begin());
         }
         big(big &&other) noexcept
            : data{ std::exchange(other.data, nullptr) },
              nelems{ std::exchange(other.nelems, 0) },
              cap{ std::exchange(other.cap, 0) } {
         }
         void swap(big &other) noexcept {
            using std::swap;
            swap(data, other.data);
            swap(nelems, other.nelems);
            swap(cap, other.cap);
         }
         big& operator=(const big &other) {
            big{ other }.swap(*this);
            return *this;
         }
         big& operator=(big &&other) noexcept {
            if (this != &other) {
               delete[] data;
               data = std::exchange(other.data, nullptr);
               nelems = std::exchange(other.nelems, 0);
               cap = std::exchange(other.cap, 0);
            }
            return *this;
         }
         template <class It>
         void assign(It debut, It fin) {
            size_type n = std::distance(debut, fin);
            assert(n <= capacity());
            std::copy(debut, fin, begin());
            nelems = n;
         }
         auto size() const noexcept { return nelems; }
         auto capacity() const noexcept { return cap; }
         iterator begin() noexcept { return data; }
         const_iterator begin() const noexcept { return data; }
         iterator end() noexcept { return begin() + size(); }
         const_iterator end() const noexcept { return begin() + size(); }
         void push_back(value_type c) {
            assert(!full());
            data[size()] = c;
            ++nelems;
         }
      };
      std::variant<small, big> rep {}; // initializes small
   public:
      size_type size() const noexcept {
         return visit([](const auto &rep) { return rep.size(); }, rep );
      }
      size_type capacity() const noexcept {
         return visit([](const auto &rep) { return rep.capacity(); }, rep);
      }
      bool full() const noexcept {
         return size() == capacity();
      }
      iterator begin() noexcept {
         return visit([](auto &rep) { return rep.begin(); }, rep);
      }
      const_iterator begin() const noexcept {
         return visit([](const auto &rep) { return rep.begin(); }, rep);
      }
      iterator end() noexcept {
         return visit([](auto &rep) { return rep.end(); }, rep);
      }
      const_iterator end() const noexcept {
         return visit([](const auto &rep) { return rep.end(); }, rep);
      }
   private:
      template <class Pol>
      void resize(Pol policy) {
         using namespace std;
         size_type newcap = policy(capacity());
         assert(newcap >= capacity());
         big s(newcap);
         s.assign(begin(), end());
         rep = s;
      }
   public:
      basic_sso_str() = default;
      template <int N>
         basic_sso_str(const char_type(&p)[N]) {
            assert(!p[N - 1]);
            if constexpr (N < data_size / sizeof(char_type)) {
               rep = small{ std::begin(p), std::end(p) };
            } else {
               rep = big{ std::begin(p), std::end(p) };
            }
         }
      void push_back(char_type c) {
         if (full()) resize([](auto n) { return n * 2; }); // no need for the 0 capacity case
         visit([c](auto &rep) { rep.push_back(c); }, rep);
      }
   };
}

 Voilà, donc. Un exercice fort amusant!

Ajouts généraux

template <class C>
   std::basic_ostream<C>&
      operator<<(std::basic_ostream<C> &os, const basic_sso_str<C> &s) {
         for(auto c : s)
            os << c;
         return os;
      }

using v0::basic_sso_str;
// using v1::basic_sso_str;
using sso_str = basic_sso_str<char>;
using wsso_str = basic_sso_str<wchar_t>;
#endif

Remarque sur des approches alternatives

L'ami Jérôme Rampon, qui s'est amusé avec cet exemple, m'a écrit la remarque suivante (je paraphrase légèrement) :

Si vous en avez envie, implémenter SSO de cette manière peut être amusant : plutôt que de jouer sur un bit du byte le plus significatif, vous pouvez mentir sur l'adresse vers laquelle mène le pointeur de données en masquant l'un de ses bits pour représenter le concept de « petite » ou de « grosse » chaîne. Un chouette exercice... Merci!

Lectures complémentaires

Pour des textes d'autres sources :

• Réfléchir sur les optimisations permises dans un programme, texte d'Andrzej Krzemieński (touchant directement SSO) en 2014 : http://akrzemi1.wordpress.com/2014/04/14/common-optimizations/
• En 2014, Howard Hinnant explique les mécanismes qui sous-tendent son implémentation de SSO : https://stackoverflow.com/questions/21694302/what-are-the-mechanics-of-short-string-optimization-in-libc/21710033#21710033
• En 2015, Elliot Goodrich a compilé un comparatif de l'implémentation de l'optimisation SSO telle que réalisée dans les principaux compilateurs C++ : https://github.com/elliotgoodrich/SSO-23
• Texte de Stoyan Nikolov en 2017, qui implémente un vecteur avec optimisation SOO : https://stoyannk.wordpress.com/2017/11/18/small-vector-optimization/
• En 2019, JeanHeyd Meneide s'amuse avec un small_bit_vector : https://thephd.github.io/small-bit-vector et https://thephd.github.io/allocator-hell-small_bit_vector