temps de calcul ?

Version imprimable

01/03/2013, 18h15
thomMonteillet

temps de calcul ?

Bonjour tous,

j'ai un code C++ qui est très bien mais qui prend beaucoup de temps,
j'aimerai savoir où il passe du temps es ce que ceci est possible ?
(je suis débutant)

Sinon, avez vous quelques conseille pour gagner du temps de calcul informatiquement parlant ?

1) par exemple je fais toujours des boucles "for i=1..." et une fois quelqu'un m'a dit d''utiliser "BOOST" or je ne l'ai jamais fait car je ne sais pas comment ça marche... es ce vraiment utile ?

2) Dans mon programme j'écris aussi pas mal de fichier texte, es ce qu'il y a une astuce là aussi pour gagner du temps ?
Moi en général à chaque itération de mon programme j'ouvre un fichier, j'écris dedans et je le referme. Peux etre que je devrais l'ouvrir et ne le refermer qu'à la fin de tout les calculs ?

3) j'ai entendu parlé de parallélisation mais ça me sembe un peu compliqué, auriez vous des conseils pour débuter dans ce domaine ? que faut il utiliser ? j'ai cru comprendre que MPI c'etait tres bien ???

merci grandement pour l'aide que vous pourrez m'apporter !
01/03/2013, 18h32
Joker-eph

Citation:

Envoyé par thomMonteillet

Bonjour tous,

j'ai un code C++ qui est très bien mais qui prend beaucoup de temps,
j'aimerai savoir où il passe du temps es ce que ceci est possible ?
(je suis débutant)

Oui, on appelle ça du profiling. Voir gprof, cachegrind, intel Vtune (payant) par exemple.

Citation:

1) par exemple je fais toujours des boucles "for i=1..." et une fois quelqu'un m'a dit d''utiliser "BOOST" or je ne l'ai jamais fait car je ne sais pas comment ça marche... es ce vraiment utile ?

Boost n'a rien à voir avec le fait de faire des boucles sur des entiers. Ce serait long d'expliquer ce qu'est Boost, comment par lire la page wikipedia ou la doc de Boost.

Citation:

2) Dans mon programme j'écris aussi pas mal de fichier texte, es ce qu'il y a une astuce là aussi pour gagner du temps ?
Moi en général à chaque itération de mon programme j'ouvre un fichier, j'écris dedans et je le referme. Peux etre que je devrais l'ouvrir et ne le refermer qu'à la fin de tout les calculs ?

Oui il faut éviter d'ouvrir/fermer, mais également éviter d'écrire autant que possible. Si tu n'a pas grand chose à écrire, peut-être que tu peux tout garder en mémoire pendant plusieurs itérations et écrire de temps en temps seulement.

Citation:

3) j'ai entendu parlé de parallélisation mais ça me sembe un peu compliqué, auriez vous des conseils pour débuter dans ce domaine ? que faut il utiliser ? j'ai cru comprendre que MPI c'etait tres bien ???

Il y a tellement de choses à faire avant de paralléliser, c'est vraiment la dernière chose que tu veux faire !
MPI est utilisé pour distribuer les données, en général sur un cluster de plusieurs machines. Pour exploiter un processeur multi-coeurs, on peut faire de l'OpenMP par exemple, ou du TBB, etc.
Ne pas oublier la vectorisation également...
01/03/2013, 18h52
thomMonteillet

merci énormement de prendre le temps de m'aider!!!

Citation:

Envoyé par Joker-eph

Oui, on appelle ça du profiling. Voir gprof, cachegrind, intel Vtune (payant) par exemple.

OK, je vais regarder. Es ce facile à utiliser pour un débutant ? es ce qu'il y a des choses qui sont dépendante de l'IDE ? moi j'utilise souvent Qt ou codeBlock...

Citation:

Envoyé par Joker-eph

Boost n'a rien à voir avec le fait de faire des boucles sur des entiers. Ce serait long d'expliquer ce qu'est Boost, comment par lire la page wikipedia ou la doc de Boost.

ah ok, j'avais cru comprendre que dans boost il y a des trucs qui s'appel "itérateurs" et que soit disant ça ferait gagner pas mal de temps si on met ceci dans toutes les boucles....

Citation:

Envoyé par Joker-eph

