perte de temps avec vector

**geoberto** · 25/07/2012, 18h00

Bonsoir à tous !

J'ai besoin d'aide, je suis en train de travailler sur un projet de matrices creuses de grandes tailles 200x200 notamment modifier une librairie existante pour l'optimisée. J'ai déjà effectué avec succès les opérations plus et inf pour des matrices représentées std::vector, mon problème est pour l'opération transpose, qui est très très lente par rapport à l'existant....

voici le début de la classe matrixvector

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
 
struct Ttriplet
{
 Ttriplet(int I, int J,serie S):i(I),j(J),s(S){}
int i;
int j;
serie s;
        int geti(){return this->i;}
        int getj(){return this->j;}
        void seti(int k){i=k;}
        void setj(int k){this->j=k;}
        serie gets(){return this->s;}
        void sets(serie sa){this->s=sa;}
} ;
 
class matrixvector{
private :
		 int col,row;
		 unsigned int size,capacity;
 
         std::vector<Ttriplet *> Data;
...

et le code de la fonction transpose:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
matrixvector transpose(matrixvector& a)
 {
    matrixvector result;
    //result.Data.reserve(a.size);
    Ttriplet *temp;
    int n=0,i=0,j=0;
    n=a.getsize();
    result.row=a.getcol();
    result.col=a.getrow();
     result.size=0;
    if(n>0)
    {
        result.size=1;
        for(i=0;i<a.col;++i)
        {
            for(j=0;j<n;++j)
            {
              //  std::cout<<a.Data[j]->j<<std::endl;
               if((a.Data.at(j)->j==i))
                    {
                        temp=new Ttriplet(a.getj(j),a.geti(j),a.Data[j]->s);
                        result.Data.push_back(temp);
                        result.size++;
                    }
//
            }
 
        }
         return(result);
    }
 
      else
    {
        mem_limite  l(28);   throw(l);
    }
 
 }

test:

Merci !

**oodini** · 25/07/2012, 18h36

Si tu te soucies des performances, commence par utiliser [] plutôt que at().

**Bousk** · 25/07/2012, 18h52

Bonjour,

il est dommage d'avoir supprimer une des plus grandes sources d'optimisation de l'utilisation du std::vector : vector::reserve.
Ton vector se remplit à coup de push_back... ce qui entraîne désallocation et réallocation en chaîne.
L'utilisation de at est également à proscrire.

Après dans les plus petites optimisations possibles
- préfère la préincrémentation à la postincrémentation
- éviter d'utiliser des variables temporaires, même pour ne stocker qu'un vecteur, tu peux faire un push_back(new T)
- pourquoi stocker result.size et l'incrémenter à chaque push_back ? vector possède sa fonction size (en temps constant) ... qu'il suffit d'appeler à la fin
- passer la matrix resultat en paramètre out plutôt que par return, ça évite une copie

qu'est-ce que serie ? pourquoi ne pas le retourner en const& ?
pourquoi il n'est pas en const& dans le paramètre de sets ?

**gbdivers** · 25/07/2012, 19h52

bonjour geoberto et bienvenue sur le forum

La programmation de libs numérique est un domaine complexe et à la vue de ton code, j'ai l'impression que tu débutes, non ?
Je te conseille de regarder les libs existantes et voir comment ce type de problématique est résolue, tu apprendras beaucoup comme ça
Par exemple (mais non exclusif) :
boost.uBlas http://www.boost.org/doc/libs/1_50_0.../doc/index.htm
nt2 http://nt2.lri.fr/contents.html

**geoberto** · 25/07/2012, 20h46

Merci Bousk, mais c'est toujours aussi lent, la lenteur vient probablement du pushback...

Le reserve ne change rien quel que soit la taille.

Oui Guillaume je débute, j'ai déjà essayé avec un tableau de Ttriplet et j'ai passé une éternité à créer moi-même un pushback et à gérer les allocations dynamiques donc j'ai choisi d'utiliser les vector. Merci pour les libs je vais regarder ça.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
void transpose(matrixCOOvector& a, matrixCOOvector &b)
 {
    //matrixCOOvector result;
    b.Data.reserve(a.size);
    Ttriplet *temp;
    int i=0,j=0;
    b.row=a.getcol();
    b.col=a.getrow();
    if(a.size>0)
    {
        for(i=0;i<a.col;++i)
        {
            for(j=0;j<a.size;++j)
            {
              //  std::cout<<a.Data[j]->j<<std::endl;
               if((a.Data[j]->j==i))
                    {
                     //  temp=new Ttriplet(a.getj(j),a.geti(j),a.Data[j]->s);
                        b.Data.push_back(new Ttriplet(a.getj(j),a.geti(j),a.Data[j]->s));
 
                    }
//
            }
 
        }
                b.size=b.Data.size();
    }
 
      else
    {
        mem_limite  l(28);   throw(l);
    }
 
 }

**JolyLoic** · 25/07/2012, 21h21

Pourquoi utiliser des pointeurs et de l'allocation dynamique ?

**oodini** · 26/07/2012, 11h14

Pour ce genre de problèmes, n'utilise pas des vecteurs, mais du stockage à l'ancienne à base de pointeurs. En plus de gagner en efficacité, tu pourras plus facilement extraire des colonnes.

Et quand tu peux, alloue la mémoire en une seule fois.

**Klaim** · 26/07/2012, 13h18

Je vois pas pourquoi utiliser un vecteur avec les valeurs au lieu des pointeurs , réservé à la taille finale, serait moins bien que faire ce que tu viens de dire?

**ternel** · 26/07/2012, 13h24

Parce que tu économiserais en pointeurs, appels de fonctions et autres?

**gbdivers** · 26/07/2012, 13h45

Il y a une petite différence de performance entre l'opérateur [], un iterateur et un pointeur nu (double p = &t[0]

. Certain diront non (que ça dépend entre autre des options de compilation)

Ici, la différence entre vecteur et un tableau C-style est négligeable par rapport à tous les autres problèmes de conception, en particulier l'utilisation de push_back et l'absence de reserve. Il y a aussi le problème de new (faire 200*200 allocations ou presque, c'est pas top)

Bref, comme d'hab -> profiling avant de chercher à faire de la micro-optimisation sur vector, un appel de fonction ou un déréférencement de pointeur

**germinolegrand** · 26/07/2012, 14h31

Bonjour, si tu sais à l'avance que tes matrices font 200x200, pourquoi utiliser un vector ?

**gbdivers** · 26/07/2012, 14h53

Parce que ce sont des matrices creuses (avec des trous donc

-> ils n'y a pas 200*200 éléments)

**Bousk** · 30/07/2012, 10h12

Pourquoi réserver une taille de a.size alors que la boucle se fait sur a.size*a.col ?

Invité · 30/07/2012, 16h05

Pourquoi réserver une taille de a.size alors que la boucle se fait sur a.size*a.col ?

vraisemblablement a.getSize() retourne le nombre de triplets stockes dans matrixvector.Data

cela dit, c'est assez byzarre de voir que tu crees une copie de ton instance plus transpose cette copie.
Generalement quand tu transposes tu le fais sur la matrice de base.
Sinon tu la copies.
Mais la tu fais 2 en 1

**Joel F** · 04/08/2012, 12h45

Envoyé par oodini

Pour ce genre de problèmes, n'utilise pas des vecteurs, mais du stockage à l'ancienne à base de pointeurs. En plus de gagner en efficacité, tu pourras plus facilement extraire des colonnes.

Et quand tu peux, alloue la mémoire en une seule fois.

On lit ca et on l’exécute, puis on arrête de dire des bêtises sur std::vector

**Matthieu Brucher** · 05/08/2012, 09h41

Envoyé par gbdivers

bonjour geoberto et bienvenue sur le forum

La programmation de libs numérique est un domaine complexe et à la vue de ton code, j'ai l'impression que tu débutes, non ?
Je te conseille de regarder les libs existantes et voir comment ce type de problématique est résolue, tu apprendras beaucoup comme ça
Par exemple (mais non exclusif) :
boost.uBlas http://www.boost.org/doc/libs/1_50_0.../doc/index.htm
nt2 http://nt2.lri.fr/contents.html

Et ma préférée : Eigen http://eigen.tuxfamily.org/

**Matthieu Brucher** · 05/08/2012, 09h43

Envoyé par gbdivers

Il y a une petite différence de performance entre l'opérateur [], un iterateur et un pointeur nu (double p = &t[0]

. Certain diront non (que ça dépend entre autre des options de compilation)

Ici, la différence entre vecteur et un tableau C-style est négligeable par rapport à tous les autres problèmes de conception, en particulier l'utilisation de push_back et l'absence de reserve. Il y a aussi le problème de new (faire 200*200 allocations ou presque, c'est pas top)

Bref, comme d'hab -> profiling avant de chercher à faire de la micro-optimisation sur vector, un appel de fonction ou un déréférencement de pointeur

Envoyé par Joel F

On lit ca et on l’exécute, puis on arrête de dire des bêtises sur std::vector

Je réponds aux deux d'un coup. Sur Visual Studio, il me smeble que at() et [] font de la vérification. Pour at(), c'est obligatoire d'après la norme, mais pour [] ce n'est pas obligatoire de ne pas tester. Pour des raisons de sécurité, Microsoft a laissé le test.

**Bousk** · 05/08/2012, 19h19

Ta dernière remarque a aiguisé ma curiosité, et voilà ce que Visual Studio (2010 ultimate) propose

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const_reference at(size_type _Pos) const
		{	// subscript nonmutable sequence with checking
		if (size() <= _Pos)
			_Xran();
		return (*(this->_Myfirst + _Pos));
		}
 
const_reference operator[](size_type _Pos) const
		{	// subscript nonmutable sequence
 #if _ITERATOR_DEBUG_LEVEL == 2
		if (size() <= _Pos)
			{	// report error
			_DEBUG_ERROR("vector subscript out of range");
			_SCL_SECURE_OUT_OF_RANGE;
			}
 
 #elif _ITERATOR_DEBUG_LEVEL == 1
		_SCL_SECURE_VALIDATE_RANGE(_Pos < size());
 #endif /* _ITERATOR_DEBUG_LEVEL */
 
		return (*(this->_Myfirst + _Pos));
		}

Donc les check pour l'opérateur ne sont présents qu'en Debug.

**JolyLoic** · 05/08/2012, 22h18

Envoyé par Matthieu Brucher

Je réponds aux deux d'un coup. Sur Visual Studio, il me smeble que at() et [] font de la vérification. Pour at(), c'est obligatoire d'après la norme, mais pour [] ce n'est pas obligatoire de ne pas tester. Pour des raisons de sécurité, Microsoft a laissé le test.

Il y a eu une version de visual studio où les vérifications étaient présentes même en mode optimisé avec les options par défaut (la motivation était qu'à l'époque windows se faisait attaquer sur sa stabilité, et donc que les gens prônant la sécurité même au détriment des performances ont eu le dessus). C'était une bêtise sans nom... Ils sont revenus en arrière. Si on travaille avec cette version (2005 et 2008), il est possible de désactiver ces vérifications en définissant la macro _SECURE_SCL à 0 (attention, il faut le faire partout, y compris dans les bibliothèques externes).

Je pense que le main dev de la bibliothèque standard microsoft doit donner plus d'infos la dedans : http://channel9.msdn.com/Series/C9-L...ced-STL-3-of-n (je ne l'ai pas encore regardé, download en cours...)).

**Lightness1024** · 07/08/2012, 12h08

attention même un profiler n'est pas suffisant, il dit où sont les passages qui prennent le plus de temps mais pas comment régler le problème.

attention a la fragmentation mémoire et à l'ordre d'accès pour favoriser le cache. c'est toujours la mémoire le problème avec les grosses données.

utiliser la carte graphique peut être une idée pour ce genre d'opérations mais 200x200 risque de ne pas être suffisant pour amortir les couts de setup + synchro.

perte de temps avec vector

C++

Discussions similaires

Partager

Partager