Conteneur pour optimisation de temps de calcul

Version imprimable

03/04/2010, 17h37
Kaluza

Conteneur pour optimisation de temps de calcul

Bonjour.

J'ai un niveau de C++ "moyen" (je maitrise bien l'utilisation de classes, de librairies comme Qt, mais je n'ai aucune expérience dans la programmation "avancée" style métaprogrammation). Je travaille actuellement sur un programme de calcul pour un problème de physique et je me suis rendu compte que la manière dont je l'avais implanté la première fois ramais à mort car la classe contenant les algos de calcul faisait appel à des dizaines d'autres classes pas forcément optimisée et qu'au final ça ramait à mort.

J'ai donc pensé qu'il serait mieux de mettre toutes les données et variables temporaires dont la classe d'algo à besoin en variables membres pour éviter qu'elle fasse appel à des dizaines d'autres classes, et d'inliner certaines fonctions de cette classe. Est-ce la bonne solution ?

Ensuite voilà mon problème : du coup le nombre de variables membres "double" de la classe a exploser (je dois en être à plus de 100) et ça m'aiderait bien si je pouvais les répartir dans des conteneurs. C'est un peu complexe mais ma classe peut faire des calculs relatifs à 4 entités physiques du coup j'ai 4 fois les "mêmes" variables. Si je pouvais plutôt classer ça dans un conteneur type vector de taille 4, ce serait plus cool. L'autre problème est que certaines de ces variables sont des vecteurs physiques (type x,y,z) donc si je voulais classer ça proprement, je devrai faire un vector de vector.
Par exemple [0][0] serait la composante x pour la première entité physique, [0][1] la composante y, [0][2] la composante z, [1][0] la composante x pour la seconde entité physique etc...

