¿Por qué procesar una matriz ordenada es más rápido que procesar una matriz no ordenada?

24454

Aquí hay un fragmento de código C ++ que muestra un comportamiento muy peculiar. Por alguna extraña razón, ordenar los datos milagrosamente hace que el código sea casi seis veces más rápido:

#include <algorithm>
#include <ctime>
#include <iostream>

int main()
{
    // Generate data
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;

    // !!! With this, the next loop runs faster.
    std::sort(data, data + arraySize);

    // Test
    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i)
    {
        // Primary loop
        for (unsigned c = 0; c < arraySize; ++c)
        {
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << std::endl;
    std::cout << "sum = " << sum << std::endl;
}
  • Sin std::sort(data, data + arraySize);, el código se ejecuta en 11.54 segundos.
  • Con los datos ordenados, el código se ejecuta en 1.93 segundos.

Inicialmente, pensé que esto podría ser solo una anomalía de lenguaje o compilador, así que probé Java:

import java.util.Arrays;
import java.util.Random;

public class Main
{
    public static void main(String[] args)
    {
        // Generate data
        int arraySize = 32768;
        int data[] = new int[arraySize];

        Random rnd = new Random(0);
        for (int c = 0; c < arraySize; ++c)
            data[c] = rnd.nextInt() % 256;

        // !!! With this, the next loop runs faster
        Arrays.sort(data);

        // Test
        long start = System.nanoTime();
        long sum = 0;

        for (int i = 0; i < 100000; ++i)
        {
            // Primary loop
            for (int c = 0; c < arraySize; ++c)
            {
                if (data[c] >= 128)
                    sum += data[c];
            }
        }

        System.out.println((System.nanoTime() - start) / 1000000000.0);
        System.out.println("sum = " + sum);
    }
}

Con un resultado similar pero menos extremo.


Mi primer pensamiento fue que la clasificación lleva los datos al caché, pero luego pensé lo tonto que era porque la matriz acababa de generarse.

  • Que esta pasando?
  • ¿Por qué procesar una matriz ordenada es más rápido que procesar una matriz no ordenada?

El código está resumiendo algunos términos independientes, por lo que el orden no debería importar.

GManNickG
fuente
16
@SachinVerma Fuera de mi cabeza: 1) La JVM podría ser finalmente lo suficientemente inteligente como para usar movimientos condicionales. 2) El código está vinculado a la memoria. 200M es demasiado grande para caber en la memoria caché de la CPU. Por lo tanto, el rendimiento se verá afectado por el ancho de banda de la memoria en lugar de la ramificación.
Mysticial
12
@ Mysticial, alrededor de 2). Pensé que la tabla de predicción realiza un seguimiento de los patrones (independientemente de las variables reales que se verificaron para ese patrón) y cambia la salida de predicción en función del historial. ¿Podría darme una razón, por qué una matriz súper grande no se beneficiaría de la predicción de rama?
Sachin Verma
15
@SachinVerma Lo hace, pero cuando la matriz es tan grande, probablemente entra en juego un factor aún mayor: el ancho de banda de la memoria. La memoria no es plana . El acceso a la memoria es muy lento y hay una cantidad limitada de ancho de banda. Para simplificar demasiado las cosas, solo se pueden transferir tantos bytes entre la CPU y la memoria en un período de tiempo fijo. Un código simple como el de esta pregunta probablemente alcanzará ese límite, incluso si las predicciones erróneas lo ralentizan. Esto no sucede con una matriz de 32768 (128 KB) porque cabe en el caché L2 de la CPU.
Mysticial
13
Hay una nueva falla de seguridad llamada BranchScope: cs.ucr.edu/~nael/pubs/asplos18.pdf
Veve

Respuestas:

31801

Eres víctima de una falla de predicción de rama .


¿Qué es la predicción de rama?

Considere un cruce de ferrocarril:

Imagen que muestra un cruce de ferrocarril Imagen de Mecanismo, vía Wikimedia Commons. Usado bajo la licencia CC-By-SA 3.0 .

Ahora, en aras de la discusión, supongamos que esto ocurre en el siglo XIX, antes de la comunicación a larga distancia o por radio.

Eres el operador de un cruce y escuchas que viene un tren. No tienes idea en qué dirección se supone que debe ir. Usted detiene el tren para preguntarle al conductor qué dirección quiere. Y luego configura el interruptor adecuadamente.

Los trenes son pesados ​​y tienen mucha inercia. Por eso tardan una eternidad en comenzar y reducir la velocidad.

¿Hay una mejor manera? ¡Adivina en qué dirección irá el tren!

  • Si acertó, continúa.
  • Si adivinaste mal, el capitán se detendrá, retrocederá y te gritará que actives el interruptor. Entonces puede reiniciar por la otra ruta.

Si aciertas siempre , el tren nunca tendrá que detenerse.
Si adivina mal con demasiada frecuencia , el tren pasará mucho tiempo deteniéndose, retrocediendo y reiniciando.


Considere una declaración if: a nivel de procesador, es una instrucción de bifurcación:

Captura de pantalla del código compilado que contiene una instrucción if

Eres un procesador y ves una rama. No tienes idea de qué camino tomará. ¿Qué haces? Detiene la ejecución y espera hasta que se completen las instrucciones anteriores. Luego continúas por el camino correcto.

Los procesadores modernos son complicados y tienen tuberías largas. Por eso tardan una eternidad en "calentarse" y "reducir la velocidad".

¿Hay una mejor manera? ¡Adivina en qué dirección irá la rama!

  • Si acertó, continúa ejecutando.
  • Si adivinó mal, debe vaciar la tubería y volver a la rama. Luego puede reiniciar por la otra ruta.

Si aciertas siempre , la ejecución nunca tendrá que detenerse.
Si adivina mal con demasiada frecuencia , pasa mucho tiempo deteniéndose, retrocediendo y reiniciando.


Esta es la predicción de rama. Admito que no es la mejor analogía ya que el tren podría señalar la dirección con una bandera. Pero en las computadoras, el procesador no sabe en qué dirección irá una rama hasta el último momento.

Entonces, ¿cómo adivinaría estratégicamente para minimizar la cantidad de veces que el tren debe retroceder y seguir el otro camino? ¡Miras la historia pasada! Si el tren sale a la izquierda el 99% del tiempo, entonces supones que se fue. Si alterna, entonces alterna sus conjeturas. Si va en una dirección cada tres veces, adivina lo mismo ...

En otras palabras, intenta identificar un patrón y seguirlo. Así es más o menos cómo funcionan los predictores de rama.

La mayoría de las aplicaciones tienen ramas con buen comportamiento. Por lo tanto, los predictores de sucursales modernos generalmente alcanzarán tasas de éxito> 90%. Pero cuando se enfrentan con ramas impredecibles sin patrones reconocibles, los predictores de ramas son prácticamente inútiles.

Lectura adicional: artículo "Predictor de rama" en Wikipedia .


Como se insinuó desde arriba, el culpable es esta declaración if:

if (data[c] >= 128)
    sum += data[c];

Observe que los datos se distribuyen uniformemente entre 0 y 255. Cuando se ordenan los datos, aproximadamente la primera mitad de las iteraciones no ingresará la instrucción if. Después de eso, todos ingresarán la declaración if.

Esto es muy amigable para el predictor de rama ya que la rama va consecutivamente en la misma dirección muchas veces. Incluso un simple contador de saturación predecirá correctamente la rama, excepto por las pocas iteraciones después de que cambie de dirección.

Visualización rápida:

T = branch taken
N = branch not taken

data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
branch = N  N  N  N  N  ...   N    N    T    T    T  ...   T    T    T  ...

       = NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT  (easy to predict)

Sin embargo, cuando los datos son completamente aleatorios, el predictor de rama se vuelve inútil, porque no puede predecir datos aleatorios. Por lo tanto, probablemente habrá alrededor del 50% de predicción errónea (no es mejor que adivinar al azar).

data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118,  14, 150, 177, 182, 133, ...
branch =   T,   T,   N,   T,   T,   T,   T,  N,   T,   N,   N,   T,   T,   T,   N  ...

       = TTNTTTTNTNNTTTN ...   (completely random - hard to predict)

Entonces, ¿qué puede hacerse?

Si el compilador no puede optimizar la rama en un movimiento condicional, puede probar algunos hacks si está dispuesto a sacrificar la legibilidad por el rendimiento.

Reemplazar:

if (data[c] >= 128)
    sum += data[c];

con:

int t = (data[c] - 128) >> 31;
sum += ~t & data[c];

Esto elimina la rama y la reemplaza con algunas operaciones bit a bit.

(Tenga en cuenta que este truco no es estrictamente equivalente a la instrucción if original. Pero en este caso, es válido para todos los valores de entrada de data[]).

Puntos de referencia: Core i7 920 @ 3.5 GHz

C ++ - Visual Studio 2010 - Lanzamiento x64

//  Branch - Random
seconds = 11.777

//  Branch - Sorted
seconds = 2.352

//  Branchless - Random
seconds = 2.564

//  Branchless - Sorted
seconds = 2.587

Java - NetBeans 7.1.1 JDK 7 - x64

//  Branch - Random
seconds = 10.93293813

//  Branch - Sorted
seconds = 5.643797077

//  Branchless - Random
seconds = 3.113581453

//  Branchless - Sorted
seconds = 3.186068823

Observaciones:

  • Con la rama: existe una gran diferencia entre los datos ordenados y no clasificados.
  • Con el Hack: no hay diferencia entre los datos ordenados y no clasificados.
  • En el caso de C ++, el pirateo es en realidad un poco más lento que con la rama cuando se ordenan los datos.

Una regla general es evitar la ramificación dependiente de los datos en los bucles críticos (como en este ejemplo).


Actualizar:

  • GCC 4.6.1 con -O3o -ftree-vectorizeen x64 es capaz de generar un movimiento condicional. Por lo tanto, no hay diferencia entre los datos ordenados y no clasificados, ambos son rápidos.

    (O algo rápido: para el caso ya ordenado, cmovpuede ser más lento, especialmente si GCC lo coloca en la ruta crítica en lugar de solo add, especialmente en Intel antes de Broadwell, donde cmovtiene latencia de 2 ciclos: el indicador de optimización de gcc -O3 hace que el código sea más lento que -O2 )

  • VC ++ 2010 no puede generar movimientos condicionales para esta rama incluso debajo /Ox.

  • Intel C ++ Compiler (ICC) 11 hace algo milagroso. Se intercambia los dos bucles , el izado de este modo la rama impredecible para el bucle externo. Entonces, no solo es inmune a las predicciones erróneas, ¡también es dos veces más rápido que lo que puedan generar VC ++ y GCC! En otras palabras, ICC aprovechó el bucle de prueba para vencer el punto de referencia ...

  • Si le da al compilador Intel el código sin bifurcación, simplemente lo vectoriza a la derecha ... y es tan rápido como con la bifurcación (con el intercambio de bucle).

Esto demuestra que incluso los compiladores modernos maduros pueden variar enormemente en su capacidad para optimizar el código ...

