C++

Meta-Programmation Template : une introduction ....

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : Meta-Programmation Template : une introduction ....

Joel F

Real men use unique_ptr

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 :

Code :

template<int V> struct Constante
{
static const int value = V;
}
// affiche '17'.
cout << Constante<17>::value << endl;

On peut aussi feinter pour utiliser ds double par exemple :

Code :

template<class T,T V> struct Constante
{
static const T value = V;
}
// affiche '17.3'.
cout << Constante<double,17.3>::value << endl;

3. Une fonction template peut determiner automatiquement ces paramétres de type.

Code :

template<class T> T max( const T& a, const T& b )
{
return ( a<b ? b : a );
}

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 :

Code :

template<int V> struct factorielle
{
enum { value=V*factorielle<V-1> };
};
template<> struct factorielle<0>
{
enum { value=1 };
};

Maintenant, nous voulons évaluez 11! :

Code :

int fact_11 = factorielle<11>::value;

Ce code enclenche une série d'évaluation :

Code :

int fact_11 = 11*factorielle<10>::value;
int fact_11 = 11*10*factorielle<9>::value;
...
int fact_11 = 11*10*9*...*2*1 = 39916800;

Evidemment l'ensemble de ce code est produit et évalué à la compilation.

3. La Boucle FOR
Considérons ce code :

Code :

for(int i=0;i<100000;i++) tab[i] = 2*i+1;

Il va générer 100000 tests de bornes, retour et affectation.
On peut gagner un peu en écrivant quelques choses comme :

Code :

for(int i=0;i<50000;i++)
{
tab[2*i] = 2*(2*i)+1;
tab[2*i+1] = 2*(2*i+1)+1;
}

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 :sol:

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 :

Code :

// fonction de base
template<int N> void remplir( int* tab )
{
tab[N] = 2*N+1;
remplir<N-1>(tab);
}
// fonction de terminaison
template<> void remplir<0>( int* tab )
{
tab[0] = 1;
}

Si nous l'appellons ainsi :

Code :

remplir<99>(tab);

Le code suivant est produit à la compilation :

Code :

tab[99] = 199;
tab[98] = 197;
tab[97] = 195;
...
tab[2] = 5;
tab[1] = 3;
tab[0] = 1;

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 :ouch:

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 :

Code :

inline void swap(int& a, int& b)
{
int temp = a;
a = b;
b = temp;
}
void sort(int* data, int N)
{
for (int i = N - 1; i > 0; --i)
{
for (int j = 0; j < i; ++j)
{
if (data[j] > data[j+1]) swap(data[j], data[j+1]);
}
}
}

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 :

Code :

void bubbleSort(int* data, int N)
{
for (int j = 0; j < N - 1; ++j)
{
if (data[j] > data[j+1]) swap(data[j], data[j+1]);
}
if (N > 2) bubbleSort(data, N-1);
}

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 :

Code :

template<int N> struct IntBubbleSort
{
static inline void sort(int* data)
{
IntBubbleSortLoop<N-1,0>::loop(data);
IntBubbleSort<N-1>::sort(data);
}
};
template<> struct IntBubbleSort<1>
{
static inline void sort(int* data) {}
};

L'appel suivant :

Code :

IntBubbleSort<4>::sort( int* data);

va générer un code semblable à :

Code :

IntBubbleSortLoop<3,0>::loop(data);
IntBubbleSortLoop<2,0>::loop(data);
IntBubbleSortLoop<1,0>::loop(data);

Bon que dois faire IntBubbleSortLoop<N,M>::loop() ???
Et bien, il va générer les divers tests sur les éléments :

Code :

template<int I, int J>
class IntBubbleSortLoop
{
private:
enum { go = (J <= I-2) };
public:
static inline void loop(int* data)
{
IntSwap<J,J+1>::compareAndSwap(data);
IntBubbleSortLoop<go ? I : 0, go ? (J+1) : 0>::loop(data);
}
};
class IntBubbleSortLoop<0,0>
{
public:
static inline void loop(int*) {}
};

Rebelote, voila le code de notre tri :

Code :

IntSwap<0,1>::compareAndSwap(data);
IntSwap<1,2>::compareAndSwap(data);
IntSwap<2,3>::compareAndSwap(data);
IntSwap<0,1>::compareAndSwap(data);
IntSwap<1,2>::compareAndSwap(data);
IntSwap<0,1>::compareAndSwap(data);