Ma question est la suivante : avec quel conteneur travailler ?
A priori la taille ne variera pas (très petite taille) et j'ai besoin d'un accès optimisé (d'un point de vue temps) en lecture et en écriture de n'importe quelle composante.

(j'ai lu la faq, je comptais utiliser des vector, mais je ne suis pas certain que des vector de vector soient le mieux lorsque j'aurai besoin d'un double classement)

Précision : l'optimisation n'est pas super critique non plus, mais disons que si j'ai un facteur 2 sur le temps de calcul ça commence à devenir important.

Merci beaucoup :ccool:

EDIT : petite précision : en fait je n'ai pas besoin d'utiliser des opération de tri etc... : c'est juste pour clarifier mon code et avoir 25 variables membres au lieu de 100...
03/04/2010, 18h25
bruno_pages

Bonjour,

attention, il est plus lent d'accéder à des éléments d'un vecteur stl qu'à des membres d'une structure/classes. De plus ainsi votre code va devenir illisible et peu maintenable => les problèmes empireront avec le temps

il y a beaucoup de raisons qui peuvent rendre un programme lent, en dehors des raisons d'algorithmie pure un code est lent parce que le code exécuté n'est pas directement utile pour produire le résultât mais passe par des méandres genre multiple recopies/allocations/libérations (par exemple lié à des passages de données par valeur et non par référence), mauvais choix de structure de mémorisation (par exemple utilisation d'un vecteur stl et non d'une liste alors qu'il y a constamment des ajouts/retraits dans la collection, ou recherches continuelles dans un vecteur/liste classique à la recherche d'un élément alors qu'une map aurait pu être utilisée). Ne pas rendre inline les getter (et même les setter ne faisant qu'un affectation bête) ralenti aussi, même si ce n'est pas là que la perte de temps est la plus grande.

avez-vous fait du profiling (genre g++ -pg si vous n'avez pas d'autre outils) ?
03/04/2010, 19h55
Kaluza

EDIT : je viens d'essayer le profiling sur une ancienne version du problème et c'est bien la classe d'algo qui est d'une lenteur extrême.
Ce que je prévois de faire c'est d'initialiser la classe d'algo avec mes anciennes classes, que la classe d'algo stocke tout ce qui lui faut dans des variables membres et qu'ensuite elle fasse les calculs "en interne" sans avoir besoin d'accéder sans cesse à d'autres classes.

Mon problème est le suivant : pour faire ce que j'ai décrit précédemment j'ai fait exploser le nombre de variables membres de type double (des intermédiaires de calcul) : j'ai recompté et j'en ai environ 400. Du coup, honnêtement, ça rend vraiment les choses indébuggables, complètement obscures, mais sans doute très rapides (j'ai pas essayé à la compilation parce que je n'ai pas terminé mais bon). En stockant mes variables dans des vectors (ou un autre conteneur) le code gagnerait énormément en clarté et en lisibilité. J'ai par exemple besoin de 4 double (énergie d'anisotropie de 4 macrospins) :
m_c1eani;
m_c2eani;
m_c3eani;
m_c4eani;
Si je stockais ça dans un conteneur de taille 4 en appelant ça m_eani, ça serait vachement plus lisible dans le code. Mais quel conteneur utiliser ?
03/04/2010, 21h01
bruno_pages

désolé mais présenté ainsi cela ressemble à un grand n'importe quoi

votre première réponse avant édition était que les résultât du profiling étaient étranges, c'est à dire ?

il est cependant bien difficile de plus vous aidez si vous ne publiez pas de code que l'on pourrait regarder ...
03/04/2010, 21h15
Joel F

Citation:

Envoyé par bruno_pages

attention, il est plus lent d'accéder à des éléments d'un vecteur stl qu'à des membres d'une structure/classes.

Si peu.

je pense surtout que le code du PO est peu cache-friendly.

Et si la taille est fixe, boost::array

Salut,

Si tu as un nombre fini de données, il n'y a rien à faire, l'accès aléatoire aux information proposé par un tableau est le plus rapide, si tu a les moyen de déterminer l'indice de la donnée qui t'intéresse...

De plus, il est assez facile de déduire une formule permettant de récupérer x, y ou z, si on considère que les informations sont d'office placées dans cet ordre dans un tableau:

Si x y et z sont de même type (pour l'exemple, considérons que ce sont des doubles :D), et que tu as 100 vecteurs à représenter, tu peux envisager de créer un tableau tab de... 300 double dans lequel la valeur x du premier vecteur est tab[0], la valeur y est tab[1] et la valeur z est tab[2] (respectivement tab[3],tab[4] et tab[5] pour le deuxième élément et ainsi de suite...)

Les formules de calcul d'indice sont donc relativement simples:
Code:

1 2 3 Pour calculer la position de la valeur X du vecteur V : V*3 pour calculer la position de la valeur Y du vecteur V : V*3+1 pour calculer la position de la valeur Z du vecteur V : V*3+2
A partir de là, tu peux parfaitement, au choix, utiliser un objet de type std::vector, mais tu peux aussi (bien que, bon, tu dois être conscient des limitations de chacune des possibilité) envisager l'utilisation d'un "simple" tableau C style de taille fixe, ou celle d'un tableau C style de taille dynamique..

Toujours pour un tableau de 100 vecteurs, cela donnerait:
Code:

1 2 3 4 5 6 7 8 9 10 11 /* le tableau C style de taille fixe */ double tabFixe[300]; /* le tableau C style de taille dynamique */ double *tabDyn=new double[300]; /* n'oublie pas delete[] tabDyn quand tu * n'en a plus besoin :D */ /* le beau tableau C++ */ std::vector<double> tabCpp(300); /* l'un des constructeurs de * vector permet de préciser le nombre d'éléments * qu'il contient :D */
A partir de là, l'accès se ferait de la même manière sous la forme d'un simple:
Code:

1 2 3 4 5 6 /*accéder à la valeur X du 15eme vecteur */ double x=tabCpp[14*3]; /* accéder à la valeur Y du 30eme vecteur */ double y=tabDyn[14*3+1]; /* accéder à la valeur Z du premier vecteur */ double z=tabFixe[2]; /* en fait: 0*3+2 :D */
Maintenant, cela implique que les différents vecteurs soient déjà triés... Et c'est, peut être en fait justement ton problème :question: