¿Cuál es el costo de rendimiento de tener un método virtual en una clase C ++?

107

Tener al menos un método virtual en una clase C ++ (o cualquiera de sus clases principales) significa que la clase tendrá una tabla virtual y cada instancia tendrá un puntero virtual.

Entonces, el costo de la memoria es bastante claro. El más importante es el costo de la memoria en las instancias (especialmente si las instancias son pequeñas, por ejemplo, si solo están destinadas a contener un número entero: en este caso, tener un puntero virtual en cada instancia podría duplicar el tamaño de las instancias. el espacio de memoria utilizado por las tablas virtuales, supongo que suele ser insignificante en comparación con el espacio utilizado por el código de método real.

Esto me lleva a mi pregunta: ¿hay un costo de rendimiento medible (es decir, impacto en la velocidad) para hacer que un método sea virtual? Habrá una búsqueda en la tabla virtual en tiempo de ejecución, en cada llamada de método, por lo que si hay llamadas muy frecuentes a este método, y si este método es muy corto, ¿entonces podría haber un impacto de rendimiento medible? Supongo que depende de la plataforma, pero ¿alguien ha ejecutado algunos puntos de referencia?

La razón por la que pregunto es que encontré un error que se debió a que un programador se olvidó de definir un método virtual. Esta no es la primera vez que veo este tipo de error. Y pensé: ¿por qué añadir la palabra clave virtual cuando sea necesario en lugar de la eliminación de la palabra clave virtual cuando estamos absolutamente seguros de que está no necesita? Si el costo de rendimiento es bajo, creo que simplemente recomendaré lo siguiente en mi equipo: simplemente haga que todos los métodos sean virtuales de forma predeterminada, incluido el destructor, en cada clase, y solo elimínelos cuando sea necesario. ¿Eso te suena loco?

MiniQuark
fuente
7
Comparar las llamadas virtuales con las no virtuales no es amenazante. Proporcionan una funcionalidad diferente. Si desea comparar las llamadas a funciones virtuales con el equivalente de C, debe agregar el costo del código que implementa la característica equivalente de la función virtual.
Martin York
Que es una declaración de cambio o una gran declaración if. Si fuera inteligente, podría volver a implementar utilizando una tabla de punteros de función, pero las probabilidades de equivocarse son mucho mayores.
Martin York
7
La pregunta es sobre llamadas a funciones que no necesitan ser virtuales, por lo que la comparación es significativa.
Mark Ransom

Respuestas:

104

Me encontré con algunos tiempos en un procesador PowerPC 3GHz en orden. En esa arquitectura, una llamada de función virtual cuesta 7 nanosegundos más que una llamada de función directa (no virtual).

Por lo tanto, no vale la pena preocuparse por el costo a menos que la función sea algo así como un acceso trivial Get () / Set (), en el que cualquier cosa que no sea inline es un desperdicio. Una sobrecarga de 7ns en una función que se inserta en 0.5ns es severa; una sobrecarga de 7ns en una función que tarda 500ms en ejecutarse no tiene sentido.

El gran costo de las funciones virtuales no es realmente la búsqueda de un puntero de función en la vtable (que suele ser un solo ciclo), sino que el salto indirecto generalmente no se puede predecir en una rama. Esto puede provocar una gran burbuja de canalización, ya que el procesador no puede obtener ninguna instrucción hasta que el salto indirecto (la llamada a través del puntero de función) se haya retirado y se haya calculado un nuevo puntero de instrucción. Entonces, el costo de una llamada de función virtual es mucho mayor de lo que podría parecer al mirar el ensamblaje ... pero aún así solo 7 nanosegundos.

Editar: Andrew, Not Sure y otros también plantean el muy buen punto de que una llamada a una función virtual puede causar una falla en la caché de instrucciones: si salta a una dirección de código que no está en la caché, todo el programa se detiene mientras el las instrucciones se obtienen de la memoria principal. Este es siempre un bloqueo significativo: en Xenon, alrededor de 650 ciclos (según mis pruebas).

Sin embargo, este no es un problema específico de las funciones virtuales porque incluso una llamada directa a la función provocará un error si salta a instrucciones que no están en la caché. Lo que importa es si la función se ha ejecutado antes recientemente (lo que hace que sea más probable que esté en la caché) y si su arquitectura puede predecir ramas estáticas (no virtuales) y obtener esas instrucciones en la caché antes de tiempo. Mi PPC no lo hace, pero quizás el hardware más reciente de Intel sí.

Mis tiempos controlan la influencia de las fallas de icache en la ejecución (deliberadamente, ya que estaba tratando de examinar la tubería de la CPU de forma aislada), por lo que descuentan ese costo.

Crashworks
fuente
3
El costo en ciclos es aproximadamente igual al número de etapas de la canalización entre la recuperación y el final de la derivación-retiro. No es un costo insignificante y puede sumarse, pero a menos que esté tratando de escribir un bucle ajustado de alto rendimiento, probablemente haya peces de mayor rendimiento para freír.
Crashworks
7 nano segundos más de lo que. Si una llamada normal es de 1 nano segundo que es digno, si una llamada normal es de 70 nano segundos, entonces no lo es.
Martin York
Si observa los tiempos, descubrí que para una función que costó 0.66ns en línea, la sobrecarga diferencial de una llamada de función directa fue 4.8ns y una función virtual 12.3ns (en comparación con la en línea). Tienes el buen punto de que si la función en sí cuesta un milisegundo, entonces 7 ns no significa nada.
Crashworks
2
Más como 600 ciclos, pero es un buen punto. Lo dejé fuera de los tiempos porque estaba interesado solo en la sobrecarga debido a la burbuja de la tubería y el prólogo / epílogo. El error de icache ocurre con la misma facilidad para una llamada de función directa (Xenon no tiene un predictor de rama de icache).
Crashworks
2
Un detalle menor, pero con respecto a "Sin embargo, este no es un problema específico de ...", es un poco peor para el envío virtual, ya que hay una página adicional (o dos si pasa por el límite de una página) que tiene que estar en la caché - para la mesa de despacho virtual de la clase.
Tony Delroy
19

Definitivamente hay una sobrecarga mensurable cuando se llama a una función virtual: la llamada debe usar vtable para resolver la dirección de la función para ese tipo de objeto. Las instrucciones adicionales son la menor de tus preocupaciones. Las vtables no solo evitan muchas optimizaciones potenciales del compilador (ya que el tipo es polimórfico del compilador), sino que también pueden destruir su I-Cache.

Por supuesto, si estas penalizaciones son significativas o no depende de su aplicación, con qué frecuencia se ejecutan esas rutas de código y sus patrones de herencia.

Sin embargo, en mi opinión, tener todo como virtual de forma predeterminada es una solución general para un problema que podría resolver de otras maneras.

Quizás podría ver cómo se diseñan / documentan / escriben las clases. Generalmente, el encabezado de una clase debe dejar bastante claro qué funciones pueden ser reemplazadas por clases derivadas y cómo se llaman. Hacer que los programadores escriban esta documentación es útil para garantizar que estén correctamente marcados como virtuales.

También diría que declarar cada función como virtual podría provocar más errores que simplemente olvidar marcar algo como virtual. Si todas las funciones son virtuales, todo puede ser reemplazado por clases base (públicas, protegidas, privadas), todo se vuelve un juego limpio. Por accidente o por intención, las subclases podrían cambiar el comportamiento de las funciones que luego causan problemas cuando se usan en la implementación base.

Andrew Grant
fuente
La mayor optimización perdida es la inserción, especialmente si la función virtual suele ser pequeña o vacía.
Zan Lynx
@Andrew: punto de vista interesante. Sin embargo, no estoy de acuerdo con su último párrafo: si una clase base tiene una función saveque depende de una implementación específica de una función writeen la clase base, entonces me parece que saveestá mal codificada o writedebería ser privada.
MiniQuark
2
El hecho de que la escritura sea privada no impide que se anule. Este es otro argumento para no hacer las cosas virtuales de forma predeterminada. En cualquier caso, estaba pensando en lo contrario: una implementación genérica y bien escrita se reemplaza por algo que tiene un comportamiento específico y no compatible.
Andrew Grant
Votado en el almacenamiento en caché: en cualquier base de código orientado a objetos grande, si no está siguiendo las prácticas de rendimiento de la localidad del código, es muy fácil que sus llamadas virtuales causen fallas de caché y causen un bloqueo.
No estoy seguro
Y una pérdida de icache puede ser realmente grave: 600 ciclos en mis pruebas.
Crashworks
9

Depende. :) (¿Esperabas algo más?)

