assembly linux - ¿Por qué GCC no optimiza a * a * a * a * a * a *(a * a * a)*(a * a * a)?




compilar con (11)

Estoy haciendo una optimización numérica en una aplicación científica. Una cosa que noté es que GCC optimizará el poder de llamada pow(a,2) al compilarlo en a*a , pero el poder de llamada pow(a,6) no está optimizado y en realidad llamará a la función de biblioteca pow , que se ralentiza considerablemente el desempeño. (En contraste, Intel C ++ Compiler , ejecutable icc , eliminará la llamada de la biblioteca para pow(a,6) .

Lo que siento curiosidad es que cuando reemplacé pow(a,6) con a*a*a*a*a*a usando GCC 4.5.1 y las opciones " -O3 -lm -funroll-loops -msse4 ", usa 5 instrucciones mulsd :

movapd  %xmm14, %xmm13
mulsd   %xmm14, %xmm13
mulsd   %xmm14, %xmm13
mulsd   %xmm14, %xmm13
mulsd   %xmm14, %xmm13
mulsd   %xmm14, %xmm13

mientras que si escribo (a*a*a)*(a*a*a) , producirá

movapd  %xmm14, %xmm13
mulsd   %xmm14, %xmm13
mulsd   %xmm14, %xmm13
mulsd   %xmm13, %xmm13

lo que reduce el número de instrucciones de multiplicación a 3. icc tiene un comportamiento similar.

¿Por qué los compiladores no reconocen este truco de optimización?


Answers

Ningún póster ha mencionado todavía la contracción de las expresiones flotantes (norma ISO C, 6.5p8 y 7.12.2). Si el pragma FP_CONTRACT se establece en ON , se permite al compilador considerar una expresión como a*a*a*a*a*a como una sola operación, como si se evaluara exactamente con un solo redondeo. Por ejemplo, un compilador puede reemplazarlo por una función de potencia interna que sea más rápida y más precisa. Esto es particularmente interesante, ya que el programador controla en parte el comportamiento directamente en el código fuente, mientras que las opciones de compilación proporcionadas por el usuario final a veces pueden usarse incorrectamente.

El estado predeterminado del pragma FP_CONTRACT está definido por la implementación, de modo que un compilador puede realizar dichas optimizaciones de forma predeterminada. Por lo tanto, el código portátil que necesita seguir estrictamente las reglas de IEEE 754 debería configurarlo explícitamente en OFF .

Si un compilador no es compatible con este pragma, debe ser conservador al evitar cualquier optimización, en caso de que el desarrollador haya elegido OFF .

GCC no admite este pragma, pero con las opciones predeterminadas, asume que está ON ; por lo tanto, para objetivos con un FMA de hardware, si uno quiere evitar la transformación a*b+c a fma (a, b, c), debe proporcionar una opción como -ffp-contract=off (para establecer explícitamente el pragma a OFF ) o -std=c99 (para indicar a GCC que se ajuste a alguna versión estándar de C, aquí C99, siga el párrafo anterior). En el pasado, la última opción no impedía la transformación, lo que significa que GCC no estaba conforme con este punto: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=37845


Como señaló Lambdageek, la multiplicación de flotadores no es asociativa y puede obtener menos precisión, pero también cuando obtiene una mayor precisión puede argumentar en contra de la optimización, porque desea una aplicación determinista. Por ejemplo, en el cliente / servidor de simulación de juegos, donde cada cliente debe simular el mismo mundo en el que desea que los cálculos de punto flotante sean deterministas.


No habría esperado que este caso fuera optimizado en absoluto. No puede ser muy a menudo cuando una expresión contiene subexpresiones que se pueden reagrupar para eliminar operaciones completas. Espero que los escritores de compiladores inviertan su tiempo en áreas en las que es más probable que resulten en mejoras notables, en lugar de cubrir un caso de vanguardia poco frecuente.

Me sorprendió saber de las otras respuestas que esta expresión podría optimizarse con los conmutadores de compilación adecuados. O la optimización es trivial, o es un caso de vanguardia de una optimización mucho más común, o los escritores del compilador fueron extremadamente minuciosos.

No hay nada de malo en proporcionar sugerencias al compilador como lo has hecho aquí. Es una parte normal y esperada del proceso de micro-optimización para reorganizar las declaraciones y expresiones para ver qué diferencias traerán.

Si bien el compilador puede justificarse al considerar las dos expresiones para entregar resultados inconsistentes (sin los interruptores adecuados), no es necesario que esté sujeto a esa restricción. La diferencia será increíblemente pequeña, tanto que si la diferencia es importante para usted, en primer lugar no debería usar la aritmética de punto flotante estándar.


Lambdageek señala correctamente que debido a que la asociatividad no es válida para los números de punto flotante, la "optimización" de a*a*a*a*a*a (a*a*a)*(a*a*a) puede cambiar el valor. Esta es la razón por la cual C99 no lo permite (a menos que el usuario lo permita específicamente, a través de la bandera del compilador o pragma). En general, la suposición es que el programador escribió lo que hizo por una razón, y el compilador debería respetar eso. Si quieres (a*a*a)*(a*a*a) , escribe eso.

Eso puede ser un dolor para escribir, sin embargo; ¿Por qué el compilador no puede hacer [lo que consideras] lo correcto cuando usas pow(a,6) ? Porque sería lo incorrecto hacer. En una plataforma con una buena biblioteca matemática, pow(a,6) es significativamente más preciso que a*a*a*a*a*a (a*a*a)*(a*a*a) . Solo para proporcionar algunos datos, ejecuté un pequeño experimento en mi Mac Pro, midiendo el peor error al evaluar un ^ 6 para todos los números flotantes de precisión simple entre [1,2):

worst relative error using    powf(a, 6.f): 5.96e-08
worst relative error using (a*a*a)*(a*a*a): 2.94e-07
worst relative error using     a*a*a*a*a*a: 2.58e-07

Usar pow lugar de un árbol de multiplicación reduce el límite de error en un factor de 4 . Los compiladores no deben (y en general no hacen) "optimizaciones" que aumentan el error a menos que el usuario tenga licencia para hacerlo (por ejemplo, a través de -ffast-math ).

Tenga en cuenta que GCC proporciona __builtin_powi(x,n) como una alternativa a pow( ) , que debe generar un árbol de multiplicación en línea. Utilícelo si desea intercambiar precisión por rendimiento, pero no desea habilitar el cálculo rápido.


Otro caso similar: la mayoría de los compiladores no optimizarán a + b + c + d a (a + b) + (c + d) (esta es una optimización, ya que la segunda expresión se puede canalizar mejor) y la evaluará como se indica (es decir, como (((a + b) + c) + d) ). Esto también es debido a casos de esquina:

float a = 1e35, b = 1e-5, c = -1e35, d = 1e-5;
printf("%e %e\n", a + b + c + d, (a + b) + (c + d));

Esto genera 1.000000e-05 0.000000e+00


GCC realmente optimiza a * a * a * a * a * a * (a * a * a) * (a * a * a) cuando a es un número entero. He intentado con este comando:

$ echo 'int f(int x) { return x*x*x*x*x*x; }' | gcc -o - -O2 -S -masm=intel -x c -

Hay muchas banderas de gcc pero nada de lujos. Significan: Leer de stdin; utilizar el nivel de optimización de O2; lista de salida en lenguaje ensamblador en lugar de un binario; la lista debe usar la sintaxis del lenguaje ensamblador de Intel; la entrada está en lenguaje C (normalmente el lenguaje se deduce de la extensión del archivo de entrada, pero no hay una extensión de archivo cuando se lee desde la entrada estándar); y escribir a stdout.

Aquí está la parte importante de la salida. Lo he anotado con algunos comentarios que indican lo que está pasando en el lenguaje ensamblador:

    ; x is in edi to begin with.  eax will be used as a temporary register.
    mov    eax, edi     ; temp1 = x
    imul    eax, edi    ; temp2 = x * temp1
    imul    eax, edi    ; temp3 = x * temp2
    imul    eax, eax    ; temp4 = temp3 * temp3

Estoy usando el sistema GCC en Linux Mint 16 Petra, un derivado de Ubuntu. Aquí está la versión gcc:

$ gcc --version
gcc (Ubuntu/Linaro 4.8.1-10ubuntu9) 4.8.1

Como han señalado otros carteles, esta opción no es posible en punto flotante, porque la aritmética de punto flotante en realidad no es asociativa.


Porque la matemática de punto flotante no es asociativa . La forma en que agrupa los operandos en la multiplicación de punto flotante tiene un efecto en la precisión numérica de la respuesta.

Como resultado, la mayoría de los compiladores son muy conservadores en cuanto a reordenar los cálculos de punto flotante a menos que puedan estar seguros de que la respuesta seguirá siendo la misma, o a menos que usted les diga que no le importa la precisión numérica. Por ejemplo: la opción -fassociative-math de gcc que permite a gcc reasociar operaciones de punto flotante, o incluso la opción -ffast-math que permite compensaciones aún más agresivas de precisión contra velocidad.


gcc puede hacer esta optimización, incluso para números de punto flotante. Por ejemplo,

double foo(double a) {
  return a*a*a*a*a*a;
}

se convierte en

foo(double):
    mulsd   %xmm0, %xmm0
    movapd  %xmm0, %xmm1
    mulsd   %xmm0, %xmm1
    mulsd   %xmm1, %xmm0
    ret

con -O -funsafe-math-optimizations . Sin embargo, este reordenamiento viola el IEEE-754, por lo que requiere la bandera.

Los enteros firmados, como señaló Peter Cordes en un comentario, pueden hacer esta optimización sin optimizaciones -funsafe-math-optimizations ya que se mantienen exactamente cuando no hay un desbordamiento y si hay un desbordamiento se obtiene un comportamiento indefinido. Así que obtienes

foo(long):
    movq    %rdi, %rax
    imulq   %rdi, %rax
    imulq   %rdi, %rax
    imulq   %rax, %rax
    ret

con sólo -O . Para enteros sin signo, es aún más fácil, ya que funcionan con potencias de mod 2, por lo que se pueden reordenar libremente incluso en caso de desbordamiento.


Ya hay algunas buenas respuestas a esta pregunta, pero para completar, quisiera señalar que la sección aplicable del estándar C es 5.1.2.2.3 / 15 (que es la misma que la sección 1.9 / 9 en el Estándar de C ++ 11). Esta sección establece que los operadores solo pueden reagruparse si son realmente asociativos o conmutativos.


Las funciones de biblioteca como "pow" generalmente se diseñan cuidadosamente para producir el error mínimo posible (en el caso genérico). Esto generalmente se logra aproximando funciones con splines (según el comentario de Pascal, la implementación más común parece estar usando el algoritmo Remez )

Fundamentalmente la siguiente operación:

pow(x,y);

tiene un error inherente de aproximadamente la misma magnitud que el error en cualquier multiplicación o división individual .

Mientras que la siguiente operación:

float a=someValue;
float b=a*a*a*a*a*a;

tiene un error inherente que es más de 5 veces el error de una sola multiplicación o división (porque está combinando 5 multiplicaciones).

El compilador debe ser realmente cuidadoso con el tipo de optimización que está haciendo:

  1. Si la optimización de pow(a,6) a a*a*a*a*a*a puede mejorar el rendimiento, pero reducir drásticamente la precisión de los números de punto flotante.
  2. Si la optimización de a*a*a*a*a*a pow(a,6) puede reducir la precisión porque "a" era un valor especial que permite la multiplicación sin error (una potencia de 2 o un número entero pequeño)
  3. si se optimiza pow(a,6) a (a*a*a)*(a*a*a) o (a*a)*(a*a)*(a*a) todavía puede haber una pérdida de precisión en comparación con la función pow .

En general, usted sabe que para valores de punto flotante arbitrarios, "pow" tiene una mejor precisión que cualquier otra función que pueda escribir, pero en algunos casos especiales las multiplicaciones múltiples pueden tener una mejor precisión y rendimiento, es responsabilidad del desarrollador elegir qué es lo más apropiado. eventualmente comentando el código para que nadie más "optimice" ese código.

Lo único que tiene sentido (la opinión personal, y al parecer una opción en GCC sin ninguna optimización en particular o marca de compilación) para optimizar debe reemplazar el "pow (a, 2)" por "a * a". Eso sería lo único sensato que debería hacer un proveedor de compiladores.


Creo que en las CPU modernas las instrucciones de ensamblaje, si bien son la última capa visible para un programador que proporciona instrucciones de ejecución a una CPU, en realidad son varias capas de la ejecución real de la CPU.

Las CPU modernas son híbridos RISC / CISC que traducen las instrucciones CISC x86 en instrucciones internas que tienen un comportamiento más RISC. Además, existen analizadores de ejecución fuera de orden, predictores de ramificación, la "fusión de microoperaciones" de Intel que intentan agrupar las instrucciones en lotes más grandes de trabajo simultáneo (como el VLIW / Itanium titanic). Incluso hay límites de caché que podrían hacer que el código se ejecute más rápido para que Dios sepa por qué, si es más grande (tal vez el controlador del caché lo haga de manera más inteligente o lo mantenga más tiempo).

CISC siempre ha tenido una capa de traducción de ensamblado a microcódigo, pero el punto es que con las CPU modernas las cosas son mucho más complicadas. Con todas las propiedades de transistores adicionales en las plantas modernas de fabricación de semiconductores, las CPU probablemente pueden aplicar varios enfoques de optimización en paralelo y luego seleccionar el que ofrece la mejor velocidad. Las instrucciones adicionales pueden estar obligando a la CPU a utilizar una ruta de optimización que sea mejor que otras.

El efecto de las instrucciones adicionales probablemente depende del modelo / generación / fabricante de la CPU y no es probable que sea predecible. La optimización del lenguaje de ensamblaje de esta manera requeriría la ejecución contra muchas generaciones de arquitectura de CPU, tal vez utilizando rutas de ejecución específicas de la CPU, y solo sería deseable para las secciones de código realmente importantes, aunque si está haciendo ensamblaje, probablemente ya lo sepa.





gcc assembly floating-point compiler-optimization fast-math