Implémenter l'optimisation SSO

Ce qui est proposé ici est incomplet (bien que fonctionnel), éminemment perfectible et impropre à tout usage commercial. C'est toutefois amusant, à coder comme à réfléchir, et pas inintéressant du tout. Prenez le tout pour ce que c'est, sans plus.

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 :

Un exemple d'organisation possible pour une « grosse chaîne » suit. Ici, uint_32 signifie « entier non-signé sur bits ». Pour les besoins de l'illustration, supposons qu'un pointeur occupe aussi 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.

uint_32
uint_32
pointeur

Nombre d'éléments

Capacité

Pointeur sur 1er élément

Grosse chaîne de caractères, espace requis : bytes

Si on utilise un espace équivalent pour une petite chaîne, on peut en arriver à ceci.

uint_32 Texte
Nombre d'éléments
Séquence de caractères d'au plus huit bytes
Petite chaîne de caractères, espace requis : bytes

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 est une solution – pas la solution, évidemment – quelque peu embryonnaire à ce problème. J'y discute des compromis qu'il m'a fallu faire, et des raisons pour les choix que j'ai privilégié en cours de route.

Le programme de test

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

Ce programme met en relief un certain nombre de particularités du type chaine proposé en exemple. En effet, soit une instance s de ce type :

  • Il est possible de lui affecter une petite chaîne ("yo")
  • Il est aussi possible de lui affecter une longue chaîne (ici, donnée à partir de la concaténation statique de trois littéraux)
  • Il est possible de projeter une chaîne sur un flux, qu'elle soit petite ou grande
  • Il et possible de faire croître la taille d'une chaîne par ajouts successifs (push_back()), de manière à ce que le passage d'un mode de représentation à l'autre soit transparent

Notez que la classe chaine que j'utilise pour cette démonstration est générique sur la base du type d'un caractère (avec spécialisations, nommées respectivement chaine pour le type char et wchaine pour le type wchar_t, à l'image du type string), ce qui nous permet :

  • D'utiliser au besoin std::cout ou std::wcout
  • D'utiliser au besoin les littéraux tels que "yo", qui est un const char*, et L"yo", qui est un const wchar_t*, et
  • D'utiliser au besoin les littéraux tels que 'a', un char, par L'a', un wchar_t

Ceci nous permet de réaliser les mêmes tests sur des caractères étendus et sur des caractères d'un byte chacun, comme le montre l'exemple de code à droite.

Notez que les gains de SSO sont plus grands si la représentation d'un élément est plus petite, du fait que les structures de contrôle (pointeurs, entiers sur bits), elles, ne changent pas de taille si les caractères sont plus gros.

#include "chaine.h"
#include <iostream>
int main()
{
   using namespace std;
   chaine s = "yo";
   cout << s << endl;
   s = "J'aime mon prof, bon, pis "
       "c'est d'meme, genre, sinon "
       "ca va aller mal";
   cout << s << endl;
   s = "hey";
   cout << s << endl;
   s = "hey!";
   cout << s << endl;
   s = "heille!";
   cout << s << endl;
   chaine s2;
   for (int i = 0; i < 26; ++i)
   {
      s2.push_back(i + 'a');
      s2.push_back(i + 'A');
   }
   cout << s2 << endl;
   wchaine ws = L"yo";
   wcout << ws << endl;
   ws = L"J'aime mon prof, bon, pis "
        L"c'est d'meme, genre, sinon "
        L"ca va aller mal";
   wcout << ws << endl;
   ws = L"hey";
   wcout << ws << endl;
   ws = L"hey!";
   wcout << ws << endl;
   ws = L"heille!";
   wcout << ws << endl;
   wchaine ws2;
   for (int i = 0; i < 26; ++i)
   {
      ws2.push_back(i + L'a');
      ws2.push_back(i + L'A');
   }
   wcout << ws2 << endl;
}

L'affichage attendu serait alors :

yo
J'aime mon prof, bon, pis c'est d'meme, genre, sinon ca va aller mal
hey
hey!
heille!
aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ
yo
J'aime mon prof, bon, pis c'est d'meme, genre, sinon ca va aller mal
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.

Dans le texte qui suit, j'utiliserai parfois chaine comme synonyme général pour mon type, qui est toutefois basic_chaine<C> et pour laquelle chaine n'est qu'une spécialisation parmi plusieurs. Ceci permettra d'alléger quelque peu l'écriture.

L'implémentation retenue – les défis

L'implémentation proposée en exemple met en relief 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 à chaine, 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 :

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).

