it-swarm-es.tech

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

Aquí hay una pieza de código C++ que parece muy peculiar. Por alguna extraña razón, la clasificación de los datos 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 del lenguaje o del compilador. Así que lo probé en 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 algo similar pero menos extremo.


Mi primer pensamiento fue que la clasificación lleva los datos a la memoria caché, pero luego pensé en lo tonto que es porque la matriz se acaba de generar.

  • Que esta pasando?
  • ¿Por qué es más rápido procesar una matriz ordenada que una matriz sin clasificar?
  • El código está resumiendo algunos términos independientes, y el orden no debería importar.
22968
GManNickG

Eres víctima de falla la predicción .


¿Qué es la predicción de rama?

Considere un cruce de ferrocarril:

Image showing a railroad junction Imagen por Mecanismo, a través de Wikimedia Commons. Utilizado bajo la licencia CC-By-SA 3.0 .

Ahora, por el bien de la discusión, supongamos que esto se remonta a la década de 1800, antes de la comunicación por radio o de larga distancia.

Eres el operador de un cruce y escuchas que se acerca un tren. No tienes idea de cómo se supone que debe ir. Detienes el tren para preguntar al conductor qué dirección quieren. Y luego pones el interruptor adecuadamente.

Los trenes son pesados ​​y tienen mucha inercia. Por lo que tardan una eternidad en arrancar y disminuir la velocidad.

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

  • Si adivinaste bien, continúa.
  • Si adivinaste mal, el capitán se detendrá, retrocederá y te gritará que gires el interruptor. Entonces puede reiniciar el otro camino.

Si acertas cada vez , el tren nunca tendrá que detenerse.
Si se equivoca con demasiada frecuencia , el tren pasará mucho tiempo deteniéndose, retrocediendo y reiniciando.


Considere una sentencia if: En el nivel del procesador, es una instrucción de bifurcación:

Screenshot of compiled code containing an if statement

Eres un procesador y ves una rama. No tienes idea de por dónde irá. ¿Qué haces? Detiene la ejecución y espera a que se completen las instrucciones anteriores. Luego sigues por el camino correcto.

Los procesadores modernos son complicados y tienen tuberías largas. Por lo tanto, tardan una eternidad en "calentarse" y "disminuir la velocidad".

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

  • Si has acertado, sigues ejecutando.
  • Si adivinaste mal, debes vaciar la tubería y volver a la rama. Entonces puedes reiniciar el otro camino.

Si acertas cada vez , la ejecución nunca tendrá que detenerse.
Si adivinas mal a menudo , pasas mucho tiempo estancado, retrocediendo y reiniciando.


Esta es la predicción de la rama. Admito que no es la mejor analogía ya que el tren podría simplemente indicar 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ías estratégicamente para minimizar la cantidad de veces que el tren debe retroceder e ir por el otro camino? ¡Miras la historia pasada! Si el tren sale a la izquierda el 99% del tiempo, entonces adivina que se fue. Si se alterna, entonces alternas tus conjeturas. Si va de una manera cada 3 veces, adivinas lo mismo ...

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

La mayoría de las aplicaciones tienen ramas bien educadas. Por lo tanto, los pronosticadores de rama modernos generalmente alcanzarán> 90% de tasa de aciertos. Pero cuando se enfrentan a 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 indicó anteriormente, el culpable es esta afirmación if:

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

Observe que los datos se distribuyen uniformemente entre 0 y 255. Cuando los datos se clasifican, aproximadamente la primera mitad de las iteraciones no ingresarán a la instrucción if. Después de eso, todos entrarán en la sentencia 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 de un 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é se puede hacer?

Si el compilador no puede optimizar la rama en un movimiento condicional, puedes intentar algunos trucos si estás 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 bitwise.

