¿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, la clasificación de los datos hace que el código sea milagrosamente casi seis veces más rápido.

 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 estúpido que es, porque la matriz se acaba de generar.

  • Que esta pasando
  • ¿Por qué la matriz ordenada se procesa más rápido que la matriz sin clasificar?
  • El código resume algunos términos independientes, y el orden no importa.
22512
27 июня '12 в 16:51 2012-06-27 16:51 GManNickG se establece el 27 de junio de 2012 a las 4:51 2012-06-27 16:51
@ 26 respuestas

Eres víctima de la desviación de la ramificación .


¿Qué es la predicción de rama?

Considere la unión ferroviaria:

2019

27 июня '12 в 16:56 2012-06-27 16:56 Mysticial da la respuesta el 27 de junio de 2012 a las 4:56 2012-06-27 16:56

Predicción de las ramas.

Con una matriz ordenada, la condición de data[c] >= 128 es la primera false para la cadena de valor, y luego se vuelve true para todos los valores posteriores. Es fácil de predecir. Con una matriz no clasificada, usted paga los costos de ramificación.

3815
27 июня '12 в 16:54 2012-06-27 16:54 Daniel Fischer da la respuesta el 27 de junio de 2012 a las 4:54 pm 2012-06-27 16:54

La razón por la que el rendimiento mejora drásticamente cuando se clasifican los datos es que se elimina la penalización por la predicción de la rama, como lo explica Mysticial perfectamente.

Ahora, si nos fijamos en el código.

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

es posible que el significado de esta rama en particular if... else... es agregar algo cuando se cumpla la condición. Este tipo de rama se puede convertir fácilmente en un operador condicional , que se compilará en una instrucción de movimiento condicional: cmovl , en el sistema x86 . Se elimina la rama y, por lo tanto, la penalización potencial para predecir la rama.

En C , por lo tanto, C++ , el operador que se compilará directamente (sin ninguna optimización) en una instrucción de movimiento condicional en x86 es un operador ternario ...?... :... ...?... :... Por lo tanto, reescribimos la declaración anterior para que sea equivalente:

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

Al mantener la legibilidad, podemos comprobar el factor de aceleración.

Para Intel Core i7 -2600K @ 3.4 GHz y prueba de referencia del modo de lanzamiento de Visual Studio 2010 (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 fiable en varias pruebas. Obtenemos una aceleración significativa cuando el resultado de la ramificación es impredecible, pero sufrimos un poco cuando es predecible. De hecho, cuando se usa un movimiento condicional, el rendimiento sigue siendo el mismo independientemente del patrón de datos.

Ahora echemos un vistazo más de cerca, explorando la construcción 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 usa el operador ternario ...?... :... ...?... :... :

 int max2(int a, int b) { return a > b ? a : b; } 

En la computadora x86-64, el GCC -S construye un 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 incluye transiciones en max2 , jmp , lo que puede llevar a un rendimiento significativo de max2 si el resultado previsto es max2 .

Entonces, ¿por qué el movimiento condicional funciona mejor?

En un procesador x86 típico, la ejecución de x86 se divide en varias etapas. En términos generales, tenemos diferentes hardware para diferentes etapas. Por lo tanto, no necesitamos esperar al final de una instrucción para comenzar una nueva. Esto se llama tubería .

En el caso de la bifurcación, la siguiente instrucción está determinada por la anterior, por lo que no podemos realizar la canalización. Hay que esperar o predecir.

En el caso de un movimiento condicional, la ejecución del comando 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; Solo las etapas finales necesitan un resultado. Por lo tanto, estamos esperando una parte 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 Prospect for a Programmer, segunda edición, explica esto en detalle. Puede consultar la Sección 3.6.6 para ver las Instrucciones de movimiento condicional, todo el Capítulo 4 para la Arquitectura del procesador y la Sección 5.11.2 para obtener información sobre el manejo especial de las penalizaciones por predicciones y las predicciones erróneas.

A veces, algunos compiladores modernos pueden optimizar nuestro código para construir con mayor rendimiento, a veces algunos compiladores no pueden (este código utiliza su propio compilador de Visual Studio). Saber la diferencia en el rendimiento entre la bifurcación y el movimiento condicional, cuando es impredecible, puede ayudarnos a escribir código con mejor rendimiento cuando el script se vuelve tan complejo que el compilador no puede optimizarlos automáticamente.

3064
28 июня '12 в 5:14 2012-06-28 05:14 La respuesta está dada por WiSaGaN el 28 de junio de 2012 a las 5:14 am 2012-06-28 05:14

Si está interesado en aún más optimizaciones que se pueden realizar con este código, considere lo siguiente:

A partir del ciclo inicial:

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

Con la permutación del ciclo, podemos cambiar este ciclo de manera 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 la condición if es constante durante la ejecución del bucle i , por lo que puede retirarse 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 (por ejemplo, / fp: rápido)

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

Es 100.000 veces más rápido que antes.

2105
03 июля '12 в 5:25 2012-07-03 05:25 la respuesta se da a cuervo vulcan el 3 de julio de 2012 a las 5:25 am 2012-07-03 05:25

Sin lugar a dudas, algunos de nosotros nos interesaremos en las formas de identificar el código que es problemático para un procesador de predictor de CPU. La herramienta de cachegrind Valgrind tiene una sintaxis de rama de predictor que se activa utilizando el --branch-sim=yes . Al ejecutarlo siguiendo los ejemplos de esta pregunta, el número de bucles externos, reducido a 10,000 y compilado con g++ , da los siguientes resultados:

Ordenar por

 ==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% ) 

