¿Qué códigos de operación son más rápidos a nivel de CPU? [cerrado]

19

En cada lenguaje de programación hay conjuntos de códigos de operación que se recomiendan sobre otros. He tratado de enumerarlos aquí, en orden de velocidad.

  1. Bitwise
  2. Suma / resta de enteros
  3. Multiplicación / división de enteros
  4. Comparación
  5. Flujo de control
  6. Suma / resta del flotador
  7. Float Multiplication / Division

Cuando necesite código de alto rendimiento, C ++ puede optimizarse manualmente en el ensamblaje, para usar instrucciones SIMD o un flujo de control más eficiente, tipos de datos, etc. Así que estoy tratando de entender si el tipo de datos (int32 / float32 / float64) o la operación utilizado ( *, +, &) afecta al rendimiento en el nivel de la CPU.

  1. ¿Una sola multiplicación es más lenta en la CPU que una adición?
  2. En la teoría MCU, aprende que la velocidad de los códigos de operación está determinada por la cantidad de ciclos de CPU que se necesitan para ejecutar. Entonces, ¿significa que multiplicar toma 4 ciclos y sumar toma 2?
  3. ¿Cuáles son exactamente las características de velocidad de los códigos de operación básicos de control matemático y control?
  4. Si dos códigos de operación toman el mismo número de ciclos para ejecutarse, ¿entonces ambos pueden usarse indistintamente sin ninguna ganancia / pérdida de rendimiento?
  5. Se agradece cualquier otro detalle técnico que pueda compartir sobre el rendimiento de la CPU x86
Robinicks
fuente
17
Esto se parece mucho a la optimización prematura, y recuerde que el compilador no genera lo que escribe, y realmente no desea escribir ensamblado a menos que realmente lo tenga también.
Roy T.
3
La multiplicación y división del flotador son cosas totalmente diferentes, no debes ponerlas en la misma categoría. Para los números de n bits, la multiplicación es un proceso O (n), y la división es un proceso O (nlogn). Esto hace que la división sea aproximadamente 5 veces más lenta que la multiplicación en las CPU modernas.
sam hocevar
1
La única respuesta real es "perfilarlo".
Tetrad
1
Ampliando la respuesta de Roy, el ensamblaje de optimización manual casi siempre será una pérdida neta, a menos que sea realmente excepcional. Las CPU modernas son bestias muy complejas y los buenos compiladores optimizadores realizan transformaciones de código que son completamente no obvias y no son triviales para el código a mano. Incluso para SSE / SIMD, siempre use intrínsecos en C / C ++ y deje que el compilador optimice su uso por usted. El uso del ensamblaje sin procesar deshabilita las optimizaciones del compilador y pierde mucho.
Sean Middleditch
No necesita optimizar manualmente el ensamblaje para usar SIMD. SIMD es muy útil para optimizar según la situación, pero existe una convención mayoritariamente estándar (funciona al menos en GCC y MSVC) para usar SSE2. En lo que respecta a su lista, en un procesador moderno multiplataforma superescalar, la dependencia de datos y la presión de registro causan más problemas que el rendimiento de enteros sin formato y, a veces, de coma flotante; Lo mismo ocurre con la localidad de datos. Por cierto, la división de enteros es lo mismo que la multiplicación en un x86 moderno
OrgnlDave

Respuestas:

26

Las guías de optimización de Agner Fog son excelentes. Tiene guías, tablas de tiempos de instrucción y documentos sobre la microarquitectura de todos los diseños recientes de CPU x86 (desde Intel Pentium). Vea también algunos otros recursos vinculados desde /programming//tags/x86/info

Solo por diversión, responderé algunas de las preguntas (números de CPU Intel recientes). La elección de operaciones no es el factor principal para optimizar el código (a menos que pueda evitar la división).

¿Una sola multiplicación es más lenta en la CPU que una adición?

Sí (a menos que sea por una potencia de 2). (3-4 veces la latencia, con solo un rendimiento por reloj en Intel). Sin embargo, no se salga de su camino para evitarlo, ya que es tan rápido como 2 o 3 agregados.

¿Cuáles son exactamente las características de velocidad de los códigos de operación básicos de control matemático y control?

Consulte las tablas de instrucciones y la guía de microarquitectura de Agner Fog si desea saber exactamente : P. Ten cuidado con los saltos condicionales. Los saltos incondicionales (como las llamadas a funciones) tienen una pequeña sobrecarga, pero no mucho.

