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


Aquí hay una pieza de código C ++ que parece muy peculiar. Por alguna extraña razón, clasificar 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 compilación. 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.


Lo primero que pensé fue que la ordenación trae los datos al caché, pero luego pensé en lo tonto que es porque el arreglo 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.

21647
2018-06-27 13:51


origen


Respuestas:


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


¿Cuál es predicción de rama?

Considere una unión ferroviaria:

Licensed Image Imagen por Mecanismo, a través de Wikimedia Commons. Usado bajo el CC-By-SA 3.0 licencia.

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

Usted es el operador de un cruce y escucha que viene un tren. No tienes idea de qué manera se supone que debe ir. Detiene el tren para preguntarle al conductor qué dirección quieren. Y luego configura el interruptor apropiadamente.

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

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

  • Si lo has acertado, continúa.
  • Si adivinó mal, el capitán se detendrá, retrocederá y le gritará que apriete el interruptor. Luego puede reiniciarse por la otra ruta.

Si adivinas todo el tiempo, el tren nunca tendrá que parar.
Si adivinas mal a menudo, el tren pasará mucho tiempo deteniéndose, retrocediendo y reiniciando.


Considera un enunciado if: En el nivel del procesador, es una instrucción de bifurcación:

image2

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

Los procesadores modernos son complicados y tienen tuberías largas. Entonces tardan para siempre en "calentarse" y "disminuir la velocidad".

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

  • Si acertó, continúa ejecutando.
  • Si adivinó mal, necesita enjuagar la tubería y retroceder a la rama. Luego puede reiniciar por la otra ruta.

Si adivinas todo el tiempo, la ejecución nunca tendrá que detenerse.
Si adivinas mal a menudo, pasas mucho tiempo estancando, retrocediendo y reiniciando.


Esta es la predicción de bifurcación. Admito que no es la mejor analogía ya que el tren podría simplemente 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 por el otro camino? ¡Miras la historia pasada! Si el tren va a la izquierda el 99% del tiempo, entonces adivina que queda. Si se alterna, entonces alternas tus conjeturas. Si va de una manera cada 3 veces, adivinas lo mismo ...

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

La mayoría de las aplicaciones tienen ramas que se comportan bien. Por lo tanto, los predictores de bifurcaciones modernos suelen alcanzar tasas de aciertos> 90%. Pero cuando se enfrentan a ramas impredecibles sin patrones reconocibles, los predictores de ramas son prácticamente inútiles.

Otras lecturas: Artículo de "predicción de rama" en Wikipedia.


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

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

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