Les union constituent un outil fort pratique, mais dont les résultats ne sont pas portables.

Dans l'exemple à droite, si un tableau de char et un entier de même taille que ce tableau sont superposés, écrire dans l'entier modifiera le tableau entier, mais écrire dans une entrée du tableau ne modifiera qu'une partie de l'entier.

La partie de l'entier qui sera modifiée variera toutefois d'une plateforme à l'autre, du fait que l'ordre des bytes dans un entier dépend de la plateforme.

Dans le code à droite, l'affichage en fin de programme pourra prendre plusieurs formes, en fonction du signe de char sur une plateforme donnée, de la taille d'un short et de l'ordre des bytes dans un entier. Sachant que x.entier valait au préalable zéro, ou 0x0000 si on l'exprime sous forme hexadécimale (et si on présume sizeof(short)==2), l'affectation x.bytes[0]=0xff changera la valeur de x.entier, qui vaudra alors 0x00ff ou 0xff00 en fonction de l'ordre des bytes dans le short.

union X
{
   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 chaine 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

Il y a des exceptions à la règle. Pensons par exemple au cas où un service serait implémenté exactement à travers la même interface et serait accessible exactement à la même adresse pour toutes les représentations.

La classe chaine 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 chaine 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 chaine. 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 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 chaine 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.

Il pourrait être raisonnable d'ajouter un attribut pour la capacité, même dans le cas où celui-ci serait redondant, dans la mesure où notre compilateur générerait des objets plus gros que le minimum requis, par exemple pour des raisons d'alignement en mémoire. Dans un tel cas, plutôt que de « perdre » cet espace, mieux vaudrait l'utiliser à bon escient.

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 bits pour cette taille, j'aurais normalement des chaînes d'une taille variant entre et . 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 à . J'ai décidé que je pouvais vivre avec ce choix.

Implémentation

Voyons maintenant comment la classe chaine (en fait, basic_chaine<C> pour divers types de caractères C) est implémentée, en procédant un fichier à la fois. Notez que basic_chaine 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 chaine.h

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

Tout d'abord, une chaine pourra être construite de différentes manières. L'un des types de données sources sera une classique séquence ASCIIZ du type de caractères sous-jacent.

Lorsqu'une telle chaîne de caractères est reçue en paramètre par un constructeur, il est utile d'en calculer la longueur, exprimée en nombre de caractères.

Il se trouve que C ne permet pas à deux fonctions d'avoir le même nom mais de différer sur le plan du nombre de paramètres ou du type de certains paramètres. Pour cette raison, une fonction comme std::strlen(), excellente pour calculer la longueur d'une séquence ASCIIZ de char, ne fonctionnera pas correctement sur une séquence ASCIIZ de wchar_t. Toutefois, ma classe basic_chaine est générique sur la base du type de caractères, et j'aimerais que le code de cette classe soit chaque fois le même, au type de caractère près.

Pour y arriver, j'aurais pu spécialiser la classe toute entière pour le type char, mais j'ai plutôt choisi d'offrir la fonction string_length(), qui offre un comportement générique de manière générale mais expose aussi une version spécialisée pour le type char; évidemment, cette version spécialisée délègue, en pratique, le travail à std::strlen().

#ifndef CHAINE_H
#define CHAINE_H
#include <limits>
#include <utility>
#include <algorithm>
#include <iterator>
#include <cassert>
template <class C>
   std::size_t string_length(const C *p)
   {
      auto q = p;
      while (*p) ++p;
      return p - q;
   }
std::size_t string_length(const char *);

Une alternative (encore meilleure que celle choisie ici) aurait été d'utiliser les services de std::char_traits<C> C est le type de caractère. Un chic exercice si vous en avez envie!

Notez que l'implémentation de string_length() pour des const char* est placée dans chaine.cpp pour éviter des erreurs d'édition des liens.

La classe générique elle-même se nomme basic_chaine<C>, à l'image de std::basic_string<C>.

Elle pourrait évidemment être enrichie par des traits, de même que par un ensemble de méthodes supplémentaires (opérateurs de comparaison, d'ordonnancement, de recherche de sous-chaînes, etc.), mais elle suffira pour démontrer que notre implémentation de SSO fonctionne.

Ma classe expose des types internes et publics. Certains des plus simples sont visibles à droite.

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

Examinons maintenant la classe par laquelle les grosses chaînes seront représentées. J'ai nommé cette classe big_data, mais je conviens que c'est un choix de nomenclature des plus discutables.

Je débute ma présentation par celle-ci pour deux raisons :

  • Tout d'abord, une raison pédagogique : des deux représentations sous-jacentes possibles, celle-ci est sans doute la plus proche des classes plus « classiques » pour représenter des chaînes de caractères. Je fais le pari qu'elle vous semblera raisonnable et compréhensible si vous avez déjà codé une telle classe par le passé
  • Ensuite, une raison technique : l'espace disponible pour une petite chaîne dépend directement de l'espace occupé par une grosse chaîne, et la taille du bloc de bytes servant à représenter les deux types de représentations doit être au moins équivalent à la taille du plus gros de ces deux types. Il faut savoir qu'en C++, le nom d'un type devant être déclaré avant qu'on ne l'utilise, et la définition d'un type devant être connue avant qu'on ne puisse exprimer des idées sur la base de la taille. Conséquemment, il nous faut décrire d'abord le type représentant une grosse chaîne, le reste en dépendant

Cela dit, la définition du type basic_chaine<C>::big_data, à droite, est plutôt simple.

Notez la fonction add(), qui permettra à une basic_chaine<C> et à elle seule (car elle est amie de big_data) d'ajouter des éléments à une big_data existante; cette méthode est d'ailleurs insuffisamment protégée pour être exposée de manière publique au code client.

Les autres méthodes de cette classe sont « ordinaires ». Elles respectent les idiomes connus du langage (RAII, par exemple, ou l'idiome d'affectation sécuritaire) et font un travail honnête. Comme la plupart des types implémentés à travers de l'allocation dynamique de mémoire, d'ailleurs, la sémantique de mouvement et l'idiome d'affectation sécuritaire y sont tout à fait appropriés.

// ...
   private:
      class big_data
      {
         size_type size_, capacity_;
         char_type *data_;
      public:
         using iterator = char_type*;
         using const_iterator = const char_type*;
         size_type size() const noexcept
            { return size_; }
         size_type capacity() const noexcept
            { return capacity_; }
         bool full() const noexcept
            { return size() == capacity(); }
         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(); }
         big_data() noexcept
            : data_{}, size_{}, capacity_{}
         {
         }
         template <class Itt>
            big_data(Itt debut, Itt fin, const size_type cap = 0)
            {
               using namespace std;
               size_ = distance(debut, fin);
               capacity_ = cap? cap : size();
               data_ = new char_type[capacity()];
               copy(debut, fin, begin());
            }
         big_data(const big_data &org)
            : size_{org.size()}, capacity_{org.size()}
         {
            using std::copy;
            data_ = new char_type[capacity()];
            copy(std::begin(org), std::end(org), begin());
         }
         big_data(big_data &&org)
            : size_{std::move(org.size_)},
              capacity_{std::move(org.capacity_)},
              data_{std::move(org.data_)}
         {
            org.data_ = {};
            org.size_ = {};
            org.capacity_ = {};
         }
         void swap(big_data &autre)
         {
            using std::swap;
            swap(data_, autre.data_);
            swap(size_, autre.size_);
            swap(capacity_, autre.capacity_);
         }
         big_data& operator=(const big_data &org)
         {
            big_data{org}.swap(*this);
            return *this;
         }
         big_data& operator=(big_data &&org)
         {
            swap(org);
            return *this;
         }
         ~big_data() noexcept
            { delete [] data_; }
      private:
         friend class basic_chaine;
         void add(char_type c)
         {
            assert(!full());
            data_[size()] = c;
            ++size_;
         }
      };

Petite parenthèse technique : il aurait été possible d'utiliser la constante littérale (1<<31) pour représenter le bit le plus haut d'un size_type, mais une telle implémentation aurait dépendu du fait que size_type soit un type entier encodé sur bits. Ceci aurait été quelque peu fragile dans les circonstances.

J'ai plutôt choisi d'établir une constante symbolique smallness_mark_bit qui s'adapte statiquement à la taille effective de size_type.

Pour y arriver :

