¿Cuál es el efecto de ordenar si ... si no, si las declaraciones por probabilidad?

187

Específicamente, si tengo una serie de if... else ifdeclaraciones, y de alguna manera sé de antemano la probabilidad relativa de que cada declaración se evalúe true, ¿cuánta diferencia en el tiempo de ejecución representa ordenarlas en orden de probabilidad? Por ejemplo, debería preferir esto:

if (highly_likely)
  //do something
else if (somewhat_likely)
  //do something
else if (unlikely)
  //do something

¿a esto?:

if (unlikely)
  //do something
else if (somewhat_likely)
  //do something
else if (highly_likely)
  //do something

Parece obvio que la versión ordenada sería más rápida, sin embargo, para facilitar la lectura o la existencia de efectos secundarios, es posible que desee ordenarlos de manera no óptima. También es difícil saber qué tan bien funcionará la CPU con la predicción de bifurcación hasta que realmente ejecute el código.

Entonces, en el transcurso de experimentar con esto, terminé respondiendo mi propia pregunta para un caso específico, sin embargo, también me gustaría escuchar otras opiniones / ideas.

Importante: esta pregunta supone que las ifdeclaraciones se pueden reordenar arbitrariamente sin tener ningún otro efecto sobre el comportamiento del programa. En mi respuesta, las tres pruebas condicionales son mutuamente excluyentes y no producen efectos secundarios. Ciertamente, si las declaraciones deben evaluarse en un cierto orden para lograr el comportamiento deseado, entonces el tema de la eficiencia es discutible.

Carlton
fuente
35
es posible que desee agregar una nota de que las condiciones son mutuamente excluyentes, de lo contrario las dos versiones no son equivalentes
idclev 463035818
28
Es bastante interesante cómo una pregunta auto respondida obtuvo más de 20 votos positivos con una respuesta bastante pobre, en una hora. Sin llamar a nada en OP, pero los votantes deben tener cuidado de saltar en el carro de la banda. La pregunta puede ser interesante, pero los resultados son dudosos.
luk32
3
Creo que esto se puede describir como una forma de evaluación de cortocircuito porque golpear una comparación niega golpear una comparación diferente. Personalmente, estoy a favor de una implementación como esta cuando una comparación rápida, digamos booleana, puede impedirme pasar a una comparación diferente que podría implicar una manipulación de cadenas, expresiones regulares o interacción de base de datos con muchos recursos.
MonkeyZeus
11
Algunos compiladores ofrecen la capacidad de recopilar estadísticas sobre las ramas tomadas y enviarlas de nuevo al compilador para permitirle realizar mejores optimizaciones.
11
Si el rendimiento como este es importante para usted, probablemente debería probar la Optimización guiada por perfil y comparar el resultado manual con el resultado del compilador
Justin

Respuestas:

96

Como regla general, la mayoría de las CPU de Intel, si no todas, suponen que las ramas hacia adelante no se toman la primera vez que las ven. Ver el trabajo de Godbolt .

Después de eso, la rama entra en un caché de predicción de rama, y ​​el comportamiento pasado se utiliza para informar la predicción de rama futura.

Entonces, en un circuito cerrado, el efecto de la falta de orden será relativamente pequeño. El predictor de rama aprenderá qué conjunto de ramas es más probable, y si tiene una cantidad de trabajo no trivial en el ciclo, las pequeñas diferencias no sumarán mucho.

En general, la mayoría de los compiladores por defecto (sin otro motivo) ordenarán el código de máquina producido aproximadamente de la manera en que lo ordenó en su código. Por lo tanto, si las declaraciones son ramas hacia adelante cuando fallan.

Por lo tanto, debe ordenar sus ramas en el orden de probabilidad decreciente de obtener la mejor predicción de rama de un "primer encuentro".

Un microbenchmark que se repite muchas veces en un conjunto de condiciones y realiza un trabajo trivial estará dominado por pequeños efectos del recuento de instrucciones y similares, y poco en cuanto a los problemas relativos de predicción de ramas. Entonces, en este caso, debe crear un perfil , ya que las reglas generales no serán confiables.

Además de eso, la vectorización y muchas otras optimizaciones se aplican a pequeños bucles estrechos.

Entonces, en el código general, coloque el código más probable dentro del ifbloque, y eso dará como resultado la menor cantidad de errores de predicción de ramificación no almacenados en caché. En bucles ajustados, siga la regla general para comenzar, y si necesita saber más, no tiene más remedio que hacer un perfil.

Naturalmente, todo esto desaparece si algunas pruebas son mucho más baratas que otras.

Yakk - Adam Nevraumont
fuente
19
También vale la pena considerar lo caras que son las pruebas en sí: si una prueba es solo un poco más probable, pero mucho más costosa, entonces puede valer la pena poner la otra prueba primero, porque los ahorros de no hacer la prueba costosa probablemente superen ahorros por predicción de sucursales, etc.
psmears
El enlace que proporcionó no respalda su conclusión. Como regla general, la mayoría de las CPU de Intel, si no todas, asumen que no se toman las ramas de avance la primera vez que las ven . De hecho, eso solo es cierto para la CPU Arrendale relativamente oscura cuyos resultados se muestran primero. Los resultados principales de Ivy Bridge y Haswell no lo respaldan en absoluto. Haswell parece muy cercano a "predecir siempre la caída" de ramas invisibles, e Ivy Bridge no está nada claro.
BeeOnRope
En general, se entiende que las CPU realmente no están utilizando predicciones estáticas como lo hicieron en el pasado. De hecho, Intel moderno probablemente está usando algo como un predictor TAGE probabilístico. Simplemente hash el historial de ramificaciones en varias tablas de historial y toma una que coincida con el historial más largo. Utiliza una "etiqueta" para tratar de evitar el alias, pero la etiqueta solo tiene unos pocos bits. Si omite todas las longitudes del historial, probablemente se haga una predicción predeterminada que no necesariamente depende de la dirección de la rama (en Haswell podemos decir que claramente no).
BeeOnRope
44