Oui il faut éviter d'ouvrir/fermer, mais également éviter d'écrire autant que possible. Si tu n'a pas grand chose à écrire, peut-être que tu peux tout garder en mémoire pendant plusieurs itérations et écrire de temps en temps seulement.

ah oui c'est une bonne idée !

Citation:

Envoyé par Joker-eph

Il y a tellement de choses à faire avant de paralléliser, c'est vraiment la dernière chose que tu veux faire !
MPI est utilisé pour distribuer les données, en général sur un cluster de plusieurs machines. Pour exploiter un processeur multi-coeurs, on peut faire de l'OpenMP par exemple, ou du TBB, etc.
Ne pas oublier la vectorisation également...

- en fait j'ai parlé de ceci car j'ai des taches qui se font totalement indépemment l'une de l'autre.
- du coup je me suis dis vu que mes taches sont compléments découplées si je pouvais les lancer sur trois PC mon programme irait 3fois plus vite ?

au fait qu'appel tu vectorisation ?
01/03/2013, 19h53
gbdivers

Oublie tes points 1, 2 et 3 et concentre toi sur le profiling pour commencer. C'est ça qui va t'indiquer les améliorations à apporter, toutes autres amélioration "a priori" risque d'être une perte de temps car non adapté à ton programme

vectorisation : utilisation des instructions de calcul parallèle CPU (SSE)
01/03/2013, 20h18
thomMonteillet

d'accord, merci.

Profiler:
quel est le profiler que vous me conseillerez ? avez vous un tuto qui explique comment s'en servir ?

Parallélisation:
par contre je suis certain que la parallélisation va me faire gagner du temps car voici comment mon code fonctionne :

- j'ai un objet "A" à qui on fourni à travers la méthode "input" un vecteur
- en sortie cet objet "A" à travers la méthode "output" me donne une matrice "B"
- et je peux avoir environ 80000 objets "A" différents. ce que je fais pour le moment c'est une boucle: pour le premier objet je fais le calcul, une fois fini je fais le calcul avec le 2eme objet, une fois fini avec le troisième...etc
- si je fais les choses en parallèle il est clair que je vais gagner du temps vu que mes objets sont totalement indépendants :zoubi:
02/03/2013, 02h36
koala01

Salut,

On peut déjà te donner quelques astuces cependant:

Essayes de passer tous les arguments qui ne sont pas des type primitifs par référence (éventuellement constante si la fonction qui les prend ne doit pas les modifier) et non par valeur: cela t'évitera bien des copies inutiles, et t'apportera sans doute un gain énorme tant en terme de temps d'exécution qu'en terme d'utilisation de mémoire.

Essayes de limiter au maximum les accès en lecture ou en écriture à des fichiers: les disques durs ont, vraiment, des performances catastrophiques comparé à la RAM, sans oublier qu'il faut fatalement un certain temps pour accéder aux endroits où se trouvent les fichiers sur le disque dur (déplacement des tête de lecture, fin du tour pour accéder à l'endroit exact, etc)

Vérifie tes algorithmes, il est souvent "facile" de gagner en performances en évitant d'entrer dans une boucle ou en faisant les choses "dans le bon ordre" ;) (mais le profiling te dira surement où il est intéressant de revoir l'algorithme :D) et quand tu crois avoir fini, revérifie les :D

Pour ce qui est du profiling, cela dépend énormément des outils que tu utilises:

La chaine de compilation Gcc vient, par exemple, avec un programme nommé gprof qui sert souvent de base au profiling, alors que certains outils sont prévus pour fonctionner avec Visual Studio et d'autres encore avec d'autres chaine d'outils ;)
02/03/2013, 04h38
Joker-eph

Citation:

Envoyé par thomMonteillet

- j'ai un objet "A" à qui on fourni à travers la méthode "input" un vecteur
- en sortie cet objet "A" à travers la méthode "output" me donne une matrice "B"
- et je peux avoir environ 80000 objets "A" différents. ce que je fais pour le moment c'est une boucle: pour le premier objet je fais le calcul, une fois fini je fais le calcul avec le 2eme objet, une fois fini avec le troisième...etc
- si je fais les choses en parallèle il est clair que je vais gagner du temps vu que mes objets sont totalement indépendants :zoubi:

