¿Cuánto afecta el orden de las etiquetas de los casos a la eficiencia de las declaraciones de cambio?

Question

Considerar:

if (condition1)
{
    // Code block 1
}
else
{
    // Code block 2
}

si se eso condition1 será true la mayoría de las veces, debería codificar la lógica tal como está escrita, en lugar de:

if (!condition1)
{
    // Code block 2
}
else
{
    // Code block 1
}

ya que evitaré la pena del jump al segundo bloque de código (nota:Tengo conocimientos limitados de lenguaje ensamblador).¿Esta idea se traslada a switch declaraciones y case ¿etiquetas?

switch (myCaseValue)
{
    case Case1:
        // Code block 1
        break;

    case Case2:
        // Code block 2
        break;

    // etc.
}

Si sé que uno de los casos ocurrirá con más frecuencia, ¿puedo reorganizar el orden de los casos? case ¿Etiquetas para que sea más eficiente?¿Debería?En mi código he estado ordenando las etiquetas de los casos alfabéticamente para facilitar la lectura del código sin pensar realmente en ello.¿Es esto una microoptimización?

Answer 1

Algunos hechos para hardware moderno como x86 o x86_64:

• Una rama incondicionalmente tomada casi no tiene costos adicionales, además de la decodificación. Si usted quiere un número, se trata de un ciclo de reloj trimestre.
• Una rama condicional, que se predijo correctamente, casi no tiene costes adicionales.
• A de ramificación condicional, que no se predijo correctamente, tiene una pena igual a la longitud de las tuberías de procesador, esto es cerca de 12-20 relojes, dependiendo del hardware.
• Los mecanismos de predicción son muy sofisticados. Bucles con un bajo número de iteraciones (en Core 2 por ejemplo hasta 64) puede ser perfectamente predicho. Pequeños patrones repetitivos como "-tomado-tomado-nottaken tomado" se pueden predecir, si no son demasiado largos (IIRC 6 en Core2).

Puede leer más sobre la predicción de saltos en Agner nieblas manual excelente .

declaraciones del interruptor normalmente se reemplazan por una tabla de saltos por el compilador. En la mayoría de los casos, el orden de los casos no hará una diferencia en absoluto. Existen mecanismos de predicción para saltos indirectos.

Así que la pregunta no es si sus saltos son más propensos a ser tomada, es si están bien predecible, al menos para el hardware que va a ejecutar el código en. Esta no es una pregunta fácil en absoluto. Pero si tiene ramas en función de una condición aleatoria (o pseudo aleatorio), usted podría tratar de reformular como una declaración sin sucursales, si es posible.

Answer 2

Su conclusión con respecto a las sentencias if no ser cierto en la mayoría de los equipos que estoy familiarizado. El problema no es que usted está saltando, pero que se están diversificando. El código podría ir en dos direcciones diferentes, dependiendo del resultado de una comparación. Esto puede atascar la tubería en la mayoría de las CPU modernas. predicción de saltos es común, y corrige el problema mayor parte del tiempo, pero no tiene nada que ver con tu ejemplo. El predictor puede predecir igual de bien que la comparación será falsa, ya que puede que sea cierto.

Como de costumbre, ver Wikipedia: Branch Predictor

Answer 3

Depende. El compilador utilizará un montón de criterios internos dependientes de la implementación de decidir si se debe implementar la switch como una secuencia de si es similar a las pruebas, o como una tabla de saltos. Esto puede depender, por ejemplo, en la forma "compacta" el conjunto de etiquetas es case. Si sus valores de etiqueta case forman un conjunto "densa", el compilador es probablemente más propensos a usar una tabla de saltos, en cuyo caso no importa el orden de las etiquetas case. Si decide ir con lo que se asemeja a una secuencia de pruebas si-si no, el orden podría ser importante.

Tenga en cuenta, sin embargo, que el cuerpo de switch es una declaración grande, con etiquetas case que proporcionan múltiples puntos de entrada a esa declaración. Por esa razón, la capacidad de los compiladores (así como la suya) para reorganizar las case "sub-bloques" dentro de esa declaración podría ser limitada.

Answer 4

etiquetas de casos deben ser ordenados de la manera más eficiente para facilitar la lectura.

Cambio de orden de las etiquetas de caso para la eficiencia es un caso de la optimización prematura menos un generador de perfiles le ha dicho específicamente que esto es un problema.

