Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
1913 connectés 

  FORUM HardWare.fr
  Programmation
  C++

  Performance des boucles for avec la STL

 
 


 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

Performance des boucles for avec la STL

n°1954286
toonj
Posté le 31-12-2009 à 16:56:37  profilanswer
 

Bonjour,
 
J'ai un programme qui fait des boucles for en cascade, sur 3 niveaux
1er niveau (le plus haut) : environ 50 boucles **Edit 50 et non 5**
2eme niveau : environ 5 boucles
3eme niveau : environ 15 boucles
 
soit environ 3750 passages au niveau le plus bas
 
se sont des boucles sur des itérateurs de deque
 
genre

Code :
  1. for (std::deque<pCollider>::iterator pCollIter = pObjIter+1; pCollIter!= (*rawMapIter).second.end(); ++pCollIter)


 
J'ai relevé les temps suivant pour le parcours de la boucle
nbr passage au niveau le plus bas    -temps de parcours en s
3530                                               0.141
3600                                               0.094
3592                                               0.093
3629                                               0.11
3647                                               0.094
 
soit environ 1/10 eme de seconde
 
Ces temps me paraissent assez long surtout que je ne fait rien pour le moment dans la boucle (juste un i++)
Pensez vous qu'ils sont raisonnables ? (Est ce que l'ordre de grandeur est normal?)
 
Peut on l'optimiser ?
Si oui, quelle(s) methode(s) conseillez vous avec la bibliothèque stl ? (des astuces pour optimiser les traitement itératif avec la stl)
 
Question bonus : qu'est ce qui coute du temps dans une boucle ? l'incrément de l'itérateur ? les tests de condition de fin ?
 
Précision : j'ai un intelcore 2 Duo 7200T avec XP


Message édité par toonj le 02-01-2010 à 13:49:27
mood
Publicité
Posté le 31-12-2009 à 16:56:37  profilanswer
 

n°1954308
theShockWa​ve
I work at a firm named Koslow
Posté le 31-12-2009 à 19:09:54  profilanswer
 

au moins précalculer l'itérateur de fin, peut-être ? (stocker dans une variable locale ton (*rawMapIter).second.end(); )
 
Sinon, les optimisations vont plutôt être d'ordre algorithmiques, en règle générale.
 
On peut espérer que ce qui prend du temps dans la boucle, ce sera justement le traitement que tu fais dans le corps. Si jamais le traitement que tu fais dans le corps de ta boucle commence à devenir comparable au temps d'incrémentation de ton itérateur et de saut dans ta boucle, il faudra chercher à dérouler ta boucle et incrémenter ton itérateur par plus grands pas.


---------------
last.fm
n°1954309
__tomjost
c'est un pseudo !
Posté le 31-12-2009 à 19:14:37  profilanswer
 

ce n'ait pas comme for(i=0;i<5;++i) , c'est plus lent!
 
declare les suivant as constant , ou calcule les avant la loop (si possible) :  
 
1/ (*rawMapIter).second.end();
2/ pObjIter+1
 
comment tu a mesurer (avec quoi) ?
et les 2 core functionnent ?
(test et poste les resultat ici , je veut voir ce qu'on gagne)  
 
:)

Message cité 1 fois
n°1954311
__tomjost
c'est un pseudo !
Posté le 31-12-2009 à 19:19:12  profilanswer
 

Sorry theshockwave ,   :D  
jai pas vu ta response quand je vien d'ecrire mas response
 

n°1954312
theShockWa​ve
I work at a firm named Koslow
Posté le 31-12-2009 à 19:22:40  profilanswer
 

__tomjost a écrit :

ce n'ait pas comme for(i=0;i<5;++i) , c'est plus lent!
 
declare les suivant as constant , ou calcule les avant la loop (si possible) :  
 
1/ (*rawMapIter).second.end();
2/ pObjIter+1
 
