Quel est le coût des performances d'avoir une méthode virtuelle dans une classe C ++?

Avoir au moins une méthode virtuelle dans une classe C ++ (ou l'une de ses classes parentes) signifie que la classe aura une table virtuelle et que chaque instance aura un pointeur virtuel.

Le coût de la mémoire est donc assez clair. Le plus important est le coût de la mémoire sur les instances (surtout si les instances sont petites, par exemple si elles sont juste censées contenir un entier: dans ce cas, avoir un pointeur virtuel dans chaque instance peut doubler la taille des instances. l'espace mémoire utilisé par les tables virtuelles, je suppose qu'il est généralement négligeable par rapport à l'espace utilisé par le code de méthode réel.

Cela m'amène à ma question: y a-t-il un coût de performance mesurable (c'est-à-dire un impact sur la vitesse) pour rendre une méthode virtuelle? Il y aura une recherche dans la table virtuelle au moment de l'exécution, à chaque appel de méthode, donc s'il y a des appels très fréquents à cette méthode, et si cette méthode est très courte, alors il pourrait y avoir un impact mesurable sur les performances? Je suppose que cela dépend de la plate-forme, mais est-ce que quelqu'un a exécuté des benchmarks?

La raison pour laquelle je pose la question est que je suis tombé sur un bogue qui était dû à un programmeur oubliant de définir une méthode virtuelle. Ce n'est pas la première fois que je vois ce genre d'erreur. Et j'ai pensé: pourquoi ajoutons- nous le mot-clé virtuel en cas de besoin au lieu de supprimer le mot-clé virtuel alors que nous sommes absolument sûrs qu'il n'est pas nécessaire? Si le coût des performances est faible, je pense que je recommanderai simplement ce qui suit à mon équipe: il suffit de rendre chaque méthode virtuelle par défaut, y compris le destructeur, dans chaque classe, et de ne la supprimer que lorsque vous en avez besoin. Cela vous semble-t-il fou?

J'ai exécuté quelques timings sur un processeur PowerPC en ordre de 3 GHz. Sur cette architecture, un appel de fonction virtuelle coûte 7 nanosecondes de plus qu'un appel de fonction direct (non virtuel).

Donc, cela ne vaut pas vraiment la peine de s'inquiéter du coût à moins que la fonction ne soit quelque chose comme un accesseur trivial Get () / Set (), dans lequel tout ce qui n'est pas en ligne est un peu inutile. Un surcoût de 7ns sur une fonction alignée sur 0,5ns est sévère; une surcharge de 7ns sur une fonction qui prend 500 ms à exécuter n'a pas de sens.

Le gros coût des fonctions virtuelles n'est pas vraiment la recherche d'un pointeur de fonction dans la vtable (ce n'est généralement qu'un seul cycle), mais le saut indirect ne peut généralement pas être prédit par branche. Cela peut provoquer une grande bulle de pipeline car le processeur ne peut pas extraire d'instructions tant que le saut indirect (l'appel via le pointeur de fonction) n'a pas été retiré et qu'un nouveau pointeur d'instruction n'a pas été calculé. Ainsi, le coût d'un appel de fonction virtuelle est beaucoup plus élevé qu'il n'y paraît en regardant l'assemblage ... mais toujours seulement 7 nanosecondes.

Edit: Andrew, Not Sure et d'autres soulèvent également le très bon point qu'un appel de fonction virtuelle peut provoquer un échec du cache d'instructions: si vous sautez vers une adresse de code qui n'est pas dans le cache, tout le programme s'arrête alors que le les instructions sont extraites de la mémoire principale. C'est toujours un décrochage important: sur Xenon, environ 650 cycles (d'après mes tests).

Cependant, ce n'est pas un problème spécifique aux fonctions virtuelles car même un appel direct de fonction provoquera un échec si vous passez à des instructions qui ne sont pas dans le cache. Ce qui compte est de savoir si la fonction a été exécutée avant récemment (ce qui la rend plus susceptible d'être dans le cache), et si votre architecture peut prédire les branches statiques (non virtuelles) et récupérer ces instructions dans le cache à l'avance. Mon PPC ne le fait pas, mais peut-être que le matériel le plus récent d'Intel le fait.