OpenMP pour ta boucle sur les 80000 objets (gros grain), et SSE/AVX/Whatever pour les traitement à l'intérieur des objets (grain fin).
Encore une fois, c'est à la fin...
02/03/2013, 11h03
thomMonteillet

salut tous et merci pour vos conseils !

Citation:

Envoyé par koala01

Essayes de passer tous les arguments qui ne sont pas des type primitifs par référence (éventuellement constante si la fonction qui les prend ne doit pas les modifier) et non par valeur: cela t'évitera bien des copies inutiles, et t'apportera sans doute un gain énorme tant en terme de temps d'exécution qu'en terme d'utilisation de mémoire.

oui, c'est que que je fais actuellement (je le fais pour toutes les variables, du double/int aux vector et objets).

Citation:

Envoyé par koala01

Essayes de limiter au maximum les accès en lecture ou en écriture à des fichiers: les disques durs ont, vraiment, des performances catastrophiques comparé à la RAM, sans oublier qu'il faut fatalement un certain temps pour accéder aux endroits où se trouvent les fichiers sur le disque dur (déplacement des tête de lecture, fin du tour pour accéder à l'endroit exact, etc)

ça c'est une bonne idée que je vais m'empresser de faire.

Citation:

Envoyé par koala01

Vérifie tes algorithmes, il est souvent "facile" de gagner en performances en évitant d'entrer dans une boucle ou en faisant les choses "dans le bon ordre" ;) (mais le profiling te dira surement où il est intéressant de revoir l'algorithme :D) et quand tu crois avoir fini, revérifie les :D

Moi, je vais reparcourir tous mon programme et vérifier ceci.
en fait ce qui est le plus long dans un programme c'est les boucles ?
par exemple si j'ai plusieurs "if" imbriqués ça prend pas trop de temps ?
(j'ai fais attention pour les boucles mais les "if" j'en ai mis plein car sans forcement optimiser...)

au fait la perrsonne qui m'avait dit d'utiliser des "itérateur" à la place de mes boucles "for" classique m'avait dit n'importe quoi ? on gagne pas forcement en temps de calcul ? (ou ce n'est pas significatif en tout cas?)

Citation:

Envoyé par koala01

Pour ce qui est du profiling, cela dépend énormément des outils que tu utilises:
La chaine de compilation Gcc vient, par exemple, avec un programme nommé gprof qui sert souvent de base au profiling, alors que certains outils sont prévus pour fonctionner avec Visual Studio et d'autres encore avec d'autres chaine d'outils ;)

D'accord, je vais me tourner vers "gprof" je pense car ça fait plusieurs fois que je le vois passer ;) (en plus je déteste visual studio)

Citation:

Envoyé par Joker-eph

OpenMP pour ta boucle sur les 80000 objets (gros grain), et SSE/AVX/Whatever pour les traitement à l'intérieur des objets (grain fin). Encore une fois, c'est à la fin...

OK, merci pour le conseil
02/03/2013, 11h14
JolyLoic

Citation:

Envoyé par thomMonteillet

par contre je suis certain que la parallélisation va me faire gagner du temps car voici comment mon code fonctionne :

- j'ai un objet "A" à qui on fourni à travers la méthode "input" un vecteur
- en sortie cet objet "A" à travers la méthode "output" me donne une matrice "B"
- et je peux avoir environ 80000 objets "A" différents. ce que je fais pour le moment c'est une boucle: pour le premier objet je fais le calcul, une fois fini je fais le calcul avec le 2eme objet, une fois fini avec le troisième...etc
- si je fais les choses en parallèle il est clair que je vais gagner du temps vu que mes objets sont totalement indépendants :zoubi:

Ce n'est pas si évident que tu gagnes du temps : Si à l'intérieur de ton traitement, tu accèdes à une ressource partagée, par exemple le disque dur, il y a des chances que si tu parallélises, tout le temps soit passé à attendre cette ressource. Un cas plus courant der essource partagée pouvant insidieusement plomber les performances en parallèle est la mémoire cache.

Ensuite, tu ne gagneras pas plus de temps que le nombre de processeurs de ta machine. Ce qui peut te sembler très bien (et l'est probablement), mais n'a d'intérêt que si à la base tu pars de code qui est déjà raisonnablement optimal. Si tes algorithmes sont mauvais, les remplacer peut provoquer des gains très importants (j'ai déjà gagnée des *1000 pour 1h de travail...) et d'autant plus importants que ton volume de données est grand. Ensuite, travailler en gérant bien la mémoire cache/la mémoire/le disque peut aussi avoir des impacts importants, minimiser le nombre d'allocations mémoire aussi.

Une fois que ce sera fait, il sera temps de regarder la parallélisation, qui est plus complexe à mettre en place, et qui en plus a besoin des améliorations citées au dessus pour pouvoir vraiment être rentable.
02/03/2013, 11h14
thomMonteillet

Citation:

Envoyé par JolyLoic

Ce n'est pas si évident que tu gagnes du temps : Si à l'intérieur de ton traitement, tu accèdes à une ressource partagée, par exemple le disque dur, il y a des chances que si tu parallélises, tout le temps soit passé à attendre cette ressource. Un cas plus courant der essource partagée pouvant insidieusement plomber les performances en parallèle est la mémoire cache.

d'accord. je pense avoir compris.

Citation:

Envoyé par JolyLoic

travailler en gérant bien la mémoire cache/la mémoire/le disque peut aussi avoir des impacts importants, minimiser le nombre d'allocations mémoire aussi.

que veux tu dire par minimiser le nombre d'allocations mémoire ? minimiser le nombre de variables ? ou minimiser le nombre d'allocations dynamiques ?

mémoire cache c'est bien mémoire RAM ? le disque OK. Mais qu'appel tu mémoire ? pour moi il y a juste mémoire RAM et disque non ?

Citation:

Envoyé par JolyLoic

Une fois que ce sera fait, il sera temps de regarder la parallélisation, qui est plus complexe à mettre en place, et qui en plus a besoin des améliorations citées au dessus pour pouvoir vraiment être rentable.

j'ai une dernière question sur le parallélisme afin de comprendre ce que c'est:
il y a en gros trois façon de procéder :
1) si un a un PC avec plusieurs processeurs on va faire du multithread et le programme va envoyer vers chaque processeurs une partie du calcul.
2) si on a d'autres PC sous la main, ou un cluster. On peut faire une parallélisation qui va envoyer des calculs sur chacunes des mémoires disponibles sur les autres PC, c'est ce que l'on appel la mémoire distribuée? (et ceci on ne le fait pas avec du multithread mais plutot avec des messages comme MPI ?)
3) la dernière méthode est la même que la 2) mais les différentes mémoires disponibles sont regroupées donc on parle de mémoire partagée.

