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

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

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 ( sí , 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:

• La sección "análisis de rendimiento" de esta respuesta resume las cosas. El resto de la respuesta se trata de optimizar un bucle que sesum += x[i] * y[i]desenrolla con múltiples acumuladores de vectores para ocultar la latencia de FMA. Es bastante técnico y de bajo nivel, pero le muestra el tipo de salida en lenguaje ensamblador que desea que haga su compilador y por qué es importante.
• ¿Por qué este código C ++ es más rápido que mi ensamblaje escrito a mano para probar la conjetura de Collatz? : esta respuesta popular que escribí explica cómo sostener el compilador a mano para hacer una mejor asm cuando sea posible. También algunos detalles de optimización de asm que le permiten vencer al compilador para pequeñas funciones / bucles en ese caso. IDK, por qué tiene tantos votos más que cualquiera de mis otras respuestas.
• ¿Cuál es la forma eficiente de contar los bits establecidos en una posición o inferior? : Un análisis de rendimiento de una secuencia de 6 insns para un problema interesante en el que un poco de mano en la fuente C llevó a gcc a mejorar el código. Algunas de mis otras respuestas son para secuencias de instrucciones aún más cortas.
• Calculadora de valor absoluto más rápida con SSE
• Problemas con ADC / SBB e INC / DEC en lazos cerrados en algunas CPU
• Rsqrt vectorizado rápido y recíproco con SSE / AVX dependiendo de la precisión
• ¿Ordenar estructuras de 64 bits con AVX?
• /programming//search?q=user%3A224132+throughput+latency+cycles

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.

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.

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,

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.