Hice la siguiente prueba para cronometrar la ejecución de dos if... else ifbloques diferentes , uno ordenado en orden de probabilidad y el otro en orden inverso:

#include <chrono>
#include <iostream>
#include <random>
#include <algorithm>
#include <iterator>
#include <functional>

using namespace std;

int main()
{
    long long sortedTime = 0;
    long long reverseTime = 0;

    for (int n = 0; n != 500; ++n)
    {
        //Generate a vector of 5000 random integers from 1 to 100
        random_device rnd_device;
        mt19937 rnd_engine(rnd_device());
        uniform_int_distribution<int> rnd_dist(1, 100);
        auto gen = std::bind(rnd_dist, rnd_engine);
        vector<int> rand_vec(5000);
        generate(begin(rand_vec), end(rand_vec), gen);

        volatile int nLow, nMid, nHigh;
        chrono::time_point<chrono::high_resolution_clock> start, end;

        //Sort the conditional statements in order of increasing likelyhood
        nLow = nMid = nHigh = 0;
        start = chrono::high_resolution_clock::now();
        for (int& i : rand_vec) {
            if (i >= 95) ++nHigh;               //Least likely branch
            else if (i < 20) ++nLow;
            else if (i >= 20 && i < 95) ++nMid; //Most likely branch
        }
        end = chrono::high_resolution_clock::now();
        reverseTime += chrono::duration_cast<chrono::nanoseconds>(end-start).count();

        //Sort the conditional statements in order of decreasing likelyhood
        nLow = nMid = nHigh = 0;
        start = chrono::high_resolution_clock::now();
        for (int& i : rand_vec) {
            if (i >= 20 && i < 95) ++nMid;  //Most likely branch
            else if (i < 20) ++nLow;
            else if (i >= 95) ++nHigh;      //Least likely branch
        }
        end = chrono::high_resolution_clock::now();
        sortedTime += chrono::duration_cast<chrono::nanoseconds>(end-start).count();

    }

    cout << "Percentage difference: " << 100 * (double(reverseTime) - double(sortedTime)) / double(sortedTime) << endl << endl;
}

Usando MSVC2017 con / O2, los resultados muestran que la versión ordenada es consistentemente un 28% más rápida que la versión no ordenada. Según el comentario de luk32, también cambié el orden de las dos pruebas, lo que hace una diferencia notable (22% frente a 28%). El código se ejecutó bajo Windows 7 en un Intel Xeon E5-2697 v2. Esto es, por supuesto, muy específico del problema y no debe interpretarse como una respuesta concluyente.

Carlton
fuente
9
Sin embargo, OP debe tener cuidado, ya que cambiar una if... else ifdeclaración podría tener un efecto sustancial sobre cómo fluye la lógica a través del código. Es unlikelyposible que el cheque no salga a menudo, pero puede ser necesario que la empresa verifique unlikelyprimero la condición antes de buscar otros.
Luke T Brooks el
21
30% más rápido? ¿Quiere decir que fue más rápido con aproximadamente el% de extra si no tenía que realizar declaraciones? Parece un resultado bastante razonable.
UKMonkey
55
¿Cómo lo comparaste? ¿Qué compilador, CPU, etc.? Estoy bastante seguro de que este resultado no es portátil.
luk32
12
Un problema con este microbenchmark es que la CPU determinará cuál de las ramas es más probable y la almacenará en caché cuando la repita repetidamente. Si las ramas no se examinan en un pequeño bucle cerrado, la memoria caché de predicción de la rama podría no tenerlas, y los costos podrían ser mucho más altos si la CPU adivina mal con la guía de la memoria caché de predicción de la rama cero.
Yakk - Adam Nevraumont el
66
Este punto de referencia no es demasiado confiable. Compilar con gcc 6.3.0 : g++ -O2 -march=native -std=c++14da una ligera ventaja a las declaraciones condicionales ordenadas, pero la mayoría de las veces, la diferencia porcentual entre las dos ejecuciones fue de ~ 5%. Varias veces, en realidad fue más lento (debido a las variaciones). Estoy bastante seguro de que ifno vale la pena preocuparse por ordenar este tipo de mensajes; PGO probablemente se encargará por completo de tales casos
Justin
30

No, no debería, a menos que esté realmente seguro de que el sistema de destino se ve afectado. Por defecto ir por legibilidad.

Dudo mucho sus resultados. He modificado un poco su ejemplo, por lo que invertir la ejecución es más fácil. Ideone muestra consistentemente que el orden inverso es más rápido, aunque no mucho. En ciertas carreras, incluso esto ocasionalmente se volteó. Yo diría que los resultados no son concluyentes. Coliru tampoco informa una diferencia real. Puedo verificar la CPU Exynos5422 en mi odroid xu4 más adelante.

