Les opérateurs new et delete

Article précédent: La sémantique de déplacement

L’allocation dynamique c’est facile: pour un new, un delete

Le quidam du coin.

Pour 12 opérateurs new, 14 opérateurs delete.

La norme de C++11.

Mmmh, va pour 16 opérateurs delete.

C++14.

Finalement 22 opérateurs new et 26 opérateurs delete.

L’apparition de C++17.

Allez, 30 opérateurs delete.

Toujours plus loin avec C++20.


Cet article va parler des opérateurs new et delete. Pas les mots clefs new et delete tout seuls, mais bien de operator new et operator delete de l’en-tête <new>, car derrière les mots clefs usuels se cachent en réalité beaucoup de fonctions surchargées. Soit appelées implicitement par le compilateur, soit explicitement par le développeur en donnant des paramètres à new.

Bien sûr, ce sont des techniques très bas niveau liées à l’allocation dynamique, à moins de vouloir écrire un allocateur global, il est probable que vous n’en ayez jamais besoin. Je vais néanmoins présenter ici les différents opérateurs existant dans le standard et à quel moment ils sont utilisés.

new ou operator new ?

La première chose à faire est de distinguer le mot clef new traditionnellement utilisé de la fonction operator new() se trouvant dans l’en-tête <new>. L’expression new T fait en réalité 2 choses:

  • Allouer une zone mémoire en utilisant operator new().
  • Construire le type T dans la zone mémoire préalablement allouée (appel du constructeur).

Ces 2 étapes peuvent se faire manuellement en utilisant explicitement un opérateur new suivi d’un placement-new qui appelle un opérateur new spécifique.

new utilise new et 2 operator new, il y a de quoi s’y perdre :).

void* mem = operator new(sizeof(T)); // on alloue une mémoire pouvant contenir un T
T* p = new(mem) T(); // on construit un T dans la zone allouée
                     // ceci n'effectue aucune allocation dynamique

Il existe la même symétrie avec l’expression delete qui utilise le destructeur suivi d’une libération de la mémoire.

p->~T(); // appel explicite du destructeur
operator delete(p); // libération de la mémoire

Ceci représente le cas de base pour une gestion plus fine de la mémoire. Pour information, c’est une partie de ce qu’utilisent les containers de la STL tel que std::vector à travers les allocateurs (std::allocator). Une partie seulement, car C++17 ajoute un paramètre d’alignement.

Séparation en catégorie

Tous les opérateurs new et presque tous les opérateurs delete sont séparés en 2 catégories: une version tableau et une version sans.

Par exemple void* operator new(std::size_t) et void *operator new[](std::size_t). À part les 4 nouveaux opérateurs delete de C++20, il n’y a pas d’exception.

Il y a néanmoins une différence de comportement avec les operator new[]: La taille nécessaire à leur allocation peut être supérieure à sizeof(T) * len. Il y a un surplus permettant de stocker la taille du tableau et ainsi appeler le bon nombre de destructeurs au moment du delete[]. Cet ajout est automatiquement fait par le compilateur et dépend de son implémentation.

Toute la suite de l’article ne présentera plus les versions tableaux, car le principe derrière est exactement le même que les versions sans tableau.

Plus que 11 opérateurs new et 17 delete :)

Fonctions d’allocation remplaçables

Parmi les opérateurs disponibles, il existe 16 fonctions candidates au remplacement de la fonction d’allocation. C’est-à-dire qu’utiliser new T/new T[n] ou delete p/delete[] p va implicitement faire appel à l’une de ces fonctions que l’utilisateur peut lui-même définir pour changer le comportement par défaut.

La version operator new, en plus du paramètre std::size_t count représentant le nombre d’octets à allouer, prend 2 paramètres optionnels:

  • std::nothrow_t qui représente l’absence d’exception et
  • std::align_val_t qui indique l’alignement de l’allocation.
void* operator new(std::size_t count);
void* operator new(std::size_t count, std::align_val_t al);
void* operator new(std::size_t count, const std::nothrow_t&) noexcept;
void* operator new(std::size_t count, std::align_val_t al, const std::nothrow_t&) noexcept;
// plus version new[]

Le paramètre std::nothrow_t s’utilise pour un new de la forme new(std::nothrow) T. Cela ne veut pas dire qu’il n’y aura jamais d’exception (le constructeur de T peut le faire), mais que l’allocation de l’espace mémoire nécessaire ne le fera pas. Si l’allocation échoue, un pointeur nul est retourné.

std::align_val_t fait référence aux types dont l’alignement est supérieur à __STDCPP_DEFAULT_NEW_ALIGNMENT__ et sera alors automatiquement ajouté par le compilateur. Cela dépend des implémentations, mais cette valeur devrait être au moins de la taille du plus grand type disponible, à priori long double.

En supposant que __STDCPP_DEFAULT_NEW_ALIGNMENT__ fait 16, pour utiliser la version new avec alignement, il faudrait un type tel que struct alignas(32) A {};.

Ensuite vient operator delete qui, à la place d’une taille, prend le pointeur à libérer.

void operator delete(void* ptr) noexcept;
void operator delete(void* ptr, std::align_val_t al) noexcept;
void operator delete(void* ptr, const std::nothrow_t&) noexcept;
void operator delete(void* ptr, std::align_val_t al, const std::nothrow_t&) noexcept;
void operator delete(void* ptr, std::size_t sz) noexcept;
void operator delete(void* ptr, std::size_t sz, std::align_val_t al) noexcept;
// plus version delete[]

Et les ennuis commencent. Il y a bien une correspondance 1-1, mais 2 fonctions prenant un std::size_t sz se sont subtilement ajoutées.

Le paramètre sz ajouté en C++14 correspond à la taille de l’objet libéré. Néanmoins, les 2 fonctions avec ce paramètre peuvent ne pas être utilisées pour les types trivialement destructibles ou incomplets. Dans ce cas, ce sont les versions sans ce paramètre qui seront utilisées. Actuellement, gcc utilise bien les fonctions avec le paramètre sz à partir de C++14, mais il faut le forcer avec -fsized-deallocation pour les standards inférieurs. Pour clang, ce flag est requis quel que soit le standard utilisé.

Les versions avec std::nothrow_t sont utilisées lorsque le constructeur de T dans l’expression new(std::nothrow) T jette une exception. Dans ce cas, l’exception est relancée après libération de la mémoire.

Peut-on faire une quelconque différence d’implémentation entre les delete qui prennent des std::nothrow_t et ceux qui ne les prennent pas ? Je ne pense pas, je n’arrive pas à imaginer un tel scénario.

Étrangement, il n’y a pas de prototype qui utilise en même temps sz et std::nothrow_t, alors que l’information de taille pourrait être utilisée pour accélérer certaines désallocations.

Encore 7 opérateurs new et 11 delete.

Placement-new, la construction sans allocation

Le placement-new est ce qui permet de construire un objet depuis une zone mémoire préalablement réservée. Soit via un tableau statique, soit à travers une allocation dynamique.

alignas(T) char buffer[sizeof(T)];
T* p = new(buffer) T; // construction de T

La destruction de cet objet se fait manuellement via un appel direct du destructeur (p->~T()) puis en libérant le buffer si nécessaire.

Cet appel à new correspond au prototype ci-dessous dont l’implémentation est prédéfinie par la bibliothèque standard:

void* operator new(std::size_t count, void* ptr) noexcept;
// + version new[]

Néanmoins, il est possible de surcharger cette fonction pour y introduire n’importe quel paramètre:

void* operator new(std::size_t count, user-defined-args...);
void* operator new(std::size_t count, std::align_val_t al, user-defined-args...);
// + version new[]

count correspond au sizeof de T et la version avec alignement sera automatiquement utilisée si définie et que l’alignement de T dépasse __STDCPP_DEFAULT_NEW_ALIGNMENT__. Dans le cas contraire, le compilateur se rabat sur celle sans alignement.

T* p = new(storage, opt) T; // pourrait correspondre à operator new(std::size_t count, Storage&, StorageOptions)
                            // et operator new(std::size_t count, std::align_val_t al, Storage&, StorageOptions)

Chacun de ses new a son équivalent delete dans le cas où le constructeur lance une exception.

La version de la bibliothèque standard qui ne fait normalement rien:

void operator delete(void* ptr, void* place) noexcept;
// + version delete[]

Et les surcharges utilisateur:

void operator delete(void* ptr, user-defined-args...);
void operator delete(void* ptr, std::align_val_t al, user-defined-args...);

cppreference.com ne fait pas explicitement mention de la version avec std::align_val_t, mais je l’ajoute pour une meilleure correspondance avec les prototypes de new.

On peut sérieusement se demander à quoi peut servir ces opérateurs prenant n’importe quel type, alors qu’ils pourraient très bien être remplacés par une fonction classique. Une fonction est beaucoup moins tordue que new(a,b,c) T.

Plus que 4 opérateurs new et 9 delete.

Les opérateurs new et delete membre

Jusqu’ici, tous les opérateurs étaient des fonctions libres qui ne peuvent avoir connaissance du type réellement alloué. Il est possible d’avoir cette information en déclarant les opérateurs new et delete en membre statique d’une classe. Les versions membres seront prioritaires à celles libres.

void* T::operator new(std::size_t count);
void* T::operator new(std::size_t count, std::align_val_t al);
void* T::operator new(std::size_t count, user-defined-args...);
void* T::operator new(std::size_t count, std::align_val_t al, user-defined-args...);
// + version new[]
void T::operator delete(void* ptr) noexcept;
void T::operator delete(void* ptr, std::align_val_t al) noexcept;
void T::operator delete(void* ptr, std::size_t sz) noexcept;
void T::operator delete(void* ptr, std::size_t sz, std::align_val_t al) noexcept;
void T::operator delete(void* ptr, args...) noexcept;
// + version delete[]

Le nombre de prototypes est inférieur au nombre de fonctions libres, mais il est tout à fait possible de les réintroduire via les types utilisateurs.

Petite particularité des opérateurs membres: il est possible d’interdire les allocations dynamiques en supprimant la fonction avec void* operator new(std::size_t count) = delete. On peut cependant outrepasser cette restriction en utilisant l’opérateur global avec ::new T.

Bientôt la fin, il ne reste que 4 opérateurs delete.

L’opérateur delete chargé d’utiliser le destructeur

En début d’article, j’indique que la construction d’un objet se fait en 4 étapes représentées par 4 appels de fonctions consécutives:

  • Allocation de la mémoire
  • Construction de l’objet dans la mémoire allouée
  • Appel du destructeur
  • Libération de la mémoire

C++20 introduit 4 opérateurs delete qui doivent eux-mêmes faire l’appel du destructeur en plus de la libération.

void T::operator delete(T* ptr, std::destroying_delete_t);
void T::operator delete(T* ptr, std::destroying_delete_t, std::align_val_t al);
void T::operator delete(T* ptr, std::destroying_delete_t, std::size_t sz);
void T::operator delete(T* ptr, std::destroying_delete_t, std::size_t sz, std::align_val_t al);
// pas de version delete[] à cause de l'overhead ajouté par le compilateur pour new[]

On y retrouve al et sz qui suivent les mêmes règles que d’habitude et un type std::destroying_delete_t qui permet une différenciation avec les autres fonctions.

Les raisons de cet ajout sont expliquées dans la proposition P0722 qui corrige les sized-delete avec des classes à taille variable (entre autres).

Pour expliquer le fonctionnement, une classe à taille variable n’est constructible qu’à travers une allocation dynamique de la mémoire ; son allocation contient un surplus de taille contenant la partie variable. Par exemple, une string peut être un segment contenant la taille suivie des chars. Tout cela dans le même segment de donnée. Comme la partie variable n’est pas dans l’objet lui-même, un sizeof de ce type de chaîne correspond à la taille de son seul membre: std::size_t length (par exemple). Les données variables sont ensuite accessibles via reinterpret_cast<char*>(this + 1). On peut retrouver la même chose avec des données variables insérées avant le pointeur de l’objet.

Le problème de ce type de classe apparaît au moment de la libération: comment utiliser l’opérateur delete prenant une taille ou un alignement quand ces 2 informations ne font pas partie du type ? Celui introduit par le compilateur sera erroné. Ou encore, comment récupérer le pointeur d’origine lorsque les données sont insérées avant le type utlisé ?

Dans le premier scénario, une solution (fausse) est de récupérer cette information depuis la fonction void T::operator delete(void* ptr) en castant ptr en type T pour y extraire les informations nécessaires. Malheureusement, ptr représente un T détruit (destructeur utilisé): lire ses membres est invalide.

Pour pallier à tous ces problèmes, les opérateurs delete introduits en C++20 prennent non plus un void* ptr, mais un T* ptr encore valide. C’est pour cette raison que cette fonction doit elle-même appeler le destructeur.

Quant au pointeur alloué, il peut vivre sa vie comme n’importe quel pointeur et être utilisé dans – par exemple – un std::unique_ptr.

Remplacement de l’allocateur global

L’allocateur global est plutôt facile à remplacer, mais seuls les opérateurs considérés comment remplaçables pourront être utilisés de manière transparente. Cela exclut les new/delete avec des variables utilisateurs dont les prototypes doivent être connus par le programme qui les utilise.

Pour ce faire, il suffit de compiler un .cpp qui contient les opérateurs pour en faire soit un .o, soit une bibliothèque. Dans les 2 cas, le bout de code sera compilé dans l’exécutable final.

Dans le cas d’une bibliothèque externe, il est possible de la charger « plus tard » via les méthodes propres à chaque système d’exploitation. Par exemple, les variables d’environnement LD_PRELOAD et LD_LIBRARY_PATH pour Linux.

La sémantique de déplacement

Article suivant: Les opérateurs new et delete
Article précédent: SFINAE

L’objectif derrière la sémantique de déplacement est de transférer les données d’un objet A à un objet B. Si les 2 objets sont du même type, on parle de constructeur de déplacement ou affectation par déplacement. Cela permet 2 choses:

  • Garantir l’unicité d’une ressource. La responsabilité étant passée à quelqu’un d’autre, il n’y a toujours qu’un seul propriétaire en charge de la durée de vie de celle-ci.
  • Éviter des copies profondes (deep copies) en les remplaçant par des copies superficielles (shallow copies) plus performantes.

Toute autre raison est une erreur.

Principe d’unicité

Prenons un petit animal sauvage et nommons-le Pikachu. Ce Pikachu est unique, il n’en existe qu’un seul dans tout l’univers. Si on compare notre Pikachu à un autre Pikachu, ils sont différents, il n’y en a pas 2 pareils, même s’ils ont le même nom.

Rangeons-le dans sa pokéball.

std::vector<Pokemon> my_bag;
my_bag.emplace_back("Pikachu");

Un soir, au coin du feu, un brigand passe par là et prend notre sac.

brigand.bag = my_bag;

Et tout l’univers est sans dessus-dessous, notre Pikachu existe en double, le principe d’unicité est brisé !

Heureusement, Pokemon n’étant pas copiable, le code ne compile pas. Ouf, l’univers est sauf !

Du coup, plutôt que copier le sac, on le déplace directement dans celui de brigand en utilisant la fonction std::move.

brigand.bag = std::move(my_bag);

Au passage, on vient d’écraser tout ce qu’il y avait dans le sac de notre voleur ; bien fait pour lui ! Mais le plus important est là: Pikachu appartient maintenant au brigand, my_bag ne devrait plus être utilisé. On a bien eu un transfert des pokémons d’un sac A vers un sac B, il y a eu déplacement.

Copie profonde et copie superficielle

La copie profonde est une copie de tous les membres, y compris des données référencées par un pointeur lorsque leur durée de vie est gérée par la classe. Ce dernier point est important, car sans pointeur – et pour aller plus loin, sans ressource, – il n’y a pas de différence entre une copie classique ou une copie superficielle. Vouloir les opérateurs de déplacement dans cette dernière situation ne sert à rien, l’implémentation serait strictement identique à celle d’une copie. Autre point, même s’il y a un pointeur, il faut que les fonctions de copie fassent une copie profonde pour que les fonctions de déplacements puissent faire une copie superficielle, sinon, rebelote, aucune différence avec la copie.

