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

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:

contents=$(<file) # lire un fichier
contents=$(<file1 <file2) # lire 2 fichiers
contents=$(<file ; ls) # lire un fichier et le retour de la commande `ls`

lines=( ${(f)contents} ) # tableau sans ligne vide
lines=( ${(s:\n:)contents} ) # équivalent
lines=( "${(@f)contents}" ) # 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 contents et lines.

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

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 <<<$contents 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) 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' $lines[3,5]
sed s/alligator/crocodile/ ${contents/alligator/crocodile}
sed s/alligator/crocodile/g ${contents//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 $lines[1,3]

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 } declare -A colors=(erreur: 31 avertissement: 33 info: 35) declare -A colorized for k in ${(k)colors} ; colorized+=($k "\033[$colors[$k]m$k\033[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 ${lines/(#m)*/$(() { echo -E $2:$1 } ${(s:b:)MATCH})}

Mais une boucle serait mieux ici.

printf

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

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&&> [return]

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, xs...>.

// `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 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:

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<std::add_pointer>>,
      if_<
        cfl<std::is_function>,
        cfe<detail::add_pointer_impl>,
        cfe<std::remove_cv>
      >
    >,
    std::remove_reference_t<T>
  >;
};

Avec l’implémentation de if_:

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 23 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 i<n> avec n un entier et x.

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]: uns 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 très 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 réduit 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 .

Au cœur d'un variant

Article suivant: Comparaison de différentes implémentations de mp_index_of
Article précédent: Faites parler votre compilateur

Cet article va être consacré à la réalisation d’une classe variant comme on peut la trouver dans la STL, boost et autres. Il existe de nombreuses techniques plus ou moins simples à réaliser et plus ou moins coûteuses à l’exécution. Je vais faire un petit tour de ce que j’ai pu voir et comment les implémenter.

Rappel sur ce qu’est un variant

Un variant est une union sécurisée comme on peut le trouver dans les langages fonctionnels. Contrairement aux union classique du C++, le variant garde l’information du type manipulé. C’est en cela qu’il est sécurisé, on ne sélectionne pas une valeur d’un certain type, mais on fournit une fonction que le variant appelle avec le type enregistré.

Même si le variant peut aisément remplacer l’héritage lorsque le nombre de classe dérivée est connue, il est beaucoup plus adapté lorsque les valeurs priment sur les comportements. Par exemple, une valeur d’une structure JSON représente un nombre, un tableau, une chaîne de caractères ou un objet. Il n’y a pas de comportement commun, les traitements se feront en fonction du type de la valeur.

Un premier variant

Notre version minimale de variant va contenir:

  • Les constructeurs par défaut, de copie et de déplacement.
  • Un constructeur pour initialiser avec un type de la liste.
  • Les opérateurs d’affectation correspondant aux constructeurs.
  • Une fonction visit (en membre, pour des raisons de simplification).

Info :

L’implémentation qui va suivre se veut simple et surtout naïve. De ce fait, elle est totalement inefficace et montre l’exemple à ne pas suivre. Elle servira néanmoins de base de travail et sera peaufinée tout au long des chapitres pour atteindre l’idéal du variant.

Comme le type change en cours de route, nous allons utiliser en interne une classe de base qui pour chaque dérivée va contenir le type réel. Grâce à cela, le type stocké pourra être supprimé et un nouveau type pourra y être enregistré. Cette classe de base pourra aussi servir à implémenter l’opérateur de copie via une fonction clone.

namespace detail
{
  struct VariantBase
  {
    virtual std::unique_ptr<VariantBase> clone() = 0;
    virtual ~VariantBase() = default;
  };
}

template<class... Ts>
class Variant
{
public:
  Variant() = default;
  Variant(Variant&&) = default;
  Variant(Variant const&);

  template<class T>
  Variant(T&& x);

  Variant& operator=(Variant&&) = default;
  Variant& operator=(Variant const&);

  template<class T>
  Variant& operator=(T&& x);

  template<class F>
  auto visit(F&&);

private:
  std::unique_ptr<detail::VariantBase> impl_;
};

Pour ne pas parasiter les codes, je n’ajoute pas les noexcept. De toute façon, avec les allocations dynamiques, cela ne va pas être évident.

Toute la difficulté va se trouver dans les implémentations de VariantBase et la fonction visit. Pour en faire une dérivée, un pattern assez commun va être utilisé, celui d’avoir une classe VariantImpl template sur le type à stocker.

namespace detail
{
  template<class T>
  struct VariantImpl : VariantBase
  {
    template<class U>
    VariantImpl(U&& x)
    : value_(std::forward<U>(x))
    {}

    std::unique_ptr<VariantBase> clone() override
    {
      return std::make_unique<VariantImpl>(value_);
    }

    T value_;
  };

  template<class T>
  auto make_variant_impl(T&& x)
  {
    return std::make_unique<VariantImpl<std::decay_t<T>>>(
      std::forward<T>(x));
  }
}

template<class... Ts>
Variant<Ts...>::Variant(Variant const& other)
: impl_(other.impl_->clone())
{}

template<class... Ts>
template<class T>
Variant<Ts...>::Variant(T&& x)
: impl_(detail::make_variant_impl(std::forward<T>(x)))
{}

template<class... Ts>
Variant<Ts...>& Variant<Ts...>::operator=(Variant const& other)
{
  impl_ = other.impl_ ? other.impl_->clone() : nullptr;
  return *this;
}

template<class... Ts>
template<class T>
Variant<Ts...>& Variant<Ts...>::operator=(T&& x)
{
  impl_ = detail::make_variant_impl(std::forward<T>(x));
  return *this;
}

En réalité ce qu’on vient de faire ici n’est ni plus ni moins qu’un std::any. Si on réfléchit bien, nous ne sommes pas limités dans les types à stocker et il n’y a aucune vérification au niveau de l’initialisation d’une valeur. C’est mal, mais on va rester comme cela pour le moment.

Reste ensuite la fonction visit. À ce stade, je dirais que la solution la plus naturelle est d’utiliser dynamic_cast pour déterminer le type réel et appeler la bonne surcharge de fonction.

template<class... Ts>
template<class F>
auto Variant<Ts...>::visit(F&& f)
{
  assert(impl_);
  auto visit_impl = [&](auto rec, auto* t, auto*... ts){
    using Impl = detail::VariantImpl<std::decay_t<decltype(*t)>>;
    if constexpr (sizeof...(ts)) {
      return dynamic_cast<Impl*>(impl_.get())
        ? f(static_cast<Impl*>(impl_.get())->value_)
        : rec(rec, ts...);
    }
    else {
      (void)rec;
      return f(static_cast<Impl*>(impl_.get())->value_);
    }
  };
  return visit_impl(visit_impl, static_cast<Ts*>(nullptr)...);
}

Cette implémentation parcourt récursivement les types du variant pour trouver celui qui correspond à la valeur de impl_, appel f avec le bon type puis propage son retour en remontant la pile d’appel. Le dernier élément est un cas spécial traité dans le else car, quand on le compare avec dynamic_cast, le résultat est toujours vrai. Comme notre variant ne contient –normalement– qu’un nombre restreint de types, si la valeur de impl_ ne correspond pas aux types qui précèdent le dernier, alors impl_ est forcément du type du dernier élément.

