Inne artykuły

[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ę):

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.

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 1	Kod 2	Kod 3	Kod 4	Kod 5	Kod 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ęzyk	Wersja	wynik 1	wynik 2	wynik 3	wynik 4	wynik 5	wynik 6
gcc	2.95	12	13	14	13	6	12
gcc	4.1	12	13	14	13	6	12
gcc	4.2	12	13	14	13	6	12
gcc	4.2.1 Apple	12	13	14	13	6	12
gcc	4.3	12	13	14	13	6	12
gcc	4.3.3	12	13	13	14	6	12
gcc	4.4.4	12	13	13	14	6	12
gcc	4.6.0 (exp.)	12	13	14	13	6	12
gcc	4.5.1 MinGW64	12	13	13	14	6	12
tcc	0.9.25	??	??	??	??	5	12
bcc	0.16.17	??	??	??	??	5	12
Microsoft C/C++	16.00.30319.01 (80x86)	12	13	13	14	6	12
Embarcadero C++	6.31 for Win32	12	13	13	14	6	12
Intel C++	12.0.1.127	12	13	13	13	6	12
Keil C	9.02	11	12	12	13	6	12
SDCC	3.0.1 #6092	11	12	13	14	5	12
clang	2.8	11	12	12	13	5	11
clang	1.6 Apple	11	12	12	13	5	11
PHP	5.2.10	11	12	12	13	5	12
java	1.6.0_06	11	12	12	13	5	11
javac	1.4.2_12	11	12	12	13	5	11
java	1.6.0_21	11	12	12	13	5	11
javac	1.6.0_22	11	12	12	13	5	11
C#	2.0	11	12	12	13	5	11
C#	4.0	11	12	12	13	5	11
C#	Mono 2.6.4	11	12	12	13	5	11
Borland Turbo C++ for DOS	2.01	12	13	13	14	6	12
HiSoft C for ZX Spectrum	1.3	11	12	12	13	5	12

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 1	Kod 2	Kod 3	Kod 4	Kod 5	Kod 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ęzyk	Wersja	wynik 1	wynik 2	wynik 3	wynik 4	wynik 5	wynik 6
Microsoft C/C/++ (bez przeciążenia)	16.00.30319.01	12	13	13	14	6	12
Microsoft C/C/++ (z przeciążeniem)	16.00.30319.01	11	13	12	14	5	12
g++ (bez przeciążenia)	4.5.0 MinGW	12	13	13	14	6	12
g++ (z przeciążeniem)	4.5.0 MinGW	11	13	12	14	5	12

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:

#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

#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

Serwis http://cpp0x.pl otrzymał licencję na publikację niniejszego artykułu o następującej treści:

Niniejszym udzielam darmowej licencji na opublikowanie artykułu "int a = 5; a = a++ + ++a; a = ?" (http://gynvael.coldwind.pl/?id=369) na łamach serwisu cpp0x.pl (http://cpp0x.pl), którego właścicielem jest Pan Piotr Szawdyński. Warunkiem publikacji jest zamieszczenie informacji o oryginalnym miejscu publikacji (tj. blogu autora, http://gynvael.coldwind.pl/) oraz informacji o autorze. Artykuł musi zostać opublikowany bez zmian w części merytorycznej. Dopuszczalne są zmiany wyglądu, formatowania, oraz korekta ew. literówek.

Autor zastrzega sobie możliwość cofnięcia niniejszej licencji.

Wszystkie teksty są chronione prawami autorskimi. Kopiowanie lub rozpowszechnianie treści poza niniejszym serwisem jest zabronione.

Powyższe ograniczenie nie dotyczy autora opracowania, któremu przysługuje prawo do rozpowszechniania własnego tekstu wedle własnego uznania.