L'utilisation d'une classe perso ralentit énormement mon programme

Version imprimable

07/06/2013, 10h44
kipgon

L'utilisation d'une classe perso ralentit énormement mon programme

Salut salut :),

ma question est presque inclue dans le titre : Je me suis créé une classe matrix pour me faciliter la vie (et m'entrainer en c++ ;) ) mais si je transpose mon code qui utilise à l'origine des tableaux 2D en un identique mais qui utilise ma classe matrix cela ralenti énormément la résolution de mon calcul :pleure:

Du coup je suis un peu déçu :( et je préfèrerais qu'on me dise que ma classe est mal faites plutôt que c'est tout à fait normal !

Donc je vous pose la question avant de vous montrer mon code !

Merci d'avance
07/06/2013, 10h57
GrosLapin

C'est dur de répondre à "pourquoi mon programme marche mal" sans le programme :p

Ou au moins les parties que tu as identifié comme lentes.

Je sais pas si ça peut t'aider mais es-tu passé par la ? http://cpp.developpez.com/faq/cpp/?p...E_matrix_array

J'avais bien vu cet article même si j'ai effectivement fait ma classe sous forme de tableaux de tableaux :

Donc il n'est pas évident que l'utilisation d'une classe perso prenne plus de temps que l'utilisation d'une classe native du c++ ?

En tout cas voici ma classe ! Enfin un bout ^^

Code:

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
matrix::matrix(int dim_i, int dim_j) : m_dim_i(dim_i), m_dim_j(dim_j)
{
    alloc();
 
    for (int i=0; i<m_dim_i; i++)
    {
        for (int j=0; j<m_dim_j; j++)
        {
            p[i][j] = 0;
        }
    }
}
 
matrix::matrix(int dim_i) : m_dim_i(dim_i), m_dim_j(1)
{
    alloc();
 
    for (int i=0; i<m_dim_i; i++)
    {
        for (int j=0; j<m_dim_j; j++)
        {
            p[i][j] = 0;
        }
    }
}
 
void matrix::alloc()
{
    p = new double*[m_dim_i];
 
    for (int i=0; i<m_dim_i; i++)
    {
        p[i] = new double[m_dim_j];
    }
}
 
matrix::~matrix()
{
    for (int i=0; i<m_dim_i; i++)
    {
        delete [] p[i];
    }
    delete [] p;
}
 
int matrix::size(int dim)
{
    if (dim == 1)
    {
        return m_dim_i;
    }
    else if (dim == 2)
    {
        return m_dim_j;
    }
    else
    {
        return 0;
    }
}

Je n'ai pas mis les opérations matricielles !

07/06/2013, 11h11
kipgon

p est un

Code:

double **p;
07/06/2013, 11h32
GrosLapin

Bon, c'est un sujet sur lequel je suis en train de me former, donc ne prend pas ce que je dis pour argent comptant.

Si je me trompe pas, tu es sur que tes "cases" de tes lignes soient contiguës en mémoire, mais par que lignes le soient ?

Est ce que tu es sur de ne pas faire de parcours "en colonne" dans tes opérations ?

Est ce que tu as fait des mesures de temps pour savoir ou est ce que ton programme avait du mal ?
07/06/2013, 11h40
kipgon

Pour les mesures de temps je les ai fais de façon globale :

- je met 5 secondes avec les tableaux 2D
- je met 49 secondes avec mes matrix :cry:

PS : je fais du calcul scientifique c'est pour cela que c'est déjà long à l'origine ;)

Par contre je ne comprends pas trop tes autres question :oops: (le C++ n'est pas ma spécialité) peux tu m'expliquer un peu plus :oops: ?
07/06/2013, 11h50
Flob90

Si vraiment ton objectif c'est de faire du calcul, alors utilises des outils qui existent déjà. Faire une classe matrice est un exercice intéressant, mais les premiers résultats seront loin d'être performants, et rechercher cette performance est plus complexe.

Tu mettra plus ton temps à profit en cherchant comment installer et utiliser une bibliothèque que fait déjà ce que tu veux. Il y en a plusieurs :
- boost ublas
- eigen3
- google blaze
- nt2
(non exhaustive)
07/06/2013, 11h52
Klaim

Il nous faut le code complet, pas juste l’implémentation des fonctions...

Mais déjà il y a des trucs très louches.
07/06/2013, 11h56
dragonjoker59

As-tu essayé en ne créant pas ta matrice en tableau de tableaux mais en un tableau simple ?
En mettant les bons accesseurs ça devrait être transparent pour l'utilisateur
07/06/2013, 11h56
GrosLapin

Tu as dim_i = [ a b .. z ] ou [a,z] sont des pointeurs

Tu as dim_j = [ bloque mémoire ]

Si tu fais une double boucle "i j", tu vas aller sur "a" puis sur le bloque mémoire qui correspond et tu vas lire le bloque. C'est un bonne chose car tu changes pas tout le temps de zone mémoire. Puis tu vas allez sur b qui va te rediriger sur une autre zone mémoire et tu vas la lire.

Si maintenant tu fait l'inverse, c'est à dire une boucle "j i". Tu vas aller du début du 1er bloque mémoire, lire ta valeur, aller au début du 2em lire ta valeur ext.

Lorsque tu lis une valeur le programme charge pas uniquement cette valeur, il charge aussi les valeurs qui la suivent, car il suppose que tu vas t'en servir après. Du coup, si tu lis un bloque de mémoire tu profites de cette optimisation. Si tu changes tout le temps de bloque mémoire... tu perds beaucoup de temps.
07/06/2013, 12h00
kipgon

Je pense que je vais faire cela, j'avais déjà vu que cela existait mais je voulais m'entrainer un peu étant donné que je suis nouveau en c++.

Mais si quelqu'un à une idée pour mon problème je suis preneur, au moins pour comprendre !
07/06/2013, 12h41
Klaim

Tant que tu montres pas au moins le header, je vois pas bien comment on peut t'aider plus.

Je ne vois pas en quoi cela peu aider mais voila

Code:

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
39
40
41
42
43
44
45
46
47
48
49
50
#ifndef MATRIX_H
#define MATRIX_H
 
#include <iostream>
 
using namespace std;
 
class matrix
{
    public:
 
    matrix(int dim_i);
    matrix(int dim_i, int dim_j);
    ~matrix();
 
    int size(int dim);
    void afficher();
    bool diagDominante();
 
    double &operator()(int i,int j);
    double &operator()(int i);
 
    matrix &operator =(const matrix &A);
 
    friend ostream &operator<<(ostream &out, const matrix &A);
 
    friend matrix operator*(const matrix& M1, const matrix& M2);
    friend matrix operator*(const double c, const matrix& A);
    friend matrix operator*(const matrix& A, const double c);
    matrix& operator*=(const matrix& A);
 
    friend matrix operator+(const matrix& A, const matrix& B);
    matrix& operator+=(const matrix& A);
 
    friend matrix operator-(const matrix& A, const matrix& B);
    matrix& operator-=(const matrix& A);
 
 
    private:
 
    void alloc();
 
    int m_dim_i;
    int m_dim_j;
 
    double **p;
 
};
 
#endif // MATRIX_H

07/06/2013, 13h33
Klaim

Ton erreur c'est d'avoir un double array.
07/06/2013, 14h09
kipgon

C'est à dire ? Le fait que je fasse un **p ?

Par rapport à ce qu'explique groslapin à propos du déplacement dans le tableau ?
07/06/2013, 14h18
Klaim

Je pense que les autres ont deja globalement repondu, mais le simple fait que tu ais un double pointeur/double tableau est une mauvaise idee.

Essaie avec un pointeur normal, change ton alloc() de maniere a ne faire que le new pour allouer i*j elements. (et a partir de la tu changes les acces pour que (x,y) sois l'element (y * j + x) )

D'autres choses basiques pourraient etre faites pour ameliorer les perfs, comme eliminer le new totalement ou le rendre optionel selon la taille de la matrice.
07/06/2013, 14h30
kipgon

J'avais vu la déclaration sous la forme (y * j + x) mais je ne voyais pas l’intérêt, j'étais loin de me douter que cela poserait autant de problème en mémoire 8O !

Je vais faire cela ;)

Sinon pourrais tu m'expliquer ceci Klaim :

Citation:

eliminer le new totalement ou le rendre optionel selon la taille de la matrice.

tu veux dire par la déclarer en statique le tableau si la matrice est petite
et si la matrice est très grande on alloue dynamiquement la mémoire ? c'est bien ça ?
07/06/2013, 15h18
Klaim

Oui c'est ca, mais je pense que ca posera trop de probleme... garde le new pour l'instant. C'est plus ou moins comme un vector donc ca devrait aller.

Je viens de faire les modifs mais j'ai un problème que je ne comprend pas !

J'arrive à déclarer une matrice 3x3 (A(3,3)), j'arrive à déclarer une matrice 3x1 (B(3)), j'arrive à donner des valeurs à ces éléments (A(1,2)=3) par contre au moment de l'affichage, A s'affiche convenablement tandis que B n'affiche de bon que le premier élément 8O !

Voyez vous l'erreur ?

Code:

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
using namespace std;
 
matrix::matrix(int dim_i, int dim_j) : m_dim_i(dim_i), m_dim_j(dim_j)
{
    p = new double[m_dim_i*m_dim_j];
 
    for (int i=0; i<m_dim_i; i++)
    {
        for (int j=0; j<m_dim_j; j++)
        {
            p[m_dim_i*i+j] = 0;
        }
    }
}
 
matrix::matrix(int dim_i) : m_dim_i(dim_i), m_dim_j(1)
{
    p = new double[m_dim_i];
 
    for (int i=0; i<m_dim_i; i++)
    {
        p[i] = 0;
    }
}
 
matrix::~matrix()
{
    delete [] p;
}
 
int matrix::size(int dim)
{
    if (dim == 1)
    {
        return m_dim_i;
    }
    else if (dim == 2)
    {
        return m_dim_j;
    }
    else
    {
        return 0;
    }
}
 
double &matrix::operator()(int i,int j)
{
    return p[m_dim_i*i+j];
}
 
double &matrix::operator()(int i)
{   
    return p[i];
}
 
ostream &operator<<(ostream &out, const matrix &A)
{
    for (int i=0; i<A.m_dim_i ; ++i)
    {
        out << endl;
 
        for (int j=0; j<A.m_dim_j; ++j)
        {
            out << A.p[A.m_dim_i*i+j] << " ";
        }
    }
 
    out << endl;
 
    return out;
}

Edit : En fait mon programme plante quant je le ferme même s'il à bien affiché la matrice :cry:

07/06/2013, 16h51
haraelendil

euh, y a pas de constructeur par copie, c'est toi qui l'a pas mis ou tu ne l'as pas fait?

Le voila :)

Code:

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
matrix &matrix::operator =(const matrix &A)
{
    if (this == &A)
    {
        return *this;
    }
    else
    {
        if (m_dim_i!= A.m_dim_i||m_dim_j!= A.m_dim_j)
        {
            this->~matrix();
        }
    }
 
    m_dim_i= A.m_dim_i;
    m_dim_j= A.m_dim_j;
 
    p = new double[m_dim_i*m_dim_j];
 
    for (int i = 0; i <m_dim_i; i++)
    {
        for (int j = 0; j <m_dim_j; j++)
        {
            p[m_dim_i*i+j] = A.p[m_dim_i*i+j];
        }
    }
 
    return *this;
}

Comme lors de mon test je ne l'utilisais pas je me suis dis que le problème ne venait pas de la !

07/06/2013, 17h46
GrosLapin

Quand tu fais A(3) ça donne dim_i = 3 dim_j = 1. Du coup à l'affichage tu affiches 0 3 6 alors que tu devrais afficher 0 1 2 du coup tu as que 0 de bon
07/06/2013, 22h26
Bousk

Bonsoir,

à vue de nez, je dirais que ça sent les copies non maîtrisées dans tous les sens.
Cela dit, on voit pas grand chose de l'implémentation et utilisation..
08/06/2013, 11h59
Médinoc
1. haraelendil a dit constructeur de copie, pas opérateur d'affectation
2. Cet opérateur d'affectation est une horreur. Tu devrais implémenter un constructeur de copie correct et utiliser l'idiome copy-and-swap quand les dimensions ne sont pas égales, ce sera beaucoup plus propre.
PS: Ton constructeur matrix(int dim_i) devrait être déclaré explicit.
13/06/2013, 15h21
kipgon

J'ai trouvé mon problème, en fait je remplissais ma matrice en faisant dim_i*i+j au lieu de dim_j*i+j ! Erreur idiote !

Sinon j'ai aussi ajouté le constructeur par copie que j'avais en effet oublié alors que je l'utilisais :mur:

Mais pour ce qui est du temps de calcul et bien c'est pire :calim2: ! 88 secondes
14/06/2013, 09h13
victor_gasgas

Si tu veux savoir où se trouve tes goulots d'étranglement , utilise un profileur !

Mais je pense que si tu as du calcul instance , ton ralentissement doit provenir de tes allocations mémoire avec new. En effet, chaque fois que tu crées, copies
ou même multiplies deux matrices tu fais une allocation.

Le profileur de donneras de très bons résultats, mais si tu as des matrices de taille petites alors tout ton temps sera passé dans les allocations dynamiques sûrement !

P.S. Si tu connais tes tailles de matrice en avances, tu pourras peut être utiliser std::array qui alloue sur la pile. Et avec quelques expressions templates et un bon niveau d'optimisation tu sortiras touts les objets temporaires : ce sont quelques techniques utilisées dans les bibliothèques matricielles. Et si tu veux aller plus moins renseignes toi sur l'alignement mémoire, les instructions simd (c.f. Boost.simd qui nous tarde tous :aie: ), etc.
14/06/2013, 09h55
jabbounet

As-tu réellement besoin d'une allocation dynamique pour tes matrices?

Dans la plupart des application ou j'ai pu rencontrer ce type d'implémentation les matrices ne dépassaient pas une taille fixe...

Un new (allocation sur le tas) coute infiniment plus cher par rapport à une allocation sur la pile.

Après tu peux aussi essayer de porter certain principes utilisés pour les string comme le short string optimisation (SSO) ou le copy on write.
14/06/2013, 10h20
Arzar

+1 avec jabbounet
C'est vrai qu'il y a un truc pas clair dans le premier post, le PO dit qu'il est passé d'un style "qui utilise à l'origine des tableaux 2D" à sa prpore classe matrix, ce qui donnent l'impression qu'il est passé d'un truc du style double mat[10][10]; (sur la pile) à matrix mat(10, 10); (sur le tas avec new) ce qui serais évidemment une méga catastrophe.
14/06/2013, 10h30
Médinoc

S'il y a beaucoup de créations et destructions et que la taille est fixe, matrix<double, 10, 10> mat; pourrait être un meilleur choix en effet.
16/06/2013, 23h16
Joel F

Citation:

Envoyé par victor_gasgas

(c.f. Boost.simd qui nous tarde tous :aie: ), etc.

oh y a eu une beta y a 4 mois et y en a une aurte bientot :o :calim2:
17/06/2013, 18h41
kipgon

Je suis effectivement passé d'un

Code:

double mat[10][10]

à un

Code:

matrix mat(10,10)

avec les new

par ce que je ne connais pas à la compilation la taille des matrices que je vais utiliser (elle est entrée dans ma GUI).

Donc en fait c'est bien la déclaration en dynamique qui coute cher en temps et pas une erreur de programmation de ma part (je suis en train d'apprendre le c++ alors je me méfie de mes erreurs ^^).

Je pense que je vais donc "abandonner" puisque j'ai déjà codé une classe matrice avec des vectors, avec des tableaux 2D et avec des tableaux linéaire (dim_j*i+j) cela m'a permis de comprendre un peu le principe de tout cela et je vais me tourner pour les usages vers la bibliothèque boost je pense ;).