(Tenga en cuenta que este truco no es estrictamente equivalente a la sentencia 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: Hay 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 hack es un poco más lento que con la rama cuando se ordenan los datos.

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


Actualización:

  • GCC 4.6.1 con -O3 o -ftree-vectorize en x64 puede generar un movimiento condicional. Por lo tanto, no hay diferencia entre los datos ordenados y no clasificados, ambos son rápidos.

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

  • Intel Compiler 11 hace algo milagroso. Es intercambia los dos bucles , elevando así la rama impredecible al bucle externo. ¡Así que no solo es inmune a las predicciones erróneas, sino que también es el doble de rápido que cualquier VC++ y GCC puede generar! En otras palabras, ICC aprovechó el ciclo de prueba para derrotar al punto de referencia ...

  • Si le da al Compilador de Intel el código sin sucursales, simplemente lo vectoriza de forma correcta ... y es tan rápido como con la rama (con el intercambio de bucles).

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

30104
Mysticial

Predicción de rama.

Con una matriz ordenada, la condición data[c] >= 128 es primero false para una racha de valores, luego se convierte en true para todos los valores posteriores. Eso es fácil de predecir. Con una matriz sin clasificar, usted paga el costo de la bifurcación.

3879
Daniel Fischer

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

Ahora, si nos fijamos en el código.

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

podemos encontrar que el significado de esta rama if... else... en particular es agregar algo cuando se cumple una condición. Este tipo de rama se puede transformar fácilmente en una declaración movimiento condicional , que se compilaría en una instrucción de movimiento condicional: cmovl, en un sistema x86. La rama y, por tanto, la penalización de predicción de rama potencial se eliminan.

En C, así C++, la declaración, que compilaría directamente (sin ninguna optimización) en la instrucción de movimiento condicional en x86, es el operador ternario ... ? ... : .... Así que 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 el modo de lanzamiento de Visual Studio 2010, 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 veamos más de cerca investigando el x86 Assembly que generan. Para simplificar, usamos dos funciones max1 y max2.

max1 usa la rama condicional if... else ...:

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

max2 usa el operador ternario ... ? ... : ...:

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

En una máquina x86-64, GCC -S genera el ensamblaje a continuación.

: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

max2 usa mucho menos código debido al uso de la instrucción cmovge. Pero la verdadera ganancia es que max2 no implica saltos de rama, jmp, que tendrían una penalización de rendimiento significativa si el resultado previsto no es correcto.

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

En un procesador típico de x86, la ejecución de una instrucción se divide en varias etapas. A grandes rasgos, tenemos diferentes hardware para tratar diferentes etapas. Así que no tenemos que esperar a que termine una instrucción para comenzar una nueva. Esto se llamacanalización.

En un caso de bifurcación, la siguiente instrucción está determinada por la anterior, por lo que no podemos realizar 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 las etapas anteriores como Fetch y Decode no dependen del resultado de la instrucción anterior; Sólo las últimas etapas necesitan el resultado. Así, esperamos una fracción del tiempo de ejecución de una instrucción. Esta es la razón por la que la versión de movimiento condicional es más lenta que la rama cuando la predicción es fácil.

El libro Sistemas informáticos: perspectiva de un programador, segunda edición explica esto en detalle. Puede consultar la Sección 3.6.6 para Instrucciones de movimiento condicional, todo el Capítulo 4 para Arquitectura del procesador, y la Sección 5.11.2 para un tratamiento especial para Predicción de rama y penalización por 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 es usar el compilador nativo de Visual Studio). Saber la diferencia de rendimiento entre la bifurcación y el movimiento condicional cuando es impredecible puede ayudarnos a escribir código con mejor rendimiento cuando el escenario se vuelve tan complejo que el compilador no puede optimizarlos automáticamente.

3125
WiSaGaN

Si tiene curiosidad acerca de 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 con seguridad este bucle 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 la condicional if es constante durante la ejecución del bucle i, por lo que puede izar la if:

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, asumiendo que el modelo de punto flotante lo permite (/ fp: se lanza rápido, por ejemplo)

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

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

2143
vulcan raven

Sin duda, algunos de nosotros estaríamos interesados ​​en maneras de identificar código que sea problemático para el predictor de rama de la CPU. La herramienta de Valgrind cachegrind tiene un simulador de predictor de rama, habilitado mediante el uso del indicador --branch-sim=yes. Al ejecutarlo sobre los ejemplos de esta pregunta, con el número de bucles externos reducido a 10000 y compilado con g++, se obtienen los siguientes resultados:

Ordenado:

==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_annotate vemos para el bucle en cuestión:

Ordenado:

          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 clasificada, la línea if (data[c] >= 128) está causando 164,050,007 ramificaciones condicionales mal pronosticadas (Bcm) bajo el modelo de predictor de ramificación 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 utilizando contadores de CPU.

perf stat ./sumtest_sorted

Ordenado:

 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 anotación 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)
...

Ver el tutorial de rendimiento para más detalles.

1784
caf

Acabo de leer 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 los idiomas administrados es una búsqueda en la tabla en lugar de usar una rama (aunque no la he probado en este caso).

