Artykuł opisuje sytuacje w których inkrementacja i dekrementacja zmiennych ma niezdefiniowane zachowanie wg standardu C oraz C++. (artykuł)
Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Zarejestruj się!
dział serwisuArtykuły
kategoriaInne artykuły
artykuł[C, C++] Inkrementacje i dekrementacje - Undefined Behaviour
Autor: Gynvael "GynDream" Coldwind
http://gynvael.coldwind.pl/

[C, C++] Inkrementacje i dekrementacje - Undefined Behaviour

[artykuł] Artykuł opisuje sytuacje w których inkrementacja i dekrementacja zmiennych ma niezdefiniowane zachowanie wg standardu C oraz C++.

int a = 5; a = a++ + ++a; a = ?

Tytułową zagadkę dostałem od furia i uznałem na tyle ciekawą, że przez kilka kolejnych dni rozdawałem ją na prawo i lewo. Zagadka jest o tyle ciekawa, że są tam dwa Undefined Behaviour w jednej krótkiej linii. Obecność UB powoduje oczywiście, że nie ma jednej dobrej odpowiedzi; odpowiedzi tak naprawdę są trzy: 11, 12 lub 13.

Zacznę od rozważań nad potencjalnymi rozwiązaniami, a potem przejdę do wyników empirycznych (które przygotował nism0).

Więc... które miejsca są UB/niewiadome/zależne od kompilatora?

Po pierwsze, nie wiadomo które a zostanie podstawione pierwsze w równaniu z drugiego polecenia (przez podstawienie mam na myśli skopiowanie wartości z pamięci do jakiegoś podręcznego rejestru). Opcje są dwie:

Opcja 1. Najpierw podstawienie pierwszego a, potem wyliczenie pre-inkrementacji i podstawienie drugiego a (post-inkrementację na chwilę pominę):
C/C++
a = a + ++a;

//Krok 1. Podstawienie pierwszego a.
a = 5 + ++a;( a == 5 )

//Krok 2. Pre-inkrementacja a.
a = 5 + a;( a == 6 )

//Krok 3. Podstawienie drugiego a.
a = 5 + 6;( a == 6 )

//Krok 4. Wyliczenie dodawania.
a = 11;
Opcja 2. Najpierw wykonana zostanie pre-inkrementacja, łącznie z zapisem wyniku do pamięci, a dopiero później nastąpi podstawienie pierwszego a.
C/C++
a = a + ++a;

//Krok 1. Pre-inkrementacja a.
a = a + a;( a == 6 )

//Krok 2 i 3. Podstawienie pierwszego i drugiego a.
a = 6 + 6;( a == 6 )

//Krok 4. Wyliczenie dodawania.
a = 12;
Czyli już z samej pre-inkrementacji i podstawiania dostajemy dwa różne wyniki (11 i 12).

Drugi UB związany jest z post-inkrementacją i potencjalnie trywialną linijką a = a++. Jak się okazuje, są tutaj również dwie opcje, które rozważę posługując się kodem pomocniczym w postaci int a = 5; a = a++;.

Terminologia:
  • a_mem - 'a' w pamięci (np. jako lokalna zmienna na stosie)
  • a_copy - kopia 'a' w jakimś podręcznym rejestrze

Opcja 1. Wynikowy kod ma następującą formę (w pseudo-assembly):
Warunki początkowe:
(a_mem == 5, a_copy == brak)

//Krok 1. Podstawienie a do równania.
a = 5++; (a_mem == 5, a_copy == 5)

//Krok 2. Post-inkrementacja na zmiennej w pamięci.
a = 5;   (a_mem == 6, a_copy == 5)

//Krok 3. Przypisanie, czyli a_copy leci do a_mem.
(a_mem == 5, a_copy == brak)
W powyższym wypadku wynik post-inkrementacji a zaginął w akcji. Tj. niby zostało zapisane do pamięci, ale po chwili operacja przypisania (=) wrzuciła finalny wynik obliczeń (czyli 5) do zmiennej a w pamięci nadpisując jednocześnie wynik post-inkrementacji. (prawdę mówiąc zawsze uważałem, że operacja post-inkrementacji jest deferowana na sam koniec wszystkich obliczeń, więc uznałbym to zachowanie za bug kompilatora)

