double[] vs valarray

Bonjour,

J'ai une question relativement bas niveau : on a fait des comparaisons de performances entre des vlarray de double et des braves tableaux de double type C' pour constater des différences de perf d'un facteur 20, environ... Est-ce qu'il existe des fortes différences de performances entre différentes implémentations de valarray ? Le choix de cette classe est sa simplicité d'écriture pour les opérations vectorielles... Bref, sinon est-ce qu'il y a une raison fondamentale qui explique qu'une classe type valarry ou vector soit tellement plus lente ? Peut-on imaginer des solutions objets rapides, si tel est le cas ?

Merci beaucoup pour toute suggestion !

Marc

Bonjour,

je n'ai jamais utilisé le valarray, mais concernant le vector
- il faut faire attention à sa taille, le remplir uniquement à coup de push_back ça entraîne de nombreux redimensionnements et copie de contenus
- l'utilisation de vector::at sera plus lente que operator[] puisque at ajoute des vérifications
- attention aux copies en paramètres de fonction => (const)&

Bonjour Bousk,

Merci pour ta réponse ! En l'occurence, il s'agit de manipuler des tableaux de dimensions fixes (3, typiquement) et de calculer des braves produits scalaires, un peu de calcul matriciel, etc, mais les valarray avait été retenus pour leur simplicité syntaxique. Du coup, la question qu'on se pose est : est-ce qu'on peut imaginer construire nous-mêmes une classe qui fasse le boulot sans une telle perte de performances ou bien vaut-il mieux revenir aux types de base du C ?

Encore merci !

Marc

Si valarray est un conteneur de la STL tu peux retrouver sa complexité pour différentes opérations.
Toutes les implémentations de valarray ont alors la même complexité.

Ensuite, pour les performances, comment avez-vous procédé pour les calculer? Une différence d'un facteur 20 me semble tout de même un peu gros.
Une mauvaise compréhension d'un conteneur peut entraîné à une mauvaise utilisation et donc à des pertes de performances.
Par exemple pour les vecteur, si on connait la taille du tableau, il faut réserver l'espace au début plutôt que de faire des push_back qui reallouera régulièrement plus d'espace comme l'a dit Bousk.


Sinon, je ne sais pas exactement quelle sera l'utilisation finale, mais je pense que le gain de temps au niveau de la programmation est beaucoup plus bénéfique qu'un gain de temps au niveau de l'exécution dans votre cas.

La question est : pourquoi tu aurais quelque chose de plus lent ?
Une classe ce n'est jamais qu'un moyen d'aggréger les données entre elles. Une classe ne rendra pas l'application particulièrement plus rapide ou lente, ce sont avant tout les algos qui jouent sur ça.
Que tu aies

Code:

---

1 2 3 4 5 6 7 8 9 10 11

struct Vector { float values[3]; Vector(float, float, float); void add(float); }; int main() { Vector v(0,1,2); v.add(4); return 1; }

---

ou

Code:

---

1 2 3 4 5 6 7

void add(float*, float); int main() { float values[3] = {0, 1, 2}; add(values, 4); return 1; }

---

c'est identique.

Quant à la performance, il faut bien se demander si elle est nécessaire et à quel point. Puis où aller la chercher.
Est-ce que ça vaut vraiment le coup d'avoir un C-array ? et tous les problèmes qui peuvent en découdre.
Pourquoi pas un std::vector correctement utilsé ?
Ou un std::array si le C++11 est utilisable.

edit: pour du calcul matriciel j'utilise glm que j'ai découverte pour openGL.

@[Hugo]
Pour ce type de problématique, tu devrais passer par un lib existante (ou au moins voir comment elles sont implémentées)

Une technique indispensable à utiliser dans ce cas, c'est les expressions template (cf Abrahams)

Ouahou, merci à tous pour vos réponses :-)

Citation:

---

Ensuite, pour les performances, comment avez-vous procédé pour les calculer?

---

A la hache : on a pris un cas et comparé le temps d'exécution avec les deux implémentations.

Citation:

---

Une différence d'un facteur 20 me semble tout de même un peu gros.

---

Indeed

Citation:

---

Une mauvaise compréhension d'un conteneur peut entraîné à une mauvaise utilisation et donc à des pertes de performances.
Par exemple pour les vecteur, si on connait la taille du tableau, il faut réserver l'espace au début plutôt que de faire des push_back qui reallouera régulièrement plus d'espace comme l'a dit Bousk.

---

On est à taille fixe, ici, donc pas de problème de ce genre.

Citation:

---

