Aplicaciones de AI en C++: ¿Qué tan costosas son las funciones virtuales? ¿Cuáles son las posibles optimizaciones?

Question

En una aplicación AI estoy escribiendo en C++,

1. no hay mucho cálculo numérico
2. hay gran cantidad de estructuras para las que se necesita el polimorfismo en tiempo de ejecución
3. muy a menudo, varias estructuras polimórficas interactúan durante el cálculo

En tal situación, ¿hay alguna técnica de optimización? Aunque no me importaría optimizar la aplicación en este momento, un aspecto de la selección de C++ sobre Java para el proyecto fue habilitar más apalancamiento para optimizar y poder utilizar métodos no orientados a objetos (plantillas, procedimientos, sobrecarga).

En particular, ¿cuáles son las técnicas de optimización relacionadas con las funciones virtuales? Las funciones virtuales se implementan a través de tablas virtuales en la memoria. ¿Hay alguna manera de prearchivar estas tablas virtuales en la memoria caché L2 (el costo de recuperación de la memoria/caché L2 está aumentando)?

Aparte de esto, ¿hay buenas referencias para las técnicas de localización de datos en C++? Estas técnicas reducirían el tiempo de espera para la obtención de datos en la memoria caché L2 necesaria para el cálculo.

Actualización: Ver también los siguientes foros relacionados: Performance Penalty for Interface, Several Levels of Base Classes

Answer 1

Las funciones virtuales son muy eficientes. Suponiendo 32 bits indicadores de la distribución de la memoria es de aproximadamente:

classptr -> [vtable:4][classdata:x] 
vtable -> [first:4][second:4][third:4][fourth:4][...] 
first -> [code:x] 
second -> [code:x] 
... 

Los puntos classptr a la memoria que es típicamente en el montón, de vez en cuando en la pila, y comienza con un puntero de cuatro bytes a la viable para esa clase. Pero lo importante de recordar es que el vtable en sí no tiene memoria asignada. Es un recurso estático y todos los objetos del mismo tipo de clase apuntarán exactamente a la misma ubicación de memoria para su matriz vtable. Llamar a diferentes instancias no atraerá diferentes ubicaciones de memoria a la memoria caché L2.

Este example from msdn muestra el vtable para la clase A con funciones virtuales func1, func2 y func3. Nada más que 12 bytes. Existe una buena posibilidad de que los vtables de las diferentes clases también estén físicamente adyacentes en la biblioteca compilada (querrá verificar si esto le preocupa especialmente) lo que podría aumentar microscópicamente la eficacia de la memoria caché.

CONST SEGMENT 
??_7A@@6B@ 
    DD FLAT:?func1@A@@UAEXXZ 
    DD FLAT:?func2@A@@UAEXXZ 
    DD FLAT:?func3@A@@UAEXXZ 
CONST ENDS 

El otro problema de rendimiento sería la sobrecarga de instrucciones de las llamadas a través de una función vtable. Esto también es muy eficiente. Casi idéntico a llamar a una función no virtual. Una vez más desde el example from msdn:

; A* pa; 
; pa->func3(); 
mov eax, DWORD PTR _pa$[ebp] 
mov edx, DWORD PTR [eax] 
mov ecx, DWORD PTR _pa$[ebp] 
call DWORD PTR [edx+8] 

En este ejemplo ebp, el puntero base de marco de pila, tiene la variable A* pa en cero offset. El registro eax se carga con el valor en la ubicación [ebp], por lo que tiene A *, y edx se carga con el valor en la ubicación [eax], por lo que tiene clase vtable. Entonces ecx se carga con [ebp], porque ecx representa "esto", ahora contiene A *, y finalmente la llamada se realiza al valor en la ubicación [edx + 8] que es la tercera dirección de función en el vtable.

Si esta llamada a la función no era virtual, no se necesitarían mov eva y mov edx, pero la diferencia en el rendimiento sería inconmensurablemente pequeña.

Answer 2

rara vez tienen que preocuparse de caché en lo que respecta a este tipo de artículos de uso común, ya que está exagerado una vez y se mantienen allí.

caché sólo es generalmente un problema cuando se trata de grandes estructuras de datos que, o bien:

