gcc flags

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

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

Lo que me interesa 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 de 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) , se producirá

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

que reduce el número de instrucciones de multiplicar 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 flotación no es asociativa y se puede obtener una menor precisión, pero también cuando se obtiene una mayor precisión se puede argumentar en contra de la optimización, porque se desea una aplicación determinista. Por ejemplo, en el cliente / servidor de simulación de juegos, donde cada cliente tiene que simular el mismo mundo, quiere que los cálculos de coma flotante sean deterministas.

Porque un número de coma 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 multiplicación de números de precisión arbitraria sin que haya ningún error asociado a esos números. La razón por la cual algunas personas no se dan cuenta de esto son quizás 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" mientras se realiza 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 pueden ejecutar) la idea de que la expresión C a * a * a * a * a * a no está funcionando con números ideales, el compilador GCC sería LIBRE para optimizar "a * a" * a * a * a * a "digamos" t = (a * a); t * t * t "que requiere un número menor de multiplicaciones. Pero desafortunadamente, el compilador de GCC no sabe si el programador que escribe el código piensa que "a" es un número con o sin un error. Y entonces GCC solo hará lo que parece el código fuente, porque eso es lo que GCC ve con su "ojo desnudo".

... una vez que sepas qué tipo de programador eres , puedes usar el interruptor "-ffast-math" para decirle a GCC que "¡Hola, GCC, sé lo que estoy haciendo!". Esto permitirá que GCC convierta a * a * a * a * a * a en una pieza de texto diferente - se ve diferente de a * a * a * a * a * a - pero todavía calcula un número dentro del intervalo de error de a * a * a * a * a * a. Esto está bien, ya que ya sabes que estás trabajando con intervalos, no con números ideales.

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

GCC realmente optimiza a * a * a * a * a * a a (a * a * a) * (a * a * a) cuando a es un número entero. Intenté 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 lujoso. Ellos quieren decir: Read from stdin; use el nivel de optimización de O2; lista de idiomas de ensamblaje de salida en lugar de un binario; la lista debe usar la sintaxis del lenguaje ensamblador de Intel; la entrada está en lenguaje C (por lo general, el idioma se deduce de la extensión de archivo de entrada, pero no hay extensión de archivo cuando se lee de stdin); y escribir a stdout.

Aquí está la parte importante de la salida. Lo he anotado con algunos comentarios que indican lo que está sucediendo 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 de 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 coma flotante, porque la aritmética de punto flotante no es realmente asociativa.

No hubiera esperado que este caso fuera optimizado en absoluto. No es frecuente que una expresión contenga subexpresiones que puedan reagruparse para eliminar operaciones completas. Esperaría que los escritores de compiladores inviertan su tiempo en áreas que tendrían más probabilidades de producir mejoras notables, en lugar de cubrir un caso marginal que rara vez se encuentra.

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

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

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

Debido a que las matemáticas de punto flotante no son asociativas . 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 sobre el reordenamiento de los cálculos de coma flotante, a menos que puedan estar seguros de que la respuesta será la misma, o a menos que 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 las operaciones de punto flotante, o incluso la opción -ffast-math que permite aún más intercambios agresivos de precisión contra velocidad.

No hay carteles que mencionen la contracción de las expresiones flotantes aún (norma ISO C, 6.5p8 y 7.12.2). Si el pragma FP_CONTRACT se establece en "on", el compilador puede considerar una expresión como a a a a a * a como una operación única, como si se evaluara exactamente con un solo redondeo. Por ejemplo, un compilador puede reemplazarlo por una función de alimentación interna que sea más rápida y más precisa. Esto es particularmente interesante ya que el programador controla directamente el comportamiento en el código fuente, mientras que las opciones del compilador proporcionadas por el usuario final a veces se pueden usar incorrectamente.

El estado predeterminado del pragma FP_CONTRACT está definido por la implementación, de modo que un compilador puede hacer tales optimizaciones por defecto. Por lo tanto, el código portátil que debe seguir estrictamente las reglas IEEE 754 debe establecerlo explícitamente en "off".

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

GCC no es compatible con este pragma. Sin embargo, todavía hace la transformación (a veces inválida) a * b + c a FMA (a, b, c) para objetivos con un hardware FMA: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=37845

Fortran (diseñado para computación científica) tiene un operador de energía incorporado, y hasta donde yo sé, los compiladores de Fortran normalmente optimizarán aumentar a poderes enteros de una manera similar a lo que describes. C / C ++ desafortunadamente no tiene un operador de energía, solo la función de biblioteca pow() . Esto no impide que los compiladores inteligentes traten el pow especialmente y lo computen de una manera más rápida para casos especiales, pero parece que lo hacen con menos frecuencia ...

Hace algunos años intenté hacer más conveniente calcular los poderes enteros de una manera óptima, y se me ocurrió lo siguiente. Es C ++, no C, y todavía depende de que el compilador sea un poco inteligente acerca de cómo optimizar / en línea cosas. De todos modos, espero que pueda ser ú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 forma óptima de calcular las potencias, pero dado que encontrar la solución óptima es un problema de NP completo y esto solo vale la pena para pequeñas potencias (en lugar de usar pow ), no hay razón para alboroto con el detalle.}

Entonces solo úsalo como power<6>(a) .

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

Probablemente también pueda olvidar que esto es C ++ y simplemente usarlo en el programa C (si compila con un compilador 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

Otro caso similar: la mayoría de los compiladores no optimizarán a + b + c + d a (a + b) + (c + d) (esto es una optimización ya que la segunda expresión puede canalizarse mejor) y la evaluarán como dada (es decir como (((a + b) + c) + d) ). Esto también se debe 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 produce 1.000000e-05 0.000000e+00

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

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

se convierte

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 IEEE-754, por lo que requiere la bandera.

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

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

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

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

fundamentalmente la siguiente operación:

pow(x,y);

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

Mientras la siguiente operación:

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

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

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

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

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

Lo único que tiene sentido (opinión personal, y aparentemente una elección en GCC que no sea una optimización particular o indicador del compilador) para optimizar debería reemplazar "pow (a, 2)" por "a * a". Esa sería la única cosa sensata que un proveedor de compiladores debería hacer.

Lambdageek señala correctamente que debido a que la asociatividad no es válida para los números de coma flotante, la "optimización" de a*a*a*a*a*a a (a*a*a)*(a*a*a) puede cambiar el valor. Es por eso que C99 no lo permite (a menos que el usuario lo permita específicamente, mediante el indicador del compilador o pragma). En general, la suposición es que el programador escribió lo que hizo por una razón, y el compilador debe respetar eso. Si quiere (a*a*a)*(a*a*a) , escriba eso.

Aunque puede ser doloroso escribirlo; ¿Por qué el compilador no puede hacer [lo que considera que es] lo correcto cuando usa pow(a,6) ? Porque sería lo incorrecto de 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 o (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 error vinculado por un factor de 4 . Los compiladores no deben (y generalmente no lo hacen) realizar "optimizaciones" que aumenten el error a menos que el usuario lo -ffast-math (p. Ej. -ffast-math ).

Tenga en cuenta que GCC proporciona __builtin_powi(x,n) como una alternativa a pow( ) , que debería generar un árbol de multiplicación en línea. Úselo si desea sacrificar la precisión por el rendimiento, pero no desea habilitar la matemática rápida.

gcc flags

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

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