On approche de la solution, il suffit de coder la méthode IntSwap<I,J>::compareAndSwap
qui va effectuer le tri :

Code :

template<int I, int J> struct IntSwap
{
static inline void compareAndSwap(int* data)
{
if (data[I] > data[J]) swap(data[I], data[J]);
}
};

swap() n'a pas changé :

Code :

inline void swap(int& a, int& b)
{
int temp = a;
a = b;
b = temp;
}

Au final , notre appel IntBubbleSort<4>::sort( int* data); devient :

Code :

if (data[0] > data[1]) swap(data[0], data[1]);
if (data[1] > data[2]) swap(data[1], data[2]);
if (data[2] > data[3]) swap(data[2], data[3]);
if (data[0] > data[1]) swap(data[0], data[1]);
if (data[1] > data[2]) swap(data[1], data[2]);
if (data[0] > data[1]) swap(data[0], data[1]);

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

Publicité

gm_superstar

Appelez-moi Super

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 :sweat:

Message édité par gm_superstar le 28-07-2003 à 22:45:49

---------------
Incongru : une FAQ abandonnée sur les Standards du Web - FAQ périmée de blabla@Prog

schnapsmann

Zaford Beeblefect

Message édité par schnapsmann le 28-07-2003 à 22:47:56

---------------
From now on, you will speak only when spoken to, and the first and last words out of your filthy sewers will be "Sir!"

Taz

bisounours-codeur

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 :

template<typename T1, typename T2>
struct SAME_TYPE
{
static const bool RESULT=false;
};
template<typename T>
struct SAME_TYPE<T, T>
{
static const bool RESULT=true;
};

Code :

SAME_TYPE<int, char>::RESULT;

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 :

// template IF statement
template <bool c, typename TRUE, typename FALSE>
struct IF;
template <typename TRUE, typename FALSE>
struct IF <true, TRUE, FALSE>
{
typedef TRUE RESULT;
};
template <typename TRUE, typename FALSE>
struct IF <false, TRUE, FALSE>
{
typedef FALSE RESULT;
};
#include <iostream>
using namespace std;
template<class T>
struct BigBar
{
T item;
void say_hello() const
{
cout << "BigBar\n";
}
};
template<class T>
struct SmallBar
{
T item;
void say_hello() const
{
cout << "SmallBar\n";
}
};
template<class T>
class Foo :
private IF < sizeof(T) <= sizeof(int),
SmallBar<T>,
BigBar<T>
> :: RESULT
{
public:
void operator()() const
{
say_hello();
}
};
int main()
{
Foo<int>()();
Foo<char>()();
Foo<double>()();
}

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

tchoupinette

C'est une super idée votre truc !! Bravo !! :jap:

Cela dit je n'ai pas trop envi de devenir un homme ... :whistle:

---------------
http://membres.lycos.fr/axelfa

Taz

bisounours-codeur

Tchoupinette a écrit :

C'est une super idée votre truc !! Bravo !! :jap:

Cela dit je n'ai pas trop envi de devenir un homme ... :whistle:

moi non plus

Joel F

Real men use unique_ptr

Arf,

"le C++, pour nous les hommes"

Ah ben non pas super le slogan [:taimp]

Taz

bisounours-codeur

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 :

template <bool c, typename TRUE, typename FALSE>
struct IF;
template <typename TRUE, typename FALSE>
struct IF <true, TRUE, FALSE>
{
typedef TRUE RESULT;
};
template <typename TRUE, typename FALSE>
struct IF <false, TRUE, FALSE>
{
typedef FALSE RESULT;
};

équivaut à

Code :

template <bool c, typename TRUE, typename FALSE>
struct IF
{
typedef TRUE RESULT;
};
template <typename TRUE, typename FALSE>
struct IF <false, TRUE, FALSE>
{
typedef FALSE RESULT;
};

et faites attention car les templates supportent aussi les paramètres par défaut!

Joel F

Real men use unique_ptr

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 ....

Taz

bisounours-codeur

Joel F a écrit :

des que je trouve un peu de temps, je fais un topic sur les differents types de spécialisation