La cuestión es que las CPU modernas tienen predictores de rama. Hay mucha, mucha lógica dedicada a buscar datos e instrucciones, y las CPU modernas x86 son bastante inteligentes, cuando se trata de esto. Algunas arquitecturas más delgadas como ARM o GPU pueden ser vulnerables a esto. Pero depende mucho del compilador y del sistema de destino.

Yo diría que la optimización de pedidos de sucursales es bastante frágil y efímera. Hazlo solo como un paso de ajuste realmente fino.

Código:

#include <chrono>
#include <iostream>
#include <random>
#include <algorithm>
#include <iterator>
#include <functional>

using namespace std;

int main()
{
    //Generate a vector of random integers from 1 to 100
    random_device rnd_device;
    mt19937 rnd_engine(rnd_device());
    uniform_int_distribution<int> rnd_dist(1, 100);
    auto gen = std::bind(rnd_dist, rnd_engine);
    vector<int> rand_vec(5000);
    generate(begin(rand_vec), end(rand_vec), gen);
    volatile int nLow, nMid, nHigh;

    //Count the number of values in each of three different ranges
    //Run the test a few times
    for (int n = 0; n != 10; ++n) {

        //Run the test again, but now sort the conditional statements in reverse-order of likelyhood
        {
          nLow = nMid = nHigh = 0;
          auto start = chrono::high_resolution_clock::now();
          for (int& i : rand_vec) {
              if (i >= 95) ++nHigh;               //Least likely branch
              else if (i < 20) ++nLow;
              else if (i >= 20 && i < 95) ++nMid; //Most likely branch
          }
          auto end = chrono::high_resolution_clock::now();
          cout << "Reverse-sorted: \t" << chrono::duration_cast<chrono::nanoseconds>(end-start).count() << "ns" << endl;
        }

        {
          //Sort the conditional statements in order of likelyhood
          nLow = nMid = nHigh = 0;
          auto start = chrono::high_resolution_clock::now();
          for (int& i : rand_vec) {
              if (i >= 20 && i < 95) ++nMid;  //Most likely branch
              else if (i < 20) ++nLow;
              else if (i >= 95) ++nHigh;      //Least likely branch
          }
          auto end = chrono::high_resolution_clock::now();
          cout << "Sorted:\t\t\t" << chrono::duration_cast<chrono::nanoseconds>(end-start).count() << "ns" << endl;
        }
        cout << endl;
    }
}
luk32
fuente
Obtengo la misma diferencia de ~ 30% en el rendimiento cuando cambio el orden de los bloques if ordenados y ordenados inversamente, como se hizo en su código. No estoy seguro de por qué Ideone y Coliru no muestran diferencias.
Carlton
Ciertamente interesante. Trataré de obtener algunos datos para otros sistemas, pero podría llevarme un día hasta que tenga que jugar con ellos. La pregunta es interesante, especialmente a la luz de sus resultados, pero son tan espectaculares que tuve que verificarla.
luk32
Si la pregunta es ¿Cuál es el efecto? la respuesta no puede ser no !
PJTraill
Sip. Pero no recibo notificaciones de actualizaciones de la pregunta original. Hicieron la formulación de la respuesta obsoleta. Lo siento. Editaré el contenido más tarde, para señalar que respondió la pregunta original y mostró algunos resultados que demostraron el punto original.
luk32
Vale la pena repetir esto: "Por defecto, vaya por legibilidad". Escribir código legible a menudo le dará mejores resultados que intentar obtener un pequeño aumento de rendimiento (en términos absolutos) al hacer que su código sea más difícil de analizar para los humanos.
Andrew Brēza
26

Solo mis 5 centavos. Parece el efecto de ordenar si las declaraciones deberían depender de:

  1. Probabilidad de cada enunciado if.

  2. Número de iteraciones, por lo que el predictor de rama podría entrar en acción.

  3. Sugerencias de compilación probables / improbables, es decir, diseño de código.

Para explorar esos factores, comparé las siguientes funciones:

shown_ifs ()

for (i = 0; i < data_sz * 1024; i++) {
    if (data[i] < check_point) // highly likely
        s += 3;
    else if (data[i] > check_point) // samewhat likely
        s += 2;
    else if (data[i] == check_point) // very unlikely
        s += 1;
}

reversed_ifs ()

for (i = 0; i < data_sz * 1024; i++) {
    if (data[i] == check_point) // very unlikely
        s += 1;
    else if (data[i] > check_point) // samewhat likely
        s += 2;
    else if (data[i] < check_point) // highly likely
        s += 3;
}

shown_ifs_with_hints ()

for (i = 0; i < data_sz * 1024; i++) {
    if (likely(data[i] < check_point)) // highly likely
        s += 3;
    else if (data[i] > check_point) // samewhat likely
        s += 2;
    else if (unlikely(data[i] == check_point)) // very unlikely
        s += 1;
}

reversed_ifs_with_hints ()

for (i = 0; i < data_sz * 1024; i++) {
    if (unlikely(data[i] == check_point)) // very unlikely
        s += 1;
    else if (data[i] > check_point) // samewhat likely
        s += 2;
    else if (likely(data[i] < check_point)) // highly likely
        s += 3;
}

