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




11 Answers

Usted es una víctima de la predicción de la rama falla.

¿Qué es la predicción de rama?

Considere un cruce de ferrocarril:

de Mecanismo, vía 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 las comunicaciones de larga distancia o de radio.

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 en qué dirección quieren. Y luego pones el interruptor adecuadamente.

Los trenes son pesados ​​y tienen mucha inercia. Así que tardan una eternidad en arrancar y frenar.

¿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: a nivel de procesador, es una instrucción de bifurcación:

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. Entonces sigues por el camino correcto.

Los procesadores modernos son complicados y tienen tuberías largas. Así que 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 lo adivinó mal, debe vaciar la tubería y rodar hacia la rama. A continuación, puede reiniciar el otro camino.

Si acertas cada vez , la ejecución nunca tendrá que detenerse.
Si se equivoca con demasiada frecuencia , pasa mucho tiempo deteniéndose, 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, tratas de 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 ramificación 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 sobre "predictor de rama" en Wikipedia .

Como se indicó anteriormente, el culpable es esta declaración if:

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

Observe que los datos se distribuyen de manera uniforme entre 0 y 255. Cuando los datos se clasifican, aproximadamente la primera mitad de las iteraciones no ingresarán a la sentencia 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 ramificación 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, 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 datos ordenados y no clasificados.
  • En el caso de C ++, el hack es en realidad 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)

Actualizar:

  • GCC 4.6.1 con -ftree-vectorize 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. 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 bucle de prueba para derrotar al punto de referencia ...

  • Si le da al Compilador 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 ...

leer vector

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



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 a la en la respuesta de .

Ahora, si nos fijamos en el código.

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

podemos encontrar que el significado de esta rama particular if... else... es agregar algo cuando se cumple una condición. Este tipo de rama se puede transformar fácilmente en una declaración de 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 , por lo tanto en C++ , la declaración, que se 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 en 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 ensamblado x86 que generan. Para simplificar, usamos dos funciones max2 y max2 .

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

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

max2 utiliza 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 ganancia real 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 x86 típico, la ejecución de una instrucción se divide en varias etapas. A grandes rasgos, tenemos diferentes hardware para tratar diferentes etapas. Por lo tanto, no tenemos que esperar a que termine una instrucción para comenzar una nueva. Esto se llama pipelining .

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 ejecución de la instrucción de movimiento condicional 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 cual 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 lo explica en detalle. Puede consultar la Sección 3.6.6 para 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 la Predicción de sucursales y penalizaciones 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). Conocer 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.




Sin duda, algunos de nosotros estaríamos interesados ​​en formas de identificar el código que es problemático para el predictor de rama de la CPU. La herramienta Valgrind cachegrind tiene un simulador de predictor de rama, habilitado mediante el uso del --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:

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_annotate vemos para el 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 sin clasificar, la línea if (data[c] >= 128) está causando 164,050,007 ramificaciones condicionales Bcm ( 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

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




Como los datos se distribuyen entre 0 y 255 cuando se ordena la matriz, alrededor de la primera mitad de las iteraciones no ingresarán a 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 datos ordenados? Aquí viene el "predictor de rama". Un predictor de ramificación es un circuito digital que intenta adivinar qué camino if-then-elsetomará una ramificación (por ejemplo, una estructura) 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!

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

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 una ifdeclaración hasta 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!




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 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 (mediante Lg(arraySize) = 15comparaciones), luego hacer una acumulación directa desde ese punto.

Algo como (sin control)

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




Una respuesta oficial sería de

  1. Intel - Evitando el costo de la mala predicción de la sucursal
  2. Intel: reorganización de sucursales y bucles para evitar errores de predicción
  3. Trabajos científicos - arquitectura predictiva de ramas
  4. Libros: JL Hennessy, DA Patterson: Arquitectura de computadora: un enfoque cuantitativo
  5. Artículos en publicaciones científicas: TY Yeh, YN Patt hizo muchos de estos sobre predicciones de sucursales.

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

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

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

Así el predictor cambiará de lado según el std::rand()golpe.

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




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 0para falsey 1para 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 0o 1, pero los operadores que tienen salida booleana como salida no pueden producir otro valor que 0o 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 normalmente es 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 hacerse mucho más eficientes si se sabe con certeza que los operandos no tienen más valores que 0y 1. La razón por la que 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 se puede optimizar si ay bse han 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 utiliza en lugar de boolpara que sea posible 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 O ( |) funciona incluso si ay btienen valores distintos 0o 1. El operador AND ( &) y el operador OR EXCLUSIVO ( ^) pueden dar resultados inconsistentes si los operandos tienen valores distintos a 0y 1.

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

bool a, b;
b = !a;

Se puede optimizar para:

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

a && bno puede ser reemplazado por a & bsi bes una expresión que no debe ser evaluada si aes false( &&no evaluará b, &será). Del mismo modo, a || bno se puede reemplazar con a | bsi bes una expresión que no se debe evaluar si aes 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 la rama).




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 ligeramente) 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 la mayor parte del tiempo el código, tanto en el caso ordenado 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




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 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 (p. Ej., Una estructura if-then-else) antes de que esto se sepa con certeza. 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 modernas de microprocesadores canalizados, 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).

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

Tomará 9 ciclos de reloj para completar 3 instrucciones.

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

Tomará 7 ciclos de reloj para completar 3 instrucciones.

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

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




En ARM, no se necesita una rama, 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 sería similar al 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



Las matrices ordenadas se procesan más rápido que una matriz no clasificada, 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 sin clasificar, 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 llegan al mismo destino, la carretera 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 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.

Actualización: Después de lo que dijo @Simon_Weaver, quiero agregar otro hecho que ... "no hace menos predicciones, hace menos predicciones incorrectas. Todavía tiene que predecir cada vez a través del bucle".




Related

java c++ performance optimization branch-prediction