Journal Mémorisation partielle de fonction constexpr

Posté par serge_sans_paille (site web personnel) le 25 septembre 2018 à 16:09. Licence CC By‑SA.

Étiquettes :

sept.

2018

Demat'inal,

Dans la lignée des expériences C++ que j'essaie de partager ici, je vous soumets ce bout de code qui m'a bien amusé :

template<class F, class T, T... Vs>
struct memoized {
    auto operator()(T v) const
    {
        static constexpr frozen::map<T, decltype(F{}(v)), sizeof...(Vs)> cached = {{Vs, F{}(Vs)}...};
        auto where = cached.find(v);
        if(where != cached.end()) {
            return where->second;
        }
        return F{}(v);
    }
};

Il utilise la bibliothèque frozen qui fournit une version figée de quelques conteneurs standards. Un cas d'utilisation totalement abscons pourrait être

struct prime_sieve {
constexpr bool operator()(uint64_t v) {
  if(v%2 == 0 && v != 2) return false;
  for(uint64_t i = 3, n = isqrt(v); i < v; i +=2)
    if(v % i == 0) return false;
  return true;
}
};

#include <iostream>
int main(int argc, char** argv) {
  memoized<prime_sieve, uint64_t, 0,1,2,3,4,5,6,7,8,90> ps;
  std::cout << ps(7) << " " << ps(100) << "\n";
  return 0;
}

Que se passe-t-il donc ? Lors de la compilation, notre compilateur C++ préféré va initialisé la table cached qui est marquée constexpr. Pour chacune des valeurs données en paramètre, il va donc appeler la fonction et stocker la valeur de retour dans la frozen::map.

Puis à l'exécution, lors d'un appel de fonction, il va faire une recherche (rapide, frozen implémente une recherche dichotomique presque sans branchement qui tire partie de la connaissance de la taille du tableau) dans cette table, renvoyer la valeur si elle est en cache, et à défaut, exécuter la fonction d'origine.

Ça peut servir si, après mesure de performances, on se rend compte que certaines valeurs sont régulièrement utilisées.

Voilà, je trouve l'idée amusante, je m'en servirai lors de la présentation que je donne ¹ cet après midi à CppCon, c'est donc une sorte de contenu exclusif LinuxFR :-)

stress stress ↩

# Ça pique les yeux

Posté par AncalagonTotof le 25 septembre 2018 à 20:22. Évalué à 10.

C'est sympa de partager. Si, si, vraiment, malgré ce que je vais dire après …
J'ai jamais aimé les templates en C++, et je vis très bien sans. Ou avec une utilisation minimale (Qt par exemple, avec ses collections, ses QStringList, etc).
Je trouve que les avantages apportés sont contrebalancés par une trop grande quantité d'injure du compilateur à la moindre coquille, mais aussi par une perte sensible de la lisibilité du code.
Là, j'ai rien pigé, je ne sais pas par quel bout le prendre.
Mon rêve de devenir gourou C++ s'effondre. Nan, s'est effondré il y a longtemps …
- [^] # Re: Ça pique les yeux
  
  Posté par serge_sans_paille (site web personnel) le 25 septembre 2018 à 20:41. Évalué à 7. Dernière modification le 25 septembre 2018 à 20:41.
  
  Si ça peut te rassurer, ou à défaut t'arracher un sourire, j'ai un sentiment similaire en assistant à CppCon. On est tous le noob de quelqu'un :-)
  - [^] # Re: Ça pique les yeux
    
    Posté par Lutin le 26 septembre 2018 à 13:30. Évalué à 10.
    
    À force de lire ce genre d'articles j'ai enlevé C++ de mon cv, au mieux je dis que je sais faire du C avec des classes.
    - [^] # Re: Ça pique les yeux
      
      Posté par Gabbro le 26 septembre 2018 à 16:10. Évalué à 10.
      
      Le simple fait de savoir que ces trucs incompréhensibles existent ne te classe-t-il pourtant pas dans la moitié des meilleurs développeurs C++ ?