comment tu a mesurer (avec quoi) ?
et les 2 core functionnent ?
(test et poste les resultat ici , je veut voir ce qu'on gagne)  
 
:)


 
L'instruction d'initialisation de la boucle n'est pas exécutée à chaque tour, donc on s'en fiche.
Le mylti threading n'est vraisemblablement pas le sujet ici.


---------------
last.fm
n°1954325
__tomjost
c'est un pseudo !
Posté le 31-12-2009 à 21:14:51  profilanswer
 

ca depend du compiler
.. pourqoui pas essayer sur un pentium4 normal
et comparer , ... 1/10 seconde c'est trop!
 (c'est pas 10Hz ????? :heink: )

n°1954356
Joel F
Real men use unique_ptr
Posté le 01-01-2010 à 13:10:20  profilanswer
 

encore une fois, tu racontes n'importe quoi. le multithreading n'a aucun rapport avec la choucroute.  
 
Le probleme ici est tres certainement le calcul de l'iterateur de foin qui n'est pas vu comme un invariant de boucle.
Je conseillerais aussi à l'OP d'utiliser std::for_each, std::accumulate et autres algorithmes de la STL plutot que de faire des boucles for.

Message cité 1 fois
n°1954378
Un Program​meur
Posté le 01-01-2010 à 15:42:13  profilanswer
 

Première question, est-ce que c'est bien du code optimisé?
Deuxièmement, comment est-ce que tu mesures le temps (50% en plus quand on diminue le nombre d'éléments de 2%, pour une opération qui ne dépend pas d'IO, ça fait penser à un problème méthodologique dans la mesure tant qu'on n'a pas une explication).


---------------
The truth is rarely pure and never simple (Oscar Wilde)
n°1954386
__tomjost
c'est un pseudo !
Posté le 01-01-2010 à 17:40:35  profilanswer
 


Pas de repsonse de toonj?
 

Joel F a écrit :

multithreading n'a aucun rapport.....


a propos de multithreading , je ne parle pas des  
thread ,...jai dit peut etre le processeur
va diviser le travail de cette loop en quelque maniere
entre les core ... ok je nsai rien de ces double core! :(  
Je vit encore avec P4 2.8Ghz et pas de problem. :)  

Message cité 1 fois
n°1954390
Dion
Acceuil
Posté le 01-01-2010 à 18:06:10  profilanswer
 

moi je tombe sur 375 et pas 3750 :o


---------------
When it comes to business/legal topics, just assume almost everyone commenting has no idea what they’re taking about and have no background in these subjects because that’s how it really is. Harkonnen 8-> Elmoricq 8====>
mood
Publicité
Posté le 01-01-2010 à 18:06:10  profilanswer
 

n°1954446
toonj
Posté le 02-01-2010 à 14:22:09  profilanswer
 

En fait au 1er niveau c'est 50 boucles.
Pour le calcul, j'ai utiliser la time. et la fonction clock();  

Code :
  1. t1 = clock();
  2. //boucles
  3. t2=clock();
  4. t= (t2-t1)/CLOCKS_PER_SEC


 
pour compiler, j'utilise Visual Studio 2008
 
Remarque de nullos : en testant sans le mode debug :whistle:  je gagne facilement  un facteur 2 à 3 !!!
et donc je tourne aux environs de 0.040 ...  
N'empêche que je me serai attendu à des temps beaucoup plus faible quand même (de l''ordre du 1000ème de seconde), mais peut être que je phantasme un peu et que compte tenu du code (ci-après) et des outils utilisés cela est cohérent... Qu'en pensez vous ?
 
mon code exact est :

Code :
  1. t1 = clock();
  2.    for (rawMapBox::iterator rawMapIter = _rawMap.begin(); rawMapIter != _rawMap.end(); ++rawMapIter)
  3.    {//50 boucles environ
  4.       std::deque<pCollider> localObjList = (*rawMapIter).second;
  5.       for (std::deque<pCollider>::iterator pObjIter = (*rawMapIter).second.begin(); pObjIter!= (*rawMapIter).second.end(); ++pObjIter)
  6.       {//5 boucles environ
  7.           for (std::deque<pCollider>::iterator pCollIter = pObjIter+1; pCollIter!= (*rawMapIter).second.end(); ++pCollIter)
  8.          {//3 boucles environ
  9.             ++iii;
  10.          }
  11.          std::map<Point2D, std::deque<pCollider>>::iterator mapiter =_rawMap.find((*rawMapIter).first +Point2D(1,0));
  12.          if (mapiter != _rawMap.end() )
  13.          {
  14.             std::deque<pCollider> neigtboorObjList = (*mapiter).second;
  15.             for (std::deque<pCollider>::iterator pCollIter = neigtboorObjList.begin(); pCollIter< neigtboorObjList.end(); ++pCollIter)
  16.            {//3 boucles environ
  17.               ++iii;
  18.            }
  20.         }
  21.         mapiter =_rawMap.find((*rawMapIter).first +Point2D(-1,1));
  22.         if (mapiter != _rawMap.end() )
  23.         {
  24.            std::deque<pCollider> neigtboorObjList = (*mapiter).second;
  25.            for (std::deque<pCollider>::iterator pCollIter = neigtboorObjList.begin(); pCollIter< neigtboorObjList.end(); ++pCollIter)
  26.            {//3 boucles environ
  27.               ++iii;
  28.            }
  29.         }
  30.         mapiter =_rawMap.find((*rawMapIter).first +Point2D(0,1));
  31.         if (mapiter != _rawMap.end() )
  32.         {
  33.            std::deque<pCollider> neigtboorObjList = (*mapiter).second;
  34.            for (std::deque<pCollider>::iterator pCollIter = neigtboorObjList.begin(); pCollIter< neigtboorObjList.end(); ++pCollIter)
  35.            {//3 boucles environ
  36.               ++iii;
  37.            }
  38.         }
  39.         mapiter =_rawMap.find((*rawMapIter).first +Point2D(1,1));
  40.         if (mapiter != _rawMap.end() )
  41.         {
  42.            std::deque<pCollider> neigtboorObjList = (*mapiter).second;
  43.            for (std::deque<pCollider>::iterator pCollIter = neigtboorObjList.begin(); pCollIter< neigtboorObjList.end(); ++pCollIter)
  44.            {//3 boucles environ(soit au total 5x3 = 15 boucles au niveau le plus bas
  45.               ++iii;
  46.            }
  47.         }
  48.       }
  49.    }
  50.    t2 = clock();


il est pas remanié volontairement, donc légèrement imbitable, mais peut être cela donnera des pistes

n°1954452
Un Program​meur
Posté le 02-01-2010 à 15:13:55  profilanswer
 

1/ Est-ce que quelqu'un a une idée de la précision de clock() sous Windows?  (la résolution est de 1ms, mais j'ai déjà vu des compteurs de temps avec une résolution supérieure à la précision).
 