Místico
fuente
256
Eche un vistazo a esta pregunta de seguimiento: stackoverflow.com/questions/11276291/… El Compilador Intel estuvo muy cerca de deshacerse por completo del bucle externo.
Mysticial
24
@Mysticial ¿Cómo sabe el tren / compilador que ha entrado en el camino equivocado?
onmyway133
26
@obe: Dadas las estructuras de memoria jerárquicas, es imposible decir cuál será el costo de una pérdida de caché. Puede fallar en L1 y resolverse en L2 más lento, o fallar en L3 y resolverse en la memoria del sistema. Sin embargo, a menos que por alguna extraña razón esta falta de memoria caché provoque que la memoria en una página no residente se cargue desde el disco, tiene un buen punto ... la memoria no ha tenido tiempo de acceso en el rango de milisegundos en aproximadamente 25-30 años ;)
Andon M. Coleman
21
Regla general para escribir código que sea eficiente en un procesador moderno: todo lo que hace que la ejecución de su programa sea más regular (menos desigual) tenderá a hacerlo más eficiente. La ordenación en este ejemplo tiene este efecto debido a la predicción de rama. La localidad de acceso (en lugar de los accesos aleatorios a lo largo y ancho) tiene este efecto debido a los cachés.
Lutz Prechelt
22
@Sandeep Sí. Los procesadores todavía tienen predicción de rama. Si algo ha cambiado, son los compiladores. Hoy en día, apuesto a que es más probable que hagan lo que hicieron ICC y GCC (bajo -O3) aquí, es decir, eliminar la rama. Dado el alto perfil de esta pregunta, es muy posible que los compiladores se hayan actualizado para manejar específicamente el caso en esta pregunta. Definitivamente prestan atención a SO. Y sucedió en esta pregunta donde GCC se actualizó en 3 semanas. No veo por qué no sucedería aquí también.
Mysticial
4087

Predicción de rama.

Con una matriz ordenada, la condición data[c] >= 128es primero falsepara una raya de valores, luego se convierte truepara todos los valores posteriores. Eso es fácil de predecir. Con una matriz sin clasificar, paga el costo de ramificación.

Daniel Fischer
fuente
105
¿Funciona mejor la predicción de ramificaciones en matrices ordenadas que en matrices con diferentes patrones? Por ejemplo, para la matriz -> {10, 5, 20, 10, 40, 20, ...} el siguiente elemento en la matriz del patrón es 80. ¿Se aceleraría este tipo de matriz mediante la predicción de rama en ¿cuál es el siguiente elemento 80 aquí si se sigue el patrón? ¿O generalmente solo ayuda con arreglos ordenados?
Adam Freeman el
133
Entonces, ¿básicamente todo lo que aprendí convencionalmente sobre big-O está fuera de la ventana? ¿Es mejor incurrir en un costo de clasificación que un costo de ramificación?
Agrim Pathak
133
@AgrimPathak Eso depende. Para entradas no demasiado grandes, un algoritmo con mayor complejidad es más rápido que un algoritmo con menor complejidad cuando las constantes son más pequeñas para el algoritmo con mayor complejidad. El punto de equilibrio es difícil de predecir. Además, compare esto , la localidad es importante. Big-O es importante, pero no es el único criterio de rendimiento.
Daniel Fischer
65
¿Cuándo tiene lugar la predicción de rama? ¿Cuándo sabrá el lenguaje que la matriz está ordenada? Estoy pensando en una situación de matriz que se parece a: [1,2,3,4,5, ... 998,999,1000, 3, 10001, 10002]? ¿Este oscuro 3 aumentará el tiempo de ejecución? ¿Será tan largo como una matriz sin clasificar?
Filip Bartuzi
63
La predicción de @FilipBartuzi Branch se lleva a cabo en el procesador, por debajo del nivel de idioma (pero el idioma puede ofrecer formas de decirle al compilador qué es probable, para que el compilador pueda emitir código adecuado para eso). En su ejemplo, el 3 fuera de servicio conducirá a una predicción errónea de la rama (para condiciones apropiadas, donde 3 da un resultado diferente que 1000), y por lo tanto, procesar esa matriz probablemente tomará un par de docenas o cien nanosegundos más de un matriz ordenada, casi nunca se nota. Lo que cuesta tiempo es una alta tasa de predicciones erróneas, una predicción errónea por 1000 no es mucho.
Daniel Fischer
3312

La razón por la cual el rendimiento mejora drásticamente cuando se ordenan los datos es que se elimina la penalización de predicción de rama, como se explica maravillosamente en la respuesta de Mysticial .

Ahora, si miramos el código

if (data[c] >= 128)
    sum += data[c];

podemos encontrar que el significado de esta if... else...rama en particular es agregar algo cuando se cumple una condición. Este tipo de rama se puede transformar fácilmente en una instrucción de movimiento condicional , que se compilaría en una instrucción de movimiento condicional: cmovlen un x86sistema. Se elimina la rama y, por lo tanto, la posible penalización de predicción de rama.

En C, por lo tanto C++, la declaración, que se compilaría directamente (sin ninguna optimización) en la instrucción de movimiento condicional x86, es el operador ternario ... ? ... : .... Entonces reescribimos la declaración anterior en una equivalente:

sum += data[c] >=128 ? data[c] : 0;

Mientras mantenemos la legibilidad, podemos verificar el factor de aceleración.

En un Intel Core i7 -2600K @ 3.4 GHz y Visual Studio 2010 Release Mode, el punto de referencia es (formato copiado de Mysticial):

x86

//  Branch - Random
seconds = 8.885

//  Branch - Sorted
seconds = 1.528

//  Branchless - Random
seconds = 3.716

//  Branchless - Sorted
seconds = 3.71

x64

//  Branch - Random
seconds = 11.302

//  Branch - Sorted
 seconds = 1.830

//  Branchless - Random
seconds = 2.736

//  Branchless - Sorted
seconds = 2.737

El resultado es robusto en múltiples pruebas. Obtenemos una gran aceleración cuando el resultado de la rama es impredecible, pero sufrimos un poco cuando es predecible. De hecho, cuando se usa un movimiento condicional, el rendimiento es el mismo independientemente del patrón de datos.

Ahora echemos un vistazo más de cerca al investigar el x86ensamblaje que generan. Para simplificar, usamos dos funciones max1y max2.

max1usa la rama condicional if... else ...:

int max1(int a, int b) {
    if (a > b)
        return a;
    else
        return b;
}

max2usa el operador ternario ... ? ... : ...:

int max2(int a, int b) {
    return a > b ? a : b;
}

En una máquina x86-64, GCC -Sgenera el siguiente ensamblaje.

:max1
    movl    %edi, -4(%rbp)
    movl    %esi, -8(%rbp)
    movl    -4(%rbp), %eax
    cmpl    -8(%rbp), %eax
    jle     .L2
    movl    -4(%rbp), %eax
    movl    %eax, -12(%rbp)
    jmp     .L4
.L2:
    movl    -8(%rbp), %eax
    movl    %eax, -12(%rbp)
.L4:
    movl    -12(%rbp), %eax
    leave
    ret

:max2
    movl    %edi, -4(%rbp)
    movl    %esi, -8(%rbp)
    movl    -4(%rbp), %eax
    cmpl    %eax, -8(%rbp)
    cmovge  -8(%rbp), %eax
    leave
    ret

max2usa mucho menos código debido al uso de instrucciones cmovge. Pero la ganancia real es que max2no implica saltos de rama jmp, lo que tendría una penalización de rendimiento significativa si el resultado predicho no es correcto.

Entonces, ¿por qué un movimiento condicional funciona mejor?

En un x86procesador típico , la ejecución de una instrucción se divide en varias etapas. Aproximadamente, tenemos hardware diferente para lidiar con diferentes etapas. Por lo tanto, no tenemos que esperar a que termine una instrucción para comenzar una nueva. Esto se llama tubería .

En un caso derivado, la siguiente instrucción está determinada por la precedente, por lo que no podemos hacer la canalización. Tenemos que esperar o predecir.

En un caso de movimiento condicional, la instrucción de movimiento condicional de ejecución se divide en varias etapas, pero a las etapas anteriores les gusta Fetchy Decodeno dependen del resultado de la instrucción anterior; solo las últimas etapas necesitan el resultado. Por lo tanto, esperamos una fracción del tiempo de ejecución de una instrucción. Es por eso que la versión de movimiento condicional es más lenta que la rama cuando la predicción es fácil.

El libro Computer Systems: A Programmer's Perspective, segunda edición, explica esto en detalle. Puede consultar la Sección 3.6.6 para ver las Instrucciones de movimiento condicional , el Capítulo 4 completo para la Arquitectura del procesador y la Sección 5.11.2 para obtener un tratamiento especial para las Penalizaciones de predicción de rama y de predicción errónea .

A veces, algunos compiladores modernos pueden optimizar nuestro código para ensamblar con un mejor rendimiento, a veces algunos compiladores no pueden (el código en cuestión está usando el compilador nativo de Visual Studio). Conocer la diferencia de rendimiento entre la rama y el movimiento condicional cuando es impredecible puede ayudarnos a escribir código con un mejor rendimiento cuando el escenario se vuelve tan complejo que el compilador no puede optimizarlos automáticamente.

WiSaGaN
fuente
77
@ BlueRaja-DannyPflughoeft Esta es la versión no optimizada. El compilador NO optimizó el operador ternario, simplemente lo TRADUCE. GCC puede optimizar si-entonces si se le da un nivel de optimización suficiente, sin embargo, este muestra el poder del movimiento condicional, y la optimización manual hace la diferencia.
WiSaGaN
100
@WiSaGaN El código no muestra nada, porque sus dos piezas de código se compilan en el mismo código de máquina. Es de vital importancia que las personas no tengan la idea de que de alguna manera la declaración if en su ejemplo es diferente de la terenaria en su ejemplo. Es cierto que reconoce la similitud en su último párrafo, pero eso no borra el hecho de que el resto del ejemplo es perjudicial.
Justin L.
55
@WiSaGaN Mi voto negativo definitivamente se convertiría en un voto positivo si modificara su respuesta para eliminar el -O0ejemplo engañoso y mostrar la diferencia en el asm optimizado en sus dos casos de prueba.
Justin L.
56
@UpAndAdam En el momento de la prueba, VS2010 no puede optimizar la rama original en un movimiento condicional, incluso cuando se especifica un alto nivel de optimización, mientras que gcc sí.
WiSaGaN
99
Este truco de operador ternario funciona muy bien para Java. Después de leer la respuesta de Mystical, me preguntaba qué se podría hacer para que Java evite la predicción de rama falsa ya que Java no tiene nada equivalente a -O3. operador ternario: 2.1943s y original: 6.0303s.
Kin Cheung
2272

Si tiene curiosidad sobre aún más optimizaciones que se pueden hacer a este código, considere esto:

Comenzando con el bucle original:

for (unsigned i = 0; i < 100000; ++i)
{
    for (unsigned j = 0; j < arraySize; ++j)
    {
        if (data[j] >= 128)
            sum += data[j];
    }
}

Con el intercambio de bucles, podemos cambiar este bucle de manera segura a:

for (unsigned j = 0; j < arraySize; ++j)
{
    for (unsigned i = 0; i < 100000; ++i)
    {
        if (data[j] >= 128)
            sum += data[j];
    }
}

Luego, puede ver que el ifcondicional es constante durante la ejecución del ibucle, por lo que puede izar la ifsalida:

for (unsigned j = 0; j < arraySize; ++j)
{
    if (data[j] >= 128)
    {
        for (unsigned i = 0; i < 100000; ++i)
        {
            sum += data[j];
        }
    }
}

Luego, verá que el bucle interno se puede contraer en una sola expresión, suponiendo que el modelo de coma flotante lo permita ( /fp:fastse lanza, por ejemplo)

for (unsigned j = 0; j < arraySize; ++j)
{
    if (data[j] >= 128)
    {
        sum += data[j] * 100000;
    }
}

Ese es 100,000 veces más rápido que antes.

