c++ - programacion - polimorfismo java

¿Puedes guardar en caché una búsqueda de función virtual en C++?

Question

Digamos que tengo una llamada de función virtual foo () en un puntero de clase base abstracto, mypointer-> foo (). Cuando mi aplicación se inicia, en función del contenido de un archivo, elige crear una instancia de una determinada clase concreta y asigna mypointer a esa instancia. Durante el resto de la vida de la aplicación, mypointer siempre señalará objetos de ese tipo concreto. No tengo forma de saber qué es este tipo concreto (puede ser instanciado por una fábrica en una biblioteca cargada dinámicamente). Solo sé que el tipo permanecerá igual después de la primera vez que se realiza una instancia del tipo concreto. El puntero no siempre apunta al mismo objeto, pero el objeto siempre será del mismo tipo concreto. Observe que el tipo se determina técnicamente en ''runtime'' porque está basado en el contenido de un archivo, pero que después de ''startup'' (el archivo está cargado) el tipo es fijo.

Sin embargo, en C ++ pago el costo de búsqueda de función virtual cada vez que se llama a foo durante toda la aplicación. El compilador no puede optimizar la búsqueda porque no hay manera de que sepa que el tipo de concreto no variará en el tiempo de ejecución (incluso si fue el compilador más sorprendente de la historia, no puede especular sobre el comportamiento de la carga dinámica). bibliotecas). En un lenguaje compilado JIT como Java o .NET, el JIT puede detectar que se está utilizando el mismo tipo una y otra vez y hacer cacheo en línea . Básicamente, estoy buscando una forma de hacerlo manualmente para punteros específicos en C ++.

¿Hay alguna forma en C ++ de almacenar en caché esta búsqueda? Me doy cuenta de que las soluciones pueden ser bastante hackish. Estoy dispuesto a aceptar hacks específicos de ABI / compilador si es posible escribir pruebas de configuración que descubran los aspectos relevantes del compilador ABI para que sea "prácticamente portátil", incluso si no es verdaderamente portátil.

Actualización: A los detractores: si esto no valía la pena optimizar, entonces dudo que los JIT modernos lo hicieran. ¿Cree que los ingenieros de Sun y MS estaban perdiendo el tiempo implementando el almacenamiento en caché en línea, y no lo compararon para garantizar una mejora?

Answer 1

¿Podrías usar un puntero de método?

El objetivo aquí es que el compilador cargue el puntero con la ubicación del método o función resuelta. Esto ocurriría una vez. Después de la asignación, el código accederá al método de una manera más directa.

Sé que un puntero a un objeto y acceder al método a través del punto del objeto invoca el polimorfismo en tiempo de ejecución . Sin embargo, debería haber una forma de cargar un puntero de método a un método resuelto, evitando el polimorfismo y llamando directamente a la función.

Revisé el wiki de la comunidad para introducir más discusión.

Answer 2

Entonces, lo que básicamente quieres hacer es convertir el polimorfismo de tiempo de ejecución en un polimorfismo en tiempo de compilación. Ahora aún necesita construir su aplicación para que pueda manejar múltiples "casos", pero una vez que se decide qué caso es aplicable a una ejecución, eso es todo por la duración.

Aquí hay un modelo del caso de polimorfismo en tiempo de ejecución:

struct Base {
  virtual void doit(int&)=0;
};

struct Foo : public Base {
  virtual void doit(int& n) {--n;}
};

struct Bar : public Base {
  virtual void doit(int& n) {++n;}
};

void work(Base* it,int& n) {
  for (unsigned int i=0;i<4000000000u;i++) it->doit(n);
}

int main(int argc,char**) {
  int n=0;

  if (argc>1)
    work(new Foo,n);
  else
    work(new Bar,n);

  return n;
}

Esto requiere ~ 14s para ejecutar en mi Core2, compilado con gcc 4.3.2 (Debian de 32 bits), opción -O3 .