A moins que vous ayez une meilleure bibliothèque à me conseiller ?
18/06/2013, 07h11
Joel F

pas boost.ublas, les performances sont bof bof
18/06/2013, 08h05
jabbounet

Citation:

Envoyé par kipgon

Je suis effectivement passé d'un

Code:

double mat[10][10]

à un

Code:

matrix mat(10,10)

avec les new

par ce que je ne connais pas à la compilation la taille des matrices que je vais utiliser (elle est entrée dans ma GUI).

La matrice est entrée dans une GUI, si c'est manuel je pense que tu peux utiliser une taille fixe max de 100x100 par exemple et n'utiliser qu'une sous partie de la matrice.
je ne pense pas qu'un utilisateur entrera manuellement une matrice 100x100, ou alors il a du temps a perdre.

Autrement tu peux très bien avoir en interne dans ton objet une matrice de taille fixe alloué sur la pile pour gérer les matrices de petites taille et un pointeur pour gérer les matrices de grande taille (que te n'allouera que dans le cas ou l'utilisateur souhaite bosser avec des matrice dépassant la taille de la matrice alloué sur la pile), ce serait une espèce d'équivalent au short string optimisation (SSO) suggéré avant.

Autre possibilité, faire une pré-allocation à l'initialisation ton application et s'en servir comme cache pour stocker les matrices mais cela nécessite de bien gérer cet espace mémoire et ce sera de toute façon moins efficace que de mettre les matrices sur la pile.

Fuseau horaire GMT +2. Il est actuellement 07h40.