  • J'utilise sizeof(size_type) pour obtenir le nombre de bytes dans un size_type, puis
  • J'utilise le trait digits d'un unsigned char pour connaître le nombre de bits dans un byte – le recours à unsigned char est volontaire ici, car digits ne tient pas compte du bit de signe

Un piège plutôt vilain

L'ami Jérôme Rampon, en compilant ceci sur une machine bits, m'a souligné que son smallness_mark_bit était zéro.Je me suis fait piéger (merci de l'avoir trouvé!) : puisque le type sous-jacent d'un enum est un int, il est possible que sizeof(smallness_mark_bit) soit inférieur à sizeof(size_type).

Deux solutions viennent à l'esprit :

  • La première, qui requiert C++ 11 mais est nettement la meilleure, est de remplacer l'enum par une énumération forte, ou enum class size_type, donc une énumération dont la représentation sous-jacente est un type choisi par le programmeur. Ceci rendrait le code pleinement portable à toutes les plateformes
  • La seconde, qui est un contournement dans ce cas-ci mais qui fonctionnerait avec C++ 03, serait d'implémenter size_type avec un unsigned int

Procédant ainsi, le code fonctionnera sur une machine bits comme sur une machine bits, et survivrait (en théorie) à une machine pour laquelle un byte n'est pas un octet.

// ...
      enum
      {
         smallness_mark_bit =
            1 << (
               sizeof(size_type) *
               std::numeric_limits<
                  unsigned char
               >::digits - 1
            )
      };
      static_assert(
         sizeof(smallness_mark_bit)==sizeof(size_type),
         "Il faudra adapter ce passage avec un enum class size_type ..."
      );

Pour ce qui est de la classe représentant une petit chaîne, classe nommée ici small_data, l'espace de représentation est un bloc de bytes de taille fixée à la compilation et équivalent à la taille d'un big_data.

Contrairement à un big_data, un small_data n'a pas recours à de l'allocation dynamique de mémoire. Sa capacité est fixée a priori. Cette implémentation privilégie la copie; la sémantique de mouvement n'y est pas vraiment à propos.

Remarquez que les manipulations ayant trait à la taille de la chaîne doivent tenir compte de ce que j'y ai nommé la Smallness Mark, soit le bit le plus haut de la taille, qui est à 1 dans le cas où la chaîne est petite.

Je couvre le problème d'une représentation de grosse chaîne dont le bit le plus haut serait allumé (mon signal de petite chaîne) dans resize(), plus bas.

// ...
      class small_data
      {
      public:
         using size_type = std::size_t;
      private:
         char data_[sizeof(big_data)];
      public:
         enum { max_chars = sizeof(big_data)-sizeof(size_type) };
         using iterator = char*;
         using const_iterator = const char*;
         iterator begin() noexcept
            { return data_ + sizeof(size_type); }
         const_iterator begin() const noexcept
            { return data_ + 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(
               *reinterpret_cast<const size_type*>(data_+0)
            );
         }
         size_type capacity() const noexcept
            { return (sizeof(data_) - sizeof(size_type)) / sizeof(char_type); }
         bool full() const noexcept
            { return size() == capacity(); }
         template <class Itt>
            small_data(Itt debut, Itt fin, size_type = {})
            {
               using std::copy;
               using std::distance;
               *reinterpret_cast<size_type*>(data_) =
                  add_smallness_mark(distance(debut, fin));
               assert(size() <= max_chars);
               copy(debut, fin, begin());
            }
      private:
         friend class basic_chaine;
         void add(char_type c)
         {
            assert(!full());
            *(begin() + size()) = c;
            *reinterpret_cast<size_type*>(data_) =
               add_smallness_mark(
                  remove_smallness_mark(
                     *reinterpret_cast<size_type*>(data_)
                  ) + 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; }
      };

Quelques outils d'ordre général pour basic_chaine :

  • La taille du bloc de bytes nommé data, qui contiendra la représentation appropriée selon les circonstances, sera data_size
  • Les méthodes is_big() permettent de déterminer si un entier donné constitue une grosse taille (pour la version paramétrique) ou si la représentation actuelle est celle d'une grosse chaîne (pour la version sans paramètres). J'ai utilisé des critères différents dans chaque cas, et celui de is_big(n) est discutable
  • Enfin, les méthodes to_big_data() et to_small_data() permettent de transtyper le bloc brut dans l'une ou l'autre des représentations sous-jacentes possibles
// ...
      enum
      {
         data_size = sizeof(small_data) < sizeof(big_data) ?
            sizeof(big_data) : sizeof(small_data)
      };
      char data[data_size];
      static bool is_big(size_type n)
         { 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); }

Pour ce qui est des services de basic_chaine, la plupart sont des délégations directes (comme dans le cas de capacity()) ou indirectes (comme dans le cas de full()) vers des services de la représentation sous-jacente.

J'aurais voulu alléger cette écriture, mais les types des deux représentations sous-jacentes sont distincts l'un de l'autre, et je rappelle que, pour implémenter une optimisation telle que SSO, je préférais ne pas avoir recours au polymorphisme dynamique.

Pour resize(), qui permet de déterminer une nouvelle capacité pour la représentation sous-jacente, j'ai choisi d'utiliser une opération unaire prenant l'ancienne capacité et retournant la nouvelle capacité à titre de stratégie de croissance. C'est une option parmi plusieurs.

// ...
      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)
         {
            using std::copy;
            char new_data[data_size] = { 0 };
            void *addr = &new_data[0];
            size_type newcap = policy(capacity());
            assert(newcap >= capacity());
            // rien n'est parfait
            assert(!small_data::has_smallness_mark(newcap));
            if (is_big(newcap))
               new (addr) big_data(begin(), end(), newcap);
            else
               new (addr) small_data(begin(), end(), newcap);
            if (is_big())
               to_big_data().~big_data();
            else
               to_small_data().~small_data();
            copy(std::begin(new_data), std::end(new_data), std::begin(data));
         }

Pour begin() et end(), le code est banal et repose sur de simples délégations.

Pour size(), du fait que la taille se trouve au même endroit (un choix délibéré et, dans cette implémentation, une considération essentielle, tel que discuté plus haut) pour les deux représentations possibles, les manipulations pour éliminer le bit indiquant une petite chaîne sont faites directement ici.

// ...
   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 small_data::remove_smallness_mark(
            *reinterpret_cast<const size_type*>(data+0)
         );
      }

