Meta-Programmation Template : une introduction .... - C++ - Programmation
Marsh Posté le 28-07-2003 à 22:45:10
Bravo ! Et bravo pour les exemples concrets. Ça manque souvent quand on veut saisir l'intérêt des templates.
/me qui se remet au C++ difficilement
Marsh Posté le 28-07-2003 à 22:45:28
Marsh Posté le 28-07-2003 à 22:55:04
je me permet de rajouter 2/3 trucs et un exemple tres concret pour ceux qui veulent se faire les dents.
1) je ferais un topic sur le mot clef typename, pour le moment retenez en le même usage que class pour les templates
2) JoelF utilise des enums, moi des constantes, les 2 choix sont valides suivant l'utilisation
Comment déterminer au moment de la compilation si 2 types sont équivalents?
Code :
|
Code :
|
Maitenant, une petite réflexion: quand on construit des classes, ont les fait souvent reposer sur des classes d'implémentation dont elles heritent, pour séparer implémentation brutale et interface. Ce qu'on aimerait faire, c'est un classe qui en fonction de son paramètre template hérite de la base qui va bien. Le code sans plus attendre
Code :
|
vous allez me dire: tout ça ne sert pas à grand chose. Voici un exemple tres concret: une classe qui implémente un tableau de taille fixe. En fonction de son occupation mémoire, il doit résider soit dans la pile soit dans le tas. On veut que les 2 implémentations soient compatibles, et que tout ce qui le peut soit optimiser (comme la permutation de 2 tableaux, tres rapides dans le cas de pointeur)
voilà la classe et un petit programme de test
http://dejean.benoit.free.fr/code/Array.hpp
http://dejean.benoit.free.fr/code/test_Array.cpp
c'est un petit exemple sans prétention, non exempt de bugs, testé sommairement, mais fonctionnel quand je m'en étais servis. compatible avec STL
Marsh Posté le 28-07-2003 à 22:59:02
C'est une super idée votre truc !! Bravo !!
Cela dit je n'ai pas trop envi de devenir un homme ...
Marsh Posté le 28-07-2003 à 23:00:16
Tchoupinette a écrit : C'est une super idée votre truc !! Bravo !! |
moi non plus
Marsh Posté le 28-07-2003 à 23:03:02
Arf,
"le C++, pour nous les hommes"
Ah ben non pas super le slogan
Marsh Posté le 28-07-2003 à 23:05:04
petite précision: la métaprogrammation de template repose sur les mécanismes de spécialisation de template, donc je vous invite à travailler ça. ce qui explique que
Code :
|
équivaut à
Code :
|
et faites attention car les templates supportent aussi les paramètres par défaut!
Marsh Posté le 28-07-2003 à 23:06:23
Il faut aussi savoir que certains compilateurs ne supportent pas toutes cs acrobaties ... gcc et cie sont en général bien fiable, mais certains autres le sont moins
@Taz : Et quand est il de la spécialisation PARTIELLE d'un tempalte ? J'ai toujours du mal avec ca ....
Marsh Posté le 28-07-2003 à 23:08:02
Joel F a écrit : Il faut aussi savoir que certains compilateurs ne supportent pas toutes cs acrobaties ... gcc et cie sont en général bien fiable, mais certains autres le sont moins |
des que je trouve un peu de temps, je fais un topic sur les differents types de spécialisation
Marsh Posté le 29-07-2003 à 08:19:22
bonjour,
je me permet de rajouter ce lien, qui m'avait initier à ce type de programmation pour ceux qui veulent aller voir:
http://osl.iu.edu/~tveldhui/papers [...] a-art.html
Comme il est dit:
"This article first appeared in the May 1995 issue of C++ Report. It has been reprinted in the book "C++ Gems" edited by Stanley Lippman."
Marsh Posté le 29-07-2003 à 08:40:55
ReplyMarsh Posté le 29-07-2003 à 09:06:50
Bravo Joel, c'était très clair !
(même si moi non plus, je ne veux pas devenir un homme )
Marsh Posté le 29-07-2003 à 09:10:13
Très très intéressant ! C'est cependant le type de code que j'hésite à écrire parce que je n'y pense pas, que je n'ai pas suffisamment d'expérience pour savoir quand l'utiliser, et qui peut rapidement jouer des pièges si on ne connait pas bien son compilateur (je pense notamment à la limite du nombre de niveaux de récursion supporté par un compilateur).
Le fait de travailler sous Visual C++ 6.0 n'invite pas non plus à pousser beaucoup les expériences (j'ai déjà passé un peu de temps sur du code qui me semblait devoir marcher mais ne fonctionnait pas parce que Visual C++ 6.0 ne respecte pas bien le Koenig Lookup).
Continuez ce genre d'articles qui sont très intéressants ! J'en profite pour orienter vers les C++ Tips and Tricks qui contiennent plein d'infos intéressantes.
Par contre, je pense qu'il y a une erreur ici :
Joel F a écrit :
|
La fonction de terminaison est plutôt :
Code :
|
il me semble ?
Marsh Posté le 29-07-2003 à 09:17:30
Code :
|
Plus precisement, il faut bien remplir l'indice 0 du tabelau ...
Je corrige asap
Marsh Posté le 29-07-2003 à 09:19:05
Oui, et donne aussi un type à la fonction sinon ça ne va toujours pas marcher :
Code :
|
Marsh Posté le 29-07-2003 à 12:57:23
je complète l'exemple de Taz sur le template If pour les compilateurs sans spécialisation partielle. C'est pas toujours possible de se passer de la spécialisation partielle, mais là c'est bon. A l'utilisation c'est pareil
Code :
|
Marsh Posté le 02-08-2003 à 03:45:37
détail technique : la "fonction de terminaison" s'appelle "le point fixe" (et n'est pas toujours une fonction comme montré dans le premier exemple).
Tiens d'ailleur ils disent quoi vos différents compilos si vous en mettez pas, il gueule a l'instanciation ou á la compilation du template, il pete la pile ou il s'est méfié avant ?
Marsh Posté le 02-08-2003 à 11:44:28
le mien il pète apres m'avoir afficher un message pour chaque instanciation...
Marsh Posté le 02-08-2003 à 12:01:07
nraynaud a écrit : détail technique : la "fonction de terminaison" s'appelle "le point fixe" (et n'est pas toujours une fonction comme montré dans le premier exemple). |
Je pense que même les meilleurs compilos c++ n'ont pas l'intelligence nécéssaire pour détecter ce genre de choses : ils se content d'un profondeur maximale de "templetisation" à ne pas dépasser.
J'ajouterais que ce genre de choses est assez difficile à détecter: dans le cas général, cela revient grosso modo a décider de la terminaison d'un programme, ce qui est un problème NP complet.
Marsh Posté le 03-08-2003 à 05:31:48
SchnapsMann a écrit : J'ajouterais que ce genre de choses est assez difficile à détecter: dans le cas général, cela revient grosso modo a décider de la terminaison d'un programme, ce qui est un problème NP complet. |
Non, justement, ce cas précis (absence de point fixe dans une expression récursive) est assez simple, il donne un joli _|_ (bottom) quand tu tentes d'inférer son type.
Ça peut parraître bizzare de tenter de typer un type, mais en réalité ça se fait courament dans certains domaines. En prenenant le langage des templates comme un langage de script qui te génère du code C amélioré, c'est assez facile de faire le lien avec le domaine fonctionel (réécriture de graphes et pattern-matching sur des valeurs).
edit : si un jour je me motive, je ferais la démo de programmes fonctionnels en template C++ et en caml.
Marsh Posté le 04-02-2004 à 16:06:33
schnapsmann a écrit : |
J'aimerais bien. En vrai, c'est indécidable (mais c'est sans doute ce que tu voulais dire)
Marsh Posté le 21-03-2004 à 12:55:43
bon a quoi sert le struct alors ?
je pose une question maintenant si ma question est completement stupide ... j irais voir ailleur.
Marsh Posté le 21-03-2004 à 13:08:00
je ne savais pas comment creer son namespace, j ai apris quelque chose. donc ma question netait pas inutile.
merci.
Marsh Posté le 21-03-2004 à 13:09:56
xiluoc a écrit : je ne savais pas comment creer son namespace, j ai apris quelque chose. donc ma question netait pas inutile. |
les struct/class n'ont rien à voir avec les "namespace"
et en bon français, on dit pas "espace de nommage" on dit "référentiel lexical"
Marsh Posté le 28-07-2003 à 22:37:25
Bon voila, j'ai décidé d'un commun accord avec Taz de pondre quelques topics sur le C++ , le vrai, celui qui fera de vous un homme
Je vais entamer ici une série de post sur la métaprogrammation template.
PRINCIPES :
La metaprogramamtion template est un ensemble de technique utilisant les mécanismes du template pour générer du code optimisé, au moment de la compilation, induisant un gain de vitesse non négligeable à l'éxécution.
Quel intéret ? Et bien, la possibilité d'écrire du code sécurisé et permettant facilement de générer des constantes, des boucles déroulées et plein d'autres astuches.
La grande idée c'est comme dit Taz : "Think you're a compiler" !
Comment ce code peut il etre reecrit afin de mettre en evidence tel ou tel comportement template ? Est-ce que ce problème n'est pas simplement resoluble par une grammaire ??
1. Rappels
Quelques faits (mé)connus des templates :
1. Les classes et fonction templates sont instanciées en place ne produisant pas ou peu d'appel de fonction.
Le code template est quasiment toujours déroulé par le compilateur, un inline automatique.
2. Les arguments des templates ne sont pas nécessairement des types. Un template peut recevoir des types entiers (char,short,int,bool) en paramétres :
On peut aussi feinter pour utiliser ds double par exemple :
3. Une fonction template peut determiner automatiquement ces paramétres de type.
A partir de la, que peut on faire ???
2. La factorielle
Considérons maintenant un code ou il est nécessaire d'utiliser de nombreuses factorielles.Disons, un calcul de développement limité. Etant des constantes, ce genre de valeur sont souvent
stockés dans des enum ou pire des #define !!!
Nos chers templates reviennent à la rescousse :
Maintenant, nous voulons évaluez 11! :
Ce code enclenche une série d'évaluation :
Evidemment l'ensemble de ce code est produit et évalué à la compilation.
3. La Boucle FOR
Considérons ce code :
Il va générer 100000 tests de bornes, retour et affectation.
On peut gagner un peu en écrivant quelques choses comme :
On gagne 50000 tests/retour.
L'ultime abus serait de dérouler ENTIEREMENT cette boucle, éliminant ainsi tous test et sauts. Bon, les maso léve la main et vont coder ca a la main
Comment faire ?
On va utiliser un aspect un peu méconnu du template : le fait que son ou ses arguments ne sont pas forcement des types mais peuvent etre des entiers. Considérons cette fonction template :
Si nous l'appellons ainsi :
Le code suivant est produit à la compilation :
Gain de vitesse notable (proche du x2 ou du x3) mas evidemment perte sur la taille de l'executable.
Par contre , il faut faire gaffe au paramétres. g++ ne deplie les templates que sur 512 niveau. Une option permet d'augmenter cette valeur, mais le temps de compilation devient vite infâme.
Un projet perso utilise 2048 comme limite et prends plusieurs minutes sur une seule fonction
4. Un Tri résolu à la compilation
Le tri à bulles est un des tris les plus simples à gérer. Néanmoins, pour des tableaux de grandes tailles,
bah c'est pas trop ça . Pourtant, sur des tableaux de petites tailles, il reste le plus intéressant à implanter :
Voila, c'est trés simple. On peut alors se dire, par exemple, de spécialiser
le tri à bulles pour des tableaux de trois éléments :
Bon .... maintenant, si nous voulons produire un code équivalent pour une taille voulue, on ne va pas non plus réécrire ce code N fois pour chaque taille. La Meta-Programamtion template arrive à la rescousse. Voila une classe de Tri A Bulles basé sur l'algo ci-dessus :
L'appel suivant :
va générer un code semblable à :
Bon que dois faire IntBubbleSortLoop<N,M>::loop() ???
Et bien, il va générer les divers tests sur les éléments :
Rebelote, voila le code de notre tri :
On approche de la solution, il suffit de coder la méthode IntSwap<I,J>::compareAndSwap
qui va effectuer le tri :
swap() n'a pas changé :
Au final , notre appel IntBubbleSort<4>::sort( int* data); devient :
Il suffit alors de changer le paramétre template de IntBubbleSort pour générer des fonctions de tri de taille diverses.
Au niveau perf, le tri est 7 à 3 fois plus rapide pour des tableaux de taille inférieure à 10, et le gain se stabilise vers 1.6 pour des tableau plus grand. un gain non négligeable somme toute. On peut aussi rajouter des paramétres templates pour gérer le type des données triées, modifiées la fonction de comparaison par des foncteurs etc ...
Voila, quelques choses simples. Je posterais une petite explication sur d'autres techniques liées aux templates comme les traits, les expressions templates etc ...
EDIT : typos, erreur diverse
Message édité par Joel F le 29-07-2003 à 09:21:01