Este enfoque funciona en general si:

  1. es una mesa pequeña y es probable que se almacene en caché en el procesador, y
  2. está ejecutando cosas en un bucle muy ajustado 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, un par de cachés están integrados en su procesador (caché L1/L2). Así que imagina que estás haciendo tus cálculos de Niza y descubre que necesitas un pedazo de memoria. El procesador obtendrá su operación de "carga" y cargará la memoria en la memoria caché, y luego utilizará la memoria caché para realizar 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 bifurcaciones, esto se optimizó en los procesadores Pentium: el procesador predice que necesita cargar una parte de los datos e intenta cargarlos en la memoria caché antes de que la operación llegue a la memoria caché. Como ya hemos visto, la predicción de bifurcación a veces es terriblemente errónea: en el peor de los casos, es necesario volver y esperar a que se cargue la memoria, lo que durará para siempre ( en otras palabras: fallar la predicción de bifurcación es mala, una carga de memoria después de un fallo de predicción de bifurcación 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ápido y todo estará bien.

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

Construyendo una mesa

Así que hemos descubierto que podemos crear una pequeña mesa. Lo siguiente que hay que hacer es tener una función de búsqueda en su lugar. Las funciones de búsqueda suelen ser funciones pequeñas que utilizan un par de operaciones enteras básicas (y, o, xor, desplazar, agregar, eliminar y quizás multiplicar). Desea que su entrada sea traducida por la función de búsqueda a algún tipo de 'clave única' en su tabla, que simplemente le da la respuesta de todo el trabajo que desea que haga.

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 'AND': si lo mantenemos, Y lo hacemos con 7FFFFFFF; si queremos deshacernos de él, Y lo hacemos con 0. También notamos que 128 es una potencia de 2, por lo que podemos seguir adelante y hacer una tabla de 32768/128 enteros y llenarla con un cero y una gran cantidad de 7FFFFFFFF.

Lenguajes gestionados

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

Bueno no exactamente... :-)

Ha habido bastante trabajo en la eliminación de 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 será alcanzada. Al menos el compilador JIT de Microsoft (pero espero que Java haga cosas similares) notará esto y eliminará la comprobación por completo. WOW, eso significa que no hay rama. Del mismo modo, se tratará con otros casos obvios.