2/ Tu es au mieux à 40 fois la précision, ça me semble assez faible si tu veux des mesures précises (surtout que je ne serais étonné que la précision soit toujours un 1/18 e ou a peu près hérité de DOS)
 
3/ Tu fais plus qu'itérer, tu as aussi une série de find dans des map qui ont un temps dépendant du nombre d'entrées dedans.  Pour plus de 8, ça ne m'étonnerais pas que ces finds prennent plus de temps que les itérations qui suivent (tu déclares qu'il n'y en a qu'environ 3...)
 
4/ Attention au cache, j'ai pas des chiffres précis en tête, mais j'ai en mémoire un rapport 100 entre le cache le plus rapide et la mémoire externe.

Message cité 1 fois

---------------
The truth is rarely pure and never simple (Oscar Wilde)
n°1954466
Joel F
Real men use unique_ptr
Posté le 02-01-2010 à 16:13:43  profilanswer
 

Un Programmeur a écrit :


1/ Est-ce que quelqu'un a une idée de la précision de clock() sous Windows?  (la résolution est de 1ms, mais j'ai déjà vu des compteurs de temps avec une résolution supérieure à la précision).


clock est a chier sous WiN32, il faut lui rpeferer QueryPerformanceCounter
 

Un Programmeur a écrit :