cuervo vulcano
fuente
276
Si quieres hacer trampa, también puedes sacar la multiplicación fuera del ciclo y sumar * = 100000 después del ciclo.
Jyaif
78
@Michael: creo que este ejemplo es en realidad un ejemplo de optimización de elevación de bucle invariante (LIH) y NO un intercambio de bucle . En este caso, todo el bucle interno es independiente del bucle externo y, por lo tanto, se puede izar fuera del bucle externo, por lo que el resultado simplemente se multiplica por una suma ide una unidad = 1e5. No importa el resultado final, pero solo quería dejar las cosas claras ya que esta es una página tan frecuentada.
Yair Altman
54
Aunque no en el simple espíritu de intercambiar bucles, lo interno ifen este punto podría convertirse en: lo sum += (data[j] >= 128) ? data[j] * 100000 : 0;que el compilador puede reducir cmovgeo equivalente.
Alex North-Keys
43
El bucle externo es para hacer que el tiempo que toma el bucle interno sea lo suficientemente grande como para perfilarse. Entonces, ¿por qué cambiarías de bucle? Al final, ese bucle se eliminará de todos modos.
saurabheights
34
@saurabheights: Pregunta incorrecta: ¿por qué el compilador NO debería intercambiar bucles? Microbenchmarks es difícil;)
Matthieu M.
1885

Sin duda, algunos de nosotros estaríamos interesados ​​en formas de identificar código que sea problemático para el predictor de rama de la CPU. La herramienta Valgrind cachegrindtiene un simulador de predicción de rama, habilitado mediante el uso de la --branch-sim=yesbandera. Ejecutarlo sobre los ejemplos en esta pregunta, con el número de bucles externos reducidos a 10000 y compilados g++, da estos resultados:

Ordenados:

==32551== Branches:        656,645,130  (  656,609,208 cond +    35,922 ind)
==32551== Mispredicts:         169,556  (      169,095 cond +       461 ind)
==32551== Mispred rate:            0.0% (          0.0%     +       1.2%   )

Sin clasificar:

==32555== Branches:        655,996,082  (  655,960,160 cond +  35,922 ind)
==32555== Mispredicts:     164,073,152  (  164,072,692 cond +     460 ind)
==32555== Mispred rate:           25.0% (         25.0%     +     1.2%   )

Profundizando en la salida línea por línea producida por cg_annotateel bucle en cuestión:

Ordenados:

          Bc    Bcm Bi Bim
      10,001      4  0   0      for (unsigned i = 0; i < 10000; ++i)
           .      .  .   .      {
           .      .  .   .          // primary loop
 327,690,000 10,016  0   0          for (unsigned c = 0; c < arraySize; ++c)
           .      .  .   .          {
 327,680,000 10,006  0   0              if (data[c] >= 128)
           0      0  0   0                  sum += data[c];
           .      .  .   .          }
           .      .  .   .      }

Sin clasificar:

          Bc         Bcm Bi Bim
      10,001           4  0   0      for (unsigned i = 0; i < 10000; ++i)
           .           .  .   .      {
           .           .  .   .          // primary loop
 327,690,000      10,038  0   0          for (unsigned c = 0; c < arraySize; ++c)
           .           .  .   .          {
 327,680,000 164,050,007  0   0              if (data[c] >= 128)
           0           0  0   0                  sum += data[c];
           .           .  .   .          }
           .           .  .   .      }

Esto le permite identificar fácilmente la línea problemática: en la versión no ordenada, la if (data[c] >= 128)línea está causando 164.050.007 ramas condicionales mal predichas ( Bcm) bajo el modelo de predicción de ramas de cachegrind, mientras que solo está causando 10.006 en la versión ordenada.


Alternativamente, en Linux puede usar el subsistema de contadores de rendimiento para realizar la misma tarea, pero con rendimiento nativo usando contadores de CPU.

perf stat ./sumtest_sorted

Ordenados:

 Performance counter stats for './sumtest_sorted':

  11808.095776 task-clock                #    0.998 CPUs utilized          
         1,062 context-switches          #    0.090 K/sec                  
            14 CPU-migrations            #    0.001 K/sec                  
           337 page-faults               #    0.029 K/sec                  
26,487,882,764 cycles                    #    2.243 GHz                    
41,025,654,322 instructions              #    1.55  insns per cycle        
 6,558,871,379 branches                  #  555.455 M/sec                  
       567,204 branch-misses             #    0.01% of all branches        

  11.827228330 seconds time elapsed

Sin clasificar:

 Performance counter stats for './sumtest_unsorted':

  28877.954344 task-clock                #    0.998 CPUs utilized          
         2,584 context-switches          #    0.089 K/sec                  
            18 CPU-migrations            #    0.001 K/sec                  
           335 page-faults               #    0.012 K/sec                  
65,076,127,595 cycles                    #    2.253 GHz                    
41,032,528,741 instructions              #    0.63  insns per cycle        
 6,560,579,013 branches                  #  227.183 M/sec                  
 1,646,394,749 branch-misses             #   25.10% of all branches        

  28.935500947 seconds time elapsed

También puede hacer anotaciones de código fuente con desmontaje.

perf record -e branch-misses ./sumtest_unsorted
perf annotate -d sumtest_unsorted
 Percent |      Source code & Disassembly of sumtest_unsorted
------------------------------------------------
...
         :                      sum += data[c];
    0.00 :        400a1a:       mov    -0x14(%rbp),%eax
   39.97 :        400a1d:       mov    %eax,%eax
    5.31 :        400a1f:       mov    -0x20040(%rbp,%rax,4),%eax
    4.60 :        400a26:       cltq   
    0.00 :        400a28:       add    %rax,-0x30(%rbp)
...

Vea el tutorial de rendimiento para más detalles.

coste y flete
fuente
74
Esto da miedo, en la lista sin clasificar, debería haber un 50% de posibilidades de llegar al complemento. De alguna manera, la predicción de la rama solo tiene una tasa de fallas del 25%, ¿cómo puede ser mejor que una falla del 50%?
TallBrian
128
@ tall.b.lo: el 25% es de todas las ramas: hay dos ramas en el bucle, una para data[c] >= 128(que tiene una tasa de fallas del 50% como sugiere) y otra para la condición del bucle c < arraySizeque tiene una tasa de fallas de ~ 0% .
caf
1341

Acabo de leer sobre esta pregunta y sus respuestas, y siento que falta una respuesta.

Una forma común de eliminar la predicción de rama que he encontrado que funciona particularmente bien en lenguajes administrados es buscar una tabla en lugar de usar una rama (aunque no lo he probado en este caso).

Este enfoque funciona en general si:

  1. es una tabla pequeña y es probable que se almacene en caché en el procesador, y
  2. está ejecutando cosas en un circuito bastante cerrado y / o el procesador puede precargar los datos.

Antecedentes y por qué

Desde la perspectiva del procesador, su memoria es lenta. Para compensar la diferencia de velocidad, hay un par de cachés integrados en su procesador (caché L1 / L2). Así que imagine que está haciendo sus buenos cálculos y descubra que necesita un pedazo de memoria. El procesador realizará su operación de 'carga' y cargará la memoria en el caché, y luego usará el caché para hacer el resto de los cálculos. Debido a que la memoria es relativamente lenta, esta 'carga' ralentizará su programa.

Al igual que la predicción de bifurcación, esto se optimizó en los procesadores Pentium: el procesador predice que necesita cargar un dato e intenta cargarlo en el caché antes de que la operación realmente llegue al caché. Como ya hemos visto, la predicción de bifurcación a veces va terriblemente mal: en el peor de los casos, debe retroceder y esperar una carga de memoria, lo que tomará una eternidad ( en otras palabras: la predicción de bifurcación errónea es mala, un recuerdo ¡cargar después de que una predicción de rama falle es simplemente horrible! ).

Afortunadamente para nosotros, si el patrón de acceso a la memoria es predecible, el procesador lo cargará en su caché rápida y todo estará bien.

Lo primero que debemos saber es qué es pequeño . Mientras más pequeño es generalmente mejor, una regla general es apegarse a las tablas de búsqueda que tienen un tamaño <= 4096 bytes. Como límite superior: si su tabla de búsqueda es mayor a 64K, probablemente valga la pena reconsiderarla.

Construyendo una mesa

Entonces hemos descubierto que podemos crear una tabla pequeña. Lo siguiente que debe hacer es establecer una función de búsqueda. Las funciones de búsqueda suelen ser funciones pequeñas que utilizan un par de operaciones enteras básicas (y, o, xor, shift, add, remove y quizás se multipliquen). Desea que su entrada sea traducida por la función de búsqueda a algún tipo de 'clave única' en su tabla, que luego simplemente le da la respuesta de todo el trabajo que quería que hiciera.

En este caso:> = 128 significa que podemos mantener el valor, <128 significa que nos deshacemos de él. La forma más fácil de hacerlo es usando un 'Y': si lo conservamos, lo hacemos Y con 7FFFFFFF; si queremos deshacernos de él, Y lo hacemos con 0. Observe también que 128 es una potencia de 2, por lo que podemos seguir adelante y hacer una tabla de números enteros 32768/128 y llenarla con un cero y mucho 7FFFFFFFF's.

Idiomas gestionados

Quizás se pregunte por qué esto funciona bien en los lenguajes administrados. Después de todo, los idiomas administrados verifican los límites de las matrices con una rama para asegurarse de que no se equivoque ...

Bueno no exactamente... :-)

Se ha trabajado bastante en eliminar esta rama para los idiomas administrados. Por ejemplo:

for (int i = 0; i < array.Length; ++i)
{
   // Use array[i]
}

En este caso, es obvio para el compilador que la condición de límite nunca se verá afectada. Al menos el compilador JIT de Microsoft (pero espero que Java haga cosas similares) lo notará y eliminará la comprobación por completo. WOW, eso significa que no hay rama. Del mismo modo, se ocupará de otros casos obvios.

Si tiene problemas con las búsquedas en los idiomas administrados, la clave es agregar una & 0x[something]FFFa su función de búsqueda para hacer que la verificación de límites sea predecible, y ver que va más rápido.

El resultado de este caso.

// Generate data
int arraySize = 32768;
int[] data = new int[arraySize];

Random random = new Random(0);
for (int c = 0; c < arraySize; ++c)
{
    data[c] = random.Next(256);
}

/*To keep the spirit of the code intact, I'll make a separate lookup table
(I assume we cannot modify 'data' or the number of loops)*/

int[] lookup = new int[256];

for (int c = 0; c < 256; ++c)
{
    lookup[c] = (c >= 128) ? c : 0;
}

// Test
DateTime startTime = System.DateTime.Now;
long sum = 0;

for (int i = 0; i < 100000; ++i)
{
    // Primary loop
    for (int j = 0; j < arraySize; ++j)
    {
        /* Here you basically want to use simple operations - so no
        random branches, but things like &, |, *, -, +, etc. are fine. */
        sum += lookup[data[j]];
    }
}

DateTime endTime = System.DateTime.Now;
Console.WriteLine(endTime - startTime);
Console.WriteLine("sum = " + sum);
Console.ReadLine();
atlaste
fuente
57
Desea omitir el predictor de rama, ¿por qué? Es una optimización.
Dustin Oprea
108
Porque ninguna rama es mejor que una rama :-) En muchas situaciones, esto es simplemente mucho más rápido ... si estás optimizando, definitivamente vale la pena intentarlo. También lo usan bastante en f.ex. graphics.stanford.edu/~seander/bithacks.html
atlaste
36
En general, las tablas de búsqueda pueden ser rápidas, pero ¿ha realizado las pruebas para esta condición en particular? Aún tendrá una condición de bifurcación en su código, solo que ahora se mueve a la parte de generación de la tabla de búsqueda. Todavía no recibirías tu impulso de rendimiento
Zain Rizvi
38
@Zain si realmente quieres saber ... Sí: 15 segundos con la rama y 10 con mi versión. De todos modos, es una técnica útil para saber de cualquier manera.
Atlas
42
¿Por qué no sum += lookup[data[j]]dónde lookupestá una matriz con 256 entradas, las primeras son cero y las últimas son iguales al índice?
Kris Vandermotten
1200

