¿Por qué Clang optimiza x * 1.0 pero NO x + 0.0?

125

¿Por qué Clang optimiza el bucle en este código?

#include <time.h>
#include <stdio.h>

static size_t const N = 1 << 27;
static double arr[N] = { /* initialize to zero */ };

int main()
{
    clock_t const start = clock();
    for (int i = 0; i < N; ++i) { arr[i] *= 1.0; }
    printf("%u ms\n", (unsigned)(clock() - start) * 1000 / CLOCKS_PER_SEC);
}

pero no el bucle en este código?

#include <time.h>
#include <stdio.h>

static size_t const N = 1 << 27;
static double arr[N] = { /* initialize to zero */ };

int main()
{
    clock_t const start = clock();
    for (int i = 0; i < N; ++i) { arr[i] += 0.0; }
    printf("%u ms\n", (unsigned)(clock() - start) * 1000 / CLOCKS_PER_SEC);
}

(Etiquetado como C y C ++ porque me gustaría saber si la respuesta es diferente para cada uno).

usuario541686
fuente
2
¿Qué indicadores de optimización están actualmente activos?
Iwillnotexist Idonotexist
1
@IwillnotexistIdonotexist: Acabo de usar -O3, aunque no sé cómo comprobar qué se activa.
user541686
2
Sería interesante ver qué sucede si agrega -ffast-math a la línea de comando.
plugwash
static double arr[N]no está permitido en C; constlas variables no cuentan como expresiones constantes en ese idioma
MM
1
[Inserte un comentario sarcástico sobre cómo C no es C ++, aunque ya lo haya llamado.]
user253751

Respuestas:

164

El estándar IEEE 754-2008 para aritmética de coma flotante y el estándar de aritmética independiente del lenguaje (LIA) ISO / IEC 10967, Parte 1, responden por qué esto es así.

IEEE 754 § 6.3 El bit de signo

Cuando una entrada o un resultado es NaN, este estándar no interpreta el signo de un NaN. Sin embargo, tenga en cuenta que las operaciones en cadenas de bits (copy, negate, abs, copySign) especifican el bit de signo de un resultado NaN, a veces basado en el bit de signo de un operando NaN. El predicado lógico totalOrder también se ve afectado por el bit de signo de un operando NaN. Para todas las demás operaciones, este estándar no especifica el bit de signo de un resultado de NaN, incluso cuando solo hay una entrada de NaN o cuando el NaN se produce a partir de una operación no válida.

Cuando ni las entradas ni el resultado son NaN, el signo de un producto o cociente es el OR exclusivo de los signos de los operandos; el signo de una suma, o de una diferencia x - y considerada como una suma x + (−y), difiere de, como máximo, uno de los signos de los sumandos; y el signo del resultado de las conversiones, la operación de cuantización, las operaciones roundTo-Integral y roundToIntegralExact (ver 5.3.1) es el signo del primer o único operando. Estas reglas se aplicarán incluso cuando los operandos o resultados sean cero o infinitos.

Cuando la suma de dos operandos con signos opuestos (o la diferencia de dos operandos con signos similares) es exactamente cero, el signo de esa suma (o diferencia) será +0 en todos los atributos de dirección de redondeo, excepto roundTowardNegative; bajo ese atributo, el signo de una suma cero exacta (o diferencia) será −0. Sin embargo, x + x = x - (−x) conserva el mismo signo que x incluso cuando x es cero.

El caso de la suma

En el modo de redondeo predeterminado (Round-to-Nearest, Ties-to-Even) , vemos que x+0.0produce x, EXCEPTO cuando xes -0.0: En ese caso, tenemos una suma de dos operandos con signos opuestos cuya suma es cero, y §6.3 párrafo 3 reglas que produce esta adición +0.0.

Como +0.0no es idéntico en bits a la original -0.0, y ese -0.0es un valor legítimo que puede ocurrir como entrada, el compilador está obligado a poner el código que transformará los ceros negativos potenciales +0.0.

