¿Puedo usar el patrón de plantilla curiosamente recurrente aquí (C++)?

Question

Tengo una aplicación C++ que se puede simplificar a algo como esto:

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)
};

Mi aplicación es crítica para el rendimiento.Normalmente hay miles de widgets en la colección.Las clases derivadas de AbstractWidget (de los cuales hay docenas) normalmente no anulan muchas de las funciones virtuales.Los que se anulan suelen tener implementaciones muy rápidas.

Teniendo esto en cuenta, siento que puedo optimizar mi sistema con una metaprogramación inteligente.El objetivo es aprovechar la integración de funciones y evitar llamadas a funciones virtuales, manteniendo al mismo tiempo el código manejable.He examinado el patrón de plantilla curiosamente recurrente (ver aquí para descripción).Esto parece casi hacer lo que quiero, pero no del todo.

¿Hay alguna manera de hacer que el CRTP funcione para mí aquí?¿O hay alguna otra solución inteligente que se le pueda ocurrir?

Answer 1

CRTP o polimorfismo en tiempo de compilación es para cuando conoce todos sus tipos en tiempo de compilación.Mientras estés usando addWidget para recopilar una lista de widgets en tiempo de ejecución y siempre que fooAll y barAll luego tienes que manejar miembros de esa lista homogénea de widgets en tiempo de ejecución, debes poder manejar diferentes tipos en tiempo de ejecución.Entonces, para el problema que presentaste, creo que estás atascado en el uso del polimorfismo en tiempo de ejecución.

Una respuesta estándar, por supuesto, es verificar que el rendimiento del polimorfismo en tiempo de ejecución sea un problema antes de intentar evitarlo...

Si realmente necesita evitar el polimorpismo en tiempo de ejecución, entonces una de las siguientes soluciones puede funcionar.

Opción 1:Utilice una colección de widgets en tiempo de compilación

Si los miembros de su WidgetCollection se conocen en el momento de la compilación, entonces puede utilizar plantillas muy fácilmente.

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);
}

Opcion 2:Reemplace el polimorfismo en tiempo de ejecución con funciones gratuitas

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]);
    }
  }
};

Feo y realmente no OO.Las plantillas podrían ayudar con esto al reducir la necesidad de enumerar cada caso especial;Pruebe algo como lo siguiente (completamente no probado), pero en este caso no volverá a estar en línea.

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]);
      }
    }
  }
};

Opción 3:eliminar OO

OO es útil porque ayuda a gestionar la complejidad y porque ayuda a mantener la estabilidad ante el cambio.Para las circunstancias que parece estar describiendo (miles de widgets, cuyo comportamiento generalmente no cambia y cuyos métodos de miembro son muy simples), es posible que no tenga mucha complejidad o cambios que administrar.Si ese es el caso, es posible que no necesite OO.

Esta solución es la misma que el polimorfismo en tiempo de ejecución, excepto que requiere que mantenga una lista estática de métodos "virtuales" y subclases conocidas (que no son OO) y le permite reemplazar las llamadas a funciones virtuales con una tabla de salto a funciones en línea.

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

El enlace dinámico simulado (hay otros usos de CRTP) es para cuando el clase base se considera polimórfico, pero clientela En realidad, solo se preocupa por una clase derivada en particular.Entonces, por ejemplo, es posible que tenga clases que representen una interfaz en alguna funcionalidad específica de la plataforma, y ​​cualquier plataforma determinada solo necesitará una implementación.El objetivo del patrón es crear una plantilla para la clase base, de modo que aunque haya varias clases derivadas, la clase base sepa en el momento de la compilación cuál está en uso.

No le ayuda cuando realmente necesita polimorfismo en tiempo de ejecución, como por ejemplo cuando tiene un contenedor de AbstractWidget*, cada elemento puede ser una de varias clases derivadas y hay que iterar sobre ellas.En CRTP (o cualquier código de plantilla), base<derived1> y base<derived2> son clases no relacionadas.Por lo tanto también lo son derived1 y derived2.No hay polimorfismo dinámico entre ellos a menos que tengan otra clase base común, pero luego regresa al punto de partida con las llamadas virtuales.

