Journal Constexpr versus template

Posté par Julien Jorge (site web personnel) le 23 avril 2021 à 13:57. Licence CC By‑SA.

Étiquettes : aucune

avr.

2021

Bonjour 'nal,

J'étais tranquille, en train de m'occuper de mes propres affaires, quand soudain je me suis demandé si l'utilisation de constexpr introduit dans C++11 pouvait réduire les temps de compilation par rapport à la méthode précédente de la métaprogrammation via des templates.

Pour rappel, l'idée de constexpr est d'indiquer au compilateur que la fonction ou variable concernée peut être calculée à la compilation si tous ses paramètres sont connus, et doit être calculée ainsi si elle apparaît dans un contexte d'expression constante (par exemple un paramètre de template).

Prenons cette chouette fonction pour illustrer :

// Calcule n en additionnant des 1 n fois.
// CC-BY-SA-NC-ND, patent pending.
unsigned count(unsigned n)
{
  return (n == 0) ? 0 : 1 + count(n - 1);
}

Si je voulais utiliser cette fonction dans un contexte où une constante de compilation est nécessaire, en C++98 je ne pourrais pas:

// count() est compilée et évaluée à l'exécution, ce qui est une
// erreur: les tableaux de taille variable ne sont pas conformes
// au standard.
int array[count(24)];

Pour contourner cela une solution est faire le calcul dans un type, via de la métaprogrammation avec templates:

template<unsigned N>
struct count_t;

// le cas d'arrêt
template<>
struct count_t<0>
{
  enum { value = 0 };
};

// le calcul récursif pour le cas général.
template<unsigned N>
struct count_t
{
  enum
    {
      value = 1 + count_t<N - 1>::value
    };
};

Et là tu vas me dire que c'est pas très DRY. Je me retrouve avec deux implémentations du même calcul, l'un est pour être effectué à la compilation et l'autre à l'exécution. Cela ne serait-il pas mieux si la même implémentation pouvait être utilisée pour les deux cas ?

constexpr enters the chat.

En C++11 il suffit de déclarer la fonction avec le mot clé constexpr pour qu'elle soit utilisable à la compilation (en gros hein, je simplifie pour l'exemple) :

constexpr int count(unsigned n)
{
  return (n == 0) ? 0 : 1 + count(n - 1);
}

void foo()
{
  // Pouf ! Ça marche.
  int array[count(24)];
}

Accessoirement il me semble que cette possibilité a aussi l'avantage de contourner la limite d'instanciations récursives des templates imposée par le compilateur.

Revenons à l'interrogation initiale. Tu n'es pas sans ignorer que la métaprogrammation à base de templates met à genoux les compilateurs. C'est la 3è plus grosse consommation d'électricité et plus gros producteur de CO2 depuis 1876. Est-ce que la version constexpr est aussi coûteuse ?

Pour comparer tout ça j'ai lancé la compilation des exemples ci-dessus en boucle, de 50 à 500 fois, et j'ai mesuré le temps que prenait la boucle, en secondes. Le tout avec G++ 9.3. Au final ça donne ça:

# nombre de compilations, templates (s.), constexpr (s.)
50,                       1.193,          0.596
100,                      2.218,          1.252
150,                      3.449,          1.763
200,                      4.628,          2.358
250,                      5.975,          2.984
300,                      7.022,          3.484
350,                      8.067,          4.132
400,                      9.237,          4.870
450,                      10.300,         5.344
500,                      11.410,         5.835

Voilà, ça compile à peu près deux fois plus rapidement en utilisant la version constexpr que la version templates. À titre de comparaison, compiler 500 fois un fichier vide prend environ 4 secondes.

# Belle exemple du gain en lisibilité

Posté par G.bleu (site web personnel) le 23 avril 2021 à 15:31. Évalué à 3.

C'est la 3è plus grosse consommation d'électricité et plus gros producteur de CO2 depuis 1876

J'imagine que les deux premiers c'est les réseaux Bitcoin et Ethereum ;-p

Plus sérieusement, ton exemple est très bon pour illustrer le gain en lisibilité qu'apporte constexpr sur un cas concret.
Personnellement, l'utilisation de templates récursifs m'ont toujours paru à la limite de l'exploit et de l'exploit ;-)
- [^] # Re: Belle exemple du gain en lisibilité
  
  Posté par SChauveau le 23 avril 2021 à 16:44. Évalué à 4.
  
  A mon avis les 2 premiers sont plutôt
  (1) le Porno
  (2) la NSA qui surveille pour savoir qui regarde (1)