El resumen: en el modo de redondeo predeterminado, en x+0.0, six

  • no lo es -0.0 , entonces xsí mismo es un valor de salida aceptable.
  • es decir -0.0 , entonces el valor de salida debe ser +0.0 , que no es idéntico a nivel de bits -0.0.

El caso de la multiplicación

En el modo de redondeo predeterminado , no ocurre tal problema con x*1.0. Si x:

  • es un (sub) número normal, x*1.0 == xsiempre.
  • es decir +/- infinity, entonces el resultado es +/- infinitydel mismo signo.
  • es NaN, entonces de acuerdo a

    IEEE 754 § 6.2.3 Propagación de NaN

    Una operación que propaga un operando NaN a su resultado y tiene un solo NaN como entrada debería producir un NaN con la carga útil de la entrada NaN si es representable en el formato de destino.

    lo que significa que NaN*1.0se recomienda que el exponente y la mantisa (aunque no el signo) no se modifiquen desde la entrada NaN. El signo no está especificado de acuerdo con §6.3p1 anterior, pero una implementación puede especificar que sea idéntico a la fuente NaN.

  • es decir +/- 0.0, el resultado es un 0con su bit de signo XORed con el bit de signo de 1.0, de acuerdo con §6.3p2. Como el bit de signo de 1.0es 0, el valor de salida no cambia desde la entrada. Por lo tanto, x*1.0 == xincluso cuando xes un cero (negativo).

El caso de la resta

En el modo de redondeo predeterminado , la resta x-0.0también es un no-op, porque es equivalente a x + (-0.0). Si xes

  • es decir NaN, §6.3p1 y §6.2.3 se aplican de manera muy similar a la suma y multiplicación.
  • es decir +/- infinity, entonces el resultado es +/- infinitydel mismo signo.
  • es un (sub) número normal, x-0.0 == xsiempre.
  • es -0.0, entonces, según §6.3p2 tenemos " el signo de una suma, o de una diferencia x - y considerada como una suma x + (−y), difiere de a lo sumo uno de los signos de los sumandos; ". Esto nos obliga a asignar -0.0como resultado de (-0.0) + (-0.0), porque -0.0difiere en el signo de ninguno de los sumandos, mientras que +0.0difiere en el signo de dos de los sumandos, en violación de esta cláusula.
  • es decir +0.0, esto se reduce al caso de adición (+0.0) + (-0.0)considerado anteriormente en El caso de la adición , que según §6.3p3 se dicta que da +0.0.

Dado que para todos los casos el valor de entrada es legal como la salida, es permisible considerar x-0.0un no-op y x == x-0.0una tautología.

Optimizaciones de cambio de valor

El estándar IEEE 754-2008 tiene la siguiente cita interesante:

IEEE 754 § 10.4 Significado literal y optimizaciones de cambio de valor

[...]

Las siguientes transformaciones que cambian el valor, entre otras, preservan el significado literal del código fuente:

  • Aplicando la propiedad de identidad 0 + x cuando x no es cero y no es una señalización de NaN y el resultado tiene el mismo exponente que x.
  • Aplicando la propiedad de identidad 1 × x cuando x no es una señal de NaN y el resultado tiene el mismo exponente que x.
  • Cambiar la carga útil o firmar un poco de NaN silencioso.
  • [...]

Dado que todos los NaN y todos los infinitos comparten el mismo exponente, y el resultado correctamente redondeado de x+0.0y x*1.0para finito xtiene exactamente la misma magnitud que x, su exponente es el mismo.

SNANS

Los NaN de señalización son valores de trampa de punto flotante; Son valores especiales de NaN cuyo uso como operando de punto flotante da como resultado una excepción de operación no válida (SIGFPE). Si se optimizara un bucle que desencadena una excepción, el software ya no se comportaría igual.

Sin embargo, como señala user2357112 en los comentarios , el Estándar C11 deja explícitamente indefinido el comportamiento de la señalización de NaNs ( sNaN), por lo que el compilador puede suponer que no se producen y, por lo tanto, no se producen las excepciones que generan . El estándar C ++ 11 omite describir un comportamiento para la señalización de NaN y, por lo tanto, también lo deja indefinido.

Modos de redondeo