Comme une illustration est plus parlante, supposons une classe vector avec 2 variables membres:

  • int* p, un pointeur alloué dynamiquement et désalloué dans le destructeur
  • size_t n qui représente le nombre d’éléments alloué

L’instance de référence nommé A contient les nombres 7, 1, 3, 7, 0, 5, ce qui donne en mémoire

A = {
  p = /*adresse=*/0x12345678 /*valeurs=*/{ 7, 1, 3, 7, 0, 5 }
  n = 6
}

La copie profonde va faire une nouvelle allocation dynamique et copier les valeurs de A.p dans B.p. L’adresse du pointeur est donc différente, mais le contenu est identique.

// B = A
B = {
  p = /*adresse=*/0x87654321 /*valeurs=*/{ 7, 1, 3, 7, 0, 5 }
  n = 6
}

La copie superficielle effectuée par un déplacement n’alloue pas de mémoire, elle copie simplement A.p dans B.p qui est une opération bien plus rapide. L’adresse des pointeurs est identique.

// B = std::move(A)
B = {
  p = /*adresse=*/0x12345678 /*valeurs=*/{ 7, 1, 3, 7, 0, 5 }
  n = 6
}

Malheureusement, lorsque le destructeur est appelé, il libère la mémoire du pointeur p qui est partagé entre A et B. Cela donne inévitablement une double désallocation qui finit sur un crash de l’application. Pour prévenir cette erreur, A.p ne doit pas être libéré, par exemple en mettant le pointeur à nullptr.

// B = std::move(A)
A = {
  p = nullptr
  n = 0
}

Le déplacement a le même fonctionnement que le principe d’unicité: l’allocation dynamique (la ressource) ne doit être possédée que par une seule instance.

Constructeur de déplacement

Le constructeur de déplacement prend ce qu’on nomme une rvalue (noté T&&). C’est une référence qui se veut temporaire. Si la valeur de cette expression provient d’une opération, elle doit être capturée dans la classe, autrement, elle est perdue. Lorsque cette valeur provient d’un déplacement explicite comme avec std::move(x), il faut considérer que x est dans un état qui ne permet plus de l’utiliser (sauf si la documentation indique le contraire).

À savoir que toutes variables – quel que soit son type réel – est toujours manipulée comme une lvalue. C’est-à-dire qu’avec int i; foo(i);, la fonction foo() reçoit une référence (int&), pas juste int.

Pour prendre un exemple connu, les chapitres suivants reposent sur le fonctionnement de std::unique_ptr, un pointeur intelligent qui fait une désallocation automatique de la mémoire dans son destructeur et interdit la copie pour respecter le principe d’unicité.

#include <cassert>

struct unique_ptr
{
  using value_type = int; // normalement un type template,
                          // mais pour cet exemple, juste un int

  unique_ptr(value_type* p = nullptr)
  : m_p(p)
  {}

  // Notre constructeur de déplacement
  // D'après la documentation std::unique_ptr, après cette fonction
  // other.m_p doit être nullptr
  unique_ptr(unique_ptr&& other);

  ~unique_ptr()
  {
    delete m_p;
  }

  // Pour simplifier, la classe ne possède que `operator*` et `operator bool ()`

  explicit operator bool () const
  {
    return m_p;
  }

  value_type& operator*()
  {
    assert(m_p);
    return *m_p;
  }

private:
  value_type* m_p;
};

Et un premier exemple d’utilisation.

#include <iostream>
#include <utility>

void print(unique_ptr& ptr)
{
  if (ptr) std::cout << *ptr;
  else std::cout << "nullptr";
  std::cout << "\n";
}

int main()
{
  unique_ptr p1(new int(3));
  unique_ptr p2{std::move(p1)}; // on déplace p1 dans p2

  // p1 est vide, cela affiche nullptr
  std::cout << "p1: ";
  print(p1);

  // p2 possède un pointer valide, cela affiche 3
  std::cout << "p2: ";
  print(p2);
}

Reste l’implémentation du constructeur de déplacement. Comme dit précédemment, seule une instance doit posséder le pointeur interne. L’instance déplacée doit être modifiée pour ne plus y faire référence, tout en restant dans un état dit destructible pour que le destructeur fonctionne convenablement. Les prérequis de MoveConstructible parlent d’un état non spécifié. C’est-à-dire que l’implémentation est libre de faire ce qu’elle veut du moment que la destruction fonctionne encore, mais il ne faut plus utiliser la variable.

Cependant, chaque fonction peut explicitement documenter le comportement comme c’est le cas avec std::unique_ptr qui met le pointeur déplacé à nullptr.

unique_ptr::unique_ptr(unique_ptr&& other)
: _p(std::exchange(other._p, nullptr))
{}

Finalement beaucoup d’explications pour 1 ligne de code. Mais nous sommes loin d’avoir terminé, notre unique_ptr ne respecte pas tous les prérequis nécessaires pour un bon constructeur de déplacement. Il n’y a pas non plus d’affectation par déplacement qui amène à de grosse surprise. Et surtout, qui nous dit qu’il n’est pas copiable ?

Fonctions spéciales

Une classe possède 6 fonctions spéciales générées automatiquement par le compilateur:

  • le constructeur par défaut
  • le constructeur par copie
  • l’affectation par copie
  • le constructeur par déplacement
  • l’affectation par déplacement
  • le destructeur

Si aucune de ces fonctions n’est déclarée dans la classe, leur existence dépend des membres la composant. Ainsi, si un membre comme std::unique_ptr existe, les 2 fonctions liées à la copie seront implicitement supprimées car inexistantes pour le type std::unique_ptr.

De plus, définir explicitement certaines fonctions va en désactiver d’autres. Il est nécessaire d’utiliser =default pour les réactiver.

↓déclare / existe→ default-ctor copy-ctor copy-assignment move-ctor move-assignment
default-constructor
copy-constructor
copy-assignment
move-constructor
move-assignment
destructor

À cela s’ajoute que le constructeur par défaut n’est plus défini en présence de n’importe quel autre constructeur (pas uniquement ceux de copie ou de déplacement).

Si on reprend notre unique_ptr précédemment, ce tableau affirme une chose: la copie n’est pas possible et l’affectation par déplacement est bien manquante.

À titre personnel, je pense qu’il vaut mieux explicitement indiquer que la copie est interdite, soit via une classe spécifique comme boost::noncopyable soit en ajoutant les prototypes suivants:

unique_ptr(unique_ptr const&) = delete;
unique_ptr& operator=(unique_ptr const&) = delete;

Quitte à déclarer certaines fonctions comme étant supprimées, il est aussi plus explicite pour l’utilisateur de la classe de mettre explicitement =default pour les autres fonctions. C’est le principe de la règle de 5 qui consiste à définir explicitement les fonctions spéciales (en excluant le constructeur par défaut dans cette règle).

À savoir aussi que – sauf cas très spécifique – les constructeurs et operator= vont par paire. Si l’un est implémenté, l’autre devrait l’être également. Ce que nous allons faire dans le prochain chapitre.

Affectation par déplacement

Cette fonction est proche du constructeur de déplacement, mais possède un petit piège qu’il est bon de savoir. Commençons par une implémentation possible:

unique_ptr& operator=(unique_ptr&& other)
{
  delete m_p;
  m_p = std::exchange(other.m_p, nullptr); // ligne qu'on retrouve dans le constructeur
  return *this;
}

En apparence, aucun problème, le pointeur à l’intérieur de other est déplacé puis remis à zéro, alors que l’ancien se fait détruire. Un petit test le confirme:

int main()
{
  unique_ptr p1{new int(3)};
  unique_ptr p2;

  print(p2); // nullptr
  p2 = std::move(p1);
  print(p2); // p2 contient int* sur 3
  print(p1); // p1 est maintenant nullptr
}

Mais que se passe-t-il si on fait un déplacement sur soi-même ?

int main()
{
  unique_ptr p{new int(3)};
  print(p); // 3
  p = std::move(p);
  print(p); // ???
} // double-free !!!

Le code affiche n’importe quoi et explose ! La raison est toute bête, on désalloue le pointeur puis on récupère celui dans other qui est identique au pointeur précédemment libéré. Une écriture aussi explicite que p = std::move(p) n’a pas beaucoup de sens, mais il est possible d’arriver dans une telle situation avec un code plus complexe et 2 variables à priori bien distinctes.

Si on se réfère au prérequis de MoveAssignable, il n’y a aucune indication sur l’état de t dans t = rv lorsque t et rv sont la même référence. Plusieurs choix s’offrent à nous en cas de self-move-assignment:

  • considérer cela comme un comportement indéfini
  • définir rv comme étant égal à nul (donc le pointeur est ici supprimé)
  • définir t comme contenant le pointeur de rv (et donc ici ne rien faire)

Self-move-assignment comme comportement indéfini

Ce choix peut paraitre étrange voire dangereux, mais il est justifié pour un besoin de performance: le déplacement doit être rapide. Gérer un tel scénario demande du code supplémentaire – généralement un if (this != &other) – et cela peut avoir un impact signification pour un cas de figure fortement marginal. Le choix du standard penche beaucoup pour un comportement indéfini et seules certaines classes l’autorisent.

Pour information, les implémentations de libc++ et libstdc++ (clang et gcc) vident les containers tel que std::vector. Il y a même une assertion si on utilise libstdc++ avec la macro _GLIBCXX_DEBUG.

#include <vector>

int main()
{
  std::vector<int> v{1,2,3};
  v = std::move(v); // kaboum avec -D_GLIBCXX_DEBUG: https://godbolt.org/z/Gn4KWe
  // v.size() == 0
}
g++ test.cpp -D_GLIBCXX_DEBUG && ./a.out
[...]
Error: attempt to self move assign.
[...]

Définir l’état de rv sur self-move-assignment

Dans ce scénario, seul l’état de rv dans t = rv est défini comme étant à nul. Pour ce faire, on désalloue le pointeur de t puis on le met à nullptr. Après un déplacement sur soi-même, le pointeur est systématiquement détruit.

unique_ptr& operator=(unique_ptr&& other)
{
  delete m_p;
  m_p = nullptr; // other.m_p devient nullptr quand other.m_p == m_p
  m_p = std::exchange(other.m_p, nullptr);
  return *this;
}

Ce comportement n’est pas très logique. Ce qui importe dans un déplacement est de connaître l’état de la destination (t). De plus, se retrouver avec t == nullptr est en contradiction avec le comportement principal du déplacement: « la valeur de t est équivalent à la valeur de rv avant affectation ».

Finalement ce choix n’est pas très judicieux.

Définir l’état de t sur self-move-assignment

Ici l’état de t est défini, même quand t = rv équivaut à un déplacement sur soi-même. Si c’est le cas, on ne désalloue rien et le déplacement ne fait rien: on a bien t équivalent à la valeur de rv avant affectation.

unique_ptr& operator=(unique_ptr&& other)
{
  auto* new_p = std::exchange(other.m_p, nullptr);
  delete m_p; // m_p = nullptr quand other.m_p == m_p
  m_p = new_p;
  return *this;
}

Cette dernière peut aussi s’écrire avec l’idiome copy-and-swap ou avec if (this == &other) return *this en début de fonction pour complètement ignorer l’affectation sur soi-même. Personnellement, j’évite les conditions dans les fonctions de déplacement lorsque cela est possible.

// copy-and-swap
unique_ptr& operator=(unique_ptr other) // on prend par valeur
{
  using std::swap;
  swap(other.m_p, m_p); // et on swap
  return *this;
  // le destructeur de other va libérer la mémoire à sa destruction
}

Ce comportement pour le déplacement est celui documenté dans std::unique_ptr qui impose l’équivalence à reset(r.release()): la valeur ne change pas lorsque t et rv référencent le même objet.

Les déplacements devraient être noexcept

C’est une chose qu’on oublie facilement, mais les fonctions de déplacement devraient être noexcept pour 2 raisons simples:

  • Le déplacement est une opération qui se veut la plus triviale possible. Les risques d’exception sont normalement nuls.
  • Les containers de la STL utilisent les fonctions de déplacement à la condition que ceux-ci sont noexcept ou qu’il n’y ait pas de fonction de copie. Voici un exemple qui montre le problème.
#include <vector>
#include <cstdio>

// copie interdite
struct A
{
  A()=default;
  A(A const&)=delete;
  A(A&&) { std::puts("A&&"); }
};

// copie autorisée, mais déplacement qui n'est pas noexcept
struct B
{
  B()=default;
  B(B const&)=default;
  B(B&&) { std::puts("B&&"); }
};

// copie autorisée et déplacement noexcept
struct C
{
  C()=default;
  C(C const&)=default;
  C(C&&) noexcept { std::puts("C&&"); }
};

int main()
{
  // va afficher au moins un A&&
  std::vector<A> a;
  a.emplace_back();
  a.emplace_back();
  a.emplace_back();

  // aucun B&&
  std::vector<B> b;
  b.emplace_back();
  b.emplace_back();
  b.emplace_back();

  // va afficher au moins un C&&
  std::vector<C> c;
  c.emplace_back();
  c.emplace_back();
  c.emplace_back();
}

(Je n’ai pas mis operator=, mais il est évident que la version par déplacement devrait aussi être noexcept.)

Une note sur l’implémentation derrière: les containers se basent sur la fonction std::move_if_noexcept.

La vérité vraie du mensonge qu’est std::move

Je ne vais pas mentir, tout le baratin précédent n’est là que pour placer ce chapitre. Autant de bla bla juste pour le plaisir de mettre ce titre :).

Ceci dit, arrivé ici, vous devriez être conscient que std::move ne fait pas grand-chose: tout se situe dans les constructeurs et opérateurs de déplacement.

Mais alors, que fait std::move ? Eh bien, rien… Ou plus précisément, la fonction ne touche pas à l’instance, mais à la catégorie de valeur. Ce n’est rien de plus qu’un cast d’une lvalue en rvalue ! On pourrait tout aussi bien remplacer std::move(x) par static_cast<std::remove_reference_t<decltype(x)>&&>(x) , le résultat serait exactement le même – à la verbosité près.

Puisque std::move n’est rien de plus qu’un cast, il est inutile de l’utiliser sur des rvalues. std::move(Bidule{}) n’a aucun sens, Bidule{} est déjà une rvalue (mieux, c’est une prvalue). Il n’est pas non plus nécessaire de l’utiliser sur le retour des fonctions qui bénéficient de la RVO et de l’élision de copie en général.

Pire, utiliser std::move lorsque cela n’est pas nécessaire désactive certaines optimisations. Sur ce point, gcc et clang ont tous deux les avertissements -Wpessimizing-move et -Wredundant-move qui se déclenchent sur une utilisation inappropriée de std::move.

A foo()
{
  A ret;
  // ...
  return std::move(ret); // -Wpessimizing-move
  return ret; // NRVO
}

A foo(A a)
{
  return std::move(a); // -Wredundant-move
}

A bar()
{
  foo(std::move(A{})); // -Wpessimizing-move
  return std::move(foo()); // -Wpessimizing-move
  return foo(); // RVO
}

std::forward

Pour finaliser les explications sur le déplacement, il faut introduire std::forward.

Cette fonction n’est utile que sur des types templates dont la catégorie de valeur n’est pas connue. L’exemple le plus simple est une fonction template<class T> void foo(T&& x);T représente une forwarding reference. Càd une référence qui est soit une lvalue, soit une rvalue. On peut aussi croiser le nom de référence universelle venant d’avant la normalisation du nom officiel.

Il faut bien comprendre que les forwarding references s’appliquent sur un type template complet, ce qui n’est pas le cas par exemple pour void foo(std::vector<T>&& vec) où la fonction attend toujours une rvalue.

Le but de std::forward est de propager la référence en castant une variable vers une rvalue quand le type d’origine est une rvalue (n’oublions pas qu’à ce niveau, une variable est une lvalue, même si son type est une rvalue).

#include <iostream>

void foo(int&& x) { std::cout << "foo(int&&)\n"; }
void foo(int& x) { std::cout << "foo(int&)\n"; }

template<class T>
void bar(T&& x)
{
  foo(std::forward<T>(x)); // `x` est castée en rvalue lorsque T&& est une rvalue
}

int main()
{
  int i = 0;
  bar(i);            // foo(int&)
  bar(std::move(i)); // foo(int&&)
}

Sans l’usage de std::forward, les 2 appels donneraient foo(int&).