datos

La matriz de datos contiene números aleatorios entre 0 y 100:

const int RANGE_MAX = 100;
uint8_t data[DATA_MAX * 1024];

static void data_init(int data_sz)
{
    int i;
        srand(0);
    for (i = 0; i < data_sz * 1024; i++)
        data[i] = rand() % RANGE_MAX;
}

Los resultados

Los siguientes resultados son para Intel i5 @ 3,2 GHz y G ++ 6.3.0. El primer argumento es check_point (es decir, probabilidad en %% para la declaración if altamente probable), el segundo argumento es data_sz (es decir, número de iteraciones).

---------------------------------------------------------------------
Benchmark                              Time           CPU Iterations
---------------------------------------------------------------------
ordered_ifs/50/4                    4660 ns       4658 ns     150948
ordered_ifs/50/8                   25636 ns      25635 ns      27852
ordered_ifs/75/4                    4326 ns       4325 ns     162613
ordered_ifs/75/8                   18242 ns      18242 ns      37931
ordered_ifs/100/4                   1673 ns       1673 ns     417073
ordered_ifs/100/8                   3381 ns       3381 ns     207612
reversed_ifs/50/4                   5342 ns       5341 ns     126800
reversed_ifs/50/8                  26050 ns      26050 ns      26894
reversed_ifs/75/4                   3616 ns       3616 ns     193130
reversed_ifs/75/8                  15697 ns      15696 ns      44618
reversed_ifs/100/4                  3738 ns       3738 ns     188087
reversed_ifs/100/8                  7476 ns       7476 ns      93752
ordered_ifs_with_hints/50/4         5551 ns       5551 ns     125160
ordered_ifs_with_hints/50/8        23191 ns      23190 ns      30028
ordered_ifs_with_hints/75/4         3165 ns       3165 ns     218492
ordered_ifs_with_hints/75/8        13785 ns      13785 ns      50574
ordered_ifs_with_hints/100/4        1575 ns       1575 ns     437687
ordered_ifs_with_hints/100/8        3130 ns       3130 ns     221205
reversed_ifs_with_hints/50/4        6573 ns       6572 ns     105629
reversed_ifs_with_hints/50/8       27351 ns      27351 ns      25568
reversed_ifs_with_hints/75/4        3537 ns       3537 ns     197470
reversed_ifs_with_hints/75/8       16130 ns      16130 ns      43279
reversed_ifs_with_hints/100/4       3737 ns       3737 ns     187583
reversed_ifs_with_hints/100/8       7446 ns       7446 ns      93782

Análisis

1. El pedido sí importa

Para iteraciones 4K y (casi) 100% de probabilidad de afirmaciones muy apreciadas, la diferencia es enorme 223%:

---------------------------------------------------------------------
Benchmark                              Time           CPU Iterations
---------------------------------------------------------------------
ordered_ifs/100/4                   1673 ns       1673 ns     417073
reversed_ifs/100/4                  3738 ns       3738 ns     188087

Para las iteraciones 4K y el 50% de probabilidad de afirmaciones muy apreciadas, la diferencia es de aproximadamente el 14%:

---------------------------------------------------------------------
Benchmark                              Time           CPU Iterations
---------------------------------------------------------------------
ordered_ifs/50/4                    4660 ns       4658 ns     150948
reversed_ifs/50/4                   5342 ns       5341 ns     126800

2. El número de iteraciones importa

La diferencia entre las iteraciones 4K y 8K para (casi) el 100% de probabilidad de afirmaciones muy apreciadas es aproximadamente dos veces (como se esperaba):

---------------------------------------------------------------------
Benchmark                              Time           CPU Iterations
---------------------------------------------------------------------
ordered_ifs/100/4                   1673 ns       1673 ns     417073
ordered_ifs/100/8                   3381 ns       3381 ns     207612

Pero la diferencia entre las iteraciones 4K y 8K para una probabilidad del 50% de afirmaciones muy apreciadas es 5,5 veces:

---------------------------------------------------------------------
Benchmark                              Time           CPU Iterations
---------------------------------------------------------------------
ordered_ifs/50/4                    4660 ns       4658 ns     150948
ordered_ifs/50/8                   25636 ns      25635 ns      27852

¿Por qué es así? Debido a la falta de predictores de rama. Aquí está la rama se pierde para cada caso mencionado anteriormente:

ordered_ifs/100/4    0.01% of branch-misses
ordered_ifs/100/8    0.01% of branch-misses
ordered_ifs/50/4     3.18% of branch-misses
ordered_ifs/50/8     15.22% of branch-misses

Entonces, en mi i5, el predictor de bifurcación falla espectacularmente para bifurcaciones poco probables y grandes conjuntos de datos.

3. Consejos ayudan un poco

Para las iteraciones 4K, los resultados son algo peores para una probabilidad del 50% y algo mejores para una probabilidad cercana al 100%:

---------------------------------------------------------------------
Benchmark                              Time           CPU Iterations
---------------------------------------------------------------------
ordered_ifs/50/4                    4660 ns       4658 ns     150948
ordered_ifs/100/4                   1673 ns       1673 ns     417073
ordered_ifs_with_hints/50/4         5551 ns       5551 ns     125160
ordered_ifs_with_hints/100/4        1575 ns       1575 ns     437687

Pero para las iteraciones de 8K, los resultados siempre son un poco mejores:

---------------------------------------------------------------------
Benchmark                              Time           CPU Iterations
---------------------------------------------------------------------
ordered_ifs/50/8                   25636 ns      25635 ns      27852
ordered_ifs/100/8                   3381 ns       3381 ns     207612
ordered_ifs_with_hints/50/8        23191 ns      23190 ns      30028
ordered_ifs_with_hints/100/8        3130 ns       3130 ns     221205

Por lo tanto, las sugerencias también ayudan, pero solo un poquito.

La conclusión general es: siempre compara el código, porque los resultados pueden sorprender.

Espero que ayude.

Andriy Berestovskyy
fuente
1
i5 Nehalem? i5 Skylake? Solo decir "i5" no es muy específico. Además, supongo que usaste g++ -O2o -O3 -fno-tree-vectorize, pero deberías decirlo.
Peter Cordes el
Es interesante que with_hints siga siendo diferente para ordenado vs. revertido. Sería bueno si se vinculara a la fuente en alguna parte. (por ejemplo, un enlace Godbolt, preferiblemente un enlace completo para que el acortamiento del enlace no se pudra.)
Peter Cordes
1
El hecho de que el predictor de bifurcación pueda predecir bien incluso en el tamaño de datos de entrada 4K, es decir, es capaz de "romper" el punto de referencia al recordar los resultados de bifurcación en un bucle con un período de miles es un testimonio del poder de los modernos predictores de rama. Tenga en cuenta que los predictores son bastante sensibles en algunos casos a cosas como la alineación, por lo que es difícil sacar conclusiones sólidas sobre algunos cambios. Por ejemplo, notó un comportamiento opuesto para la sugerencia en diferentes casos, pero podría explicarse por la sugerencia que cambia aleatoriamente el diseño del código que afectó al predictor.
BeeOnRope
1
@PeterCordes mi punto principal es que mientras podemos intentar predecir los resultados de un cambio, aún así medimos mejor el rendimiento antes y después del cambio ... Y tienes razón, debería haber mencionado que se optimizó con -O3 y el procesador es i5-4460 @ 3.20GHz
Andriy Berestovskyy
19

Basado en algunas de las otras respuestas aquí, parece que la única respuesta real es: depende . Depende al menos de lo siguiente (aunque no necesariamente en este orden de importancia):

  • Probabilidad relativa de cada rama. Esta es la pregunta original que se hizo. En base a las respuestas existentes, parece haber algunas condiciones bajo las cuales el pedido por probabilidad ayuda, pero parece que no siempre es así. Si las probabilidades relativas no son muy diferentes, entonces es poco probable que haga alguna diferencia en el orden en que se encuentran. Sin embargo, si la primera condición ocurre el 99.999% del tiempo y la siguiente es una fracción de lo que queda, entonces lo haría supongamos que poner el más probable primero sería beneficioso en términos de tiempo.
  • Costo de calcular la condición verdadera / falsa para cada rama. Si el costo de tiempo de probar las condiciones es realmente alto para una rama versus otra, entonces es probable que esto tenga un impacto significativo en el tiempo y la eficiencia. Por ejemplo, considere una condición que toma 1 unidad de tiempo para calcular (por ejemplo, verificar el estado de una variable booleana) versus otra condición que toma decenas, cientos, miles o incluso millones de unidades de tiempo para calcular (por ejemplo, verificar el contenido de un archivo en el disco o realizar una consulta SQL compleja en una base de datos grande). Suponiendo que el código verifique las condiciones en orden cada vez, las condiciones más rápidas probablemente deberían ser las primeras (a menos que dependan de que otras condiciones fallen primero).
  • Compilador / Intérprete Algunos compiladores (o intérpretes) pueden incluir optimizaciones de un tipo de otro que pueden afectar el rendimiento (y algunos de estos solo están presentes si se seleccionan ciertas opciones durante la compilación y / o ejecución). Entonces, a menos que esté comparando dos compilaciones y ejecuciones de código idéntico en el mismo sistema usando el mismo compilador exacto donde la única diferencia es el orden de las ramas en cuestión, tendrá que dar margen para las variaciones del compilador.
  • Sistema operativo / hardware Como mencionan luk32 y Yakk, varias CPU tienen sus propias optimizaciones (al igual que los sistemas operativos). Entonces, los puntos de referencia son nuevamente susceptibles de variación aquí.
  • Frecuencia de ejecución del bloque de código Si rara vez se accede al bloque que incluye las ramas (por ejemplo, solo una vez durante el inicio), entonces es muy poco importante el orden en que se colocan las ramas. Por otro lado, si su código está golpeando este bloque de código durante una parte crítica de su código, entonces el pedido puede ser muy importante (dependiendo de los puntos de referencia).

La única forma de saberlo con certeza es comparar su caso específico, preferiblemente en un sistema idéntico (o muy similar) al sistema previsto en el que finalmente se ejecutará el código. Si está destinado a ejecutarse en un conjunto de sistemas variables con hardware, sistema operativo, etc. diferente, entonces es una buena idea comparar con múltiples variaciones para ver cuál es el mejor. Incluso puede ser una buena idea que el código se compile con un pedido en un tipo de sistema y otro pedido en otro tipo de sistema.