Esto es muy amigable con el pronosticador de bifurcación ya que la sucursal 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 cambiar 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 bifurcación se vuelve inútil porque no puede predecir datos aleatorios. Por lo tanto, probablemente habrá alrededor del 50% de errores de predicción. (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 ataques 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 al enunciado 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 Sucursal: Hay una gran diferencia entre los datos clasificados y no ordenados.
  • Con el Hack: No hay diferencia entre los datos clasificados y no ordenados.
  • En el caso de C ++, el truco 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 datos en bucles críticos. (como en este ejemplo)


Actualizar:

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

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

  • Intel Compiler 11 hace algo milagroso. Eso intercambia los dos bucles, con lo que izar la rama impredecible al bucle externo. Por lo tanto, no solo es inmune a las predicciones erróneas, sino que también es dos veces más rápido que cualquier otro que VC ++ y GCC puedan generar. En otras palabras, ICC aprovechó el bucle de prueba para vencer al punto de referencia ...

  • Si le das al compilador Intel el código sin sucursales, simplemente lo vectoriza a la derecha ... 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 ...


28564
2018-06-27 13:56



Predicción de rama

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


3635
2018-06-27 13:54



La razón por la que el rendimiento mejora drásticamente cuando se ordenan los datos es que se elimina la penalización de predicción de bifurcación, como se explica muy bien en MysticialLa respuesta de

Ahora, si miramos el código

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

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

En C, por lo tanto C++, la declaración, que compilaría directamente (sin ninguna optimización) en la instrucción de movimiento condicional en x86, es el operador ternario ... ? ... : .... Entonces, reescribimos la declaración anterior en una declaración 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 sucursal es impredecible, pero sufrimos un poco cuando es predecible. De hecho, cuando se usa un movimiento condicional, el rendimiento es el mismo independientemente del patrón de datos.

Ahora veamos más de cerca investigando el x86 montaje que generan. Para simplificar, utilizamos dos funciones max1 y max2.

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

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

max2 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 involucra 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 típico x86 procesador, la ejecución de una instrucción se divide en varias etapas. Aproximadamente, tenemos diferentes hardware para tratar con diferentes etapas. Entonces no tenemos que esperar que una instrucción termine para comenzar una nueva. Se llama pipelining.

En un caso de ramificación, la siguiente instrucción está determinada por la anterior, por lo que no podemos hacer pipelining. Tenemos que esperar o predecir.

En un caso de movimiento condicional, la instrucción de movimiento condicional de ejecución se divide en varias etapas, pero las etapas anteriores como Fetch y Decode no depende 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. 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 Sistemas informáticos: una perspectiva del programador, segunda edición explica esto en detalle. Puede verificar la Sección 3.6.6 para Instrucciones de movimiento condicional, todo el Capítulo 4 para Arquitectura del procesador, y la Sección 5.11.2 para un tratamiento especial para Predicción de ramas y sanciones por errores de predicción.

A veces, algunos compiladores modernos pueden optimizar nuestro código para ensamblarlo con un mejor rendimiento, a veces algunos compiladores no pueden (el código en cuestión usa 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.


2958
2018-06-28 02:14



Si le interesan aún más optimizaciones que se pueden hacer con 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 bucle, podemos cambiar este bucle de forma segura a:

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

Entonces, puedes ver que el if condicional es constante durante la ejecución del i loop, para que pueda izar el if fuera:

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 puede colapsarse en una sola expresión, suponiendo que el modelo de coma flotante lo permita (/ fp: se lanza rápido, por ejemplo)

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

Ese es 100.000 veces más rápido que antes


2024
2017-07-03 02:25



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

Ordenado

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

Sin clasificar:

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

Profundizando en la salida línea por línea producida por cg_annotate vemos para el ciclo en cuestión:

Ordenado

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

Sin clasificar:

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

Esto le permite identificar fácilmente la línea problemática: en la versión sin clasificar, if (data[c] >= 128) línea está causando 164,050,007 ramas condicionales mal predestinadas (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 un rendimiento nativo utilizando contadores de CPU.

perf stat ./sumtest_sorted

Ordenado

 Performance counter stats for './sumtest_sorted':

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

  11.827228330 seconds time elapsed

Sin clasificar:

 Performance counter stats for './sumtest_unsorted':

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

  28.935500947 seconds time elapsed

También puede hacer una anotación de código fuente con dissassembly.

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.


1687
2017-10-12 05:53



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

Una forma común de eliminar la predicción de bifurcación que he encontrado que funciona especialmente bien en los lenguajes administrados es una búsqueda de tablas en lugar de usar una bifurcación (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 guarde en la memoria caché del procesador
  2. Está ejecutando cosas en un bucle bastante cerrado y / o el procesador puede precargar los datos

Antecedentes y por qué

Pfew, ¿qué diablos se supone que significa eso?

Desde la perspectiva del procesador, tu memoria es lenta. Para compensar la diferencia de velocidad, construyen un par de cachés en su procesador (caché L1 / L2) que lo compensan. Entonces imagina que estás haciendo tus buenos cálculos y imagina que necesitas un pedazo de memoria. El procesador obtendrá su operación de "carga" y cargará la pieza de 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 debe cargar un dato e intenta cargarlo en el caché antes de que la operación llegue al caché. Como ya hemos visto, la predicción de ramas a veces sale terriblemente mal: en el peor de los casos, es necesario volver atrás y esperar una carga de memoria, lo que llevará una eternidad (en otras palabras: la predicción de bifurcación defectuosa es mala, ¡una carga de memoria después de que una predicción de bifurcación falla es simplemente horrible!)

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

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

Construyendo una mesa

Así que hemos descubierto que podemos crear una pequeña mesa. Lo siguiente que hay que hacer es obtener una función de búsqueda en su lugar. Las funciones de búsqueda son generalmente pequeñas funciones que usan un par de operaciones básicas enteras (y, o, xor, shift, add, remove y quizás multiplicar). Desea que su entrada sea traducida por la función de búsqueda a algún tipo de "clave única" en su tabla, que 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 mediante el uso de un 'Y': si lo mantenemos, lo hacemos Y con 7FFFFFFF; si queremos deshacernos de él, lo Y con 0. Observe también que 128 es un poder de 2 - entonces podemos seguir y hacer una tabla de enteros 32768/128 y llenarlo con un cero y un montón de 7FFFFFFFF's

Idiomas administrados

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

Bueno no exactamente... :-)

Ha habido bastante trabajo para eliminar esta rama para idiomas administrados. Por ejemplo:

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

En este caso, es obvio para el compilador que la condición de límite nunca será golpeada. Al menos el compilador JIT de Microsoft (pero espero que Java haga cosas similares) lo notará y eliminará el cheque 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 idiomas administrados, la clave es agregar un & 0x[something]FFFa su función de búsqueda para hacer que la verificación de límites sea predecible, y verla ir más rápido.

El resultado de este caso

// 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.Next(256);

//To keep the spirit of the code in-tact 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();

1158
2018-04-24 06:26



Como los datos se distribuyen entre 0 y 255 cuando se ordena la matriz, alrededor de la primera mitad de las iteraciones no ingresará al if-establecimiento (el if la declaració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 bifurcación es un circuito digital que intenta adivinar de qué manera una rama (por ejemplo, if-then-else estructura) irá antes de que esto se sepa con certeza. El propósito del predictor de bifurcación es mejorar el flujo en la tubería de instrucciones. ¡Los predictores de ramas desempeñan un papel fundamental para lograr un alto rendimiento efectivo!

Hagamos un poco de benchmark para entenderlo mejor

El rendimiento de un if-La declaración depende de si su condición tiene un patrón predecible. Si la condición siempre es verdadera o siempre es 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, el if-La declaración será mucho más costosa.

Midamos el rendimiento de este ciclo con diferentes condiciones:

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

Aquí están los tiempos del ciclo con diferentes patrones 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 "malo"Patrón verdadero-falso puede hacer una if-establecimiento hasta seis veces más lento que un "bueno"Patrón! Por supuesto, qué patrón es bueno y cuál es malo depende de las instrucciones exactas generadas por el compilador y en el procesador específico.

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


1033
2018-02-15 07:24