Ahora supongamos que reemplazamos la versión de "trabajo" con una versión con plantilla (con plantilla en el tipo concreto en el que va a trabajar):

template <typename T> void work(T* it,int& n) {
  for (unsigned int i=0;i<4000000000u;i++) it->T::doit(n);
}

main no necesita actualización, pero tenga en cuenta que las 2 llamadas al work ahora desencadenan instancias y llamadas a dos funciones diferentes y específicas del tipo (consulte la función polimórfica anterior).

Hey presto se ejecuta en 0.001s. ¡No es un factor de aceleración malo para un cambio de 2 líneas! Sin embargo, tenga en cuenta que la aceleración masiva se debe completamente al compilador, una vez que se elimina la posibilidad de polimorfismo de tiempo de ejecución en la función de work , simplemente optimizando el bucle y compilando el resultado directamente en el código. Pero eso realmente hace un punto importante: en mi experiencia, las principales ventajas de utilizar este tipo de truco provienen de las oportunidades de mejorar la alineación y la optimización que permiten al compilador cuando se genera una función menos polimórfica y más específica, no desde la mera eliminación de indirección de vtable (que realmente es muy barato).

Pero realmente no recomiendo hacer cosas como esta a menos que los perfiles indiquen absolutamente que el polimorfismo en tiempo de ejecución realmente está afectando tu rendimiento. También te morderá tan pronto como alguien subclasifique Foo o Bar e intente pasarlo a una función realmente pensada para su base.

Puede encontrar esta pregunta relacionada interesante también.

Answer 3

Entonces, suponiendo que se trata de un problema fundamental que desea resolver (para evitar argumentos de optimización prematuros) e ignorando la piratería específica de la plataforma y del compilador, puede hacer una de estas dos cosas, en extremos opuestos de la complejidad:

1. Proporcione una función como parte del .dll que internamente simplemente llama directamente a la función miembro correcta. Usted paga el costo de un salto indirecto, pero al menos no paga el costo de una búsqueda vtable. Su kilometraje puede variar, pero en ciertas plataformas, puede optimizar la llamada de función indirecta.
2. Reestructurar su aplicación de modo que en lugar de llamar a una función miembro por instancia, llame a una sola función que tome una colección de instancias. Mike Acton tiene una post maravillosa (con una plataforma particular y tipo de aplicación doblada) sobre por qué y cómo debes hacer esto.

Answer 4

Hace poco hice una pregunta muy similar y obtuve la respuesta de que es posible como una extensión de GCC, pero no de manera portátil:

C ++: ¿Puntero a la versión monomórfica de la función de miembro virtual?

En particular, también lo probé con Clang y no es compatible con esta extensión (a pesar de que admite muchas otras extensiones de GCC).

Answer 5

Hay dos costos para una llamada de función virtual: la búsqueda vtable y la llamada a función.

La búsqueda vtable ya está a cargo del hardware. Las CPU modernas (suponiendo que no trabaje en una CPU integrada muy simple) predecirán la dirección de la función virtual en su predictor de bifurcación y la ejecutarán especulativamente en paralelo con la búsqueda de matriz. El hecho de que la búsqueda vtable ocurra en paralelo con la ejecución especulativa de la función significa que, cuando se ejecuta en un bucle en las situaciones que describe, las llamadas a funciones virtuales tienen una sobrecarga nula en comparación con las llamadas a funciones directas, no en línea.

De hecho, ya probé esto en el pasado, aunque en el lenguaje de programación D, no en C ++. Cuando inlining estaba deshabilitado en la configuración del compilador y llamé a la misma función en un bucle varias millones de veces, los tiempos estaban dentro de épsilon uno del otro si la función era virtual o no.

El segundo y más importante costo de las funciones virtuales es que impiden la creación de la función en la mayoría de los casos. Esto es incluso más importante de lo que parece, porque la optimización es una optimización que puede permitir muchas otras optimizaciones, como el plegado constante en algunos casos. No hay forma de alinear una función sin volver a compilar el código. Los JIT evitan esto porque constantemente están recompilando código durante la ejecución de su aplicación.

