Rendimiento de la matriz de funciones sobre las instrucciones if y switch

Question

Escribo una parte muy crítica del rendimiento del código y tuve esta loca idea de sustituir sentencias case (o sentencias if) con una matriz de punteros a función.

Déjenme demostrar; aquí va la versión normal:

while(statement) 
{ 
    /* 'option' changes on every iteration */ 

    switch(option) 
    { 
     case 0: /* simple task */ break; 
     case 1: /* simple task */ break; 
     case 2: /* simple task */ break; 
     case 3: /* simple task */ break; 
    } 
} 

Y aquí está la versión "función de llamada":

void task0(void) { 
    /* simple task */ 
} 

void task1(void) { 
    /* simple task */ 
} 

void task2(void) { 
    /* simple task */ 
} 

void task3(void) { 
    /* simple task */ 
} 

void (*task[4]) (void); 

task[0] = task0; 
task[1] = task1; 
task[2] = task2; 
task[3] = task3; 

while(statement) 
{ 
    /* 'option' changes on every iteration */ 

    /* and now we call the function with 'case' number */ 
    (*task[option])(); 
} 

Así qué versión será más rápido? ¿La sobrecarga de la llamada de función elimina el beneficio de velocidad sobre la declaración de cambio normal (o si)?

Por supuesto, esta última versión no es tan legible, pero estoy buscando toda la velocidad que pueda obtener.

Estoy a punto de comparar esto cuando preparo las cosas, pero si alguien ya tiene una respuesta, no me molestaré.

Answer 1

Creo que al final del día sus instrucciones de conmutación serán las más rápidas, porque los punteros de función tienen la "sobrecarga" de la búsqueda de la función y la función se llama a sí misma. Un interruptor es solo una tabla jmp recta. Por supuesto, depende en diferentes cosas que solo las pruebas pueden darle una respuesta. Ese es mi valor de dos centavos.

Answer 2

La instrucción de conmutación debe compilarse en un branch table, que es esencialmente lo mismo que su conjunto de funciones, si su compilador tiene al menos la capacidad de optimización básica.

Answer 3

De qué versión dependerá más rápido. La implementación ingenua de switch es una enorme construcción if ... else if ... else if ..., lo que significa que se necesita un promedio de O (n) tiempo para ejecutar donde n es el número de casos. Su tabla de saltos es O (1), por lo tanto, cuantos más casos diferentes haya y cuanto más se usen los casos posteriores, es más probable que la tabla de saltos sea mejor. Para un pequeño número de casos o conmutadores donde el primer caso se elige con más frecuencia que otros, la implementación ingenua es mejor. El asunto es complicado por el hecho de que el compilador puede elegir usar una tabla de salto incluso cuando haya escrito un interruptor si cree que será más rápido.

La única manera de saber cuál elegir es la prueba de rendimiento de su código.

Answer 4

Un buen compilador compilará un interruptor con casos en un pequeño rango numérico como un solo condicional para ver si el valor está en ese rango (que a veces se puede optimizar) seguido de un salto de salto. Esto es casi seguro que sea más rápido que una llamada de función (directo o indirecto) porque:

1. Un salto es mucho menos caro que una llamada (que debe guardar registros de llamadas-Demolí, ajustar la pila, etc.).
2. El código en los casos de instrucción de conmutación puede hacer uso de valores de expresión ya almacenados en caché en los registros de la persona que llama.

Es posible que un compilador muy avanzada podría determinar que el puntero de llamadas a través de funciones sólo se refiere a uno de un pequeño conjunto de funciones de vinculación estática, y con ello optimizar las cosas en gran medida, tal vez incluso la eliminación de las llamadas y la sustitución ellos por saltos. Pero no contaría con eso.

Answer 5

En primer lugar, lo haría randomly-pause unas cuantas veces, para asegurarme de que se dedique suficiente tiempo en este envío para siquiera molestarme en optimizarlo.

En segundo lugar, si lo es, dado que cada bifurcación pasa muy pocos ciclos, desea una tabla de salto para llegar a la bifurcación deseada. La razón por la que existen switch afirmaciones es sugerir al compilador que puede generar uno si los valores del interruptor son compactos.

¿Cuánto dura la lista de valores de conmutación? Si es corto, la escalera if podría ser aún más rápida, especialmente si coloca los códigos utilizados con mayor frecuencia en la parte superior. Una alternativa a if-ladder (que nunca he visto usar a nadie) es un if-tree, el código equivalente de un árbol binario.

Probablemente no desee una serie de indicadores de función. Sí, es una referencia de matriz para obtener el puntero a la función, pero hay varias instrucciones sobrecargadas para llamar a una función, y parece que eso podría abrumar la pequeña cantidad que se realiza dentro de cada función.

En cualquier caso, mirar el lenguaje ensamblador, o un solo paso en el nivel de instrucción, le dará una buena idea de lo eficiente que es.

Answer 6

Llegué a este post recientemente ya que me preguntaba lo mismo. Terminé tomándome el tiempo para probarlo. Ciertamente, depende en gran medida de lo que esté haciendo, pero para mi VM fue una velocidad decente (15-25%), y me permitió simplificar algunos códigos (que es de donde proviene la aceleración). A modo de ejemplo (código simplificado para mayor claridad), un bucle "for" fue capaz de ser implementado fácilmente usando un bucle for:

void OpFor(Frame* frame, Instruction* &code) 
{ 
    i32 start = GET_OP_A(code); 
    i32 stop_value = GET_OP_B(code); 
    i32 step = GET_OP_C(code); 
    // instruction count (ie. block size) 
    u32 i_count = GET_OP_D(code); 
    // pointer to end of block (NOP if it branches) 
    Instruction* end = code + i_count; 

    if(step > 0) 
    { 
    for(u32 i = start; i < stop_value; i += step) 
    { 
     // rewind instruction pointer 
     Instruction* cur = code; 

     // execute code inside for loop 
     while(cur != end) 
     { 
     cur->func(frame, cur); 
     ++cur; 
     } 
    } 
    } 
    else 
    // same with <= 
}