- [^] # Re: Ça pique les yeux
  
  Posté par arnaudus le 26 septembre 2018 à 09:20. Évalué à 10.
  
  À mon avis, il faut voir les templates pour ce qu'ils sont : des outils au service des développeurs de bibliothèques. Si tu regardes le main, la syntaxe n'est pas trop affreuse.
  
  Par contre, j'avoue que j'ai vraiment un doute sur cette tendance à remplacer le polymorphisme par la programmation générique. Bon, c'est toujours un peu compliqué de reprocher aux développeurs de chercher le gain de performance, mais le coût associé est, à mon avis, terrifiant. Pensez par exemple aux logiciels libres : de combien de contributeurs potentiels se prive-t-on avec un code truffé de variadic templates qui s'apparentent au brainfuck? Ça n'est même pas un problème de lisibilité, c'est avant tout un problème d'abstraction, de syntaxe obscure, et de normes tarabiscotées, qui transforment la méta-programmation en exercice complètement élitiste, réservé aux professionnels du domaine. C'est quasiment un autre langage, en fait.
  - [^] # Re: Ça pique les yeux
    
    Posté par robin le 26 septembre 2018 à 10:53. Évalué à 0. Dernière modification le 26 septembre 2018 à 10:53.
    
    C'était totalement vrai dans le passé, mais depuis C++17 les choses se sont très considérablement améliorées. L'utilisation des fonctions constexpr, notamment, aide énormément.
    
    bépo powered
    - [^] # Re: Ça pique les yeux
      
      Posté par arnaudus le 26 septembre 2018 à 15:19. Évalué à 10.
      Mouais…
      
      static constexpr frozen::map<T, decltype(F{}(v)), sizeof...(Vs)> cached = {{Vs, F{}(Vs)}...};
      
      Franchement, rien qu'à parser ça, c'est chaud. Il y a deux qualificateurs (static et constexpr), avec static qui est hautement polysémique en C++ et constexpr qui vient d'être introduit dans la norme. Ensuite, on a visiblement une map, à dimension ésotérique. Et ensuite, on a une syntaxe pour l'initialisation qui est hyper obscure. J'ai l'impression qu'avec un peu de doc, je pourrais m'en sortir avec une connaissance du C++ "normale". Par contre, il faut comprendre aussi ce que bien peut faire decltype(F{}(v)), sizeof...(Vs), et {{x}...}, et dans mon cerveau, c'est un gros "syntax error". Ça ne ressemble en fait même pas à un truc compilable, en fait. On est vraiment en présence d'un nouveau langage, mais ça ressemble autant que C++ que perl ressemble à java…
      - [^] # Re: Ça pique les yeux
        
        Posté par Gof (site web personnel) le 27 septembre 2018 à 09:06. Évalué à 5.
        
        et constexpr qui vient d'être introduit dans la norme.
        
        Euh, faut pas exagérer. Ça fait au moins 10 ans que constexpr fut introduit. (Le Working Draft ISO de 2008 le contiens déjà).
        C++11 n'est plus nouveau. C'est dépassé par plusieurs nouveau standards depuis.
        Pareil pour l'initialisation avec {}
        
        D'ailleurs, l'expression peut être simplifiée: Je pense que ceci devrai fonctionner.
        
        constexpr frozen::map cached = {{Vs, F{}(Vs)}...};
        
        À vérifier, mais le static me semble inutile ici puisque c'est une constexpr dont on ne prends pas l'addresse. (Ou alors le compilateur essaie-t-il quand même de recopier toute la map sur la stack?)
        Et en C++17, ont peu omettre les types du templates s'il peuvent être déduits via des guide de déduction.
        
        [^] # Re: Ça pique les yeux
        
        Posté par lasher le 05 octobre 2018 à 14:10. Évalué à 3.
        
        Je ne suis pas dev C++ (enfin, si, mais non). Je suis à fond pour C++11 et ses copains¹. Mais dans tous les cas je suis d'accord que (1) Tous ces nouveaux mots-clef et mécanismes sont utiles, mais que (2) ils n'en restent pas moins abscons pour quelqu'un d'un peu extérieur².
        
        Je rajouterais que, tout comme pour C (qui est toujours enseigné comme si C99 et C11 n'avaient jamais existé³), C++ reste la plupart du temps enseigné par des gens qui ne se mettent pas à jour en termes de normes. Et je ne parle même pas des gens qui enseignent le C++ en « premier langage » alors qu'en fait on parle plutôt de « C avec std::cout » (même si la POO tend à suivre ensuite).
        
        Du coup je veux bien que quelqu'un me parse la ligne initiale. :-) Mon C++ est très balbutiant car j'ai peu d'expérience avec mis à part certains mécanismes directement utiles pour mon boulot.
        
        Même si je trouve que l'évolution de C++98 à C++11 demande déjà beaucoup de boulot à ceux dont c'est pas le cœur de métier, alors quand j'ai vu C++17 et C++20, pfiou (C++14 étant une màj mineure je ne le compte pas comme étant une nuisance). Ça risque de faire beaucoup de boulot pour les développeurs « occasionnels » … et même les autres en fait. ↩
        
        On est Trolldi, je me permets : si après des lignes comme ça, on continue de faire chier avec Perl, je trouve qu'il y a un problème de paille et de poutre assez énorme. J'aime beaucoup Perl, et tout comme ceux qui disent qu'il s'agit de connaître les idiomes C++ en méta-programmation, ou les nouveaux idiomes en C++1x, je dis la même chose à propos de Perl, de ses constructions, ses variables implicites, etc. ↩
        
        Je plaide coupable pour le C d'ailleurs. J'essaie petit à petit de changer le contenu du cours pour permettre de moderniser le cours de mes collègues, mais c'est dur : il faut qu'ils valident – nous enseignons aux mêmes élèves et nous devons être synchro; et changer la structure du cours signifie changer celle des TD et TP, ce qui requiert pas mal de préparation. Du coup, le temps que le cours soit enfin adapté à C11, j'ai peur qu'on me dise que désormais on va tout faire en Python (discussion déjà abordée avec certains collègues récents…). ↩
    - [^] # Re: Ça pique les yeux
      
      Posté par Nicolas Boulay (site web personnel) le 27 septembre 2018 à 10:50. Évalué à 3. Dernière modification le 27 septembre 2018 à 10:50.
      
      C'est très chaud quand même. Les templates ne sont que de la propagation de constante explicite, non ? Si on ajoute les conteneurs dans la propagation de constante (ce que je n'ai pas encore vu dans un langage de programmation), qu'est-ce qui reste aux templates ?
      
      "La première sécurité est la liberté"
  - [^] # Re: Ça pique les yeux
    
    Posté par YBoy360 (site web personnel) le 26 septembre 2018 à 16:59. Évalué à 2.
    je suis pas persuadé que le gain en performance soit considérable quand on utilise des templates.
    
    Peut-être dans certaines catégorie d'applications, avec très peu de code et beaucoup de calculs, il y a un gain lié au fait que le compilateur génère du code plus "spécialisé", mais le comportement lié à l'utilisation des templates fait exploser la taille des librairies et le temps de compilation.
    
    Hors le volume du code instancié en mémoire à un impact très négatif sur les performances (et c'est très très chiant à optimiser).
    
    L'exemple cité dans ce journal montre un cache statique… C'est quand même plus lisible d'appeler la fonction sur les valeurs à la première utilisation (ou de la remplir au fil de l'eau en stockant le résultat). Il y a bien des façons d'initialiser un cache, quelle est la stratégie du compilateur? que change les options de compilation? Par exemple si j'écris 2 fois la ligne