Una vez que una clase obtiene una función virtual, ya no puede ser un tipo de datos POD (puede que tampoco lo haya sido antes, en cuyo caso esto no marcará la diferencia) y eso hace que toda una gama de optimizaciones sea imposible.

std :: copy () en tipos simples de POD puede recurrir a una rutina simple de memcpy, pero los tipos que no son POD deben manejarse con más cuidado.

La construcción se vuelve mucho más lenta porque la vtable debe inicializarse. En el peor de los casos, la diferencia de rendimiento entre los tipos de datos POD y no POD puede ser significativa.

En el peor de los casos, es posible que vea una ejecución 5 veces más lenta (ese número se toma de un proyecto universitario que hice recientemente para volver a implementar algunas clases de biblioteca estándar. Nuestro contenedor tardó aproximadamente 5 veces más en construirse tan pronto como el tipo de datos que almacenó obtuvo un vtable)

Por supuesto, en la mayoría de los casos, es poco probable que vea una diferencia de desempeño medible, esto es simplemente para señalar que en algunos casos fronterizos, puede ser costoso.

Sin embargo, el rendimiento no debería ser su principal consideración aquí. Hacer que todo sea virtual no es una solución perfecta por otras razones.

Permitir que todo se anule en las clases derivadas hace que sea mucho más difícil mantener invariantes de clase. ¿Cómo garantiza una clase que permanece en un estado consistente cuando cualquiera de sus métodos podría redefinirse en cualquier momento?