Si tiene problemas con las búsquedas en idiomas administrados, la clave es agregar un & 0x[something]FFF a su función de búsqueda para hacer que la verificación de límites sea predecible, y ver cómo se hace 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();
1247
atlaste

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 instrucción if- (la declaración if 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 datos ordenados? Aquí viene el "predictor de rama". Un predictor de rama es un circuito digital que trata de adivinar qué camino tomará una rama (por ejemplo, una estructura if-then-else) antes de que esto se sepa con seguridad. El propósito del predictor de rama es mejorar el flujo en la línea de instrucciones. ¡Los predictores de rama juegan un papel crítico en el logro de un alto rendimiento efectivo!

Vamos a hacer algunas marcas de banco para entenderlo mejor

El rendimiento de una declaración if- 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 bifurcación en el procesador recogerá el patrón. Por otro lado, si el patrón es impredecible, la declaración if- será mucho más costosa.

Vamos a medir el rendimiento de este bucle con diferentes condiciones:

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

Aquí están los tiempos del bucle 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

¡Un patrón " malo " verdadero-falso puede hacer que una if- sea seis veces más lenta que un patrón " bueno "! Por supuesto, qué patrón es bueno y cuál es malo depende de las instrucciones exactas generadas por el compilador y del procesador específico.

¡Así que no hay duda sobre el impacto de la predicción de la rama en el rendimiento!

1118
Saqlain

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

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

Al utilizar el valor 0/1 del bit de decisión como un índice en una matriz, podemos hacer un código que será igual de rápido si los datos se clasifican o no. Nuestro código siempre agregará un valor, pero cuando el bit de decisión sea 0, agregaremos el valor en algún lugar que no nos importe. 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 los agregados pero nunca tiene un error de predicción de ramificación. 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 un poco 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 configura y usa la tabla de búsqueda (llamada de manera imaginativa lut para "LookUp Table" en el código). Aquí está el código de 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 solo tenía 256 bytes, por lo que encaja perfectamente 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 consulta sería demasiado grande para ser práctica. Por otro lado, podemos combinar las dos técnicas que se muestran arriba: primero desplace los bits y luego indexe una tabla de búsqueda. Para un valor de 24 bits que solo queremos el valor de la mitad superior, potencialmente podríamos cambiar 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 indexación en una matriz, en lugar de usar una declaración if, se puede usar para decidir qué puntero usar. Vi una biblioteca que implementaba árboles binarios, y en lugar de tener dos punteros con nombre (pLeft y pRight o lo que sea) tenía una serie 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

1039
steveha

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

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

Algo como (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 da una solución aproximada para ambos ordenados o sin clasificar es: sum= 3137536; (asumiendo una distribución verdaderamente uniforme, 16384 muestras con un valor esperado de 191.5) :-)

942
Yves Daoust

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

Para entender la predicción de la rama, primero se debe entender Canal de instrucciones :

Cualquier instrucción se divide en una secuencia de pasos para que los diferentes pasos se puedan ejecutar simultáneamente en paralelo. Esta técnica se conoce como canalización de instrucciones y se utiliza 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 - Recupera las instrucciones de la memoria.
  2. ID - Decodificar la instrucción
  3. EX - Ejecutar la instrucción.
  4. WB - Escribir de nuevo en el registro de la CPU

tubería de 4 etapas en general para 2 instrucciones. 4-stage pipeline in 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 la 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 la condición devuelve true: enter image description here

Cuando si la condición devuelve falso: enter image description here

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

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

El predictor de rama intentará adivinar qué camino tomará una rama (una estructura if-then-else) antes de que esto se sepa con seguridad. 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 conjetura correcta, la tubería se ve así: enter image description here

Si luego se detecta que la suposición fue incorrecta, las instrucciones parcialmente ejecutadas se descartan y la tubería comienza nuevamente con la bifurcación correcta, incurriendo en un retraso. El tiempo que se pierde en el caso de una predicción errónea de una sucursal es igual al número de etapas en la tubería desde la etapa de captación hasta la etapa de ejecución. Los microprocesadores modernos tienden a tener tuberías bastante largas, por lo que el retraso de la 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 ramificación .

En el código del OP, la primera vez que el 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 bucle for, puede basar la predicción en la historia. Para una matriz ordenada en orden ascendente, hay tres posibilidades:

  1. Todos los elementos son menos de 128.
  2. Todos los elementos son mayores que 128.
  3. Algunos elementos nuevos que comienzan son menos de 128 y más tarde se vuelven mayores de 128

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

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

En todos estos casos, la falla será mucho 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 dará como resultado menos ciclos de CPU.

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

765
Harsh Sharma

Una respuesta oficial sería de

  1. Intel - Evitando 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. Trabajos científicos - Predicción de rama arquitectura informática
  4. Libros: J.L. Hennessy, D.A. Patterson: Arquitectura de computadora: un enfoque cuantitativo
  5. Artículos en publicaciones científicas: T.Y. Yeh, Y.N. Patt hizo muchos de estos en las predicciones de la rama.

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

 2-bit state diagram

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

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

por lo que el predictor cambiará de lado a medida que la std::Rand() sopla.

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


669
Surt

En la misma línea (creo que esto no se resaltó con ninguna respuesta) es bueno mencionar que a veces (especialmente en el software donde el rendimiento es importante, como en el kernel de Linux) puede encontrar algunas declaraciones de tipo if como las siguientes:

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

o similarmente:

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

Tanto likely() como unlikely() son de hecho macros que se definen usando algo como el __builtin_expect del GCC para 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 es compatible con otros elementos incorporados 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 pasa por los componentes integrados 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á comprobando una condición de error que solo ocurre 1/10000000 veces, ¿por qué no informar al compilador sobre esto? De esta manera, de forma predeterminada, la predicción de rama supondría que la condición es falsa.

634
rkachach

Las operaciones booleanas utilizadas con frecuencia 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 0 para false y 1 para true.

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

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

Esto es típicamente implementado por el compilador 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 ser mucho más eficientes si se sabe con certeza que los operandos no tienen otros valores que 0 y 1. La razón por la cual el compilador no asume que las variables pueden tener otros valores si no están inicializadas o provienen de fuentes desconocidas. El código anterior puede optimizarse si a y b se han inicializado a valores válidos o si provienen de operadores que producen resultados booleanos. El código optimizado se ve así:

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

char se usa en lugar de bool para poder utilizar los operadores bitwise (& y |) en lugar de los operadores booleanos (&& y ||). Los operadores bitwise son instrucciones simples que toman solo un ciclo de reloj. El operador OR (|) funciona incluso si a y b tienen valores distintos a 0 o 1. El operador AND (&) y el operador EXCLUSIVE OR (^) pueden dar resultados inconsistentes si los operandos tienen valores diferentes a 0 y 1.

~ no puede ser usado para NOT. En su lugar, puede hacer un NOT booleano en una variable que se sabe que es 0 o 1 al XOR'ing con 1:

bool a, b;
b = !a;

se puede optimizar para:

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

a && b no se puede reemplazar con a & b si b es una expresión que no debe ser evaluada si a es false (&& no evaluará b, & will). Del mismo modo, a || b no puede reemplazarse con a | b si b es una expresión que no debe ser evaluada si a es true.

El uso de operadores bitwise 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 sucursales).

