virtuales que puro puras polimorfismo objeto modificador herencia funciones funcion c++ optimization

que - Aplicaciones de AI en C++: ¿Cuán costosas son las funciones virtuales? ¿Cuáles son las posibles optimizaciones?



polimorfismo puro c++ (15)

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

Trabaje en la optimización de llamadas a funciones virtuales cuando haya descubierto que realmente son el cuello de botella.

En una aplicación de IA, estoy escribiendo en C ++,

  1. no hay mucha computación numérica
  2. hay muchas estructuras para las cuales se necesita 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 : vea también los siguientes foros relacionados: penalización de rendimiento para la interfaz , varios niveles de clases base

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 de C ++ que use esta técnica.

Las funciones virtuales son muy eficientes. Suponiendo punteros de 32 bits, el diseño de la memoria es aproximadamente:

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

El classptr apunta a la memoria que normalmente está en el montón, ocasionalmente en la pila, y comienza con un puntero de cuatro bytes al vtable 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 ejemplo de 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. De nuevo desde el ejemplo de 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 del marco de pila, tiene la variable A* pa en el desplazamiento cero. 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 función no fuera virtual, no se necesitarían mov eax y mov edx, pero la diferencia de rendimiento sería inconmensurablemente pequeña.

Puede implementar el polimorfismo en tiempo de ejecución mediante el uso de 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 obtener más información: http://www.codeproject.com/KB/cpp/SimulationofVirtualFunc.aspx

Rara vez tiene que preocuparse por el caché en lo que respecta a los artículos de uso común, ya que se recogen una vez y se guardan allí.

Por lo general, la caché es un problema cuando se trata de estructuras de datos de gran tamaño que:

  1. Son lo suficientemente grandes y se utilizan durante mucho tiempo con una sola función, de modo que la función puede sacar todo lo que necesita de la 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 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, es la razón por la cual funciones como memcpy usan cache-bypass de instrucciones de transmisión como movnt (dq | q) para entradas de datos extremadamente grandes (multi-megabyte).

Si una aplicación de IA no requiere una 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 funciones virtuales,

  1. La gente ha escrito compiladores que recurren al análisis del 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 de "cambiar ... mayúsculas y minúsculas" 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.

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

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

La explicación en Wikipedia es lo suficientemente clara, y tal vez podría ayudarlo si realmente determinara que las llamadas a métodos virtuales fueron fuente de cuellos de botella en el rendimiento.

Actualmente, el costo es más o menos el mismo que el de las funciones normales 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).

Como ya se dijo 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 económico.

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úrate 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.

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

Estoy reforzando todas las respuestas que dicen en efecto:

  • Si en realidad no sabe que es un problema, es probable que cualquier preocupación sobre solucionarlo esté fuera de lugar.

Lo que quieres saber es:

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

Algunos perfiladores pueden darte 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 hacer una pausa varias veces debajo de un depurador.

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

Si no lo ves realmente, 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.

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 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.

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 se encuentre en un punto de código, está SEGURO sobre el tipo de objeto que se llama, puede realizar una llamada en línea que evitará el sistema polimórfico y permitirá que el compilador realice la alineación.

class B : public A { inline virtual int foo() { //...do something different } void bar() { //logic... B::foo(); // more logic } };

En este ejemplo, la llamada a foo() se hará no polimórfica y se vinculará a la implementación B 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.