¿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  #include  #include  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 = 128) sum += data[c]; } } double elapsedTime = static_cast(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 comstackció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 = 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.

Eres una víctima de error de predicción de twig .


¿Cuál es predicción de twig?

Considere una unión ferroviaria:

Imagen con licencia Imagen de Mecanismo, a través de 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 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 correctamente cada vez , el tren nunca tendrá que parar.
Si adivina mal con demasiada frecuencia , el tren perderá mucho tiempo deteniéndose, retrocediendo y reiniciando.


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

imagen2

Eres un procesador y ves una twig. 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 twig!

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

Si adivinas correctamente cada vez , la ejecución nunca tendrá que detenerse.
Si adivina incorrectamente con demasiada frecuencia , pasa mucho tiempo atascado, 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 twig 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 twig.

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

Lectura adicional: artículo de “Branch predictor” en Wikipedia .


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

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

Observe que los datos se distribuyen uniformemente entre 0 y 255. Cuando se ordenan los datos, aproximadamente la primera mitad de las iteraciones no ingresará a la instrucción if. Después de eso, todos ingresarán la statement 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 twig, 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 = NNNNN ... NNTTT ... TTT ... = 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 comstackdor no puede optimizar la twig 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 twig 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 twig 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 -ftree-vectorize o -ftree-vectorize en x64 puede 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 twig incluso en /Ox .

  • Intel Compiler 11 hace algo milagroso. Intercambia los dos bucles , con lo que izar la twig 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 comstackdor Intel el código sin sucursales, simplemente lo vectoriza a la derecha … y es tan rápido como con la twig (con el intercambio de bucles).

Esto demuestra que incluso los comstackdores modernos maduros pueden variar enormemente en su capacidad para optimizar el código …

Predicción de twig

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

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

Ahora, si miramos el código

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

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

En C , así C++ , la instrucción, que se comstackría directamente (sin ninguna optimización) en la instrucción de movimiento condicional en x86 , es el operador ternario ... ? ... : ... ... ? ... : ... Entonces, reescribimos la statement anterior en una statement equivalente:

 sum += data[c] >=128 ? data[c] : 0; 

Mientras mantenemos la legibilidad, podemos verificar el factor de aceleración.

En un modo de lanzamiento Intel Core i7 -2600K a 3.4 GHz y 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 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 ensamblaje x86 que generan. Para simplificar, utilizamos dos funciones max2 y max2 .

max1 usa la twig 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 instrucción cmovge . Pero la ganancia real es que max2 no involucra saltos de twig, 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 procesador x86 típico, 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. Esto se llama canalización .

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 dependen del resultado de la instrucción anterior; solo las últimas etapas necesitan el resultado. Por lo tanto, esperamos una fracción del tiempo de ejecución de una instrucción. Esta es la razón por la cual la versión de movimiento condicional es más lenta que la twig cuando la predicción es fácil.

El libro Computer Systems: A Programmer’s Perspective, segunda edición explica esto en detalle. Puede consultar la Sección 3.6.6 para Instrucciones de movimiento condicionales , todo el Capítulo 4 para Arquitectura de procesador , y la Sección 5.11.2 para un tratamiento especial para Penalizaciones de predicción de ramificaciones y errores de predicción errónea .

A veces, algunos comstackdores modernos pueden optimizar nuestro código para ensamblarlo con un mejor rendimiento, a veces algunos comstackdores no pueden (el código en cuestión usa el comstackdor nativo de Visual Studio). Conocer la diferencia de rendimiento entre la twig 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 comstackdor no puede optimizarlos automáticamente.

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

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

 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

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. El cachegrind herramienta Valgrind tiene un simulador de predicción de twigs habilitado mediante el --branch-sim=yes . Ejecutarlo sobre los ejemplos en esta pregunta, con el número de bucles externos reducidos a 10000 y comstackdos 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 que 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, la línea if (data[c] >= 128) está causando 164,050,007 twigs condicionales Bcm ( Bcm ) bajo el modelo de predicción de twigs de Bcm , 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) ... 