Si on veut comprendre la magie derrière, il faut regarder le type réel de T:

  • bar(i): T&& = int&. T = int&
  • bar(std::move(i)): T&& = int&&. T = int.

Appliquer une rvalue sur un type qui est une lvalue donne une lvalue. C’est ce qu’on appelle les règles de reference collapsing.

lhs rhs référence
& & &
& && &
&& & &
&& && &&

C’est également le mécanisme derrière std::forward<T>(x) qui combine simplement T à une rvalue pour caster la variable dans la bonne catégorie de valeur. Ceci est strictement équivalent à static_cast<T&&>(x) ou static_cast<decltype(x)&&>(x). Certains projets définissent une macro FWD(x) qui fonctionne ainsi.

Que personne ne bouge, v’là la conclusion

Pour résumer tout ça:

  • std::move n’est qu’un cast user-friendly vers une rvalue, ce n’est pas lui qui fait le déplacement à proprement parler. Mal l’utiliser désactive aussi certaines optimisations.
  • Le comportement du déplacement est défini par les fonctions qui reçoivent une rvalue.
  • Définir certaines fonctions spéciales en désactivent d’autres, il est préférable d’indiquer explicitement le comportement de chacune de préférence avec =default ou =delete. Pour rappel, les fonctions spéciales sont ici les constructeurs de déplacement et de copie, l’affectation par déplacement et de copie ainsi que le destructeur.
  • le constructeur de déplacement et l’affectation par déplacement devrait être noexcept pour que les containers de la STL les utilisent.
  • std::forward s’utilise pour des paramètres template de la forme T&& pour propager le type de référence (lvalue ou rvalue).

Voilà qui clôture cet article sur la sémantique de déplacement. Et n’oubliez pas, une variable n’est jamais une rvalue et – sauf exception de la NRVO – il faut explicitement utiliser std::move pour l’utiliser comme une rvalue.

SFINAE

Article suivant: La sémantique de déplacement
Article précédent: Effets et utilisations de noexcept

SFINAE (Substitution Failure Is Not An Error) est un mécanisme du compilateur pour ignorer certaines instanciations de fonction ou de classe qui ne compilent pas, sans pour autant émettre une erreur de compilation.

Pour comprendre pleinement le mécanisme derrière, il faut assimiler le principe de substitution appliquée par le compilateur. Lorsqu’une expression dépend d’un paramètre template, le compilateur va évaluer l’expression en la substituant par le type ou la valeur de l’expression. Prenons le code suivant:

struct A { using type = int; };

template<class T>
void foo(typename T::type value);

foo<A>(3);

À l’appel de foo<A>, le compilateur remplace typename T::type par A::type, qui correspond ici à int. C’est la substitution. Lorsque le compilateur n’arrive pas à faire cette substitution – car par exemple il n’y a pas de membre type – il va chercher une autre fonction foo<A> qui pourrait être utilisée.

struct B { using value_type = int; };

template<class T>
void foo(typename T::type value); // B::type n'existe pas, cette fonction est ignorée

template<class T>
void foo(typename T::value_type value);

foo<B>(3);

Bien sûr, si le compilateur peut utiliser les 2 fonctions foo précédentes, il y aura ambiguïté et finalement une erreur.

struct C
{
  using value_type = int;
  using type = int;
};

foo<C>(3);
test.cpp:15:3: error: call to 'foo' is ambiguous
  foo<C>(3);
  ^~~~~~
test.cpp:2:6: note: candidate function [with T = C]
void foo(typename T::type value);
     ^
test.cpp:5:6: note: candidate function [with T = C]
void foo(typename T::value_type value);
     ^

Il faut bien comprendre que SFINAE n’est pas un mécanisme pour simplifier les messages d’erreur, ni pour les ignorer. Le résultat est même plutôt inverse, à un certain point, il est difficile de savoir pourquoi une fonction est utilisée à la place d’une autre, le compilateur ne donnant aucun diagnostic. Les erreurs sont plus verbeuses – l’ensemble des prototypes sont listés – et les ambiguïtés difficiles à corriger sans ajouter de la complexité.

Plus le nombre de prototypes liés à un nom de fonction croît, plus le code devient difficile et les erreurs – principalement d’ambiguïtés – nombreuses. Il faut bien réfléchir à la manière de s’y prendre pour ne pas être happé par le code avec des prototypes à rallonge à ne plus savoir quoi en faire. Le but de cet article est de présenter différentes solutions pour exploiter SFINAE sans être enfermé dans un usage unique qui se limite souvent à la superposition de condition dans un std::enable_if_t.

Dépendance de type/valeur

Le SFINAE repose entièrement sur les valeurs ou types template, on parle de value-dependent ou type-dependent (je ne ferais pas de distinction entre les 2). Tout ce qui n’est pas lié à une valeur template sera évalué automatiquement par le compilateur, que l’expression soit ou non dans une classe ou une fonction template.

Par exemple:

struct A { using type = int; };

template<class T>
int foo(T x, A::type y) // A::type doit exister, car le type n'est pas type-dependent
                        // Si A::type n'existe pas, il y aura une erreur
                        // même si foo() n'est pas utilisée
{
  return x + 1; // Cette expression dépend de x qui est template,
                // une erreur ne pourra survenir qu'au moment de l'instanciation de foo()
  return ""; // cette expression n'a aucune dépendance -> il devrait y avoir une erreur
}

Si le compilateur respecte scrupuleusement la norme et sans la moindre utilisation de foo(), tout ce qui n’a pas de dépendance doit être évalué au plus tôt et systématiquement.

  • le type A::type doit exister
  • le second retour ne doit pas compiler

Étrangement, du moment que la fonction n’est pas utilisée, gcc ne vérifie pas si le retour est convertible vers celui de la fonction, mais demande quand même une expression valide, alors que msvc ne fait aucune vérification au sein de la fonction. Par contre clang indique qu’une chaîne de caractères n’est pas convertible en int.

L’évaluation systématique des types indépendants explique pourquoi le code ci-dessous donne toujours une erreur.

if constexpr (xxx)
{
  // ...
}
else
{
  static_assert(false); // toujours évalué -> erreur de compilation
}

On touche ici au contexte d’évaluation: le prototype, suivi du corps de fonction. Le second est évalué différemment selon les compilateurs, mais cela ne cause pas réellement de problème, car les erreurs apparaissent au moment de l’utilisation de la fonction.

Quand on parle de contexte, on parle aussi de sous-contexte. Dans le cas de SFINAE, la dépendance d’un contexte au contexte parent ne peut pas être attrapé, ce qui résultera dans tous les cas à une erreur de compilation. Le corps d’une fonction est un exemple, un autre concerne les membres d’une classe:

struct A
{
  using type = int;
};

struct B
{};

template<class T>
struct C // contexte principal (instanciation de la structure)
{
  using type = typename T::type; // sous-contexte,
                                 // T::type dépend de T du contexte parent
};

template<class T, class = typename T::type>
constexpr int foo(int)
{ return 1; }

template<class T>
constexpr int foo(char)
{ return 2; }

static_assert(foo<A>(0) == 1);
static_assert(foo<B>(0) == 2);
static_assert(foo<C<A>>(0) == 1);
static_assert(foo<C<B>>(0) == 2); // erreur
test.cpp:12:28: error: no type named 'type' in 'B'
  using type = typename T::type; // sous-contexte,
               ~~~~~~~~~~~~^~~~
test.cpp:16:36: note: in instantiation of template class 'C<B>' requested here
template<class T, class = typename T::type>
                                   ^

Pour que C fonctionne avec SFINAE, il faut une spécialisation de C sans le membre type. Cela requière un développement spécifique qui rend le support de SFINAE quelquefois difficile à mettre en place.

Emplacement des expressions pour le SFINAE

Partout où il est possible de mettre un type ou une valeur est propice à la substitution: paramètre template, contenu de noexcept, decltype, sizeof et même les paramètres par défaut. Quel que soit l’emplacement, si le compilateur ne trouve pas une expression qu’il peut compiler, il va simplement ignorer la fonction ou l’instanciation.

Généralement, pour vérifier une expression, le plus simple est d’ajouter un paramètre de template initialisé avec l’expression qui doit être valide ou passer par decltype. Pour ce dernier, une petite astuce pour ajouter plusieurs expressions consiste à les séparer par des virgules et entourer le tout d’une paire de parenthèse:

template<..., class = decltype(...)> // ici ou
auto f(...) -> decltype(((void)expr1, (void)(expr2), expr3));
                     // ^ pour que decltype ne voit qu'une expression
                     //  ^ le cast en void permet d'inhiber d'éventuelle surcharge de ,
                     //             ^ la virgule pour séparer chacune des expressions
                     //                              ^ l'expression pour le type de retour

Technique et usage du SFINAE

À partir de maintenant, je vais présenter les techniques qui me viennent à l’esprit en me basant si possible sur des éléments de la STL pour des exemples pratiques. Les plus curieux pourront comparer avec l’implémentation de la STL qu’ils utilisent (msvc, clang (libc++) et gcc (libstdc++) pour les plus connues).

Sélection de fonction à travers un type membre

Dans ce premier exemple, nous allons voir comment implémenter std::make_unique. Pour rappel, il existe 3 versions:

make_unique<T>(args...) -> unique_ptr<T>;
make_unique<T[]>(size) -> unique_ptr<T[]>; // arrays of unknown bound
make_unique<T[N]>(args...) = delete; // arrays of known bound

Comme le premier type template influence les paramètres et le type de retour, le plus simple est un trait qui va sélectionner le bon prototype. Contrairement au trait que l’on rencontre habituellement, celui-ci va définir un type membre différent pour chaque spécialisation utilisée par un prototype. Ainsi, seul un prototype pourra être utilisé pendant que les autres ne trouveront pas le membre attendu. Cette implémentation est tout droit sortie des STLs.

namespace detail
{
  template<class T>
  struct make_unique_select
  {
    using single_object = std::unique_ptr<T>;
  };

  template<class T>
  struct make_unique_select<T[]>
  {
    using array = std::unique_ptr<T[]>;
  };

  template<class T, std::size_t N>
  struct make_unique_select<T[N]>
  {
    struct invalid_type {};
  };
}

template<class T, class... Args>
typename detail::make_unique_select<T>::single_object
make_unique(Args&&... args)
{
  return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
}

template<class T>
typename detail::make_unique_select<T>::array
make_unique(std::size_t num)
{
  return unique_ptr<T>(new std::remove_extent_t<T>[num]());
}

template<class T, class... Args>
typename detail::make_unique_select<T>::invalid_type
make_unique(Args&&...) = delete;

Si le C++ supportait la spécialisation partielle de fonction, on pourrait se passer de detail::make_unique_select. Par contre, comme l’implémentation de make_unique dépend uniquement d’un type template qui doit être explicitement mis, on peut simplifier le code grâce aux variables template et en déplaçant l’implémentation des fonctions dans les spécialisations de structure.

namespace detail
{
  template<class T>
  struct make_unique_impl
  {
    template<class... Args>
    std::unique_ptr<T> operator()(Args&&... args) const
    {
       return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
    }
  };

  template<class T>
  struct make_unique_impl<T[]>
  {
    std::unique_ptr<T[]> operator()(std::size_t num) const
    {
      return std::unique_ptr<T[]>(new std::remove_extent_t<T>[num]());
    }
  };

  template<class T, std::size_t N>
  struct make_unique_impl<T[N]>
  {
    template<class... Args>
    struct invalid_type operator()(Args&&...) const = delete;
  };
}

template<class T>
constexpr detail::make_unique_impl<T> make_unique {};

Ce qui revient à des bêtes spécialisations de template.

Condition dans une spécialisation template

Grâce à un paramètre supplémentaire, il est possible d’ajouter des conditions dans une spécialisation pour y ajouter des contraintes. Voici un exemple simplifié avec une implémentation de std::is_convertible.

template<class From, class To, class = void>
struct is_convertible : std::false_type
{};

template<class From, class To>
struct is_convertible<From, To,
  // on utilise le paramètre "fantôme",
  // mais le type final de l'expression doit être le même que la valeur par défaut
  class = decltype(
    // fonction créée à la volée qui prend un paramètre To
    // qui échouera si From n'est pas convertible
    std::declval<void(&)(To)>()(std::declval<From>())
  )
> : std::true_type
{};

Cette technique permet de n’instancier un type que si tous les prérequis sont acceptés. Au début de l’article, j’ai présenté un exemple de classe où T::type (avec T = C<B>) donne une erreur, car le sous-membre (type) dépend d’un contexte parent. Voici comment on peut palier à ce problème:

template<class T, class = void>
struct C
{
  // par défaut aucun membre
};

// si T::type existe bien, cette spécialisation sera utilisée
template<class T>
struct C<T, std::void_t<typename T::type>>
{
  using type = typename T::type;
};

Ceci fonctionne pour des types, mais les compilateurs sont plus capricieux avec des valeurs. Par exemple, une spécialisation sur des valeurs divisibles par 16 comme ci-dessus donne une erreur avec gcc, msvc et icc. Étrangement, seul clang l’accepte.

template<std::size_t N, bool = false>
struct is_mod16 : std::false_type
{};

template<std::size_t N>
struct is_mod16<N, (N % 16 == 0)> : std::true_type // erreur
{};

Faute de mieux, le plus simple est de passer par std::enable_if_t<N % 16 == 0> et prendre un type comme second paramètre de template.

Jouer avec les conversions implicites

Il est possible d’ajouter un paramètre dans une fonction et jouer avec les conversions implicites pour prioriser l’ordre d’appel.

template<class T, class = typename T::type>
constexpr int foo(int) { return 1; }

template<class T, class = typename T::value_type>
constexpr int foo(char) { return 2; }

struct A
{
  using type = int;
};

struct B
{
  using value_type = int;
};

struct C : A, B
{};

static_assert(foo<A>(42) == 1);
static_assert(foo<B>(42) == 2);
// les 2 fonctions sont valides, mais T::type est prioritaire car 42 est un int
static_assert(foo<C>(42) == 1);

On peut même ajouter autant de paramètres que nécessaire pour avoir une chaîne de priorité. Par exemple, on pourrait faire une fonction front() qui utilise en priorité la fonction front(cont) dans le namespace de l’objet (règles d’ADL), sinon cont.front() et en dernier recours *begin(cont).

#include <iterator>

// juste pour simplifier l'écriture des fonctions
#define DECLTYPE_AUTO_RETURN_NOEXCEPT(...)                 \
  noexcept(noexcept(__VA_ARGS__)) -> decltype(__VA_ARGS__) \
  {                                                        \
    return (__VA_ARGS__);                                  \
  }

namespace adl_barrier
{
  // pour que front_impl() voit une fonction front() qu'elle pourrait utiliser
  struct na {};
  void front(na) = delete;

  // pour que begin(cont) utilise le begin de son namespace (ADL) ou std::begin()
  using std::begin;

  template<class Cont>
  constexpr auto front_impl(Cont& cont, int, int)
  DECLTYPE_AUTO_RETURN_NOEXCEPT(front(cont))

  template<class Cont>
  constexpr auto front_impl(Cont& cont, int, char)
  DECLTYPE_AUTO_RETURN_NOEXCEPT(cont.front())

  template<class Cont>
  constexpr auto front_impl(Cont& cont, char, char)
  DECLTYPE_AUTO_RETURN_NOEXCEPT(*begin(cont))
}

template<class Cont>
constexpr auto front(Cont&& cont)
// le perfect forwarding n'est pas respecté pour simplifier l'exemple
DECLTYPE_AUTO_RETURN_NOEXCEPT(adl_barrier::front_impl(cont, 1, 1))


namespace mylib
{
  struct A
  {
    char const * s;
  };

  constexpr char front(A const& a)
  {
    return a.s[0];
  }


  struct B
  {
    char const * s;
  };

  constexpr char const* begin(B const& b)
  {
    return b.s;
  }


  struct C
  {
    char const * s;

    constexpr char front() const
    {
      return s[0];
    }
  };
}

static_assert(front(mylib::A{"ax"}) == 'a'); // mylib::front(A)
static_assert(front(mylib::B{"bx"}) == 'b'); // *mylib::begin(B)
static_assert(front(mylib::C{"cx"}) == 'c'); // C::front()
constexpr char carr[] = "dx";
static_assert(front(carr) == 'd'); // *std::begin(carr)