Hacer que todo sea virtual puede eliminar algunos errores potenciales, pero también introduce otros nuevos.

jalf
fuente
7

Si necesita la funcionalidad de envío virtual, debe pagar el precio. La ventaja de C ++ es que puede utilizar una implementación muy eficiente de distribución virtual proporcionada por el compilador, en lugar de una versión posiblemente ineficiente que implemente usted mismo.

Sin embargo, si no lo necesita, si no lo necesita, posiblemente vaya demasiado lejos. Y la mayoría de las clases no están diseñadas para ser heredadas: crear una buena clase base requiere más que hacer que sus funciones sean virtuales.


fuente
Buena respuesta, pero, en mi opinión, no lo suficientemente enfático en la segunda mitad: abrumarse con los gastos generales si no lo necesita es, francamente, una locura, especialmente cuando se usa este lenguaje cuyo mantra es "no pagues por lo que no no uso ". Hacer todo virtual por defecto hasta que alguien justifique por qué puede / debería ser no virtual es una política abominable.
underscore_d
5

El envío virtual es un orden de magnitud más lento que algunas alternativas, no tanto por la indirección como por la prevención de la inserción. A continuación, lo ilustraré contrastando el envío virtual con una implementación que incrusta un "número de tipo (-identificación)" en los objetos y usando una declaración de cambio para seleccionar el código específico del tipo. Esto evita la sobrecarga de llamadas a funciones por completo, simplemente haciendo un salto local. Existe un costo potencial de mantenimiento, dependencias de recompilación, etc. a través de la localización forzada (en el conmutador) de la funcionalidad específica del tipo.


IMPLEMENTACIÓN

#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';
  }
}

RESULTADOS DE RENDIMIENTO

En mi sistema 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

Esto sugiere que un enfoque de cambio de número de tipo en línea es aproximadamente (1,28 - 0,23) / (0,344 - 0,23) = 9,2 veces más rápido. Por supuesto, eso es específico para el sistema exacto probado / indicadores del compilador y versión, etc., pero generalmente es indicativo.


COMENTARIOS RE VIRTUAL DISPATCH

Sin embargo, debe decirse que los gastos generales de llamadas a funciones virtuales son algo que rara vez es significativo, y solo para funciones triviales a menudo llamadas (como getters y setters). Incluso entonces, es posible que pueda proporcionar una única función para obtener y configurar una gran cantidad de cosas a la vez, minimizando el costo. La gente se preocupa demasiado por el envío virtual, por lo que debe realizar el perfil antes de encontrar alternativas incómodas. El principal problema con ellos es que realizan una llamada de función fuera de línea, aunque también deslocalizan el código ejecutado, lo que cambia los patrones de utilización de la caché (para mejor o (más a menudo) para peor).

Tony Delroy
fuente
Hice una pregunta con respecto a su código porque tengo algunos resultados "extraños" usando g++/ clangy -lrt. Pensé que valía la pena mencionarlo aquí para futuros lectores.
Holt
@Holt: ¡buena pregunta dados los desconcertantes resultados! Lo echaré un vistazo más de cerca en los pocos días si tengo la mínima oportunidad. Salud.
Tony Delroy
3