Vea el tutorial de rendimiento para más detalles.

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 rest de los cálculos. Debido a que la memoria es relativamente lenta, esta ‘carga’ ralentizará su progtwig.

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 bifurcación a veces sale terriblemente mal: en el peor de los casos, necesita volver atrás y esperar realmente una carga de memoria, lo que llevará una eternidad ( en otras palabras: la predicción de bifurcación defectuosa es mala, un recuerdo cargar 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ño ? 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 twig para garantizar que no se equivoca …

Bueno no exactamente… 🙂

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

 for (int i=0; i 

En este caso, es obvio para el comstackdor que la condición de límite nunca será golpeada. Al menos el comstackdor JIT de Microsoft (pero espero que Java haga cosas similares) lo notará y eliminará el cheque por completo. WOW - eso significa que no hay twig. 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]FFF a 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(); 

Como los datos se distribuyen entre 0 y 255 cuando se ordena la matriz, alrededor de la primera mitad de las iteraciones no ingresará la expresión -si (la statement if se comparte a continuación).

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

La pregunta es: ¿qué hace que la statement anterior no se ejecute en ciertos casos como en el caso de los datos ordenados? Aquí viene el “predictor de twig”. Un predictor de bifurcación es un circuito digital que intenta adivinar de qué manera irá una bifurcación (por ejemplo, una estructura if-then-else ) 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 twigs desempeñan un papel fundamental para lograr un alto rendimiento efectivo!

Hagamos un poco de benchmark para entenderlo mejor

El rendimiento de una statement de if 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, la indicación if 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 

A “ bad ” true-false pattern can make an if -statement up to six times slower than a “ good ” pattern! Of course, which pattern is good and which is bad depends on the exact instructions generated by the compiler and on the specific processor.

So there is no doubt about the impact of branch prediction on performance!

One way to avoid branch prediction errors is to build a lookup table, and index it using the data. Stefan de Bruijn discussed that in his answer.

But in this case, we know values are in the range [0, 255] and we only care about values >= 128. That means we can easily extract a single bit that will tell us whether we want a value or not: by shifting the data to the right 7 bits, we are left with a 0 bit or a 1 bit, and we only want to add the value when we have a 1 bit. Let’s call this bit the “decision bit”.

By using the 0/1 value of the decision bit as an index into an array, we can make code that will be equally fast whether the data is sorted or not sorted. Our code will always add a value, but when the decision bit is 0, we will add the value somewhere we don’t care about. 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(clock() - start) / CLOCKS_PER_SEC; sum = a[1]; 

This code wastes half of the adds but never has a branch prediction failure. It’s tremendously faster on random data than the version with an actual if statement.

But in my testing, an explicit lookup table was slightly faster than this, probably because indexing into a lookup table was slightly faster than bit shifting. This shows how my code sets up and uses the lookup table (unimaginatively called lut for “LookUp Table” in the code). Here’s the C++ code:

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

In this case, the lookup table was only 256 bytes, so it fits nicely in a cache and all was fast. This technique wouldn't work well if the data was 24-bit values and we only wanted half of them... the lookup table would be far too big to be practical. On the other hand, we can combine the two techniques shown above: first shift the bits over, then index a lookup table. For a 24-bit value that we only want the top half value, we could potentially shift the data right by 12 bits, and be left with a 12-bit value for a table index. A 12-bit table index implies a table of 4096 values, which might be practical.

EDIT: One thing I forgot to put in.

The technique of indexing into an array, instead of using an if statement, can be used for deciding which pointer to use. I saw a library that implemented binary trees, and instead of having two named pointers ( pLeft and pRight or whatever) had a length-2 array of pointers and used the "decision bit" technique to decide which one to follow. For example, instead of:

 if (x < node->value) node = node->pLeft; else node = node->pRight; 

this library would do something like:

 i = (x < node->value); node = node->link[i]; 

Here's a link to this code: Red Black Trees , Eternally Confuzzled

In the sorted case, you can do better than relying on successful branch prediction or any branchless comparison trick: completely remove the branch.

Indeed, the array is partitioned in a contiguous zone with data < 128 and another with data >= 128 . So you should find the partition point with a dichotomic search (using Lg(arraySize) = 15 comparisons), then do a straight accumulation from that point.

Something like (unchecked)

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

or, slightly more obfuscated

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

A yet faster approach, that gives an approximate solution for both sorted or unsorted is: sum= 3137536; (assuming a truly uniform distribution, 16384 samples with expected value 191.5) 🙂

The above behavior is happening because of Branch prediction.

To understand branch prediction one must first understand Instruction Pipeline :

Any instruction is broken into a sequence of steps so that different steps can be executed concurrently in parallel. This technique is known as instruction pipeline and this is used to increase throughput in modern processors. To understand this better please see this example on Wikipedia .

Generally, modern processors have quite long pipelines, but for ease let’s consider these 4 steps only.

  1. IF — Fetch the instruction from memory
  2. ID — Decode the instruction
  3. EX — Execute the instruction
  4. WB — Write back to CPU register

4-stage pipeline in general for 2 instructions. 4-stage pipeline in general

Moving back to the above question let’s consider the following instructions:

  A) if (data[c] >= 128) /\ / \ / \ true / \ false / \ / \ / \ / \ B) sum += data[c]; C) for loop or print(). 