Moi j’aime pas dynamic_cast

dynamic_cast est souvent un signe révélateur d’un problème de conception. Si on abstrait les valeurs, c’est dans le but de ne pas se soucier du type de l’implémentation. Or, un variant met le focus sur le type et rend caduque cette abstraction. Seulement, dynamic_cast a un coût d’exécution exorbitant par rapport à la tâche qu’il effectue ici.

De ce fait, dynamic_cast n’est pas une bonne solution, il est plus judicieux de conserver une information pour différencier les types. Comme un variant contient une liste d’éléments, l’indice du type utilisé suffit amplement.

class Variant
{
  // ...
private:
  std::unique_ptr<detail::VariantBase> impl_;
  std::size_t type_index_;
}

Maintenant, il faut convertir un type en indice, c’est à ce moment que la méta-programmation arrive à la rescousse.

#include <type_traits>

namespace detail
{
  template<class T, class... Ts>
  struct count_items_to_right_of;

  template<class T, class U, class... Us>
  struct count_items_to_right_of<T, U, Us...>
  : count_items_to_right_of<T, Us...>
  {};

  template<class T, class... Us>
  struct count_items_to_right_of<T, T, Us...>
  : std::integral_constant<std::size_t, sizeof...(Us)>
  {};
}

template<class T, class... Ts>
using mp_index_of = std::integral_constant<
  std::size_t,
  sizeof...(Ts) - detail::count_items_to_right_of<T, Ts...>::value - 1
>;

mp_index_of est un alias sur std::integral_constant. L’implémentation déroule récursivement les éléments de Ts jusqu’à trouver T et retourne le nombre d’éléments qu’il reste dans la liste. Soustraire ce résultat à sizeof...(Ts) - 1 permet d’avoir la position de T.

On met à jour l’implémentation pour initialiser le nouveau membre.

template<class... Ts>
Variant<Ts...>::Variant(Variant const& other)
: impl_(other.impl_->clone())
, type_index_(other.type_index_)
{}

template<class... Ts>
template<class T>
Variant<Ts...>::Variant(T&& x)
: impl_(detail::make_variant_impl(std::forward<T>(x)))
, type_index_(mp_index_of<std::decay_t<T>, Ts...>::value)
{}

template<class... Ts>
Variant<Ts...>& Variant<Ts...>::operator=(Variant const& other)
{
  impl_ = other.impl_ ? other.impl_->clone() : nullptr;
  type_index_ = other.type_index_;
  return *this;
}

template<class... Ts>
template<class T>
Variant<Ts...>& Variant<Ts...>::operator=(T&& x)
{
  impl_ = detail::make_variant_impl(std::forward<T>(x));
  type_index_ = mp_index_of<std::decay_t<T>, Ts...>::value;
  return *this;
}

Puis on supprime dynamic_cast de la fonction visit, le remplaçant par une comparaison d’index.

template<class... Ts>
template<class F>
auto Variant<Ts...>::visit(F&& f)
{
  assert(impl_);
  auto visit_impl = [&](auto rec, auto* t, auto*... ts){
    using T = std::decay_t<decltype(*t)>;
    using Impl = detail::VariantImpl<std::decay_t<T>>;
    if constexpr (sizeof...(ts)) {
      return type_index_ == mp_index_of<T, Ts...>::value
        ? f(static_cast<Impl*>(impl_.get())->value_)
        : rec(rec, ts...);
    }
    else {
      (void)rec;
      return f(static_cast<Impl*>(impl_.get())->value_);
    }
  };
  return visit_impl(visit_impl, static_cast<Ts*>(nullptr)...);
}

Peu de changement finalement, mais maintenant variant peut fonctionner sans support de RTTI !

On notera aussi que puisque nous possédons l’indice lié au type, on peut aussi remplacer les fonctions virtuelles par un appel à visit pour supprimer la vtable et enlever l’indirection pour accéder aux fonctions virtuelles dans celle-ci.

L’allocation dynamique n’est pas gratuite

Il est vrai que l’allocation dynamique a un coût non négligeable sur les performances. Personne n’a idée de faire new int alors qu’en regardant de plus près, c’est exactement ce que fait notre implémentation. Vient ensuite les déréférencements de pointeur qui font sauter des optimisations. Effet amplifié lorsque les fonctions sont virtual. Décidément, l’allocation dynamique pour un variant n’est pas une bonne idée.

Le mieux serait de stocker nos types de la même manière qu’une union: un seul bloc mémoire de la taille du type le plus grand. À ma connaissance il existe 2 possibilités:

Pour choisir le procédé le plus efficace, nous implémentons les 2 dans une classe qui ne possède que les fonctions d’accès et les constructeurs.

template<class... Ts>
struct AlignedStorage
{
  template<class T>
  T& get()
  {
    return *reinterpret_cast<T*>(&data);
  }

private:
  std::aligned_union_t<0, Ts...> data;
};

Sans les constructeurs, la version avec std::aligned_union est vraiment simple. Mais l’utilisation de reinterpret_cast empêche de mettre la fonction get() en constexpr (gcc l’accepte néanmoins).

À contrario, la version avec une union récursive est extrêmement verbeuse (toujours sans constructeur d’initialisation de valeur):

namespace detail
{
  template<class T, class... Ts>
  union RecursiveUnion
  {
    char dummy;
    T value;
    RecursiveUnion<Ts...> others;

    RecursiveUnion() : dummy() {}
    ~RecursiveUnion(){}
  };

  template<class T>
  union RecursiveUnion<T>
  {
    char dummy;
    T value;

    RecursiveUnion() : dummy() {}
    ~RecursiveUnion(){}
  };

  template<class T, class... Ts>
  T& get(RecursiveUnion<T, Ts...>& u)
  {
    return u.value;
  }

  template<class T, class U>
  T& get(U& u)
  {
    return get<T>(u.others);
  }
}

template<class... Ts>
struct UnionStorage
{
  template<class T>
  T& get()
  {
    return detail::get<T>(data);
  }

private:

  detail::RecursiveUnion<Ts...> data;
};

Si on regarde l’assembleur, il s’avère que les 2 versions sont exactement les mêmes.

Pour initialiser l’objet avec une valeur, la version avec std::aligned_union doit utiliser un placement new qui empêche de rendre le constructeur constexpr. Ce qui par la même occasion s’applique aussi au variant. Sans compter le problème du reinterpret_cast dans la fonction get(). Du coup, bien que cette version soit plus simple et que je ne mette pas constexpr, l’union récursive est préférable.

// std::in_place_index_t
template<std::size_t i>
struct in_place_index_t
{
  explicit in_place_index_t() = default;
};