3/ Tu fais plus qu'itérer, tu as aussi une série de find dans des map qui ont un temps dépendant du nombre d'entrées dedans.  Pour plus de 8, ça ne m'étonnerais pas que ces finds prennent plus de temps que les itérations qui suivent (tu déclares qu'il n'y en a qu'environ 3...)


les find des map sont en o(log N) de mémoire donc oui, ca coute au bout d'un moment
 

Un Programmeur a écrit :


4/ Attention au cache, j'ai pas des chiffres précis en tête, mais j'ai en mémoire un rapport 100 entre le cache le plus rapide et la mémoire externe.


Ca depend des archis, ca oscille entre 15 et 350 selon l'archi et le niveau de cache

n°1954518
toonj
Posté le 02-01-2010 à 21:59:28  profilanswer
 

J'ai tout refait avec des for_each et des foncteurs
j'obtiens maintenant un temps quasi constant de 0.015s (comme c'est à peu près le même quel que soit le nombre de boucle (2000 ou 4000) j'en déduis que c'est la précision de la mesure
Surtout que je suis toujours en debug et que j'ai ajouté un peu du traitement au plus bas niveau de la boucle.
 
Conclusion : utiliser for_each
 
Cela soulève d'autres pbs que j'ai abordé dans un nouveau topic Enchainer les for_each de la Stl
http://forum.hardware.fr/hfr/Progr [...] m#t1954517
 
avis à ceux qui peuvent m'aider, et merci pour ce topic

n°1954527
bjone
Insert booze to continue
Posté le 03-01-2010 à 01:19:58  profilanswer
 

On ne bench pas en debug...

n°1954540
GrosBocdel
Posté le 03-01-2010 à 09:25:12  profilanswer
 

Pourquoi est-ce qu'un for_each devrait être plus rapide qu'une boucle for?
 

n°1954541
Joel F
Real men use unique_ptr
Posté le 03-01-2010 à 09:40:17  profilanswer
 

Certaines implémentations de la STL font des optimisations en fonctions des propriétés des types ou tente de dérouler.

n°1956328
el muchach​o
Comfortably Numb
Posté le 09-01-2010 à 10:00:59  profilanswer
 

__tomjost a écrit :


Pas de repsonse de toonj?
 


 

__tomjost a écrit :


a propos de multithreading , je ne parle pas des  
thread ,...jai dit peut etre le processeur
va diviser le travail de cette loop en quelque maniere
entre les core ... ok je nsai rien de ces double core! :(  
Je vit encore avec P4 2.8Ghz et pas de problem. :)  


OMG un double core, ce sont deux processeurs identiques sur la même puce, c'est tout. Si tu n'as pas de threads, ton code s'exécute sur un seul core.

Message cité 1 fois

---------------
Les aéroports où il fait bon attendre, voila un topic qu'il est bien
n°1956329
Joel F
Real men use unique_ptr
Posté le 09-01-2010 à 10:04:04  profilanswer
 

el muchacho a écrit :


OMG un double core, ce sont deux processeurs identiques sur la même puce, c'est tout. Si tu n'as pas de threads, ton code s'exécute sur un seul core.


 
J'avais pas relevé  :sweat:

n°1958601
__tomjost
c'est un pseudo !
Posté le 18-01-2010 à 20:35:01  profilanswer
 

j'ai essayer hier un code sur un double-core (tres retarder... :sleep: )
 
pour le double core (ou +), la creation des thread  
est automatiser (plus facile) , ou le compiler a son mode
pour parallelizer les section du code ou on utilise l'openmp
(ca se control par les params du compiler )
 
ca s'applle work-sharing , j'ai etait pas loin du tout
 
pour l'openmp on ajoute :
 
#pragma omp parallel for num_threads(2) , ... il ya d'autre option de control
for(){
 #pragma ...optional ici
 for(){
 }
}  
 
... ne prenez pas ca au serieux ,
je ne suis pas entrain de passer des examens.
 
