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

matriz dinamica java (21)

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:

Es una mesa pequeña y es probable que se almacene en caché en el procesador
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();

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.

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

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.

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

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.

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

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

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.

IF - Obtener las instrucciones de la memoria
ID - Decodificar la instrucción
EX - Ejecutar la instrucción.
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:

Todos los elementos son menos de 128.
Todos los elementos son mayores que 128.
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 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) :-)

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.

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

Una respuesta oficial sería de

Intel - Evitando el costo de la mala predicción de la sucursal
Intel: reorganización de sucursales y bucles para evitar errores de predicción
Trabajos científicos - arquitectura predictiva de ramas
Libros: JL Hennessy, DA Patterson: Arquitectura de computadora: un enfoque cuantitativo
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.

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.

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.

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.

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

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

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

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

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:

Predictor de rama
http://www.geoffchappell.com/studies/windows/km/ntoskrnl/api/ex/profile/demo.htm
Revisión de la Predicción de Rama
Predicción de rama

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