(RecursiveUnion devient VariadicUnion)

    template<class U>
    VariadicUnion(in_place_index_t<0>, U&& x)
    : value(std::forward<U>(x))
    {}

    template<std::size_t I, class U>
    VariadicUnion(in_place_index_t<I>, U&& x)
    : others(in_place_index_t<I-1>{}, std::forward<U>(x))
    {}

Puis on adapte les fonctions de Variant. Le code final est plutôt gros alors je ne mets que le lien .

Pour éviter une condition particulière dans le code, l’union possède un membre supplémentaire: Uninit, utilisé par init, copy et destroy pour représenter un variant sans valeur.

Il y a aussi une condition dans operator= pour choisir entre la fonction copy si les 2 éléments sont du même type ou les fonctions destroy+init dans le cas contraire. Cette condition peut être supprimée si:

  • Tous les éléments ont un destructeur trivial: il n’y a pas besoin de faire destroy+init.
  • La fonction visit peut prendre plusieurs variants en paramètre pour faire un switch allant de 0 à (sizeof...(Ts) + 1) * (sizeof...(Ts) + 1).

Mot de la fin

Bien que le variant actuel soit incomplet, il est utilisable et proche des implémentations actuelles. Mais il y a plusieurs petits détails qui ne sont pas approfondis ici:

  • l’optimisation sur type_index,
  • les différents moyens de remplacer une vtable (ici je n’utilise que le if/else récursif),
  • le coût d’utilisation d’un objet en fonction de sa nature (par exemple: le compilateur dévirtualise-t-il les fonctions virtuelles venant d’un membre de variant ?)
  • les unions récursives
  • et bien d’autres

Les prochains articles seront davantage axés sur la méta-programmation et indirectement reliés avec certains aspects du variant présentés ici.

Les sources sont disponibles sur github .

Faites parler votre compilateur

Article suivant: Au cœur d'un variant
Article précédent: Ma vision de l'accessibilité appliquée pour ce blog

En C++, notre meilleur ami est le compilateur. Encore faut-il bien le configurer pour qu’il nous crache un maximum d’avertissements en pleine poire. Hélas, il s’avère que les options dépendent grandement du compilateur et de la version.

Du côté de Clang, il y a un -Weverything qui active absolument tous les warnings – dont certains que je qualifie de douteux –, alors que pour Gcc, -Wall et -Wextra n’activent pas tout. Mais pour les 2, il n’y a pas d’option qui regroupe celle de débogage ou d’analyse dynamique. Du coup, pour chaque nouvelle version, il y a un nombre plus ou moins important de flag à ajouter.

De ce constat, et parce que je possède plusieurs formats de fichier à mettre à jour, je me suis fait un générateur qu’on peut trouver sur mon github: cpp-compiler-options. Les fichiers générés sont dans le dossier output et couvrent clang-3.1 à 6.0 et gcc-4.7 à 7.1.

Petite astuce pour gcc et clang. On peut mettre des options dans un fichier et le donner au compilateur en préfixant le nom du fichier par @. Il y a un mémo dans le README.

Ma vision de l'accessibilité appliquée pour ce blog

Article suivant: Faites parler votre compilateur
Article précédent: De Blogspot à Hugo, il a changé de peau

Pour changer de la programmation logicielle, je vais parler de l’accessibilité d’un site et des petits détails exaspérants que je rencontre sur la toile. Je pense qu’une bonne partie parle à chacun, généralement on fait avec, simplement parce qu’il n’y a pas d’autre choix, mais c’est toujours frustrant de tomber dessus.

Pour le blog, j’ai passé pas mal de temps sur un template déjà existant en touchant finalement un peu à toutes les parties CSS et HTML. Je vais ici parler un peu de couleur, de police, de lien, de la manière de disposer des cadres et quelques autres bricoles insignifiantes et par définition essentielles.

Plus de clics, moins de contenu

Depuis plusieurs années, une pratique courante consiste à multiplier les clics pour accéder à du contenu. Cela prend plusieurs formes, généralement à travers un menu sectionné sur une multitude de pages, des listes déroulantes ou du texte qui apparait au clic. De l’intuitif comme ils disent.

Le défaut de vouloir tout cacher est de rendre difficile d’accès l’information:

  • Il n’est pas possible de faire une recherche de texte.
  • Si on ne sait pas dans quel menu aller, on finit par cliquer partout.
  • L’information est diffuse sur plusieurs pages, c’est beaucoup de manipulations, pénible et long. Encore plus s’il faut naviguer sur plusieurs pages avec une connexion lente.

Un des exemples typiques que je déteste est matérialisé par la FAQ de dvp: chaque catégorie doit être déroulée pour qu’apparaissent les questions. Résultat, depuis la mise en place de ce nouveau système, je ne la consulte plus puisque trouver une question approximative est une gageure. Il me faut trouver la catégorie, l’éventuelle sous-catégorie, dérouler chacune et enfin pouvoir faire une recherche de texte sur le mot qui m’intéresse dans la question (le moteur de recherche donne souvent beaucoup trop de résultats).

À contrario, les FAQs sur le site du gouvernement permettent un affichage de toutes les questions et/ou réponses ce qui permet une recherche rapide et une lecture continue.

Je trouve que le site doisjeutiliser.fr donne un bon résumé de la situation. Et je suis d’accord avec tous les autres contre-exemples.

De plus, comme le langage graphique est différent entre les logiciels et entre sites on ne sait pas toujours le comportement associé au clic ou au lien par manque d’indicateur, on va au-devant de grosses surprises. Une icône qui représente une sous-catégorie déroulée pour tel site, mais enroulée pour un autre site. Un clic pour dérouler alors que cela ouvre une nouvelle page, voire pire, une nouvelle fenêtre ou, inversement, ouvrir dans un nouvel onglet un lien fait pour afficher un zone cachée (généralement, on tombe sur une page vide). Dans les 2 scénarios c’est une mauvaise surprise.

Et certains ont la bonne idée de redéfinir (ou de simuler) les actions d’une liste déroulante en supprimant toute action clavier. Tu veux atteindre « août » en appuyant sur a ? Fais autrement ! Avec un peu de chance, il faudra aussi cliquer sur le bouton « Ok » pour valider son choix. Il ne faudrait pas user la touche entrée…

Vous l’aurez compris, je suis contre cette pratique du « clic pour apparaître » à outrance. Pour prendre en exemple le blog, sur l’ancien (blogspot) les archives sont déroulées par années et par mois. Avec une moyenne qui dépasse difficilement 2 articles/mois, en trouver un précis en moins de 2 clics mérite une médaille. Ici, les archives sont sur une page dédiée qui permet une vue d’ensemble immédiate sans étaler les titres sur plusieurs lignes.

(On y notera la police monospace sur la date qui facilite le parcours vertical ;).)

Disposition générale et débordement

De mon point de vue, un site web possède classiquement un en-tête, un menu et du contenu, le tout positionné dans un nombre restreint de possibilités. La grande différence se joue sur la gestion du vide. Càd, la place que va prendre un élément sur la page.

Il existe principalement 3 cas de figures:

  • Prendre un maximum de place.
  • Mettre une limite maximum sur la largeur.
  • Avoir une largeur fixée.