Mi regla general personal (para la mayoría de los casos, en ausencia de un punto de referencia) es ordenar según:

  1. Condiciones que dependen del resultado de condiciones anteriores,
  2. Costo de calcular la condición, entonces
  3. Probabilidad relativa de cada rama.
Ampersat
fuente
13

La forma en que generalmente veo esto resuelto para el código de alto rendimiento es mantener el orden más legible, pero proporcionar pistas al compilador. Aquí hay un ejemplo del kernel de Linux :

if (likely(access_ok(VERIFY_READ, from, n))) {
    kasan_check_write(to, n);
    res = raw_copy_from_user(to, from, n);
}
if (unlikely(res))
    memset(to + (n - res), 0, res);

Aquí se supone que pasará la verificación de acceso y que no se devolverá ningún error res. Intentar reordenar cualquiera de estas cláusulas si solo confundiría el código, pero las macros likely()y unlikely()realmente ayudan a la legibilidad al señalar cuál es el caso normal y cuál es la excepción.

La implementación de Linux de esas macros utiliza características específicas de GCC . Parece que clang y el compilador Intel C admiten la misma sintaxis, pero MSVC no tiene esa característica .

jpa
fuente
44
Esto sería más útil si se pudiera explicar cómo el likely()y unlikely()se definen las macros, e incluir alguna información acerca de la característica del compilador correspondiente.
Nate Eldredge
1
AFAIK, estas sugerencias "solo" cambian el diseño de la memoria de los bloques de código y si un sí o un no conducirán a un salto. Esto puede tener ventajas de rendimiento, por ejemplo, por la necesidad (o falta de ella) de leer páginas de memoria. Pero esto no reorganiza el orden en el que se evalúan las condiciones dentro de una larga lista de otros si
Hagen von Eitzen
@HagenvonEitzen Hmm sí, ese es un buen punto, no puede afectar el orden de else ifsi el compilador no es lo suficientemente inteligente como para saber que las condiciones son mutuamente excluyentes.
jpa
7

También depende de su compilador y la plataforma para la que está compilando.

En teoría, la condición más probable debería hacer que el control salte lo menos posible.

Por lo general, la condición más probable debe ser primero:

if (most_likely) {
     // most likely instructions
} else 

Los asm más populares se basan en ramas condicionales que saltan cuando la condición es verdadera . Ese código C probablemente se traducirá a tal pseudoasm:

jump to ELSE if not(most_likely)
// most likely instructions
jump to end
ELSE:

Esto se debe a que los saltos hacen que la CPU cancele la canalización de ejecución y se bloquee porque el contador del programa cambió (para arquitecturas que admiten tuberías que son realmente comunes). Luego se trata del compilador, que puede o no aplicar algunas optimizaciones sofisticadas sobre tener la condición estadísticamente más probable para que el control haga menos saltos.

NoImaginationGuy
fuente
2
Usted declaró que la rama condicional se produce cuando la condición es verdadera, pero el ejemplo de "pseudo asm" muestra lo contrario. Además, no se puede decir que los saltos condicionales (mucho menos todos los saltos) se estanquen debido a que las CPU modernas suelen tener predicciones de ramificación. De hecho, si se predice que la rama se tomará pero no se tomará, la tubería se detendrá. Todavía trataría de ordenar las condiciones en orden descendente de probabilidad, pero lo que el compilador y la CPU hacen de él depende en gran medida de la implementación.
Arne Vogel
1
Pongo "no (más_ probable)", de modo que si más_ probable es cierto, el control continuará sin saltar.
NoImaginationGuy
1
"Los asm más populares se basan en ramas condicionales que saltan cuando la condición es verdadera" ... ¿cuáles ISA serían? Ciertamente no es cierto para x86 ni para ARM. Infierno para las CPU ARM básicas (y las muy antiguas x86, incluso para bps complejos, por lo general todavía comienzan con esa suposición y luego se adaptan), el predictor de rama asume que no se toma una rama hacia adelante y las ramas hacia atrás siempre lo son, por lo tanto, lo opuesto al reclamo es verdad.
Voo
1
La mayoría de los compiladores que probé utilizaron el enfoque que mencioné anteriormente para una prueba simple. Tenga en cuenta que clangen realidad tomó un enfoque diferente para test2y test3: a causa de la heurística que indican que una < 0o == 0prueba es probable que sea falsa, decidió clonar el resto de la función en ambos caminos, por lo que es capaz de hacer que la condition == falsede la caída a través del camino. Esto es factible solo porque el resto de la función es breve: test4agregué una operación más y volví al enfoque que describí anteriormente.
BeeOnRope
1
@ArneVogel - correctamente ramas tomadas predichos no Stall totalmente la tubería en las CPU modernas pero siguen siendo a menudo mucho peor que no tener: (1) que significa que el flujo de control no es contigua por lo que el resto de las instrucciones después de la jmpno son útil para desperdiciar / descodificar el ancho de banda (2) incluso con la predicción, los núcleos grandes modernos solo hacen una búsqueda por ciclo, por lo que pone un límite estricto de 1 rama / ciclo tomado (OTOH Intel moderno puede hacer 2 no tomados / ciclo) (3 ) es más difícil para la predicción de rama tratar con ramas consecutivas tomadas y en el caso de predictores rápidos + lentos ...
BeeOnRope
6