Como los datos se distribuyen entre 0 y 255 cuando se ordena la matriz, alrededor de la primera mitad de las iteraciones no entrarán en la ifdeclaración-(la ifdeclaración se comparte a continuación).

if (data[c] >= 128)
    sum += data[c];

La pregunta es: ¿qué hace que la declaración anterior no se ejecute en ciertos casos como en el caso de los datos ordenados? Aquí viene el "predictor de rama". Un predictor de rama es un circuito digital que trata de adivinar en qué dirección if-then-elseirá una rama (por ejemplo, una estructura) antes de que esto sea seguro. El propósito del predictor de rama es mejorar el flujo en la tubería de instrucciones. ¡Los predictores de rama juegan un papel crítico para lograr un alto rendimiento efectivo!

Hagamos algunas marcas de banco para entenderlo mejor

El rendimiento de una ifdeclaración depende de si su condición tiene un patrón predecible. Si la condición es siempre verdadera o siempre falsa, la lógica de predicción de ramificación en el procesador recogerá el patrón. Por otro lado, si el patrón es impredecible, la ifdeclaración será mucho más costosa.

Midamos el rendimiento de este bucle con diferentes condiciones:

for (int i = 0; i < max; i++)
    if (condition)
        sum++;

Aquí están los tiempos del ciclo con diferentes patrones de verdadero-falso:

Condition                Pattern             Time (ms)
-------------------------------------------------------
(i & 0×80000000) == 0    T repeated          322

(i & 0xffffffff) == 0    F repeated          276

(i & 1) == 0             TF alternating      760

(i & 3) == 0             TFFFTFFF           513

(i & 2) == 0             TTFFTTFF           1675

(i & 4) == 0             TTTTFFFFTTTTFFFF   1275

(i & 8) == 0             8T 8F 8T 8F        752

(i & 16) == 0            16T 16F 16T 16F    490

Una “ mala ” patrón de verdadero o falso puede hacer una if-statement hasta seis veces más lento que una “ buena ” patrón! Por supuesto, qué patrón es bueno y cuál es malo depende de las instrucciones exactas generadas por el compilador y el procesador específico.

Por lo tanto, no hay dudas sobre el impacto de la predicción de sucursales en el rendimiento.

Saqlain
fuente
23
@MooingDuck Porque no hará una diferencia: ese valor puede ser cualquier cosa, pero aún estará dentro de los límites de estos umbrales. Entonces, ¿por qué mostrar un valor aleatorio cuando ya conoce los límites? Aunque estoy de acuerdo en que podría mostrar uno por el bien de la integridad, y "solo por el gusto de hacerlo".
cst1992
24
@ cst1992: En este momento, su sincronización más lenta es TTFFTTFFTTFF, lo que, a mi parecer, es bastante predecible. El azar es inherentemente impredecible, por lo que es completamente posible que sea aún más lento y, por lo tanto, fuera de los límites que se muestran aquí. OTOH, podría ser que TTFFTTFF golpee perfectamente el caso patológico. No puedo decirlo, ya que no mostró los tiempos al azar.
Mooing Duck
21
@MooingDuck Para un ojo humano, "TTFFTTFFTTFF" es una secuencia predecible, pero de lo que estamos hablando aquí es del comportamiento del predictor de rama incorporado en una CPU. El predictor de rama no es el reconocimiento de patrones de nivel AI; es muy simple. Cuando solo alterna ramas, no predice bien. En la mayoría de los códigos, las ramas van de la misma manera casi todo el tiempo; considere un ciclo que se ejecuta mil veces. La rama al final del bucle vuelve al inicio del bucle 999 veces, y luego la milésima vez hace algo diferente. Un predictor de rama muy simple funciona bien, por lo general.
steveha
18
@steveha: Creo que estás haciendo suposiciones sobre cómo funciona el predictor de ramificación de CPU, y no estoy de acuerdo con esa metodología. No sé qué tan avanzado es ese predictor de rama, pero creo que es mucho más avanzado que tú. Probablemente tengas razón, pero las medidas definitivamente serían buenas.
Mooing Duck
55
@steveha: El predictor adaptativo de dos niveles podría bloquearse en el patrón TTFFTTFF sin ningún problema. "Las variantes de este método de predicción se utilizan en la mayoría de los microprocesadores modernos". La predicción de sucursal local y la predicción de sucursal global se basan en un predictor adaptativo de dos niveles, también pueden hacerlo. "La predicción de rama global se utiliza en procesadores AMD y en procesadores Intel Pentium M, Core, Core 2 y Atom basados ​​en Silvermont" También agregue el predictor de acuerdo, el predictor híbrido, la predicción de saltos indirectos, a esa lista. El predictor de bucle no se activa, pero alcanza el 75%. Eso deja solo 2 que no se pueden bloquear
Mooing Duck
1126

Una forma de evitar errores de predicción de rama es crear una tabla de búsqueda e indexarla utilizando los datos. Stefan de Bruijn lo discutió en su respuesta.

Pero en este caso, sabemos que los valores están en el rango [0, 255] y solo nos importan los valores> = 128. Eso significa que podemos extraer fácilmente un solo bit que nos dirá si queremos un valor o no: cambiando los datos a la derecha son 7 bits, nos quedan 0 bits o 1 bit, y solo queremos agregar el valor cuando tenemos 1 bit. Llamemos a este bit el "bit de decisión".

Al usar el valor 0/1 del bit de decisión como un índice en una matriz, podemos hacer un código que será igualmente rápido si los datos se ordenan o no. Nuestro código siempre agregará un valor, pero cuando el bit de decisión es 0, agregaremos el valor en algún lugar que no nos interese. Aquí está el código:

// Test
clock_t start = clock();
long long a[] = {0, 0};
long long sum;

for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        int j = (data[c] >> 7);
        a[j] += data[c];
    }
}

double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
sum = a[1];

Este código desperdicia la mitad de las adiciones pero nunca tiene una falla de predicción de rama. Es tremendamente más rápido en datos aleatorios que la versión con una declaración if real.

Pero en mis pruebas, una tabla de búsqueda explícita fue ligeramente más rápida que esto, probablemente porque la indexación en una tabla de búsqueda fue un poco más rápida que el desplazamiento de bits. Esto muestra cómo mi código se configura y usa la tabla de búsqueda (inimaginablemente llamada lut"Tabla de búsqueda" en el código). Aquí está el código C ++:

// Declare and then fill in the lookup table
int lut[256];
for (unsigned c = 0; c < 256; ++c)
    lut[c] = (c >= 128) ? c : 0;

// Use the lookup table after it is built
for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        sum += lut[data[c]];
    }
}

En este caso, la tabla de búsqueda tenía solo 256 bytes, por lo que cabe muy bien en un caché y todo fue rápido. Esta técnica no funcionaría bien si los datos fueran valores de 24 bits y solo quisiéramos la mitad de ellos ... la tabla de búsqueda sería demasiado grande para ser práctica. Por otro lado, podemos combinar las dos técnicas que se muestran arriba: primero cambiar los bits, luego indexar una tabla de búsqueda. Para un valor de 24 bits que solo queremos el valor de la mitad superior, podríamos potencialmente desplazar los datos a la derecha en 12 bits, y quedarnos con un valor de 12 bits para un índice de tabla. Un índice de tabla de 12 bits implica una tabla de 4096 valores, lo que podría ser práctico.

La técnica de indexar en una matriz, en lugar de usar una ifinstrucción, se puede usar para decidir qué puntero usar. Vi una biblioteca que implementó árboles binarios, y en lugar de tener dos punteros con nombre ( pLefty / pRighto lo que sea) tenía una matriz de punteros de longitud 2 y usé la técnica de "bit de decisión" para decidir cuál seguir. Por ejemplo, en lugar de:

if (x < node->value)
    node = node->pLeft;
else
    node = node->pRight;

esta biblioteca haría algo como:

i = (x < node->value);
node = node->link[i];

Aquí hay un enlace a este código: Red Black Trees , Eternally Confuzzled

steveha
fuente
29
Correcto, también puede usar el bit directamente y multiplicarlo (lo data[c]>>7cual también se trata aquí) Intencionalmente dejé fuera esta solución, pero por supuesto que tienes razón. Solo una pequeña nota: la regla general para las tablas de búsqueda es que si cabe en 4KB (debido al almacenamiento en caché), funcionará, preferiblemente haga que la tabla sea lo más pequeña posible. Para los lenguajes administrados lo empujaría a 64 KB, para los lenguajes de bajo nivel como C ++ y C, probablemente lo reconsideraría (esa es solo mi experiencia). Desde entonces typeof(int) = 4, trataría de mantener un máximo de 10 bits.
atlaste
17
Creo que la indexación con el valor 0/1 probablemente será más rápida que una multiplicación entera, pero supongo que si el rendimiento es realmente crítico, debe perfilarlo. Estoy de acuerdo en que las tablas de búsqueda pequeñas son esenciales para evitar la presión de la memoria caché, pero claramente si tiene una memoria caché más grande, puede salirse con una tabla de búsqueda más grande, por lo que 4KB es más una regla general que una regla difícil. Creo que quisiste decir sizeof(int) == 4? Eso sería cierto para 32 bits. Mi teléfono celular de dos años tiene un caché L1 de 32 KB, por lo que incluso una tabla de búsqueda 4K podría funcionar, especialmente si los valores de búsqueda eran un byte en lugar de un int.
steveha
12
Posiblemente me falta algo, pero en su jmétodo igual a 0 o 1, ¿por qué no simplemente multiplica su valor jantes de agregarlo en lugar de usar la indexación de matriz (posiblemente debería multiplicarse por en 1-jlugar de j)
Richard Tingle
66
@steveha La multiplicación debería ser más rápida, intenté buscarla en los libros de Intel, pero no pude encontrarla ... de cualquier manera, la evaluación comparativa también me da ese resultado aquí.
Atlas
10
@steveha PD: otra posible respuesta sería la int c = data[j]; sum += c & -(c >> 7);que no requiere multiplicación alguna.
atlaste
1022

En el caso ordenado, puede hacerlo mejor que confiar en una predicción de rama exitosa o en cualquier truco de comparación sin rama: elimine completamente la rama.

De hecho, la matriz se divide en una zona contigua con data < 128y otra con data >= 128. Por lo tanto, debe encontrar el punto de partición con una búsqueda dicotómica (usando Lg(arraySize) = 15comparaciones), luego hacer una acumulación directa desde ese punto.

Algo así (sin marcar)

int i= 0, j, k= arraySize;
while (i < k)
{
  j= (i + k) >> 1;
  if (data[j] >= 128)
    k= j;
  else
    i= j;
}
sum= 0;
for (; i < arraySize; i++)
  sum+= data[i];

o, un poco más ofuscado

int i, k, j= (i + k) >> 1;
for (i= 0, k= arraySize; i < k; (data[j] >= 128 ? k : i)= j)
  j= (i + k) >> 1;
for (sum= 0; i < arraySize; i++)
  sum+= data[i];

