con - gcc linux




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

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.


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:

  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.


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


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.





fast-math