Without branch prediction, the following would occur:

To execute instruction B or instruction C the processor will have to wait till the instruction A doesn’t reach till EX stage in the pipeline, as the decision to go to instruction B or instruction C depends on the result of instruction A. So the pipeline will look like this.

when if condition returns true: enter image description here

When if condition returns false: enter image description here

As a result of waiting for the result of instruction A, the total CPU cycles spent in the above case (without branch prediction; for both true and false) is 7.

So what is branch prediction?

Branch predictor will try to guess which way a branch (an if-then-else structure) will go before this is known for sure. It will not wait for the instruction A to reach the EX stage of the pipeline, but it will guess the decision and go to that instruction (B or C in case of our example).

In case of a correct guess, the pipeline looks something like this: enter image description here

If it is later detected that the guess was wrong then the partially executed instructions are discarded and the pipeline starts over with the correct branch, incurring a delay. The time that is wasted in case of a branch misprediction is equal to the number of stages in the pipeline from the fetch stage to the execute stage. Modern microprocessors tend to have quite long pipelines so that the misprediction delay is between 10 and 20 clock cycles. The longer the pipeline the greater the need for a good branch predictor .

In the OP’s code, the first time when the conditional, the branch predictor does not have any information to base up prediction, so the first time it will randomly choose the next instruction. Later in the for loop, it can base the prediction on the history. For an array sorted in ascending order, there are three possibilities:

  1. All the elements are less than 128
  2. All the elements are greater than 128
  3. Some starting new elements are less than 128 and later it become greater than 128

Let us assume that the predictor will always assume the true branch on the first run.

So in the first case, it will always take the true branch since historically all its predictions are correct. In the 2nd case, initially it will predict wrong, but after a few iterations, it will predict correctly. In the 3rd case, it will initially predict correctly till the elements are less than 128. After which it will fail for some time and the correct itself when it sees branch prediction failure in history.

In all these cases the failure will be too less in number and as a result, only a few times it will need to discard the partially executed instructions and start over with the correct branch, resulting in fewer CPU cycles.

But in case of a random unsorted array, the prediction will need to discard the partially executed instructions and start over with the correct branch most of the time and result in more CPU cycles compared to the sorted array.

An official answer would be from

  1. Intel – Avoiding the Cost of Branch Misprediction
  2. Intel – Branch and Loop Reorganization to Prevent Mispredicts
  3. Scientific papers – branch prediction computer architecture
  4. Books: JL Hennessy, DA Patterson: Computer architecture: a quantitative approach
  5. Articles in scientific publications: TY Yeh, YN Patt made a lot of these on branch predictions.

You can also see from this lovely diagram why the branch predictor gets confused.

2-bit state diagram

Each element in the original code is a random value

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

so the predictor will change sides as the std::rand() blow.

On the other hand, once it’s sorted, the predictor will first move into a state of strongly not taken and when the values change to the high value the predictor will in three runs through change all the way from strongly not taken to strongly taken.


