Impacto de rendimiento de búsqueda vtable en C++

real-time virtual-method (6)

Estoy evaluando para volver a escribir una pieza de software en tiempo real desde C / lenguaje ensamblador a C ++ / lenguaje ensamblador (por razones que no son relevantes para las partes de la pregunta del código son absolutamente necesarias).

Una interrupción viene con una frecuencia de 3 kHz, y para cada interrupción, se deben hacer aproximadamente 200 cosas diferentes en una secuencia. El procesador funciona con 300 MHz, lo que nos da 100,000 ciclos para hacer el trabajo. Esto se ha resuelto en C con una serie de punteros de función:

// Each function does a different thing, all take one parameter being a pointer // to a struct, each struct also being different. void (*todolist[200])(void *parameters); // Array of pointers to structs containing each function''s parameters. void *paramlist[200]; void realtime(void) { int i; for (i = 0; i < 200; i++) (*todolist[i])(paramlist[i]); }

La velocidad es importante. Las 200 iteraciones anteriores se realizan 3,000 veces por segundo, por lo que prácticamente hacemos 600,000 iteraciones por segundo. Lo anterior para bucles compila a cinco ciclos por iteración, lo que arroja un costo total de 3,000,000 ciclos por segundo, es decir, un 1% de carga de CPU. La optimización del ensamblador podría reducirlo a cuatro instrucciones, sin embargo, me temo que podríamos obtener algún retraso adicional debido a los accesos de memoria cercanos entre sí, etc. En resumen, creo que esos cinco ciclos son bastante óptimos.

Ahora a la reescritura de C ++. Esas 200 cosas que hacemos están relacionadas entre sí. Hay un subconjunto de parámetros que todos necesitan y usan, y tienen en sus respectivas estructuras. En una implementación de C ++, por lo tanto, podrían considerarse claramente como heredados de una clase base común:

class Base { virtual void Execute(); int something_all_things_need; } class Derived1 : Base { void Execute() { /* Do something */ } int own_parameter; // Other own parameters } class Derived2 : Base { /* Etc. */ } Base *todolist[200]; void realtime(void) { for (int i = 0; i < 200; i++) todolist[i]->Execute(); // vtable look-up! 20+ cycles. }

Mi problema es la búsqueda vtable. No puedo hacer 600,000 búsquedas por segundo; esto representaría más del 4% de la carga de CPU desperdiciada. Además, el todolist nunca cambia durante el tiempo de ejecución, solo se configura una vez en el inicio, por lo que el esfuerzo de buscar qué función llamar es realmente desperdiciado. Al hacerme la pregunta "¿cuál es el resultado final más óptimo posible?", Miro el código del ensamblador dado por la solución C y vuelvo a encontrar una serie de punteros de función ...

¿Cuál es la forma limpia y correcta de hacer esto en C ++? Crear una buena clase base, clases derivadas y así sucesivamente se siente bastante inútil cuando, al final, uno nuevamente selecciona los punteros de función por razones de rendimiento.

Actualización (incluida la corrección de donde comienza el bucle):

El procesador es un ADSP-214xx y el compilador es VisualDSP ++ 5.0. Al habilitar #pragma optimize_for_speed , el bucle C es de 9 ciclos. La optimización de ensamblaje en mi mente produce 4 ciclos, sin embargo no lo probé, por lo que no está garantizado. El bucle de C ++ es de 14 ciclos. Soy consciente de que el compilador podría hacer un mejor trabajo, sin embargo, no quería descartar esto como un problema del compilador: seguir adelante sin polimorfismo sigue siendo preferible en un contexto integrado, y la opción de diseño aún me interesa. Para referencia, aquí el ensamblaje resultante:

DO:

i3=0xb27ba; i5=0xb28e6; r15=0xc8;

Aquí está el bucle real:

r4=dm(i5,m6); i12=dm(i3,m6); r2=i6; i6=i7; jump (m13,i12) (db); dm(i7,m7)=r2; dm(i7,m7)=0x1279de; r15=r15-1; if ne jump (pc, 0xfffffff2);

C ++:

i5=0xb279a; r15=0xc8;

Aquí está el bucle real:

i5=modify(i5,m6); i4=dm(m7,i5); r2=i4; i4=dm(m6,i4); r1=dm(0x3,i4); r4=r2+r1; i12=dm(0x5,i4); r2=i6; i6=i7; jump (m13,i12) (db); dm(i7,m7)=r2; dm(i7,m7)=0x1279e2; r15=r15-1; if ne jump (pc, 0xffffffe7);

Mientras tanto, creo que he encontrado una especie de respuesta. La menor cantidad de ciclos se logra haciendo lo menos posible. Tengo que obtener un puntero de datos, buscar un puntero de función y llamar a la función con el puntero de datos como parámetro. Cuando se obtiene un puntero, el registro de índice se modifica automáticamente por una constante, y uno puede igualmente permitir que esta constante sea igual a 1. Entonces, una vez más, uno se encuentra con una matriz de punteros de función y una matriz de punteros de datos.

Naturalmente, el límite es lo que se puede hacer en ensamblaje, y ahora se ha explorado. Teniendo esto en cuenta, ahora entiendo que, aunque para uno es natural introducir una clase base, no fue realmente lo que encajaba. Así que supongo que la respuesta es que si uno quiere una serie de punteros de función, debe hacerse uno mismo una matriz de punteros de función ...

¿Qué te hace pensar que una sobrecarga de búsqueda es de 20 ciclos? Si eso es realmente cierto, necesitas un mejor compilador de C ++.

Intenté esto en una caja de Intel, sin saber nada sobre el procesador que está usando, y como era de esperar, la diferencia entre el código de envío C y el envío de C ++ vtable es una instrucción, que tiene que ver con el hecho de que el vtable implica un extra indirecto.

Código C (basado en OP):

void (*todolist[200])(void *parameters); void *paramlist[200]; void realtime(void) { int i; for (i = 0; i < 200; i++) (*todolist[i])(paramlist[i]); }

Código C ++:

class Base { public: Base(void* unsafe_pointer) : unsafe_pointer_(unsafe_pointer) {} virtual void operator()() = 0; protected: void* unsafe_pointer_; }; Base* todolist[200]; void realtime() { for (int i = 0; i < 200; ++i) (*todolist[i])(); }

Ambos compilados con gcc 4.8, -O3:

En el código C ++, el primer movq obtiene la dirección de vtable, y la call se indexa a través de eso. Así que esa es una instrucción de sobrecarga.

Según OP, el compilador C ++ de DSP produce el siguiente código. He insertado comentarios basados en mi comprensión de lo que está pasando (lo que podría estar mal). Tenga en cuenta que (IMO) el bucle comienza una ubicación antes de lo que indica OP; De lo contrario, no tiene sentido (para mí).

# Initialization. # i3=todolist; i5=paramlist | # i5=todolist holds paramlist i3=0xb27ba; | # No paramlist in C++ i5=0xb28e6; | i5=0xb279a; # r15=count r15=0xc8; | r15=0xc8; # Loop. We need to set up r4 (first parameter) and figure out the branch address. # In C++ by convention, the first parameter is ''this'' # Note 1: r4=dm(i5,m6); # r4 = *paramlist++; | i5=modify(i5,m6); # i4 = *todolist++ | i4=dm(m7,i5); # .. # Note 2: | r2=i4; # r2 = obj | i4=dm(m6,i4); # vtable = *(obj + 1) | r1=dm(0x3,i4); # r1 = vtable[3] | r4=r2+r1; # param = obj + r1 i12=dm(i3,m6); # i12 = *todolist++; | i12=dm(0x5,i4); # i12 = vtable[5] # Boilerplate call. Set frame pointer, push return address and old frame pointer. # The two (push) instructions after jump are actually executed before the jump. r2=i6; | r2=i6; i6=i7; | i6=i7; jump (m13,i12) (db); | jump (m13,i12) (db); dm(i7,m7)=r2; | dm(i7,m7)=r2; dm(i7,m7)=0x1279de; | dm(i7,m7)=0x1279e2; # if (count--) loop r15=r15-1; | r15=r15-1; if ne jump (pc, 0xfffffff2); | if ne jump (pc, 0xffffffe7);

Notas:

En la versión C ++, parece que el compilador ha decidido realizar el incremento posterior en dos pasos, probablemente porque quiere el resultado en un registro i lugar de en r4 . Esto sin duda está relacionado con el tema a continuación.
El compilador ha decidido calcular la dirección base de la clase real del objeto, utilizando la vtable del objeto. Esto ocupa tres instrucciones, y presumiblemente también requiere el uso de i4 como un paso temporal en el paso 1. La búsqueda de vtable en sí misma ocupa una instrucción.

Por lo tanto: el problema no es la búsqueda vtable, que podría haberse realizado en una sola instrucción adicional (pero en realidad requiere dos). El problema es que el compilador siente la necesidad de "encontrar" el objeto. Pero ¿por qué gcc / i86 no necesita hacer eso?

La respuesta es: solía hacerlo, pero ya no. En muchos casos (donde no hay herencia múltiple, por ejemplo), la conversión de un puntero a una clase derivada a un puntero de una clase base no requiere modificar el puntero. En consecuencia, cuando llamamos a un método de la clase derivada, podemos darle el puntero de clase base como this parámetro. Pero en otros casos, eso no funciona, y tenemos que ajustar el puntero cuando hacemos el reparto y, por lo tanto, volverlo a ajustar cuando hacemos la llamada.

Hay (al menos) dos formas de realizar el segundo ajuste. Una es la forma que muestra el código DSP generado, donde el ajuste se almacena en el vtable, incluso si es 0, y luego se aplica durante la llamada. La otra forma, (llamada vtable-thunks ) es crear un thunk (un poco de código ejecutable) que ajusta el puntero de this y luego salta al punto de entrada del método, y coloca un puntero a este procesador en el vtable. (Todo esto se puede hacer en tiempo de compilación). La ventaja de la solución de procesador es que en el caso común en el que no es necesario realizar ningún ajuste, podemos optimizar el procesador y no queda ningún código de ajuste. (La desventaja es que si necesitamos un ajuste, generamos una rama adicional).

Como lo entiendo, VisualDSP ++ está basado en gcc, y podría tener las -fvtable-thunks y -fno-vtable-thunks . Así que podrías compilar con -fvtable-thunks . Pero si lo haces, deberías compilar todas las bibliotecas de C ++ que usas con esa opción, porque no puedes mezclar los dos estilos de llamada. Además, hubo (hace 15 años) varios errores en la implementación de vtable-thunks de gcc, por lo que si la versión de gcc utilizada por VisualDSP ++ es lo suficientemente antigua, es posible que también tenga esos problemas (IIRC, todos ellos implicaban herencia múltiple, por lo que podrían no se aplica a su caso de uso.)

(Prueba original, antes de la actualización):

Probé el siguiente caso simple (sin herencia múltiple, lo que puede ralentizar las cosas):

class Base { public: Base(int val) : val_(val) {} virtual int binary(int a, int b) = 0; virtual int unary(int a) = 0; virtual int nullary() = 0; protected: int val_; }; int binary(Base* begin, Base* end, int a, int b) { int accum = 0; for (; begin != end; ++begin) { accum += begin->binary(a, b); } return accum; } int unary(Base* begin, Base* end, int a) { int accum = 0; for (; begin != end; ++begin) { accum += begin->unary(a); } return accum; } int nullary(Base* begin, Base* end) { int accum = 0; for (; begin != end; ++begin) { accum += begin->nullary(); } return accum; }

Y lo compilé con gcc (4.8) usando -O3. Como esperaba, produjo exactamente el mismo código de ensamblaje que hubiera hecho su despacho de C. Aquí está el bucle for en el caso de la función unary , por ejemplo:

.L9: movq (%rbx), %rax movq %rbx, %rdi addq $16, %rbx movl %r13d, %esi call *8(%rax) addl %eax, %ebp cmpq %rbx, %r12 jne .L9

Averigüe dónde coloca su compilador vtable y acceda a él directamente para obtener los punteros de función y almacenarlos para su uso. De esa manera, tendrá prácticamente el mismo enfoque que en C con una serie de punteros de función.

Como ya se ha mencionado, puede utilizar plantillas para eliminar el envío dinámico. Aquí hay un ejemplo que hace esto:

template <typename FirstCb, typename ... RestCb> struct InterruptHandler { void execute() { // I construct temporary objects here since I could not figure out how you // construct your objects. You can change these signatures to allow for // passing arbitrary params to these handlers. FirstCb().execute(); InterruptHandler<RestCb...>().execute(); } } InterruptHandler</* Base, Derived1, and so on */> handler; void realtime(void) { handler.execute(); }

Esto debería eliminar por completo las búsquedas de vtable y, al mismo tiempo, ofrecer más oportunidades para la optimización del compilador, ya que el código en el interior se puede insertar.

Sin embargo, tenga en cuenta que necesitará cambiar algunas partes dependiendo de cómo inicialice sus manejadores. El marco básico debe seguir siendo el mismo. Además, esto requiere que tengas un compilador compatible con C++11 .

Esto no está relacionado con su pregunta, pero si está tan interesado en el rendimiento, puede usar plantillas para hacer un desenrollado de bucle para el todolist:

void (*todo[3])(void *); void *param[3]; void f1(void*) {std::cout<<"1" << std::endl;} void f2(void*) {std::cout<<"2" << std::endl;} void f3(void*) {std::cout<<"3" << std::endl;} template<int N> struct Obj { static void apply() { todo[N-1](param[N-1]); Obj<N-1>::apply(); } }; template<> struct Obj<0> { static void apply() {} }; todo[0] = f1; todo[1] = f2; todo[2] = f3; Obj<sizeof todo / sizeof *todo>::apply();

Puede ocultar el borrado de tipo void* y la recuperación de tipo dentro de las plantillas. El resultado sería (con suerte) la misma matriz para los punteros de función. Esto te ayudaría con el casting y compatible con tu código:

#include <iostream> template<class ParamType,class F> void fun(void* param) { F f; f(*static_cast<ParamType*>(param)); } struct my_function { void operator()(int& i) { std::cout << "got it " << i << std::endl; } }; int main() { void (*func)(void*) = fun<int, my_function>; int j=4; func(&j); return 0; }

En este caso, puede crear nuevas funciones como un objeto de función con más tipo de seguridad. El enfoque "normal" de OOP con funciones virtuales no ayuda aquí.

En el caso de un entorno A C ++ 11, puede crear la matriz con la ayuda de varias plantillas en tiempo de compilación (pero con una sintaxis complicada).

Sugiero usar métodos estáticos en sus clases derivadas y colocar estas funciones en su matriz. Esto eliminaría la sobrecarga de la búsqueda de v-table. Esto es lo más cercano a su implementación en lenguaje C.

Puedes terminar sacrificando el polimorfismo por la velocidad.
¿Es necesaria la herencia?
El hecho de que cambie a C ++ no significa que tenga que cambiar a Orientado a objetos.

Además, ¿has intentado desenrollar tu bucle en el ISR?
Por ejemplo, realice 2 o más llamadas de ejecución antes de volver a la parte superior del bucle.

Además, ¿puedes mover alguna de las funcionalidades del ISR? ¿Se puede realizar alguna parte de la funcionalidad mediante el "bucle de fondo" en lugar del ISR? Esto reduciría el tiempo en su ISR.