varias superponer studio modificar lineas graficos graficas ejes c performance switch-statement embedded lookup-tables

superponer - Tabla de búsqueda vs conmutador en software integrado C



superponer graficas en r (6)

Como fui el autor original del comentario, debo agregar un tema muy importante que no mencionó en su pregunta. Es decir, el original era sobre un sistema integrado. Suponiendo que este es un sistema típico de metal desnudo con Flash integrado, existen diferencias muy importantes con respecto a una PC en la que me concentraré.

Dichos sistemas integrados suelen tener las siguientes limitaciones.

  • sin memoria caché de la CPU
  • Flash requiere estados de espera para relojes de CPU más altos (es decir,> 32 MHz). La relación real depende del diseño del molde, el proceso de baja potencia / alta velocidad, el voltaje de operación, etc.
  • Para ocultar estados de espera, Flash tiene líneas de lectura más amplias que el bus de CPU.
  • Esto solo funciona bien para el código lineal con captación previa de instrucción.
  • Los accesos a datos perturban la captación previa de la instrucción o están estancados hasta que finaliza.
  • Flash puede tener un caché de instrucciones interno muy pequeño.
  • Si hay alguno, hay un caché de datos aún más pequeño.
  • Las pequeñas memorias caché provocan la destrucción más frecuente (reemplazando una entrada anterior antes de que se haya utilizado en otro momento).

Para, por ejemplo, el STM32F4xx una lectura lleva 6 relojes a 150MHz / 3.3V para 128 bits (4 palabras). Entonces, si se requiere un acceso a datos, es probable que agregue más de 12 relojes de retraso para que se obtengan todos los datos (hay ciclos adicionales involucrados).

Presumiendo códigos de estado compactos, para el problema real, esto tiene los siguientes efectos en esta arquitectura (Cortex-M4):

  • Lookup-table: la lectura de la dirección de la función es un acceso a datos. Con todas las implicaciones mencionadas anteriormente.
  • Un interruptor otoh utiliza una instrucción especial de "búsqueda de tabla" que utiliza datos de espacio de código justo detrás de la instrucción. De modo que las primeras entradas posiblemente ya se hayan captado previamente. Otras entradas no rompen la captación previa. También el acceso es un acceso de código, por lo tanto, los datos van a la memoria caché de instrucciones de Flash.

También tenga en cuenta que el switch no necesita funciones, por lo que el compilador puede optimizar completamente el código. Esto no es posible para una tabla de búsqueda. Al menos, no se requiere el código para la entrada / salida de funciones.

Debido a los factores antes mencionados y otros, es difícil determinar una estimación. Depende en gran medida de su plataforma y la estructura del código. Pero asumiendo el sistema dado anteriormente, el interruptor es muy probable que sea más rápido (y más claro, por cierto).

En otro hilo, me dijeron que un switch puede ser mejor que una tabla de búsqueda en términos de velocidad y compacidad.

Entonces me gustaría entender las diferencias entre esto:

Tabla de búsqueda