au revoir ! :hello:
 
[EDIT : rien! , j'ajoute "parallel" entre "omp" et "for" ,voir le spec 2.5 pour les details]


Message édité par __tomjost le 23-01-2010 à 21:36:17
n°1958607
Joel F
Real men use unique_ptr
Posté le 18-01-2010 à 20:46:52  profilanswer
 

c'est tout sauf du work sharing punaise ...  
quand tu essaye d'avoir l'air caler, renseigne toi mieux :€

Message cité 1 fois
n°1958617
__tomjost
c'est un pseudo !
Posté le 18-01-2010 à 22:11:05  profilanswer
 

Joel F a écrit :

c'est tout sauf du work sharing punaise ...  
quand tu essaye d'avoir l'air caler, renseigne toi mieux :€


 le dictionaire dit:  punaise = bug  
 
 je suis un bug !! , merci Joel F!  :jap:  
 
 Ignorant , j'ai tester ca!  :fou:  
 si tu nage encore en boost et Nt2 , j'ai plusieurs
 domaine a m'occuper , et je ne doit pas me concentrer
 sur des chose qu'on est sur d'apprendre en deux jour.
 
 ton but est d'avoir un leader-ship ou quoi sur ce forum ?
 j'ai remarquer ca des le debut , mais tu es trop
 superficiel avec trop d'euphorie!!
 
 j'essaye toujours a calmer les chose , mais...
 Ok je vous laisse , ENJOY!
 
 le probleme qu'il ne me connait pas ...
 peut etre il regarde les smilies et essaye d'imaginer!  :lol:  
 
Quel type !!
 
 au revoir encore.  :hello:  
 
[EDIT: je laisse comme ca! , je ne suis pas un moderateur :o ]

Message cité 1 fois
Message édité par __tomjost le 21-01-2010 à 22:50:18
n°1958681
theShockWa​ve
I work at a firm named Koslow
Posté le 19-01-2010 à 10:32:20  profilanswer
 

__tomjost a écrit :


 le dictionaire dit:  punaise = bug  
 
 je suis un bug !! , merci Joel Falcou!  :jap:  
 
 Sale ignorant , j'ai tester ca!  :fou:  
 si tu nage encore en boost et Nt2 , j'ai plusieurs
 domaine a m'occuper , et je ne doit pas me concentrer
 sur des chose qu'on est sur d'apprendre en deux jour.
 
 ton but est d'avoir un leader-ship ou quoi sur ce forum ?
 j'ai remarquer ca des le debut , mais tu es trop
 superficiel avec trop d'euphorie!!
 
 j'essaye toujours a calmer les chose , mais...
 Ok je vous laisse , ENJOY!
 
 le probleme qu'il ne me connait pas ...
 peut etre il regarde les smilies et essaye d'imaginer!  :lol:  
 
Quel type !!
 
 au revoir encore.  :hello:  


 
c'est une blague ? [:pingouino]


---------------
last.fm
n°1958752
Modération
Posté le 19-01-2010 à 14:25:30  answer
 

Citation :

au revoir encore.

Si vous continuez dans cette voie, ce sera même "a dans un mois"...

mood
Publicité
Posté le   profilanswer
 


Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  C++

  Performance des boucles for avec la STL

 

Sujets relatifs
Problème avec les bouclesBoucles for imbriquées
Performance d'un applet Java?boucles imbriqués en une seul requette (ds la meme table quoi)
Utilisation de Fork: plusieurs boucles executées en parrallèlePb boucles imbriquées pour comparaison de deux tableaux
boucles imbriquées[C] executer plusieurs boucles en meme temps
analyse d'un fichier CAD au format STLLes boucles en VB
Plus de sujets relatifs à : Performance des boucles for avec la STL

Forum MesDiscussions.Net, Version 2010.2
(c) 2000-2011 Doctissimo
Page générée en 0.092 secondes

Copyright © 1997-2025 Groupe LDLC (Signaler un contenu illicite / Données personnelles)