Decidí volver a ejecutar la prueba en mi propia máquina usando el código Lik32. Tuve que cambiarlo debido a que mi compilador o Windows pensaba que la alta resolución es de 1 ms, usando

mingw32-g ++. exe -O3 -Wall -std = c ++ 11 -fexceptions -g

vector<int> rand_vec(10000000);

GCC ha realizado la misma transformación en ambos códigos originales.

Tenga en cuenta que solo las dos primeras condiciones se prueban, ya que la tercera siempre debe ser cierta, GCC es una especie de Sherlock aquí.

Contrarrestar

.L233:
        mov     DWORD PTR [rsp+104], 0
        mov     DWORD PTR [rsp+100], 0
        mov     DWORD PTR [rsp+96], 0
        call    std::chrono::_V2::system_clock::now()
        mov     rbp, rax
        mov     rax, QWORD PTR [rsp+8]
        jmp     .L219
.L293:
        mov     edx, DWORD PTR [rsp+104]
        add     edx, 1
        mov     DWORD PTR [rsp+104], edx
.L217:
        add     rax, 4
        cmp     r14, rax
        je      .L292
.L219:
        mov     edx, DWORD PTR [rax]
        cmp     edx, 94
        jg      .L293 // >= 95
        cmp     edx, 19
        jg      .L218 // >= 20
        mov     edx, DWORD PTR [rsp+96]
        add     rax, 4
        add     edx, 1 // < 20 Sherlock
        mov     DWORD PTR [rsp+96], edx
        cmp     r14, rax
        jne     .L219
.L292:
        call    std::chrono::_V2::system_clock::now()

.L218: // further down
        mov     edx, DWORD PTR [rsp+100]
        add     edx, 1
        mov     DWORD PTR [rsp+100], edx
        jmp     .L217

And sorted

        mov     DWORD PTR [rsp+104], 0
        mov     DWORD PTR [rsp+100], 0
        mov     DWORD PTR [rsp+96], 0
        call    std::chrono::_V2::system_clock::now()
        mov     rbp, rax
        mov     rax, QWORD PTR [rsp+8]
        jmp     .L226
.L296:
        mov     edx, DWORD PTR [rsp+100]
        add     edx, 1
        mov     DWORD PTR [rsp+100], edx
.L224:
        add     rax, 4
        cmp     r14, rax
        je      .L295
.L226:
        mov     edx, DWORD PTR [rax]
        lea     ecx, [rdx-20]
        cmp     ecx, 74
        jbe     .L296
        cmp     edx, 19
        jle     .L297
        mov     edx, DWORD PTR [rsp+104]
        add     rax, 4
        add     edx, 1
        mov     DWORD PTR [rsp+104], edx
        cmp     r14, rax
        jne     .L226
.L295:
        call    std::chrono::_V2::system_clock::now()

.L297: // further down
        mov     edx, DWORD PTR [rsp+96]
        add     edx, 1
        mov     DWORD PTR [rsp+96], edx
        jmp     .L224

Entonces, esto no nos dice mucho, excepto que el último caso no necesita una predicción de rama.

Ahora probé las 6 combinaciones de los if, los 2 primeros son el inverso original y ordenados. alto es> = 95, bajo es <20, medio es 20-94 con 10000000 iteraciones cada uno.

high, low, mid: 43000000ns
mid, low, high: 46000000ns
high, mid, low: 45000000ns
low, mid, high: 44000000ns
mid, high, low: 46000000ns
low, high, mid: 44000000ns

high, low, mid: 44000000ns
mid, low, high: 47000000ns
high, mid, low: 44000000ns
low, mid, high: 45000000ns
mid, high, low: 46000000ns
low, high, mid: 45000000ns

high, low, mid: 43000000ns
mid, low, high: 47000000ns
high, mid, low: 44000000ns
low, mid, high: 45000000ns
mid, high, low: 46000000ns
low, high, mid: 44000000ns

high, low, mid: 42000000ns
mid, low, high: 46000000ns
high, mid, low: 46000000ns
low, mid, high: 45000000ns
mid, high, low: 46000000ns
low, high, mid: 43000000ns

high, low, mid: 43000000ns
mid, low, high: 47000000ns
high, mid, low: 44000000ns
low, mid, high: 44000000ns
mid, high, low: 46000000ns
low, high, mid: 44000000ns

high, low, mid: 43000000ns
mid, low, high: 48000000ns
high, mid, low: 44000000ns
low, mid, high: 44000000ns
mid, high, low: 45000000ns
low, high, mid: 45000000ns

high, low, mid: 43000000ns
mid, low, high: 47000000ns
high, mid, low: 45000000ns
low, mid, high: 45000000ns
mid, high, low: 46000000ns
low, high, mid: 44000000ns

high, low, mid: 43000000ns
mid, low, high: 47000000ns
high, mid, low: 45000000ns
low, mid, high: 45000000ns
mid, high, low: 46000000ns
low, high, mid: 44000000ns

high, low, mid: 43000000ns
mid, low, high: 46000000ns
high, mid, low: 45000000ns
low, mid, high: 45000000ns
mid, high, low: 45000000ns
low, high, mid: 44000000ns

high, low, mid: 42000000ns
mid, low, high: 46000000ns
high, mid, low: 44000000ns
low, mid, high: 45000000ns
mid, high, low: 45000000ns
low, high, mid: 44000000ns

1900020, 7498968, 601012

