El programa se comporta de forma extraña en los IDE en línea

82

Me he encontrado con el siguiente programa C ++ ( fuente ):

#include <iostream>
int main()
{
    for (int i = 0; i < 300; i++)
        std::cout << i << " " << i * 12345678 << std::endl;
}

Parece un programa simple y da la salida correcta en mi máquina local, es decir, algo como:

0 0
1 12345678
2 24691356
...
297 -628300930
298 -615955252
299 -603609574

Pero, en IDE en línea como codechef , da el siguiente resultado:

0 0
1 12345678
2 24691356
...
4167 -95167326
4168 -82821648
4169 -7047597

¿Por qué el forbucle no termina en 300? Además, este programa siempre termina en 4169. ¿Por qué 4169y no algún otro valor?

c++ undefined-behavior integer-overflow arpanmangal
fuente
45
Probablemente porque el desbordamiento de enteros con signo tiene un comportamiento indefinido.
eerorika
17
Sé que el desbordamiento firmado es UB, pero este es un error espectacular ...
Galik
45
Una buena lección para no asumir que UB está restringido
MM
12
Tengo curiosidad por saber por qué cree que la primera salida es "la salida correcta".
Lightness Races in Orbit
5
@LightnessRacesinOrbit - bueno, ¡ese recordatorio es valioso!
Davidbak

Respuestas:

108

Voy a asumir que los compiladores en línea usan GCC o un compilador compatible. Por supuesto, cualquier otro compilador también puede hacer la misma optimización, pero la documentación de GCC explica bien lo que hace:

-faggressive-loop-optimizations

Esta opción le dice al optimizador de bucle que use restricciones de lenguaje para derivar límites para el número de iteraciones de un bucle. Esto supone que el código de bucle no invoca un comportamiento indefinido, por ejemplo, provocando desbordamientos de enteros con signo o accesos fuera de límites a la matriz. Los límites del número de iteraciones de un bucle se utilizan para guiar el desenrollado y pelado del bucle y las optimizaciones de la prueba de salida del bucle. Esta opción está activada de forma predeterminada.

Esta opción simplemente permite hacer suposiciones en base a los casos en los que se comprueba la UB. Para aprovechar esas suposiciones, es posible que sea necesario habilitar otras optimizaciones, como el plegado constante.

El desbordamiento de enteros con signo tiene un comportamiento indefinido. El optimizador pudo demostrar que cualquier valor imayor que 173 causaría UB, y debido a que puede asumir que no hay UB, también puede asumir que inunca es mayor que 173. Luego puede probar que i < 300siempre es cierto, y por lo que la condición del bucle se puede optimizar.

¿Por qué 4169 y no algún otro valor?

Esos sitios probablemente limitan el número de líneas de salida (o caracteres o bytes) que muestran y comparten el mismo límite.

eerorika
fuente
3
Si el compilador puede probar que habrá UB para cualquier valor isuperior a 173, ¿por qué no emite una advertencia en lugar de realizar una optimización sin sentido?
Jabberwocky
7
@MichaelWalz Emite uno.
HolyBlackCat
3
@MichaelWalz: Eliminar las pruebas booleanas redundantes no es una optimización sin sentido; es muy útil. Lo que sería (en su mayoría) inútil es agregar código adicional para deshabilitar / deshacer la optimización en presencia de código fuente roto.
25
@MichaelWalz: El compilador no puede detectar UB de manera confiable como sugieres (aunque a veces puede advertir sobre una ocurrencia probable, como lo hace aquí). En cambio, puede proceder con las mejores intenciones suponiendo que no habrá UB . Esas son dos cosas quizás sutilmente pero de hecho sustancialmente diferentes. No es como si el compilador dijera "¡ajá! ¡UB! Ahora puedo activar tal o cual optimización " - la optimización siempre estuvo ahí. Está haciendo cosas como esta todo el tiempo . Pero, siempre que su programa esté escrito correctamente, no verá ningún cambio en su posible semántica.
Lightness Races in Orbit
20
Como analogía, el fabricante de la puerta de entrada de su casa puede haber decidido que sería más robusta si tuviera una pieza de metal colocada tácticamente en algún lugar en el medio. Nunca te darás cuenta, a menos que estés haciendo agujeros en tu puerta y por lo tanto usando las puertas incorrectamente .
Lightness Races in Orbit
40