Les variadiques de la dernière chance

Il existe en C des paramètres variadiques dont l’usage est limité aux types de base et aux pointeurs. Ce genre de paramètre à une particularité intéressante: il n’est pris en compte qu’à la seule condition qu’aucune autre fonction ne pourrait correspondre. Il a donc une priorité inférieure à la conversion et ne rentre pas en conflit avec. On pourrait réécrire std::is_convertible comme suit

template<class From, class To>
struct is_convertible_impl
{
  std::true_type test(To);
  std::false_type test(...);
};

template<class From, class To>
using is_convertible = decltype(is_convertible_impl<From, To>::test(std::declval<From>()));

Rendre dépendant un type indépendant

Cela peut paraître idiot, mais pour rendre dépendant un type indépendant du contexte, il suffit qu’il traverse un type dépendant.

Voici un exemple pour avoir le plus proche d’un if constexpr () {} else static_assert(false):

constexpr auto fn_identity = [](auto&& x) -> decltype(auto) {
  return static_cast<decltype(x)&&>(x);
};

template<class>
inline auto dependent_identity = fn_identity;

template<class T>
void foo(T const& x)
{
  if constexpr (std::is_array_v<T>)
  {
    // ...
  }
  else
  {
    // _ depend de T, mais est toujours égal à fn_identity
    auto _ = dependent_identity<T>;
    // _(false) retourne false,
    // mais la valeur est indirectement dépendante de T
    static_assert(_(false));
    // on notera que même si _ n'est pas une variable constexpr
    // le résultat de _(false) l'est :)
  }
}

// on peut aussi utiliser la variable x plutôt que T, avec quelque chose comme
template<class T, class U>
constexpr first(T x, U const&)
{
  return x;
}

//...
static_assert(first(false, x));

Cela s’applique aussi au membre d’une classe en ajoutant un template avec un paramètre par défaut qui ne sera jamais modifié par l’extérieur.

template<class T>
struct A
{
  template<class U = T>
  using type = typename U::type;
};

// son écriture en est par contre fortement alourdie:
A<T>::type<>
A<T>::template type<> // dans une fonction/classe template

Ou sur une fonction membre:

template<class T>
struct A
{
  // sans ce template, le type T doit obligatoirement avoir une fonction foo()
  // sinon, l'instanciation de A ne pourra pas se faire et A<int> donnerait
  // request for member ‘foo’ in ‘std::declval<int&>()’, which is of non-class type ‘int’
  template<class U = T>
  decltype(std::declval<U&>().foo()) foo();
};

C++20 et concept

Depuis C++20, il existe un nouvel outil pour exploiter le SFINAE: les concepts. Les concepts sont des contraintes ajoutées aux types qui doivent être vérifiées pour que le compilateur accepte d’utiliser la fonction ou d’instancier le type. Cela simplifie l’utilisation du SFINAE et rend le code beaucoup plus lisible. La fonctionnalité étant récente, la plupart des compilateurs ne la supporte pas encore.

Effets et utilisations de noexcept

Article suivant: SFINAE
Article précédent: std::array, oui, mais pourquoi ?

Fonction noexcept

noexcept est un mot clef apparu en C++11. Dans le prototype d’une fonction, il indique que cette dernière ne jette pas d’exception. Cela ne veut pas dire qu’aucune exception ne sera présente dans la fonction, mais qu’aucune exception ne sortira de la fonction. Dans le cas contraire, le programme s’arrête subitement avec un appel à std::terminate.

noexcept n’impose aucune restriction sur ce que peut faire la fonction. Il est tout à fait possible d’utiliser des fonctions qui ne sont pas marquées noexcept à l’intérieur d’une fonction noexcept, voire, de jeter des exceptions. La seule contrainte se trouve sur le chemin de sortie: il ne doit pas se faire avec une exception.

Voici un code totalement inutile de démonstration avec une exception qui traverse une fonction foo() marquée noexcept:

void foo() noexcept
{
  throw 42; // noexcept ? Pas vu
}

#include <iostream>

int main()
{
  try {
    foo(); // le programme s'arrête ici
  }
  catch (...) {
  }
  std::cout << "ok\n"; // ne s'affiche jamais
}

La compilation puis l’exécution donne:

$ g++ test.cpp && ./a.out
test.cpp: In function void foo():
test.cpp:3:9: warning: throw will always call terminate() [-Wterminate]
    3 |   throw 42;
      |         ^~
terminate called after throwing an instance of 'int'
zsh: abort (core dumped)  ./a.out

G++, Clang et MSVC émettent tous 3 un avertissement et le programme explose comme attendu.

L’avertissement ici est évident, mais ce n’est pas toujours le cas, le compilateur ne pouvant garantir que toutes les fonctions utilisées dans une fonction noexcept ne jettent pas elles-mêmes des exceptions.

Notre fonction foo() est une énorme bombe à retardement. Chouette, une raison supplémentaire pour faire planter un programme ;)

Les bénéfices de noexcept

Une mauvaise utilisation de noexcept peut faire planter un programme. Mais une fonctionnalité à risque ne vient jamais sans avantage. Puisque noexcept garantit qu’aucune exception ne sorte de la fonction, le compilateur peut éjecter le code qui s’en occupe. Si les fonctions ne lancent pas d’exception, il peut déterminer avec certitude quels sont les chemins de sortie, supprimer du code, réordonner les instructions et appliquer autres obscures magies dont il a le secret.

Dit comme ça, on pourrait croire que plein d’optimisations s’offrent à nous, mais non. Premièrement, les compilateurs sont capables de faire des exceptions qui n’ont de coût qu’au moment de l’appel. Bien sûr, l’exécutable est plus gros et peut impacter le cache d’instruction, mais le coût d’une exception non utilisée est nulle. Secundo, ce n’est pas évident de produire un exécutable qui supprime vraiment du code, à moins d’avoir absolument toutes les fonctions en noexcept, la magie du compilateur se verra limité. Surtout que les bonnes options d’optimisation donnent des résultats comparables.

Après plusieurs essais d’exemples de code pseudo-réaliste, en voici 2 basés sur une fonction très simple

// foo.cpp
int foo(int x) NOEXCEPT
{
  return x;
}

NOEXCEPT sera à remplacer par noexcept ou rien. Respectivement les options de compilation -DNOEXCEPT=noexcept et -DNOEXCEPT=.

Ce premier exemple prouve que le compilateur est capable de prendre en compte noexcept pour supprimer du code.

// main.cpp
#include <iostream>

int foo(int) NOEXCEPT;

void bar(std::ostream& out)
{
  char const* err;
  try {
    // trace de l'étape en cours
    err = "foo step";
    auto r = foo(1);
    // fin du "traitement"
    err = nullptr;

    out << r; // ceci peut lancer une exception std::ios_base::failure
  }
  catch(std::exception const& e)
  {
    // err != nullptr uniquement si foo() lance une exception
    if (err)
      std::cerr << "oups: " << err << "\n";
    std::cerr << e.what() << "\n";
  }
}

Ce code permet d’afficher un message sur l’étape en cours avant une éventuelle exception. Dans notre cas, foo() ne lance pas d’exception, mais en l’absence de noexcept, main.cpp ne le sait pas.

Si foo() ne lance pas d’exception, alors err sera toujours égal à nullptr dans le catch. Il est alors possible de supprimer la condition qui serait toujours évaluée à false, ce qui doit donner un exécutable plus petit.

Le petit script suivant va compiler chaque .cpp avec et sans noexcept puis afficher la taille de l’exécutable.

for x in noexcept '' ; do
  d=NOEXCEPT=$x
  g++ -O3 -D$d *.cpp &&
  echo $d &&
  stat ./a.out *.o --format="$(echo "%n\t%s")"
done
  NOEXCEPT= NOEXCEPT=noexcept
stat ./a.out 17632 16816

Pronostic vérifié. On peut même regarder l’assembleur sur godbolt pour s’en convaincre.

Voici un second exemple plus simple qui montre que le compilateur supprime totalement la gestion des exceptions lorsqu’il lui est permis de le faire.

#include <memory>

int foo(int) NOEXCEPT;

int bar(std::unique_ptr<int>&& p)
{
    // some stuff
    // ...
    auto u = std::move(p);
    return foo(*u);
}

Et l’asm de https://godbolt.org/z/-yIB7m

bar(std::unique_ptr<int, std::default_delete<int> >&&):
        push    r12
        push    rbp
        sub     rsp, 8
        mov     rbp, QWORD PTR [rdi]
        mov     QWORD PTR [rdi], 0
        mov     edi, DWORD PTR [rbp+0]
        call    foo(int)
        mov     rdi, rbp
        mov     esi, 4
        mov     r12d, eax
        call    operator delete(void*, unsigned long)
        add     rsp, 8
        mov     eax, r12d
        pop     rbp
        pop     r12
        ret
; ce qui suit ne concerne que l'éventuelle exception de foo()
        mov     r12, rax
        jmp     .L2
bar(std::unique_ptr<int, std::default_delete<int> >&&) [clone .cold]:
.L2:
        mov     rdi, rbp
        mov     esi, 4
        call    operator delete(void*, unsigned long)
        mov     rdi, r12
        call    _Unwind_Resume

La seconde partie du code asm n’est utilisée que pour le traitement d’une exception, elle se situe en dehors du flux normal d’exécution et disparait lorsque foo() ne lance pas d’exception.

Mais attention, si une fonction noexcept appelle une fonction qui n’est pas noexcept, le compilo va ajouter du code pour forcer l’utilisation de std::terminate(). Cela revient presque à un support d’exception, mais en plus léger.

Maintenant, il faut savoir qu’avec l’option -flto la taille des exécutables sont les mêmes que foo() soit noexcept ou pas. Simplement parce que le compilateur déduit que foo() ne lance pas d’exception. Mais dans le cas de bibliothèque partagée, -flto ne pourra rien faire et la différence subsistera.

Puisque le compilateur peut déduire lui-même qu’une fonction ne lance pas d’exception, pourquoi et surtout quand mettre noexcept ?

Quand mettre noexcept

Déjà, on peut dire qu’une fonction qui ne lance absolument pas d’exception peut être noexcept. Cette information est surtout utile dans les APIs ou bibliothèques qui ont cette garantie. Un analyseur statique pourrait aussi vérifier qu’aucune exception ne la traverse. Dans le cas contraire, c’est plutôt risqué.

Néanmoins, noexcept est vraiment important sur les constructeurs déplacement.

Pour être plus précis, conjointement avec les conteneurs de la STL, cela va déterminer si le conteneur utilise ou non le déplacement. Si la fonction est noexcept, le déplacement d’un élément ne peut pas échouer. Dans le cas d’un std::vector<T>, cela veut dire qu’après un agrandissement de la capacité, tous les éléments peuvent être déplacés sans échec. Par contre, si le déplacement lance une exception, une partie des données pourrait se perdre et std::vector utilise alors la copie. On parle de résistance aux exceptions ou d’exception-safety. Dans le cas de std::vector, c’est une garantie forte: l’état du vector est inchangé s’il y a une exception sur l’augmentation de la capacité. Pour en savoir un peu plus sur l’exception-safety, c’est par là.

Pour illustrer l’influence de noexcept avec std::vector, voici une petite classe qui affiche quel constructeur est utilisé. Le constructeur de déplacement est toujours présent, seule la présence de noexcept diffère.

#include <iostream>

struct A
{
  A(int i) : i(i) {}

  A(A const& a) : i(a.i)
  { std::cout << "A&(" << i << ")\n"; }

  A(A&& a) NOEXCEPT : i(a.i)
  { std::cout << "A&&(" << i << ")\n"; }

  int i;
};

#include <vector>

int main()
{
  std::vector<A> v;
  v.emplace_back(1);
  v.emplace_back(2); // agrandissement de la capacité + déplacement/copie de A(1)
}

Et les résultats après compilation:

  NOEXCEPT= NOEXCEPT=noexcept
./a.out A&(1) A&&(1)

Maintenant imaginons que notre classe A contienne des std::string et des std::vector. Si le constructeur de déplacement n’est pas noexcept, alors il y aura de nombreuses copies qui auront un gros impact sur les performances. Ce n’est généralement pas ce qu’on veut.

Personnellement, je déconseille d’écrire le constructeur et operator= de déplacement ou de copie. 99% du temps, la version par défaut fait le job, le compilateur déduisant lui-même noexcept pour les fonctions par défaut – et c’est bien le seul moment. S’il y a une véritable nécessité, il est généralement possible d’avoir une classe qui ne fournit que ce service et l’utiliser en variable membre.

Si on écrit explicitement noexcept sur une fonction par défaut – par exemple X(X&&) noexcept = default; – le compilateur va vérifier que le déplacement de chaque membre ne lance pas d’exception. Et dans le cas contraire, ne compile pas.

Pour finir, les destructeurs sont implicitement noexcept. Si un destructeur balance une exception, le programme va s’arrêter. Les raisons sont assez simples: il est difficile de catcher une exception d’un destructeur et il est impossible d’arriver à un état cohérent sans code spécifique si les objets ne peuvent être détruits. De plus, il faut savoir que jeter une exception pendant le traitement d’une exception appelle automatiquement std::terminate(). Du coup, les exceptions dans un destructeur sont plutôt une mauvaise idée.

Mais si on veut autoriser le destructeur à jeter des exceptions ou pouvoir marquer nos fonctions en noexcept à la seule condition qu’une expression précise soit elle-même noexcept il existe un nouveau mot clef: noexcept. Oui, mais non, il est différent.

Spécificateur d’exception et opérateur noexcept

Il existe 2 mots clef pour noexcept: le spécificateur d’exception et l’opérateur.

  • Le spécificateur noexcept ou noexcept(bool) se met toujours dans le prototype de la fonction. noexcept et noexcept(true) indiquent que la fonction ne jette pas d’exception, noexcept(false) indique que la fonction jette potentiellement une exception.
  • L’opérateur noexcept(expr) prend une expression est retourne un booléen qui indique si oui ou non une expression peut lancer une exception.

Voici quelques exemples:

constexpr bool foo() { return true; }

void f1() noexcept;
void f2() noexcept(false);
void f3() noexcept(foo()); // -> noexcept(true)
void f4() noexcept(noexcept(f1())); // noexcept seulement si f1() est noexcept
void f5() noexcept(noexcept(new int));
void f6() noexcept(noexcept(false));

std::cout << noexcept(f1())  << "\n"; // true
std::cout << noexcept(f2())  << "\n"; // false
std::cout << noexcept(f3())  << "\n"; // true
std::cout << noexcept(f4())  << "\n"; // true
std::cout << noexcept(f5())  << "\n"; // false
std::cout << noexcept(f6())  << "\n"; // true
std::cout << noexcept(true)  << "\n"; // true
std::cout << noexcept(false) << "\n"; // true

Pas très compliqué dans l’ensemble, même si bien que logique, le résultat de f6() et la dernière ligne peuvent surprendre: false est une expression qui ne retourne jamais d’exception, par conséquent, l’opérateur noexcept retourne true.

La STL offre aussi les traits std::is_nothrow_* pour vérifier si certaines expressions sont noexcept ; ainsi qu’une fonction std::move_if_noexcept qui retourne une rvalue si le constructeur de déplacement est noexcept et une lvalue constante dans le cas inverse.

Avant C++11, il existait le spécificateur throw() pour indiquer qu’une fonction ne jette pas d’exception. Son comportement est très différent et pas du tout efficace. En C++17, il devient l’équivalent de noexcept(true) pour finalement être supprimé en C++20.

Signature et type de fonction

2 fonctions qui ne diffèrent que par la spécification d’exception ne peuvent être surchargées car leur signature est identique. Ceci n’est pas autorisé:

void foo();
void foo() noexcept; // erreur

Du fait de la signature identique, noexcept peut très bien apparaître dans le prototype d’une fonction exposée dans une bibliothèque C (extern "C"), mais cette information disparaît dans la bibliothèque elle-même. Mieux que ça, si la bibliothèque est compilée sans noexcept, mais que le .h distribué les met, le compilateur retrouve ses petits, car le name mangling est le même.

