Puis-je utiliser le modèle de modèle curieusement récurrent ici (C ++)?

Question

J'ai une application C ++ qui peut être simplifiée comme suit:

class AbstractWidget {
 public:
  virtual ~AbstractWidget() {}
  virtual void foo() {}
  virtual void bar() {}
  // (other virtual methods)
};

class WidgetCollection {
 private:
  vector<AbstractWidget*> widgets;

 public:
  void addWidget(AbstractWidget* widget) {
    widgets.push_back(widget);
  }

  void fooAll() {
    for (unsigned int i = 0; i < widgets.size(); i++) {
      widgets[i]->foo();
    }
  }

  void barAll() {
    for (unsigned int i = 0; i < widgets.size(); i++) {
      widgets[i]->bar();
    }
  }

  // (other *All() methods)
};

Mon application est critique pour la performance. Il existe généralement des milliers de widgets dans la collection. Les classes dérivées de AbstractWidget (il y en a des dizaines) la plupart des fonctions virtuelles ne sont pas remplacées. Ceux qui sont remplacés ont généralement des implémentations très rapides.

Cela étant dit, j’estime pouvoir optimiser mon système grâce à une méta-programmation intelligente. L’objectif est d’exploiter l’intégration de fonctions et d’éviter les appels de fonctions virtuelles, tout en maintenant le code gérable. J'ai examiné le modèle de modèle curieusement récurrent (voir ici pour obtenir une description). Cela semble presque faire ce que je veux, mais pas tout à fait.

Y at-il un moyen de faire fonctionner le CRTP pour moi ici? Ou bien, y a-t-il une autre solution intelligente à laquelle on puisse penser?

Answer 1

Le polymorphisme CRTP ou au moment de la compilation est utilisé lorsque vous connaissez tous vos types au moment de la compilation. Tant que vous utilisez addWidget pour collecter une liste de widgets au moment de l'exécution et que fooAll et barAll doivent alors gérer les membres de cette liste homogène de widgets au moment de l'exécution, vous devez être capable de gérer différents types à l'exécution. Donc, pour le problème que vous avez présenté, je pense que vous êtes bloqué par le polymorphisme d'exécution.

Une réponse standard consiste bien sûr à vérifier que les performances du polymorphisme à l'exécution sont un problème avant d'essayer de l'éviter ...

Si vous devez vraiment éviter le polymorpisme au moment de l'exécution, l'une des solutions suivantes peut fonctionner.

Option 1: utiliser une collection de widgets à la compilation

Si les membres de votre WidgetCollection sont connus au moment de la compilation, vous pouvez très facilement utiliser des modèles.

template<typename F>
void WidgetCollection(F functor)
{
  functor(widgetA);
  functor(widgetB);
  functor(widgetC);
}

// Make Foo a functor that's specialized as needed, then...

void FooAll()
{
  WidgetCollection(Foo);
}

Option 2: remplacement du polymorphisme d'exécution par des fonctions libres

class AbstractWidget {
 public:
  virtual AbstractWidget() {}
  // (other virtual methods)
};

class WidgetCollection {
 private:
  vector<AbstractWidget*> defaultFooableWidgets;
  vector<AbstractWidget*> customFooableWidgets1;
  vector<AbstractWidget*> customFooableWidgets2;      

 public:
  void addWidget(AbstractWidget* widget) {
    // decide which FooableWidgets list to push widget onto
  }

  void fooAll() {
    for (unsigned int i = 0; i < defaultFooableWidgets.size(); i++) {
      defaultFoo(defaultFooableWidgets[i]);
    }
    for (unsigned int i = 0; i < customFooableWidgets1.size(); i++) {
      customFoo1(customFooableWidgets1[i]);
    }
    for (unsigned int i = 0; i < customFooableWidgets2.size(); i++) {
      customFoo2(customFooableWidgets2[i]);
    }
  }
};

Moche, et vraiment pas OO. Les modèles pourraient y contribuer en réduisant la nécessité de répertorier tous les cas particuliers; essayez quelque chose comme ce qui suit (complètement non testé), mais dans ce cas, vous n’êtes plus en ligne.

class AbstractWidget {
 public:
  virtual AbstractWidget() {}
};

class WidgetCollection {
 private:
  map<void(AbstractWidget*), vector<AbstractWidget*> > fooWidgets;

