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




10 Answers

Predicción de la rama.

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

vector arreglos programacion

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.



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

Comenzando con el bucle original:

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

Con el intercambio de bucles, podemos cambiar con seguridad este bucle a:

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

Luego, puede ver que el condicional if es constante durante la ejecución del bucle i , por lo que puede levantar el if :

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

Luego, verá que el bucle interno se puede contraer en una sola expresión, asumiendo que el modelo de punto flotante lo permite (/ fp: se lanza rápido, por ejemplo)

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

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




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

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

Este enfoque funciona en general si:

  1. Es una mesa pequeña y es probable que se almacene en caché en el procesador
  2. Está ejecutando cosas en un bucle muy ajustado y / o el procesador puede cargar previamente los datos

Antecedentes y por qué

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

Desde la perspectiva del procesador, su memoria es lenta. Para compensar la diferencia en la velocidad, construyen un par de cachés en su procesador (caché L1 / L2) que compensan eso. Así que imagina que estás haciendo tus buenos cálculos y descubre que necesitas un pedazo de memoria. El procesador obtendrá su operación de "carga" y cargará la memoria en la memoria caché, y luego utilizará la memoria caché para realizar el resto de los cálculos. Debido a que la memoria es relativamente lenta, esta 'carga' ralentizará su programa.

Al igual que la predicción de bifurcaciones, esto se optimizó en los procesadores Pentium: el procesador predice que necesita cargar una parte de los datos e intenta cargarlos en la memoria caché antes de que la operación llegue a la memoria caché. Como ya hemos visto, la predicción de bifurcación a veces es terriblemente errónea: en el peor de los casos, es necesario volver y esperar a que se cargue la memoria, lo que durará una eternidad ( en otras palabras: fallar la predicción de bifurcación es mala, una memoria cargar después de fallar una predicción de rama es simplemente horrible! ).

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

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

Construyendo una mesa

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

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

Idiomas gestionados

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

Bueno no exactamente... :-)

Ha habido bastante trabajo en la eliminación de esta rama para los idiomas administrados. Por ejemplo:

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

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

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



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

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

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

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

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

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

Este código desperdicia la mitad de los agregados, pero nunca tiene un error de predicción de ramificación. Es tremendamente más rápido en datos aleatorios que la versión con una declaración if real.

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

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

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

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

EDITAR: Una cosa que me olvidé de poner.

La técnica de indexación en una matriz, en lugar de usar una ifdeclaración, puede usarse para decidir qué puntero usar. Vi una biblioteca que implementaba árboles binarios, y en lugar de tener dos punteros con nombre ( pLefty pRightlo que sea) tenía una serie de punteros de longitud 2 y usaba 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




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

Para entender la predicción de la rama, primero se debe entender la tubería de instrucciones :

Cualquier instrucción se divide en una secuencia de pasos para que diferentes pasos puedan ejecutarse simultáneamente en paralelo. Esta técnica se conoce como canalización de instrucciones y se utiliza para aumentar el rendimiento en los procesadores modernos. Para entender esto mejor, por favor 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 - Decodificar la instrucción
  3. EX - Ejecutar la instrucción.
  4. WB - Escribe 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 la predicción de rama, ocurriría lo siguiente:

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

cuando si la condición se vuelve verdadera:

Cuando si la condición devuelve falso:

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

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

El predictor de rama intentará adivinar qué camino tomará una rama (una estructura if-then-else) antes de que esto se sepa con seguridad. No esperará a que la instrucción A llegue a la etapa EX de la tubería, pero adivinará la decisión e irá a esa instrucción (B o C en el caso de nuestro ejemplo).

En caso de una conjetura correcta, la tubería se ve algo como esto:

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

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

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

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

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

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

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




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

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

o similarmente:

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

Ambos likely()y unlikely()de hecho son macros que se definen utilizando 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 es compatible con otros elementos incorporados que podrían cambiar el comportamiento del programa en ejecución o emitir instrucciones de bajo nivel como borrar la memoria caché, etc. Consulte esta documentación que describe los componentes integrados de GCC disponibles.

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




¡Eso es seguro!...

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

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

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

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

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

1. Estático

2. dinámico

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

Para escribir efectivamente su código para aprovechar estas reglas, al escribir if-else o cambiar declaraciones, primero revise 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 ramificación estática, ya que normalmente solo se utiliza la condición del iterador de bucle.




Ganancia de predicción de rama!

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

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

Siempre que haya una declaració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 branch condicionales .

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

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

Visualización:

Digamos que necesita elegir la ruta 1 o la ruta 2. Esperando a que su compañero revise el mapa, se detuvo en ## y esperó, o simplemente puede elegir la ruta 1 y si tuvo suerte (la ruta 1 es la ruta correcta), entonces genial, no tuvo que esperar a que su compañero verificara el mapa (ahorró el tiempo que le habría costado verificarlo), de lo contrario, simplemente volverá.

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

 O      Route 1  /-------------------------------
/|\             /
 |  ---------##/
/ \            \
                \
        Route 2  \--------------------------------



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

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

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

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

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

Realmente hay tres tipos diferentes de ramas:

Ramas condicionales hacia adelante : en función de una condición de tiempo de ejecución, el PC (contador de programas) se cambia para apuntar a una dirección hacia adelante en el flujo de instrucciones.

Ramas condicionales hacia atrás : la PC se cambia para apuntar hacia atrás en el flujo de instrucciones. La bifurcación se basa en alguna condición, como la bifurcación hacia atrás al 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 podría codificarse como "jmpne" redirigiría el flujo de instrucciones solo si el resultado de una comparación de dos valores en las instrucciones anteriores de "comparar" muestra que los valores no son iguales. (El esquema de direccionamiento segmentado utilizado por la arquitectura x86 agrega complejidad adicional, ya que los saltos pueden ser "cerca" (dentro de un segmento) o "lejos" (fuera del segmento). Cada tipo tiene diferentes efectos en los algoritmos de predicción de bifurcación.)

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

Referencias:




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

Puede tener una condición de parada en lugar de solo verificar el valor, de esta manera solo hace un bucle sobre los datos relevantes e ignora el resto.
La predicción de rama solo fallará una vez.

 // sort backwards (higher values first)
 std::sort(data, data + arraySize, std::greater<int>());

 for (unsigned c = 0; c < arraySize; ++c) {
       if (data[c] < 128) {
              break;
       }
       sum += data[c];               
 }



Related