Sinon, je ne sais pas exactement quelle sera l'utilisation finale, mais je pense que le gain de temps au niveau de la programmation est beaucoup plus bénéfique qu'un gain de temps au niveau de l'exécution dans votre cas.

---

Euh, en fait on voudrait les deux : c'est pour faire du calcul massivement parallèle, à l'arrivée, et les perf sont vraiment importantes (voilà ce que ça donne quand des physiciens se mettent au C++, savent rien faire ces gens-là ;-) )

Citation:

---

Quant à la performance, il faut bien se demander si elle est nécessaire et à quel point. Puis où aller la chercher.
Est-ce que ça vaut vraiment le coup d'avoir un C-array ? et tous les problèmes qui peuvent en découdre.
Pourquoi pas un std::vector correctement utilsé ?
Ou un std::array si le C++11 est utilisable.

---

Merci pour ces pistes, on va méditer tout ça. C++11 pourrait être utilisable... Quel serait le bénéfice, ici ?

Citation:

---

edit: pour du calcul matriciel j'utilise glm que j'ai découverte pour openGL.

---

Je vais aller regarder ça. Pour le moment, tout l'algèbre est géré par lapack et on voudrait limiter le nombre de bibliothèques au minimum.

Citation:

---

Pour ce type de problématique, tu devrais passer par un lib existante (ou au moins voir comment elles sont implémentées)

Une technique indispensable à utiliser dans ce cas, c'est les expressions template (cf Abrahams)

---

OK, merci, je vais aller gratter dans cette direction !

Merci encore à tous !

Marc

Parallèle réseaux ? cluster ? multi thread ? gpu ?

au fait, tu as du code pour montrer comment tu alloues et fait les calculs ?

Citation:

---

Envoyé par [Hugo]

A la hache : on a pris un cas et comparé le temps d'exécution avec les deux implémentations.

---

Plusieurs questions se posent alors :
- Avez vous essayer sur de très grands tableaux pour obtenir des résultat cohérent?
- Avez vous bien mesuré le temps système et non le temps total ? (en effet un même algorithme peut être plus ou moins lent selon le nombre de processus actifs)
- Il aurait plutôt fallu comparer le nombre de cycle de votre CPU car le CPU adapte sa vitesse en fonction de son utilisation passée.
- Avez vous essayé sur un grand nombre d'essais et fait des moyennes ?
- Êtes-vous sûr que vos implémentations étaient optimales ?
- Avez-vous bien compilé la solution "style C" en C++ et non en C ?

Bref, je pense qu'il ne faut pas trop ce soucier de ce "facteur 20".
Je sais qu'un vecteur est légèrement plus lent que l'équivalent "style C" mais c'est plus que négligeable au dire de mon prof. de C++.


La seule chose qui importe vraiment, c'est la complexité de vos algorithmes. On peut faire toutes les optimisations que l'on souhaite, une complexité plus faible sera toujours meilleurs pour de gros calculs (à nuancer bien sûr).

La STL a l'avantage de fournir des algorithmes dont tu peux voir la complexité.

glm est header-only (puisque template)

Citation:

---

Parallèle réseaux ? cluster ? multi thread ? gpu ?

au fait, tu as du code pour montrer comment tu alloues et fait les calculs ?

---

Clusters et gros calculateurs, genre qui font péter les petaflops. Pas de GPU en perspective. Donc MPI, à coup sûr, peut-être threads et/ou openMP en plus... On va se régaler.

Sinon, je suis out pour le moment, j'essaierai de poster des bouts de code demain.

Citation:

---

Plusieurs questions se posent alors :
- Avez vous essayer sur de très grands tableaux pour obtenir des résultat cohérent?

---

Les exécutions durent quelques minutes à une demi-heure sur nos petits benchmarks, qui finissent avec quelques dizaines de degrés de liberté. Pour passer la centaine, il faut compter la journée... C'est un peu chronophage (d'où la parallélisation). Mais les tableaux dont on parle sont des vecteurs position, donc de taille 3.

Citation:

---

- Avez vous bien mesuré le temps système et non le temps total ? (en effet un même algorithme peut être plus ou moins lent selon le nombre de processus actifs)
- Il aurait plutôt fallu comparer le nombre de cycle de votre CPU car le CPU adapte sa vitesse en fonction de son utilisation passée.
- Avez vous essayé sur un grand nombre d'essais et fait des moyennes ?

---

c'est mon collègue qui a fait, mais je le soupçonne de bien travailler... je vérifierai, bonne question !

Citation:

---

