Complexité du polymorphisme

Le
Gégé
Salut,

Suite à un post que j'avais ouvert récemment, j'ai isolé une curiosit=
é
que j'aimerais éclaircir grâce à vos remarques :

J'ai une classe mère A avec une methode a() virtuelle pure, et une
methode b() normale.
Je crée une classe dérivée B dans laquelle je mets dans a() la même
implémentation que b().

Concrètement B.a(), et B.b() font la même chose.

Je caste B en A de façon à utiliser plutot A.a() et A.b()

Si j'exécute ces 2 méthodes un très grand nombre de fois, je remarque
que a() est beaucoup plus lente que b().

Est-ce un résultat attendu ?

Merci

G
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses Page 1 / 3
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Alain Ketterlin
Le #17798711
Gégé
Suite à un post que j'avais ouvert récemment, j'ai isolé une curiosité
que j'aimerais éclaircir grâce à vos remarques :

J'ai une classe mère A avec une methode a() virtuelle pure, et une
methode b() normale.
Je crée une classe dérivée B dans laquelle je mets dans a() la même
implémentation que b().



C'est-à-dire :

class A {
virtual X a(...) {...}
Y b(...) {...}
};

class B : public A {
virtual X a(...) {...}
};


Concrètement B.a(), et B.b() font la même chose.



Oui mais l'appel n'est pas fait de la même façon.

Je caste B en A de façon à utiliser plutot A.a() et A.b()



Tu castes l'objet ou juste un pointeur ?

Si j'exécute ces 2 méthodes un très grand nombre de fois, je remarque
que a() est beaucoup plus lente que b().

Est-ce un résultat attendu ?



Plus ou moins. Un appel de méthode virtuelle est toujours plus
coûteux, parce que la liaison est dynamique. L'appel est donc
indirect : il y a au minimum une indirection supplémentaire. En gros,

o->a(...)

devient

o->t[123](...) // 123 est supposé être un id de a()

parce que chaque classe a potentiellement sa version de a(), et
l'appel (o->a()) ne peut pas être résolu à la compil. C'est un temps
éventuellement non négligeable.

Cela dit, si tu fais quelque chose comme :

A unA = monB;
unA.a();

alors il ne devrait pas y avoir de surcoût, parce que le compilo sait
exactement quelle version de a() utiliser. Mais ce n'est pas sûr qu'il
le fasse systématiquement, il faut peut-être augmenter le niveau
d'optimisation.

-- Alain.
Gégé
Le #17800801
Merci Alain pour ta réponse.

Je pensais à un exemple comme celui-ci :

/////////////////////////////////////////////////////////////////////////// ///////////////////////////////////////////////

#include <vector>
#include <iostream>
#include <ctime>
using namespace std;

class A
{
public :
virtual void a() = 0;
void b();
};

void A::b()
{
return;
}

class B : public A
{
public :
void a();
};

void B::a()
{
return;
}

void main(int argc, char * argv[])
{

A * _A = new B();
clock_t t1, t2, t0;


t0 = clock();
const int N = 1000000000;
for ( int i = 0; i < N; i++ )
{
_A->a();
}

t1 = clock();
for ( int i = 0; i < N; i++ )
{
_A->b();
}

t2 = clock();
cout << "a() : " << ( double )( t1 - t0 ) / CLOCKS_PER_SEC << "
sec" << endl;
cout << "b() : " << ( double )( t2 - t1 ) / CLOCKS_PER_SEC << "
sec" << endl;

delete _A;
system("pause");

return;
}

/////////////////////////////////////////////////////////////////////////// ///////////////////////////////////////////////

Ceci dit, les résultats sont qd meme assez proches ... mais dans mon
projet j'ai de bien plus grosses différences ...
J'utilise en revanche beaucoup plus d'objets instanciés (30.000), je
ne sais pas si ça peut jouer ....
Gégé
Le #17800791
<<
Mais ce n'est pas sûr qu'il
le fasse systématiquement, il faut peut-être augmenter le niveau
d'optimisation.






Qu'appelles-tu "niveau d'optimisation" ?
Merci
Marc Boyer
Le #17801101
On 2008-11-10, Gégé
Merci Alain pour ta réponse.

Je pensais à un exemple comme celui-ci :