Mon contrôle du temps pour l'influence d'icache manque sur l'exécution (délibérément, puisque j'essayais d'examiner le pipeline du processeur de manière isolée), donc ils actualisent ce coût.

Il y a certainement une surcharge mesurable lors de l'appel d'une fonction virtuelle - l'appel doit utiliser la vtable pour résoudre l'adresse de la fonction pour ce type d'objet. Les instructions supplémentaires sont le cadet de vos soucis. Non seulement les vtables empêchent de nombreuses optimisations potentielles du compilateur (puisque le type est polymorphe du compilateur), ils peuvent également écraser votre I-Cache.

Bien entendu, le fait que ces pénalités soient importantes ou non dépend de votre application, de la fréquence à laquelle ces chemins de code sont exécutés et de vos modèles d'héritage.

À mon avis cependant, avoir tout comme virtuel par défaut est une solution globale à un problème que vous pourriez résoudre d'une autre manière.

Peut-être pourriez-vous regarder comment les classes sont conçues / documentées / écrites. En général, l'en-tête d'une classe doit indiquer clairement quelles fonctions peuvent être remplacées par des classes dérivées et comment elles sont appelées. Demander aux programmeurs d'écrire cette documentation est utile pour s'assurer qu'ils sont correctement marqués comme virtuels.

Je dirais aussi que déclarer chaque fonction comme virtuelle pourrait conduire à plus de bogues que simplement oublier de marquer quelque chose comme virtuel. Si toutes les fonctions sont virtuelles, tout peut être remplacé par des classes de base - publiques, protégées, privées - tout devient un jeu équitable. Par accident ou intentionnellement, les sous-classes pourraient alors changer le comportement des fonctions qui causent alors des problèmes lorsqu'elles sont utilisées dans l'implémentation de base.

Ça dépend. :) (Vous attendiez-vous à autre chose?)

Une fois qu'une classe obtient une fonction virtuelle, elle ne peut plus être un type de données POD, (il se peut qu'elle n'en ait pas été avant non plus, auquel cas cela ne fera pas de différence) et cela rend toute une gamme d'optimisations impossible.

std :: copy () sur les types POD simples peut recourir à une simple routine memcpy, mais les types non-POD doivent être traités plus soigneusement.

La construction devient beaucoup plus lente car la vtable doit être initialisée. Dans le pire des cas, la différence de performances entre les types de données POD et non POD peut être significative.

