Discussion :

[PierroVsf]

Bonjour,

Dans l'optique de faire un moteur physique, j'ai choisi d'utiliser les template pour faire des arbres syntaxiques et simplifier mes calculs.
le système est éxpliqué dans ce tutoriel:
http://loulou.developpez.com/tutorie...taprog/#LIII-C

Je travaille sur des vecteur de 3 double et des matrices de 3*3 doubles.
Ce que je veux faire est dériver une expression mathématique, pour ensuite rentrer dans un solveur les tèrmes inconnus( les tèrmes inconnus seront les tèrmes de dérivée seconde). Pour l'instant j'ai simplement implémenté la dérivation et l'évaluation de l'expression. Et le problème est que le compilateur n'inline pas assez l'arbre syntaxique, or sa complexité devient quadratique en fonction du nombre d'éléments dans l'arbre syntaxique. On peut facilement le voir lorsque l'on fait une sortie assembleur:
Par exemple si l'arbre syntaxique est réellement construit (ce qui ne devrait pas arriver si l'inlining fonctionne bien):

Pour une suite d'additions la taille de la variable de l'expression a la taille de l'ensemble des variable qu'il contitent

Code :

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

sizeof(v1+v2+v3+v4+v5+v6+v7+v8)==sizeof(v1)*8

Or la construction de l'arbre se fait comme suit:
(avec Tn+1==Opplus<Tn,T> et

Code :

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

sizeof(Tn)==sizeof(T)*n

)

Code :

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

Opplus<Tn,T>(Tn a, T b):op1(a),op2(b){}

La construction du type intérmédière Tn se fait en copiant une variable de taille n*sizeof(T)
Or il ya n type intérmédière construit donc la taille totale des variables déplacée est sizeof(T)n*(n+1)/2

Ce qui fait beaucoup, la complexité devient quadratique alors que l'on voulait gagner en complexité!!
Le compilateur ne fait pas son travail! Deplus cela devient dangereux lorsque je dérive une expression qui fait intervenir des multiplication:

Code :

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

sizeof(derive(derive(v*v*v)))==sizeof(v)*27

J'ai donc de gros template, si le template n'est pas optimisé la complexité finale dans le pire des cas est de
27*28/2*C(copie)+27*C(opérations)
alors qu'il ne devrait y avoir seulement 27*C(opérations)

Voilà le code du template pour quelques opérations(ce code fonctionne):
essais.h
matr9d.cpp
matr9d.h
essais.cpp
patrons.h

matr9f.h et matr9f.cpp contienne le vecteur de 3 double et la matrice de 3*3 double, avec plein d'opérations.
patrons.h contient deux trois template
essai.cpp contient le main et essai.h contient l'arbre syntaxique.

On peut essayer différentes expressions qui réalisent la même chose entre le calcul direct et le calcul par évaluationde l'arbre syntaxique. On voit que la sortie assembleur effectuée avec l'arbre syntaxique est plus longue.

compilation pour sortie assembleur:
g++ -O2 -S -std=c++0x *.cpp


Y a-t-il un truc pour régler ce problème?

Merci d'avance pour vos réponses

[prgasp77]

J'ai peut-être parcouru trop vite tes fichiers, mais je ne vois nul part de construction d'arbre syntaxique par métaprogrammation... Où sont tes méta-opérateurs ? Où sont tes méta-constructeurs ?

[Ehonn]

Je répond uniquement sur la question de l'inlining (pour le reste : 0. la question est trop floue, ça parle de métaprogrammation mais il n'y a que les base de la programmation générique 1. Au vu du titre je m'attendais à voir la construction d'une expression qui ressemble à de la lazy evaluation + simplification de l'arbre qui rentre les expressions dans des types "plus haut" 2. Plusieurs choses me gène dans ce code mais surtout : pourquoi ne pas utiliser la bibliothèque standard (std::swap, std::vector) ?)

Donc, si tu veux que le compilateur puisse inliner, le plus simple est de mettre la définition des fonctions dans un fichier d'entête. Il existe une solution pour forcer l'inlining, cette solution dépend du compilateur ; utiliser BOOST_FORCE_INLINE devrait suffire.

[ternel]

Je rajoute mon p'tit grain de sel
Mettre les définitions dans l'en-tête, et si la définition n'est pas dans sa classe, ajouter le spécificateur inline

[PierroVsf]

Désolé pour le manque de précision, je m'explique un peu plus:

Toutes les fonctions de l'arbre syntaxique sont dans essais.h.
A la différence du tutoriel que j'ai cité : http://loulou.developpez.com/tutorie...taprog/#LIII-C
Je n'utilise pas une classe pour les opérateurs binaires et une classe pour les opérateurs unaires, mais j'ai une classe par opérateur, sinon l'arbre syntaxique est fondamentalement pareil.

J'ai inliné toutes les fonctions du fichier contenant l'arbre syntaxique (essai.h).

Ensuite effectivement j'ai voulu réaliser un arbre syntaxique le plus simple possible pour faire apparaître ce problème. Mais si ce problème arrive pour un arbre simple comme celui-ci, je trouve que l'on ne peut plus faire confiance à ce type de système.

Je n'utilise pas de tableaux dans mon arbre syntaxique. Il y a effectivement une classe dynamictab qui ressemble à la classe std::vector et une fonction echange qui est exactement la fonction swap, mais celles si n'on rien a voir avec le code utilisé( ce sont des rèste d'autre programme que j'ai fait).

Le seul code à regarder est la classe essais.h

La question est:
auriez vous un arbre syntaxique qui ne soit pas limité par ce problème pour que je m'en inspire?
auriez vous une méthode pour que l'inline se fasse a tout les coups (si possible avec gcc)?

Ou simplement connaissez vous ce problème?

[jo_link_noir]

Inline sur les fonctions ne sert pas, 1) parce que le mot clef n'est pas fait pour ça, et 2) parce que le compilo s'en contrefout. En plus, c'est le comportement par défaut des fonctions template.

Concernant les fichiers en assembleur, au bureau, celui avec l'arbre syntaxique est 2 fois plus petit. Je viens de restest chez moi et les fichiers font la même taille pour un contenir très proche.

Concernant les types dans l'arbre, pourquoi ne pas prendre des références / références constantes ? Ainsi, plus de copie.