Une solution n’est pas meilleure qu’une autre, le choix dépend du design, du type de contenu et du dispositif d’affichage. La plupart du temps le site prend toute la largeur jusqu’à une taille raisonnable avant de permuter en taille fixe définie en pourcentage ou en pixel.

On peut très bien avoir un contenu qui prend toute la page quelle que soit la résolution, mais il faut être conscient qu’une ligne trop grande est difficile à lire. Plus une ligne est longue ou un paragraphe dense, moins il y a de points de repère visuels pour « suivre » le texte. Cela augmente le risque de glisser à la ligne suivante au milieu d’une phrase, de sauter une ligne ou relire la même au lieu de passer à la suivante. L’extrême inverse étant le format colonne utilisé par les journaux ou magazines, mais difficile à reproduire sur un navigateur.

Concernant la disposition du menu, à priori, n’importe laquelle fait l’affaire. À gauche, à droite ou en haut, quelle importance ? Mais c’est oublier un point essentiel: que faire quand un élément est trop grand ? La solution immédiate est simple: aller à la ligne. C’est même le comportement par défaut des navigateurs sur les blocs de texte. Ouf, nous sommes sauvés, tout va bien dans le meilleur des mondes.

Sauf qu’il existe aussi les images, les tableaux, les lecteurs vidéo et l’ensemble des éléments dont un « saut de ligne » n’est pas envisageable. Et là, c’est le drame. Heureusement, il existe plein d’horribles solutions.

Les exemples qui suivent sont faits avec une ligne de code qui ne fait pas de saut de ligne automatique.

  • S’adapter au plus grand.
    Débordement par la droite.
    Débordement par la gauche. Le scroll disparaît. Au moins pour Firefox.
  • Compacter les éléments ou mettre dans un scroll.
    Un scroll alors qu'il y a de l'espace à droite.
  • Cacher le surplus.
    Il n'y a plus moyen de lire le contenu qui déborde.
  • Superposer les éléments.
    La partie droite cache une partie du contenu.

Presque toutes ces images ont un point commun: un menu à droite. Ce n’est pas anodin, il est difficile d’avoir un menu à droite quand la partie gauche veut prendre sa place.

En déplaçant le menu à gauche, les problèmes de superposition contenu/menu disparaîssent d’eux-mêmes. On peut alors laisser le bloc prendre une place optimale.

Mais il faut le faire intelligemment pour ne pas tomber sur le premier cas qui ajoute un scroll horizontal pour l’ensemble du contenu. Vous vous imaginez devoir scroller pour lire une ligne ? Puis bon, les paragraphes qui deviennent des lignes de 3 kilomètres, non merci !

Il serait également bête de faire comme le second cas qui ajoute un scroll sur tous les éléments dépassant une certaine taille alors qu’un énorme vide persiste sur la droite.

J’ai assisté sur la doc de Hugo au passage d’un gabarit full page à celui d’une taille fixe et, malheureusement, chaque code se voyait estampillé d’un scroll horizontal. Obligé de déplacer la souris dessus pour qu’il s’agrandisse automatiquement jusqu’au bord droit de ma fenêtre. Ce qui rendait par la même occasion le scroll superflu. La seule question qui m’est venue est « Pourquoi dois-je utiliser une souris ? Pourquoi ce n’est pas l’apparence par défaut ? ».

Bon ok, deux questions.

Pour le blog, mon choix s’est porté sur un menu à gauche, un contenu sur plus au moins 60% de large pour le centrer, mais avec les contenus trop grands qui débordent un maximum avant le recourt au scroll. C’est la disposition la plus pratique à mes yeux. Le résultat peut même être visible sur l’avant-dernier article dont un code possède une ligne plus grande qu’à l’habitude.

Liens, zone de clic et surbrillance

Comment parler du web sans un petit mot sur les liens ? Le point central de la navigation internet et pourtant si difficile à cliquer pour moi.

J’ai l’impression de faire partie des gens dont la souris est invariablement attirée par la rangée de pixels non cliquable en plein milieu d’un lien. C’est systématique lorsque celui-ci est sur plusieurs lignes. Tout indique que je suis dessus: la couleur de fond du cadre qui change, celle du texte, la petite décoration qui apparaît. Tout, sauf le pointeur de souris. Mais il y a tellement de changement autour que ce détail ne se voit même plus.

Clic... Clic ? Clic clic clic ! Comment ? Je ne suis pas dessus ?

Arrive mon second fléau, déplacer suffisamment la souris pour être sur le lien. Mais pas trop, parce que ce foutu cadre qui change de couleur n’en fait pas partie non plus.

Le problème que je rencontre ici est récurant. Des changements de couleurs et de formes donnent l’impression de pouvoir effectuer une action alors que ce n’est pas vrai. Il vient alors un sentiment d’incompréhension très désagréable qui se change petit à petit en frustration lorsqu’on réalise que le pointeur de souris n’a pas la bonne forme.

Quand un cadre contenant un lien change de couleur au passage de la souris, c’est une invitation au clic. Celui-ci se doit d’être cliquable pour répondre au principe de la moindre surprise. Bonus, cela élargit la surface de clic et rend par la même occasion le lien plus accessible.

C'est quand même plus agréable lorsque le cadre est un lien.

Cette extension de la zone de clic est très présente sur le blog. Comme les espaces blancs décoratifs sur le menu qui font partie du lien. Il est possible en plein écran de plaquer le curseur à gauche et de pouvoir cliquer dessus. Ou par exemple les liens « Précédent » et « Suivant » en fin d’article qui prennent chacun une moitié de largeur de contenu. Ou encore les icônes de flux RSS qui possèdent une zone de clic réelle beaucoup plus grande que l’image. Chacun de ces éléments possède une zone de clic plus large pour simplifier la visée.

Une dernière chose à éviter impérativement sur un lien concerne l’application d’un effet de gras au survol. Si par malheur le lien se situe en fin de ligne, la mise en gras va agrandir de quelques pixels les lettres et peut déplacer des mots à la ligne suivante. Qui se retrouvent en dehors de la zone de pointage. Qui reviennent car ne sont plus concernés par le survol. Puis repartent. Et ainsi de suite rendant le lien presque incliquable pour ceux ayant échappé à la crise d’épilepsie. Bien sûr, si le lien est une boîte qui grandit ou ne se déplace pas, il n’y a aucun problème.

À présent, parlons d’une évidence: un lien doit être mis en surbrillance par rapport au reste du contenu. S’il n’y a aucun repère visuel qui le différencie, personne ne le remarquera. Dans l’imaginaire collectif, un texte bleu ou violet et surtout souligné représente un lien. Bien que l’on puisse le modifier, je déconseille d’enlever le soulignement. Un simple changement de couleur pouvant être considéré comme une mise en gras.

En plus de la pseudo-classe :hover –source des problèmes cités au début du chapitre lorsqu’elle est mal utilisée–, il est essentiel de mettre en valeur les liens possédant le focus (:focus) pour les adeptes de la navigation clavier. Certains navigateurs comme Opéra possèdent des raccourcis clavier très pratiques pour sauter de lien en lien, mais très handicapants lorsque le site n’utilise pas ce marqueur visuel.