Dans le pire des cas, vous constaterez peut-être une exécution 5 fois plus lente (ce nombre provient d'un projet universitaire que j'ai réalisé récemment pour réimplémenter quelques classes de bibliothèque standard. Notre conteneur a mis environ 5 fois plus de temps à se construire dès que le type de données qu'il stockait a vtable)

Bien sûr, dans la plupart des cas, il est peu probable que vous constatiez une différence de performance mesurable, c'est simplement pour souligner que dans certains cas frontaliers, cela peut être coûteux.

Cependant, les performances ne devraient pas être votre principale considération ici. Rendre tout virtuel n'est pas une solution parfaite pour d'autres raisons.

Permettre que tout soit remplacé dans les classes dérivées rend la gestion des invariants de classe beaucoup plus difficile. Comment une classe garantit-elle qu'elle reste dans un état cohérent lorsqu'une de ses méthodes peut être redéfinie à tout moment?

Rendre tout virtuel peut éliminer quelques bogues potentiels, mais cela en introduit également de nouveaux.

Si vous avez besoin de la fonctionnalité d'envoi virtuel, vous devez en payer le prix. L'avantage de C ++ est que vous pouvez utiliser une implémentation très efficace de répartition virtuelle fournie par le compilateur, plutôt qu'une version éventuellement inefficace que vous implémentez vous-même.

Cependant, vous encombrer de frais généraux si vous n'en avez pas besoin, cela va peut-être un peu trop loin. Et la plupart des classes ne sont pas conçues pour être héritées - pour créer une bonne classe de base, il faut plus que rendre ses fonctions virtuelles.

La distribution virtuelle est un ordre de grandeur plus lente que certaines alternatives - pas tant en raison de l'indirection que de la prévention de l'inlining. Ci-dessous, j'illustre cela en comparant l'envoi virtuel avec une implémentation intégrant un "numéro d'identification de type" dans les objets et en utilisant une instruction switch pour sélectionner le code spécifique au type. Cela évite complètement la surcharge des appels de fonction - il suffit de faire un saut local. Il y a un coût potentiel pour la maintenabilité, les dépendances de recompilation, etc. par la localisation forcée (dans le commutateur) de la fonctionnalité spécifique au type.

LA MISE EN OEUVRE

#include <iostream>
#include <vector>

// virtual dispatch model...

struct Base
{
    virtual int f() const { return 1; }
};

struct Derived : Base
{
    virtual int f() const { return 2; }
};

// alternative: member variable encodes runtime type...

struct Type
{
    Type(int type) : type_(type) { }
    int type_;
};

struct A : Type
{
    A() : Type(1) { }
    int f() const { return 1; }
};

struct B : Type
{
    B() : Type(2) { }
    int f() const { return 2; }
};

struct Timer
{
    Timer() { clock_gettime(CLOCK_MONOTONIC, &from); }
    struct timespec from;
    double elapsed() const
    {
        struct timespec to;
        clock_gettime(CLOCK_MONOTONIC, &to);
        return to.tv_sec - from.tv_sec + 1E-9 * (to.tv_nsec - from.tv_nsec);
    }
};

int main(int argc)
{
  for (int j = 0; j < 3; ++j)
  {
    typedef std::vector<Base*> V;
    V v;

    for (int i = 0; i < 1000; ++i)
        v.push_back(i % 2 ? new Base : (Base*)new Derived);

    int total = 0;

    Timer tv;

    for (int i = 0; i < 100000; ++i)
        for (V::const_iterator i = v.begin(); i != v.end(); ++i)
            total += (*i)->f();

    double tve = tv.elapsed();

    std::cout << "virtual dispatch: " << total << ' ' << tve << '\n';

    // ----------------------------

    typedef std::vector<Type*> W;
    W w;

    for (int i = 0; i < 1000; ++i)
        w.push_back(i % 2 ? (Type*)new A : (Type*)new B);

    total = 0;

    Timer tw;

    for (int i = 0; i < 100000; ++i)
        for (W::const_iterator i = w.begin(); i != w.end(); ++i)
        {
            if ((*i)->type_ == 1)
                total += ((A*)(*i))->f();
            else
                total += ((B*)(*i))->f();
        }

    double twe = tw.elapsed();

    std::cout << "switched: " << total << ' ' << twe << '\n';

    // ----------------------------

    total = 0;

    Timer tw2;

    for (int i = 0; i < 100000; ++i)
        for (W::const_iterator i = w.begin(); i != w.end(); ++i)
            total += (*i)->type_;

    double tw2e = tw2.elapsed();

    std::cout << "overheads: " << total << ' ' << tw2e << '\n';
  }
}

RÉSULTATS DE PERFORMANCE

Sur mon système Linux:

~/dev  g++ -O2 -o vdt vdt.cc -lrt
~/dev  ./vdt                     
virtual dispatch: 150000000 1.28025
switched: 150000000 0.344314
overhead: 150000000 0.229018
virtual dispatch: 150000000 1.285
switched: 150000000 0.345367
overhead: 150000000 0.231051
virtual dispatch: 150000000 1.28969
switched: 150000000 0.345876
overhead: 150000000 0.230726

Cela suggère qu'une approche à commutation de numéro de type en ligne est d'environ (1,28 - 0,23) / (0,344 - 0,23) = 9,2 fois plus rapide. Bien sûr, cela est spécifique au système exact testé / aux indicateurs et à la version du compilateur, etc., mais généralement à titre indicatif.

COMMENTAIRES CONCERNANT L'EXPÉDITION VIRTUELLE

Il faut dire cependant que les frais généraux des appels de fonction virtuelle sont rarement significatifs, et seulement pour les fonctions souvent appelées triviales (comme les getters et les setters). Même dans ce cas, vous pourriez être en mesure de fournir une seule fonction pour obtenir et définir un grand nombre de choses à la fois, en minimisant le coût. Les gens s'inquiètent beaucoup trop de la répartition virtuelle - alors faites le profilage avant de trouver des alternatives peu pratiques. Le principal problème avec eux est qu'ils effectuent un appel de fonction hors ligne, bien qu'ils délocalisent également le code exécuté, ce qui modifie les modèles d'utilisation du cache (pour le meilleur ou (plus souvent) pour le pire).

Le coût supplémentaire n'est pratiquement rien dans la plupart des scénarios. (pardonnez la blague). ejac a déjà affiché des mesures relatives sensibles.

La plus grande chose à laquelle vous renoncez, ce sont les optimisations possibles dues à l'inlining. Ils peuvent être particulièrement utiles si la fonction est appelée avec des paramètres constants. Cela fait rarement une réelle différence, mais dans quelques cas, cela peut être énorme.

Concernant les optimisations:
Il est important de connaître et de considérer le coût relatif des constructions de votre langage. Notation Big O est la moitié ONL de l'histoire - comment votre échelle d'application . L'autre moitié est le facteur constant devant lui.

En règle générale, je ne ferais pas tout mon possible pour éviter les fonctions virtuelles, à moins qu'il n'y ait des indications claires et spécifiques indiquant qu'il s'agit d'un goulot d'étranglement. Une conception propre passe toujours en premier, mais ce n'est qu'une partie prenante qui ne devrait pas indûment blesser les autres.

Exemple artificiel: un destructeur virtuel vide sur un tableau d'un million de petits éléments peut parcourir au moins 4 Mo de données, détruisant votre cache. Si ce destructeur peut être intégré, les données ne seront pas touchées.

Lors de l'écriture de code de bibliothèque, de telles considérations sont loin d'être prématurées. Vous ne savez jamais combien de boucles seront placées autour de votre fonction.

Alors que tout le monde a raison sur les performances des méthodes virtuelles et autres, je pense que le vrai problème est de savoir si l'équipe connaît la définition du mot-clé virtuel en C ++.

Considérez ce code, quelle est la sortie?

#include <stdio.h>

class A
{
public:
    void Foo()
    {
        printf("A::Foo()\n");
    }
};

class B : public A
{
public:
    void Foo()
    {
        printf("B::Foo()\n");
    }
};

int main(int argc, char** argv)
{    
    A* a = new A();
    a->Foo();

    B* b = new B();
    b->Foo();

    A* a2 = new B();
    a2->Foo();

    return 0;
}

Rien d'étonnant ici:

A::Foo()
B::Foo()
A::Foo()

Comme rien n'est virtuel. Si le mot-clé virtuel est ajouté au début de Foo dans les classes A et B, nous obtenons ceci pour la sortie:

A::Foo()
B::Foo()
B::Foo()

À peu près ce que tout le monde attend.

Maintenant, vous avez mentionné qu'il y a des bogues parce que quelqu'un a oublié d'ajouter un mot-clé virtuel. Considérez donc ce code (où le mot-clé virtuel est ajouté à A, mais pas à la classe B). Quelle est la sortie alors?

#include <stdio.h>

class A
{
public:
    virtual void Foo()
    {
        printf("A::Foo()\n");
    }
};

class B : public A
{
public:
    void Foo()
    {
        printf("B::Foo()\n");
    }
};

int main(int argc, char** argv)
{    
    A* a = new A();
    a->Foo();

    B* b = new B();
    b->Foo();

    A* a2 = new B();
    a2->Foo();

    return 0;
}

Réponse: La même chose que si le mot-clé virtuel est ajouté à B? La raison en est que la signature de B :: Foo correspond exactement à A :: Foo () et parce que A de Foo est virtuel, B l'est aussi.

Considérons maintenant le cas où le Foo de B est virtuel et celui de A ne l'est pas. Quelle est la sortie alors? Dans ce cas, la sortie est

A::Foo()
B::Foo()
A::Foo()

Le mot-clé virtuel fonctionne vers le bas dans la hiérarchie, pas vers le haut. Cela ne rend jamais les méthodes de classe de base virtuelles. La première fois qu'une méthode virtuelle est rencontrée dans la hiérarchie, c'est lorsque le polymorphisme commence. Il n'y a pas de moyen pour les classes ultérieures de faire en sorte que les classes précédentes aient des méthodes virtuelles.

N'oubliez pas que les méthodes virtuelles signifient que cette classe donne aux futures classes la possibilité de remplacer / modifier certains de ses comportements.

Donc, si vous avez une règle pour supprimer le mot-clé virtuel, cela peut ne pas avoir l'effet escompté.

Le mot clé virtuel en C ++ est un concept puissant. Vous devez vous assurer que chaque membre de l'équipe connaît vraiment ce concept afin qu'il puisse être utilisé comme prévu.

En fonction de votre plate-forme, la surcharge d'un appel virtuel peut être très indésirable. En déclarant chaque fonction virtuelle, vous les appelez essentiellement toutes via un pointeur de fonction. À tout le moins, il s'agit d'une déréférence supplémentaire, mais sur certaines plates-formes PPC, il utilisera des instructions microcodées ou autrement lentes pour y parvenir.

Je déconseille votre suggestion pour cette raison, mais si cela vous aide à éviter les bugs, cela vaut peut-être la peine de faire un compromis. Je ne peux pas m'empêcher de penser qu'il doit y avoir un terrain d'entente qui vaut la peine d'être trouvé.

Il faudra juste quelques instructions asm supplémentaires pour appeler la méthode virtuelle.

Mais je ne pense pas que vous vous inquiétez du fait que fun (int a, int b) ait quelques instructions supplémentaires 'push' par rapport à fun (). Ne vous inquiétez donc pas non plus des virtuels, jusqu'à ce que vous soyez dans une situation particulière et que vous ne voyiez pas que cela entraîne vraiment des problèmes.

PS Si vous avez une méthode virtuelle, assurez-vous d'avoir un destructeur virtuel. De cette façon, vous éviterez d'éventuels problèmes

En réponse aux commentaires «xtofl» et «Tom». J'ai fait de petits tests avec 3 fonctions:

1. Virtuel
2. Ordinaire
3. Normal avec 3 paramètres int

Mon test était une simple itération:

for(int it = 0; it < 100000000; it ++) {
    test.Method();
}

Et voici les résultats:

1. 3,913 secondes
2. 3873 secondes
3. 3 970 secondes

Il a été compilé par VC ++ en mode débogage. Je n'ai fait que 5 tests par méthode et calculé la valeur moyenne (les résultats peuvent donc être assez inexacts) ... Quoi qu'il en soit, les valeurs sont presque égales en supposant 100 millions d'appels. Et la méthode avec 3 push / pop supplémentaires était plus lente.

Le point principal est que si vous n'aimez pas l'analogie avec le push / pop, pensez à plus de if / else dans votre code? Pensez-vous au pipeline CPU lorsque vous ajoutez un supplément if / else ;-) De plus, vous ne savez jamais sur quel CPU le code sera exécuté ... Un compilateur habituel peut générer du code plus optimal pour un CPU et moins optimal pour un autre ( Intel Compilateur C ++ )