 public:
  template<typename T>
  void addWidget(T* widget) {
    fooWidgets[TemplateSpecializationFunctionGivingWhichFooToUse<widget>()].push_back(widget);
  }

  void fooAll() {
    for (map<void(AbstractWidget*), vector<AbstractWidget*> >::const_iterator i = fooWidgets.begin(); i != fooWidgets.end(); i++) {
      for (unsigned int j = 0; j < i->second.size(); j++) {
        (*i->first)(i->second[j]);
      }
    }
  }
};

Option 3: Éliminer l'OO

OO est utile car il aide à gérer la complexité et à maintenir la stabilité face au changement. Pour les circonstances que vous semblez décrire - des milliers de widgets, dont le comportement ne change généralement pas et dont les méthodes de membre sont très simples - vous n’avez peut-être pas beaucoup de complexité ou de changement à gérer. Si tel est le cas, vous n’avez peut-être pas besoin de OO.

Cette solution est identique au polymorphisme d’exécution, à la différence près que vous devez conserver une liste statique de & "virtual &"; méthodes et des sous-classes connues (qui ne sont pas OO) et vous permet de remplacer les appels de fonctions virtuelles par une table de saut de fonctions en ligne.

class AbstractWidget {
 public:
  enum WidgetType { CONCRETE_1, CONCRETE_2 };
  WidgetType type;
};

class WidgetCollection {
 private:
  vector<AbstractWidget*> mWidgets;

 public:
  void addWidget(AbstractWidget* widget) {
    widgets.push_back(widget);
  }

  void fooAll() {
    for (unsigned int i = 0; i < widgets.size(); i++) {
      switch(widgets[i]->type) {
        // insert handling (such as calls to inline free functions) here
      }
    }
  }
};

Answer 2

La liaison dynamique simulée (il existe d’autres utilisations du protocole CRTP) s’applique lorsque la classe de base se considère comme polymorphe, alors que les clients ne s’intéressent qu’à un seul dérivé classe. Ainsi, par exemple, vous pourriez avoir des classes représentant une interface dans une fonctionnalité spécifique à une plate-forme, et toute plate-forme donnée n'aura jamais besoin que d'une implémentation. Le but du modèle est de gabarit la classe de base, de sorte que même s’il existe plusieurs classes dérivées, la classe de base sait au moment de la compilation laquelle est utilisée.

Cela ne vous aide pas lorsque vous avez réellement besoin d'un polymorphisme à l'exécution, comme par exemple lorsque vous avez un conteneur de AbstractWidget*, chaque élément peut être l'une de plusieurs classes dérivées, et vous devez effectuer une itération dessus. Dans CRTP (ou tout autre code de modèle), base<derived1> et base<derived2> sont des classes non liées. Il en va de même pour derived1 et derived2. Il n'y a pas de polymorphisme dynamique entre eux sauf s'ils ont une autre classe de base commune, mais vous êtes de retour là où vous avez commencé avec des appels virtuels.

Vous pouvez accélérer le processus en remplaçant votre vecteur par plusieurs vecteurs: un pour chaque classe dérivée que vous connaissez et un générique pour ajouter ultérieurement de nouvelles classes dérivées sans mettre à jour le conteneur. Ensuite, addWidget effectue une vérification (lente) typeid ou un appel virtuel au widget, pour ajouter le widget au conteneur approprié, et peut-être des surcharges lorsque l'appelant connaît la classe d'exécution. Veillez à ne pas ajouter accidentellement une sous-classe de WidgetIKnowAbout au vecteur WidgetIKnowAbout*. fooAll et barAll peuvent effectuer une boucle sur chaque conteneur en effectuant des appels (rapides) aux fonctions non virtuelles fooImpl et barImpl qui seront ensuite insérées en ligne. Ils effectuent ensuite une boucle sur le vecteur foo, espérons-le beaucoup plus petit, en appelant les fonctions virtuelles bar ou <=>.

C'est un peu brouillon et pas pur-OO, mais si presque tous vos widgets appartiennent à des classes connues de votre conteneur, vous constaterez peut-être une augmentation de ses performances.