603
Maciej

¡Eso es seguro!...

La predicción de bifurcación hace que la lógica se ejecute más lentamente, debido a la conmutación que ocurre en su código. Es como si estuvieras en una calle recta o en una calle con muchos giros, ¡seguro que la recta se hará más rápido! ...

Si la matriz está ordenada, su condición es falsa en el primer paso: data[c] >= 128, luego se convierte en un verdadero valor 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 clasificada, necesitas un montón de giro y procesamiento que hacen que tu código se ejecute más lento, sin duda ...

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

 Branch Prediction

Así que programáticamente, predicción de rama hace que el proceso sea más lento ...

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

1. Estático

2. Dinámico

 Branch Prediction

El microprocesador usa la predicción de rama estática la primera vez que se encuentra una rama condicional, y la predicción de rama dinámica se usa para ejecuciones sucesivas del código de rama condicional.

Para escribir efectivamente su código para aprovechar estas reglas, al escribir if-else or switch statement, verifique los casos más comunes primero y trabaje progresivamente hasta los menos comunes. Los bucles no requieren necesariamente ningún orden especial de código para la predicción de ramificación estática, ya que normalmente solo se utiliza la condición del iterador de bucle.

280
Alireza

Esta pregunta ya ha sido contestada de manera excelente muchas veces. Sin embargo, me gustaría llamar la atención del grupo sobre otro interesante análisis.

Recientemente, este ejemplo (modificado muy levemente) también se usó como una forma de demostrar cómo se puede perfilar un fragmento de código dentro del propio programa en Windows. En el camino, el autor también muestra cómo usar los resultados para determinar dónde está gastando el código la mayor parte de su tiempo, tanto en el caso clasificado como en el no clasificado. 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 la cantidad de predicciones erróneas de las sucursales en el caso no clasificado.

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

262
ForeverLearning

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

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 utiliza un diagrama para elaborar el Predictor de Rama intuitivamente.

En la arquitectura de computadoras, un predictor de rama es un circuito digital que intenta adivinar qué camino tomará una rama (por ejemplo, una estructura if-then-else) antes de que esto se sepa con seguridad. El propósito del predictor de rama es mejorar el flujo en la línea de instrucciones. Los predictores de rama desempeñan un papel crítico en el logro de un alto rendimiento efectivo en muchas arquitecturas de microprocesadores modernos, como x86.

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

 figure 1

Basándome 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 ramificación, 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.

 without branch predictor

Tomará 9 ciclos de reloj para completar 3 instrucciones.

  1. Usa Branch Predictor y no tomes un salto condicional. Supongamos que la predicción es no tomando el salto condicional.

 enter image description here

Tomará 7 ciclos de reloj para completar 3 instrucciones.

  1. Usa Branch Predictor y da un salto condicional. Supongamos que la predicción es no tomando el salto condicional.

 enter image description here

Tomará 9 ciclos de reloj para completar 3 instrucciones.

El tiempo que se pierde en el caso de una predicción errónea de una sucursal es igual al número de etapas en la tubería desde la etapa de captación hasta la etapa de ejecución. Los microprocesadores modernos tienden a tener tuberías bastante largas, por lo que el retraso de la predicción errónea es de entre 10 y 20 ciclos de reloj. Como resultado, hacer que una tubería sea más larga aumenta la necesidad de un predictor de ramificación 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 muy básica de Branch Predictor. Si esos gifs son molestos, siéntase libre de eliminarlos de la respuesta y los visitantes también pueden obtener la demostración de git

176
Gearon

