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

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) comstackndo 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 comstackdor Intel C ++ , icc ejecutable, eliminará la llamada a la biblioteca para pow(a,6) .

Lo que me -O3 -lm -funroll-loops -msse4 es que cuando reemplacé pow(a,6) con a*a*a*a*a*a usando GCC 4.5.1 y 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 comstackdores no reconocen este truco de optimización?

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

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 comstackdor o pragma). En general, la suposición es que el progtwigdor escribió lo que hizo por una razón, y el comstackdor debe respetar eso. Si quiere (a*a*a)*(a*a*a) , escriba eso.

Aunque puede ser doloroso escribirlo; ¿Por qué el comstackdor 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 comstackdores 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 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.

Otro caso similar: la mayoría de los comstackdores 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

Fortran (diseñado para computación científica) tiene un operador de energía incorporado, y hasta donde yo sé, los comstackdores de Fortran normalmente optimizarán boost 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 comstackdores 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 comstackdor 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 struct power_impl; template struct power_impl { template static T calc(const T &x) { if (N%2 == 0) return power_impl::calc(x*x); else if (N%3 == 0) return power_impl::calc(x*x*x); return power_impl::calc(x)*x; } }; template<> struct power_impl<0> { template static T calc(const T &) { return 1; } }; template inline T power(const T &x) { return power_impl::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 sum compensada (un ejemplo en el que el orden de operaciones es esencial).

Probablemente también pueda olvidar que esto es C ++ y simplemente usarlo en el progtwig C (si comstack con un comstackdor C ++).

Espero que esto pueda ser útil.

EDITAR:

Esto es lo que obtengo de mi comstackdor:

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 

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 progtwigdores 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 comstackdor 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 comstackdor de GCC no sabe si el progtwigdor 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 progtwigdor 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.

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 -xc - 

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 syntax 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 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 comstackdor 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 comstackdor 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 progtwigdor controla directamente el comportamiento en el código fuente, mientras que las opciones del comstackdor 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 comstackdor 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 comstackdor no es compatible con este pragma, debe ser conservador evitando dicha optimización, en caso de que el desarrollador haya elegido establecerlo en OFF .

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

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.

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 comstackdores 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 comstackció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 comstackdor fueron extremadamente minuciosos.

No hay nada de malo en proporcionar pistas al comstackdor 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 comstackdor 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.

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 comstackdor debe ser muy cuidadoso con el tipo de optimización que está haciendo:

  1. 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.
  2. 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 pequeño número entero)
  3. 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 comstackdor) para optimizar debería reemplazar “pow (a, 2)” por “a * a”. Esa sería la única cosa sensata que un proveedor de comstackdores debería hacer.

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