Si dos códigos de operación toman el mismo número de ciclos para ejecutarse, ¿entonces ambos pueden usarse indistintamente sin ninguna ganancia / pérdida de rendimiento?

No, podrían competir por el mismo puerto de ejecución que otra cosa, o no. Depende de qué otras cadenas de dependencia pueda trabajar la CPU en paralelo. (En la práctica, no suele tomarse ninguna decisión útil. De vez en cuando surge que podría usar un desplazamiento de vectores o un desplazamiento aleatorio de vectores, que se ejecutan en diferentes puertos en las CPU de Intel. Pero cambio por bytes de todo el registro ( PSLLDQetc.) se ejecuta en la unidad aleatoria).

Se agradece cualquier otro detalle técnico que pueda compartir sobre el rendimiento de la CPU x86

Los documentos de microarquitectura de Agner Fog describen las canalizaciones de las CPU de Intel y AMD con suficiente detalle para determinar exactamente cuántos ciclos debe tomar un ciclo por iteración, y si el cuello de botella es el rendimiento de UOP, una cadena de dependencia o contención para un puerto de ejecución. Vea algunas de mis respuestas en StackOverflow, como esta o esta .

Además, http://www.realworldtech.com/haswell-cpu/ (y similar para diseños anteriores) es una lectura divertida si te gusta el diseño de CPU.

Aquí está su lista, ordenada para una CPU Haswell, basada en mis mejores huéspedes. Sin embargo, esta no es realmente una forma útil de pensar sobre las cosas para nada más que ajustar un bucle asm. Los efectos de predicción de caché / rama generalmente dominan, así que escriba su código para tener buenos patrones. Los números son muy manuales y tratan de tener en cuenta la alta latencia, incluso si el rendimiento no es un problema, o para generar más uops que obstruyen la tubería para que otras cosas sucedan en paralelo. Esp. los números de caché / rama están muy inventados. La latencia es importante para las dependencias transportadas en bucle, el rendimiento importa cuando cada iteración es independiente.

TL: DR estos números están compuestos según lo que estoy imaginando para un caso de uso "típico", en cuanto a compensaciones entre latencia, cuellos de botella en el puerto de ejecución y rendimiento de front-end (o paradas para cosas como fallas de sucursales ) No utilice estos números para ningún tipo de análisis de rendimiento serio .

  • 0.5 a 1 bit a bit / suma entera / sustracción /
    cambio y rotación (conteo de tiempo de compilación) /
    versiones vectoriales de todo esto (1 a 4 por rendimiento de ciclo, latencia de 1 ciclo)
  • 1 vector mínimo, máximo, comparar-igual, comparar-mayor (para crear una máscara)
  • 1.5 vectores aleatorios. Haswell y los más nuevos solo tienen un puerto aleatorio, y me parece que es común necesitar muchos barajaduras si es necesario, por lo que lo pongo un poco más alto para alentar a pensar en usar menos barajaduras. No son gratis, especialmente. si necesita una máscara de control pshufb de memoria.
  • 1.5 carga / almacenamiento (acierto de caché L1. Rendimiento mejor que latencia)
  • 1.75 Multiplicación entera (latencia 3c / una por 1c tput en Intel, 4c lat en AMD y solo una por 2c tput). Las constantes pequeñas son incluso más baratas usando LEA y / o ADD / SUB / shift . Pero, por supuesto, las constantes de tiempo de compilación siempre son buenas y, a menudo, pueden optimizarse para otras cosas. (Y el compilador a menudo puede reducir la fuerza de la multiplicación en un bucle tmp += 7en un bucle en lugar de tmp = i*7)
  • 1.75 algunos shuffle de vector de 256b (latencia adicional en insns que pueden mover datos entre 128b carriles de un vector AVX) (O de 3 a 7 en Ryzen, donde los barajos de cruce de carriles necesitan muchos más uops)
  • 2 fp add / sub (y versiones vectoriales de la misma) (1 o 2 por ciclo de rendimiento, latencia de 3 a 5 ciclos). Puede ser lento si tiene un cuello de botella en la latencia, por ejemplo, sumando una matriz con solo 1 sumvariable. (Podría ponderar esto y fp mul tan bajo como 1 o tan alto como 5 dependiendo del caso de uso).
  • 2 vectores fp mul o FMA. (x * y + z es tan barato como un mul o un add si compila con el soporte FMA habilitado).
  • 2 insertar / extraer registros de uso general en elementos vectoriales ( _mm_insert_epi8, etc.)
  • 2.25 vector int mul (elementos de 16 bits o pmaddubsw haciendo 8 * 8 -> 16 bits). Más barato en Skylake, con mejor rendimiento que el escalar mul
  • 2.25 cambio / rotación por conteo variable (latencia 2c, uno por rendimiento de 2c en Intel, más rápido en AMD o con BMI2)
  • 2.5 Comparación sin ramificación ( y = x ? a : b, o y = x >= 0) ( test / setcco cmov)
  • 3 int-> conversión flotante
  • 3 Flujo de control perfectamente predicho (rama pronosticada, llamada, retorno).
  • 4 int int mul (elementos de 32 bits) (2 uops, latencia 10c en Haswell)
  • División de 4 enteros o %por una constante de tiempo de compilación (sin potencia de 2).
  • 7 operaciones horizontales de vectores (por ejemplo, PHADDagregar valores dentro de un vector)
  • 11 (vector) FP Division (latencia 10-13c, uno por rendimiento de 7c o peor). (Puede ser barato si se usa raramente, pero el rendimiento es de 6 a 40 veces peor que FP mul)
  • 13? Control de flujo (rama mal predicha, quizás 75% predecible)
  • 13 división int ( , en realidad , es más lenta que la división FP y no se puede vectorizar). (tenga en cuenta que los compiladores se dividen por una constante usando mul / shift / add con una constante mágica , y div / mod por potencias de 2 es muy barato).
  • 16 (vector) FP sqrt
  • 25? carga (hit de caché L3). (Las tiendas de caché son más baratas que las cargas).
  • 50? FP trig / exp / log. Si necesita una gran cantidad de exp / log y no necesita una precisión completa, puede cambiar la precisión por la velocidad con un polinomio más corto y / o una tabla. También puede SIMD vectorizar.
  • 50-80? rama siempre impredecible, que cuesta 15-20 ciclos
  • 200-400? cargar / almacenar (error de caché)
  • 3000 ??? leer la página del archivo (hit de caché de disco del sistema operativo) (componiendo números aquí)
  • 20000 ??? página de lectura de disco (fallo de caché de disco del sistema operativo, SSD rápido) (número totalmente inventado)