El costo adicional es prácticamente nada en la mayoría de los escenarios. (perdón por el juego de palabras). ejac ya ha publicado medidas relativas sensatas.

Lo más importante a lo que renuncias son las posibles optimizaciones debido a la inserción. Pueden ser especialmente buenos si la función se llama con parámetros constantes. Esto rara vez hace una diferencia real, pero en algunos casos, esto puede ser enorme.


Con respecto a las optimizaciones:
es importante conocer y considerar el costo relativo de las construcciones de su lenguaje. La notación Big O es solo la mitad de la historia: ¿cómo escala su aplicación ? La otra mitad es el factor constante frente a él.

Como regla general, no saldría de mi camino para evitar las funciones virtuales, a menos que haya indicaciones claras y específicas de que se trata de un cuello de botella. Un diseño limpio siempre es lo primero, pero es solo una parte interesada que no debe dañar indebidamente a los demás.


Ejemplo elaborado: un destructor virtual vacío en una matriz de un millón de elementos pequeños puede atravesar al menos 4 MB de datos, destrozando su caché. Si ese destructor se puede eliminar, los datos no se modificarán.

Al escribir código de biblioteca, estas consideraciones están lejos de ser prematuras. Nunca se sabe cuántos bucles se colocarán alrededor de su función.

Peterchen
fuente
2

Si bien todos los demás tienen razón sobre el rendimiento de los métodos virtuales y demás, creo que el problema real es si el equipo conoce la definición de la palabra clave virtual en C ++.

Considere este código, ¿cuál es el resultado?

#include <stdio.h>

class A
{
public:
    void Foo()
    {
        printf("A::Foo()\n");
    }
};

class B : public A
{
public:
    void Foo()
    {
        printf("B::Foo()\n");
    }
};

int main(int argc, char** argv)
{    
    A* a = new A();
    a->Foo();

    B* b = new B();
    b->Foo();

    A* a2 = new B();
    a2->Foo();

    return 0;
}

Nada sorprendente aquí:

A::Foo()
B::Foo()
A::Foo()

Como nada es virtual. Si la palabra clave virtual se agrega al frente de Foo en las clases A y B, obtenemos esto para la salida:

A::Foo()
B::Foo()
B::Foo()

Básicamente lo que todos esperan.

Ahora, mencionaste que hay errores porque alguien olvidó agregar una palabra clave virtual. Así que considere este código (donde la palabra clave virtual se agrega a la clase A, pero no a la clase B). Entonces, ¿cuál es la salida?

#include <stdio.h>

class A
{
public:
    virtual void Foo()
    {
        printf("A::Foo()\n");
    }
};

class B : public A
{
public:
    void Foo()
    {
        printf("B::Foo()\n");
    }
};

int main(int argc, char** argv)
{    
    A* a = new A();
    a->Foo();

    B* b = new B();
    b->Foo();

    A* a2 = new B();
    a2->Foo();

    return 0;
}

Respuesta: ¿Lo mismo que si se agrega la palabra clave virtual a B? La razón es que la firma de B :: Foo coincide exactamente con A :: Foo () y debido a que A's Foo es virtual, también lo es B's.

Ahora considere el caso en el que Foo de B es virtual y el de A no. Entonces, ¿cuál es la salida? En este caso, la salida es

A::Foo()
B::Foo()
A::Foo()

La palabra clave virtual funciona hacia abajo en la jerarquía, no hacia arriba. Nunca hace que los métodos de la clase base sean virtuales. La primera vez que se encuentra un método virtual en la jerarquía es cuando comienza el polimorfismo. No hay forma de que las clases posteriores hagan que las clases anteriores tengan métodos virtuales.

No olvide que los métodos virtuales significan que esta clase le está dando a las clases futuras la capacidad de anular / cambiar algunos de sus comportamientos.

Entonces, si tiene una regla para eliminar la palabra clave virtual, es posible que no tenga el efecto deseado.

La palabra clave virtual en C ++ es un concepto poderoso. Debe asegurarse de que cada miembro del equipo realmente conozca este concepto para que pueda usarse como se diseñó.

Tommy Hui
fuente
Hola Tommy, gracias por el tutorial. El error que tuvimos se debió a la falta de una palabra clave "virtual" en un método de la clase base. Por cierto, estoy diciendo que todas las funciones sean virtuales (no al revés), luego, cuando claramente no sea necesario, elimine la palabra clave "virtual".
MiniQuark
@MiniQuark: Tommy Hui dice que si haces que todas las funciones sean virtuales, un programador puede terminar eliminando la palabra clave en una clase derivada, sin darse cuenta de que no tiene ningún efecto. Necesitaría alguna forma de asegurarse de que la eliminación de la palabra clave virtual siempre ocurra en la clase base.
M. Dudley
1

