Pregunta ¿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) compilando en a*a, pero la llamada pow(a,6) no está optimizado y realmente llamará a la función de la biblioteca pow, lo que ralentiza en gran medida el rendimiento. (A diferencia de, Compilador Intel C ++ejecutable icc, eliminará la convocatoria de biblioteca pow(a,6).)

Lo que me interesa es que cuando lo 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 mulsd instrucciones:

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

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

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


1965
2018-06-21 18:49


origen


Respuestas:


Porque Floating Point Math no es asociativo. 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: el -fassociative-math opción de gcc que permite a gcc reasociar operaciones de punto flotante, o incluso -ffast-math opción que permite intercambios aún más agresivos de precisión contra velocidad.


2565
2018-06-22 15:32



Lambdageek correctamente señala 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 tu quieres (a*a*a)*(a*a*a), escribe 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 el incorrecto cosas que hacer. En una plataforma con una buena biblioteca de matemáticas, pow(a,6) es significativamente más preciso que cualquiera 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

Utilizando pow en 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 autorice (por ejemplo, mediante -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.


613
2018-06-22 22:39



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 se puede canalizar mejor) y evaluarla 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));

Estas salidas 1.000000e-05 0.000000e+00


152
2018-06-23 11:44



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 la biblioteca pow(). Esto no impide que los compiladores inteligentes traten pow especialmente y computarlo 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 poderes, pero desde encontrar la solución óptima es un problema NP-completo y esto solo vale la pena hacerlo para pequeños poderes de todos modos (en lugar de usar pow), no hay razón para preocuparse por los detalles.

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

Esto hace que sea fácil escribir los poderes (no es necesario deletrear 6 as 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 suma compensada (un ejemplo donde el orden de las 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:

por a*a*a*a*a*a,

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

por (a*a*a)*(a*a*a),

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

por power<6>(a),

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

74
2018-06-23 10:07



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 sabes qué tipo de programador  es decir, puede 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.


49
2018-03-29 06:51



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.


49
2018-06-27 21:03



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 FP_CONTRACT pragma está configurado para 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 de FP_CONTRACT pragma 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 decidido configurarlo para OFF.

GCC no es compatible con este pragma, pero con las opciones predeterminadas, supone que es ON; por lo tanto para los objetivos con un hardware FMA, si uno quiere evitar la transformación a*b+c Para fma (a, b, c), uno debe 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 conforme 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


27
2018-06-23 12:44



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.


26
2018-06-21 18:52



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.


26
2018-01-03 16:40



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 las funciones con splines (de acuerdo con el comentario de Pascal, la implementación más común parece estar usando Algoritmo de Remez)

fundamentalmente la siguiente operación:

pow(x,y);

tiene un error inherente de aproximadamente el 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 que 5 veces el error de una sola multiplicación o división (porque estás combinando 5 multiplicaciones).

El compilador 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*a eso mayo mejorar el rendimiento, pero reducir 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) en realidad 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)
  3. si 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 pow función.

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.


22
2017-10-01 19:33