Comparaison de différentes implémentations de mp_index_of
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
xet_et - ceux sur des suites
xeti<n>avecnun entier.
Pour chaque test, T représente x et il peut être présent ou non dans Ts.
les valeurs de Ts sont présentées dans les légendes sous forme abrégée:
[x*500]: une liste de 500x.[_*250, x, _*249]: une liste de 250_, suivit dexet d’une liste de249_.[i{0..40}*150]: une suite de 150i0, une autre de 150i1et ainsi de suite jusqu’ài40.[i0..i{0..140}]: une suite[i0..i0], puis[i0..i1], etc jusqu’à[i0..i140].[i{0..n},x,i{n-(n..0)..n}];n=100: les suites[i{0..100},x,i{100..100}],[i{1..100},x,i{99..100}], etc
Les sources se trouvent sur github dans un même fichier cpp. Chacune des implémentations possède son propre namespace et des macros activent individuellement chaque test.
Relation temps de compilation et mémoire
Dans du code utilisant la méta-programmation, le temps de compilation suit la même courbe que la mémoire. Plus une compilation est lente, plus la mémoire utilisée augmente allant jusqu’à saturation.
Et la mémoire est fortement liée au nombre de types instanciés par le compilateur. Ici, il ne faut pas voir une instance comme une variable, mais comme la première création d’un type. Par exemple, index_of<int, int> est une instance de type (ou d’alias), index_of<int, int, int> une seconde instance, index_of<int, float> une troisième, etc. Chaque type construit s’ajoute dans la mémoire du compilateur et l’ensemble utilise de plus en plus de place. C’est ainsi que le compilateur implémente naturellement la mémoïsation pour les templates.
Pour réduire le temps de compilation, il faut donc réduire le nombre de type instancié.
La récursivité
La première chose qu’on apprend avec les variadiques, c’est que les boucles se font avec de la récursivité en enlevant un par un les éléments. C’est une forme facile à écrire et à comprendre, mais qui crée beaucoup de types intermédiaires à l’intérieur du compilateur.
namespace recursive_ternary
{
namespace detail
{
template<class T, class... Ts>
struct _index_of : std::integral_constant<int, 1>
{};
template<class T, class First, class... Rest>
struct _index_of<T, First, Rest...>
: std::integral_constant<int, std::is_same_v<T, First>
? 0 : _index_of<T, Rest...>::value + 1>
{};
}
template<class T, class... Ts>
using mp_index_of = std::integral_constant<int,
(detail::_index_of<T, Ts...>::value > sizeof...(Ts))
? -1 : detail::_index_of<T, Ts...>::value>;
}Une implémentation avec ternaire récursive comme on peut la trouver dans le fichier variant de libstdc++. Elle souffre d’un léger problème: il y a autant d’instance de _index_of que d’élément dans la liste, même si T se trouve en première position.
namespace recursive_indexed
{
namespace detail
{
template<int i, class T, class... Ts>
struct _index_of
: std::integral_constant<int, -1>
{};
template<int i, class T, class First, class... Rest>
struct _index_of<i, T, First, Rest...>
: _index_of<i+1, T, Rest...>
{};
template<int i, class T, class... Rest>
struct _index_of<i, T, T, Rest...>
: std::integral_constant<int, i>
{};
}
template<class T, class... Ts>
using mp_index_of = typename detail::_index_of<0, T, Ts...>::type;
}L’indice courant se trouve en paramètre template et la récursion s’arrête dès que T est trouvé. Seulement, l’ajout de l’indice en paramètre va dégrader la mémoïsation en créant plus de types que nécessaire.
namespace recursive
{
namespace detail
{
template<class T, class... Ts>
struct _index_of
: std::integral_constant<int, 1>
{};
template<class T, class First, class... Rest>
struct _index_of<T, First, Rest...>
: std::integral_constant<int, 1+_index_of<T, Rest...>::value>
{};
template<class T, class... Rest>
struct _index_of<T, T, Rest...>
: std::integral_constant<int, 0>
{};
}
template<class T, class... Ts>
using mp_index_of = std::integral_constant<int,
(detail::_index_of<T, Ts...>::value > sizeof...(Ts))
? -1 : detail::_index_of<T, Ts...>::value>;
}Un mélange des 2 implémentations précédentes sans les inconvénients. En réalité, c’est la forme la plus communément écrite.
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.
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>;
}
Là où la version récursive était rapide, la transformation en une liste de booléan l’est tout autant. Le bénéfice devient évident sur une grande variété de listes (test 4) et des listes homogènes (test 6) où le temps de compilation est divisé par 3.
L’algorithme recursive_bool2 spécialisé dans la recherche d’un std::true_type permet de grappiller encore quelques millisecondes principalement grâce à une spécialisation de template en moins.
À contrario, la version 3 qui manipule des booléens plutôt que des types est lente. Manipuler des types serait donc plus rapide que manipuler des valeurs dans les spécialisations. Le même comportement est présent dans Clang, même s’il est moins prononcé.
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>;
}
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.
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
pack8sont 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.
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.
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 ;).
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.
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 .