(Je profite du paragraphe pour parler des liens d’évitement (ici et ) pour sauter les regroupements de texte comme le menu et simplifier la vie des utilisateurs de clavier et autres dispositifs).

Pour finir sur les pseudo-classes et clore le sujet, je trouve que beaucoup de sites ignorent :active, alors que c’est un excellent moyen d’informer un visiteur que son clic est bien pris en compte. C’est un indicateur qui manque souvent quand j’ouvre dans un nouvel onglet: ai-je bien cliqué ? Cette information m’est tellement essentielle que je force dans mon navigateur un cadre en pointillé rouge lorsque je valide un lien.

La police des caractères

Une chose que j’ai apprise en testant plusieurs polices d’écriture, est que la taille apparente varie énormément entre 2 fonts. Mettre une taille de police adaptée à la lecture n’est pas suffisant, il faut aussi que chaque police dans la liste de font-family ait une taille similaire au risque d’avoir des textes trop grands, ou pire, trop petits.

Je suis également tombé sur un conseil qui va à l’encontre du bon sens: mettre un font-size: 62.5% global. Avec pour seule justification que la taille par défaut est trop grande. Sans prendre en compte la taille effective d’une police et en rejetant toute configuration utilisateur. Si « 62.5% » est trop petit, c’est le problème de l’utilisateur après tout.

Police16px10px (62.5%)
Sans-serif Lorem ipsum Lorem ipsum
Arial Lorem ipsum Lorem ipsum
Times New Roman Lorem ipsum Lorem ipsum
Times Lorem ipsum Lorem ipsum

Étrangement, il n’y a que sur internet où la taille est redéfinie. Sur une application de bureau personne ne s’en occupe et les polices et tailles configurées au niveau du système sont utilisées automatiquement pour les différents types d’éléments (titre, paragraphe, police monospace, etc).

Mon seul conseil pour font-size est d’appliquer le différentiel entre Serif/Sans-Serif et la police choisie car Serif ou Sans-Serif ont un différentiel de jambage supérieur et inférieur égal au nombre de pixels demandé.

Comme on parle d’empattement (serif ou sans-serif), j’en suis venu à la conclusion qu’une police sans empattement est plus lisible sur un écran. Peut-être à cause de la petitesse des lettres qui « charge » visuellement les glyphes. Ou Le rétro-éclairage, je ne sais pas.

Le pouvoir de la couleur

La couleur est un vecteur d’information aussi importante –voire plus– que la forme. Par contre, il faut utiliser la couleur d’usage sur l’objet représenté au risque de perturber le lecteur.

Perturbant, n'est-ce pas ?

La couleur et les effets permettent également de distinguer les éléments entre eux. Par exemple, une légère ombre sur un bouton lui donne un relief qui le distingue d’un cadre lambda. Mais il faut savoir varier. Si je prends comme exemple les boutons sociaux, il est difficile d’en trouver un précisément lorsqu’ils sont tous de la même couleur.

Y a-t-il ton réseau préféré ?

Alors que mettre la couleur habituellement utilisée par une marque permet de se focaliser presque sans effort dessus.

Et maintenant ?

Même si les couleurs du site sont banales, je me permets quelques remarques. Premièrement, il vaut mieux se restreindre à un nombre raisonnable de couleurs, mais suffisamment contrastées pour les dissocier. Trop de couleurs empêchent de hiérarchiser l’information, un contraste trop faible de dissocier les éléments ce qui rend illisible le texte.

Il existe différents outils pour faire des palettes de couleurs qu’on peut fabriquer avec le logiciel Agave, le très bon site Adobe Kuler, colourco.de ou code-couleur.com qui liste quelques palettes de couleurs. Ce dernier contient également la signification de certaines couleurs dans le monde occidental. Je trouve intéressant d’ajouter cet article trouvé sur la toile pour voir un peu –bien que difficile à vérifier– l’évolution et usage au fil du temps. En cherchant un peu, on tombe sur pléthore de sites et de conseils. On a l’embarras du choix.

Si je peux donner un conseil, évitez les couleurs trop pures ; celles qui contiennent une composante de couleur proche de 255 et les autres à 0 comme pour les couleurs primaires (ex: #ff0000). Ce sont des couleurs très prononcées, pas du tout naturelles. Je trouve qu’elles brillent trop et agressent les yeux.

Une dernière chose concernant les couleurs, tout le monde ne les voit pas de la même façon, essayer un filtre pour simuler le daltonisme est une expérience intéressante.

Les métadonnées sont importantes !

Les métadonnées sont toutes les informations relatives à un document qui permettent notamment de le replacer dans un contexte sans le supposer après lecture de plusieurs paragraphes (même ainsi, certains éléments sont impossibles à déduire). Elles sont tellement importantes qu’il est possible de déduire le contenu du document associé sans l’avoir jamais lu.

J’exagère un peu, mais si on prend un article de blog et qu’on a l’habitude de lire les commentaires de l’auteur sur des forums, on se fait une relativement bonne idée du contenu de ses écrits. Mais pour cela il faut au moins avoir le nom de l’auteur, le sujet principal (titre, domaine du sujet) et probablement la date. Cela paraît évident, mais des fois, un ou plusieurs éléments manquent. Grossièrement, ce sont pour moi des marqueurs qui permettent de filtrer les lectures potentiellement intéressantes et de se préparer mentalement.

Plus généralement, les métadonnées sont un moyen de mettre en relation des données avec d’autres via des URIs dans le but de faire des requêtes extrêmement sophistiquées à la manière de SQL (SPARQL). On parle aussi de web sémantique que je trouve une très bonne idée pour des ressources ayant beaucoup de relations, de dépendances, etc comme les encyclopédies ou des documents de normalisation, mais c’est un travail de longue haleine et franchement superflu dans le cadre d’un blog.

Donc voilà, les métadonnées c’est cool, mais je me contente de quelques informations en tête et pied d’article. On peut aussi les retrouver de manière plus structurée dans le flux RSS.

Parmi les informations qui gravitent autour des articles ici, on trouve:

  • Les catégories, car c’est un moyen facile de centrer le domaine d’application et filtrer les contenus.
  • La date, parce qu’une information se périme vite. Les bonnes pratiques d’hier sont les mauvaises pratiques de demain. Et si je parle d’hier, on sait au moins de quel hier je fais référence.
  • La date de dernière mise à jour s’il y a lieu. Il y a aussi une entrée dédiée dans le menu. Pour le moment je ne sais pas comment mettre en valeur les changements, peut-être une note en pied de page ?
  • Le temps de lecture. C’est un bête calcul en fonction du nombre de mots qui peut être plus précis que la taille du scroll en présence d’image. Et comme la page d’accueil contient plusieurs articles, la taille du scroll n’est pas une information fiable.
  • L’auteur, même si pour le coup il n’y aura – probablement – que moi.
  • Le lien permanent et les boutons de partage pour conquérir le monde.

Les commentaires

Sur un site statique, il n’est pas possible d’intégrer son propre système de commentaire. On peut utiliser un service web comme disqus.com qui est très bien fait, mais aussi lourd et lent à charger.

C’est un reproche qui peut se faire sur beaucoup de sites. À force d’incorporer nombre de services externes (pour certains discutables), le site est ralenti et perd en fluidité.

Comme je pense qu’un espace commentaire est toujours intéressant, je tenais vraiment à en avoir un sur le blog. Alors je me suis dit, quitte à utiliser github.io, autant y aller jusqu’au bout et me servir des issues de github comme système d’échange. Ce n’est pas aussi bien intégré dans la page qu’un système natif (il faut passer par github pour poster), mais cela fait son job. Je perds par contre les commentaires anonymes puisqu’il faut un compte pour poster.

Mais encore

À vrai dire, il y a pas mal de petites choses non citées qui m’agacent beaucoup (titre tronqué devenant trop court, animation trop lente, etc), mais ce sont des conseils qu’on peut retrouver assez facilement sur la toile.

J’ai davantage axé mes propos sur des détails que je trouve peu discutés. Tellement peu évoqués que j’ai l’impression d’être le seul concerné. Pour dire. Mais si cela permet de faire réfléchir, tant mieux.

Après, c’est bien possible que n’étant pas spécialement attiré par les technos web, un site spécialisé que je ne connais pas en parle mieux que moi. Tant mieux aussi.

De Blogspot à Hugo, il a changé de peau

Article suivant: Ma vision de l'accessibilité appliquée pour ce blog
Article précédent: Minimiser les copies dans operator+

Il y a 2 ans je me suis dit :

Au prochain article, j’essaye un autre système de blog !

Et depuis 2 ans, plus rien… Je n’ai pas parcouru le web à la recherche de la solution idéale, loin de là, je n’avais juste pas d’idée d’article.

Il y a 3 mois, en regardant une classe de matrice en C++, une idée m’est venue. J’ai écrit mon article puis cherché un système de site statique.

Au départ, j’avais en tête Octopress utilisé par Luc Hermitte pour son blog. Le principe est d’écrire des fichiers en markdown, de générer le blog et mettre le tout sur github pour avoir une adresse en github.io. Le mettre sur github n’est pas une obligation, mais c’est pour moi le plus simple.

J’ai donc essayé Hugo… Ma logique est infaillible :).