Lo inventé totalmente basado en conjeturas . Si algo parece mal, es porque estaba pensando en un caso de uso diferente o por un error de edición.

El costo relativo de las cosas en las CPU AMD será similar, excepto que tienen desplazadores enteros más rápidos cuando el conteo de cambios es variable. Las CPU de la familia AMD Bulldozer son, por supuesto, más lentas en la mayoría de los códigos, por una variedad de razones. (Ryzen es bastante bueno en muchas cosas).

Tenga en cuenta que es realmente imposible reducir las cosas a un costo unidimensional . Además de errores de caché y errores de bifurcación, el cuello de botella en un bloque de código puede ser latencia, rendimiento total de UOP (frontend) o rendimiento de un puerto específico (puerto de ejecución).

Una operación "lenta" como la división FP puede ser muy barata si el código circundante mantiene a la CPU ocupada con otro trabajo . (el vector FP div o sqrt son 1 uop cada uno, solo tienen una latencia y un rendimiento deficientes. Solo bloquean la unidad de división, no todo el puerto de ejecución en el que se encuentra. Div entero es de varios uops). Entonces, si solo tiene una división de FP por cada ~ 20 mul y sumar, y hay otro trabajo para la CPU (por ejemplo, una iteración de bucle independiente), entonces el "costo" del FP div podría ser aproximadamente el mismo que un FP mul. Este es probablemente el mejor ejemplo de algo que es de bajo rendimiento cuando es todo lo que está haciendo, pero que se mezcla muy bien con otro código (cuando la latencia no es un factor), debido a los bajos niveles totales.

Tenga en cuenta que la división de enteros no es tan amigable con el código circundante: en Haswell, son 9 uops, con un rendimiento de 8-11c y latencia de 22-29c. (La división de 64 bits es mucho más lenta, incluso en Skylake). Por lo tanto, los números de latencia y rendimiento son algo similares a FP div, pero FP div es solo una uop.

Para ver ejemplos de análisis de una secuencia corta de insns para rendimiento, latencia y uops totales, vea algunas de mis respuestas SO:

IDK si otras personas escriben respuestas SO, incluido este tipo de análisis. Me resulta mucho más fácil encontrar el mío, porque sé que entro en detalles a menudo y puedo recordar lo que he escrito.