Un enfoque aún más rápido, que brinda una solución aproximada para ambos, clasificados o no clasificados es: sum= 3137536;(suponiendo una distribución verdaderamente uniforme, 16384 muestras con el valor esperado 191.5) :-)

Yves Daoust
fuente
23
sum= 3137536- inteligente Obviamente, ese no es el punto de la pregunta. La pregunta se trata claramente de explicar características de rendimiento sorprendentes. Me inclino a decir que la adición de hacer en std::partitionlugar de std::sortes valiosa. Aunque la pregunta real se extiende más allá del punto de referencia sintético dado.
sehe
12
@DeadMG: esta no es la búsqueda dicotómica estándar para una clave determinada, sino una búsqueda del índice de partición; requiere una sola comparación por iteración. Pero no confíe en este código, no lo he comprobado. Si está interesado en una implementación correcta garantizada, hágamelo saber.
Yves Daoust
832

El comportamiento anterior está sucediendo debido a la predicción de Branch.

Para comprender la predicción de ramificación, primero se debe comprender la canalización de instrucciones :

Cualquier instrucción se divide en una secuencia de pasos para que se puedan ejecutar diferentes pasos simultáneamente en paralelo. Esta técnica se conoce como canalización de instrucciones y se usa para aumentar el rendimiento en los procesadores modernos. Para entender esto mejor, vea este ejemplo en Wikipedia .

En general, los procesadores modernos tienen tuberías bastante largas, pero para mayor facilidad consideremos estos 4 pasos solamente.

  1. IF - Obtener las instrucciones de la memoria
  2. ID: decodifica las instrucciones
  3. EX - Ejecuta la instrucción
  4. WB - Escribir de nuevo en el registro de la CPU

Tubería de 4 etapas en general para 2 instrucciones. Tubería de 4 etapas en general

Volviendo a la pregunta anterior, consideremos las siguientes instrucciones:

                        A) if (data[c] >= 128)
                                /\
                               /  \
                              /    \
                        true /      \ false
                            /        \
                           /          \
                          /            \
                         /              \
              B) sum += data[c];          C) for loop or print().

Sin predicción de rama, ocurriría lo siguiente:

Para ejecutar la instrucción B o la instrucción C, el procesador tendrá que esperar hasta que la instrucción A no llegue hasta la etapa EX en la tubería, ya que la decisión de ir a la instrucción B o la instrucción C depende del resultado de la instrucción A. Por lo tanto, la tubería Se verá así.

cuando si la condición devuelve verdadero: ingrese la descripción de la imagen aquí

Cuando la condición devuelve falso: ingrese la descripción de la imagen aquí

Como resultado de esperar el resultado de la instrucción A, el total de ciclos de CPU gastados en el caso anterior (sin predicción de rama; tanto para verdadero como para falso) es 7.

Entonces, ¿qué es la predicción de rama?

El predictor de rama intentará adivinar en qué dirección irá una rama (una estructura si-entonces-otra) antes de que esto sea seguro. No esperará a que la instrucción A llegue a la etapa EX de la tubería, pero adivinará la decisión e irá a esa instrucción (B o C en el caso de nuestro ejemplo).

En caso de una suposición correcta, la tubería se ve así: ingrese la descripción de la imagen aquí

Si luego se detecta que la suposición fue incorrecta, las instrucciones ejecutadas parcialmente se descartan y la tubería comienza de nuevo con la rama correcta, lo que genera un retraso. El tiempo que se desperdicia en caso de una predicción errónea de la rama es igual al número de etapas en la tubería desde la etapa de recuperación hasta la etapa de ejecución. Los microprocesadores modernos tienden a tener tuberías bastante largas, por lo que el retraso de predicción errónea es de entre 10 y 20 ciclos de reloj. Cuanto más larga sea la tubería, mayor será la necesidad de un buen predictor de rama .

En el código del OP, la primera vez que es condicional, el predictor de rama no tiene ninguna información para basar la predicción, por lo que la primera vez elegirá aleatoriamente la siguiente instrucción. Más adelante en el ciclo for, puede basar la predicción en el historial. Para una matriz ordenada en orden ascendente, hay tres posibilidades:

  1. Todos los elementos son menores de 128.
  2. Todos los elementos son mayores que 128
  3. Algunos elementos nuevos iniciales son menores que 128 y luego se vuelven mayores que 128

Supongamos que el predictor siempre asumirá la rama verdadera en la primera ejecución.

Entonces, en el primer caso, siempre tomará la rama verdadera ya que históricamente todas sus predicciones son correctas. En el segundo caso, inicialmente pronosticará mal, pero después de algunas iteraciones, pronosticará correctamente. En el tercer caso, inicialmente pronosticará correctamente hasta que los elementos sean inferiores a 128. Después de lo cual fallará durante un tiempo y se corregirá cuando vea un fallo de predicción de rama en la historia.

En todos estos casos, la falla será demasiado menor en número y, como resultado, solo unas pocas veces tendrá que descartar las instrucciones parcialmente ejecutadas y comenzar de nuevo con la rama correcta, lo que resulta en menos ciclos de CPU.

Pero en el caso de una matriz aleatoria sin clasificar, la predicción deberá descartar las instrucciones ejecutadas parcialmente y comenzar de nuevo con la rama correcta la mayor parte del tiempo y resultar en más ciclos de CPU en comparación con la matriz ordenada.

Sharma áspero
fuente
1
¿Cómo se ejecutan dos instrucciones juntas? ¿Se hace esto con núcleos de CPU separados o la instrucción de canalización está integrada en un solo núcleo de CPU?
M.kazem Akhgary
1
@ M.kazemAkhgary Todo está dentro de un núcleo lógico. Si está interesado, esto se describe muy bien, por ejemplo, en el Manual del desarrollador de software Intel
Sergey.quixoticaxis.Ivanov
728

Una respuesta oficial sería de

  1. Intel: evitar el costo de la predicción errónea de sucursales
  2. Intel - Reorganización de sucursales y bucles para evitar errores de predicción
  3. Artículos científicos - arquitectura informática de predicción de sucursales
  4. Libros: JL Hennessy, DA Patterson: Arquitectura de computadoras: un enfoque cuantitativo
  5. Artículos en publicaciones científicas: TY Yeh, YN Patt hizo muchos de estos en predicciones de ramas.

También puede ver en este hermoso diagrama por qué el predictor de rama se confunde.

Diagrama de estado de 2 bits

Cada elemento en el código original es un valor aleatorio

data[c] = std::rand() % 256;

entonces el predictor cambiará de lado como el std::rand()golpe.

Por otro lado, una vez que se ordena, el predictor se moverá primero a un estado de fuerte no tomado y cuando los valores cambien al valor alto, el predictor cambiará en tres ejecuciones desde fuertemente no tomado hasta fuertemente tomado.


Surt
fuente
697

En la misma línea (creo que esto no fue resaltado por ninguna respuesta) es bueno mencionar que a veces (especialmente en software donde el rendimiento importa, como en el kernel de Linux) puede encontrar algunas declaraciones if como las siguientes:

if (likely( everything_is_ok ))
{
    /* Do something */
}

o similarmente:

if (unlikely(very_improbable_condition))
{
    /* Do something */    
}

Ambas, likely()y unlikely()de hecho, son macros que se definen usando algo como los GCC __builtin_expectpara ayudar al compilador a insertar el código de predicción para favorecer la condición teniendo en cuenta la información proporcionada por el usuario. GCC admite otras funciones integradas que podrían cambiar el comportamiento del programa en ejecución o emitir instrucciones de bajo nivel, como borrar la memoria caché, etc. Consulte esta documentación que analiza las funciones integradas de GCC disponibles.

Normalmente, este tipo de optimizaciones se encuentran principalmente en aplicaciones en tiempo real o sistemas integrados donde el tiempo de ejecución es importante y es crítico. Por ejemplo, si está buscando alguna condición de error que solo ocurre 1/10000000 veces, ¿por qué no informar al compilador sobre esto? De esta manera, por defecto, la predicción de rama supondría que la condición es falsa.

rkachach
fuente
679

Las operaciones booleanas de uso frecuente en C ++ producen muchas ramas en el programa compilado. Si estas ramas están dentro de bucles y son difíciles de predecir, pueden ralentizar significativamente la ejecución. Las variables booleanas se almacenan como enteros de 8 bits con el valor 0para falsey 1para true.

Las variables booleanas están sobredeterminadas en el sentido de que todos los operadores que tienen variables booleanas como entrada verifican si las entradas tienen otro valor que no sea 0o 1, pero los operadores que tienen booleanos como salida no pueden producir ningún otro valor que 0o 1. Esto hace que las operaciones con variables booleanas como entrada sean menos eficientes de lo necesario. Considere un ejemplo:

bool a, b, c, d;
c = a && b;
d = a || b;

Normalmente, el compilador lo implementa de la siguiente manera:

bool a, b, c, d;
if (a != 0) {
    if (b != 0) {
        c = 1;
    }
    else {
        goto CFALSE;
    }
}
else {
    CFALSE:
    c = 0;
}
if (a == 0) {
    if (b == 0) {
        d = 0;
    }
    else {
        goto DTRUE;
    }
}
else {
    DTRUE:
    d = 1;
}

Este código está lejos de ser óptimo. Las ramas pueden tardar mucho tiempo en caso de predicciones erróneas. Las operaciones booleanas pueden hacerse mucho más eficientes si se sabe con certeza que los operandos no tienen otros valores que 0y 1. La razón por la cual el compilador no hace tal suposición es que las variables pueden tener otros valores si no se inicializan o provienen de fuentes desconocidas. El código anterior se puede optimizar si ay bse ha inicializado a valores válidos o si vienen de los operadores que producen salida booleana. El código optimizado se ve así:

char a = 0, b = 1, c, d;
c = a & b;
d = a | b;

charse usa en lugar de boolpara hacer posible el uso de operadores bit a bit ( &y |) en lugar de los operadores booleanos ( &&y ||). Los operadores bit a bit son instrucciones únicas que toman solo un ciclo de reloj. El operador O ( |) funciona incluso si ay btienen valores distintos 0o 1. El operador AND ( &) y el operador EXCLUSIVO OR ( ^) pueden dar resultados inconsistentes si los operandos tienen otros valores distintos de 0y 1.

~No se puede utilizar para NO. En cambio, puede hacer un NOT booleano en una variable que se sabe que es 0o 1haciendo XOR con 1:

bool a, b;
b = !a;

se puede optimizar para:

char a = 0, b;
b = a ^ 1;

a && bno se puede reemplazar con a & bif bes una expresión que no debe evaluarse if ais false( &&no evaluará b, &will). Del mismo modo, a || bno se puede reemplazar con a | bif bes una expresión que no debe evaluarse if ais true.

Usar operadores bit a bit es más ventajoso si los operandos son variables que si los operandos son comparaciones:

bool a; double x, y, z;
a = x > y && z < 5.0;

es óptimo en la mayoría de los casos (a menos que espere que la &&expresión genere muchas predicciones erróneas de rama).

Maciej
fuente
342

¡Eso es seguro!...

¡La predicción de bifurcación hace que la lógica funcione más lentamente, debido al cambio que ocurre en su código! Es como si estuvieras yendo por una calle recta o una calle con muchas curvas, ¡seguro que la recta se hará más rápido! ...

Si se ordena la matriz, su condición es falsa en el primer paso:, data[c] >= 128luego se convierte en un valor verdadero para todo el camino hasta el final de la calle. Así es como llegas al final de la lógica más rápido. Por otro lado, al usar una matriz no ordenada, necesita una gran cantidad de giros y procesamientos que hacen que su código se ejecute más lento con seguridad ...