Suivent les opérations propres à l'identité d'une basic_chaine et à sa copie. J'ai couvert les cas suivants :

  • Construction par défaut (remplir le bloc de bytes avec des zéros)
  • Construction de copie (repose sur une construction par copie de la représentation sous-jacente)
  • Une affectation très spécifique à notre type
  • Construction à partir d'un tableau d'une certaine taille (connue à la compilation, dans ce cas-ci... On pourrait en profiter pour réaliser certaines optimisations supplémentaires, d'ailleurs, avis aux intéressé(e)s)
  • Construction à partir d'une séquence ASCIIZ, dont l'implémentation se limite à de la délégation vers l'équivalent pour le substrat le plus approprié, et
  • Le destructeur, qui délègue ses tâches de nettoyage au substrat effectif

Je n'ai pas couvert la sémantique de mouvement, du fait qu'au sens de basic_chaine, cette sémantique n'est pas appropriée (la représentation effective de ce type reposant sur un bloc de bytes bruts dont la taille est connue à la compilation).

Pour des raisons analogues, je n'ai pas eu recours ici à l'idiome d'affectation sécuritaire. Les opérations de copie me semblaient trop ciblées pour chercher à aller dans cette direction.

Mon implémentation de push_back() repose sur un redimensionnement général suivi d'un ajout spécialisé. L'opération permettant de déterminer la nouvelle capacité est une λ locale à la fonction.

Ce qui est probablement subtil dans tout cela est qu'il faut souvent laisser la représentation sous-jacente faire les opérations essentielles (copier les données, allouer des ressources, les libérer, etc.) mais qu'il faut aussi parfois copier un bloc de bytes bruts dans un autre, ces blocs bruts n'étant pas responsables de leur contenu. Dans le doute sur votre compréhension de l'une ou l'autre de ces manoeuvres, contactez votre chic prof!

// ...
      basic_chaine()
      {
         using std::fill;
         fill(std::begin(data), std::end(data), 0);
      }
      basic_chaine(const basic_chaine &org)
      {
         void *addr = &data[0];
         if (org.is_big())
            new (addr) big_data(org.to_big_data());
         else
            new (addr) small_data(org.to_small_data());
      }
      basic_chaine& operator=(const basic_chaine &autre)
      {
         using std::copy;
         if (this != &autre)
         {
            char new_data[data_size] = { 0 };
            void *addr = &new_data[0];
            if (autre.is_big())
               new (addr) big_data(autre.to_big_data());
            else
               new (addr) small_data(autre.to_small_data());
            if (is_big())
               to_big_data().~big_data();
            else
               to_small_data().~small_data();
            copy(std::begin(new_data), std::end(new_data), std::begin(data));
         }
         return *this;
      }
      template <int N>
         basic_chaine(const char_type (&p)[N])
         {
            void *addr = &data[0];
            if (is_big(N))
               new (addr) big_data(p);
            else
               new (addr) small_data(p);
         }
      basic_chaine(const char_type *p)
      {
         void *addr = &data[0];
         size_type n = string_length(p);
         if (is_big(n))
            new (addr) big_data(p, p + n);
         else
            new (addr) small_data(p, p + n);
      }
      ~basic_chaine() noexcept
      {
         if (is_big())
            to_big_data().~big_data();
         else
            to_small_data().~small_data();
      }
      void push_back(char_type c)
      {
         const size_type local_data_size = data_size;
         auto resizer = [=](const size_type oldcap) {
            return oldcap? static_cast<size_type>(oldcap * 1.67) : local_data_size;
         };
         if (full())
            resize(resizer);
         if (is_big())
            to_big_data().add(c);
         else
            to_small_data().add(c);
      }
   };

