statement - switch en c++ ejemplos resueltos

Switch(){case:} rendimiento en C

Question

Posible duplicado:
¿Por qué cambiar / Caso y no If / Else If?

Me gustaría comprender cómo un enunciado de switch() case: el compilador convierte la instrucción en C en códigos de operación del ensamblador.

Específicamente, estoy interesado en entender la diferencia con una serie de ramas if then else .

La comparación de rendimiento es el tema principal.

Algunas palabras sobre vocabulario: estoy familiarizado con los conceptos principales de los ensambladores, ya que hace tiempo que codifiqué en ensamblador para sistemas más simples, pero ciertamente no sé nada acerca de la semántica del ensamblador x86. Entonces, una salida de ensamblador directo no será útil. Pseudo-código es mucho preferido.

Answer 1

Dependiendo de varias heurísticas en el compilador, el código generado puede terminar siendo una simple cadena de declaraciones "if else if". En algunas situaciones, cuando el espacio de casos es pequeño, el compilador puede crear una tabla de salto, por ejemplo:

switch (foo) {
case 0:
a();
case 1:
b();
case 2:
c();
case 3:
d();
default:
e();
}

Se puede traducir a algo así como:

if (foo < 0 || foo > 3) goto label_default;
else goto internal_jump_table[foo];
internal_jump_table = { label_0, label_1, label_2, label_3 };
label_0: a();
label_1: b();
label_2: c();
label_3: d();
label_default: e();

Hay otras optimizaciones que se pueden hacer. En lugar de verificar la igualdad, el compilador puede construir una jerarquía de sentencias if para buscar binariamente el valor correcto. O tal vez tenga muchos valores en los que una tabla de salto es adecuada y algunos valores atípicos en los que se realiza una búsqueda normal. O tal vez solo dos mesas de salto.

Answer 2

La respuesta común siempre es "eso depende". El rendimiento puede depender de la plataforma / tipo de CPU, el compilador, las opciones del compilador, etc.

Creo que, dadas las circunstancias correctas, un constructo switch() tendrá un log de complejidad (n), donde n es el número de case: declaraciones. Esto se logra mediante "búsqueda binaria".

Esta página tiene muchos detalles (se centra en el compilador de Microsofts, pero las ideas generales que creo se aplican en general).

Answer 3

Teniendo en cuenta un número "suficientemente grande" de switch cases de switch cases (suficiente para permitir que el compilador opte por generar una tabla de ramificación en lugar de un if / else simple si ):

• una caja de conmutación tendrá acceso de tiempo constante (O (1)) al bloque correcto de código que se ejecutará

• mientras que una serie if/else if tendrá tiempo lineal (O ( n ) donde n es el número de condiciones para evaluar (sentencias if ), para n> = "lo suficientemente grande")

Actualización: ¡ Por supuesto, estas consideraciones no tienen en cuenta la optimización del compilador!

Answer 4

El compilador puede decidir implementarlo como la serie equivalente de sentencias if / else if , o puede decidir optimizarlo usando una tabla de ramificación . Esto depende de varios parámetros, como el número de ramas y el tamaño del rango mínimo que incluye todos los valores con los que se compara.

Actualización: recuerdo haber leído en alguna parte que, por lo general, los compiladores no se molestan en crear una tabla de ramificación a menos que haya al menos 4 conmutadores o más; El comentario informativo de Stephane Rouberol a continuación documenta específicamente cómo se puede configurar este umbral para GCC.