- [^] # Re: Belle exemple du gain en lisibilité
  
  Posté par Gil Cot ✔ (site web personnel, Mastodon) le 23 avril 2021 à 17:54. Évalué à 1.
  
  Il a dit que le premier est cinq cents fichiers vides et le second template.
  (okay, je sors, je courses en ouikinde)
  
  “It is seldom that liberty of any kind is lost all at once.” ― David Hume
- [^] # Re: Belle exemple du gain en lisibilité
  
  Posté par David Delassus (site web personnel) le 26 avril 2021 à 00:22. Évalué à 2.
  
  Faut pas oublier npm qui essaye de résoudre des dépendances, et rust qui essaye de vérifier la memory-safety de ton programme :)
  
  https://link-society.com - https://kubirds.com - https://github.com/link-society/flowg

# Pas si simple.

Posté par SChauveau le 23 avril 2021 à 16:07. Évalué à 10.

j'ai modifié ton code en changeant 24 en 800 et aussi en répétant la définition du tableau 100 fois (dans des scopes séparés).

Pour 100 compilations, la version constexpr prend 17.2s contre seulement 2.8s pour les template.

En doublant le nombre de définition des tableaux, le temps de compilation avec constexpr double quasiment (33.3s) alors que template ne change quasiment pas (3.0s).

Mon explication est que, dans la version template, la quasi totalité du temps se passe lors de la 1ere instanciation (donc les 800 classes count_t, count_t, …). Pour les 99 tableaux restants, le coût est minimal car le compilateur possède déjà la classe count_t dans sa table des symboles.

Au contraire la version constexpr doit réévaluer count(800) à chaque apparition.

#define P 800

#if 1

constexpr int count(unsigned n)
{
  return (n == 0) ? 0 : 1 + count(n - 1);
}

#define N count(P)
#else
template<unsigned N>
struct count_t;

// le cas d'arrêt
template<>
struct count_t<0>
{
  enum { value = 0 };
};

// le calcul récursif pour le cas général.
template<unsigned N>
struct count_t
{
  enum
    {
      value = 1 + count_t<N - 1>::value
    };
};
#define N count_t<P>::value 
#endif

void foo()
{
  // Pouf ! Ça marche.
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }

  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }

  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }

  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }

  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }

  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }

  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }

  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }

  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }

  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }

   { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }

  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }

  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }

  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }

  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }

  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }

  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }

  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }

  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }

  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
  { int array[N]; }
}

[^] # Re: Pas si simple.

Posté par SChauveau le 23 avril 2021 à 16:10. Évalué à 2.

Le formatage a fait sauter quelques caractères. Il fallait lire:

Mon explication est que, dans la version template, la quasi totalité du temps se passe lors de la 1ere instanciation (donc les 800 classes count_t<800>, count_t<799>, …). Pour les 99 tableaux restants, le coût est minimal car le compilateur possède déjà la classe count_t<800> dans sa table des symboles.
- [^] # Re: Pas si simple.
  
  Posté par Julien Jorge (site web personnel) le 23 avril 2021 à 16:38. Évalué à 2.
  
  Bien vu ! Le fait que le coût n'impacte que la première instanciation des templates fait sens, j'aurais dû y penser :)
  - [^] # Re: Pas si simple.
    
    Posté par SChauveau le 23 avril 2021 à 16:52. Évalué à 2.
    On peut probablement avoir le beurre et l'argent du beurre en encapsulant la fonction constexpr dans une template. Et potentiellement avec une autre fonction constexpr par dessus pour garder une syntaxe lisible:
```
constexpr int count_impl(unsigned n)
{
  return (n == 0) ? 0 : 1 + count_impl(n - 1);
}

template<unsigned N>
struct count_t
{
  enum { value = count_impl(N)};
};

constexpr int count(unsigned n) { return count_t<N>::value }
```
    Dans ce cas, la classe sert en quelque sorte de cache.
    - [^] # Re: Pas si simple.
      
      Posté par Gil Cot ✔ (site web personnel, Mastodon) le 23 avril 2021 à 17:56. Évalué à 1.
      
      ouch c'est moins évident les poupées russes
      
      “It is seldom that liberty of any kind is lost all at once.” ― David Hume
  - [^] # Re: Pas si simple.
    
    Posté par serge_sans_paille (site web personnel) le 23 avril 2021 à 20:41. Évalué à 2.
    
    On pourrait imaginer que le compilo mémoise l'appel à la fonction constexpr - j'imagine que c'est valable et on retomberait sur nos pattes :-)
    
    Chouette article, sur le fond et la forme c'est un plaisir à lire !
    - [^] # Re: Pas si simple.
      
      Posté par SChauveau le 23 avril 2021 à 21:55. Évalué à 2.
      
      C'est possible mais cela pourrait coûter très cher car les fonctions constexpr peuvent contenir des boucles. Il n'y a donc pas de limite théorique au nombre d'appels de fonctions constexpr lors de l'évaluation d'une seule expression.
      
      A ce propos, j'ai utilisé 800 dans mon code car g++ refusait de compiler avec 1000. Erreur 'too many recursive templates' ou quelque chose dans le genre.
      - [^] # Re: Pas si simple.
        
        Posté par Julien Jorge (site web personnel) le 24 avril 2021 à 07:33. Évalué à 2.
        
        De souvenir, la limite d'instantiations récursives de template est à 900 par défaut dans g++. Il y a une option de compilation pour la changer.
        
        Un commentaire sur Reddit sur ces sujets de métaprogrammation fait référence à https://github.com/tcbrindle/raytracer.hpp où il est question de memoïsation des évaluations des constexpr dans gcc. Je ne sais pas si ça a été implémenté finalement ; ça irait à l'encontre de tes résultats, il y a peut-être autre chose en jeu.
        
        J'y apprends aussi que clang a une limite sur le nombre d'évaluations de constexpr.
- [^] # Re: Pas si simple.
  
  Posté par Arthapz le 25 avril 2021 à 18:11. Évalué à 1.
  
  Je me demande si avec consteval du C++20 ça change quelque chose
[^] # Re: Pas si simple.

Posté par corentin38 (site web personnel) le 24 avril 2021 à 10:55. Évalué à 2.
L'article est super intéressant et les commentaires tout autant ! Merci ! Mais …

les 800 classes count_t, count_t, …

Je me demande quand même à quel moment quelqu'un s'est dit que ce serait une bonne idée !

Et j'ai repéré ça, aussi :
```
   { int array[N]; }
  { int array[N]; }
```
SChauveau, ce petit écart d'indentation me fait craindre le pire. Tu n'as pas tout tapé à la main, n'est-ce pas ? Sinon, pour que la comparaison tienne, il faut inclure le temps de rédaction du programme au benchmark !
- [^] # Re: Pas si simple.
  
  Posté par SChauveau le 24 avril 2021 à 13:35. Évalué à 2.
  
  Je n'aime pas trop le terme mais pour faire simple je suis un "expert" en compilation (doctorat en informatique + 20 ans à travailler dans le domaine). Quand je vois un article comme celui ci, je n'ai donc pas trop de difficultés à imaginer les implémentations possibles avec leur avantages et inconvénients.
  
  Concernant l'indentation. Elle apparaît au milieu donc cela s'est probablement produit quand j'ai fait le gros copier-coller pour passer de 100 à 200 tableaux.

# et avec les fold-expressions ?

Posté par nokomprendo (site web personnel) le 23 avril 2021 à 16:20. Évalué à 4.
depuis c++17, on a les fold-expressions aussi:
```
template <int ... N>
struct count2 {
    static const int value = (0 + ... + N); 
};

int array2[count2<24>::value];
```
Et il me semble que les templates font de la mémoization donc s'il y a beaucoup d'appels différents, ça peut changer les choses.