In the same line (I think this was not highlighted by any answer) it’s good to mention that sometimes (specially in software where the performance matters—like in the Linux kernel) you can find some if statements like the following:

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

or similarly:

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

Both likely() and unlikely() are in fact macros that are defined by using something like the GCC’s __builtin_expect to help the compiler insert prediction code to favour the condition taking into account the information provided by the user. GCC supports other builtins that could change the behavior of the running program or emit low level instructions like clearing the cache, etc. See this documentation that goes through the available GCC’s builtins.

Normally this kind of optimizations are mainly found in hard-real time applications or embedded systems where execution time matters and it’s critical. For example, if you are checking for some error condition that only happens 1/10000000 times, then why not inform the compiler about this? This way, by default, the branch prediction would assume that the condition is false.

Frequently used Boolean operations in C++ produce many branches in compiled program. If these branches are inside loops and are hard to predict they can slow down execution significantly. Boolean variables are stored as 8-bit integers with the value 0 for false and 1 for true .

Boolean variables are overdetermined in the sense that all operators that have Boolean variables as input check if the inputs have any other value than 0 or 1 , but operators that have Booleans as output can produce no other value than 0 or 1 . This makes operations with Boolean variables as input less efficient than necessary. Consider example:

 bool a, b, c, d; c = a && b; d = a || b; 

This is typically implemented by the compiler in the following way:

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

This code is far from optimal. The branches may take a long time in case of mispredictions. The Boolean operations can be made much more efficient if it is known with certainty that the operands have no other values than 0 and 1 . The reason why the compiler does not make such an assumption is that the variables might have other values if they are uninitialized or come from unknown sources. The above code can be optimized if a and b have been initialized to valid values or if they come from operators that produce Boolean output. The optimized code looks like this:

 char a = 0, b = 1, c, d; c = a & b; d = a | b; 

char is used instead of bool in order to make it possible to use the bitwise operators ( & and | ) instead of the Boolean operators ( && and || ). The bitwise operators are single instructions that take only one clock cycle. The OR operator ( | ) works even if a and b have other values than 0 or 1 . The AND operator ( & ) and the EXCLUSIVE OR operator ( ^ ) may give inconsistent results if the operands have other values than 0 and 1 .

~ can not be used for NOT. Instead, you can make a Boolean NOT on a variable which is known to be 0 or 1 by XOR’ing it with 1 :

 bool a, b; b = !a; 

can be optimized to:

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

a && b cannot be replaced with a & b if b is an expression that should not be evaluated if a is false ( && will not evaluate b , & will). Likewise, a || b can not be replaced with a | b if b is an expression that should not be evaluated if a is true .

Using bitwise operators is more advantageous if the operands are variables than if the operands are comparisons:

 bool a; double x, y, z; a = x > y && z < 5.0; 

is optimal in most cases (unless you expect the && expression to generate many branch mispredictions).

That’s for sure!…

Branch prediction makes the logic run slower, because of the switching which happens in your code! It’s like you are going a straight street or a street with a lot of turnings, for sure the straight one is going to be done quicker!…

If the array is sorted, your condition is false at the first step: data[c] >= 128 , then becomes a true value for the whole way to the end of the street. That’s how you get to the end of the logic faster. On the other hand, using an unsorted array, you need a lot of turning and processing which make your code run slower for sure…

Look at the image I created for you below. Which street is going to be finished faster?

Branch Prediction

So programmatically, branch prediction causes the process to be slower…

Also at the end, it’s good to know we have two kinds of branch predictions that each is going to affect your code differently:

1. Static

2. Dynamic

Branch Prediction

Static branch prediction is used by the microprocessor the first time a conditional branch is encountered, and dynamic branch prediction is used for succeeding executions of the conditional branch code.

In order to effectively write your code to take advantage of these rules, when writing if-else or switch statements, check the most common cases first and work progressively down to the least common. Loops do not necessarily require any special ordering of code for static branch prediction, as only the condition of the loop iterator is normally used.

This question has already been answered excellently many times over. Still I’d like to draw the group’s attention to yet another interesting analysis.