1. son lo suficientemente grandes y se utiliza desde hace mucho tiempo por una sola función para que la función puede empujar todo lo que necesita de la memoria caché, o
2. Se accede de forma aleatoria lo suficiente como para que las propias estructuras de datos no estén necesariamente en la memoria caché cuando se carga desde ellas.

Cosas como los Vtables generalmente no van a ser un problema de rendimiento/caché/memoria; por lo general, solo hay un Vtable por tipo de objeto, y el objeto contiene un puntero al Vtable en lugar del propio Vtable. Así que a menos que tengas unos miles de tipos de objetos, no creo que los Vtables arruinen tu caché.

1), dicho sea de paso, funciones como memcpy usan instrucciones de transmisión de caché-bypass como movnt (dq | q) para entradas de datos extremadamente grandes (multi-megabytes).

Answer 3

Si una aplicación AI no requiere gran cantidad de crujidos numéricos, no me preocuparía la desventaja de rendimiento de las funciones virtuales. Habrá un golpe de rendimiento marginal, solo si aparecen en los cálculos complejos que se evalúan repetidamente. No creo que puedas obligar a la tabla virtual a permanecer en caché L2 tampoco.

Hay un par de optimizaciones disponibles para las funciones virtuales,

1. personas han escrito los compiladores que recurren a análisis de código y la transformación del programa. Pero estos no son compiladores de grado de producción.
2. Puede reemplazar todas las funciones virtuales con bloques equivalentes "cambiar ... casillas" para llamar a las funciones apropiadas según el tipo en la jerarquía. De esta forma, eliminará la tabla virtual administrada por el compilador y tendrá su propia tabla virtual en forma de interruptor ... bloque de casos. Ahora, las posibilidades de que su propia tabla virtual esté en la memoria caché L2 son altas en la ruta del código. Recuerde, necesitará RTTI o su propia función "typeof" para lograr esto.

Answer 4

¿Realmente ha perfilado y encontrado dónde y qué necesita optimización?

Trabaja en la optimización de llamadas a funciones virtuales cuando descubres que realmente son el cuello de botella.

Answer 5

Puede implementar el polimorfismo en tiempo de ejecución utilizando funciones virtuales y en tiempo de compilación mediante el uso de plantillas. Puede reemplazar funciones virtuales con plantillas. Eche un vistazo a este artículo para más información - http://www.codeproject.com/KB/cpp/SimulationofVirtualFunc.aspx

Answer 6

Una solución al polimorfismo dinámico podría ser un polimorfismo estático, utilizable si sus tipos son conocidos en tipo de compilación: El CRTP (patrón de plantilla curiosamente recurrente).

http://en.wikipedia.org/wiki/Curiously_recurring_template_pattern

La explicación de Wikipedia es bastante claro, y tal vez podría ayuda que si realmente determinado llamadas a métodos virtuales eran fuente de cuellos de botella de rendimiento.

Answer 7

Las llamadas virtuales no presentan una sobrecarga mucho mayor que las funciones normales. Sin embargo, la mayor pérdida es que una función virtual cuando se llama de forma polimórfica no puede estar en línea. Y la incorporación en muchas situaciones representará una ganancia real en el rendimiento.

Algo que puede hacer para evitar el desperdicio de esa instalación en algunas situaciones es declarar la función en línea virtual.

Class A { 
    inline virtual int foo() {...} 
}; 

Y cuando está en un punto de código que está seguro sobre el tipo de objeto que se llama, es posible realizar una llamada de línea que evitará el sistema polimórfico y permitir la expansión en línea por el compilador.

class B : public A { 
    inline virtual int foo() 
    { 
     //...do something different 
    } 

    void bar() 
    { 
     //logic... 
     B::foo(); 
     // more logic 
    } 
}; 

En este ejemplo, se realizará la llamada a foo() no polimórficos y unido a B aplicación de foo(). Pero hágalo solo cuando sepa con certeza cuál es el tipo de instancia, porque la característica de polimorfismo automático desaparecerá, y esto no es muy obvio para los lectores de códigos posteriores.

Answer 8

La única optimización que puedo pensar es el compilador JIT de Java. Si lo entiendo correctamente, supervisa las llamadas a medida que se ejecuta el código, y si la mayoría de las llamadas se dirigen solo a la implementación particular, inserta el salto condicional a la implementación cuando la clase es correcta. De esta manera, la mayoría de las veces, no hay una búsqueda vtable. Por supuesto, para el caso raro cuando pasamos una clase diferente, todavía se usa vtable.