Peter Cordes
fuente
La "rama predicha" en 4 tiene sentido: ¿cuál debería ser realmente la "rama predicha" en 20-25? (Pensé que las ramas mal predichas (enumeradas alrededor de 13) eran mucho más caras que eso, pero es exactamente por eso que estoy en esta página, para aprender algo más cercano a la verdad, ¡gracias por la gran mesa!)
Matt
@ Matt: Creo que fue un error de edición y se suponía que era una "rama mal predicha". Gracias por señalar eso. Tenga en cuenta que 13 es para una rama pronosticada imperfectamente, no una rama siempre mal predicha, así que lo aclaré. Volví a hacer el saludo manual e hice algunas ediciones. : P
Peter Cordes
16

Depende de la CPU en cuestión, pero para una CPU moderna, la lista es algo como esto:

  1. Bitwise, suma, resta, comparación, multiplicación
  2. División
  3. Control de flujo (ver respuesta 3)

Dependiendo de la CPU, puede haber un costo considerable para trabajar con tipos de datos de 64 bits.

Tus preguntas:

  1. Nada o no apreciablemente en una CPU moderna. Depende de la CPU.
  2. Esa información es algo así como 20 a 30 años desactualizada (la escuela apesta, ahora tienes pruebas), las CPU modernas manejan un número variable de instrucciones por reloj, cuántas dependen de lo que el planificador proponga.
  3. La división es un poco más lenta que el resto, el flujo de control es muy rápido si la predicción de la rama es correcta y muy lenta si es incorrecta (algo así como 20 ciclos, depende de la CPU). El resultado es que una gran cantidad de código está limitado principalmente por el flujo de control. No haga con iflo que razonablemente puede hacer con la aritmética.
  4. No hay un número fijo para la cantidad de ciclos que toma una instrucción, pero a veces dos instrucciones diferentes pueden funcionar igual, ponerlas en otro contexto y tal vez no, ejecutarlas en una CPU diferente y es probable que vea un tercer resultado.
  5. Además del flujo de control, el otro gran desperdicio de tiempo es la pérdida de caché, cada vez que intente leer datos que no están en caché, la CPU tendrá que esperar a que se recupere de la memoria. En general, debe tratar de manejar las piezas de datos una al lado de la otra simultáneamente, en lugar de seleccionar datos de todo el lugar.

Y finalmente, si estás haciendo un juego, no te preocupes demasiado por todo esto, mejor concéntrate en hacer un buen juego que cortar los ciclos de la CPU.

aaaaaaaaaaaa
fuente
También me gustaría señalar que la FPU es bastante rápida: especialmente en Intel, por lo que el punto fijo solo es realmente necesario si desea resultados deterministas.
Jonathan Dickinson el
2
Solo pondría más énfasis en la última parte: hacer un buen juego. Ayuda a tener el código claro, por lo que 3. solo se aplica cuando realmente mides un problema de rendimiento. Siempre es fácil cambiar esos ifs en algo mejor si surge la necesidad. Por otro lado, 5. es más complicado: definitivamente estoy de acuerdo en que es un caso en el que realmente quieres pensar primero, ya que generalmente significa cambiar la arquitectura.
Luaan
3

Hice una prueba sobre la operación de números enteros que hizo un millón de bucles en x64_64, llegué a una breve conclusión como a continuación,

agregar --- 116 microsegundos

sub ---- 116 microsegundos

mul ---- 1036 microsegundos

div ---- 13037 microsegundos

los datos anteriores ya han reducido la sobrecarga inducida por el bucle,

hxiao
fuente
2

Los manuales del procesador Intel son una descarga gratuita desde su sitio web. Son bastante grandes, pero técnicamente pueden responder a su pregunta. El manual de optimización en particular es lo que busca, pero el manual de instrucciones también tiene los tiempos y las latencias para la mayoría de las principales líneas de CPU para instrucciones SIMD, ya que varían de un chip a otro.

En general, consideraría las ramas completas, así como la búsqueda de punteros (lista de enlaces de viajes, llamadas a funciones virtuales) como los mejores asesinos, pero los cpus x86 / x64 son muy buenos en ambos, en comparación con otras arquitecturas. Si alguna vez se transfiere a otra plataforma, verá cuánto problema pueden ser, si está escribiendo un código de alto rendimiento.

Zoner
fuente
+1, las cargas dependientes (persecución del puntero) es un gran problema. Un error de caché bloqueará futuras cargas incluso de comenzar. Tener muchas cargas de la memoria principal en vuelo a la vez proporciona un ancho de banda mucho mejor que tener una operación requiere que la anterior se complete por completo.
Peter Cordes