Recently this example (modified very slightly) was also used as a way to demonstrate how a piece of code can be profiled within the program itself on Windows. Along the way, the author also shows how to use the results to determine where the code is spending most of its time in both the sorted & unsorted case. Finally the piece also shows how to use a little known feature of the HAL (Hardware Abstraction Layer) to determine just how much branch misprediction is happening in the unsorted case.

The link is here: http://www.geoffchappell.com/studies/windows/km/ntoskrnl/api/ex/profile/demo.htm

Branch-prediction gain!

It is important to understand that branch misprediction doesn’t slow down programs. The cost of a missed prediction is just as if branch prediction didn’t exist and you waited for the evaluation of the expression to decide what code to run (further explanation in the next paragraph).

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

Whenever there’s an if-else \ switch statement, the expression has to be evaluated to determine which block should be executed. In the assembly code generated by the compiler, conditional branch instructions are inserted.

A branch instruction can cause a computer to begin executing a different instruction sequence and thus deviate from its default behavior of executing instructions in order (ie if the expression is false, the program skips the code of the if block) depending on some condition, which is the expression evaluation in our case.

That being said, the compiler tries to predict the outcome prior to it being actually evaluated. It will fetch instructions from the if block, and if the expression turns out to be true, then wonderful! We gained the time it took to evaluate it and made progress in the code; if not then we are running the wrong code, the pipeline is flushed, and the correct block is run.

Visualization:

Let’s say you need to pick route 1 or route 2. Waiting for your partner to check the map, you have stopped at ## and waited, or you could just pick route1 and if you were lucky (route 1 is the correct route), then great you didn’t have to wait for your partner to check the map (you saved the time it would have taken him to check the map), otherwise you will just turn back.

While flushing pipelines is super fast, nowadays taking this gamble is worth it. Predicting sorted data or a data that changes slowly is always easier and better than predicting fast changes.

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

As what has already been mentioned by others, what behind the mystery is Branch Predictor .

I’m not trying to add something but explaining the concept in another way. There is a concise introduction on the wiki which contains text and diagram. I do like the explanation below which uses a diagram to elaborate the Branch Predictor intuitively.

In computer architecture, a branch predictor is a digital circuit that tries to guess which way a branch (eg an if-then-else structure) will go before this is known for sure. The purpose of the branch predictor is to improve the flow in the instruction pipeline. Branch predictors play a critical role in achieving high effective performance in many modern pipelined microprocessor architectures such as x86.

Two-way branching is usually implemented with a conditional jump instruction. A conditional jump can either be “not taken” and continue execution with the first branch of code which follows immediately after the conditional jump, or it can be “taken” and jump to a different place in program memory where the second branch of code is stored. It is not known for certain whether a conditional jump will be taken or not taken until the condition has been calculated and the conditional jump has passed the execution stage in the instruction pipeline (see fig. 1).

Figura 1

Based on the described scenario, I have written an animation demo to show how instructions are executed in a pipeline in different situations.

  1. Without the Branch Predictor.

Without branch prediction, the processor would have to wait until the conditional jump instruction has passed the execute stage before the next instruction can enter the fetch stage in the pipeline.

The example contains three instructions and the first one is a conditional jump instruction. The latter two instructions can go into the pipeline until the conditional jump instruction is executed.

without branch predictor

It will take 9 clock cycles for 3 instructions to be completed.

  1. Use Branch Predictor and don’t take a conditional jump. Let’s assume that the predict is not taking the conditional jump.

enter image description here

It will take 7 clock cycles for 3 instructions to be completed.

  1. Use Branch Predictor and take a conditional jump. Let’s assume that the predict is not taking the conditional jump.

enter image description here

It will take 9 clock cycles for 3 instructions to be completed.

The time that is wasted in case of a branch misprediction is equal to the number of stages in the pipeline from the fetch stage to the execute stage. Modern microprocessors tend to have quite long pipelines so that the misprediction delay is between 10 and 20 clock cycles. As a result, making a pipeline longer increases the need for a more advanced branch predictor.

As you can see, it seems we don’t have a reason not to use Branch Predictor.