Par contre, avant C++17 le type d’une fonction ne prend jamais en compte noexcept. C’est-à-dire que les types void(*)() et void(*)() noexcept sont identiques.

À partir de C++17, noexcept fait partie intégrante du type de la fonction. Un pointeur de fonction noexcept n’est pas compatible avec un pointeur de fonction qui jette potentiellement une exception. Néanmoins, une fonction noexcept est convertible en un pointeur de fonction qui n’est pas noexcept. Les posts conditions sont plus fortes ce qui ne brise pas le LSP.

void foo() noexcept;
void bar();

void(*f)() noexcept = foo;
void(*f)() noexcept = bar; // non depuis C++17

void(*g)() = bar;
void(*g)() = foo; // ok

Cette caractéristique s’applique aussi aux fonctions virtual.

class A
{
  virtual void foo() noexcept = 0;
  virtual void bar() = 0;
};

class B : A
{
  void foo() override; // il manque noexcept
  void bar() noexcept override; // ok, plus de restriction sur les conditions de sortie
};

class C : B
{
  void bar() override; // erreur, même si A::bar() n'est pas noexcept, B::bar() l'est
};

Ce qu’il faut retenir

Finalement il n’y a pas grand chose à retenir. noexcept permet certaines optimisations, mais appliqué n’importe comment il est source de bug. Si vous n’êtes pas sûr, ne l’utilisez pas.

Cependant, comme cela influence les conteneurs de la STL, il faut impérativement penser à le mettre sur le constructeur de déplacement.

std::array, oui, mais pourquoi ?

Article suivant: Effets et utilisations de noexcept
Article précédent: Grep, sed, awk, sort... Non ! Zsh

Depuis C++11, un nouveau type de tableau fait son apparition: std::array. S’il est là, ce n’est pas uniquement parce que la STL est cool, mais bien parce que les tableaux C posent des problèmes dans lesquels les débutants sautent à pieds joints.

Les tableaux C se convertissent en pointeur trop facilement

Le tableau C a l’alarmante faculté de se convertir en pointeur par simple affectation ou opération arithmétique. Par exemple, Soustraire 2 tableaux donne la distance qui sépare les 2 variables dans la mémoire, ce qui n’a aucun sens. Mais puisque les tableaux se dégradent en pointeur, le compilateur l’accepte sans broncher.

Le seul pseudo-avantage est l’arithmétique des pointeurs qui permet de manipuler un tableau presque comme un pointeur – à la différence que l’incrémentation et la décrémentation ne sont pas possibles.

Ainsi, on pourra écrire auto* p = a + i plutôt que auto* p = &a[i].

Ou encore &i[a] (i.e. &2[a]), forme uniquement valide avec des tableaux ou des pointeurs. Tant qu’à hériter du C, prenons le meilleur… :D

Votre prototype de fonction ment

Voici une fonction tout à fait banale qui affiche les valeurs d’un tableau:

void print(int const array[3])
{
  for (int i : array)
  {
    std::cout << i << "\n";
  }
}

Fonction qui ne compile pas, car array n’est pas un tableau, mais un pointeur. Et un pointeur ne fonctionne pas avec les boucles sur intervalle. Gcc indique l’erreur en affichant le prototype tel qu’il devrait être lu: “dans la fonction void print(const int*)”. Clang va même jusqu’à dire qu’un paramètre de type int[3] est considéré comme un pointeur. La conversion en pointeur se propage même à ce niveau.

Ce qui veut dire qu’écrire un prototype qui prend un tableau de 3 int est un mensonge. Le compilateur ne fera aucune vérification sur la taille du tableau passé en paramètre. Pour lui, que l’argument soit un tableau de 1, 2, 3 ou plus d’éléments, c’est pareil: un pointeur. Par conséquent, les 4 prototypes suivants sont strictement identiques:

void print(int const array[4]);
void print(int const array[3]);
void print(int const array[]);
void print(int const* array);

Bien sûr, il est possible d’avoir un vrai tableau en paramètre avec l’aide des références et d’une syntaxe alambiquée:

void print(int const (&array)[3]); // bienvenue dans le monde merveilleux de C++

À ce moment, le compilateur considère array comme étant un tableau de 3 entiers constants et la boucle précédente pourra fonctionner. Si l’utilisateur met un tableau de moins ou de plus de 3 éléments, le compilateur va gentiment l’envoyer bouler.

Un tableau C se convertit en entier… Dans certains circonstances

Il est possible de convertir un tableau C en entier sans faire exprès, de la même manière qu’un pointeur se convertit en entier.

using T = unsigned long long;

void foo(T);

int a[10];

foo(T(a1)); // ok, on passe l'adresse de `a`. À ne pas confondre avec la valeur du premier élément

J’ai déjà eu ce genre d’erreur dans un code proche de write(a, std::size_t(a)) à la place de write(a, std::size(a)).

Les tailles des tableaux multidimensionnels sont à l’envers

Lorsqu’on déclare un tableau multidimensionnel, l’ordre des dimensions est à lire à l’envers. Ce qui n’est pas le cas en utilisant des alias.

int a[2][3]; // tableau de 2 tableaux de 3 int

using A = int[2]; // tableau de 2 int
A a[3]; // tableau de 3 tableaux de 2 int

Un tableau C n’est pas copiable

Le tableau est le seul type du C qui ne supporte ni la copie, ni l’affectation, ce qui le rend inutilisable en retour de fonction ou dans n’importe quel conteneur de la STL tel que std::vector. Il n’est pas non plus possible de construire un tableau directement dans l’appel d’une fonction sauf en C99 ou C++ avec un cast ou à travers un alias.

// cast
foo((int[]){1,2});

// alias
template<class T>
using carray = T[];

foo(carray<int>{1,2});

Par contre, une structure qui contient un tableau est aussi bien copiable qu’affectable. Manipuler un tableau directement impose plusieurs contraintes complètement loufoques, mais mettez le tout dans une boîte et tout est permis. Ce qui m’amène à std::array, car il fait justement office de boîte.

Std::array, un conteneur comme les autres

Le gros avantage de std::array est son interface commune avec les autres conteneurs:

  • size()
  • empty()
  • begin()/end()
  • data()

Ainsi que quelques membres utilitaires comme fill(), front(), back() et la panoplie de type comme value_type, reference, etc qu’on s’attend à voir.

Si je prends le cas de size(), la version tableau C est beaucoup plus compliquée: sizeof(array)/sizeof(array[0]), Mais aussi dangereuse, car le comportement sera totalement imprévisible si, suite à un refactoring, notre tableau est remplacé par std::vector.

La manière intelligente de faire consiste en une fonction libre size(T(&)[N]) qui s’occupe de cela pour nous. Si le type change, alors la fonction ne correspond plus et des erreurs apparaissent. Au passage, C++17 introduit std::size(cont), std::empty(cont) et std::data(cont) valides pour tous les conteneurs, y compris les tableaux. Voici un article de Lmghs sur le sujet et les raisons de ce choix.

Un tableau de 0 élément

Dans certaines circonstances, on peut vouloir un tableau de 0 élément. Cela fonctionne très bien avec std::array contrairement au tableau C qui doit utiliser une extension du compilateur pour le supporter (c’est interdit par le standard). Pour pallier à ce problème avec les tableau C, sa taille est généralement forcée à 1, mais d’autres complications surviennent dès que les types ne sont pas trivialement constructibles.

Std::array est un tuple

Propriété anecdotique, les fonctions et classes associées au tuple sont disponibles pour std::array. Cela permet par exemple de jouer avec std::apply pour transformer un std::array en un pack variadique.

std::array<int, 3> a{1,2,3};
int sum = std::apply([](auto... xs){ return xs + ...; }, a);

Dans la pratique, il n’y a pas d’inconvénient à le faire sur un tableau C ici, mais le standard ne le prévoit pas.

Déduction de taille VS taille explicite

Un gros avantage du tableau C se situe sur la déclaration de la taille au moment de l’initialisation: le compilateur peut la déduire. Alors qu’avec std::array il faut la mettre en paramètre template au risque d’y mettre une valeur trop grande (une valeur trop petite donne une erreur).

Sauf que depuis C++17, les guides de déduction rendent optionnels les paramètres template. Ce n’est pas un strict équivalent puisque le type est aussi déduit, mais c’est généralement ce qu’on veut car tous les éléments doivent être du même type1. Dans le pire des cas, on peut se tourner vers quelque chose comme std::make_array<T>(xs...) (en TS) qui permet de spécifier le type du tableau sans indiquer explicitement la taille.

int a1[3]{1,2,3}
int a2[]{1,2,3} // taille implicite

std::array<int, 3> a3{1,2,3};
std::array a4{1,2,3}; // taille et type implicites
std::array a5 = std::make_array<int>(1,2,3); // taille implicite

  1. On notera que auto a[] {1,2,3} n’est pas autorisé. ↩︎

Grep, sed, awk, sort... Non ! Zsh

Article suivant: std::array, oui, mais pourquoi ?
Article précédent: Presque toujours std::move

Depuis plusieurs années maintenant, j’utilise Zsh comme shell par défaut. Et par la force des choses, il m’arrive de taper des commandes zsh, de faire des boucles zsh, de penser zsh. Bref, de coder en zsh. Bien que le langage a des inconvénients, il possède de nombreuses fonctionnalités qui recouvrent celles de certains utilitaires Unix.

Les gros avantage d’utiliser zsh plutôt que les commandes Unix sont au nombre de 3:

  • Pas de post traitement pour mettre le résultat d’une commande dans une variable.
  • Beaucoup plus rapide que lancer une commande. La création de process prend du temps et se ressent dans une boucle.
  • Écrire en 3 lettres ce qu’on peut faire en 32. C’est-à-dire frimer ;).

Il y a aussi des inconvénients:

  • Moins lisible, surtout lorsque l’on remplace une suite de pipe comme aaa | bbb | ccc. Mais on peut simplifier avec des variables intermédiaires.
  • Peut être plus lent lorsqu’il y a beaucoup de texte à manipuler. En gros, faire un grep d’un fichier de 1000 lignes est plus lent qu’avec zsh, mais plus rapide si le fichier fait 100000 lignes, car zsh ne travaille pas par flux.

Syntaxe de base

Le man de zsh fait plus de 5 fois celui de bash. Le manuel est tellement gros qu’il est divisé en 16 parties + un man zshall pour les afficher tous. Difficile de tout mettre en 1 article alors je me contente de certaines parties de zshexpn (zsh expansion and substitution). Parmi celles utilisées ici il y a les options d’expansion de paramètres (${(@)x}) et les modificateurs (${x:h} ou $x:h). Il existe un pdf compilant les options et syntaxe de zsh: http://www.bash2zsh.com/zsh_refcard/refcard.pdf.

Lire un fichier

Voici comment les scripts zsh peuvent lire un fichier et mettre chaque ligne dans un tableau grâce aux extensions de paramètres:

content=$(<file) # lire un fichier
content=$(<file1 <file2) # lire 2 fichiers (si multios est activé)
content=$(<file ; ls) # lire un fichier et le retour de la commande `ls`

lines=( ${(f)content} ) # tableau sans ligne vide
lines=( ${(s:\n:)content} ) # équivalent
lines=( "${(@f)content}" ) # tableau avec toutes les lignes (il faut les quotes et @)

lines=( ${(f)$(<file)} ) # forme condensée du premier cas

# -E permet de désactiver l'interpréation des séquences d'échappement (ex. \e)
echo -E ${(j:\n:)lines} # concatène les lignes avec \n
# ou
echo -E ${(F)lines}

# affiche chaque ligne d'un fichier dans des crochets
echo -E "[${(j:]\n[:)"${(@f)$(<file)}"}]"

Il y a encore de nombreux paramètres qui peuvent être trouvés dans le manuel ou via l’auto-complétion de zsh. Aussi, pour simplifier les exemples qui suivront, j’utiliserai directement les variables content et lines.

Petite note concernant echo: comme cette commande prend des arguments, le contenu affiché peut influencer le résultat. Pour éviter tout problème, il vaut mieux partir sur une redirection de flux de cette forme >&1 <<<$content. Équivalent à cat <<<$content mais sans appel de commande.

Glob et glob étendu

L’une des grandes forces de zsh réside dans le globbing. Il ne se restreint pas qu’à la recherche de fichier, mais peut aussi s’appliquer sur les éléments d’un tableau ou des chaînes pour filtrer ou transformer. En plus de * et ?, zsh comprend [...], [^...] et <x-y> pour un nombre entre x et y inclu (<-> pour n’importe quel nombre).