Pourquoi quitter Blogspot ?

Avant de commencer, une petite explication sur pourquoi Blogspot ne m’est pas pratique.

La principale raison est que l’utilisation de Blogspot m’oblige à faire du post-traitement sur mes articles. Pour avoir la couleur dans les codes, ils sont écrits dans un éditeur puis convertits en HTML (via Kate dans mon cas). La couleur de fond est trop contrastée pour le blog ce qui oblige un post-traitement supplémentaire. L’ensemble est plutôt rapide à faire, mais modifier un code est pénible.

Puisque je suis dans le mode HTML de blogspot, je me tape aussi tout le balisage des liens, paragraphes, mots importants, etc, ce qui parasite le texte. L’absence de couleur dans la zone d’édition n’aide pas beaucoup.

Autre point, j’écris rarement un article depuis l’interface web. Déjà parce qu’il faut y accéder – il y a un peu trop de clics à faire et Blogspot reste lent à charger – ensuite parce que l’éditeur est trop pauvre. Ça paraît con, mais les possibilités de mon éditeur de code sont très sollicités, même pour l’écriture d’un article. J’envisage même de faire des plugins pour de la saisie rapide.

Ceci fait qu’utiliser un générateur de type markdown me trottait dans la tête depuis un bon moment. Il existe plein de générateurs vers HTML, Pandoc étant probablement le plus connu. C’est suffisant. On écrit un article, on convertit et on colle la sortie dans la zone d’édition du blog.

J’aurais très bien pu utiliser Blogspot + un générateur. Sauf que je trouve Blogspot lourd à charger et les possibilités de menu et de mise en page sont un peu limitées. Alors autant voir ailleurs !

Essai de Hugo

En fait, au moment où je commençais à regarder les systèmes existants, quelqu’un sur le MM de 42 mit un lien vers Hugo. Le principe reste le même – au moins pour la génération de blog – avec comme objectif principal de ne pas avoir de dépendance et de générer rapidement le site.

Un truc qui me plaît bien est de pouvoir utiliser autre chose que le markdown par défaut, par exemple, Asciidoctor ou ReStructuredText. Les implémentations ne sont pas nativement incorporées à Hugo ce qui rend leur utilisation plus lente dans la génération (il faut appeler un programme externe). Toutefois, il y a en native 2 implémentaitons de markdown et le mode Org de Emacs. Pour se faire une idée du mode org, il y a 3 traductions françaises dont 2 à venir de Pragmatic Emacs sur linuxfr.

J’ai essayé Asciidoc, mais il ne fonctionne pas tel quel, il m’a fallu un intermédiaire qui supprime l’option --safe pour la coloraion du code (celle-ci utilise Pygmentize). Par contre, je trouve le code HTML généré vraiment trop verbeux. À mon sens, entourer les paragraphes de <div class="paragraph">...</div> est plus que superflux. Je ne sais pas ce qu’il en est des autres formats ne les ayant pas essayés, pour le moment mes besoins suffisent pour le markdown. À savoir que les formats non natifs ne peuvent pas générer le sommaire, il faut faire un post-traitement sur la sortie HTML.

Une autre chose sympathique que je n’ai pas eu l’occasion d’utiliser concerne les templates Hugo au sein même des documents. Par exemple, un template image qui sort un code HTML avec caption + figure + image de la bonne taille + lien pour voir l’image d’origine. En gros, générer un truc bien casse pied à écrire :).

Et Octopress ?

Bon Hugo c’est bon pour moi, mais j’ai rapidement fait un tour sur Octopress entre deux. Pour tout dire, j’ai rapidement abandonné. Le plugin le plus intéressant pour moi est Codeblock et il ne fonctionne pas comme indiqué. J’ai regardé les sources et finalement renoncé.

Au passage, je remarque que le projet n’est plus maintenu depuis plusieurs années et qu’il se base sur Jekyll. J’essaye ce dernier et me retrouve avec des problèmes de dépendances et des packageurs – il y en a pas qu’un – qui demandent les droits root pour l’installation. Las, j’abandonne. Finalement, Hugo c’est bien.

Pour finir

J’ai beaucoup touché au template de Hugo, aussi bien la partie CSS que HTML en me basant sur un des thèmes disponibles. À la base je voulais un thème sombre, mais j’ai finalement adopté un thème clair pour le contenu. Premièrement parce que le thème choisi l’est de base, deuxièmement parce que je trouve le résultat peu satisfaisant. Toutefois, le thème sombre est disponible en le sélectionnant dans le menu du navigateur: Vue -> Style de page -> Night theme (sur firefox, cela varie peut-être sur d’autres navigateurs). À terme, je pense chavirer du côté obscur.