"El comportamiento indefinido no está definido". (C)

Un compilador usado en codechef parece usar la siguiente lógica:

  1. El comportamiento indefinido no puede suceder.
  2. i * 12345678se desborda y da como resultado UB if i > 173(asumiendo 32 bits int).
  3. Por lo tanto, inunca se puede exceder 173.
  4. Por i < 300lo tanto, es superfluo y se puede reemplazar por true.

El bucle en sí parece infinito. Aparentemente, codechef simplemente detiene el programa después de un período de tiempo específico o trunca la salida.

SantoNegroGato
fuente
11
@ArpanMangal Acabo de contar los caracteres en la salida, y parece que sí 2^16. Aparentemente, es una coincidencia que ambos trunquen la salida a los 2^16caracteres.
HolyBlackCat
3
@ArpanMangal: demonios nasales como 4169, y actualmente están de fiesta en ideone y codechef. UB no está definido, puede ser cualquier cosa, incluidos los demonios nasales. Con toda seriedad, tratar de analizar UB es una pérdida de tiempo, use ese tiempo para descubrir cómo evitar que suceda.
jmoreno
6
@jmoreno no es una pérdida de tiempo si está interesado en el diseño del compilador
user253751
2
@jmoreno Sin embargo, esta vez fue posible analizarlo. Comprender cómo exactamente UB rompe las cosas puede ser útil para concluir en qué casos UB es aceptable, si corresponde.
HolyBlackCat
4
@jmoreno Todo lo que hace el universo es correcto (por definición), entonces, ¿de qué sirve estudiar astronomía?
user253751
11

Está invocando un comportamiento indefinido probablemente en la 174a iteración dentro de su forbucle, ya que el intvalor máximo probablemente 2147483647todavía se 174 * 123456789evalúa como una expresión 2148147972que es un comportamiento indefinido, ya que no hay un desbordamiento de enteros con signo. Entonces, está observando los efectos de UB, particularmente con el compilador GCC con indicadores de optimización establecidos en su caso. Es probable que el compilador le haya advertido sobre esto emitiendo la siguiente advertencia:

warning: iteration 174 invokes undefined behavior [-Waggressive-loop-optimizations]

Elimine los -O2indicadores de optimización ( ) para observar diferentes resultados.

Ron
fuente
4
Vale la pena señalar que el comportamiento indefinido puede tener efectos retroactivos , ya que UB ocurriría en la iteración 174, ¡el estándar ni siquiera requiere que las primeras 173 iteraciones del bucle procedan como se esperaba!
@ Hurkyl De hecho. Es algo paradójico que UB provoque que todo el programa, incluidas las declaraciones anteriores, muestre UB.
Ron
12
@Ron: No es paradójico. O el programa tiene una semántica bien definida o no la tiene. Período. Recuerde, el código C ++ no es una secuencia de instrucciones que se deben ejecutar; es una descripción de un programa .
Lightness Races in Orbit
@LightnessRacesinOrbit: Es posible que un programa tenga semánticas parcialmente no especificadas pero no totalmente indefinidas. El estándar C intenta aplicar ese concepto a lo que llama "Bounded UB", aunque el lenguaje que usa es un poco vago. Permitir a los compiladores una libertad amplia pero no ilimitada en el manejo de cosas como el desbordamiento de enteros no interferiría con muchas optimizaciones útiles, pero haría que el lenguaje sea mucho más adecuado para procesar datos recibidos de fuentes no confiables.
supercat
@supercat: De hecho, el comportamiento no especificado no es lo mismo que el comportamiento indefinido. Estamos discutiendo esto último
Lightness Races in Orbit
7

El compilador puede asumir que no se producirá un comportamiento indefinido, y dado que el desbordamiento firmado es UB, puede asumir que nunca i * 12345678 > INT_MAX, por lo tanto, también i <= INT_MAX / 12345678 < 300y por lo tanto eliminar la comprobación i < 300.

yassin
fuente