Ganancia de predicción de rama!

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

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

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

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 las instrucciones en orden (es decir, si la expresión es falsa, el programa omite el código del bloque if) 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. Recibirá instrucciones del bloque if, y si la expresión resulta ser verdadera, ¡entonces maravilloso! Ganamos el tiempo necesario para evaluarla y progresamos 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 puede elegir route1 y si tuvo suerte (la ruta 1 es la ruta correcta), entonces, genial, no tuvo que esperar a que su compañero verificara el mapa (ahorró el tiempo que le habría costado verificarlo), de lo contrario, simplemente volverá.

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

 O      Route 1  /-------------------------------
/|\             /
 |  ---------##/
/ \            \
                \
        Route 2  \--------------------------------
168
Tony Tannous

Se trata de la predicción de la 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 de potencia, sufren de una alta tasa de predicción errónea.

  • Por otro lado, las predicciones de ramificación complejas, ya sea basadas en neuronas o variantes de la predicción de ramificación 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 técnicas de predicción complejas, el tiempo que se tarda en predecir las ramas es, en sí mismo, muy alto (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 menor tasa de fallos posible, bajo consumo de energía y baja complejidad con los recursos mínimos.

Realmente hay tres tipos diferentes de ramas:

Reenviar ramas condicionales - basado en una condición de tiempo de ejecución, la PC (contador de programa) se cambia para apuntar a una dirección hacia adelante en el flujo de instrucciones.

Ramas condicionales hacia atrás - la PC se cambia para apuntar hacia atrás en el flujo de instrucciones. La bifurcación se basa en alguna condición, como la bifurcación hacia atrás al principio 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 podría 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 podría codificarse como "jmpne" redirigiría el flujo de instrucciones solo si el resultado de una comparación de dos valores en las instrucciones anteriores de "comparar" 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 "cerca" (dentro de un segmento) o "lejos" (fuera del segmento). Cada tipo tiene diferentes efectos en los algoritmos de predicción de bifurcación.)

Predicción de rama estática/dinámica : El microprocesador usa la predicción de rama estática la primera vez que se encuentra una rama condicional, y la predicción de rama dinámica se usa para ejecuciones sucesivas del código de rama condicional.

Referencias:

113
Farhad

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

Puede tener una condición de parada en lugar de solo verificar el valor, de esta manera solo repasará los datos relevantes e ignorará el resto.
La predicción de rama solo fallará 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];               
 }
107
Yochai Timmer

En ARM, no se necesita bifurcación, porque cada instrucción tiene un campo de condición de 4 bits, que se prueba a costo cero. Esto elimina la necesidad de sucursales cortas, y no habría un golpe de predicción de ramificación. Por lo tanto, la versión ordenada se ejecutaría más lentamente que la versión sin clasificar en ARM, debido a la sobrecarga adicional de la clasificación. El bucle interno se vería algo como lo siguiente:

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
103
Luke Hutchison

Las matrices ordenadas se procesan más rápido que una matriz sin clasificar, debido a fenómenos llamados predicción de rama.

El predictor de ramificación es un circuito digital (en arquitectura de computadora) que intenta predecir qué camino tomará una ramificación, mejorando el flujo en la línea de instrucciones. El circuito/computadora predice el siguiente paso y lo ejecuta.

Hacer una predicción incorrecta lleva a volver al paso anterior y a ejecutar otra predicción. Suponiendo que la predicción es correcta, el código continuará en el siguiente paso. La predicción incorrecta hace que se repita el mismo paso, hasta que se produzca la predicción correcta.

La respuesta a tu pregunta es muy simple.

En una matriz no clasificada, la computadora hace múltiples predicciones, lo que lleva a una mayor probabilidad de errores. Considerando que, en ordenado, la computadora hace menos predicciones reduciendo la posibilidad de errores. Hacer más predicciones requiere más tiempo.

Arreglo ordenado: camino recto

____________________________________________________________________________________
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT

Matriz Sin Clasificar: Carretera Curvada

______   ________
|     |__|

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

___________________________________________ Straight road
 |_________________________________________|Longer road

Aunque ambas carreteras alcanzan el mismo destino, la recta es más corta y la otra más larga. Si elige el otro por error, no hay vuelta atrás, por lo que perderá tiempo extra si elige la carretera más larga. 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 para cada momento a través del bucle.

92
Omkaar.K

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

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

Ordenar solo las secciones de elementos k completa el preprocesamiento en tiempo lineal en lugar de n.log(n).

#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" de 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.

14
user2297550

¡Porque está arreglado!

Es fácil recuperar y manipular datos ordenados que desordenados.

Al igual que me gusta cómo elijo prendas de ropa de las tiendas (ordenadas) y de mi armario (desordenado).

0
Arun Joshla