La plupart des morceaux modifiés concernent des éritants que je rencontre sur certains sites et logiciels. J’ai essayé de faire quelque chose d’accessible et de pratique (là je vous vends un objet rare et de grande valeur :D). Du coup, le prochain article y sera consacré. Ça va me changer du c++ et de la méta-programmation.

Et parce que les habitudes ont la vie dure, l’article qui suivra sera dédié au dispatcheur d’un std::variant. La méta-prog, on ne la quitte que les pieds devant :o).

En même temps, les articles de l’ancien blog seront déportés et mis à jour si besoin.

Minimiser les copies dans operator+

Article suivant: De Blogspot à Hugo, il a changé de peau
Article précédent: Comment se passer de std::forward

Je vais me baser sur un classique: une classe de matrice contenant un std::vector<int> . Cette classe va implémenter 2 opérateurs mathématiques: + et += . Le premier en fonction libre, le second en fonction membre.

Pour rigoler un peu, on ajoute une petite contrainte qui est « l’efficacité ». Petit mot qui englobe un peu tout et n’importe quoi tel que la performance en mémoire et en temps.

À vrai dire, il y a énormément de choses possibles rien que sur la structure du code: instruction vectorisée, alignement mémoire, expression template, etc. Des bibliothèques comme uBLAS, Eigen, Blitz implémentent une tripotée de choses. Ici, on va uniquement s’intéresser à la manière d’implémenter operator+ pour recycler les variables temporaires dans le but d’avoir le moins d’allocations possibles dûes aux copies.

Grosso-modo, des rvalues à droite, des rvalues à gauche, des rvalues partout et pour finir, pas de rvalue.

En réalité, il y a plusieurs approches possibles que je mets ici en opposition sans qu’elles le soient réellement.

  1. une surcharge pour tous les prototypes possibles.
  2. un opérator unique pour les gouverner tous.

Plein de surcharges de operator+

Faire 4 prototypes pour distinguer les rvalues des lvalues est un choix assez naturel. Si un prototype contient une rvalue, alors il y a moyen de recycler une valeur. On pourrait même ajouter noexcept sur de tels prototypes.

Voici ce que donne l’implémentation:

Matrix operator+(Matrix const& lhs, Matrix const& rhs)
{
  Matrix ret {lhs};
  ret += rhs;
  return ret; // et non pas return `ret += rhs`, ce qui empêcherait la NRVO.
}

Matrix operator+(Matrix&& lhs, Matrix const& rhs)
{
  lhs += rhs;
  return std::move(lhs); // ne pas oublier std::move, sinon il y a aura copie en sortie
}

Matrix operator+(Matrix const& lhs, Matrix&& rhs)
{
  rhs += lhs; // commutativité: x+y = y+x
  return std::move(rhs);
}

Matrix operator+(Matrix&& lhs, Matrix&& rhs)
{
  rhs += lhs; // éventuellement `rhs += std::move(lhs)`
  return std::move(rhs);
}

Petite note sur la dernière implémentation. Utiliser rhs comme valeur de retour permet de gagner un mov (asm). ici.

Bon, c’est bien joli, mais on peut quasiment faire la même avec seulement 2 prototypes. Seulement, pour une raison que j’ignore, ni clang, ni gcc n’applique la RVO correctement. Le constructeur de déplacement est systèmatiquement utilisé.

Matrix operator+(Matrix lhs, Matrix const& rhs)
{
  lhs += rhs;
  return lhs; // pas de RVO ???
}

Matrix operator+(Matrix const& lhs, Matrix&& rhs)
{
  rhs += lhs; // commutativité: x+y = y+x
  return std::move(rhs);
}

Les prototypes ne sont pas symétriques pour éviter les ambiguïtés. Le prototype prenant un paramètre par copie sera moins prioritaire que celui avec une rvalue, mais il accepte toutes les formes de référence.

Ainsi, si dans l’expression a + b , b une rvalue, la seconde fonction sera utilisée. Dans les autres cas, la première fonction sera utilisée. On peut facilement vérifier quelle expression correspond à quelle fonction avec un std::cout << __PRETTY_FUNCTION__ << '\n' dans les implémentations et le test qui suit.

template<class Lhs, class Rhs>
void test()
{
  std::cout << "Matrix " << (std::is_const<Lhs>{} ? "const" : "     ") << " a; ";
  std::cout << "Matrix " << (std::is_const<Rhs>{} ? "const" : "     ") << " b;\n\n";

  Lhs a;
  Rhs b;

  std::cout << std::left;
  #define C(a,b) std::cout << std::setw(13) << #a << "+ " << std::setw(15) << #b; a+b
  C(a,            b);
  C(a,            std::move(b));
  C(std::move(a), b);
  C(std::move(a), std::move(b));
  #undef C
}

int main()
{
  test<      Matrix,       Matrix>(); std::cout << "\n\n";
  test<      Matrix, const Matrix>(); std::cout << "\n\n";
  test<const Matrix,       Matrix>(); std::cout << "\n\n";
  test<const Matrix, const Matrix>();
}

Résultat:

Matrix       a; Matrix       b;

a            + b              Matrix operator+(Matrix, const Matrix&)
a            + std::move(b)   Matrix operator+(const Matrix&, Matrix&&)
std::move(a) + b              Matrix operator+(Matrix, const Matrix&)
std::move(a) + std::move(b)   Matrix operator+(const Matrix&, Matrix&&)


Matrix       a; Matrix const b;

a            + b              Matrix operator+(Matrix, const Matrix&)
a            + std::move(b)   Matrix operator+(Matrix, const Matrix&)
std::move(a) + b              Matrix operator+(Matrix, const Matrix&)
std::move(a) + std::move(b)   Matrix operator+(Matrix, const Matrix&)


Matrix const a; Matrix       b;

a            + b              Matrix operator+(Matrix, const Matrix&)
a            + std::move(b)   Matrix operator+(const Matrix&, Matrix&&)
std::move(a) + b              Matrix operator+(Matrix, const Matrix&)
std::move(a) + std::move(b)   Matrix operator+(const Matrix&, Matrix&&)


Matrix const a; Matrix const b;

a            + b              Matrix operator+(Matrix, const Matrix&)
a            + std::move(b)   Matrix operator+(Matrix, const Matrix&)
std::move(a) + b              Matrix operator+(Matrix, const Matrix&)
std::move(a) + std::move(b)   Matrix operator+(Matrix, const Matrix&)

Si on y tient vraiment, on peut ajouter Matrix operator+(Matrix&&, Matrix&&) . Mais comme dit précédemment le besoin est très faible.

Un prototype multi-fonction

Une autre solution pour la surcharge d’opérateur est de ne faire qu’un seul et unique prototype template qui s’active en présence d’un certain type. Ce n’est pas une approche opposée à la précédente (elle peut servir de complément), mais je vais présenter ici comment le faire avec seulement un prototype.

Pour filtrer les types compatibles, on va utiliser la bonne vieille méthode à base de std::enable_if . Ce qui donne:

template<class MatrixLhs, class MatrixRhs>
std::enable_if_t<
  std::is_same<std::decay_t<MatrixLhs>, Matrix>::value &&
  std::is_same<std::decay_t<MatrixRhs>, Matrix>::value,
  Matrix>
operator+(MatrixLhs&& lhs, MatrixRhs&& rhs);

Dans la réalité, l’addition d’une matrice fonctionne aussi sur des entiers (cf: int + Matrix , Matrix + int ). Le filtre sera alors beaucoup plus compliqué puisqu’il faut qu’au moins une des opérandes soit un type Matrix et que les paramètres soient des types compatibles (en prenant en compte la présence des références et des const). La condition devient alors quelque chose comme:

is_matrix_operand<Lhs> &&
is_matrix_operand<Rhs> &&
(is_matrix<Lhs> || is_matrix<Rhs>)

Il devient alors très facile d’ajouter un nouveau type à prendre en compte, comme par exemple un conteneur de la SL, un tableau C, un autre type matriciel d’une autre bibliothèque, etc. Faire comme dans le premier chapitre avec un prototype pour chaque cas devient vite infernal.

Il est également envisageable de faire des prototypes par catégorie de variable: Sequence et Matrix, Integer et Matrix.

Revenons-en à notre operator+ et son implémentation. Celle-ci va être plus compliqué car elle doit être équivalente aux 4 implémentations du début ; sachant que la première possède une variable et les opérandes sont inversés dans la troisième et la quatrième.

Une solution possible est de mettre 2 valeurs intermédiaires qui représentent l’opérande de gauche et l’opérande de droite et dont le type s’adapte en fonction des types en entrée.

Ci-dessous un tableau récapitulatif des types et valeurs de nos 2 nouvelles variables Lhs et Rhs. Les const sont supprimés car seule la référence importe.

Prototype NewLhs NewRhs
M & , M & M = lhs M & = rhs
M && , M & M && = lhs M & = rhs
M & , M && M && = rhs M & = lhs
M && , M && M && = rhs M && = lhs

Et l’implémentation:

template<class T>
struct rvalue_wrapper
{
  T& value;

  operator T&& () const noexcept
  { return static_cast<T&&>(value); }
};

template<class T>
T&& unwrap(rvalue_wrapper<T> x) noexcept
{
  return x;
}

template<class T>
T&& unwrap(T&& x) noexcept
{
  return std::forward<T>(x);
}

template<class Lhs, class Rhs>
Matrix operator +(Lhs&& lhs, Rhs&& rhs)
{
  using NewLhs = std::conditional_t<
    std::is_lvalue_reference<Lhs>::value &&
    std::is_lvalue_reference<Rhs>::value,
    Matrix,
    rvalue_wrapper<Matrix>>;

  using NewRhs = std::conditional_t<
    !std::is_lvalue_reference<Lhs>::value &&
    !std::is_lvalue_reference<Rhs>::value,
    Matrix&,
    Matrix&&>;

  constexpr bool swap_arg = !std::is_lvalue_reference<Rhs>::value;

  NewLhs new_lhs{const_cast<Matrix&>(swap_arg ? rhs : lhs)};
  NewRhs new_rhs{static_cast<NewRhs>(const_cast<Matrix&>(swap_arg ? lhs : rhs))};

  unwrap(new_lhs) += static_cast<NewRhs>(new_rhs);

  return new_lhs;
}

Le code mérite quelques explications. Pour commencer, parlons de rvalue_reference qui est un palliatif pour une optimisation au niveau de return . Au niveau du retour, si NewLhs est une rvalue, il faut utiliser std::move , sauf que l’utiliser sur une variable locale à la fonction bloque le RVO. Hélas, même avec un if (std::is_rvalue_reference<NewLhs>{}) return std::move(lhs); avant return new_lhs l’optimisation n’est pas faite. Cela fonctionne néanmoins avec if constexpr de c++17. Le but de rvalue_reference est finalement de rendre automatique un retour par rvalue grâce à l’opérateur de cast interne.

Concernant ce curieux enchaînement de cast, celui-ci s’explique par la difficulté de contrôler le type retourné par une ternaire. Une ternaire sur deux variables de même type va retourner une référence (une variable est toujours une lvalue). La référence sera considérée constante si une des deux valeurs est une référence constante. Du coup, on vire le const pour ensuite construire les types NewLhs et NewRhs.

Ici, le constructeur de la matrice (quand NewLhs = Matrix) va recevoir un type non const. À moins qu’un constructeur existe pour les références non const, cela ne cause pas de problème. On peut très bien ajouter un std::conditional pour forcer le const.

En première impression static_cast<NewRhs> pourrait être optionnel, mais celui-ci permet de forcer la rvalue pour construire NewRhs. Une lvalue (le retour de const_cast<Matrix&> ) ne pouvant être affectée à une rvalue sans cela.

Les casts présents fonctionnent bien parce que lhs et rhs sont tous deux du même type. Dans le cas contraire, il faut faire un branchement à la compilation via de la surcharge de fonction (dispatch de type) tel que font falcon::cif ou boost::hana::if_ . Plusieurs de mes articles en parlent.

N’écrivez pas operator+ vous-même, c’est trop compliqué !

Sérieusement, qui veut écrire une 20taine de lignes pour chaque opérateur ? Ne le faites pas, le code est alourdi, la lisibilité réduite. Il y a moyen d’implémenter la plupart des opérateurs en quelques lignes pour le même résultat.

De plus, l’implémentation des opérateurs peuvent varier. Par exemple, pas de commutativité. Ses variantes sont difficiles à détecter dans une grande masse de code, il devient facile de faire une erreur aussi bien à l’écriture qu’à la lecture.

Autre point, les types des opérandes peuvent être nombreux, faire tous les prototypes necessaires vous vaudra des heures de souffrances :).

Du coup, comment faire ? Une solution facile est d’utiliser une macro pour implémenter les opérateurs voulus. C’est simple et rapide, mais l’utiliser avec des types template est un peu délicat. Cela reste néanmoins la solution la plus simple.

Une autre manière passe par du CRTP pour que la classe de base implémente les opérateurs voulus sous forme de fonction amie. C’est la solution de boost/operators.hpp. Malheureusement, elle ne prend pas en compte les optimisations possibles sur les rvalues écrits dans cet article. Il faut la ré-écrire.

La dernière solution consiste à se servir des traits pour activer ou non certains prototypes comme dans le chapitre précédent. Une mise en oeuvre poussée peut être extrêmement extensible et s’adapte très facilement aux catégories de valeur (séquence, intégrale), mais c’est un poil complexe à mettre en place. Je ne connais pas de bibliothèque qui le fasse.

Au final, il n’existe actuellement pas d’outil satisfaisant pour générer les opérateurs alors qu’il est presque aussi rapide d’écrire une lib ou des macros pour le faire. Le temps perdu sera largement compensé par le nombre d’opérateurs à implémenter par la suite. Avec un peu de jugeote, il est même possible de mutualiser l’écriture des opérateurs @=. Pensez-y la prochaine fois qu’il faudra écrire des opérateurs ;).

Revenir en haut