¿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 solicitud es el rendimiento crítico. En general, hay miles de widgets en la colección. Las clases derivadas de AbstractWidget (de las cuales hay docenas) generalmente dejan muchas de las funciones virtuales no anuladas. Los que se reemplazan suelen tener implementaciones muy rápidas.

Dado esto, siento que puedo optimizar mi sistema con una meta-programación inteligente. El objetivo es aprovechar la función en línea y evitar las llamadas a funciones virtuales, mientras se mantiene el código manejable. He investigado el patrón de plantilla curiosamente recurrente (consulte here para obtener una descripción). Esto parece casi hacer lo que quiero, pero no del todo.

¿Hay alguna manera de hacer que el CRTP me funcione aquí? O, ¿hay alguna otra solución inteligente en la que se pueda pensar?

Answer 1

CRTP o polimorfismo en tiempo de compilación es para cuando conoce todos sus tipos en tiempo de compilación. Siempre que use addWidget para recopilar una lista de widgets en tiempo de ejecución y siempre que fooAll y barAll tengan que manejar miembros de esa lista homogénea de widgets en tiempo de ejecución, debe ser capaz de manejar diferentes tipos en tiempo de ejecución. Entonces, para el problema que has presentado, creo que estás atrapado usando el polimorfismo en tiempo de ejecución.

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

Si realmente necesita para evitar polimorfismo en tiempo de ejecución, a continuación, una de las siguientes las soluciones pueden funcionar

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

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

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

Opción 2: Reemplazar 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; intente algo como lo siguiente (completamente no probado), pero está de vuelta a no incluir en este caso.

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 en la cara del cambio. Para las circunstancias que pareces estar describiendo, miles de widgets, cuyo comportamiento generalmente no cambia, y cuyos métodos miembros son muy simples, es posible que no tengas mucha complejidad o cambios para administrar. Si ese es el caso, entonces es posible que no necesite OO.

Esta solución es igual que el polimorfismo de tiempo de ejecución, excepto que requiere mantener una lista estática de métodos "virtuales" y subclases conocidas (que no es OO) y le permite reemplazar llamadas de funciones virtuales con una tabla de salto a funciones inline

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 problema que tendrá aquí es con WidgetCollection::widgets. Un vector solo puede contener elementos de un tipo, y usar el CRTP requiere que cada AbstractWidget tenga un tipo diferente, con plantilla del tipo derivado deseado. Es decir, que está AbstractWidget sería algo como esto:

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

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

Answer 3

No si necesita 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 ser heredados de un padre común. Y, si widgetA :: bar() hace algo diferente de widgetB :: bar(), debe hacer que las funciones sean virtuales.

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

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

Y entonces las funciones no necesitarían ser virtuales.

Answer 4

de unión (hay otros usos de CRTP) es para cuando la clase base de piensa de sí mismo como ser polimórfico, pero clientes en realidad sólo se preocupan por una clase derivada dinámica particular simulado. Entonces, por ejemplo, puede tener clases que representen una interfaz en alguna funcionalidad específica de la plataforma, y ​​cualquier plataforma dada solo necesitará una implementación. El objetivo del patrón es templar la clase base, de modo que, aunque haya múltiples clases derivadas, la clase base sepa, en tiempo de compilación, cuál de ellas está en uso.

No es de 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 debe iterar sobre ellos. 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 regresas al lugar donde comenzaste con llamadas virtuales.

Puede obtener cierta velocidad al reemplazar su vector con varios vectores: uno para cada una de las clases derivadas que conozca, y uno genérico para cuando agrega nuevas clases derivadas más tarde y no actualiza el contenedor. A continuación, addWidget realiza una comprobación (lenta) de typeid o una llamada virtual al widget, para agregar el widget al contenedor correcto, y tal vez tiene algunas sobrecargas cuando el llamante conoce la clase de tiempo de ejecución. Tenga cuidado de no agregar accidentalmente una subclase de WidgetIKnowAbout al vector WidgetIKnowAbout*. fooAll y barAll pueden pasar por encima de cada contenedor haciendo llamadas (rápidas) a no virtuales fooImpl y barImpl funciones que luego serán inline. Luego recorren el vector AbstractWidget*, que es mucho más pequeño, llamando a las funciones virtuales foo o bar.

Es un poco desordenado y no puro OO, pero si casi todos sus widgets pertenecen a las clases que su contenedor conoce, entonces 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 posiblemente no pueda conocer (porque están en diferentes bibliotecas, por ejemplo), entonces no es posible que tenga en línea (a menos que su enlazador dinámico pueda alinearse. 't). Podría eliminar la sobrecarga de las llamadas virtuales al jugar con los punteros de funciones de los miembros, pero la ganancia casi seguramente sería insignificante o incluso negativa. La mayor parte de la sobrecarga de una llamada virtual está en la llamada en sí, no en la búsqueda virtual, y las llamadas a través de punteros a función no estarán en línea.

Mírelo de otra manera: si el código va a estar en línea, eso significa que el código de máquina real tiene que ser diferente para los diferentes tipos. Esto significa que necesita múltiples bucles, o un bucle con un interruptor, porque el código de máquina claramente no puede cambiar en ROM en cada pasada a través del bucle, de acuerdo con el tipo de 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 copie en la RAM, marque ejecutable y salte. 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 llamadas virtuales ...

Answer 5

La respuesta corta es no.

La respuesta larga (o aún por debajo campared a algunas otras respuestas :-)

Usted está tratando de forma dinámica para averiguar cuál es la función de ejecutar en tiempo de ejecución (que 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 determinar cómo alinear las funciones sin importar lo que intente.

El único inconveniente es que si los vectores siempre contienen los mismos elementos (es decir, se puede calcular un tiempo de compilación, lo que se va a 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 6

Las probabilidades indican que después de realizar todo ese esfuerzo, no verá ninguna diferencia en el rendimiento.

Esto es absolutamente el incorrecto manera de optimizar. No arreglarías un error lógico cambiando las líneas de código al azar, ¿o sí? No, eso es tonto. No "arregla" el código hasta que primero encuentre qué líneas están causando realmente su problema. Entonces, ¿por qué trataría el rendimiento errores de manera diferente?

Es necesario que el perfil de su aplicación y encontrar dónde están los cuellos de botella reales. A continuación, agilice ese código y vuelva a ejecutar el generador de perfiles. Repita hasta que el error de rendimiento (ejecución muy lenta) se haya ido.