Program zachowuje się dziwnie w internetowych IDE

82

Natrafiłem na poniższy program w C ++ ( źródło ):

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

Wygląda jak prosty program i podaje prawidłowe dane wyjściowe na mojej lokalnej maszynie, np. Coś takiego:

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

Ale w internetowych środowiskach IDE, takich jak codechef , daje następujący wynik:

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

Dlaczego forpętla nie kończy się przy 300? Również ten program zawsze kończy się 4169. Dlaczego 4169a nie inna wartość?

arpanmangal
źródło
45
Prawdopodobnie dlatego, że przepełnienie liczby całkowitej ze znakiem ma niezdefiniowane zachowanie.
eerorika
17
Wiem, że podpisane przepełnienie to UB, ale to spektakularna porażka ...
Galik,
45
Dobra lekcja nie zakładania, że ​​UB jest ograniczony
MM
12
Jestem ciekawy, dlaczego uważasz, że pierwszy wynik jest „prawidłowym wyjściem”.
Wyścigi lekkości na orbicie
5
@LightnessRacesinOrbit - cóż, to przypomnienie jest cenne!
davidbak

Odpowiedzi:

108

Zakładam, że kompilatory online używają GCC lub kompatybilnego kompilatora. Oczywiście każdy inny kompilator może również przeprowadzić taką samą optymalizację, ale dokumentacja GCC dobrze wyjaśnia, co robi:

-faggressive-loop-optimizations

Ta opcja mówi optymalizatorowi pętli, aby używał ograniczeń językowych do określania granic dla liczby iteracji pętli. Zakłada się, że kod pętli nie wywołuje niezdefiniowanego zachowania, na przykład powodując przepełnienia liczb całkowitych ze znakiem lub dostęp do tablicy poza granicami. Granice liczby iteracji pętli służą do prowadzenia optymalizacji rozwijania i odrywania pętli oraz testów wyjścia z pętli. Opcja jest wyłączona domyślnie.

Ta opcja pozwala jedynie na przyjmowanie założeń na podstawie przypadków, w których udowodniono UB. Aby skorzystać z tych założeń, może być konieczne włączenie innych optymalizacji, takich jak ciągłe zwijanie.


Przepełnienie liczby całkowitej ze znakiem ma niezdefiniowane zachowanie. Optymalizator był w stanie udowodnić, że jakakolwiek wartość iwiększa niż 173 spowodowałaby UB, a ponieważ może założyć, że nie ma UB, może również założyć, że inigdy nie jest większa niż 173. Następnie może dalej udowodnić, że i < 300jest to zawsze prawda, i więc stan pętli można zoptymalizować.

Dlaczego 4169, a nie inna wartość?

Witryny te prawdopodobnie ograniczają liczbę wyświetlanych wierszy wyjściowych (lub znaków lub bajtów) i mają ten sam limit.

eerorika
źródło
3
Jeśli kompilator może udowodnić, że będzie UB dla dowolnej wartości iwiększej niż 173, to dlaczego nie emituje ostrzeżenia zamiast bezcelowej optymalizacji?
Jabberwocky
7
@MichaelWalz To emituje jeden.
HolyBlackCat
3
@MichaelWalz: Usunięcie zbędnych testów logicznych nie jest bezcelową optymalizacją; jest to bardzo przydatne. To , co byłoby (w większości) bezcelowe, to dodawanie dodatkowego kodu wyłączającego / cofającego optymalizację w obecności uszkodzonego kodu źródłowego.
25
@MichaelWalz: Kompilator nie może niezawodnie wykryć UB, jak sugerujesz (chociaż czasami może ostrzec o prawdopodobnym wystąpieniu, tak jak w rzeczywistości ma to miejsce tutaj). Zamiast tego może działać z najlepszymi intencjami, zakładając, że nie będzie UB . To są dwie, być może subtelnie, ale w rzeczywistości zasadniczo różne rzeczy. To nie jest tak, że kompilator powiedział "aha! UB! Teraz mogę włączyć taką a taką optymalizację " - optymalizacja była zawsze. Robi takie rzeczy cały czas . Ale dopóki program jest poprawnie napisany, nie zauważysz żadnych zmian w jego niedoszłej semantyce.
Wyścigi lekkości na orbicie
20
Analogicznie, producent drzwi wejściowych do twojego domu mógł zdecydować, że byłyby one bardziej wytrzymałe, gdyby miały taktycznie umieszczony kawałek metalu gdzieś pośrodku. Nigdy tego nie zauważysz, chyba że wybijasz dziury w drzwiach, a tym samym niewłaściwie używasz drzwi .
Wyścigi lekkości na orbicie
40