Publicité

SoWhatIn22

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."

skeye

flag!
Vous vous déchainez sur le C++ !!
:jap:

polo021

skeye a écrit :

flag!
Vous vous déchainez sur le C++ !!
:jap:

drapo [:texla]

umag

deux yeux sinon rien

:hello: Bravo Joel, c'était très clair !

(même si moi non plus, je ne veux pas devenir un homme :lol: )

gatorette

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 :

...

Code :

// fonction de base
template<int N> remplir( int* tab )
{
tab[N] = 2*N+1;
remplir<N-1>(tab);
}
// fonction de terminaison
template<int N> remplir( int* tab )
{
tab[0] = 1;
}

...

La fonction de terminaison est plutôt :

Code :

template<0> remplir( int* tab )
{
// ...
}

il me semble ?

---------------
each day I don't die is cheating

Joel F

Real men use unique_ptr

Code :

// fonction de terminaison
template<> remplir<0>( int* tab )
{
tab[0] = 1;
}

Plus precisement, il faut bien remplir l'indice 0 du tabelau ...
Je corrige asap

umag

deux yeux sinon rien

Oui, et donne aussi un type à la fonction sinon ça ne va toujours pas marcher :

Code :

// fonction de terminaison
template<> void remplir<0>( int* tab )
{
tab[0] = 1;
}

Message édité par umag le 29-07-2003 à 09:19:46

Joel F

Real men use unique_ptr

Correction fait [:prosterne]

gloop

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 :

// Les deux types suivants "simulent" des template-typedef
// Sélectionne toujours le premier type
struct SelectFirstType
{
template<typename Tp1, typename Tp2>
struct TypeSelector
{
typedef Tp1 Type;
};
};
// Sélectionne toujours le second type
struct SelectSecondType
{
template<typename Tp1, typename Tp2>
struct TypeSelector
{
typedef Tp2 Type;
};
};
// On choisit le premier sélecteur
template<bool condition>
struct SelectSelector
{
typedef SelectFirstType Selector;
};
// Spécialisation pour false, en choisissant le second type
template<>
struct SelectSelector<false>
{
typedef SelectSecondType Selector;
};
// Selecteur de type
template<bool condition, typename Tp1, typename Tp2>
struct If
{
// On sélectionne le selecteur
typedef typename SelectSelector<condition>::Selector Selector;
// puis on l'utilise
typedef typename Selector::TypeSelector<Tp1, Tp2>::Type Type;
};

nraynaud

lol

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 ?

---------------
trainoo.com, c'est fini

Taz

bisounours-codeur

le mien il pète apres m'avoir afficher un message pour chaque instanciation...

schnapsmann

Zaford Beeblefect

nraynaud a écrit :

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.

nraynaud

lol

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.

Message édité par nraynaud le 03-08-2003 à 05:40:01

glacote

schnapsmann a écrit :

J'aimerais bien. En vrai, c'est indécidable (mais c'est sans doute ce que tu voulais dire)

Taz

bisounours-codeur

supprimez ces 2 messages svp

xiluoc

un pc pour les unirs ....

bon a quoi sert le struct alors ?
je pose une question maintenant si ma question est completement stupide ... j irais voir ailleur.

Taz

bisounours-codeur

elle est stupide

verdoux

And I'm still waiting

Le struct définit un type et un espage de nommage.

xiluoc

un pc pour les unirs ....

je ne savais pas comment creer son namespace, j ai apris quelque chose. donc ma question netait pas inutile.
merci.

Taz

bisounours-codeur

xiluoc a écrit :

je ne savais pas comment creer son namespace, j ai apris quelque chose. donc ma question netait pas inutile.
merci.

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"

Publicité

FORUM HardWare.fr

Programmation

C++

Meta-Programmation Template : une introduction ....

Sujets relatifs
debuter la programmation avec un logiciel gratuit	aide pour programmation
Template et virtuelle pure	Programmation d'une carte I/O
Programmation en Java: question de la part d'un débutant...	Spécialisation template & Pétage de plomb
Question aux developpeurs : limites de programmation	Affectation template & héritage
Programmation Pocket PC	programmation shell
Plus de sujets relatifs à : Meta-Programmation Template : une introduction ....

Page générée en 0.168 secondes