compilar - gcc compiler linux

¿Por qué GCC no optimiza aaaaaa(aaa)(aa*a)? (12)

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?

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.

Debido a que un número de punto flotante de 32 bits, como 1.024, no es 1.024. En una computadora, 1.024 es un intervalo: de (1.024-e) a (1.024 + e), donde "e" representa un error. Algunas personas no se dan cuenta de esto y también creen que * en a * a significa la multiplicación de números de precisión arbitraria sin que haya errores asociados a esos números. La razón por la que algunas personas no se dan cuenta de esto es tal vez los cálculos matemáticos que ejercieron en las escuelas primarias: trabajar solo con números ideales sin errores adjuntos, y creer que está bien simplemente ignorar "e" al realizar la multiplicación. No ven la "e" implícita en "float a = 1.2", "a * a * a" y códigos C similares.

Si la mayoría de los programadores reconocen (y sean capaces de ejecutar) la idea de que la expresión C a * a * a * a * a * a * a * a en realidad no funciona con los números ideales, el compilador GCC sería GRATIS para optimizar "a * a * a * a * a * a "en decir" t = (a * a); t * t * t "que requiere un número menor de multiplicaciones. Pero desafortunadamente, el compilador GCC no sabe si el programador que escribe el código piensa que "a" es un número con o sin error. Y así, GCC solo hará lo que parece el código fuente, porque eso es lo que GCC ve a simple vista.

... una vez que sepa qué tipo de programador es, puede usar el interruptor de "matemática avanzada" para decirle a GCC que "Oye, GCC, ¡sé lo que estoy haciendo!". Esto permitirá que GCC convierta a * a * a * a * a * a * en una parte diferente del texto, se ve diferente de a * a * a * a * a * a - pero aún calcula un número dentro del intervalo de error de a * a * a * a * a * a. Esto está bien, ya que ya sabe que está trabajando con intervalos, no con números ideales.

Fortran (diseñado para computación científica) tiene un operador de potencia incorporado, y que yo sepa, los compiladores de Fortran generalmente optimizarán el aumento a potencias enteras de manera similar a lo que usted describe. C / C ++ desafortunadamente no tiene un operador avanzado, solo la función de biblioteca pow() . Esto no impide que los compiladores inteligentes traten especialmente a pow y lo calculen de una manera más rápida para casos especiales, pero parece que lo hacen con menos frecuencia ...

Hace algunos años intentaba hacer que fuera más conveniente calcular potencias de enteros de una manera óptima, y se me ocurrió lo siguiente. Sin embargo, es C ++, no C, y aún depende de que el compilador sea algo inteligente sobre cómo optimizar / integrar cosas. De todos modos, espero que le resulte útil en la práctica:

template<unsigned N> struct power_impl; template<unsigned N> struct power_impl { template<typename T> static T calc(const T &x) { if (N%2 == 0) return power_impl<N/2>::calc(x*x); else if (N%3 == 0) return power_impl<N/3>::calc(x*x*x); return power_impl<N-1>::calc(x)*x; } }; template<> struct power_impl<0> { template<typename T> static T calc(const T &) { return 1; } }; template<unsigned N, typename T> inline T power(const T &x) { return power_impl<N>::calc(x); }

_{Aclaración para los curiosos: esto no encuentra la manera óptima de calcular los poderes, pero dado que encontrar la solución óptima es un problema NP-completo y esto, de todos modos, vale la pena hacerlo solo para los pequeños (en lugar de usar pow ), no hay razón para hacerlo. alboroto con el detalle.}

Luego solo úselo como power<6>(a) .

Esto hace que sea fácil escribir poderes (no es necesario deletrear 6 a s con parens), y le permite tener este tipo de optimización sin -ffast-math en caso de que tenga algo que dependa de la precisión, como una suma compensada (un ejemplo donde el orden de operaciones es esencial).

Probablemente también puede olvidar que esto es C ++ y simplemente usarlo en el programa C (si se compila con un compilador de C ++).

Espero que esto pueda ser útil.

EDITAR:

Esto es lo que obtengo de mi compilador:

Para a*a*a*a*a*a ,

movapd %xmm1, %xmm0 mulsd %xmm1, %xmm0 mulsd %xmm1, %xmm0 mulsd %xmm1, %xmm0 mulsd %xmm1, %xmm0 mulsd %xmm1, %xmm0

Para (a*a*a)*(a*a*a) ,

movapd %xmm1, %xmm0 mulsd %xmm1, %xmm0 mulsd %xmm1, %xmm0 mulsd %xmm0, %xmm0

Para el power<6>(a) ,

mulsd %xmm0, %xmm0 movapd %xmm0, %xmm1 mulsd %xmm0, %xmm1 mulsd %xmm0, %xmm1

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.

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:

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

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

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.

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

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.

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.

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.

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.

compilar - gcc compiler linux

¿Por qué GCC no optimiza a*a*a*a*a*a*(a*a*a)*(a*a*a)? (12)

¿Por qué GCC no optimiza aaaaaa(aaa)(aa*a)? (12)