Podrías obtener algo de aceleración reemplazando tu vector con varios vectores:uno para cada una de las clases derivadas que conoce y uno genérico para cuando agregue nuevas clases derivadas más adelante y no actualice el contenedor.Luego addWidget hace algo (lento) typeid verificación o una llamada virtual al widget, para agregar el widget al contenedor correcto, y tal vez tenga algunas sobrecargas para cuando la persona que llama conoce la clase de tiempo de ejecución.Tenga cuidado de no agregar accidentalmente una subclase de WidgetIKnowAbout hacia WidgetIKnowAbout* vector. fooAll y barAll puede recorrer cada contenedor a su vez haciendo llamadas (rápidas) a no virtuales fooImpl y barImpl funciones que luego se insertarán.Luego recorren el que, con suerte, será mucho más pequeño. AbstractWidget* vector, llamando a lo virtual foo o bar funciones.

Es un poco complicado y no es puro OO, pero si casi todos sus widgets pertenecen a clases que su contenedor conoce, es posible que vea un aumento en el rendimiento.

Tenga en cuenta que si la mayoría de los widgets pertenecen a clases que su contenedor no puede conocer (porque están en diferentes bibliotecas, por ejemplo), entonces no es posible tenerlos en línea (a menos que su enlazador dinámico pueda hacerlo en línea.El mío no puede).Podría eliminar la sobrecarga de la llamada virtual jugando con los punteros de funciones miembro, pero la ganancia casi con seguridad sería insignificante o incluso negativa.La mayor parte de la sobrecarga de una llamada virtual está en la llamada misma, no en la búsqueda virtual, y las llamadas a través de punteros de función no estarán integradas.

Míralo de otra manera:Si el código va a estar integrado, eso significa que el código de máquina real debe ser diferente para los diferentes tipos.Esto significa que necesita varios bucles o un bucle con un interruptor, porque el código de máquina claramente no puede cambiar en la ROM en cada paso por el bucle, según el tipo de algún puntero extraído de una colección.

Bueno, supongo que tal vez el objeto podría contener algún código ASM que el bucle copia en la RAM, lo marca como ejecutable y salta al mismo.Pero esa no es una función miembro de C++.Y no se puede hacer de forma portátil.Y probablemente ni siquiera sería rápido, con la copia y la invalidación de icache.Por eso existen las llamadas virtuales...

Answer 3

La respuesta corta es no.

La respuesta larga (o aún breve hizo campaña para otras respuestas :-)

Usted está tratando dinámicamente de averiguar qué función ejecutar en tiempo de ejecución (eso es lo que son las funciones virtuales). Si tiene un vector (cuyos miembros no pueden determinarse en el momento de la compilación), entonces no puede encontrar la manera de integrar las funciones sin importar lo que intente.

El único caviat para eso es que si los vectores siempre contienen los mismos elementos (es decir, podría calcular en tiempo de compilación qué se ejecutará en tiempo de ejecución). Luego podría volver a trabajar esto, pero requeriría algo más que un vector para contener los elementos (probablemente una estructura con todos los elementos como miembros).

Además, ¿realmente crees que el despacho virtual es un cuello de botella?
Personalmente lo dudo mucho.

Answer 4

El problema que tendrá aquí es con WidgetCollection::widgets. Un vector solo puede contener elementos de un tipo, y el uso de CRTP requiere que cada AbstractWidget tenga un tipo diferente, con el tipo derivado deseado. Es decir, tu Derived se vería así:

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

Lo que significa que cada AbstractWidget< Derived > con un tipo <=> diferente constituiría un tipo diferente <=>. Almacenar todo esto en un solo vector no funcionará. Parece que, en este caso, las funciones virtuales son el camino a seguir.

Answer 5

No si necesitas un vector de ellos. Los contenedores STL son completamente homogéneos, lo que significa que si necesita almacenar un widgetA y un widgetB en el mismo contenedor, deben heredarse de un padre común. Y, si widgetA :: bar () hace algo diferente a widgetB :: bar (), debe hacer que las funciones sean virtuales.

¿Todos los widgets deben estar en el mismo contenedor? Podrías hacer algo como

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

Y luego las funciones no tendrían que ser virtuales.

Answer 6

Lo más probable es que después de realizar todo ese esfuerzo, no verá ninguna diferencia de rendimiento.

Esta es absolutamente la forma incorrecta de optimizar. No corregirías un error lógico cambiando líneas de código aleatorias, ¿verdad? No, eso es tonto. No & "; Arregla &"; código hasta que encuentre por primera vez qué líneas realmente están causando su problema. Entonces, ¿por qué trataría los errores de rendimiento de manera diferente?

Necesita crear un perfil de su aplicación y encontrar dónde están los cuellos de botella reales. Luego, acelere ese código y vuelva a ejecutar el generador de perfiles. Repita hasta que desaparezca el error de rendimiento (ejecución demasiado lenta).