Dependiendo de su plataforma, la sobrecarga de una llamada virtual puede ser muy indeseable. Al declarar que cada función es virtual, esencialmente las llama a todas a través de un puntero de función. Como mínimo, esto es una desreferencia adicional, pero en algunas plataformas PPC utilizará instrucciones microcodificadas o lentas para lograrlo.

No recomiendo su sugerencia por esta razón, pero si le ayuda a prevenir errores, entonces puede valer la pena el intercambio. Sin embargo, no puedo evitar pensar que debe haber un término medio que vale la pena encontrar.

Dan Olson
fuente
-1

Requerirá solo un par de instrucciones asm adicionales para llamar al método virtual.

Pero no creo que te preocupes de que fun (int a, int b) tenga un par de instrucciones extra 'push' en comparación con fun (). Así que no se preocupe también por los virtuales, hasta que se encuentre en una situación especial y vea que realmente genera problemas.

PD: si tienes un método virtual, asegúrate de tener un destructor virtual. De esta forma evitarás posibles problemas


En respuesta a los comentarios 'xtofl' y 'Tom'. Hice pequeñas pruebas con 3 funciones:

  1. Virtual
  2. Normal
  3. Normal con 3 parámetros int

Mi prueba fue una iteración simple:

for(int it = 0; it < 100000000; it ++) {
    test.Method();
}

Y aquí los resultados:

  1. 3.913 segundos
  2. 3.873 segundos
  3. 3.970 segundos

Fue compilado por VC ++ en modo de depuración. Hice solo 5 pruebas por método y calculé el valor medio (por lo que los resultados pueden ser bastante inexactos) ... De todos modos, los valores son casi iguales asumiendo 100 millones de llamadas. Y el método con 3 push / pop adicionales fue más lento.

El punto principal es que si no le gusta la analogía con push / pop, ¿piensa en un if / else adicional en su código? ¿Piensa en la canalización de la CPU cuando agrega if / else ;-) Además, nunca se sabe en qué CPU se ejecutará el código ... El compilador habitual puede generar código más óptimo para una CPU y menos óptimo para otra ( Intel Compilador C ++ )

alex2k8
fuente
2
el asm adicional podría desencadenar una falla de página (que no estaría allí para funciones no virtuales); creo que simplifica enormemente el problema.
xtofl
2
+1 al comentario de xtofl. Las funciones virtuales introducen la indirección, que introduce "burbujas" de canalización y afectan el comportamiento del almacenamiento en caché.
Tom
1
Sincronizar cualquier cosa en el modo de depuración no tiene sentido. MSVC hace código muy lento en modo de depuración y la sobrecarga de bucle probablemente oculta la mayor parte de la diferencia. Si su objetivo es un alto rendimiento, sí, debería pensar en minimizar las ramas if / else en la ruta rápida. Consulte agner.org/optimize para obtener más información sobre la optimización del rendimiento x86 de bajo nivel. (También algunos otros enlaces en la wiki de etiquetas x86
Peter Cordes
1
@Tom: el punto clave aquí es que las funciones no virtuales pueden estar en línea, pero las virtuales no pueden (a menos que el compilador pueda desvirtualizar, por ejemplo, si usó finalen su anulación y tiene un puntero al tipo derivado, en lugar del tipo base ). Esta prueba llamó a la misma función virtual cada vez, por lo que predijo perfectamente; no hay burbujas en la tubería, excepto por un callrendimiento limitado . Y ese indirecto callpuede ser un par más. La predicción de rama funciona bien incluso para ramas indirectas, especialmente si siempre tienen el mismo destino.
Peter Cordes
Esto cae en la trampa común de los microbenchmarks: se ve rápido cuando los predictores de rama están activos y no sucede nada más. La sobrecarga de predicción errónea es mayor para una indirecta callque para una directa.call . (Y sí, las callinstrucciones normales también necesitan predicción. La etapa de recuperación debe conocer la siguiente dirección a buscar antes de que se decodifique este bloque, por lo que debe predecir el siguiente bloque de recuperación en función de la dirección del bloque actual, en lugar de la dirección de instrucción. como predecir en qué parte de este bloque hay una instrucción de rama ...)
Peter Cordes