It’s quite a simple demo that clarifies the very basic part of Branch Predictor. If those gifs are annoying, please feel free to remove them from the answer and visitors can also get the demo from git

It’s about branch prediction. ¿Qué es?

  • A branch predictor is one of the ancient performance improving techniques which still finds relevance into modern architectures. While the simple prediction techniques provide fast lookup and power efficiency they suffer from a high misprediction rate.

  • On the other hand, complex branch predictions –either neural based or variants of two-level branch prediction –provide better prediction accuracy, but they consume more power and complexity increases exponentially.

  • In addition to this, in complex prediction techniques the time taken to predict the branches is itself very high –ranging from 2 to 5 cycles –which is comparable to the execution time of actual branches.

  • Branch prediction is essentially an optimization (minimization) problem where the emphasis is on to achieve lowest possible miss rate, low power consumption, and low complexity with minimum resources.

There really are three different kinds of branches:

Forward conditional branches – based on a run-time condition, the PC (program counter) is changed to point to an address forward in the instruction stream.

Backward conditional branches – the PC is changed to point backward in the instruction stream. The branch is based on some condition, such as branching backwards to the beginning of a program loop when a test at the end of the loop states the loop should be executed again.

Unconditional branches – this includes jumps, procedure calls and returns that have no specific condition. For example, an unconditional jump instruction might be coded in assembly language as simply “jmp”, and the instruction stream must immediately be directed to the target location pointed to by the jump instruction, whereas a conditional jump that might be coded as “jmpne” would redirect the instruction stream only if the result of a comparison of two values in a previous “compare” instructions shows the values to not be equal. (The segmented addressing scheme used by the x86 architecture adds extra complexity, since jumps can be either “near” (within a segment) or “far” (outside the segment). Each type has different effects on branch prediction algorithms.)

Static/dynamic Branch Prediction : Static branch prediction is used by the microprocessor the first time a conditional branch is encountered, and dynamic branch prediction is used for succeeding executions of the conditional branch code.

Referencias

  • Branch predictor

  • A Demonstration of Self-Profiling

  • Branch Prediction Review

  • Branch Prediction

Besides the fact that the branch prediction may slow you down, a sorted array has another advantage:

You can have a stop condition instead of just checking the value, this way you only loop over the relevant data, and ignore the rest.
The branch prediction will miss only once.

  // sort backwards (higher values first) std::sort(data, data + arraySize, std::greater()); for (unsigned c = 0; c < arraySize; ++c) { if (data[c] < 128) { break; } sum += data[c]; } 

On ARM, there is no branch needed, because every instruction has a 4-bit condition field, which is tested at zero cost. This eliminates the need for short branches, and there would be no branch prediction hit. Therefore, the sorted version would run slower than the unsorted version on ARM, because of the extra overhead of sorting. The inner loop would look something like the following:

 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 

Sorted arrays are processed faster than an unsorted array, due to phenomena called the branch prediction.

Branch predictor is a digital circuit (in computer architecture) trying to predict which way a branch will go, improving the flow in the instruction pipeline. The circuit/computer predicts the next step and executes it.

Making a wrong prediction leads to going back to the previous step, and executing with another prediction. Assuming the prediction is correct, the code will continue to the next step. Wrong prediction results in repeating the same step, until correct prediction occurs.

The answer to your question is very simple.

In an unsorted array, the computer makes multiple predictions, leading to an increased chance of errors. Whereas, in sorted, the computer makes fewer predictions reducing the chance of errors. Making more prediction requires more time.

Sorted Array: Straight Road

 ____________________________________________________________________________________ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT 

Unsorted Array: Curved Road

 ______ ________ | |__| 

Branch prediction: Guessing/predicting which road is straight and following it without checking

 ___________________________________________ Straight road |_________________________________________|Longer road 

Although both the roads reach the same destination, the straight road is shorter, and the other is longer. If then you choose the other by mistake, there is no turning back, and so you will waste some extra time if you choose the longer road. This is similar to what happens on the computer, and I hope this helped you understand better.

Update: After what @Simon_Weaver said, I want to add another fact that… “it doesn’t make fewer predictions – it makes fewer incorrect predictions. It still has to predict for each time through the loop.”