Answer 5

Creo que incluso su premisa inicial - que se puede optimizar el comunicado if reordenando el condicional bien puede ser defectuoso. En una versión no optimizada que podrían encontrar haciendo lo que estamos hablando tiene algún valor - tal vez. En el caso general que vas a tener que ir al menos una vez por cualquiera de los casos, así que no hay ninguna ventaja (en general) para organizar el condicional de todos modos. Pero eso es para no optimizado construye, por lo que se preocupa por que la optimización?

En optimizado construye, creo que puede ser sorprendido por lo que un compilador genera, a veces por una sentencia if. El compilador puede mover uno o el otro (o ambos) de los casos a un lugar fuera de línea. Creo que se trata de optimizar este inocentemente jugando con la que la condición 'es lo primero' no necesariamente va a hacer lo que quiera. En el mejor que debe hacer esto sólo después de examinar lo que está generando el compilador. Y, por supuesto, esto se convierte en un proceso costoso, puesto que incluso el más ligero cambio de realizar todo el estado puede cambiar la forma en que el compilador decide generar el código de salida.

Ahora, en lo que se refiere a la sentencia switch, yo siempre voy con el uso de un switch cuando se hace que el código sea más legible. Lo peor que un compilador debe hacer con una declaración switch que es equivalente a una declaración if es generar el mismo código. Durante más de unos pocos casos, cambian los estados generalmente se compilan como una tabla de saltos. Pero, de nuevo un conjunto de pruebas que se están comparando if una sola variable a un conjunto de valores podría muy bien ser reconocido por un compilador tal que hará lo mismo. Sin embargo, supongo que el uso de un interruptor permitirá al compilador para reconocer la situación mucho más fácilmente.

Si usted está realmente interesado en conseguir el máximo rendimiento de la actuación de ese condicional, es posible considerar el uso de algo así como Perfil guiada del MSVC Optimization (PGO o 'pogo'), que utiliza los resultados de perfiles funciona para optimizar cómo consiguen generan condicionales. No sé si es o no si GCC tiene capacidades similares.

Answer 6

No estoy seguro sobre el compilador de C #, pero sé que en el montaje de una sentencia switch en realidad se puede programar como un salto a una línea específica, en lugar de evaluar la expresión como una sentencia if. Dado que en un selecto que tiene todas las constantes, sólo se trata de los casos como los números de línea y saltar directamente al número de línea (valor caso) aprobada en sin ningún tipo de evaluación. Esto hace que el orden de las declaraciones de casos en realidad no importa en absoluto.

Answer 7

Supongo que eres consciente de que sólo importará si se trata de un punto de acceso.La mejor manera de saber si es un punto de acceso es ejecutar el código, probar el contador del programa y ver si está allí más del 10% del tiempo.Si es un punto de acceso, vea cuánto tiempo se dedica a hacer el if o switch.Generalmente es insignificante, a menos que su Block 1 y/o Block 2 hacer casi nada.Puedes usar un generador de perfiles para esto.Simplemente lo pausaré repetidamente.

Si no está familiarizado con el lenguaje ensamblador, le sugiero que lo aprenda, lo suficiente como para comprender lo que genera el compilador.Es interesante y no difícil.

Answer 8

Como otros han dicho, depende de muchas cosas, incluyendo cuántos casos existen, cómo se realiza la optimización y la arquitectura se está ejecutando en. Para una visión general interesante, ver http://ols.fedoraproject.org/ GCC / reimpresiones-2008 / Sayle-reprint.pdf

Answer 9

Si coloca los casos que ocurren con mayor frecuencia en primer lugar, esto va a optimizar el código un poco, y debido a la forma statments interruptores funcionan de la misma es verdadera. Cuando el programa entra en el interruptor y se encuentra un caso que es verdad, lo ejecutará y pulsa ruptura, que vaya a salir fuera del circuito. Su pensamiento es correcta.

Sin embargo, creo que esta optimización es bastante escaso, y si se retrasa el tiempo de desarrollo para hacer esto, es probable que no vale la pena. Además, si tiene que modificar su programa fluya de manera drástica para dar cabida a esto, no es probable que vale la pena. Sólo se está ahorrando un par de ciclos a la mayoría y probablemente nunca vería la mejora.