„Niezdefiniowane zachowanie jest nieokreślone”. (do)

Kompilator używany na codechef wydaje się używać następującej logiki:

  1. Niezdefiniowane zachowanie nie może się zdarzyć.
  2. i * 12345678przepełnia i powoduje UB if i > 173(zakładając 32 bity int).
  3. Tak więc inigdy nie może przekroczyć 173.
  4. Dlatego i < 300jest zbędny i można go zastąpić true.

Sama pętla wydaje się być nieskończona. Wygląda na to, że codechef po prostu zatrzymuje program po określonym czasie lub obcina dane wyjściowe.

HolyBlackCat
źródło
11
@ArpanMangal Właśnie policzyłem znaki w wyjściu i wydaje się, że tak 2^16. Najwyraźniej to zbieg okoliczności, że obcinają dane wyjściowe do 2^16znaków.
HolyBlackCat
3
@ArpanMangal: demony nosowe, takie jak 4169, a obecnie bawią się w ideone i codechef. UB jest nieokreślony, może to być wszystko, w tym demony nosowe. Mówiąc poważnie, próba analizy UB jest stratą czasu, wykorzystaj ten czas, aby dowiedzieć się, jak temu zapobiec.
jmoreno
6
@jmoreno to nie jest strata czasu, jeśli interesuje Cię projekt kompilatora
user253751
2
@jmoreno Chociaż tym razem udało się to przeanalizować. Zrozumienie, jak dokładnie UB psuje rzeczy, może być przydatne do wyciągnięcia wniosków, w jakich przypadkach UB jest akceptowalne, jeśli w ogóle.
HolyBlackCat
4
@jmoreno Wszystko, co robi wszechświat, jest poprawne (z definicji), więc po co studiować astronomię?
user253751
11

Wywołujesz niezdefiniowane zachowanie prawdopodobnie w 174. iteracji wewnątrz twojej forpętli, ponieważ intprawdopodobnie maksymalna wartość jest 2147483647jeszcze 174 * 123456789obliczana, 2148147972co jest niezdefiniowanym zachowaniem, ponieważ nie ma przepełnienia liczb całkowitych ze znakiem. Więc obserwujesz efekty UB, szczególnie z kompilatorem GCC z ustawionymi flagami optymalizacji. Prawdopodobnie kompilator ostrzegłby Cię o tym, wydając następujące ostrzeżenie:

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

Usuń -O2flagi optymalizacji ( ), aby obserwować różne wyniki.

Ron
źródło
4
Warto zauważyć, że niezdefiniowane zachowanie może mieć skutki wsteczne - ponieważ UB miałoby miejsce w iteracji 174, standard nawet nie wymaga, aby pierwsze 173 iteracje pętli przebiegały zgodnie z oczekiwaniami!
@Hurkyl Rzeczywiście. To trochę paradoksalne, że UB powoduje, że cały program, łącznie z poprzednimi instrukcjami, wykazuje UB.
Ron,
12
@Ron: To nie jest paradoks. Albo program ma dobrze zdefiniowaną semantykę, albo nie. Kropka. Pamiętaj, że kod C ++ nie jest sekwencją instrukcji do wykonania; jest to opis programu .
Wyścigi lekkości na orbicie,
@LightnessRacesinOrbit: Program może mieć semantykę, która jest częściowo nieokreślona, ​​ale nie jest całkowicie nieokreślona. Standard C próbuje zastosować to pojęcie do tego, co nazywa „ograniczonym UB”, chociaż język, którego używa, jest nieco niejasny. Umożliwienie kompilatorom szerokiej, ale nie nieograniczonej swobody w obsłudze takich rzeczy, jak przepełnienie liczb całkowitych nie kolidowałoby z wieloma użytecznymi optymalizacjami, ale uczyniłoby język znacznie bardziej odpowiednim do przetwarzania danych otrzymanych z niewiarygodnych źródeł.
supercat
@supercat: Rzeczywiście, nieokreślone zachowanie to nie to samo, co niezdefiniowane zachowanie. Omawiamy to drugie
Lightness Races in Orbit
7

Kompilator może założyć, że niezdefiniowane zachowanie nie wystąpi, a ponieważ przepełnienie podpisane to UB, może założyć, że nigdy i * 12345678 > INT_MAX, a zatem również, i <= INT_MAX / 12345678 < 300a tym samym usunąć sprawdzenie i < 300.

yassin
źródło