Opcja 2. Post-inkrementacja dzieje się po przypisaniu.
Warunki początkowe:
(a_mem == 5, a_copy == brak)

//Krok 1. Podstawienie a do równania.
a = 5++; (a_mem == 5, a_copy == 5)

//Krok 3. Przypisanie, czyli a_copy leci do a_mem.
(zostaje a++) (a_mem == 5, a_copy == brak)

//Krok 2. Post-inkrementacja na zmiennej w pamięci.
(a_mem == 6, a_copy == brak)
Czyli post-inkrementacja zostaje faktycznie zdeferowana na koniec obliczeń.

Podsumowując, ostateczny wynik a = a++ + ++a to:
  • Opcja 1 i 1: 5+6 i wynik post-inkrementacji MIA, razem 11
  • Opcja 2 i 1: 6+6 i wynik post-inkrementacji MIA, razem 12
  • Opcja 1 i 2: 5+6 i post-inkrementacja zdeferowana, razem 12
  • Opcja 2 i 2: 6+6 i post-inkrementacja zdeferowana, razem 13

Jak wspomniałem na początku, nism0 porobił trochę testów (empirycznych), z czego wyszła następująca tabelka (update: jak słusznie zauważył nonek, kolumny 1 i 2 oraz 4 z 5 w tabeli były zamienione miejscami względem wyników; teraz już jest OK, thx nonek ;>) (update 2: jeszcze jedna seria literówek poprawiona (dot. C#), thx qyon):
Kod 1Kod 2Kod 3Kod 4Kod 5Kod 6
C/C++
int a = 5;
a = a++ + a++;
C/C++
int a = 5;
a = a++ + ++a;
C/C++
int a = 5;
a = ++a + a++;
C/C++
int a = 5;
a = ++a + ++a;
C/C++
int a = 5;
a = a++;
C/C++
int a = 5;
a = a + ++a;

Kompilator/JęzykWersjawynik 1wynik 2wynik 3wynik 4wynik 5wynik 6
gcc2.9512131413612
gcc4.112131413612
gcc4.212131413612
gcc4.2.1 Apple12131413612
gcc4.312131413612
gcc4.3.312131314612
gcc4.4.412131314612
gcc4.6.0 (exp.)12131413612
gcc4.5.1 MinGW6412131314612
tcc0.9.25????????512
bcc0.16.17????????512
Microsoft C/C++16.00.30319.01 (80x86)12131314612
Embarcadero C++6.31 for Win3212131314612
Intel C++12.0.1.12712131313612
Keil C9.0211121213612
SDCC3.0.1 #609211121314512
clang2.811121213511
clang1.6 Apple11121213511
PHP5.2.1011121213512
java1.6.0_0611121213511
javac1.4.2_1211121213511
java1.6.0_2111121213511
javac1.6.0_2211121213511
C#2.011121213511
C#4.011121213511
C#Mono 2.6.411121213511
Borland Turbo C++ for DOS2.0112131314612
HiSoft C for ZX Spectrum1.311121213512

Podziękowania za dodatkowe wyniki dla: Icewall, Krzysztof Kotowicz (za PHP 5.2.10), mlen (za 2x clang, 2x gcc), none'a (za 2xJava), Keraj (za 2x Java), MDobak (za SDCC i Keil C), garbaty_lamer (za 3xC#, Turbo C++, HiSoft C), Xgrzyb90 (za gcc 4.4.4), no_name (za gcc 4.3.3), dikamilo (za mingw64 4.5.1).

Update: kapitalny screen z HiSoft C for ZX Spectrum który garbaty lamer wrzucił w komentarzach:


Wyniki z innych kompilatorów jak zwykle mile widziane (kod do testów, autorstwa nism0, umieściłem poniżej). Wyniki z innych języków programowania posiadających pre- i post-inkrementacje również mogą być ciekawe.

I tyle na dzisiaj. Szczęśliwego nowego roku ;>

Update:
P.S. Zachęcam do rzucenia okiem na komentarze, szczególnie na komentarz Rolek'a (Rolka? ;>), który zaproponował test (kod jest w jego komentarzu) z przeciążeniem operatorów (wyniki by Rolek (MSVC++) & me (g++)):
Kod 1Kod 2Kod 3Kod 4Kod 5Kod 6
C/C++
int a = 5;
a = a++ + a++;
C/C++
int a = 5;
a = a++ + ++a;
C/C++
int a = 5;
a = ++a + a++;
C/C++
int a = 5;
a = ++a + ++a;
C/C++
int a = 5;
a = a++;
C/C++
int a = 5;
a = a + ++a;

Kompilator/JęzykWersjawynik 1wynik 2wynik 3wynik 4wynik 5wynik 6
Microsoft C/C/++ (bez przeciążenia)16.00.30319.0112131314612
Microsoft C/C/++ (z przeciążeniem)16.00.30319.0111131214512
g++ (bez przeciążenia)4.5.0 MinGW12131314612
g++ (z przeciążeniem)4.5.0 MinGW11131214512


Poza tym, krlm rzucił dobry link o sequence points: http://en.wikipedia.org/wiki/Sequence_point.

Komentarz garbatego_lamera dot C# jest również ciekawy i warty uwagi:
Nudne to wklejanie takich samych wyników. To, co w niektórych językach jest undefined, w innych jest perfectly defined. Cytat z §7.3 specyfikacji:
Operands in an expression are evaluated from left to right. For example, in F(i) + G(i++) * H(i), method F is called using the old value of i, then method G is called with the old value of i, and, finally, method H is called with the new value of i. This is separate from and unrelated to operator precedence.

End of update.

Oryginalny kod do testów:
C/C++
#include <stdio.h>

int main( void )
{
    int a = 5, b = 5, c = 5, d = 5, e = 5, f = 5;
   
    // test pierwszy
    a = a++ + a++;
    printf( "%i \n", a );
   
    // test drugi
    b = b++ + ++b;
    printf( "%i \n", b );
   
    // test trzeci
    c = ++c + c++;
    printf( "%i \n", c );
   
    // test czwarty
    d = ++d + ++d;
    printf( "%i \n", d );
   
    // test piaty
    e = e++;
    printf( "%i \n", e );
   
    // test szosty
    f = f + ++f;
    printf( "%i \n", f );
   
    // koniec testow
    return 0;
}

Appendix 4

Komentarz by Cem Paya (ad Java0):
Similar to C#, this is also not a riddle for Java because Java defines evaluation to be strictly left-to-right.

See section 15.7 here for some examples with side-effects as in your case:
http://java.sun.com/docs/books/jls/second_edition/html/expressions.doc.html

In C++ where it is undefined, the result can also depend on the optimization level used during compilation, which can change the number of times a value is referenced. eg the compiler expects "a" to not change its value during the evaluation and may optimize other occurences to the same one it fetched.

Wybrane komentarze

2011-01-03 19:07:14, Rolek

Jeśli opakujemy inta w klasę to wyniki też są trochę inne :D
C/C++
#include <cstdio>

class Int
{
    int m_val;
public:
    Int( const int val = 0 )
        : m_val( val )
    { }
    Int( const Int & o )
        : m_val( o.m_val )
    { }
    operator int() const { return m_val; }
    Int & operator =( const Int & o ) { m_val = o.m_val; return * this; }
    Int & operator ++() { ++m_val; return * this; }
    Int operator ++( int ) { Int t = * this; ++* this; return t; }
    Int operator +( const Int & r ) const { return m_val + r.m_val; }
};

template < typename T > void foo( void )
{
    T a = 5, b = 5, c = 5, d = 5, e = 5, f = 5;
   
    // test pierwszy
    a = a++ + a++;
    printf( "%i ",( int ) a );
   
    // test drugi
    b = b++ + ++b;
    printf( "%i ",( int ) b );
   
    // test trzeci
    c = ++c + c++;
    printf( "%i ",( int ) c );
   
    // test czwarty
    d = ++d + ++d;
    printf( "%i ",( int ) d );
   
    // test piaty
    e = e++;
    printf( "%i ",( int ) e );
   
    // test szosty
    f = f + ++f;
    printf( "%i ",( int ) f );
   
}

int main()
{
    printf( " int: " ); foo < int >();
    printf( " Int: " ); foo < Int >();
    return 0;
}

Wyniki:
int: 12 13 13 14 6 12
Int: 11 13 12 14 5 12

IDE: MsVC++2010EE
Kompilator: Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 16.00.30319.01 for 80x86