Quel est le coût en termes de performances de l'utilisation d'une méthode virtuelle dans une classe C++ ?

Question

Le fait d'avoir au moins une méthode virtuelle dans une classe C++ (ou dans 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 très 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 pourrait doubler la taille des instances. Quant à 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 réel de la méthode.

Cela m'amène à ma question : y a-t-il un coût mesurable en termes de performances (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 quelqu'un a-t-il effectué des tests de référence ?

La raison de ma question est que je suis tombé sur un bug qui était dû au fait qu'un programmeur avait oublié de définir une méthode virtuelle. Ce n'est pas la première fois que je vois ce genre d'erreur. Et je me suis demandé pourquoi nous ajouter le mot-clé virtuel lorsque cela est nécessaire au lieu de enlever le mot-clé virtuel lorsque nous sommes absolument sûrs qu'il est no nécessaire ? Si le coût de la performance est faible, je pense que je vais simplement recommander ce qui suit dans mon équipe : il suffit de faire chaque virtuelle par défaut, y compris le destructeur, dans chaque classe, et ne la supprimez que lorsque vous en avez besoin. Cela vous semble-t-il fou ?

Answer 1

J'ai couru quelques timings sur un 3ghz dans l'ordre de processeur PowerPC. Sur cette architecture, un appel de fonction virtuelle coûte 7 nanosecondes plus que directe (non virtuelle) d'appel de fonction.

Donc, pas vraiment la peine de s'inquiéter du coût, sauf si la fonction est quelque chose comme un trivial Get () et Set() accesseur, dans lequel rien d'autre que dans la ligne est le genre de gaspillage. Un 7ns frais généraux sur une fonction qui inlines à 0,5 ns est grave; un 7ns-dessus sur une fonction qui prend de 500 ms à exécuter est dénuée de sens.

Le coût énorme de fonctions virtuelles n'est pas vraiment à la recherche d'un pointeur de fonction dans la vtable (qui est habituellement juste un seul cycle), mais que le sous-saut ne peuvent généralement pas être de la branche prédit. Cela peut entraîner un grand pipeline de la bulle que le processeur ne peut pas récupérer toutes les instructions jusqu'à ce que le saut indirect (l'appel à l'aide du pointeur de fonction) a pris sa retraite et un nouveau pointeur d'instruction calculée. Ainsi, le coût d'un appel de fonction virtuelle est beaucoup plus grand qu'il ne paraît à partir de la recherche à l'assemblée... mais toujours seulement 7 nanosecondes.

Edit: Andrew, Pas Sûr, et d'autres soulèvent également le très bon point qu'un appel de fonction virtuelle peut provoquer une cache d'instructions manquer: si vous sautez à une adresse de code qui n'est pas dans le cache, alors tout le programme arrive à un cul de tourner pendant que les instructions sont lues depuis la mémoire principale. C'est toujours un important décrochage: le Xénon, à environ 650 cycles (par mes tests).

Cependant ce n'est pas un problème spécifique à des fonctions virtuelles, parce que même directement appel de fonction sera la cause d'une miss si vous sauter aux instructions qui ne sont pas dans le cache. Ce qui importe est de savoir si la fonction a été exécutée avant que récemment (en les rendant plus susceptibles d'être dans le cache), et si votre architecture peut prédire statique (et non virtuel) des branches et de l'extraction de ces instructions dans le cache à l'avance. Mon PPC n'est pas, mais peut-être que Intel les plus récents de matériel.

Mes timings de contrôler l'influence de l'icache manque à l'exécution (délibérément, car j'étais en train d'examiner le PROCESSEUR pipeline dans l'isolement), la réduction des coûts.

Answer 2

L'appel d'une fonction virtuelle entraîne une surcharge mesurable - 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 dernier de vos soucis. Non seulement les vtables empêchent de nombreuses optimisations potentielles du compilateur (puisque le type est polymorphe pour le compilateur), mais ils peuvent également détruire votre I-Cache.

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