Si je fais un programme en multithread pourra t il être utilisé ensuite pour faire du 2) et 3) ? à mon avis non ?
et vis et versa, si je fais un programme pour 2) sera t il utilisable par 3) et 1) ?

je voudrais juste comprendre les différentes parallélisation qui existe (et pourquoi utiliser l'une plutôt que l'autre). merci
02/03/2013, 19h11
Joker-eph

Citation:

Envoyé par thomMonteillet

salut tous et merci pour vos conseils !

oui, c'est que que je fais actuellement (je le fais pour toutes les variables, du double/int aux vector et objets).

Je ne vois pas l'intérêt pour les types primitifs, ni même pour un objet très petit d'ailleurs, ça risque plutôt d'être contre-productif.

Citation:

Moi, je vais reparcourir tous mon programme et vérifier ceci.
en fait ce qui est le plus long dans un programme c'est les boucles ?
par exemple si j'ai plusieurs "if" imbriqués ça prend pas trop de temps ?
(j'ai fais attention pour les boucles mais les "if" j'en ai mis plein car sans forcement optimiser...)

Les if sont potentiellement coûteux, mais seulement s'ils sont sur un chemin critique.

Citation:

au fait la perrsonne qui m'avait dit d'utiliser des "itérateur" à la place de mes boucles "for" classique m'avait dit n'importe quoi ? on gagne pas forcement en temps de calcul ? (ou ce n'est pas significatif en tout cas?)

Ce n'est pas automatique, ça dépend sur quoi tu itères, et quel types d'opération tu fais dans la boucle sur ton conteneur.
A la base il n'y a jamais de recettes magique, il faut que tu cherches plutôt à comprendre ce qui se passe et quelle est la différence en terme d'exécution.

Ça rejoint le fait de passer des int par const ref pour gagner du temps parce que quelqu'un aura dit que les references constantes c'est plus rapide :aie:

Citation:

Envoyé par thomMonteillet

que veux tu dire par minimiser le nombre d'allocations mémoire ? minimiser le nombre de variables ? ou minimiser le nombre d'allocations dynamiques ?

new/delete (malloc/free). Genre ne pas faire ça dans une boucle.

Citation:

mémoire cache c'est bien mémoire RAM ? le disque OK. Mais qu'appel tu mémoire ? pour moi il y a juste mémoire RAM et disque non ?

Non pas du tout, il y a plusieurs niveaux de mémoire. Google "mémoire cache" et wikipedia doit sortir en premier : http://fr.wikipedia.org/wiki/M%C3%A9moire_cache

Citation:

j'ai une dernière question sur le parallélisme afin de comprendre ce que c'est:
il y a en gros trois façon de procéder :
1) si un a un PC avec plusieurs processeurs on va faire du multithread et le programme va envoyer vers chaque processeurs une partie du calcul.
2) si on a d'autres PC sous la main, ou un cluster. On peut faire une parallélisation qui va envoyer des calculs sur chacunes des mémoires disponibles sur les autres PC, c'est ce que l'on appel la mémoire distribuée? (et ceci on ne le fait pas avec du multithread mais plutot avec des messages comme MPI ?)
3) la dernière méthode est la même que la 2) mais les différentes mémoires disponibles sont regroupées donc on parle de mémoire partagée.