Par contre le constexpr a l'avantage de pouvoir être appelé au runtime aussi, je crois.
- [^] # Re: et avec les fold-expressions ?
  
  Posté par SChauveau le 23 avril 2021 à 16:37. Évalué à 4.
  
  Cela fait pas mal de temps que je n'ai pas utilisé les fold-expressions mais je ne pense pas que cela fonctionne comme tu le propose ici. C'est une sorte de vararg donc pour count2<24>, l'expression 0+...+N est en fait équivalent à 0+24. Pour obtenir la somme demandée il te faudrait explicitement indiquer tout les membres de la somme: count2<1,2,3,4,5,6, etc ,24>
  - [^] # Re: et avec les fold-expressions ?
    
    Posté par nokomprendo (site web personnel) le 23 avril 2021 à 16:55. Évalué à 2.
    
    Ah oui c'est possible, j'ai pas trop réfléchi en fait, désolé…
    - [^] # Re: et avec les fold-expressions ?
      
      Posté par SChauveau le 23 avril 2021 à 17:11. Évalué à 2. Dernière modification le 23 avril 2021 à 17:11.
      La confusion est facile à faire. Certains langages utilisent effectivement .. ou … comme opérateurs d'intervalle. Par exemple en Bash
      
      # echo {3..11} 3 4 5 6 7 8 9 10 11
- [^] # Re: et avec les fold-expressions ?
  
  Posté par Clément V le 23 avril 2021 à 23:25. Évalué à 4.
  Comme l'a fait remarquer SChauveau, les fold-expressions utilisent des packs. Il faut donc en créer un, par exemple avec make_integer_sequence :
```
template <typename T>
struct count_impl;

template <int... Ints>
struct count_impl<std::integer_sequence<int, Ints...>>
{
    static constexpr int value = (0 + ... + Ints); 
};

template <int N>
constexpr int count = count_impl<std::make_integer_sequence<int, N+1>>::value;
```
  Mais ça utilise des templates avec plein de paramètres, sûrement très lourds. Alors qu'on pourrait simplement utiliser une boucle for.
```
template <int N>
constexpr int count = [](){
    int s = 0;
    for (int i = 1; i <= N; i++)
        s += i;
    return s;
}();
```
  Mais je n'ai pas fait de benchmarks pour comparer, peut-être que je me trompe.
  - [^] # Re: et avec les fold-expressions ?
    
    Posté par Clément V le 24 avril 2021 à 11:54. Évalué à 3.
    Je tente un petit benchmark vite fait, et au passage je compare aussi variable template vs. fonction.
```
#include <utility>

#ifdef USE_TEMPLATE
template <int N>
constexpr int count = [](){
    int s = 0;
    for (int i = 1; i <= N; ++i)
        s += i;
    return s;
}();
#define COUNT(n) count<n>
#elif USE_FUNCTION
constexpr int count(int n) {
    int s = 0;
    for (int i = 1; i <= n; ++i)
        s += i;
    return s;
}
#define COUNT(n) count(n)
#elif USE_FOLD
template <typename T>
struct count_impl;

template <int... Ints>
struct count_impl<std::integer_sequence<int, Ints...>>
{
    static constexpr int value = (0 + ... + Ints);
};

template <int N>
constexpr int count = count_impl<std::make_integer_sequence<int, N+1>>::value;

#define COUNT(n) count<n>
#endif

int main() {
    { int array[COUNT(1)]; }
    // ...
}
```
    Je crée des tableaux de taille COUNT(1) jusqu'à COUNT(800), puis 1000 de plus avec COUNT(100). J'utilise g++ 11.0.1 et clang++ 12.0.0. Les temps sont des moyennes pifométriques calculées après quelques essais.
    - g++: TEMPLATE → 530ms, FUNCTION → 450ms, FOLD → 15s
    - clang++: TEMPLATE → 540ms, FUNCTION → 600ms, FOLD → instantiating fold expression with 257 arguments exceeded expression nesting limit of 256
    Ce genre d'utilisations de fold expressions est clairement une mauvaise idée. Entre variable et fonction, la différence est moins nette et dépend du compilateur, donc pas de vainqueur.
    - [^] # Re: et avec les fold-expressions ?
      
      Posté par Julien Jorge (site web personnel) le 24 avril 2021 à 19:47. Évalué à 4.
      
      Je ne suis pas sûr que ce soit judicieux de mettre les folds dans la comparaison. Autant je m'attends à pouvoir convertir en fonction constexpr n'importe quel calcul fait via des templates, autant je doute que n'importe lequel de ces calculs puisse être converti en fold expression. Du coup les approches ne sont pas vraiment comparables :)

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.