Notez que si la plupart des widgets appartiennent à des classes que votre conteneur ne peut pas connaître (parce qu'elles se trouvent dans des bibliothèques différentes, par exemple), vous ne pouvez pas avoir la possibilité d'inline (à moins que votre éditeur de liens dynamique puisse être intégré. Mine peut " t). Vous pouvez supprimer la surcharge d'appels virtuels en décochant des pointeurs sur les fonctions des membres, mais le gain sera presque certainement négligeable, voire négatif. La majeure partie de la surcharge d'un appel virtuel se trouve dans l'appel lui-même, et non dans la recherche virtuelle, et les appels via les pointeurs de fonction ne seront pas en ligne.

Envisagez-le sous un autre angle: si le code doit être en ligne, cela signifie que le code machine réel doit être différent pour les différents types. Cela signifie que vous avez besoin de plusieurs boucles ou d'une boucle avec un commutateur, car le code machine ne peut clairement pas changer dans la ROM à chaque passage dans la boucle, en fonction du type de pointeur extrait d'une collection.

Eh bien, je suppose que l’objet pourrait contenir du code asm que la boucle copie dans la RAM, marque l’exécutable et se jette dans. Mais ce n'est pas une fonction membre C ++. Et cela ne peut pas être fait de manière portable. Et ce ne serait probablement même pas rapide avec la copie et l’invalidation du icache. C’est pourquoi les appels virtuels existent ...

Answer 3

La réponse courte est non.

La réponse longue (ou encore courte à d’autres réponses: -)

Vous essayez de déterminer de manière dynamique quelle fonction doit être exécutée au moment de l’exécution (c’est ce que sont les fonctions virtuelles). Si vous avez un vecteur (dont les membres ne peuvent pas être déterminés au moment de la compilation), vous ne pouvez pas savoir comment intégrer les fonctions, quoi que vous essayiez.

Le seul inconvénient à cela est que si les vecteurs contiennent toujours les mêmes éléments (par exemple, vous pourriez calculer lors de la compilation ce qui sera exécuté au moment de l'exécution). Vous pouvez ensuite retravailler cela, mais cela nécessiterait autre chose qu'un vecteur pour contenir les éléments (probablement une structure avec tous les éléments comme membres).

Aussi, pensez-vous vraiment que l'envoi virtuel est un goulot d'étranglement?
Personnellement, j'en doute fort.

Answer 4

Le problème que vous allez avoir ici concerne WidgetCollection::widgets. Un vecteur ne peut contenir que des éléments d’un type et l’utilisation du CRTP nécessite que chaque AbstractWidget ait un type différent, modélisé par le type dérivé souhaité. C'est-à-dire que vous êtes Derived ressemblé à quelque chose comme ceci:

template< class Derived >
class AbstractWidget {
    ...
    void foo() {
        static_cast< Derived* >( this )->foo_impl();
    }        
    ...
}

Ce qui signifie que chaque AbstractWidget< Derived > de type <=> différent constituerait un type différent <=>. Tout stocker dans un seul vecteur ne fonctionnera pas. Il semble donc que, dans ce cas, les fonctions virtuelles sont la solution.

Answer 5

Pas si vous avez besoin d’un vecteur. Les conteneurs STL sont complètement homogènes, ce qui signifie que si vous devez stocker un widgetA et un widgetB dans le même conteneur, ils doivent être hérités d'un parent commun. Et si widgetA :: bar () fait quelque chose de différent de widgetB :: bar (), vous devez rendre les fonctions virtuelles.

Tous les widgets doivent-ils être dans le même conteneur? Vous pourriez faire quelque chose comme

vector<widgetA> widget_a_collection;
vector<widgetB> widget_b_collection;

Et les fonctions n'auraient pas besoin d'être virtuelles.

Answer 6

Il est peu probable qu'après tous ces efforts, vous ne constatiez aucune différence de performances.

C’est absolument la mauvaise façon d’optimiser. Vous ne corrigeriez pas un bogue logique en modifiant des lignes de code aléatoires, n'est-ce pas? Non, c'est idiot. Vous ne & Quot; ne corrigez pas & Quot; code jusqu’à ce que vous trouviez d’abord les lignes qui causent réellement votre problème. Alors, pourquoi traiteriez-vous les bogues de performance différemment?

Vous devez profiler votre application et trouver les véritables goulots d'étranglement. Puis accélérez ce code et réexécutez le profileur. Répétez cette procédure jusqu'à ce que le bogue de performance (exécution trop lente) disparaisse.