La 3 n'existe pas (en pratique). Le 1 est un modèle à mémoire partagée.

Citation:

Si je fais un programme en multithread pourra t il être utilisé ensuite pour faire du 2) et 3) ? à mon avis non ?
et vis et versa, si je fais un programme pour 2) sera t il utilisable par 3) et 1) ?

Oui, c'est orthogonal, sachant que 2) est un peu plus difficile que 1).

Citation:

je voudrais juste comprendre les différentes parallélisation qui existe (et pourquoi utiliser l'une plutôt que l'autre). merci

Ne pas oublier la vectorisation (SSE/AVX), ça peut offrir un gain intéressant selon le type de calcul.
02/03/2013, 19h46
thomMonteillet

Citation:

Envoyé par Joker-eph

Je ne vois pas l'intérêt pour les types primitifs, ni même pour un objet très petit d'ailleurs, ça risque plutôt d'être contre-productif.

En fait je me suis dis que ça pouvais être bien d'avoir des références car ça permet d'être certain que l'on travail bien sur la valeur original et non une copie. Ensuite, je les mets le plus souvent possible en constante afin de ne pas avoir de problèmes lorsque j'echange des données entre fonctions.

mais si c'est réellement couteux en temps de calcul je vais enlever ceci :ccool:

Citation:

Envoyé par Joker-eph

Les if sont potentiellement coûteux, mais seulement s'ils sont sur un chemin critique.

qu'appel tu chemin critique ? un endroit où une boucle passe plusieurs fois ?

Citation:

Envoyé par Joker-eph

Ce n'est pas automatique, ça dépend sur quoi tu itères, et quel types d'opération tu fais dans la boucle sur ton conteneur.
A la base il n'y a jamais de recettes magique, il faut que tu cherches plutôt à comprendre ce qui se passe et quelle est la différence en terme d'exécution.

d'accord, donc si je n'utilise pas d'itérateurs ça va pas changer grand chose.
je zap les itérateurs alors et je reste avec mes boucles.

Citation:

Envoyé par Joker-eph

new/delete (malloc/free). Genre ne pas faire ça dans une boucle.

ça marche, merci du conseil :)
en fait je n'utilise jamais ceci car je travail avec des "vector" (donc je ne dois ne pas les initialisez dans des boucles si j'ai bien compris).

Citation:

Envoyé par Joker-eph

Non pas du tout, il y a plusieurs niveaux de mémoire. Google "mémoire cache" et wikipedia doit sortir en premier : http://fr.wikipedia.org/wiki/M%C3%A9moire_cache

d'accord, je vais regarder. merci

Citation:

Envoyé par Joker-eph

La 3 n'existe pas (en pratique). Le 1 est un modèle à mémoire partagée.
Oui, c'est orthogonal, sachant que 2) est un peu plus difficile que 1).
Ne pas oublier la vectorisation (SSE/AVX), ça peut offrir un gain intéressant selon le type de calcul.

je vais regarder merci !