Avec le glob étendu (setopt extendedglob) on possède alors un équivalent des regex:

  • x# 0 ou plus de x
  • x## 1 ou plus de x
  • x~y exclut y de x
  • ^x tous sauf x
  • (#s) début (équivalent de ^ des regex)
  • (#e) fin (équivalent de $ des regex)

Ainsi que la syntaxe ksh si activée

ksh-like glob operators
@(...) (...)
*(...) (...)#
+(...) (...)##
?(...) (|...)
!(...) (^(...))

Équivalent des commandes *Unix

Maintenant que la petite introduction syntaxique est faite, on peut s’attaquer au remplacement des commandes systèmes. Bien sûr, toutes les options d’une commande ne peuvent pas être simulées facilement avec zsh, mais je présente ici l’essentiel. Je précise que les commandes bash ont implicitement <<<$content comme flux de lecture et que le résultat des commandes zsh est fait avec un echo -E.

Je conseille aussi le petit Zsh Native Scripting Guide.

grep

bash zsh
grep 'Alligator' ${(M)lines:#*Alligator*}
grep -v 'Alligator' ${lines:#*Alligator*}
grep '^Alligator .* Alligator$' ${(M)lines:#Alligator * Alligator}
grep -i 'alligator' ${(M)lines:#(#i)*alligator*}
grep -m1 'alligator' ${lines[(r)*alligator*]}

(#i) pour insentive n’est utilisable qu’avec setopt extendedglob et peut s’appliquer sur un groupe seulement de caractère (i.e. ((#i)a)lbator). Il existe l’option inverse: #I. Ainsi que #l qui fait une recherche insensible à la case pour les lettres minuscules du pattern, et en majuscule pour celles en majuscule dans le pattern.

agrep

agrep pour “approximate grep”. C’est un grep qui autorise une marge d’erreur dans la recherche. Zsh possède une option de glob qui fait à peu près la même chose: (#a3) pour une recherche avec 3 erreurs.

bash zsh
agrep -3 'alligator' ${(M)lines:#*((#a3)alligator)*}

sed

bash zsh
sed '3,6!d' ou sed -n '3,6p' $lines[3,6]
sed s/alligator/crocodile/ ${content/alligator/crocodile}
sed s/alligator/crocodile/g ${content//alligator/crocodile}
sed 's/^alligator\*$/_/' ${lines:s%alligator*%_} ou ${lines/(#s)alligator\*(#e)/_}
sed 's/^\w\+$/[&]/' ${lines:/(#m)[[:alnum:]]##/[$MATCH]}
sed -E 's/^(\w+) = (\w+)$/\2 = \1/' ${lines:/(#b)([[:alnum:]]##) = ([[:alnum:]]##)/$match[2] = $match[1]}
bash zsh
head -n3 ${(F)lines[1,3]}

tail

bash zsh
tail -n3 ${(F)lines[-3,-1]}

Malheuresement, un nombre négatif en dehors du tableau va afficher un contenu vide. Si on veut un strict équivalent, il faut faire un petit calcul mathématique:

n=10

result=$lines[$((n > $#lines ? 1 : -n)),-1]

awk

Pour celui-là, l’entrée sera le texte ci-dessous. Le programme va coloriser le préfixe.

info: un alligator dort sur le balcon
avertissement: l'alligator se réveille
erreur: l'alligator attaque
note: penser à investir dans une porte plus solide
awk zsh
BEGIN { colors["erreur:"]="31" colors["avertissement:"]="33" colors["info:"]="35" for (k in colors) colorized[k]="\033[" colors[k] "m" k "\033[0m" } { s=colorized[$1] if (s) print s substr($0, length($1)+1) else print $0 } setopt extendedglob declare -A colors=( erreur: 31 avertissement: 33 info: 35 ) declare -A colorized esc=$'\e' for k in ${(k)colors} ; colorized+=($k "${esc}[$colors[$k]m$k${esc}[0m") echo -E ${(F)lines/(#m)(#s)[a-z]##:/${colorized[$MATCH]:-$MATCH}}

find

bash zsh
find -name '*alligator*' **/*alligator*
find -name '*alligator*' -a -not '*crocodile*' **/*alligator*~*crocodile*
find -type d **/*(/)
find -not -type d **/*(^/)
find -type l **/*(@)
find -atime 3 **/*(a3)

Bon, vous l’aurez compris, zsh permet de nombreux filtres dans la recherche de fichier. Il peut trier la recherche par date, nom, groupe, etc ou même via une fonction personnalisée.

sort

bash zsh
sort ${(o)lines}
sort -n ${(on)lines}
sort -rn ${(On)lines}
sort -u ${(uo)lines}

À noter que ${(u)lines} élimine les doublons sans trier le tableau.

Manipulation de chemin

bash zsh
dirname "$0" $0:h
basename "$0" $0:t
realpath "$0" $0:P

Il y en a évidemment d’autres.

cut

bash zsh
cut -d: -f2,1 echo -E ${(F)lines/(#m)*/$(() { >&1 <<< $2:$1 } ${(s-:-)MATCH})}

Mais une boucle serait mieux ici. De plus cette ligne ne prend pas en compte l’absence de : qu’il faudrait gérer pour être un strict équivalent à la commande cut.

printf

bash zsh
printf '%04d' 42 echo -E ${(l:4::0:)${:-42}} ou echo -E ${(l:4::0:)n}

À noter que contrairement à printf, le 4 correspond au nombre de caractère qui sera affiché. Ce qui signifie qu’un nombre sur 5 chiffres sera tronqué.

Presque toujours std::move

Article suivant: Grep, sed, awk, sort... Non ! Zsh
Article précédent: Méta-fonction et continuation

Le principe de std::move est de “déplacer1” un objet qui n’est plus utilisé dans l’objectif de décharger la responsabilité dans une autre variable ou d’utiliser le constructeur de déplacement à la place de celui de copie.

Pour avoir de meilleures performances, il est tentant de le mettre partout lorsque la variable n’est plus utilisée. Un constructeur de déplacement sera toujours préférable au constructeur de copie, pourquoi s’en priver ?

Rire sarcastique.

Parce qu’il est possible de “déplacer” les valeurs sans passer le constructeur !

Du “déplacement” sans std::move

C’est fort du roquefort ! Pas de constructeur, pas de std::move, mais un objet qui se déplace quand même. On croirait faire de la magie !

std::move va forcer l’appel à un constructeur de déplacement alors que le compilateur a les moyens – et même l’obligation – de le faire pour nous. Ou mieux, bypasser tous les constructeurs et mettre la valeur directement là où il faut. On parle d’élision par copie ou de (N)RVO (Named Return Value Optimization). Sauf que std::move bloque ces optimisations.

Dans le cas de l’élision de copie, le compilateur construit directement les paramètres de type T (un type sans référence) lorsqu’on utilise un temporaire.

Avec void foo(T), il faut faire foo(T{...}) et non pas foo(std::move(T({...}). Comme on ne fait pas T x = std::move(T{...}), mais T x = T{...} (on peut faire T x{}, c’est pour l’exemple)

Les temporaires peuvent aussi exister depuis l’appel à une fonction qui retourne T.

Avec T bar(), il faut faire foo(bar()), et non pas foo(std::move(bar())).

La (N)RVO est une optimisation qui fonctionne sur le même principe au niveau de la valeur de retour.

On n’écrit pas T bar() { return std::move(T{...}); }, mais T bar() { return T{...}; }.

Le compilateur possède aussi un comportement spécial pour la variable locale retournée: celle-ci doit être déplacée si possible. Et si possible, on optimise avec une élision.

On écrit

T bar() {
  T x;
  // ...
  return x;
}

À la place de

T bar() {
  T x;
  // ...
  return std::move(x);
}

Au final, les seuls moments où std::move devrait être utilisé, sont

  • Pour transférer une variable de type référence (lvalue ou rvalue) en la forçant en rvalue.
  • Pour passer une variable de type plein (sans référence) à une autre fonction.

  1. std::move n’est qu’un static_cast<T&&> ↩︎

Méta-fonction et continuation

Article suivant: Presque toujours std::move
Article précédent: Simuler une vtable sans fonction virtuelle

J’ai pas mal bossé avec des bibliothèques de méta-programmation, et une que j’apprécie particulièrement est Kvasir.Mpl. Son originalité réside dans le support des continuations et –parce que cela va bien de paire,– l’évaluation paresseuse ainsi que des algorithmes pensés pour manipuler des packs (template variadique) plutôt que des listes de type (list<Ts...>).

Continuation

Chaque algorithme dispose d’un paramètre qui décrit l’étape suivante du traitement, c’est la continuation. En shell ou dans des bibliothèques comme rangev3, les continuations se font avec l’opérateur |. Par exemple grep x | wc -l ou filter(is_odd) | take(6). Il n’est pas possible d’utiliser | avec des templates, alors la continuation est un paramètre ajouté à l’algorithme. En chaînant les continuations, on construit un nouvel algorithme qui s’utilise avec call<algo, args...>.

// `C` pour continuation

template<class C>
struct add_const;

template<class C>
struct add_lvalue_reference;

template<class C>
using add_const_lvalue_reference = add_const<add_lvalue_reference<C>>; // un chaînage

Les continuations limitent drastiquement le recours aux “lambdas”. Dans d’autres bibliothèques du genre, add_const_lvalue_reference s’écrirait lambda<add_lvalue_reference, lambda<add_const, _>> ce qui est, il faut l’avouer, beaucoup moins glamour.

Dans des algorithmes du type transformation, l’impact sur la lecture du code est immédiat:

transform<lambda<next, lambda<times, _1, _2>>, L1, L2>
// vs
call<transform<times<next<>/*, C=listify*/>, L1, L2>

Qui se traduit par la construction d’une nouvelle liste avec la formule (x*y)+1.

Ce code met bien en évidence un autre aspect des continuations: la lecture du code se fait de gauche à droite alors que les lambdas se lisent de droite à gauche et oblige le lecteur à faire des allers/retours pour suivre le flux de code.

transform<lambda<next, lambda<times, _1, _2>>, L1, L2>
 /* 1 */       /* 3 */       /* 2 */
call<transform<times<next<>/*, C=listify*/>, L1, L2>
      /* 1 *//* 2 *//* 3 */      /* 4 */

Méta-fonction

Au niveau de kvasir, une méta-fonction est un type qui possède un membre template nommé f. Tous les algorithmes de kvasir sont des méta-fonctions et l’appel se fait avec call<metafunc, param1, param2,...>. Si on complète add_const et add_lvalue_reference plus haut, cela donne:

// Cette implémentation de call est volontairement simplifiée
// et ne fonctionne pas pour tous F
template<class F, class... Ts>
using call = typename F::template f<Ts...>;

template<class C>
struct add_const
{
  template<class T>
  using f = call<C, T const>;
};

template<class C>
struct add_lvalue_reference
{
  template<class T>
  using f = call<C, T&>;
};

Il ne reste qu’une dernière étape, la continuation finale lorsqu’il n’y a plus rien à faire. Les plus utilisés sont au nombre de 2 et servent de valeur par défaut à l’ensemble des algorithmes, j’ai nommé identity et listify.

struct identity
{
  template<class T>
  using f = T;
};

template<class...>
class list {};

struct listify
{
  template<class... Ts>
  using f = list<Ts...>;
};

C’est beau, c’est propre

Il y a quelques jours, après mon petit passage quotidien dans libstdc++ et en regardant std::decay, je me suis dit c’est beau, c’est propre qu’il faudrait comparer avec une implémentation qui utilise les concepts de kvasir.

Voici en l’état la version fournie avec gcc-8.2:

// Decay trait for arrays and functions, used for perfect forwarding
// in make_pair, make_tuple, etc.
template<typename _Up,
     bool _IsArray = is_array<_Up>::value,
     bool _IsFunction = is_function<_Up>::value>
  struct __decay_selector;

// NB: DR 705.
template<typename _Up>
  struct __decay_selector<_Up, false, false>
  { typedef typename remove_cv<_Up>::type __type; };

template<typename _Up>
  struct __decay_selector<_Up, true, false>
  { typedef typename remove_extent<_Up>::type* __type; };

template<typename _Up>
  struct __decay_selector<_Up, false, true>
  { typedef typename add_pointer<_Up>::type __type; };

/// decay
template<typename _Tp>
  class decay
  {
    typedef typename remove_reference<_Tp>::type __remove_type;

  public:
    typedef typename __decay_selector<__remove_type>::__type type;
  };

En réalité, ce qui m’a particulièrement tiqué se situe dans la déclaration de __decay_selector: is_array et is_function sont toujours évaluées avec _Up et il faut écrire plusieurs spécialisations.

L’idée du sélecteur est un bon concept et se remplace facilement par une suite de conditions:

// ce que fait plus ou moins libc++ de llvm
template<class T>
using __decay_selector = conditional<
  is_array_v<T>,
  remove_extent_t<T>*,
  conditional_t<
    is_function_v<T>,
    add_pointer_t<T>,
    remove_cv_t<T>
  >
>;

Qui engendre son lot de problèmes: en plus des 2 traits précédents, remove_extent, add_pointer et remove_cv sont toujours déclarés avec T. Cela ne pose pas de réel problème ici – à part le temps de compilation–, malheureusement, dans certaines situations, les branches ne doivent s’évaluer qu’en fonction du prédicat et les traits de la STL ne le permettent pas sans ajouter des intermédiaires.

Mais les continuations changent tout puisque les méta-fonctions ne sont évaluées que pour la branche qui respecte le prédicat. Ainsi, remove_extent<T> ne sera pas instancié lorsque is_array_v<T> est faux, ce qui rend les continuations très facilement composables.

template<class T>
struct decay
{
  using type = call<
    if_<
      cfl<std::is_array>,
      cfe<std::remove_extent, cfe<detail::add_pointer_impl>>,
      if_<
        cfl<std::is_function>,
        cfe<std::add_pointer>,
        cfe<std::remove_cv>
      >
    >,
    std::remove_reference_t<T>
  >;
};

Avec l’implémentation de if_, cfl (continuation from a lazy metafunction) et cfe (continuation from a eager metafunction):

namespace detail
{
  template<bool B>
  struct conditional;
}

template<class P, class TC, class FC>
struct if_
{
  template<class... Ts>
  using f = call<call<detail::conditional<call<P, Ts...>::value>, TC, FC>, Ts...>;
};

template<template<class...> class F, class C = identity>
struct cfl
{
  template<class... Ts>
  using f = call<C, F<Ts...>>;
};

template<template<class...> class F, class C = identity>
struct cfe
{
  template<class... Ts>
  using f = call<C, typename F<Ts...>::type>;
};


namespace detail
{
  template<bool B>
  struct conditional
  {
    template<class T, class U> using f = T;
  };

  template<>
  struct conditional<false>
  {
    template<class T, class U> using f = U;
  };
}

L’ensemble des sources se trouve sur github .

Simuler une vtable sans fonction virtuelle

Article suivant: Méta-fonction et continuation
Article précédent: Comparaison de différentes implémentations de mp_index_of

La vtable est le mécanisme interne utilisé par C++ pour implémenter les fonctions virtuelles. Lorsqu’une classe possède une fonction virtuelle, un pointeur sur la vtable (virtual table) est automatiquement réservé par le compilateur. Cette table contient des pointeurs de fonction sur l’ensemble des fonctions virtuelles de la classe et chaque classe dérivée possède sa propre vtable.

Pour une classe de base implémentant une fonction foo virtuelle comme ci-dessous, l’utilisation de obj->foo(/*params...*/) va être remplacé par quelque chose proche de cast<FunctionType>(obj->__vtable[0])(obj/*, params...*/).

struct Base
{
  virtual void foo() = 0;
};

Chaque classe dérivée qui ajoute des fonctions virtuelles réserve des cases supplémentaires dans son tableau. Le compilateur se basant sur les types utilisés pour garantir la validité des indices.

Ce fonctionnement est très économique : un pointeur pour chaque instance d’une classe et une vtable en lecture seule par classe. C’est également très facile d’ajouter de nouvelles tables, y compris dynamiquement par le chargement de bibliothèque. Mais il y a aussi des inconvénients comme une fragmentation mémoire au niveau de la position des tables et un double déréférencement pour accéder au pointeur de fonction.

Pour la suite on se base sur une interface avec une fonction draw: void draw(std::ostream&) const et 2 objets ce qu’il a de plus classique: Rect et Circle.

struct Rect
{
  void draw(std::ostream& out) const
  {
    out << "Rect\n";
  }
};

struct Circle
{
  void draw(std::ostream& out) const
  {
    out << "Circle\n";
  }
};

Une vtable à la mano

Notre vtable va contenir des pointeurs de fonction. Le type commun d’une majorité de pointeurs est void*. Sauf que les pointeurs de fonction sont une exception, il n’est pas légal de les transformer en void* – même si en interne le compilateur peut se le permettre pour sa vtable. Par contre, on peut récupérer l’adresse du pointeur de fonction pour avoir un pointeur de pointeur de fonction. Cela fait beaucoup de pointeurs et d’indirections alors le tableau sera remplacé par un tuple, car finalement on connait exactement les types de fonction que contient la vtable.

using draw_func_type = void(void const*, std::ostream&);

using drawable_vtable = std::tuple<draw_func_type const*>;

Maintenant qu’on a un type pour la vtable, il faut pouvoir la construire à partir de n’importe quel type qui pourrait supporter cette interface.

template<class T>
inline auto draw_func_ptr = [](void const* base, std::ostream& out) {
  static_cast<T const*>(base)->draw(out);
};

template<class T>
inline drawable_vtable drawable_vtable_for{
  draw_func_ptr<T>
};

Grâce à ses variables inline, on peut construire notre tableau très facilement. Il ne reste plus qu’à faire un petit wrapper pour utiliser Rect et Circle indistinctement.

struct Drawable
{
  template<class T>
  Drawable(T& x)
  : obj(&x)
  , vtable(drawable_vtable_for<T>)
  {}

  void draw(std::ostream& out) const
  {
    std::get<0>(vtable)(obj, out);
  }

private:
  void* obj;
  drawable_vtable const& vtable;
};

Drawable pourrait contenir directement Rect ou Circle plutôt qu’avoir un void*, mais pour supporter n’importe quel type et être optimisé, il est préférable d’utiliser SBO (Small Buffer Optimization) Dans une optique de simplification, la classe n’accepte que des références et garde un pointeur. On peut la considérer comme une vue polymorphique.

Une petite démonstration de la chose:

#include <iostream>

void draw(Drawable drawable, std::ostream& out)
{
  drawable.draw(out);
}

int main()
{
  Rect rect;
  Circle circle;

  draw(rect, std::cout); // affiche Rect
  draw(circle, std::cout); // affiche Circle
}

C’est tout :).

Il est possible de rendre plus simple la déclaration de la classe Drawable avec des macros pour supprimer 2/3 du code, mais je passe mon tour.

Par contre, il y a peut-être moyen d’avoir mieux pour la vtable.

Une vtable par type vs une vtable par instance

Notre Drawable contient une référence sur la vtable qui est elle-même un tableau de 1 pointeur de fonction. Autant jeter la vtable et avoir directement le pointeur de fonction comme membre. C’est plus direct et le code est plus court.

struct Drawable
{
  template<class T>
  Drawable(T& x)
  : obj(&x)
  , draw_func(draw_func_ptr<T>)
  {}

  void draw(std::ostream& out) const
  {
    draw_func(obj, out);
  }

private:
  void* obj;
  draw_func_type* draw_func;
};

Pour une classe qui ne possède qu’une fonction polymorphique, le pointeur de fonction en membre est un peu plus efficace qu’une vtable en évitant une indirection. std::function utilise le même principe en interne en plus de prendre l’ownership de l’objet. Prendre l’ownership implique de mettre l’objet en membre, si l’objet prend trop de place, comme une lambda avec une grosse capture, alors elle déborde du tampon interne et une allocation dynamique est généralement effectuée. Pour un comportement plus proche des exemples ci-dessus qui prennent une référence sur les données, il existe fn2::function_view.

Par contre, pour chaque fonction polymorphique, la classe doit contenir un pointeur de fonction ce qui augmente sa taille. Si cet objet est mis dans un vector, alors il y aura beaucoup de pointeurs similaires entre les valeurs et une vtable peut réduire drastiquement la mémoire allouée par le vecteur.

Il y a un dernier point qui n’est pas visible avec les exemples du dessus : le comportement peut être dynamiquement modifié. C’est-à-dire qu’une instance peut décider de modifier le comportement d’une de ses fonctions en la remplaçant (taper dans draw_func) sans avoir de variable d’état. La fonction en cours d’exécution représentant l’état courant. C’est un aspect de la programmation orientée prototype.

Bien sûr, avec une vtable, modifier un des pointeurs impacte tous les objets y faisant référence.

Après, rien n’empêche d’avoir un comportement hybride, une vtable pour les fonctions communes, peu utilisées ou “lentes”, et un membre pour les fonctions polymorphiques qui doivent etre “rapides” d’accès ou qui changent en court de route. Des projets tels dyno permettent cela.

La méthode du gros switch

C’est une méthode très bourrin et pas très adapté au C++. Elle consiste à connaître l’ensemble des types utilisés pour une interface et de les associer à la fonction. Plus de vtable, plus d’indirection, mais à la place un saut à base de switch. Le compilateur pourrait plus facilement inliner le code, mais on perd la posibilité de charger dynamiquement des bibliothèques.

Le problème, c’est qu’il faut centraliser manuellement toutes les instances au même endroit pour faire notre table de saut, car il n’existe aucun moyen de récupérer – par exemple – toutes les instances d’un trait is_drawable. Si le compilateur ne nous aide pas, cette solution n’est pas facile à maintenir. On peut néanmoins passer par un générateur de source qui sélectionnerait à la manière d’un clang-query tous les types pour générer complètement le corps de la fonction Drawable::draw.

Comparaison de différentes implémentations de mp_index_of

Article suivant: Simuler une vtable sans fonction virtuelle
Article précédent: Au cœur d'un variant

Dans l’article précédent sur les variants, j’ai fait une implémentation un peu spéciale de index_of. Je vais présenter une quinzaine d’implémentations possibles et le coût de chacune sur le compilateur.

Info : L’implémentation citée précédemment ne se retrouve pas ici car une forme récursive plus “classique” a les mêmes conséquences.

Avant-propos

Toutes les implémentations de mp_index_of<T, Ts...> retournent un std::integral_constant<int, i> correspondant à l’indice de T dans Ts ou -1 si T n’existe pas.

Clang possède des outils tel que templight, mais il n’y a pas d’équivalent pour Gcc. Par conséquent, les tests sont faits avec /usr/bin/time --format="%E %M" qui ressort le temps et la mémoire maximum utilisée par un programme.

Au niveau des options de compilation, -fsyntax-only permet de vérifier la validité d’un code sans générer de fichier de sortie. -std=c++17 est présent pour utiliser les plies, mais tous les algorithmes n’en ont pas besoin. -ftemplate-depth=n et -fconstexpr-depth=n appliquent une profondeur limite dans la récursivité appliquée respectivement aux templates et aux fonctions constexpr. -w supprime tous les avertissements (tels que des macros non utilisés) pour éviter que des sorties inopportunes influencent la mesure.

Il y a 2 formes de test:

  • ceux sur des listes contenant 2 types nommés x et _ et
  • ceux sur des suites x et i<n> avec n un entier.

Pour chaque test, T représente x et il peut être présent ou non dans Ts.

les valeurs de Ts sont présentées dans les légendes sous forme abrégée:

  • [x*500]: une liste de 500 x.
  • [_*250, x, _*249]: une liste de 250 _, suivit de x et d’une liste de 249 _.
  • [i{0..40}*150]: une suite de 150 i0, une autre de 150 i1 et ainsi de suite jusqu’à i40.
  • [i0..i{0..140}]: une suite [i0..i0], puis [i0..i1], etc jusqu’à [i0..i140].
  • [i{0..n},x,i{n-(n..0)..n}];n=100: les suites [i{0..100},x,i{100..100}], [i{1..100},x,i{99..100}], etc

Les sources se trouvent sur github dans un même fichier cpp. Chacune des implémentations possède son propre namespace et des macros activent individuellement chaque test.

Relation temps de compilation et mémoire

Dans du code utilisant la méta-programmation, le temps de compilation suit la même courbe que la mémoire. Plus une compilation est lente, plus la mémoire utilisée augmente allant jusqu’à saturation.

Et la mémoire est fortement liée au nombre de types instanciés par le compilateur. Ici, il ne faut pas voir une instance comme une variable, mais comme la première création d’un type. Par exemple, index_of<int, int> est une instance de type (ou d’alias), index_of<int, int, int> une seconde instance, index_of<int, float> une troisième, etc. Chaque type construit s’ajoute dans la mémoire du compilateur et l’ensemble utilise de plus en plus de place. C’est ainsi que le compilateur implémente naturellement la mémoïsation pour les templates.

Pour réduire le temps de compilation, il faut donc réduire le nombre de type instancié.

La récursivité

La première chose qu’on apprend avec les variadiques, c’est que les boucles se font avec de la récursivité en enlevant un par un les éléments. C’est une forme facile à écrire et à comprendre, mais qui crée beaucoup de types intermédiaires à l’intérieur du compilateur.

namespace recursive_ternary
{
namespace detail
{
  template<class T, class... Ts>
  struct _index_of : std::integral_constant<int, 1>
  {};

  template<class T, class First, class... Rest>
  struct _index_of<T, First, Rest...>
  : std::integral_constant<int, std::is_same_v<T, First>
    ? 0 : _index_of<T, Rest...>::value + 1>
  {};
}

template<class T, class... Ts>
using mp_index_of = std::integral_constant<int,
  (detail::_index_of<T, Ts...>::value > sizeof...(Ts))
    ? -1 : detail::_index_of<T, Ts...>::value>;
}

Une implémentation avec ternaire récursive comme on peut la trouver dans le fichier variant de libstdc++. Elle souffre d’un léger problème: il y a autant d’instance de _index_of que d’élément dans la liste, même si T se trouve en première position.

namespace recursive_indexed
{
namespace detail
{
  template<int i, class T, class... Ts>
  struct _index_of
  : std::integral_constant<int, -1>
  {};

  template<int i, class T, class First, class... Rest>
  struct _index_of<i, T, First, Rest...>
  : _index_of<i+1, T, Rest...>
  {};

  template<int i, class T, class... Rest>
  struct _index_of<i, T, T, Rest...>
  : std::integral_constant<int, i>
  {};
}

template<class T, class... Ts>
using mp_index_of = typename detail::_index_of<0, T, Ts...>::type;
}

L’indice courant se trouve en paramètre template et la récursion s’arrête dès que T est trouvé. Seulement, l’ajout de l’indice en paramètre va dégrader la mémoïsation en créant plus de types que nécessaire.

namespace recursive
{
namespace detail
{
  template<class T, class... Ts>
  struct _index_of
  : std::integral_constant<int, 1>
  {};

  template<class T, class First, class... Rest>
  struct _index_of<T, First, Rest...>
  : std::integral_constant<int, 1+_index_of<T, Rest...>::value>
  {};

  template<class T, class... Rest>
  struct _index_of<T, T, Rest...>
  : std::integral_constant<int, 0>
  {};
}

template<class T, class... Ts>
using mp_index_of = std::integral_constant<int,
  (detail::_index_of<T, Ts...>::value > sizeof...(Ts))
    ? -1 : detail::_index_of<T, Ts...>::value>;
}

Un mélange des 2 implémentations précédentes sans les inconvénients. En réalité, c’est la forme la plus communément écrite.

duré de compilation avec gcc de 3 implémentations récursives

Sans surprise, sur les 3 premiers tests, la version avec ternaire est à peu près stable quelle que soit la position de x, même s’il semble qu’évaluer la ternaire ralentisse un peu la compilation lorsque x se situe vers la fin. Alors que les 2 autres implémentations sont beaucoup plus rapides lorsque x est au début pour rattraper progressivement la version ternaire. Sans que je sache l’expliquer, la version avec index explose le compteur pour le test 3.

Comme la courbe de progression pour la version récursive classique n’est pas linéaire, je déduis que le nombre d’éléments dans un pack d’argument influence le temps de compilation. Il y a ±600ms de différence pour parcourir les 700 premiers _ contre seulement ±220ms pour les 700 restant. Cela peut se comprendre assez facilement, plus il y a de types dans la template, plus la création d’un identifiant au sein du compilateur va prendre du temps.

Le test 5 met clairement à défaut la version avec indice, car la mémoïsation ne s’applique pas ici. Avec la version ternaire et récursive, lorsque le compilateur calcule la position d’une liste de la forme [0,1,2,3], il l’a aussi fait pour [1,2,3], [2,3] et [3] ce qui permet d’être très rapide lorsqu’il tombe sur des valeurs déjà évaluées. Or, la version avec indice ajoute un élément qui empêche cela: <0, [0,1,2,3]> se déroule en <1, [1,2,3]>, <2, [2,3]> et <3, [3]> alors que <0, [0,1,2]> se déroule en <1, [1,2]> et <2, [2]>. Les suites sont différentes, le compilateur crée donc beaucoup plus de types intermédiaires ce qui ralentit la compilation.

Dans l’ensemble, l’algorithme avec index est à éviter, car il montre qu’une mauvaise mémoïsation ralentit fortement l’évaluation de template. Il faut également éviter la version ternaire au profil d’une implémentation qui stoppe la récursivité pour ne pas faire de calcul inutile. Finalement, l’algorithme de récursion classique est plus rapide dans tous les cas.

Ce qui est vrai pour Gcc, ne l’est pas forcément pour Clang comme le montre le graphique ci-dessous.

duré de compilation avec clang de 3 implémentations récursives

Premier constat, le test 3 n’a pas de pic inexplicable pour l’algorithme avec indice. Et, bien que la version récursive classique soit toujours plus rapide que celle avec ternaire, il est amusant de constater que l’implémentation avec indice supplante de peu la version classique. Sauf bien sûr lorsque la mémoïsation est mise à défaut comme dans le test 5.

Si on compare le temps de compilation entre Clang et Gcc, il s’avère que Gcc est un peu plus rapide que son concurrent alors même que les premiers tests se font sur une liste de 1200 éléments contre 1400. De mon expérience, c’est presque toujours le cas avec des templates récursives sur de “grands” ensembles.

Info : La limite de 1200 est dûe à une limitation de Clang qui ne peut pas dépasser 1293 niveaux de profondeur sans crasher (en tout cas chez moi probablement à cause d’un dépassement de pile).

Profiter davantage de mémoïsation

Il est possible d’augmenter la mémoïsation en réduisant les types dans la liste en une suite de valeur true/false. La mémoïsation est alors beaucoup plus efficace, mais la comparaison se fait sur chaque élément de la liste. Heureusement, dans un code normal, la probabilité de tomber sur la même instance de std::is_same<T, U> est très grande ce qui rend cette solution encore plus efficace.

namespace recursive_bool
{
template<class T, class... Ts>
using mp_index_of = recursive::mp_index_of<
  std::true_type,
  typename std::is_same<T, Ts>::type...
>;
}

L’utilisation de typename std::is_same<T, Ts>::type au lieu de simplement std::is_same<T, Ts> permet de restreindre les types à std::false_type et std::true_type.

On peut aussi faire la comparaison avec un detail::_index_of spécialement dédié à la recherche d’un std::true_type.

namespace recursive_bool2
{
namespace detail
{
  template<class, class... Rest>
  struct _index_of
  : std::integral_constant<int, 1+_index_of<Rest...>::value>
  {};

  template<class... Rest>
  struct _index_of<std::true_type, Rest...>
  : std::integral_constant<int, 0>
  {};
}

template<class T, class... Ts>
using mp_index_of = std::integral_constant<int,
  (detail::_index_of<typename std::is_same<T, Ts>::type...,
                     std::true_type>::value >= sizeof...(Ts))
    ? -1 : detail::_index_of<typename std::is_same<T, Ts>::type...,
                             std::true_type>::value>;
}

Et une autre version qui travaille sur des valeurs plutôt que des types pour vérifier si cela a une influence.

namespace recursive_bool3
{
namespace detail
{
  template<bool, bool... Rest>
  struct _index_of
  : std::integral_constant<int, 1+_index_of<Rest...>::value>
  {};

  template<bool... Rest>
  struct _index_of<true, Rest...>
  : std::integral_constant<int, 0>
  {};
}

template<class T, class... Ts>
using mp_index_of = std::integral_constant<int,
  (detail::_index_of<std::is_same<T, Ts>::value..., true>::value >= sizeof...(Ts))
    ? -1 : detail::_index_of<std::is_same<T, Ts>::value..., true>::value>;
}

comparaison de temps de 3 implémentations qui font une transformation en booléan

Là où la version récursive était rapide, la transformation en une liste de booléan l’est tout autant. Le bénéfice devient évident sur une grande variété de listes (test 4) et des listes homogènes (test 6) où le temps de compilation est divisé par 3.

L’algorithme recursive_bool2 spécialisé dans la recherche d’un std::true_type permet de grappiller encore quelques millisecondes principalement grâce à une spécialisation de template en moins.

À contrario, la version 3 qui manipule des booléens plutôt que des types est lente. Manipuler des types serait donc plus rapide que manipuler des valeurs dans les spécialisations. Le même comportement est présent dans Clang, même s’il est moins prononcé.

comparaison de temps de 3 implémentations qui font une transformation en booléan

Récursivité par bloc

La récursivité possède un défaut qui n’est pas forcément un problème dans le code de tous les jours: le niveau de récursion est limité par le compilateur. Gcc s’arrête à une profondeur de 900, Clang à 1024 et si je ne me trompe pas, la limite est de 500 pour MSVC. Bien sûr, cela est configurable. C’est d’ailleurs ce qui a été fait pour générer les premiers graphiques même si comme dit précédemment, Clang crashe lorsqu’on dépasse 1293.

Une technique employée pour dépasser artificiellement cette limite est de prendre plusieurs valeurs par niveau de récursivité. Cela réduit la profondeur de récursion et le nombre de types instanciés. S’il y a moins de types instanciés, la compilation devrait également être plus rapide.

Le code devient malheureusement beaucoup plus verbeux et compliqué:

namespace pack8
{
namespace detail
{
  template<bool Ok, class T,
           class U0 = T, class U1 = T, class U2 = T, class U3 = T, class U4 = T, class U5 = T, class U6 = T, class U7 = T,
           class... Rest>
  struct _index_of
  : std::integral_constant<int, (std::is_same_v<T, U0> ? 0 :
                                 std::is_same_v<T, U1> ? 1 :
                                 std::is_same_v<T, U2> ? 2 :
                                 std::is_same_v<T, U3> ? 3 :
                                 std::is_same_v<T, U4> ? 4 :
                                 std::is_same_v<T, U5> ? 5 :
                                 std::is_same_v<T, U6> ? 6 :
                                 std::is_same_v<T, U7> ? 7 : 8)
    + _index_of<std::is_same_v<T, U0> ||
                std::is_same_v<T, U1> ||
                std::is_same_v<T, U2> ||
                std::is_same_v<T, U3> ||
                std::is_same_v<T, U4> ||
                std::is_same_v<T, U5> ||
                std::is_same_v<T, U6> ||
                std::is_same_v<T, U7>
    , T, Rest...>::value>
  {};

  template<class T, class U0, class U1, class U2, class U3, class U4, class U5, class U6, class U7, class... Rest>
  struct _index_of<true, T, U0, U1, U2, U3, U4, U5, U6, U7, Rest...>
  : std::integral_constant<int, 0>
  {};

  template<class T, class U0, class U1, class U2, class U3, class U4, class U5, class U6, class U7>
  struct _index_of<false, T, U0, U1, U2, U3, U4, U5, U6, U7>
  : std::integral_constant<int, std::is_same_v<T, U0> ? 0 :
                                std::is_same_v<T, U1> ? 1 :
                                std::is_same_v<T, U2> ? 2 :
                                std::is_same_v<T, U3> ? 3 :
                                std::is_same_v<T, U4> ? 4 :
                                std::is_same_v<T, U5> ? 5 :
                                std::is_same_v<T, U6> ? 6 :
                                std::is_same_v<T, U7> ? 7 : 8>
  {};
}

template<class T, class... Ts>
using mp_index_of = std::integral_constant<int,
  (detail::_index_of<false, T, Ts...>::value >= sizeof...(Ts))
    ? -1 : detail::_index_of<false, T, Ts...>::value>;
}

Et L’équivalent qui fait une transformation en liste de booléen avant:

namespace pack8_bool
{
namespace detail
{
  using Ok = std::true_type;

  template<bool,
           class U0 = Ok, class U1 = Ok, class U2 = Ok, class U3 = Ok, class U4 = Ok, class U5 = Ok, class U6 = Ok, class U7 = Ok,
           class... Rest>
  struct _index_of
  : std::integral_constant<int, (U0::value ? 0 :
                                 U1::value ? 1 :
                                 U2::value ? 2 :
                                 U3::value ? 3 :
                                 U4::value ? 4 :
                                 U5::value ? 5 :
                                 U6::value ? 6 :
                                 U7::value ? 7 : 8)
    + _index_of<U0::value ||
                U1::value ||
                U2::value ||
                U3::value ||
                U4::value ||
                U5::value ||
                U6::value ||
                U7::value
    , Rest...>::value>
  {};

  template<class U0, class U1, class U2, class U3, class U4, class U5, class U6, class U7, class... Rest>
  struct _index_of<true, U0, U1, U2, U3, U4, U5, U6, U7, Rest...>
  : std::integral_constant<int, 0>
  {};
}

template<class T, class... Ts>
using mp_index_of = std::integral_constant<int,
  (detail::_index_of<false, typename std::is_same<T, Ts>::type...>::value >= sizeof...(Ts))
    ? -1 : detail::_index_of<false, typename std::is_same<T, Ts>::type...>::value>;
}

duré de compilation avec gcc pour un algo récursive par pack de 8

Même lorsque la position de x est éloignée (test 2 et 3), les pack8 sont efficaces. Si on prend la différence entre le test 1 et 2, et 2 et 3, il y a plus ou moins un facteur 8.

Comme c’était le cas lorsqu’on comparaît l’algorithme recursive avec recursive_bool, pack8_bool est plus rapide que pack8 lorsque le nombre de listes différentes augmente (test 5 et 7).

Le test 6 profite déjà d’une mémoïsation optimale pour les 3 implémentations, même si pack8_bool est un chouia plus lent que les autres ici.

Toutefois, la suprématie de pack8_bool par rapport à pack8 est beaucoup plus ténue avec Clang.

duré de compilation avec gcc pour un algo récursive par pack de 8

Penser différemment

Plutôt qu’avoir un index_of le plus rapide possible, il est possible de combiner d’autres algorithmes pour arriver au même résultat. Il y a un double avantage dans le cadre d’une bibliothèque de méta-programmation:

  • Implémenter un nouvel algorithme efficace est plus facile, car les optimisations telles que celles utilisées par pack8 sont déportées sur ceux avec une réelle implémentation.
  • Un nombre restreint d’algorithmes est plus souvent utilisé ce qui augmente la mémoïsation.

Ainsi, index_of peut se faire en combinant std::make_index_sequence, join, front et éventuellement tranform. On peut aussi le faire avec foldl/foldr.

Pour le faire avec join, on construit une liste d’indices de la taille de Ts qui est ensuite transformée en list<i> lorsque le type est identique à T et en list<> dans le cas contraire. Puis, on fusionne toutes les listes en une seule avec un int<-1> ajouté en fin. Le premier élément de cette liste correspond au résultat de index_of.

Il serait préférable de ne pas ajouter -1, mais ajouter une valeur dans la liste puis faire un post traitement. Cela augmente les collisions de type et par conséquent la mémoïsation. Mais restons simple !

namespace by_indices
{
namespace detail
{
  template<class...>
  struct list;

  template<class L>
  struct front;

  template<class T, class... Ts>
  struct front<list<T, Ts...>>
  {
    using type = T;
  };

  template<class = list<>, class = list<>, class = list<>, class = list<>, class = list<>, class = list<>, class = list<>, class = list<>,
           class = list<>, class = list<>, class = list<>, class = list<>, class = list<>, class = list<>, class = list<>, class = list<>,
           class = list<>, class = list<>, class = list<>, class = list<>, class = list<>, class = list<>, class = list<>, class = list<>,
           class = list<>, class = list<>, class = list<>, class = list<>, class = list<>, class = list<>, class = list<>, class = list<>,
           class = list<>, class = list<>, class = list<>, class = list<>, class = list<>, class = list<>, class = list<>, class = list<>,
           class = list<>, class = list<>, class = list<>, class = list<>, class = list<>, class = list<>, class = list<>, class = list<>,
           class = list<>, class = list<>, class = list<>, class = list<>, class = list<>, class = list<>, class = list<>, class = list<>,
           class = list<>, class = list<>, class = list<>, class = list<>, class = list<>, class = list<>, class = list<>, class = list<>,
           class... Ls>
  struct _join;

  template<class... _0, class... _1, class... _2, class... _3, class... _4, class... _5, class... _6, class... _7,
           class... _8, class... _9, class... _10, class... _11, class... _12, class... _13, class... _14, class... _15,
           class... _16, class... _17, class... _18, class... _19, class... _20, class... _21, class... _22, class... _23,
           class... _24, class... _25, class... _26, class... _27, class... _28, class... _29, class... _30, class... _31,
           class... _32, class... _33, class... _34, class... _35, class... _36, class... _37, class... _38, class... _39,
           class... _40, class... _41, class... _42, class... _43, class... _44, class... _45, class... _46, class... _47,
           class... _48, class... _49, class... _50, class... _51, class... _52, class... _53, class... _54, class... _55,
           class... _56, class... _57, class... _58, class... _59, class... _60, class... _61, class... _62, class... _63>
  struct _join<list<_0...>, list<_1...>, list<_2...>, list<_3...>, list<_4...>, list<_5...>, list<_6...>, list<_7...>,
               list<_8...>, list<_9...>, list<_10...>, list<_11...>, list<_12...>, list<_13...>, list<_14...>, list<_15...>,
               list<_16...>, list<_17...>, list<_18...>, list<_19...>, list<_20...>, list<_21...>, list<_22...>, list<_23...>,
               list<_24...>, list<_25...>, list<_26...>, list<_27...>, list<_28...>, list<_29...>, list<_30...>, list<_31...>,
               list<_32...>, list<_33...>, list<_34...>, list<_35...>, list<_36...>, list<_37...>, list<_38...>, list<_39...>,
               list<_40...>, list<_41...>, list<_42...>, list<_43...>, list<_44...>, list<_45...>, list<_46...>, list<_47...>,
               list<_48...>, list<_49...>, list<_50...>, list<_51...>, list<_52...>, list<_53...>, list<_54...>, list<_55...>,
               list<_56...>, list<_57...>, list<_58...>, list<_59...>, list<_60...>, list<_61...>, list<_62...>, list<_63...>>
  {
    using type = list<_0..., _1..., _2..., _3..., _4..., _5..., _6..., _7...,
                      _8..., _9..., _10..., _11..., _12..., _13..., _14..., _15...,
                      _16..., _17..., _18..., _19..., _20..., _21..., _22..., _23...,
                      _24..., _25..., _26..., _27..., _28..., _29..., _30..., _31...,
                      _32..., _33..., _34..., _35..., _36..., _37..., _38..., _39...,
                      _40..., _41..., _42..., _43..., _44..., _45..., _46..., _47...,
                      _48..., _49..., _50..., _51..., _52..., _53..., _54..., _55...,
                      _56..., _57..., _58..., _59..., _60..., _61..., _62..., _63...>;
  };

  template<class... _0, class... _1, class... _2, class... _3, class... _4, class... _5, class... _6, class... _7,
           class... _8, class... _9, class... _10, class... _11, class... _12, class... _13, class... _14, class... _15,
           class... _16, class... _17, class... _18, class... _19, class... _20, class... _21, class... _22, class... _23,
           class... _24, class... _25, class... _26, class... _27, class... _28, class... _29, class... _30, class... _31,
           class... _32, class... _33, class... _34, class... _35, class... _36, class... _37, class... _38, class... _39,
           class... _40, class... _41, class... _42, class... _43, class... _44, class... _45, class... _46, class... _47,
           class... _48, class... _49, class... _50, class... _51, class... _52, class... _53, class... _54, class... _55,
           class... _56, class... _57, class... _58, class... _59, class... _60, class... _61, class... _62, class... _63,
           class... Ls>
  struct _join<list<_0...>, list<_1...>, list<_2...>, list<_3...>, list<_4...>, list<_5...>, list<_6...>, list<_7...>,
               list<_8...>, list<_9...>, list<_10...>, list<_11...>, list<_12...>, list<_13...>, list<_14...>, list<_15...>,
               list<_16...>, list<_17...>, list<_18...>, list<_19...>, list<_20...>, list<_21...>, list<_22...>, list<_23...>,
               list<_24...>, list<_25...>, list<_26...>, list<_27...>, list<_28...>, list<_29...>, list<_30...>, list<_31...>,
               list<_32...>, list<_33...>, list<_34...>, list<_35...>, list<_36...>, list<_37...>, list<_38...>, list<_39...>,
               list<_40...>, list<_41...>, list<_42...>, list<_43...>, list<_44...>, list<_45...>, list<_46...>, list<_47...>,
               list<_48...>, list<_49...>, list<_50...>, list<_51...>, list<_52...>, list<_53...>, list<_54...>, list<_55...>,
               list<_56...>, list<_57...>, list<_58...>, list<_59...>, list<_60...>, list<_61...>, list<_62...>, list<_63...>,
               Ls...>
  : _join<list<_0..., _1..., _2..., _3..., _4..., _5..., _6..., _7...,
               _8..., _9..., _10..., _11..., _12..., _13..., _14..., _15...,
               _16..., _17..., _18..., _19..., _20..., _21..., _22..., _23...,
               _24..., _25..., _26..., _27..., _28..., _29..., _30..., _31...,
               _32..., _33..., _34..., _35..., _36..., _37..., _38..., _39...,
               _40..., _41..., _42..., _43..., _44..., _45..., _46..., _47...,
               _48..., _49..., _50..., _51..., _52..., _53..., _54..., _55...,
               _56..., _57..., _58..., _59..., _60..., _61..., _62..., _63...
          >, Ls...> {};

  template<class Ints, class... Ts>
  struct _find_index;

  template<class>
  struct if_
  {
    template<class T, class U>
    using type = U;
  };

  template<>
  struct if_<std::true_type>
  {
    template<class T, class U>
    using type = T;
  };

  template<std::size_t... Ints, class... Is>
  struct _find_index<std::integer_sequence<std::size_t, Ints...>, Is...>
  : front<
      typename _join<
        typename if_<Is>::template type<
          list<std::integral_constant<int, int(Ints)>>,
          list<>
        >...,
        list<std::integral_constant<int, -1>>
      >::type
    >
  {};
}

template<class T, class... Ts>
using mp_index_of = typename detail::_find_index<
  std::make_index_sequence<sizeof...(Ts)>,
  typename std::is_same<T, Ts>::type...>::type;
}

Wooa, cette monstruosité. Il faut être complètement barge pour écrire cette horreur. C’est pourtant une chose que l’on trouve dans Metal, Brigand, Cpp11 ou Boost.Hana. La palme d’or revient à Kvasir.Mpl avec une template de 1025 éléments variadiques.

comparaison de temps avec gcc de pack8 et une qui utilise d’autres algorithmes

C’est étonnamment efficace. Pas autant que pack8_bool, mais globalement plus qu’une récursion classique. Dans un projet, join et front seront utilisés ailleurs et à travers d’autres algorithmes ce qui, toujours grâce à la mémoïsation, réduit le coût total.

Fonction constexpr

Depuis C++14, il est possible d’avoir des conditions et des boucles dans les fonctions. On peut alors écrire index_of presque comme on écrirait n’importe quelle fonction impérative.

namespace loop
{
namespace detail
{
  template<bool... xs>
  constexpr int _index_of()
  {
    bool matches[]{xs..., false};
    for (std::size_t i = 0; i < sizeof...(xs); ++i) {
      if (matches[i]) {
        return int(i);
      }
    }
    return -1;
  }
}

template<class T, class... Ts>
  using mp_index_of = std::integral_constant<int,
    detail::_index_of<std::is_same_v<T, Ts>...>()>;
}

Les booléens sont en paramètre template. C’est dommage, parce que cela limite les transferts de paramètre depuis une autre fonction. Il vaut mieux mettre les valeurs en paramètre de fonction comme on le fait d’habitude.

namespace loop2
{
namespace detail
{
  template<class... T>
  constexpr int _index_of(T... xs)
  {
    bool matches[]{xs..., false};
    for (std::size_t i = 0; i < sizeof...(xs); ++i) {
      if (matches[i]) {
        return int(i);
      }
    }
    return -1;
  }
}

template<class T, class... Ts>
  using mp_index_of = std::integral_constant<int,
    detail::_index_of(std::is_same_v<T, Ts>...)>;
}

C’est beau, c’est simple, c’est élégant.

comparaison de temps de pack8_bool et une fonction constexpr

C’est fou, mais dans l’ensemble on y gagne encore. Néanmoins, la version qui prend les valeurs en paramètre est légèrement plus lente.

J’ai aussi essayé avec des fonctions récursives, mais c’est une vraie catastrophe. Premièrement, c’est extrêmement lent. Deuxièmement, la profondeur de récursion est encore plus basse qu’avec les templates: 512 pour Gcc (900 avec templates) et 800 pour Clang (1024 avec template). Mais surtout, une profondeur trop grande fait rapidement planter Clang.

En réalité, le coût d’appel de fonction est supérieur à celui d’une instanciation de classe. Mais si la fonction n’est pas récursive, alors le coût peut être amorti par rapport à une implémentation récursive, comme ici.

Fold expression

En C++17 arrive les fold expressions. Plus besoin de boucle explicite ou de fonction récursive pour dérouler des valeurs. Seulement, avec index_of, il faut jouer d’ingéniosité pour stopper le fold tout en ayant un compteur qui s’incrémente. La manière la plus simple est de mettre plusieurs instructions séparées par des ,. La dernière valeur de cette “liste” sera celle utilisée pour vérifier si T égale Ts.

namespace fold
{
namespace detail
{
  template<bool... xs>
  constexpr int _index_of()
  {
    int i = -1;
    (void)((((void)++i, !xs) && ...) && ++i);
    return i >= int(sizeof...(xs)) ? -1 : i;
  }
}

template<class T, class... Ts>
using mp_index_of = std::integral_constant<int, detail::_index_of<std::is_same_v<T, Ts>...>()>;
}

Le code est beaucoup plus concis, mais aussi beaucoup plus obscur. Il faut dire que index_of n’est pas le meilleur algorithme pour représenter la beauté des folds ;).

comparaison de temps avec gcc d’une fonction constexpr et un fold

Le résultat est très similaire à une boucle manuelle. Clang donne la même chose, mais les versions précédentes de Gcc sont extrêmement lentes avec les fold.

comparaison de temps avec clang d’une fonction constexpr et un fold

Pour terminer

On peut retenir de ces différents tests que

  • le nombre de spécialisations a un coût,
  • le temps de compilation est quadratique au nombre de paramètre variadique,
  • il faut limiter la récursion et le nombre de types instanciés,
  • les algorithmes doivent profiter de la mémoïsation,
  • spécialiser des valeurs est plus lent que spécialiser des types,
  • les fold expressions sont très efficaces,
  • une fonction constexpr est lente à instancier, mais l’utilisation de boucle peut compenser ce défaut.

Il n’y a pas eu de test sur l’affirmation qui va suivre, mais d’expérience, je sais que les alias sont plus rapides qu’une instanciation de classe, mais aussi plus cryptique au niveau des erreurs.

Si vous voulez des graphiques qui comparent 2 compilateurs, le générateur de graphe et les résultats de compilation se trouvent dans le dépôt .

Revenir en haut