Answer 6

He visto situaciones donde evitar una llamada de función virtual es beneficioso. Esto no me parece que sea uno de esos casos porque realmente está usando la función de forma polimórfica. Simplemente está persiguiendo una dirección indirecta adicional, no un gran golpe, y una que podría estar parcialmente optimizada en algunas situaciones. Si realmente importa, puede reestructurar su código para que las opciones dependientes del tipo, como las llamadas a funciones virtuales, se realicen menos veces, fuera de los bucles.

Si realmente crees que vale la pena intentarlo, puedes establecer un puntero de función separado para una función no virtual específica de la clase. Podría (pero probablemente no lo haría) considerar hacerlo de esta manera.

class MyConcrete : public MyBase
{
public:
  static void foo_nonvirtual(MyBase* obj);
  virtual void foo()
  { foo_nonvirtual(this); }
};

void (*f_ptr)(MyBase* obj) = &MyConcrete::foo_nonvirtual;
// Call f_ptr instead of obj->foo() in your code.
// Still not as good a solution as restructuring the algorithm.

Además de hacer que el algoritmo sea un poco más inteligente, sospecho que cualquier intento de optimizar manualmente la llamada de función virtual causará más problemas de los que resuelve.

Answer 7

No puede usar un puntero de método porque los punteros a las funciones de miembro no se consideran tipos de retorno covariantes. Vea el ejemplo a continuación:

#include <iostream>

struct base;
struct der;

typedef void(base::*pt2base)();
typedef void(der::*pt2der)();

struct base {
    virtual pt2base method() = 0;
    virtual void testmethod() = 0;
    virtual ~base() {}
};

struct der : base {
    void testmethod() {
        std::cout << "Hello from der" << std::endl;
    }
    pt2der method() { **// this is invalid because pt2der isn''t a covariant of pt2base**
        return &der::testmethod;
    }
};

La otra opción sería tener el método declarado pt2base method() pero la devolución no sería válida porque der :: testmethod no es del tipo pt2base.

Además, incluso si tuviera un método que recibió una orden o referencia al tipo base, tendría que convertirlo dinámicamente al tipo derivado en ese método para hacer algo particularmente polimórfico, lo que aumenta el costo que estamos tratando de ahorrar.

Answer 8

¿Por qué la llamada virtual es costosa? Porque simplemente no conoce el destino de la sucursal hasta que el código se ejecuta en tiempo de ejecución. Incluso las CPU modernas aún manejan perfectamente la llamada virtual y las llamadas indirectas. No se puede simplemente decir que no cuesta nada porque solo tenemos una CPU más rápida. No, no es.

1. ¿Cómo podemos hacerlo rápido?

Ya tienes una comprensión bastante profunda del problema. Pero, lo único que puedo decir es que si la llamada a la función virtual es fácil de predecir, entonces podría realizar una optimización del nivel del software. Pero, si no lo es (es decir, realmente no tienes idea de cuál sería el objetivo de la función virtual), entonces no creo que haya una buena solución por el momento. Incluso para la CPU, es difícil predecir en un caso tan extremo.

En realidad, los compiladores como PGO (Optimización guiada de perfiles) de Visual C ++ tienen optimización de especulación de llamadas virtuales ( Link ). Si el resultado del perfilado puede enumerar los objetivos de la función virtual activa, se traducirá en llamada directa que puede estar en línea. Esto también se llama desvirtualización . También se puede encontrar en algún optimizador dinámico de Java.

2. Para aquellos que dicen que no es necesario