```
memoized<prime_sieve, uint64_t, 0,1,2,3,4,5,6,7,8,90> ps1;
memoized<prime_sieve, uint64_t, 0,1,2,3,4,5,6,7,8,90> ps2;
```
    Est-ce qu'il va stocker 2 fois les résultats? Si ces lignes sont dans 2 librairies différentes, que ce passe t-il? (bien sûr qu'il va stocker 2 fois les résultats… )
    Et si le prime_sieve est dans une autre librairie, que ce passe t-il?
    
    En tout cas la syntaxe est impressionnante.
    - [^] # Re: Ça pique les yeux
      
      Posté par Clément V le 26 septembre 2018 à 18:13. Évalué à 6. Dernière modification le 26 septembre 2018 à 18:13.
      Par exemple si j'écris 2 fois la ligne
      
      memoized<prime_sieve, uint64_t, 0,1,2,3,4,5,6,7,8,90> ps1; memoized<prime_sieve, uint64_t, 0,1,2,3,4,5,6,7,8,90> ps2;
      
      Est-ce qu'il va stocker 2 fois les résultats? Si ces lignes sont dans 2 librairies différentes, que ce passe t-il? (bien sûr qu'il va stocker 2 fois les résultats… )
      
      Le cache est statique, c'est donc la même variable partagée par tous les appels à une même fonction. Dans le cas où les types memoized sont identiques, le cache n'est pas recalculé. Mais si les types sont différents, les fonctions sont différentes, et donc, même avec des valeurs communes, le cache est complètement recalculé :
      
      memoized<prime_sieve, uint64_t, 0,1,2,3,4,5,6,7,8,90> ps1; memoized<prime_sieve, uint64_t, 0,1,2,3,4,5,6,7,8,90,91> ps2;
      
      ne partagent pas le même cache.
    - [^] # Re: Ça pique les yeux
      
      Posté par arnaudus le 27 septembre 2018 à 13:33. Évalué à 4.
      
      je suis pas persuadé que le gain en performance soit considérable quand on utilise des templates.
      
      J'imagine que ça dépend du code, comme tu ne passes pas par une vtable, ça te fait sauter les indirections.
      
      Moi, c'est plus la béatification des calculs par le compilateur qui me fait douter. Attention, je ne prétends pas que ça n'est jamais utile, c'est juste qu'il y a tellement de manières plus ou moins élégantes de le faire, mais qui ont le mérite de ne pas brainfucker du code… Déja, tu peux très bien calculer tes trucs au runtime et stocker les résultats en mémoire si les calculs ne sont pas trop longs (de toutes manières, s'ils sont trop longs, ta compilation va durer quinze plombes, ça n'est pas intéressant non plus). Par ailleurs, si ce que tu veux c'est une grosse base de données sur des séries mathématiques (un million de décimales de pi, les nombres premiers entre 10 et 20 millions, etc), alors une solution équivalente serait de les calculer une fois et de les mettre dans un .h (éventuellement généré automatiquement lors de la compilation?). Si c'est quelque chose de plus spécifique à ton soft, c'est certainement tout à fait raisonnable de coller tes trucs dans un fichier ou une base de données et de lire dedans la première fois que tu en as besoin (typiquement, ouvertures aux échecs, etc). De toutes manières, il arrive forcément un moment où la recherche dans une bdd prendra plus de temps que de recalculer, donc c'est toujours un compromis.
      
      Ça ne retire en rien des capacités impressionnantes des dernières évolutions du C++, mais c'est juste que j'ai du mal à trouver ça exceptionnellement intéressant.