Process returned 0 (0x0)   execution time : 2.899 s
Press any key to continue.

Entonces, ¿por qué el orden es alto, bajo, medio y luego más rápido (marginalmente)

Porque lo más impredecible es el último y, por lo tanto, nunca se ejecuta a través de un predictor de rama.

          if (i >= 95) ++nHigh;               // most predictable with 94% taken
          else if (i < 20) ++nLow; // (94-19)/94% taken ~80% taken
          else if (i >= 20 && i < 95) ++nMid; // never taken as this is the remainder of the outfalls.

Entonces las ramas serán predichas tomadas, tomadas y el resto con

6% + (0.94 *) 20% de predicciones erróneas.

"Ordenado"

          if (i >= 20 && i < 95) ++nMid;  // 75% not taken
          else if (i < 20) ++nLow;        // 19/25 76% not taken
          else if (i >= 95) ++nHigh;      //Least likely branch

Las ramas serán predichas con no tomado, no tomado y Sherlock.

25% + (0.75 *) 24% predicciones erróneas

Dando una diferencia del 18-23% (diferencia medida de ~ 9%) pero necesitamos calcular ciclos en lugar de predecir erróneamente el%.

Supongamos una penalización de predicción errónea de 17 ciclos en mi CPU Nehalem y que cada verificación demora 1 ciclo en emitirse (4-5 instrucciones) y el ciclo también toma un ciclo. Las dependencias de datos son los contadores y las variables de bucle, pero una vez que las predicciones erróneas están fuera del camino, no debería influir en el tiempo.

Entonces, para "reversa", obtenemos los tiempos (esta debería ser la fórmula utilizada en Computer Architecture: A Quantitative Approach IIRC).

mispredict*penalty+count+loop
0.06*17+1+1+    (=3.02)
(propability)*(first check+mispredict*penalty+count+loop)
(0.19)*(1+0.20*17+1+1)+  (= 0.19*6.4=1.22)
(propability)*(first check+second check+count+loop)
(0.75)*(1+1+1+1) (=3)
= 7.24 cycles per iteration

y lo mismo para "ordenado"

0.25*17+1+1+ (=6.25)
(1-0.75)*(1+0.24*17+1+1)+ (=.25*7.08=1.77)
(1-0.75-0.19)*(1+1+1+1)  (= 0.06*4=0.24)
= 8.26

(8.26-7.24) /8.26 = 13.8% vs. ~ 9% medido (¡cerca del medido!?!).

Entonces, lo obvio del OP no es obvio.

Con estas pruebas, otras pruebas con código más complicado o más dependencias de datos serán diferentes, así que mida su caso.

Cambiar el orden de la prueba cambió los resultados, pero eso podría deberse a diferentes alineamientos del inicio del bucle, que idealmente deberían estar alineados a 16 bytes en todas las CPU Intel más nuevas, pero no en este caso.

Surt
fuente
4

Póngalos en el orden lógico que desee. Claro, la ramificación puede ser más lenta, pero la ramificación no debería ser la mayoría del trabajo que está haciendo su computadora.

Si está trabajando en una porción de código de rendimiento crítico, entonces ciertamente use el orden lógico, la optimización guiada por el perfil y otras técnicas, pero para el código general, creo que es más una elección estilística.

Jack
fuente
66
Las fallas de predicción de sucursales son caras. En microbenchmarks, tienen un costo bajo , porque los x86 tienen una gran tabla de predictores de ramificación. Un ciclo cerrado en las mismas condiciones hace que la CPU sepa mejor que tú cuál es la más probable. Pero si tiene ramas en todo el código, puede hacer que su caché de predicción de ramas se quede sin ranuras, y la CPU asume lo que sea predeterminado. Saber cuál es esa suposición predeterminada puede ahorrar ciclos en toda su base de código.
Yakk - Adam Nevraumont el
La respuesta de @Yakk Jack es la única correcta aquí. No haga optimizaciones que reduzcan la legibilidad si su compilador puede hacer esa optimización. No haría un plegado constante, eliminación de código muerto, desenrollado de bucle o cualquier otra optimización si su compilador lo hace por usted, ¿verdad? Escriba su código, use la optimización guiada por perfil (que está diseñada para resolver este problema porque los codificadores apestan al adivinar) y luego vea si su compilador lo optimiza o no. Al final, no desea tener ninguna ramificación en el código crítico de rendimiento de todos modos.
Christoph Diegelmann
@ Christoph No incluiría el código que sabía que estaba muerto. No usaría i++cuándo ++ilo haría, porque soy consciente de que i++para algunos iteradores es difícil optimizarlo ++iy la diferencia (para mí) no importa. Se trata de evitar la pesimismo; poner el bloque más probable primero como un hábito predeterminado no causará una reducción notable de legibilidad (¡y en realidad podría ayudar!), al tiempo que da como resultado un código que es amigable para la predicción de ramas (y por lo tanto le brinda un pequeño aumento uniforme de rendimiento que no se puede recuperar) por micro optimización posterior)
Yakk - Adam Nevraumont
3

Si ya conoce la probabilidad relativa de la declaración if-else, entonces, para fines de rendimiento, sería mejor usar la forma ordenada, ya que solo verificará una condición (la verdadera).

De manera no ordenada, el compilador verificará todas las condiciones innecesariamente y llevará tiempo.

aditya rawat
fuente