Discussion :

[Invité]

Bonjour,

Je lis actuellement sur la métaprogrammation (le C++ template metaprogramming de Abrahams et Gurtovoy, notamment), et j'ai une question sur son application au calcul numérique...

Comme tout le monde, je pense, je suis très admiratif devant l'ingéniosité du procédé, mais je n'arrive pas à comprendre l'intérêt pratique de la chose.

Je veux dire, je suis capable d'écrire quelque chose comme

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
template<unsigned long N,unsigned long P> struct Puissance
{
static const unsigned long value=Puissance<N,P-1>::value*N;
};
 
template<unsigned long N> struct Puissance<N,0>
{
static const unsigned long value=1;
};

voire,

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
template<unsigned long N,unsigned long P> struct Puissance
{
static const unsigned long value=Puissance<N,P/2>::value*Puissance<N,P/2>::value*(P%2==1?N:1);
};
 
template<unsigned long N> struct Puissance<N,0>
{
static const unsigned long value=1;
};

et peut être même des trucs un rien plus malin (pour limiter au maximum le nombre d'instanciations), et trouver admirable de pouvoir écrire

Puissance<7,3>;
au lieu de
343; // 7^3
voire
7*7*7;

Mais je ne suis pas certain d'en voir l'intérêt pratique...

Quelqu'un a-t-il un exemple de metaprogramme numérique non trivial?

Francois

[Goten]

Numérique? non du tout... comme ils le précisent, (me semble bien qu'ils le précisent dans le bouquin), l'intérêt principal de la MP reste les "calculs" sur les types, et la génération de code.
En bref le véritable intérêt de la MP c'est d'avoir un langage fonctionnel à disposition quoi pour faire des opérations sur des types etc.


Si on veut vraiment chercher la petite bête, on peut dire que les expressions templates servent dans le calcul numérique (et non pas à faire du) et permettent de gagner du temps.. (beaucoup de temps).

Je veux dire, oui la MP numérique ça existe (ton exemple de factorielle etc), mais bon ça reste des choses triviales sans bien grand intérêt quoi...

edit : d'ailleurs, tu peux le voir dans le bouquin, mis à part au tout tout début où ils montrent l'exemple sur du convertisseur binaire, tout les reste est centré sur MPL (et donc la manipulation de type)

[Invité]

Si on veut vraiment chercher la petite bête, on peut dire que les expressions templates servent dans le calcul numérique (et non pas à faire du) et permettent de gagner du temps.. (beaucoup de temps).

Je pense que je lancerai un fil sur le sujet un peu plus tard... Actuellement, ma sensation c'est que les expression templates, c'est effectivement un moyen de gagner du temps sur des problèmes très précis : calcul sur des vecteurs denses, calculs de puissances (comme l'exponentiation binaire de mon exemple). Dans ces cas, ça a l'avantage d'être relativement facile à programmer...

Maintenant, sur des problème typiques d'analyse numérique, par exemple opérations sur des matrices creuses (ou convolutions de polynomes ayant peu de termes, ou calculs de probas avec pas mal de zéros, tous les problèmes où il y a enormément de termes mais beaucoup de zéros, quoi), j'ai l'impression qu'elles seront toujours battues par des méthodes d'évaluation paresseuse.

En gros, l'expression template te permet d'éviter les évaluations intermédiaires, dans des expressions comme

M=AX+BY+CZ (où tous ces termes sont des matrices ou des vecteurs)

mais elles ne sauront tirer parti du fait que ces matrices sont creuses (et donc que dès qu'on voit un zéro, on peut tuer un bout du calcul), parce que c'est typiquement une décision d'exécution...

Voire, si en plus on stocke les données de façon intelligente, on peut même éviter de tester la nullité des éléments nuls (on gagne alors deux fois : sur le parcours des éléments, et sur le calcul! quand on sait qu'un produit matriciel c'est typiquement N^3...)

Mais je vais lancer un fil, c'est promis...

edit : d'ailleurs, tu peux le voir dans le bouquin, mis à part au tout tout début où ils montrent l'exemple sur du convertisseur binaire, tout les reste est centré sur MPL (et donc la manipulation de type)

En fait, ils donnent quelques exemples supplémentaires au milieu. Josuttis et Vandevoorde, de leur côté, présentent le numérique comme introduction à la métaprogrammation. Mais effectivement ca ne va jamais plus loin...

C'est un peu pour cela que je me demandais...

Francois

[Goten]

Les expressions templates permettent de faire *beaucoup* plus que ça. De façon général les expressions templates permettent de définir des DSEL (regarde boost.proto). (remarque que, quand tu t'en sers dans le calcul algébrique linéaire, tu définis un DSEL).


Mais sinon oui dans le cas d'opération sur des arrays etc, les expr templates évitent la création de temporaire (ce qui est vraiment lourd sur de grosses matrices), maintenant elles peuvent être combinés aux autres optimisations que tu cites! (c'est en général le cas d'ailleurs).


ps : le Josuttis & Vandevoorde est vraiment excellent lui aussi!. Mais le Abrahams reste un ovni...

[Alp]

Alors la MP numérique telle que tu la montre au début, bah ça sert si tu as la flemme de sortir ta calculette ou si le calcul est trop complexe pour ça, tu peux le faire calculer par ton compilateur et avoir le nombre à dispo pré-calculé au runtime. C'est tout.

Le reste de la MP, comme tu le découvriras avec ce livre, c'est excessivement plus puissant. Regarde Boost.MPL, Boost.Proto, Boost.Spirit, Boost.Lambda, etc.

Les techniques sont très variées, ça va d'avoir des sortes d'Abstract Syntax Trees compile-time que tu traverses jusqu'à tagger des types en leur adjoignant un autre type pour attacher des informations supplémentaires, etc. En gros, le genre de choses que tu pourrais faire au runtime d'habitude, avec des valeurs, mais là avec des types !

Les intérêts sont multiples ça dépend de la situation. Un exemple assez frappant c'est une bibliothèque qui permet de paralléliser *automatiquement* et *à la compilation* (une fois la compilation terminée, on sait quels trucs seront lancés sur un core, et lesquels seront lancés sur un autre, etc) une chaîne de traitement de signal. Par exemple ici selon comment on attache 2 traitements (la sortie de l'un étant l'entrée de l'autre par ex), c'est à dire série ou parallèle principalement, on va tagger le traitement avec un type ou un autre, et selon le type on va pouvoir ensuite faire en sorte de les "séparer" pour qu'ils soient exécutés en parallèle.

Après t'as les expression templates et les typelists & autres joyeusetés qui constituent la base de ce genre de pratique oui.
J'ai écrit 2 trucs vite fait sur mon blog anglais, si ça te dit :
http://alpmestan.wordpress.com/2009/...plates-matter/ (orienté assez pratique)
http://alpmestan.wordpress.com/2009/...pe-lists-in-c/ (un peu plus dans le genre "regardez comment ça marche")

Si tu as des questions n'hésite pas.

PS : si tu trouves une façon d'attacher l'information que la matrice est creuse dans le type, là y'a moyen de se faire plaisir, mais hélas c'est le genre de choses que tu ne sais qu'au runtime. Et c'est là qu'un langage comme Haskell trouera C++ en perfs avec parallélisation intelligente + laziness.

[Joel F]

Ca sert comme le reste de la métaprog. J'ai un bout de code dans NT² qui inverse des matrices de rationelles au compile-time pour calculer des intersections de range de nid de boucle.

[Invité]

Alors la MP numérique telle que tu la montre au début, bah ça sert si tu as la flemme de sortir ta calculette ou si le calcul est trop complexe pour ça, tu peux le faire calculer par ton compilateur et avoir le nombre à dispo pré-calculé au runtime. C'est tout.

Merci, ca confirme un peu mon intuition...

Le reste de la MP, comme tu le découvriras avec ce livre, c'est excessivement plus puissant. Regarde Boost.MPL, Boost.Proto, Boost.Spirit, Boost.Lambda, etc.

Oui, ca j'en suis bien conscient. Je m'intéresse davantage au calcul numérique, parce que c'est un domaine où j'en aurais une utilité immédiate (le reste c'est sur le temps libre)

J'ai écrit 2 trucs vite fait sur mon blog anglais, si ça te dit :
http://alpmestan.wordpress.com/2009/...plates-matter/ (orienté assez pratique)
http://alpmestan.wordpress.com/2009/...pe-lists-in-c/ (un peu plus dans le genre "regardez comment ça marche")

Je les ai déjà lus (c'est très intéressant), mais je vais les relire...

PS : si tu trouves une façon d'attacher l'information que la matrice est creuse dans le type, là y'a moyen de se faire plaisir, mais hélas c'est le genre de choses que tu ne sais qu'au runtime. Et c'est là qu'un langage comme Haskell trouera C++ en perfs avec parallélisation intelligente + laziness.

En fait, tu sais généralement à la compilation si une matrice est creuse. Ce que tu ne sais pas, c'est où sont les zéros...

Tu as alors deux options (pour battre Haskell...)
- utiliser une représentation où les zéros des matrices creuses ne sont pas gardés. Conceptuellement, tes matrices, tes vecteurs, ou tes polynomes deviennent alors des listes de paires (indice, coeff). On est alors dans une approche pur runtime, je pense, où l'on essaye de réduire la taille des boucles de calcul. Ce n'est pas facile à faire, mais ca peut être radical
- (c'est encore une idée mal aboutie) essayer de travailler les expression templates pour qu'elles exploitent mieux les valeurs nulles (ca doit aussi pouvoir se faire en runtime, remarque).

L'idée est la suivante : une expression template décrit un calcul, on a donc le choix de la représentation. Actuellement, on écrit une représentation en opérateurs binaires ou unaires classiques, mais rien ne l'impose. Et les propriétés des opérateurs ne sont pas prises en compte. Je suppose qu'on pourrait forcer les ET à mettre au début, par exemple, une multiplication par un terme "vraisemblablement nul". L'idée étant que sur une expression de type

x*f(y,z,...);

si x est nul, on n'a plus besoin d'évaluer f... (c'est comme les conditions de test, quoi).

En premier ordre, on peut juste intégrer ces simplications dans les surcharges des opérateurs des ET, mais on pourrait peut être trouver des solutions "pensées pour" ce genre de chose.

Francois

[JolyLoic]

J'ai vu un exemple de calcul de ce type au compile-time qui pouvait avoir un intérêt : Le résultat servait à initialiser la taille d'un std::array.

Autrement, les expression templates sur les matrices sont complémentaires à l'utilisation de matrices creuses, et non pas concurrentes. Avec des matrices creuses, tu ne calcules pas là où il n'y a que des 0. Avec des expressions templates, tu supprimes les intermédiaires, et éventuellement tu ne calcules que le coefficient qui t'intéresse dans la matrice.

[Joel F]

J'ai vu un exemple de calcul de ce type au compile-time qui pouvait avoir un intérêt : Le résultat servait à initialiser la taille d'un std::array.

Autrement, les expression templates sur les matrices sont complémentaires à l'utilisation de matrices creuses, et non pas concurrentes. Avec des matrices creuses, tu ne calcules pas là où il n'y a que des 0. Avec des expressions templates, tu supprimes les intermédiaires, et éventuellement tu ne calcules que le coefficient qui t'intéresse dans la matrice.

Y a une equipe de EDF R&D qui fait exactement ça sur des matrices creuses sructurées.