Mira la imagen que creé para ti a continuación. ¿Qué calle se va a terminar más rápido?

Predicción de rama

Entonces, mediante programación, la predicción de ramificación hace que el proceso sea más lento ...

También al final, es bueno saber que tenemos dos tipos de predicciones de rama que afectarán su código de manera diferente:

1. Estática

2. Dinámico

Predicción de rama

La predicción de ramificación estática es utilizada por el microprocesador la primera vez que se encuentra una ramificación condicional, y la predicción de ramificación dinámica se usa para ejecuciones posteriores del código de ramificación condicional.

Para escribir de manera efectiva su código para aprovechar estas reglas, cuando escriba sentencias if-else o switch , verifique primero los casos más comunes y trabaje progresivamente hasta los menos comunes. Los bucles no requieren necesariamente ningún orden especial de código para la predicción de rama estática, ya que normalmente solo se usa la condición del iterador de bucle.

Alireza
fuente
304

Esta pregunta ya ha sido respondida excelentemente muchas veces. Aún así, me gustaría llamar la atención del grupo sobre otro análisis interesante.

Recientemente, este ejemplo (modificado muy ligeramente) también se usó como una forma de demostrar cómo se puede perfilar un fragmento de código dentro del programa en Windows. En el camino, el autor también muestra cómo usar los resultados para determinar dónde pasa la mayor parte del tiempo el código, tanto en el caso ordenado como en el no ordenado. Finalmente, la pieza también muestra cómo usar una característica poco conocida de la HAL (Capa de abstracción de hardware) para determinar cuánta predicción de ramificación está ocurriendo en el caso no ordenado.

El enlace está aquí: http://www.geoffchappell.com/studies/windows/km/ntoskrnl/api/ex/profile/demo.htm

ForeverLearning
fuente
3
Ese es un artículo muy interesante (de hecho, acabo de leerlo todo), pero ¿cómo responde la pregunta?
Peter Mortensen
2
@ PeterMortensen Estoy un poco desconcertado por su pregunta. Por ejemplo, aquí hay una línea relevante de esa pieza: el When the input is unsorted, all the rest of the loop takes substantial time. But with sorted input, the processor is somehow able to spend not just less time in the body of the loop, meaning the buckets at offsets 0x18 and 0x1C, but vanishingly little time on the mechanism of looping. autor está tratando de discutir la creación de perfiles en el contexto del código publicado aquí y en el proceso tratando de explicar por qué el caso ordenado es mucho más rápido.
ForeverLearning
261

Como lo que ya han mencionado otros, lo que está detrás del misterio es Branch Predictor .

No estoy tratando de agregar algo, sino explicar el concepto de otra manera. Hay una introducción concisa en la wiki que contiene texto y diagrama. Me gusta la explicación a continuación que usa un diagrama para elaborar el Predictor de rama intuitivamente.

En la arquitectura de la computadora, un predictor de rama es un circuito digital que intenta adivinar en qué dirección irá una rama (por ejemplo, una estructura si-entonces-otra) antes de que esto sea seguro. El propósito del predictor de rama es mejorar el flujo en la tubería de instrucciones. Los predictores de rama desempeñan un papel fundamental para lograr un alto rendimiento efectivo en muchas arquitecturas modernas de microprocesadores canalizados como x86.

La ramificación bidireccional generalmente se implementa con una instrucción de salto condicional. Un salto condicional puede "no tomarse" y continuar la ejecución con la primera rama de código que sigue inmediatamente después del salto condicional, o puede "tomarse" y saltar a un lugar diferente en la memoria del programa donde está la segunda rama de código almacenado No se sabe con certeza si se realizará o no un salto condicional hasta que se haya calculado la condición y el salto condicional haya pasado la etapa de ejecución en la canalización de instrucciones (ver figura 1).

Figura 1

Basado en el escenario descrito, he escrito una demostración de animación para mostrar cómo se ejecutan las instrucciones en una tubería en diferentes situaciones.

  1. Sin el Predictor de rama.

Sin la predicción de rama, el procesador tendría que esperar hasta que la instrucción de salto condicional haya pasado la etapa de ejecución antes de que la siguiente instrucción pueda ingresar a la etapa de recuperación en la tubería.

El ejemplo contiene tres instrucciones y la primera es una instrucción de salto condicional. Las últimas dos instrucciones pueden ir a la tubería hasta que se ejecute la instrucción de salto condicional.

sin predictor de rama

Tomará 9 ciclos de reloj para completar 3 instrucciones.

  1. Usa Branch Predictor y no hagas un salto condicional. Supongamos que la predicción no está dando el salto condicional.

ingrese la descripción de la imagen aquí

Tomará 7 ciclos de reloj para completar 3 instrucciones.

  1. Usa el Predictor de rama y da un salto condicional. Supongamos que la predicción no está dando el salto condicional.

ingrese la descripción de la imagen aquí

Tomará 9 ciclos de reloj para completar 3 instrucciones.

El tiempo que se desperdicia en caso de una predicción errónea de la rama es igual al número de etapas en la tubería desde la etapa de recuperación hasta la etapa de ejecución. Los microprocesadores modernos tienden a tener tuberías bastante largas, por lo que el retraso de predicción errónea es de entre 10 y 20 ciclos de reloj. Como resultado, hacer una tubería más larga aumenta la necesidad de un predictor de rama más avanzado.

Como puede ver, parece que no tenemos una razón para no usar Branch Predictor.

Es una demostración bastante simple que aclara la parte más básica de Branch Predictor. Si esos gifs son molestos, no dude en eliminarlos de la respuesta y los visitantes también pueden obtener el código fuente de demostración en vivo de BranchPredictorDemo

Eugene
fuente
1
Casi tan buenos como las animaciones de marketing de Intel, y estaban obsesionados no solo con la predicción de sucursales sino también con la ejecución fuera de orden, siendo ambas estrategias "especulativas". Leer con anticipación en la memoria y el almacenamiento (búsqueda previa secuencial en el búfer) también es especulativo. Todo se suma.
mckenzm
@mckenzm: el ejecutivo especulativo fuera de orden hace que la predicción de sucursales sea aún más valiosa; además de ocultar burbujas de búsqueda / decodificación, la predicción de rama + ejecución especulativa elimina las dependencias de control de la latencia de ruta crítica. El código dentro o después de un if()bloque puede ejecutarse antes de que se conozca la condición de ramificación. O para un ciclo de búsqueda como strleno memchr, las interacciones pueden superponerse. Si tuviera que esperar a que se conozca el resultado de coincidencia o no antes de ejecutar cualquiera de las próximas iteraciones, tendría un cuello de botella en la carga de caché + latencia ALU en lugar de rendimiento.
Peter Cordes
210

Ganancia de predicción de rama!

Es importante comprender que la predicción errónea de la rama no ralentiza los programas. El costo de una predicción perdida es como si la predicción de la rama no existiera y esperara la evaluación de la expresión para decidir qué código ejecutar (más explicaciones en el siguiente párrafo).

if (expression)
{
    // Run 1
} else {
    // Run 2
}

Siempre que haya una instrucción if-else\ switch, la expresión debe evaluarse para determinar qué bloque debe ejecutarse. En el código de ensamblaje generado por el compilador, se insertan instrucciones de ramificación condicional .

Una instrucción de bifurcación puede hacer que una computadora comience a ejecutar una secuencia de instrucciones diferente y, por lo tanto, se desvíe de su comportamiento predeterminado de ejecutar instrucciones en orden (es decir, si la expresión es falsa, el programa omite el código del ifbloque) dependiendo de alguna condición, que es La evaluación de la expresión en nuestro caso.

Dicho esto, el compilador intenta predecir el resultado antes de que se evalúe realmente. Obtendrá instrucciones del ifbloque, y si la expresión resulta ser verdadera, ¡entonces maravillosa! Ganamos el tiempo necesario para evaluarlo e hicimos progresos en el código; si no, entonces estamos ejecutando el código incorrecto, la tubería se vacía y se ejecuta el bloque correcto.

Visualización:

Digamos que necesita elegir la ruta 1 o la ruta 2. Esperando a que su compañero revise el mapa, se detuvo en ## y esperó, o simplemente podría elegir la ruta1 y si tuvo suerte (la ruta 1 es la ruta correcta), entonces genial, no tuviste que esperar a que tu compañero revisara el mapa (ahorraste el tiempo que le habría tomado revisar el mapa), de lo contrario simplemente regresarás.

Si bien el vaciado de tuberías es súper rápido, hoy en día vale la pena tomar esta apuesta. Predecir datos ordenados o datos que cambian lentamente siempre es más fácil y mejor que predecir cambios rápidos.

 O      Route 1  /-------------------------------
/|\             /
 |  ---------##/
/ \            \
                \
        Route 2  \--------------------------------
Tony Tannous
fuente
Si bien el lavado de tuberías es súper rápido, en realidad no. Es rápido en comparación con una pérdida de memoria caché hasta DRAM, pero en un x86 moderno de alto rendimiento (como la familia Intel Sandybridge) se trata de una docena de ciclos. Aunque la recuperación rápida le permite evitar esperar a que todas las instrucciones independientes más antiguas lleguen a la jubilación antes de comenzar la recuperación, aún así pierde muchos ciclos iniciales en un error de predicción. ¿Qué sucede exactamente cuando una CPU de skylake predice erróneamente una rama? . (Y cada ciclo puede tener aproximadamente 4 instrucciones de trabajo). Malo para el código de alto rendimiento.
Peter Cordes
153

En ARM, no se necesita una bifurcación, porque cada instrucción tiene un campo de condición de 4 bits, que prueba (a costo cero) cualquiera de las 16 condiciones diferentes que pueden surgir en el Registro de estado del procesador, y si la condición de una instrucción es falso, se omiten las instrucciones. Esto elimina la necesidad de ramificaciones cortas, y no habría éxito de predicción de ramificación para este algoritmo. Por lo tanto, la versión ordenada de este algoritmo sería más lenta que la versión no ordenada en ARM, debido a la sobrecarga adicional de la clasificación.

El bucle interno para este algoritmo se vería similar al siguiente en lenguaje ensamblador ARM:

MOV R0, #0     // R0 = sum = 0
MOV R1, #0     // R1 = c = 0
ADR R2, data   // R2 = addr of data array (put this instruction outside outer loop)
.inner_loop    // Inner loop branch label
    LDRB R3, [R2, R1]     // R3 = data[c]
    CMP R3, #128          // compare R3 to 128
    ADDGE R0, R0, R3      // if R3 >= 128, then sum += data[c] -- no branch needed!
    ADD R1, R1, #1        // c++
    CMP R1, #arraySize    // compare c to arraySize
    BLT inner_loop        // Branch to inner_loop if c < arraySize

Pero esto es realmente parte de una imagen más grande:

CMPlos códigos de operación siempre actualizan los bits de estado en el Registro de estado del procesador (PSR), porque ese es su propósito, pero la mayoría de las otras instrucciones no tocan el PSR a menos que agregue un Ssufijo opcional a la instrucción, especificando que el PSR debe actualizarse en función del resultado de la instrucción. Al igual que el sufijo de condición de 4 bits, poder ejecutar instrucciones sin afectar el PSR es un mecanismo que reduce la necesidad de ramificaciones en ARM y también facilita el envío fuera de servicio a nivel de hardware , porque después de realizar alguna operación X se actualiza los bits de estado, posteriormente (o en paralelo) puede hacer un montón de otro trabajo que explícitamente no debería afectar los bits de estado, luego puede probar el estado de los bits de estado establecidos anteriormente por X.