[SNIP l'exemple]
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

Ceci dit, les résultats sont qd meme assez proches ... mais dans mon
projet j'ai de bien plus grosses différences ...



Comme le disais Alain, dans le cas d'un accès à une méthode
vituelle appellée à travers un pointeur, il faut d'abord
trouver quel code appeller puis l'exécuter, alors que si le
compilo sait déterminer à la compilation quel code appeller,
la phase de recherche n'a pas lieu à l'éxécution.

Après, je suis surpris qu'il y ait de grandes différences, car
c'était un reproche beaucoup fait aux LOO à une époque, et
les compilos ont souvent été développés en essayant de réduire
ce coût.

J'utilise en revanche beaucoup plus d'objets instanciés (30.000), je
ne sais pas si ça peut jouer ....



Je ne vois pas ce que ça aurait à faire dans l'histoire, mais bon...
Peut-être un problème de cache, mais ce sont pas des problèmes
forcément faciles à identifier.

Marc Boyer
--
Si tu peux supporter d'entendre tes paroles
Travesties par des gueux pour exciter des sots
IF -- Rudyard Kipling (Trad. André Maurois)
Jean-Marc Bourguet
Le #17801861
Marc Boyer
Je ne vois pas ce que ça aurait à faire dans l'histoire, mais bon...
Peut-être un problème de cache, mais ce sont pas des problèmes
forcément faciles à identifier.



Ma première idée quand on parle de ce genre de différences, c'est de
regarder le code généré pour voir s'il y a une explication évidente (du
genre: tient, le compilateur a réussi à inliner l'appel non virtuel et pas
l'appel virtuel).

--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org
Sylvain SF
Le #17801851
Gégé a écrit :
<<
Mais ce n'est pas sûr qu'il
le fasse systématiquement, il faut peut-être augmenter le niveau
d'optimisation.

Qu'appelles-tu "niveau d'optimisation" ?



faut-il définir "optimisation", "niveau" ou les 2 ?

un compilo C++ est capable de générer du code selon différents
critères, dont présence d'info. de debug, compacité vs performance,
etc, ces options d'optimisation peuvent être (selon le compilo)
définies une à une ou globalement selon un "niveau" plus ou
moins arbitraire et qui impliquera des optim. simples (niveau
bas) ou très poussées (niveau haut), le temps de compile dépend
évidemment de ce niveau, on n'utilisera donc pas nécessiarement
le même en mise au point et en livraison.

concernant tes boucle d'1 million d'itérations, en mode niveau
zéro d'optimisation (en mode debug en fait) j'ai pour ma part
les temps de 28 et 26 sec. la différence est assez négligeable
et ce n'est pas étonnant car on ne mesure que le temps d'appel
(un call) précédé de 1 (non virtuel) mov ou 4 (appel virtuel).

si je passe en mode optimisé (niveau "standard") les temps deviennent
2.05 sec et 0.0 sec. où l'on mesure le temps de la résolution virtuelle,
en effet le premier appel doit être résolu (car il est virtuel) et le
compile appelle bien la méthode B::a(), pour le 2nd appel le compilo
a la certitude d'appeler A::b() (puisque non virtuel) et il se rend
compte que cette méthode ne fait rien (il vient de compiler un simple
return), donc il ne l'appelle pas et la boucle complète est supprimée
(cela se nomme une optimisation, ici virer le code mort).

donc pour plagier les réponses précédentes, l'impact de l'appel
virtuel est (très généralement) non significatif mais cette
différence peut varier selon les optimisations faites.

Sylvain.
James Kanze
Le #17806361
On Nov 10, 11:29 am, Gégé
Suite à un post que j'avais ouvert récemment, j'ai isolé une
curiosité que j'aimerais éclaircir grâce à vos remarques :



J'ai une classe mère A avec une methode a() virtuelle pure, et
une methode b() normale. Je crée une classe dérivée B dans
laquelle je mets dans a() la même implémentation que b().



C-à-d :

struct A
{
void virtual a() = 0 ;
void b() { /* implementation */ }
} ;

struct B : A
{
void virtual a() { /* implementation */ }
}

Concrètement B.a(), et B.b() font la même chose.



C-à-d que les parties « /* implementation */ » ci-dessus sont
identiques.

Je caste B en A de façon à utiliser plutot A.a() et A.b()



Je ne le crois pas. Le langage ne permet pas d'objets de type A.
Est-ce que tu veux dire que tu as créé une référence à A qui
désigne la partie A d'un objet de type B, c-à-d :

B objet ;
A& ref = objet ;

(Une conversion explicit n'est pas nécessaire.)

Si j'exécute ces 2 méthodes un très grand nombre de fois, je
remarque que a() est beaucoup plus lente que b().



C-à-d ref.a() et ref.b() ? Et qu'est-ce que tu entends par
« beaucoup plus lente » ?

Est-ce un résultat attendu ?



Sans savoir exactement ce que tu as mesuré, et comment, on ne
sait pas. Mais en général, le temps nécessaire pour appeler une
fonction virtuelle, quand le compilateur ne connaît pas le type
réel, est forcément plus élevé que le temps nécessaire pour
appeler une fonction non virtuelle ; il faut résoudre l'appel
lors de l'exécution. Dire que ça rend le code « beaucoup plus
lente », en revanche... Ça dépend du compilateur, du processeur,
et de ce que contient la fonction, mais typiquement, la
différence est à peine mesurable sur les processeurs que
j'utilise, dans les contextes où je l'utilise. Ce qui peut
parfois faire une diffénce, en revanche, c'est que si le
compilateur sait déjà quelle fonction va réelement être appelée,
il peut le générer en ligne, ce qui ouvre souvent d'autres
possibilités d'optimisation.

--
James Kanze (GABI Software) email:
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
James Kanze
Le #17806531
On Nov 10, 11:59 am, Alain Ketterlin wrote:
Gégé


[...]
> Si j'exécute ces 2 méthodes un très grand nombre de fois, je
> remarque que a() est beaucoup plus lente que b().



> Est-ce un résultat attendu ?



Plus ou moins. Un appel de méthode virtuelle est toujours plus
coûteux, parce que la liaison est dynamique. L'appel est donc
indirect : il y a au minimum une indirection supplémentaire.
En gros,



   o->a(...)



devient



   o->t[123](...) // 123 est supposé être un id de a()



parce que chaque classe a potentiellement sa version de a(),
et l'appel (o->a()) ne peut pas être résolu à la compil. C'est
un temps éventuellement non négligeable.



Ça correspond à peu près à l'implémentation la plus courante.
Modolo un tas d'optimisations possibles.

Note que sur certains processeurs, l'effet de l'indirection est
plus important que sur d'autres ; parce que le cible du saut
n'est pas connu, la « branch prediction » ne fonctionne pas de
la même façon. Un ami chez HP m'a racconté que sur les
architectures PA, un saut indirect pourrait prendre jusqu'à dix
fois plus de temps qu'un saut direct. Et que ça valait aussi
pour le saut de retour de la fonction. Du coup, la génération
inline apporter beaucoup plus que sur d'autres processeurs.

Évidemment, il y a un tas de possibilités d'optimisation. Si tu
écris quelque chose comme :
B objet ;
A& ref = objet ;
ref.a() ;
, un bon compilateur reconnaît bien que le type dynamique de
ref, ici, ne pourrait jamais être que B, et donc génère du code
pour un appel direct. De même, si tu as quelque chose comme :

f( A& ref )
{
for ( /* beaucoup de fois */ ) {
ref.a() ;
}
}

et les informations du profileur indique que f est appelé
prèsque toujours avec un B, le compilateur pourrait très bien
générer quelque chose d'équivalent à :

f( A& ref )
{
if ( typeid( ref ) == typeid( B ) ) {
for ( /* beaucoup de fois */ ) {
// appel direct à B::f()
}
} else {
for ( /* beaucoup de fois */ ) {
// appel virtuel classique
}
}
}

Avec génération inline de B::f() dans la première boucle, si ça
vaut la peine.

Cela dit, si tu fais quelque chose comme :



   A unA = monB;
   unA.a();



alors il ne devrait pas y avoir de surcoût, parce que le
compilo sait exactement quelle version de a() utiliser.



En fait, dans son exemple, ça ne doit même pas compiler.

Mais ce n'est pas sûr qu'il le fasse systématiquement, il faut
peut-être augmenter le niveau d'optimisation.



Si on appel la fonction sur un objet, je ne connais pas de
compilateur qui génère une résolution dynamique, quelque soit le
niveau d'optimisation.

--
James Kanze (GABI Software) email:
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
James Kanze
Le #17806521
On Nov 10, 3:56 pm, Gégé
Merci Alain pour ta réponse.



Je pensais à un exemple comme celui-ci :



////////////////////////////////////////////////////////////////////////



[...]
void main(int argc, char * argv[])



Juste un détail sans rapport, mais ça ne compile pas avec mon
compilateur. Main doit renvoyer un int.

{
    A * _A = new B();
    clock_t t1, t2, t0;



    t0 = clock();
    const int N = 1000000000;
    for ( int i = 0; i < N; i++ )
    {
        _A->a();



Ici, un bon compilateur saurait que _A designe un B, et
générerait l'appel direct (qu'il mettrait ensuite inline, ce qui
mène à la suppression de la boucle).

    }



    t1 = clock();
    for ( int i = 0; i < N; i++ )
    {
        _A->b();



Ici aussi, un bon compilateur supprimera carrément la boucle.
(Dans ce cas-ci, même g++, qui est assez faiblard en ce qui
concerne les optimisations, le fait.)

    }



    t2 = clock();
    cout << "a() : " << ( double )( t1 - t0 ) / CLOCKS_PER_SEC << "
sec" << endl;
    cout << "b() : " << ( double )( t2 - t1 ) / CLOCKS_PER_SEC << "
sec" << endl;



    delete _A;
    system("pause");
        return;



}



////////////////////////////////////////////////////////////////////////



Ceci dit, les résultats sont qd meme assez proches ... mais
dans mon projet j'ai de bien plus grosses différences ...



Qu'en dit le profileur ?

J'utilise en revanche beaucoup plus d'objets instanciés
(30.000), je ne sais pas si ça peut jouer ....



Pour commencer, il faut voirs ce que dit le profileur. Ensuite,
il faut voir l'effet des optimisations du compilateur. Des
petits essais avec le code qui ne fait rien ne prouve rien,
parce que l'optimisateur arrive souvent à supprimer ce que tu
essaies de mesurer. Donc, dans ton code (corriger pour qu'il
compile), avec g++, il y a une différence énorme, parce que g++
supprime complètement la deuxième boucle, mais pas la première
(même avec -O3).

--
James Kanze (GABI Software) email:
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
James Kanze
Le #17806661
On Nov 10, 3:58 pm, Gégé [...]
Mais ce n'est pas sûr qu'il le fasse systématiquement, il faut
peut-être augmenter le niveau d'optimisation.



Qu'appelles-tu "niveau d'optimisation" ?



Est-ce que tu as lu la documentation de ton compilateur ? Sinon,
pourquoi pas ? C'est la première chose à faire quand on se
trouve devant un nouveau compilateur. Le niveau d'optimisation,
c'est bien quelque chose qu'il faut spécifier chaque fois qu'on
compile du code. D'une façon différente pour chaque compilateur.
Donc, avec g++, je vais invoquer soit :
g++ -std=c++98 -pedantic -ffor-scope -fno-gnu-keywords -foperator-
names -pipe -Wall -W -Wno-sign-compare -Wno-deprecated -Wno-non-
virtual-dtor -Wpointer-arith -Wno-unused -Wno-switch -Wno-missing-
braces -Wno-long-long -static-libgcc -O3 -fomit-frame-pointer -finline-
functions
soit:
g++ -std=c++98 -pedantic -ffor-scope -fno-gnu-keywords -foperator-
names -pipe -Wall -W -Wno-sign-compare -Wno-deprecated -Wno-non-
virtual-dtor -Wpointer-arith -Wno-unused -Wno-switch -Wno-missing-
braces -Wno-long-long -static-libgcc -ggdb3 -D_GLIBCXX_CONCEPT_CHECKS -
D_GLIBCXX_DEBUG -D_GLIBCXX_DEBUG_PEDANTIC
selon le niveau d'optimisation (et d'autres choses) voulu; pour
VC++, c'est soit :
cl -vmg -GR -Gy -EHs -Zc:forScope,wchar_t -J -nologo -DNOMINMAX -
D_CRT_SECURE_NO_DEPRECATE -Ox -Gs
soit
cl -vmg -GR -Gy -EHs -Zc:forScope,wchar_t -J -nologo -DNOMINMAX -
D_CRT_SECURE_NO_DEPRECATE -MTd -GS- -Zi -w -D_DEBUG

Dans les deux cas, le premier a un niveau d'optimisation plus
élevé, le deuxième fournit d'avantage d'information pour le
debogguage, et d'avantage de vérifications lors de l'exécution.

(Si tu utilises un IDE, il y a bien des onglets qui permettent à
spécifier tout ça. Il faut s'en servir.)

--
James Kanze (GABI Software) email:
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
Publicité
Poster une réponse
Anonyme