Si está utilizando lenguajes de script, C # y la preocupación acerca de la eficiencia de la codificación, sí, no tiene valor. Sin embargo, cualquier persona que esté ansiosa por salvar un solo ciclo para obtener un mejor rendimiento, la rama indirecta sigue siendo un problema importante. Incluso las últimas CPU no son buenas para manejar llamadas virtuales. Un buen ejemplo sería una máquina virtual o intérprete, que generalmente tiene una gran caja de interruptores. Su rendimiento está muy relacionado con la predicción correcta de la rama indirecta. Entonces, no puedes simplemente decir que es de muy bajo nivel o que no es necesario. Hay cientos de personas que intentan mejorar el rendimiento en el fondo. Es por eso que simplemente puede ignorar tales detalles :)

3. Algunos aburridos hechos arquitectónicos relacionados con las funciones virtuales

dsimcha ha escrito una buena respuesta sobre cómo la CPU puede manejar las llamadas virtuales de manera efectiva. Pero, no es exactamente correcto. En primer lugar, todas las CPU modernas tienen predictores de bifurcación, que literalmente predicen los resultados de una sucursal para aumentar el rendimiento de la canalización (o, más paralelismo en el nivel de instrucción o ILP . Incluso puedo decir que el rendimiento de la CPU de un solo subproceso depende únicamente de cuánto puede extraer ILP de un solo hilo. La predicción de bifurcación es el factor más crítico para obtener un ILP más alto).

En la predicción de bifurcación, hay dos predicciones: (1) dirección (es decir, la bifurcación se toma? O no se toma? Respuesta binaria), y (2) bifurcación objetivo (es decir, ¿dónde iré? No es una respuesta binaria). Con base en la predicción, la CPU ejecuta especulativamente el código. Si la especulación no es correcta, entonces la CPU se revierte y se reinicia desde la rama mal pronosticada. Esto está completamente oculto desde la vista del programador. Por lo tanto, no se sabe realmente qué está sucediendo dentro de la CPU a menos que se esté perfilando con VTune, lo que da una tasa de predicción errónea de las ramas.

En general, la predicción de dirección de rama es altamente precisa (95% +), pero aún es difícil predecir los destinos de ramificación, especialmente las llamadas virtuales y el conmutador (es decir, la tabla de salto). La llamada virtual es una rama indirecta que requiere una mayor carga de memoria, y también la CPU requiere la predicción del objetivo de bifurcación. CPUs modernas como Nehalem de Intel y Phenom de AMD tienen una tabla de objetivos de sucursales indirecta especializada.

Sin embargo, no creo que buscar Vtable suponga una gran sobrecarga. Sí, requiere una mayor carga de memoria que puede hacer que la memoria caché se pierda. Pero, una vez que vtable se carga en la memoria caché, se trata de un golpe de memoria caché. Si también le preocupa ese costo, puede poner el código de captación previa para cargar vtable de antemano. Pero, la verdadera dificultad de la llamada de función virtual es que la CPU no puede hacer un gran trabajo para predecir el destino de la llamada virtual, lo que puede dar lugar a la fuga de la tubería con frecuencia debido a la predicción errónea del objetivo.

Answer 9

Todas las respuestas se refieren al escenario más simple, donde llamar a un método virtual solo requiere obtener la dirección del método real para llamar. En el caso general, cuando entran en juego herencia múltiple y virtual, llamar a un método virtual requiere cambiar this puntero.

El mecanismo de envío de métodos se puede implementar de más de una manera, pero es común encontrar que la entrada en la tabla virtual no es el método real para llamar, sino más bien un código intermediario ''trampolín'' insertado por el compilador que reubica el this puntero antes de llamar al método real.

Cuando el envío es el más simple, solo una redirección adicional del puntero, entonces intentar optimizarlo no tiene sentido. Cuando el problema es más complejo, cualquier solución será dependiente del compilador y pirata informático. Además, ni siquiera sabe en qué situación se encuentra: si los objetos se cargan desde dlls, entonces no se sabe realmente si la instancia real devuelta pertenece a una jerarquía de herencia lineal simple o a un escenario más complejo.