El campo de prueba de condición y el campo opcional "bit de estado establecido" se pueden combinar, por ejemplo:

  • ADD R1, R2, R3realiza R1 = R2 + R3sin actualizar ningún bit de estado.
  • ADDGE R1, R2, R3 realiza la misma operación solo si una instrucción previa que afectó los bits de estado resultó en una condición Mayor o Igual.
  • ADDS R1, R2, R3realiza la suma y luego actualiza los N, Z, Cy Vbanderas en el Registro de estado del procesador en función de si el resultado fue negativo, cero, realizado (para la adición sin firmar), o se desbordó (para la adición firmado).
  • ADDSGE R1, R2, R3realiza la adición solo si la GEprueba es verdadera y luego actualiza los bits de estado según el resultado de la adición.

La mayoría de las arquitecturas de procesador no tienen esta capacidad de especificar si los bits de estado deben actualizarse o no para una operación determinada, lo que puede requerir escribir código adicional para guardar y luego restaurar bits de estado, o puede requerir ramificaciones adicionales, o puede limitar la salida del procesador de eficiencia de ejecución de órdenes: uno de los efectos secundarios de la mayoría de las arquitecturas de conjuntos de instrucciones de CPU que actualizan a la fuerza los bits de estado después de la mayoría de las instrucciones es que es mucho más difícil separar qué instrucciones se pueden ejecutar en paralelo sin interferir entre sí. La actualización de bits de estado tiene efectos secundarios, por lo tanto, tiene un efecto de linealización en el código.La capacidad de ARM de mezclar y combinar pruebas de condición sin ramificación en cualquier instrucción con la opción de actualizar o no actualizar los bits de estado después de cualquier instrucción es extremadamente poderosa, tanto para los programadores como para los compiladores de lenguaje ensamblador, y produce un código muy eficiente.

Si alguna vez se ha preguntado por qué ARM ha sido tan exitoso, la brillante efectividad y la interacción de estos dos mecanismos son una gran parte de la historia, porque son una de las mayores fuentes de eficiencia de la arquitectura ARM. La brillantez de los diseñadores originales de ARM ISA en 1983, Steve Furber y Roger (ahora Sophie) Wilson, no puede ser exagerada.

Luke Hutchison
fuente
1
La otra innovación en ARM es la adición del sufijo de instrucción S, también opcional en (casi) todas las instrucciones, que si está ausente, evita que las instrucciones cambien los bits de estado (con la excepción de la instrucción CMP, cuyo trabajo es establecer bits de estado, entonces no necesita el sufijo S). Esto le permite evitar las instrucciones de CMP en muchos casos, siempre que la comparación sea cero o similar (por ejemplo, SUBS R0, R0, # 1 establecerá el bit Z (cero) cuando R0 llegue a cero). Los condicionales y el sufijo S incurren en gastos generales cero. Es una ISA bastante hermosa.
Luke Hutchison
2
No agregar el sufijo S le permite tener varias instrucciones condicionales seguidas sin preocuparse de que una de ellas pueda cambiar los bits de estado, lo que podría tener el efecto secundario de omitir el resto de las instrucciones condicionales.
Luke Hutchison
Tenga en cuenta que el OP no incluye el tiempo para ordenar en su medición. Probablemente sea una pérdida general ordenar primero antes de ejecutar un bucle x86 de ramificación, aunque el caso no ordenado hace que el bucle se ejecute mucho más lento. Pero clasificar una gran variedad requiere mucho trabajo.
Peter Cordes
Por cierto, podría guardar una instrucción en el bucle indexando en relación con el final de la matriz. Antes del ciclo, configure R2 = data + arraySize, luego comience con R1 = -arraySize. La parte inferior del bucle se convierte en adds r1, r1, #1/ bnz inner_loop. Los compiladores no usan esta optimización por alguna razón: / Pero de todos modos, la ejecución predicada del complemento no es fundamentalmente diferente en este caso de lo que puede hacer con el código sin ramificación en otras ISA, como x86 cmov. Aunque no es tan agradable: el indicador de optimización de gcc -O3 hace que el código sea más lento que -O2
Peter Cordes
1
(La ejecución predicada ARM realmente NOPs la instrucción, por lo que incluso puede usarla en cargas o almacenes que fallarían, a diferencia de x86 cmovcon un operando de origen de memoria. La mayoría de los ISA, incluido AArch64, solo tienen operaciones de selección de ALU. Por lo tanto, la predicción ARM puede ser poderosa, y utilizable de manera más eficiente que el código sin ramificación en la mayoría de las ISA.)
Peter Cordes
147

Se trata de la predicción de rama. ¿Qué es?

  • Un predictor de rama es una de las antiguas técnicas de mejora del rendimiento que aún encuentra relevancia en las arquitecturas modernas. Si bien las técnicas de predicción simples proporcionan una búsqueda rápida y eficiencia energética, sufren una alta tasa de predicción errónea.

  • Por otro lado, las predicciones de ramas complejas, ya sean neurales o variantes de predicción de ramas de dos niveles, proporcionan una mejor precisión de predicción, pero consumen más potencia y la complejidad aumenta exponencialmente.

  • Además de esto, en las técnicas de predicción complejas, el tiempo necesario para predecir las ramas es en sí mismo muy alto (rango de 2 a 5 ciclos), que es comparable al tiempo de ejecución de las ramas reales.

  • La predicción de rama es esencialmente un problema de optimización (minimización) en el que se hace hincapié en lograr la tasa de fallas más baja posible, el bajo consumo de energía y la baja complejidad con recursos mínimos.

Realmente hay tres tipos diferentes de ramas:

Ramificaciones condicionales de reenvío : en función de una condición de tiempo de ejecución, la PC (contador de programa) se cambia para apuntar a una dirección hacia adelante en la secuencia de instrucciones.

Ramas condicionales hacia atrás : la PC se cambia para apuntar hacia atrás en la secuencia de instrucciones. La bifurcación se basa en alguna condición, como la bifurcación hacia atrás al comienzo de un bucle de programa cuando una prueba al final del bucle indica que el bucle debe ejecutarse nuevamente.

Ramas incondicionales : esto incluye saltos, llamadas a procedimientos y devoluciones que no tienen una condición específica. Por ejemplo, una instrucción de salto incondicional puede codificarse en lenguaje ensamblador simplemente como "jmp", y la secuencia de instrucciones debe dirigirse inmediatamente a la ubicación de destino señalada por la instrucción de salto, mientras que un salto condicional que puede codificarse como "jmpne" redirigiría la secuencia de instrucciones solo si el resultado de una comparación de dos valores en instrucciones anteriores de "comparación" muestra que los valores no son iguales. (El esquema de direccionamiento segmentado utilizado por la arquitectura x86 agrega complejidad adicional, ya que los saltos pueden ser "cercanos" (dentro de un segmento) o "lejanos" (fuera del segmento). Cada tipo tiene diferentes efectos en los algoritmos de predicción de ramas.

Predicción de bifurcación estática / dinámica : el microprocesador usa la predicción de bifurcación estática la primera vez que se encuentra una bifurcación condicional, y la predicción de bifurcación dinámica se usa para ejecutar con éxito el código de bifurcación condicional.

Referencias

Farhad
fuente
146

Además del hecho de que la predicción de ramificación puede ralentizarlo, una matriz ordenada tiene otra ventaja:

Puede tener una condición de detención en lugar de simplemente verificar el valor, de esta manera solo recorre los datos relevantes e ignora el resto.
La predicción de rama se perderá solo una vez.

 // sort backwards (higher values first), may be in some other part of the code
 std::sort(data, data + arraySize, std::greater<int>());

 for (unsigned c = 0; c < arraySize; ++c) {
       if (data[c] < 128) {
              break;
       }
       sum += data[c];               
 }
Yochai Timmer
fuente
1
Correcto, pero el costo de instalación de ordenar la matriz es O (N log N), por lo que romper temprano no lo ayuda si la única razón por la que está ordenando la matriz es para poder romper temprano. Sin embargo, si tiene otras razones para ordenar previamente la matriz, entonces sí, esto es valioso.
Luke Hutchison el
Depende de cuántas veces clasifique los datos en comparación con las veces que los repita. El tipo en este ejemplo es solo un ejemplo, no tiene que ser justo antes del ciclo
Yochai Timmer
2
Sí, ese es exactamente el punto que hice en mi primer comentario :-) Usted dice "La predicción de la rama se perderá solo una vez". Pero no está contando los errores de predicción de rama O (N log N) dentro del algoritmo de ordenación, que en realidad es mayor que los errores de predicción de rama O (N) en el caso no ordenado. Por lo tanto, necesitaría usar la totalidad de los datos ordenados O (log N) veces para alcanzar el punto de equilibrio (probablemente en realidad más cerca de O (10 log N), dependiendo del algoritmo de clasificación, por ejemplo, para la clasificación rápida, debido a errores de caché - mergesort es más coherente con el caché, por lo que necesitaría un uso más cercano a O (2 log N) para alcanzar el punto de equilibrio.)
Luke Hutchison,
Sin embargo, una optimización significativa sería hacer "la mitad de una selección rápida", clasificando solo los elementos menores que el valor de pivote objetivo de 127 (suponiendo que todo lo que sea menor o igual que el pivote se ordena después del pivote). Una vez que llegue al pivote, sume los elementos antes del pivote. Esto se ejecutaría en el tiempo de inicio de O (N) en lugar de O (N log N), aunque todavía habrá muchas fallas de predicción de rama, probablemente del orden de O (5 N) en función de los números que di antes, ya que Es la mitad de una clasificación rápida.
Luke Hutchison
132

Las matrices ordenadas se procesan más rápido que una matriz no clasificada, debido a un fenómeno llamado predicción de ramificación.

El predictor de rama es un circuito digital (en arquitectura de computadora) que intenta predecir en qué dirección irá una rama, mejorando el flujo en la tubería de instrucciones. El circuito / computadora predice el siguiente paso y lo ejecuta.

Hacer una predicción incorrecta lleva a volver al paso anterior y ejecutar con otra predicción. Suponiendo que la predicción es correcta, el código continuará con el siguiente paso. Una predicción incorrecta da como resultado la repetición del mismo paso, hasta que se produce una predicción correcta.

La respuesta a tu pregunta es muy simple.

En una matriz sin clasificar, la computadora realiza múltiples predicciones, lo que aumenta la posibilidad de errores. Mientras que, en una matriz ordenada, la computadora hace menos predicciones, lo que reduce la posibilidad de errores. Hacer más predicciones requiere más tiempo.

TATTEO

Matriz sin clasificar: carretera curva

______   ________
|     |__|

Predicción de rama: adivinar / predecir qué camino es recto y seguirlo sin verificar

___________________________________________ Straight road
 |_________________________________________|Longer road

Aunque ambas carreteras llegan al mismo destino, la carretera recta es más corta y la otra es más larga. Si luego elige el otro por error, no hay vuelta atrás, por lo que perderá más tiempo si elige el camino más largo. Esto es similar a lo que sucede en la computadora, y espero que esto te haya ayudado a entender mejor.


También quiero citar @Simon_Weaver de los comentarios:

No hace menos predicciones, hace menos predicciones incorrectas. Todavía tiene que predecir cada vez a través del ciclo ...

Omkaar.K
fuente
124

Probé el mismo código con MATLAB 2011b con mi MacBook Pro (Intel i7, 64 bit, 2.4 GHz) para el siguiente código MATLAB:

% Processing time with Sorted data vs unsorted data
%==========================================================================
% Generate data
arraySize = 32768
sum = 0;
% Generate random integer data from range 0 to 255
data = randi(256, arraySize, 1);


%Sort the data
data1= sort(data); % data1= data  when no sorting done


%Start a stopwatch timer to measure the execution time
tic;

for i=1:100000

    for j=1:arraySize

        if data1(j)>=128
            sum=sum + data1(j);
        end
    end
end

toc;

ExeTimeWithSorting = toc - tic;

Los resultados para el código MATLAB anterior son los siguientes:

  a: Elapsed time (without sorting) = 3479.880861 seconds.
  b: Elapsed time (with sorting ) = 2377.873098 seconds.

Los resultados del código C como en @GManNickG obtengo:

  a: Elapsed time (without sorting) = 19.8761 sec.
  b: Elapsed time (with sorting ) = 7.37778 sec.

Basado en esto, parece que MATLAB es casi 175 veces más lento que la implementación de C sin clasificar y 350 veces más lento con la clasificación. En otras palabras, el efecto (de la predicción de ramificación) es 1.46x para la implementación de MATLAB y 2.7x para la implementación de C.

Shan
fuente
77
Solo en aras de la exhaustividad, probablemente no sea así como implementaría eso en Matlab. Apuesto a que sería mucho más rápido si se hace después de vectorizar el problema.
ysap
1
Matlab realiza paralelización / vectorización automática en muchas situaciones, pero el problema aquí es verificar el efecto de la predicción de rama. ¡Matlab no es inmune de ninguna manera!
Shan
1
¿Matlab utiliza números nativos o una implementación específica de mat mat lab (cantidad infinita de dígitos más o menos?)
Thorbjørn Ravn Andersen
55

La suposición de otras respuestas de que uno necesita ordenar los datos no es correcta.

El siguiente código no clasifica toda la matriz, sino solo segmentos de 200 elementos, y por lo tanto se ejecuta más rápido.

La clasificación de solo secciones de elementos k completa el preprocesamiento en tiempo lineal O(n), en lugar del O(n.log(n))tiempo necesario para ordenar toda la matriz.

#include <algorithm>
#include <ctime>
#include <iostream>

int main() {
    int data[32768]; const int l = sizeof data / sizeof data[0];

    for (unsigned c = 0; c < l; ++c)
        data[c] = std::rand() % 256;

    // sort 200-element segments, not the whole array
    for (unsigned c = 0; c + 200 <= l; c += 200)
        std::sort(&data[c], &data[c + 200]);

    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i) {
        for (unsigned c = 0; c < sizeof data / sizeof(int); ++c) {
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    std::cout << static_cast<double>(clock() - start) / CLOCKS_PER_SEC << std::endl;
    std::cout << "sum = " << sum << std::endl;
}

Esto también "prueba" que no tiene nada que ver con ningún problema algorítmico, como el orden de clasificación, y de hecho es una predicción de rama.

usuario2297550
fuente
44
¿Realmente no veo cómo esto prueba algo? Lo único que ha demostrado es que "no hacer todo el trabajo de ordenar toda la matriz lleva menos tiempo que ordenar toda la matriz". Su afirmación de que esto "también funciona más rápido" depende mucho de la arquitectura. Vea mi respuesta sobre cómo funciona esto en ARM. PD: puede hacer que su código sea más rápido en arquitecturas que no sean ARM colocando la suma dentro del bucle de bloque de 200 elementos, ordenando en reversa y luego utilizando la sugerencia de Yochai Timmer de romper una vez que obtenga un valor fuera de rango. De esa manera, cada suma de bloques de 200 elementos puede terminarse antes de tiempo.
Luke Hutchison
Si solo desea implementar el algoritmo de manera eficiente sobre datos sin clasificar, debe hacer esa operación sin ramificación (y con SIMD, por ejemplo, con x86 pcmpgtbpara encontrar elementos con su conjunto de bits alto, luego AND a cero elementos más pequeños). Pasar cualquier tiempo realmente clasificando trozos sería más lento. Una versión sin sucursales tendría un rendimiento independiente de los datos, lo que también demuestra que el costo proviene de la predicción errónea de la sucursal. O simplemente use los contadores de rendimiento para observar eso directamente, como Skylake int_misc.clear_resteer_cycleso int_misc.recovery_cyclespara contar los ciclos inactivos frontales de las predicciones erróneas
Peter Cordes
Ambos comentarios anteriores parecen ignorar los problemas algorítmicos generales y la complejidad, a favor de abogar por hardware especializado con instrucciones especiales de la máquina. Encuentro el primero particularmente insignificante en que descarta alegremente las importantes percepciones generales en esta respuesta a favor ciego de instrucciones de máquina especializadas.
user2297550
36

La respuesta de Bjarne Stroustrup a esta pregunta:

Eso suena como una pregunta de entrevista. ¿Es verdad? ¿Cómo sabrías? Es una mala idea responder preguntas sobre la eficiencia sin primero hacer algunas mediciones, por lo que es importante saber cómo medir.

Entonces, probé con un vector de un millón de enteros y obtuve:

Already sorted    32995 milliseconds
Shuffled          125944 milliseconds

Already sorted    18610 milliseconds
Shuffled          133304 milliseconds

Already sorted    17942 milliseconds
Shuffled          107858 milliseconds

Lo corrí varias veces para estar seguro. Sí, el fenómeno es real. Mi código clave fue:

void run(vector<int>& v, const string& label)
{
    auto t0 = system_clock::now();
    sort(v.begin(), v.end());
    auto t1 = system_clock::now();
    cout << label 
         << duration_cast<microseconds>(t1  t0).count() 
         << " milliseconds\n";
}

void tst()
{
    vector<int> v(1'000'000);
    iota(v.begin(), v.end(), 0);
    run(v, "already sorted ");
    std::shuffle(v.begin(), v.end(), std::mt19937{ std::random_device{}() });
    run(v, "shuffled    ");
}

Al menos, el fenómeno es real con este compilador, la biblioteca estándar y la configuración del optimizador. Las diferentes implementaciones pueden y dan diferentes respuestas. De hecho, alguien hizo un estudio más sistemático (una búsqueda rápida en la web lo encontrará) y la mayoría de las implementaciones muestran ese efecto.

Una razón es la predicción de rama: la operación clave en el algoritmo de clasificación es “if(v[i] < pivot]) …”o equivalente. Para una secuencia ordenada, esa prueba siempre es verdadera, mientras que, para una secuencia aleatoria, la rama elegida varía aleatoriamente.

Otra razón es que cuando el vector ya está ordenado, nunca necesitamos mover elementos a su posición correcta. El efecto de estos pequeños detalles es el factor de cinco o seis que vimos.

Quicksort (y clasificación en general) es un estudio complejo que ha atraído a algunas de las mejores mentes de la informática. Una buena función de clasificación es el resultado de elegir un buen algoritmo y prestar atención al rendimiento del hardware en su implementación.

Si desea escribir código eficiente, necesita saber un poco sobre la arquitectura de la máquina.

Selcuk
fuente
28

Esta pregunta tiene sus raíces en los modelos de predicción de sucursales en las CPU. Recomiendo leer este artículo:

Aumento de la tasa de obtención de instrucciones a través de la predicción de múltiples sucursales y un caché de direcciones de sucursal

Cuando haya ordenado elementos, IR no podría molestarse en buscar todas las instrucciones de la CPU, una y otra vez, las recupera de la memoria caché.

hatirlatici
fuente
Las instrucciones permanecen activas en el caché de instrucciones L1 de la CPU, independientemente de las predicciones erróneas. El problema es buscarlos en la tubería en el orden correcto, antes de que las instrucciones inmediatamente anteriores hayan decodificado y terminado de ejecutarse.
Peter Cordes
15

Una forma de evitar errores de predicción de rama es crear una tabla de búsqueda e indexarla utilizando los datos. Stefan de Bruijn lo discutió en su respuesta.

Pero en este caso, sabemos que los valores están en el rango [0, 255] y solo nos interesan los valores> = 128. Eso significa que podemos extraer fácilmente un solo bit que nos dirá si queremos un valor o no: cambiando los datos a la derecha son de 7 bits, nos quedan 0 bits o 1 bit, y solo queremos agregar el valor cuando tenemos 1 bit. Llamemos a este bit el "bit de decisión".

Al usar el valor 0/1 del bit de decisión como un índice en una matriz, podemos hacer un código que será igualmente rápido si los datos se ordenan o no. Nuestro código siempre agregará un valor, pero cuando el bit de decisión es 0, agregaremos el valor en algún lugar que no nos interese. Aquí está el código:

// Prueba

clock_t start = clock();
long long a[] = {0, 0};
long long sum;

for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        int j = (data[c] >> 7);
        a[j] += data[c];
    }
}