- Êtes-vous sûr que vos implémentations étaient optimales ?
- Avez-vous bien compilé la solution "style C" en C++ et non en C ?

---

Nos implémentations ne sont sûrement pas encore optimales (et ça va prendre quelques années dans le meilleur des cas). Mais on aimerait régler ce "détail" qui coûte cher en réécriture quand on se plante. On a pas mal encapsuler les algo, je pense qu'on a une bonne granularité, mais avant de passer en parallèle il vaut mieux être au clair sur la structure de données, histoire de ne pas recoder le MPI tout les 36 du mois, c'est long et vraiment casse-pied. Pour ne pas dire que les bugs MPI...
Bien compilé C++, forcément, le code est globalement en C++. Ces petits tableaux ne sont que des données membres d'objets plus gros.

Citation:

---

La seule chose qui importe vraiment, c'est la complexité de vos algorithmes. On peut faire toutes les optimisations que l'on souhaite, une complexité plus faible sera toujours meilleurs pour de gros calculs (à nuancer bien sûr).

---

Je suis bien d'accord ! Mais on aimerait éviter de devoir reprendre tous les messages MPI 100 fois, et donc mieux vaut ne pas trop se planter sur ce genre de détails non plus.

Encore un grand merci à tous !!

Marc

Plusieurs remarques en vrac :
* pour la partie structure des données et algo, on est bien d'accord : lors de la parallélisation, vous devrez probablement adapter tout ça (un algo peut tout à fait être le plus efficace en mono thread et être moisi en parallèle)
* tu as déjà de libs mpi pour la structure des données
* le mot magique pour faire vos choix (structure, algo, optimisation, etc.) c'est profiling
* la différence de perfs peut s'expliquer par les copies cachés, les tests cachés, les lutins aux grandes dents cachés, bref, tout ce qui est caché (chose que tu as moins de risque d'avoir avec les tableaux style C)
* je suppose (j'espère, si vous voulez travailler sérieusement) que vous vous êtes rapproché d'une équipe de spécialistes en parallélisme ?
Si c'est pas le cas, je vous conseille fortement de le faire. Connaître les techniques, optimisations, outils, langages, etc. est un boulot à plein temps, vous allez faire des choix non optimaux si vous demander pas conseils.
Tu peux peut être contacter JoelF (http://www.lri.fr/membre.php?mb=1146)

Bon courage

Plusieurs piste :

- mpi implique des comms et ce sera trjrs le pr9bleme
- tableau. de taille fixe =std::array ensuite, les tableau de tableau ca rend le cache triste. préférez des tableaux 2d compact.

ensuite, gaffe au cache, aux copies, vectorisez etc .....

Bonjour,

Après longue absence, merci pour vos réponses !! De fait, nous travaillons avec des gens de l'INRIA, mais ces questions ne sont finalement pas aussi évidentes qu'on aurait pu l'imaginer à l'origine... Méditation in progress sur la base de vos suggestions. Je ne crois pas qu'on avait essayé les std::array !!

Marc

quelle equipe de l'INRIA ?

c'est jamais trivial l'optimisation et le parallelsime, ca se saurait :aie:

Il me semble avoir lui quelque part que le type qui a écrit les valarray les a a posteriori reniés, tellement il trouvait ça mal foutu.

Sinon, Josuttis a écrit un chapitre en consultation libre à leur sujet.

Le labri, à Bordeaux. Quant à la parallélisation... haha !! Je découvre (encore que pour le moment, ce n'est pas encore nous qui mettons la main dans le camboui, mais ça va venir).

oodni je crois avoir entendu la même histoire sur les valarray (que je n'ai pas choisis, pour ma part, et sur lesquels on est en train de revenir, je pense). Lemieux ne serait-il pas de les virer tout à fait ? Je ne sais pas s'ils sont très utilisés ?

Citation:

---

Envoyé par oodini

Sinon, Josuttis a écrit un chapitre en consultation libre à leur sujet.

---

Citation:

---

Envoyé par [Hugo

]oodni je crois avoir entendu la même histoire sur les valarray (que je n'ai pas choisis, pour ma part, et sur lesquels on est en train de revenir, je pense). Lemieux ne serait-il pas de les virer tout à fait ? Je ne sais pas s'ils sont très utilisés ?

---

Il me semble que le problème venait (un peu ? beaucoup ?) du fait que les calculs produisaient beaucoup de temporaires et de boucles cachées, donc très mauvais en terme de performances. D'après le doc de Josuttis, ce point semble corrigé.
Peu être que du coup, cela facilitera son adoption ?