À mon avis, le fait que tout soit virtuel par défaut est une solution générale à un problème que l'on pourrait résoudre par d'autres moyens.

Vous pourriez peut-être examiner la façon dont 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. Il est utile que les programmeurs rédigent cette documentation pour s'assurer qu'elles sont correctement marquées comme virtuelles.

Je dirais également que le fait de déclarer chaque fonction comme virtuelle pourrait entraîner plus de bogues que le simple fait d'oublier de marquer quelque chose comme virtuel. Si toutes les fonctions sont virtuelles, tout peut être remplacé par des classes de base - public, protected, private - tout devient un jeu équitable. Par accident ou intentionnellement, les sous-classes peuvent alors modifier le comportement des fonctions qui posent alors des problèmes lorsqu'elles sont utilisées dans l'implémentation de base.

Answer 3

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

Dès qu'une classe obtient une fonction virtuelle, elle ne peut plus être un type de données POD (elle peut ne pas l'avoir été auparavant, auquel cas cela ne fera pas de différence) et cela rend impossible toute une série d'optimisations.

std::copy() sur des types POD simples peut recourir à une simple routine memcpy, mais les types non-POD doivent être manipulé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 performance entre les types de données POD et non-POD peut être significative.

Dans le pire des cas, vous pouvez constater une exécution 5 fois plus lente (ce chiffre est tiré d'un projet universitaire que j'ai réalisé récemment pour réimplémenter quelques classes de la bibliothèque standard. Notre conteneur mettait environ 5 fois plus de temps à se construire dès que le type de données qu'il stockait devenait une table virtuelle).

Bien sûr, dans la plupart des cas, il est peu probable que vous constatiez une différence de performance mesurable. un peu de Dans les cas limites, cela peut être coûteux.

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

Le fait de permettre que tout soit surchargé dans les classes dérivées rend beaucoup plus difficile le maintien des invariants de classe. Comment une classe peut-elle garantir qu'elle reste dans un état cohérent lorsque n'importe laquelle de ses méthodes peut être redéfinie à tout moment ?

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

Answer 4

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

Cependant, s'encombrer des frais généraux si vous n'en avez pas besoin, c'est peut-être aller un peu trop loin. Et la plupart des classes ne sont pas conçues pour qu'on en hérite - pour créer une bonne classe de base, il ne suffit pas de rendre ses fonctions virtuelles.

Answer 5

La répartition virtuelle est un ordre de grandeur plus lent que certaines alternatives - pas tant à cause de l'indirection que de la prévention de l'inlining. J'illustre cela ci-dessous en comparant la répartition virtuelle avec une implémentation intégrant un "numéro d'identification de type" dans les objets et utilisant une instruction de commutation pour sélectionner le code spécifique au type. Cela permet d'éviter complètement le surcoût 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. à cause de la localisation forcée (dans le switch) de la fonctionnalité spécifique au type.

---

MISE EN ŒUVRE

#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 DU RENDEMENT

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 en ligne de type-nombre commuté est d'environ (1,28 - 0,23) / (0,344 - 0,23) = 9.2 fois plus vite. Bien sûr, cela dépend du système testé, de la version du compilateur, etc. mais c'est une indication générale.

---

COMMENTAIRES SUR LA RÉPARTITION VIRTUELLE

Il faut toutefois préciser que les frais généraux liés aux appels de fonctions virtuelles sont rarement significatifs, et seulement pour les fonctions dites triviales (comme les getters et setters). Même dans ce cas, il est possible 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 - faites donc le profilage avant de trouver des alternatives gênantes. Le principal problème avec ces fonctions est qu'elles effectuent un appel de fonction hors ligne, mais elles délocalisent également le code exécuté, ce qui modifie les modèles d'utilisation du cache (pour le meilleur ou (le plus souvent) pour le pire).