static void func1(){} static void func2(){} typedef enum { FUNC1, FUNC2, FUNC_COUNT } state_e; typedef void (*func_t)(void); const func_t lookUpTable[FUNC_COUNT] = { [FUNC1] = &func1, [FUNC2] = &func2 }; void fsm(state_e state) { if (state < FUNC_COUNT) lookUpTable[state](); else ;// Error handling }

y esto:

Cambiar

static void func1(){} static void func2(){} void fsm(int state) { switch(state) { case FUNC1: func1(); break; case FUNC2: func2(); break; default: ;// Error handling } }

Pensé que una tabla de búsqueda era más rápida ya que los compiladores intentan transformar las sentencias de conmutación en tablas de salto cuando sea posible. Como esto puede estar mal, me gustaría saber por qué.

¡Gracias por tu ayuda!

El uso de un LUT de indicadores de función obliga al compilador a usar esa estrategia. En teoría, podría compilar la versión del conmutador básicamente al mismo código que la versión de LUT (ahora que ha agregado controles fuera de límites a ambos). En la práctica, eso no es lo que gcc o clang eligen hacer, por lo que vale la pena mirar la salida de asm para ver qué sucedió.

(actualización: gcc -fpie ( -fpie por defecto en la mayoría de las distribuciones modernas de Linux) le gusta hacer tablas de desplazamientos relativos, en lugar de punteros de función absolutos, por lo que la rodata también es independiente de posición. Código de inicialización GCC Jump Table generando movsxd y add? Esto podría ser una optimización perdida, consulte mi respuesta para obtener enlaces a los informes de errores de gcc. La creación manual de una matriz de indicadores de función podría evitar eso.

Puse el código en el explorador del compilador Godbolt con ambas funciones en una unidad de compilación (con salida gcc y clang), para ver cómo se compila realmente. Expandí las funciones un poco, así que no fueron solo dos casos.

void fsm_switch(int state) { switch(state) { case FUNC0: func0(); break; case FUNC1: func1(); break; case FUNC2: func2(); break; case FUNC3: func3(); break; default: ;// Error handling } //prevent_tailcall(); } void fsm_lut(state_e state) { if (likely(state < FUNC_COUNT)) // without likely(), gcc puts the LUT on the taken side of this branch lookUpTable[state](); else ;// Error handling //prevent_tailcall(); }

Ver también ¿Cómo funcionan las macros likely () y improbables () en el kernel de Linux y cuál es su beneficio?

x86

En x86, clang hace su propia LUT para el conmutador, pero las entradas son punteros a dentro de la función, no a los punteros de la función final . Entonces, para clang-3.7, el switch compila código estrictamente peor que el LUT implementado manualmente. De cualquier forma, las CPU x86 tienden a tener una predicción de bifurcación que puede manejar llamadas / saltos indirectos, al menos si son fáciles de predecir.

GCC usa una secuencia de ramas condicionales ( pero desafortunadamente no realiza una cola directamente con ramas condicionales, que AFAICT está a salvo en x86 . Comprueba 1, <1, 2, 3, en ese orden, con ramas mayormente no tomadas hasta encuentra una coincidencia.

Hacen un código esencialmente idéntico para la LUT: verificación de límites, cero los 32 bits superiores del registro arg con un mov , y luego un salto indirecto de memoria con un modo de direccionamiento indexado.

BRAZO:

gcc 4.8.2 con -mcpu=cortex-m4 -O2 código interesante.

Como dijo Olaf, hace una tabla en línea de entradas 1B . No salta directamente a la función de destino, sino a una instrucción de salto normal (como b func3 ). Este es un salto incondicional normal, ya que es una llamada de cola.

Cada entrada de destino de tabla necesita significativamente más código (Godbolt) si fsm_switch hace algo después de la llamada (como en este caso una llamada de función no en línea, si void prevent_tailcall(void); se declara pero no está definida), o si está inline en una función más grande.

@@ With void prevent_tailcall(void){} defined so it can inline: @@ Unlike in the godbolt link, this is doing tailcalls. fsm_switch: cmp r0, #3 @ state, bhi .L5 @ tbb [pc, r0] @ state @@ There''s no section .rodata directive here: the table is in-line with the code, so there''s no need for base pointer to be loaded into a reg. And apparently it''s even loaded from I-cache, not D-cache .byte (.L7-.L8)/2 .byte (.L9-.L8)/2 .byte (.L10-.L8)/2 .byte (.L11-.L8)/2 .L11: b func3 @ optimized tail-call .L10: b func2 .L9: b func1 .L7: b func0 .L5: bx lr @ This is ARM''s equivalent of an x86 ret insn

IDK si hay mucha diferencia entre qué tan bien funciona la predicción de bifurcación para tbb contra un salto indirecto completo o llamada ( blx ), en un núcleo ARM ligero. Un acceso de datos para cargar la tabla puede ser más importante que el salto de dos pasos a una instrucción de bifurcación que obtiene con un switch .

He leído que las ramas indirectas están mal pronosticadas en ARM. Espero que no esté mal si la rama indirecta tiene el mismo objetivo cada vez. Pero si no, asumiría que la mayoría de los núcleos ARM no encontrarán ni siquiera patrones cortos de la misma forma que los grandes núcleos x86.

La captación / decodificación de instrucciones lleva más tiempo en x86, por lo que es más importante evitar burbujas en la secuencia de instrucciones. Esta es una razón por la cual las CPU x86 tienen una predicción de bifurcación tan buena. Los predictores modernos de ramas incluso hacen un buen trabajo con los patrones para las ramas indirectas, según el historial de esa rama y / u otras ramas que conducen a ella.

La función LUT tiene que pasar un par de instrucciones cargando la dirección base de la LUT en un registro, pero por lo demás es bastante similar a x86:

fsm_lut: cmp r0, #3 @ state, bhi .L13 @, movw r3, #:lower16:.LANCHOR0 @ tmp112, movt r3, #:upper16:.LANCHOR0 @ tmp112, ldr r3, [r3, r0, lsl #2] @ tmp113, lookUpTable bx r3 @ indirect register sibling call @ tmp113 .L13: bx lr @ @ in the .rodata section lookUpTable: .word func0 .word func1 .word func2 .word func3

Vea la respuesta de Mike de SST para un análisis similar en un Microchip dsPIC.

En la familia de dispositivos Microchip dsPIC, una tabla de búsqueda se almacena como un conjunto de direcciones de instrucción en el propio Flash. Realizar la búsqueda implica leer la dirección del Flash y luego llamar a la rutina. Hacer la llamada agrega otro puñado de ciclos para empujar el puntero de instrucción y otros bits y bobs (por ejemplo, establecer el marco de pila) de mantenimiento.

Por ejemplo, en dsPIC33E512MU810, usando XC16 (v1.24) el código de búsqueda:

lookUpTable[state]();

Compila para (desde la ventana de desensamblaje en MPLAB-X):

! lookUpTable[state](); 0x2D20: MOV [W14], W4 ; get state from stack-frame (not counted) 0x2D22: ADD W4, W4, W5 ; 1 cycle (addresses are 16 bit aligned) 0x2D24: MOV #0xA238, W4 ; 1 cycle (get base address of look-up table) 0x2D26: ADD W5, W4, W4 ; 1 cycle (get address of entry in table) 0x2D28: MOV [W4], W4 ; 1 cycle (get address of the function) 0x2D2A: CALL W4 ; 2 cycles (push PC+2 set PC=W4)

... y cada función (vacía, sin hacer nada) se compila para:

!static void func1() !{} 0x2D0A: LNK #0x0 ; 1 cycle (set up stack frame) ! Function body goes here 0x2D0C: ULNK ; 1 cycle (un-link frame pointer) 0x2D0E: RETURN ; 3 cycles

Este es un total de 11 ciclos de instrucciones de sobrecarga para cualquiera de los casos, y todos toman el mismo. (Nota: Si la tabla o las funciones que contiene no están en la misma página Flash de palabras de programa de 32K, habrá una sobrecarga aún mayor debido a que la Unidad de generación de direcciones debe leer desde la página correcta o configurar la PC para hacer una llamada larga).

Por otro lado, siempre que la instrucción switch completa se ajuste a un determinado tamaño, el compilador generará código que realiza una prueba y rama relativa como dos instrucciones por caso, tomando tres (o posiblemente cuatro) ciclos por caso hasta el verdadero .

Por ejemplo, la declaración de cambio:

switch(state) { case FUNC1: state++; break; case FUNC2: state--; break; default: break; }

Compila para:

! switch(state) 0x2D2C: MOV [W14], W4 ; get state from stack-frame (not counted) 0x2D2E: SUB W4, #0x0, [W15] ; 1 cycle (compare with first case) 0x2D30: BRA Z, 0x2D38 ; 1 cycle (if branch not taken, or 2 if it is) 0x2D32: SUB W4, #0x1, [W15] ; 1 cycle (compare with second case) 0x2D34: BRA Z, 0x2D3C ; 1 cycle (if branch not taken, or 2 if it is) ! { ! case FUNC1: state++; break; 0x2D38: INC [W14], [W14] ; To stop the switch being optimised out 0x2D3A: BRA 0x2D40 ; 2 cycles (go to end of switch) ! case FUNC2: state--; break; 0x2D3C: DEC [W14], [W14] ; To stop the switch being optimised out 0x2D3E: NOP ; compiler did a fall-through (for some reason) ! default: break; 0x2D36: BRA 0x2D40 ; 2 cycles (go to end of switch) ! }

Esto es una sobrecarga de 5 ciclos si se toma el primer caso, 7 si se toma el segundo caso, etc., lo que significa que se divide en el cuarto caso.

Esto significa que conocer sus datos en el momento del diseño tendrá una influencia significativa en la velocidad a largo plazo. Si tiene un número significativo (más de 4 casos) y todos ocurren con una frecuencia similar, una tabla de búsqueda será más rápida a largo plazo. Si la frecuencia de los casos es significativamente diferente (por ejemplo, el caso 1 es más probable que el caso 2, que es más probable que el caso 3, etc.) entonces, si ordena el cambio con el caso más probable primero, entonces el interruptor será más rápido a largo plazo. Para el caso extremo cuando solo tienes unos pocos casos, el interruptor será (probablemente) más rápido de todos modos para la mayoría de las ejecuciones y es más legible y menos propenso a errores.

Si solo hay unos pocos casos en el interruptor, o algunos casos ocurrirán con más frecuencia que otros, entonces hacer la prueba y la rama del interruptor probablemente tomará menos ciclos que usar una tabla de búsqueda. Por otro lado, si tiene más de un puñado de casos de eso con una frecuencia similar, la búsqueda probablemente será más rápida en promedio.

Consejo: Vaya con el interruptor a menos que sepa que la búsqueda será definitivamente más rápida y que el tiempo de ejecución es importante.

Editar: El ejemplo de mi interruptor es un poco injusto, ya que ignoré la pregunta original y alineé el ''cuerpo'' de las cajas para resaltar la verdadera ventaja de usar un interruptor sobre una búsqueda. ¡Si el interruptor también tiene que hacer la llamada, solo tiene la ventaja para el primer caso!

En primer lugar, en algunos procesadores, las llamadas indirectas (por ejemplo, a través de un puntero), como las que aparecen en el ejemplo de la tabla de búsqueda , son costosas (rotura de tuberías, TLB, efectos de caché). También podría ser cierto para saltos indirectos ...

Entonces, un buen compilador de optimización puede func1() la llamada a func1() en su ejemplo de Switch ; entonces no ejecutará ningún prólogo o epílogo para funciones en línea.

Es necesario realizar un benchmark para estar seguro, ya que muchos otros factores importan en el rendimiento. Ver también this (y la referencia allí).

La respuesta de msc y los comentarios te dan buenos consejos sobre por qué el rendimiento puede no ser el esperado. Benchmarking es la regla, pero los resultados pueden variar de una arquitectura a otra, y pueden cambiar con otras versiones del compilador y, por supuesto, su configuración y opciones seleccionadas.

Sin embargo, tenga en cuenta que sus 2 piezas de código no realizan la misma validación en el state :

  • El cambio no hará nada con gracia, el state no es uno de los valores definidos,
  • La versión de la tabla de salto invocará un comportamiento indefinido para todos los valores FUNC1 y FUNC2 .

No hay una forma genérica de inicializar la tabla de salto con punteros de función ficticia sin hacer suposiciones en FUNC_COUNT . Obtiene el mismo comportamiento, la versión de la tabla de salto debería verse así:

void fsm(int state) { if (state >= 0 && state < FUNC_COUNT && lookUpTable[state] != NULL) lookUpTable[state](); }

Intente realizar una evaluación comparativa e inspeccionar el código de ensamblaje. Aquí hay un práctico compilador en línea para esto: http://gcc.godbolt.org/#

Para tener aún más salidas de compilador, aquí lo que produce el compilador TI C28x utilizando el código de ejemplo de @PeterCordes:

_fsm_switch: CMPB AL,#0 ; [CPU_] |62| BF $C$L3,EQ ; [CPU_] |62| ; branchcc occurs ; [] |62| CMPB AL,#1 ; [CPU_] |62| BF $C$L2,EQ ; [CPU_] |62| ; branchcc occurs ; [] |62| CMPB AL,#2 ; [CPU_] |62| BF $C$L1,EQ ; [CPU_] |62| ; branchcc occurs ; [] |62| CMPB AL,#3 ; [CPU_] |62| BF $C$L4,NEQ ; [CPU_] |62| ; branchcc occurs ; [] |62| LCR #_func3 ; [CPU_] |66| ; call occurs [#_func3] ; [] |66| B $C$L4,UNC ; [CPU_] |66| ; branch occurs ; [] |66| $C$L1: LCR #_func2 ; [CPU_] |65| ; call occurs [#_func2] ; [] |65| B $C$L4,UNC ; [CPU_] |65| ; branch occurs ; [] |65| $C$L2: LCR #_func1 ; [CPU_] |64| ; call occurs [#_func1] ; [] |64| B $C$L4,UNC ; [CPU_] |64| ; branch occurs ; [] |64| $C$L3: LCR #_func0 ; [CPU_] |63| ; call occurs [#_func0] ; [] |63| $C$L4: LCR #_prevent_tailcall ; [CPU_] |69| ; call occurs [#_prevent_tailcall] ; [] |69| LRETR ; [CPU_] ; return occurs ; [] _fsm_lut: ;* AL assigned to _state CMPB AL,#4 ; [CPU_] |84| BF $C$L5,HIS ; [CPU_] |84| ; branchcc occurs ; [] |84| CLRC SXM ; [CPU_] MOVL XAR4,#_lookUpTable ; [CPU_U] |85| MOV ACC,AL << 1 ; [CPU_] |85| ADDL XAR4,ACC ; [CPU_] |85| MOVL XAR7,*+XAR4[0] ; [CPU_] |85| LCR *XAR7 ; [CPU_] |85| ; call occurs [XAR7] ; [] |85| $C$L5: LCR #_prevent_tailcall ; [CPU_] |88| ; call occurs [#_prevent_tailcall] ; [] |88| LRETR ; [CPU_] ; return occurs ; []

También utilicé -O2 optimizaciones. Podemos ver que el conmutador no se convierte en una tabla de salto incluso si el compilador tiene la habilidad.