double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
sum = a[1];

Este código desperdicia la mitad de las adiciones, pero nunca tiene una falla de predicción de rama. Es tremendamente más rápido en datos aleatorios que la versión con una declaración if real.

Pero en mis pruebas, una tabla de búsqueda explícita fue ligeramente más rápida que esto, probablemente porque la indexación en una tabla de búsqueda fue un poco más rápida que el desplazamiento de bits. Esto muestra cómo mi código se configura y usa la tabla de búsqueda (sin imaginación llamada lut para "Tabla de búsqueda" en el código). Aquí está el código C ++:

// Declara y luego completa la tabla de búsqueda

int lut[256];
for (unsigned c = 0; c < 256; ++c)
    lut[c] = (c >= 128) ? c : 0;

// Use the lookup table after it is built
for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        sum += lut[data[c]];
    }
}

En este caso, la tabla de búsqueda tenía solo 256 bytes, por lo que cabe muy bien en un caché y todo fue rápido. Esta técnica no funcionaría bien si los datos fueran valores de 24 bits y solo quisiéramos la mitad de ellos ... la tabla de búsqueda sería demasiado grande para ser práctica. Por otro lado, podemos combinar las dos técnicas que se muestran arriba: primero cambiar los bits, luego indexar una tabla de búsqueda. Para un valor de 24 bits que solo queremos el valor de la mitad superior, podríamos desplazar los datos a la derecha en 12 bits, y quedarnos con un valor de 12 bits para un índice de tabla. Un índice de tabla de 12 bits implica una tabla de 4096 valores, lo que podría ser práctico.

La técnica de indexar en una matriz, en lugar de usar una instrucción if, se puede usar para decidir qué puntero usar. Vi una biblioteca que implementó árboles binarios, y en lugar de tener dos punteros con nombre (pLeft y pRight o lo que sea) tenía una matriz de punteros de longitud 2 y usé la técnica de "bit de decisión" para decidir cuál seguir. Por ejemplo, en lugar de:

if (x < node->value)
    node = node->pLeft;
else
    node = node->pRight;
this library would do something like:

i = (x < node->value);
node = node->link[i];

es una buena solución tal vez funcione

Manoj Kashyam
fuente
¿Con qué compilador / hardware de C ++ probó esto y con qué opciones de compilador? Me sorprende que la versión original no se vectorice automáticamente a un buen código SIMD sin ramas. ¿Habilitaste la optimización completa?
Peter Cordes
Una tabla de búsqueda de 4096 entradas parece una locura. Si cambia algunos bits, no solo puede usar el resultado LUT si desea agregar el número original. Todo esto suena como trucos tontos para evitar su compilador que no utiliza fácilmente técnicas sin ramificación. Más sencillo sería mask = tmp < 128 : 0 : -1UL;/total += tmp & mask;
Peter Cordes