No conozco ningún compilador/tiempo de ejecución C++ que utilice esta técnica.

Answer 9

La sección 5.3.3 del draft Technical Report on C++ Performance está completamente dedicada a la sobrecarga de las funciones virtuales.

Answer 10

El costo es más o menos el mismo que el de las funciones normales en la actualidad para CPUS recientes, pero no pueden incluirse. Si llama a la función millones de veces, el impacto puede ser significativo (intente llamar a millones de veces la misma función, por ejemplo, una vez con inline una vez sin, y verá que puede ser dos veces más lenta si la función en sí misma hace algo simple; no es un caso teórico: es bastante común para una gran cantidad de cálculos numéricos).

Answer 11

estoy reforzando todas las respuestas que dicen en efecto:

• Si en realidad no se sabe que es un problema, cualquier preocupación acerca de la fijación es probable que sea fuera de lugar.

Lo que se quiere saber es:

• ¿Qué fracción de tiempo de ejecución (cuando está actualmente en funcionamiento) se gasta en el proceso de invocación de métodos y, en particular, qué métodos son los más costosos (por esta medida).

Algunos perfiladores pueden darle esta información indirectamente. Deben resumir a nivel de declaración, pero excluyendo el tiempo dedicado al método en sí.

Mi técnica favorita es simplemente pausarla varias veces bajo un depurador.

Si el tiempo invertido en el proceso de invocaciones de funciones virtuales es significativo, como por ejemplo 20%, en promedio 1 de 5 muestras mostrará, en la parte inferior de la pila de llamadas, en la ventana de desmontaje, las instrucciones para seguir el puntero de la función virtual.

Si realmente no ve eso, no es un problema.

En el proceso, probablemente verá otras cosas más arriba en la pila de llamadas, que en realidad no son necesarias y podrían ahorrarle mucho tiempo.

Answer 12

Las funciones virtuales tienden a ser una llamada de función de búsqueda e indirección. En algunas plataformas, esto es rápido. En otros, por ejemplo, una popular arquitectura de PPC utilizada en consolas, esto no es tan rápido.

Las optimizaciones generalmente giran en torno a expresar la variabilidad más arriba en la pila de llamadas para que no necesite invocar una función virtual varias veces dentro de zonas activas.

Answer 13

Como ya se indicó en las otras respuestas, la sobrecarga real de una llamada de función virtual es bastante pequeña. Puede marcar la diferencia en un círculo cerrado donde se llama millones de veces por segundo, pero rara vez es un gran problema.

Sin embargo, aún puede tener un mayor impacto ya que es más difícil para el compilador optimizar. No puede alinear la llamada de función, porque no sabe en tiempo de compilación a qué función se llamará. Eso también hace que algunas optimizaciones globales sean más difíciles. ¿Y cuánto rendimiento le cuesta esto? Depende. Por lo general, no hay nada de qué preocuparse, pero hay casos en los que puede significar un golpe de rendimiento significativo.

Y, por supuesto, también depende de la arquitectura de la CPU. En algunos, puede llegar a ser bastante costoso.

Pero vale la pena tener en cuenta que cualquier tipo de polimorfismo en tiempo de ejecución lleva más o menos la misma sobrecarga. Implementar la misma funcionalidad a través de sentencias de cambio o similares, para seleccionar entre varias funciones posibles, puede no ser más barato.

La única manera confiable de optimizar esto sería si pudiera mover parte del trabajo al tiempo de compilación. Si es posible implementar parte de él como polimorfismo estático, es posible que se acelere un poco.

Pero primero, asegúrese de tener un problema. ¿Es realmente el código demasiado lento para ser aceptable? En segundo lugar, descubra qué lo hace lento a través de un generador de perfiles. Y tercero, arreglarlo.

Answer 14

Con CPU modernas, con visión de futuro y múltiples despachos, la sobrecarga para una función virtual bien podría ser cero. Nada. Cremallera.

Answer 15

Polimorfismo estático, como algunos usuarios han respondido aquí. Por ejemplo, WTL usa este método. Se puede encontrar una explicación clara de la implementación de WTL en http://www.codeproject.com/KB/wtl/wtl4mfc1.aspx#atltemplates