L'affichage sur un flux est banal, et repose sur une algorithmique d'itérateurs, pleinement détachée du substrat. Ceci met d'ailleurs en relief la beauté de cette métaphore.

template <class C>
   std::basic_ostream<C>& operator<<
      (std::basic_ostream<C> &os, const basic_chaine<C> &s)
   {
      using namespace std;
      using value_type = typename
         basic_chaine<C>::value_type;
      for(const auto &val : s)
         os << val;
      return os;
   }

À l'image des chaînes de caractères standards, exprimées de manière générique par std::basic_string et spécialisées sous la forme de std::string pour les char et sous la forme de std::wstring pour le type wchar_t, j'ai spécialisé basic_chaine pour les types char et wchar_t.

Simple et efficace.

using chaine = basic_chaine<char>;
using wchaine = basic_chaine<wchar_t>;
#endif

Fichier chaine.cpp

Pour ce qui est de chaine.cpp, la situation est toute simple.

Il se trouve que string_length() est une implémentation générique pour la majorité des types de caractères, mais qu'il y a lieu d'avoir une spécialisation pour le type char du fait que la bibliothèque standard de C offre une fonction strlen() qui a fait ses preuves.

Puisque cette « saveur » n'est pas générique, il importe d'en déposer la définition dans un fichier source, pour ne pas violer la règle ODR.

#include "chaine.h"
#include <cstring>
using std::strlen;
size_t string_length(const char *p)
   { return strlen(p); }

Voilà, donc. Un exercice fort amusant!

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) :

« [...] Dans ton exemple, sur small_data, tu utilises le premier bit MSB (bit le plus plus significatif) du premier byte de data_ pour indiquer qu'il s'agit d'un small_data. Ce choix te coûte un byte au complet pour avoir utilisé un bit.

Pour le fun, même si c'est un peu plus lent à l'exécution, tu aurais pu aussi utiliser un truc un peu différent en jouant sur un masquage de l'adresse de data_. En effet, vu que tu as a priori un alignement en mémoire des données sur au moins 4 bytes minimum, il te reste deux bits de masque pour « faire du booléen ». C'est pas une approche qui est forcément appréciée par tout le monde, mais SSO est déjà une optimisation de bas niveau qui joue fort le transtypage.

Avec cette technique, il y a une perte en vitesse lors des accès aux éléments de data_ parce qu'il faut masquer à chaque fois l'adresse; par contre, tu peux ainsi gagner un byte sur small_data. ».

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 :


Valid XHTML 1.0 Transitional

CSS Valide !