Volviendo a la salida lineal creada por cg_annotate , vemos para el ciclo en cuestión:

Ordenar por

  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 una versión no clasificada, la línea if (data[c] >= 128) causa Bcm ramificaciones condicionales predecidas incorrectamente ( Bcm ) como parte del modelo de predictor de rama cachegrind, mientras que solo llama a 10,006 en el ordenado versión


Alternativamente, en Linux, puede usar un subsistema de contador de rendimiento para realizar la misma tarea, pero con su propio rendimiento utilizando contadores de CPU.

 perf stat ./sumtest_sorted 

Ordenar por

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

Para más detalles, consulte el manual de rendimiento .

1758
12 окт. respuesta dada caf 12 oct. 2012-10-12 08:53 '12 a las 8:53 2012-10-12 08:53

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

La forma habitual de eliminar la predicción de ramificación, que me pareció que funcionaba particularmente bien en los idiomas administrados, es buscar en la tabla en lugar de usar ramificación (aunque en este caso no la verifiqué).

Este enfoque funciona en general si:

  1. esta es una tabla pequeña y lo más probable es que se almacene en caché en el procesador, y
  2. Está trabajando en un bucle bastante estrecho y / o el procesador puede precargar datos.

Antecedentes y por qué

Desde el punto de vista del procesador, su memoria es lenta. Para compensar la diferencia de velocidad, un par de cachés (caché L1 / L2) están integrados en su procesador. Así que imagine que está haciendo sus buenos cálculos y descubra que necesita un pedazo de memoria. El procesador realizará la operación de carga y cargará parte de la memoria en el caché, y luego utilizará el caché para realizar los cálculos restantes. Como la memoria es relativamente lenta, esta "carga" ralentizará su programa.

Al igual que la predicción de rama, se optimizó en los procesadores Pentium: el procesador predice que necesita cargar algunos 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 rama a veces sale terriblemente mal: en el peor de los casos, es necesario volver y esperar una carga de memoria que durará para siempre (en otras palabras: una predicción de rama fallida es mala, ¡la carga de memoria después de una falla de predicción de rama es terrible! ).

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

Lo primero que necesitamos saber es que hay poco? Aunque un tamaño más pequeño suele ser mejor, la regla de oro es seguir las tablas de búsqueda <= 4096 bytes. Como límite superior: si su tabla de referencia es más grande que 64 KB, probablemente debería revisarse.

Construir la mesa

Entonces, nos dimos cuenta de que podemos crear una mesa pequeña. Lo siguiente que hay que hacer es reemplazar la función de búsqueda. Las funciones de búsqueda suelen ser funciones pequeñas que utilizan varias operaciones de enteros básicos (y, o, xor, shift, add, remove y posiblemente multiplicación). Вы хотите, чтобы ваш ввод был переведен с помощью функции поиска в какой-то "уникальный ключ" в вашей таблице, который затем просто дает вам ответ на всю работу, которую вы хотели, чтобы он делал.