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

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.

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

¿Qué es la predicción de rama?

Considere 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:

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 ...

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.

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.

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.

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.

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();

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.

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

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) :-)

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.

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:

Cuando la condición devuelve falso:

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í:

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.

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.

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.

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.

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).

¡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?

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

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.

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

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).

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.

Tomará 9 ciclos de reloj para completar 3 instrucciones.

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

Tomará 7 ciclos de reloj para completar 3 instrucciones.

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

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

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  \--------------------------------

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.

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

• Predictor de rama

• Una demostración de autoperforación

• Revisión de predicción de rama

• Predicción de rama

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];               
 }

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 ...

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.

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.

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.

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é.

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