# C'est mieux si les paramètres sont inconnus lors de la compilation

Posté par Julien Jorge (site web personnel) le 26 septembre 2018 à 10:12. Évalué à 8.
Ma première réaction était « mais pourquoi met-il les résultats en cache alors que le compilateur va tout calculer à la compilation ? ». prime_sieve::operator()(uint64_t) est constexpr, du coup le compilateur peut l'exécuter pour les paramètres connus à la compilation. Autrement dit, ça fonctionne très bien sans memoized :
```
int main(int argc, char** argv) {
  prime_sieve ps;
  // les appels à ps(…) sont remplacés par le résultat dès la compilation.
  std::cout << ps(7) << " " << ps(100) << "\n";
  return 0;
}
```
En fait là où c'est très intéressant c'est quand les paramètres ne sont pas connus à la compilation. Dans ce cas memoized::operator() sera effectivement appelée au runtime et l'appel pourra profiter des valeurs qui auront été mises en cache à la compilation.

PS : je pense qu'il y a une typo dans la condition d'arrêt de ta boucle, i < v devrait être i < n, non ?
- [^] # Re: C'est mieux si les paramètres sont inconnus lors de la compilation
  
  Posté par serge_sans_paille (site web personnel) le 26 septembre 2018 à 20:28. Évalué à 4. Dernière modification le 26 septembre 2018 à 20:28.
  
  Complètement d'accord, mon exemple est bien mauvais :-) Merci d'avoir pointé ça !
# Merci tout simplement

Posté par wolowizard le 26 septembre 2018 à 21:51. Évalué à 5.

J'en apprends régulièrement sur le C++ avec les dépêches et journaux et c'est bien.

Quand bien même à chaque fois que je lis des articles sur C++ sur linuxfr, le résumé des commentaires c'est "imbitable" ; j'en apprends et j'améliore ma compréhension sur ce langage.

Bien sûr, je ne peux prétendre coder C++ avec facilité comme certain mais en tout cas, j'arrive maintenant à en lire…et à apprécier certaines structures…

Il y a quelques communautés sur linuxfr qui pousse à vouloir qu'on en apprenne plus sur le langage qu'elles utilisent (je pense typiquement à tout ce qui touche le fonctionnel et plus spécifiquement OCaml, C++).

Cette fois j'ai réussi à capter la structure sans souffler ! (contrairement au switch C++17.
Comme quoi, il ne faut jamais désespérer et accepter le fait que ça prend du temps.

Merci franchement et j'espère qu'il y en aura d'autres !

Ça attise la curiosité d'aller lire pythran.

Suivre le flux des commentaires

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