En modos de redondeo alternativo, las optimizaciones permitidas pueden cambiar. Por ejemplo, en el modo Round-to-Negative-Infinity , la optimización se x+0.0 -> xvuelve permisible, pero x-0.0 -> xse prohíbe.

Para evitar que GCC asuma modos y comportamientos de redondeo predeterminados, el indicador experimental -frounding-mathse puede pasar a GCC.

Conclusión

Clang y GCC , incluso en -O3, sigue cumpliendo con IEEE-754. Esto significa que debe cumplir con las reglas anteriores del estándar IEEE-754. nox+0.0 es idéntico a xtodos en xvirtud de esas reglas, pero x*1.0 se puede elegir que sea así : a saber, cuando

  1. Obedezca la recomendación de pasar sin cambios la carga útil de xcuando es un NaN.
  2. Deje el bit de signo de un resultado NaN sin cambios * 1.0.
  3. Obedezca la orden de XOR el bit de signo durante un cociente / producto, cuando nox es un NaN.

Para habilitar la optimización IEEE-754-insegura (x+0.0) -> x, la bandera -ffast-mathdebe pasarse a Clang o GCC.

Iwillnotexist Idonotexist
fuente
2
Advertencia: ¿qué pasa si se trata de un NaN de señalización? (De hecho pensé que podría haber sido la razón de alguna manera, pero no sabía muy bien cómo, por lo que pedí.)
user541686
66
@Mehrdad: el Anexo F, la parte (opcional) de la norma C que especifica la adhesión de C a IEEE 754, explícitamente no cubre la señalización de NaN. (C11 F.2.1., Primera línea: "Esta especificación no define el comportamiento de la señalización de NaNs"). Las implementaciones que declaran conformidad con el Anexo F quedan libres de hacer lo que quieran con la señalización de NaNs. El estándar C ++ tiene su propio manejo de IEEE 754, pero sea lo que sea (no estoy familiarizado), dudo que también especifique el comportamiento de NaN de señalización.
user2357112 es compatible con Monica el
2
@Mehrdad: sNaN invoca un comportamiento indefinido de acuerdo con el estándar (pero probablemente está bien definido por la plataforma), por lo que el compilador de aplastamiento aquí está permitido.
Joshua
1
@ user2357112: la posibilidad de capturar errores como un efecto secundario para los cálculos que de otro modo no se usarían generalmente interfiere con mucha optimización; si a veces se ignora el resultado de un cálculo, un compilador podría diferir útilmente el cálculo hasta que pueda saber si se utilizará el resultado, pero si el cálculo hubiera producido una señal importante, eso puede ser malo.
supercat
2
Oh, mira, una pregunta que se aplica legítimamente tanto a C como a C ++ que se responde con precisión para ambos lenguajes con una referencia a un solo estándar. ¿Esto hará que las personas sean menos propensas a quejarse de preguntas etiquetadas tanto con C como con C ++, incluso cuando la pregunta trata sobre un lenguaje común? Lamentablemente, creo que no.
Kyle Strand
35

x += 0.0No es un NOOP si xes así -0.0. Sin embargo, el optimizador podría eliminar todo el ciclo ya que los resultados no se utilizan. En general, es difícil saber por qué un optimizador toma las decisiones que toma.

user2357112 es compatible con Monica
fuente
2
De hecho, me envió este después de haber simplemente leer por qué x += 0.0no es un no-op, sin embargo, pensé que probablemente no es la razón porque todo el bucle debe ser optimizado a cabo de cualquier manera. Puedo comprarlo, simplemente no es tan convincente como esperaba ...
user541686
Dada la propensión de los lenguajes orientados a objetos a producir efectos secundarios, me imagino que sería difícil asegurarse de que el optimizador no esté cambiando el comportamiento real.
Robert Harvey
Podría ser la razón, ya que con long longla optimización está en vigencia (lo hizo con gcc, que se comporta igual para el doble al menos)
e2-e4
2
@ ringø: long longes un tipo integral, no un tipo IEEE754.
MSalters
1
¿Qué pasa x -= 0, es lo mismo?
Viktor Mellgren