Porovnání dvou celých čísel v C

16.11.2016 19:02 | Přečteno: 3078× | C |

Mějme následující řadu deseti celých čísel, kterou budeme dále chtít seřadit sestupně.

int seq[10] = { 11, -8, 92, 22,  7, -25, -95, 63,  3, 43 };

K seřazení můžeme použít například knihovní funkci qsort.

qsort(seq, 10, sizeof(int), compar);

Řadicí algoritmy vyžadují ke své činnosti funkci, která porovná dva prvky z řady. Pro vzestupné řazení funkcí qsort musí tato funkce vracet celé číslo (a) menší než, (b) rovno nebo (c) větší než nula, když je první prvek z této dvojice (a) menší než, (b) roven nebo (c) větší než prvek druhý. Pro náš případ to bude rozdíl těchto dvou prvků.

int compar(const void *p1, const void *p2)
{
	return *(const int *)p2 - *(const int *)p1;
}

A jako výsledek dostaneme správně seřazenou řadu.

92 63 43 22 11 7 3 -8 -25 -95

A teď kdo uhádne, co je na příkladu výše špatně?

Nebudu vás napínat. Implementace selže na číslech, jejichž rozdíl se nevleze do datového typu int. Uvažme například následující řadu.

int seq[10] = { -1951288147, 51, -2022032484, 79, -1227112550, 1760804629, 75, -2038298820, 1264956463, 22 };

Po volání qsort bude řada vypadat takto:

79 51 -1227112550 -1951288147 -2022032484 -2038298820 1760804629 1264956463 75 22

Podobný problém nastane také u porovnání datových typů širších než typ int. Řešení může být v našem případě porovnání:

int compar(const void *p1, const void *p2)
{
	return (*(const int *)p2 > *(const int *)p1) - (*(const int *)p2 < *(const int *)p1);
}

A výsledek (tentokrát správně):

1760804629 1264956463 79 75 51 22 -1227112550 -1951288147 -2022032484 -2038298820

Ještě dodám, že problém se týká i příbuzných funkcí jako například bsearch.        

Komentáře

[tom]

Implementace selže na číslech... Integer overflow na znamenkovem typu je v C nedefinovana operace, takze takovy kod je spatne uz podle definice jazyka.

[Josef Kufner]

Zjevně to při přetečení přeteče do kladné oblasti a výsledek porovnání je z ničeho nic opačný, z čehož je qsort poněkud zmatený.

[tom]

Zalezi na prekladaci a na platforme. Prekladac muze ocekavat, ze takova situace nikdy nenastane. Napriklad: int i; for (i = 1; i > 0; i++); muze prekladac optimalizovat na nekonecny cyklus. Na nekterych platformach pri preteceni dostanete SIGFPE.

[BFU]

Nemuze, protoze to je znamenkovy int a ten se pretoci do < 0 a porovnani bude false.

[Michal Kubeček]

Měl byste se naučit rozlišovat mezi empiricky odpozorovaným chováním jednoho konkrétního překladače na jedné konkrétní platformě a tím, co garantuje norma jazyka.

Např. gcc 4.8.1 na x86_64 přeloží s -O3 funkci

int main() {
        int i;

        for (i = 1; i > 0; i++)
                ;

        printf("%d\n", i);
        return 0;
}

na

0000000000400410 <main>:
  400410:       eb fe                   jmp    400410 <main>
  400412:       66 90                   xchg   %ax,%ax

Tj. nejen že z toho udělá nekonečný cyklus, ale rovnou vyhodí i volání printf() a návrat z funkce za ním.

[Jendа]

Nevíš, jestli tahle optimalizace skutečně zrychlí nějaké reálné programy, nebo slouží jenom pro vytrollení nepozorných programátorů? :)

[Michal Kubeček]

Těžko říct. Ale třeba v jádře je běžné, že v závislosti na konfiguračních volbách (což jsou vlastně makra) může někde z preprocesoru vypadnout kus kódu, který je zbytečný, a počítá se s tím, že si s tím optimalizátor poradí.

Na druhou stranu se ale taky občas stane, že nějaká vynalézavá optimalizace novějšího gcc (třeba "není potřeba testovat pointer na null, když už jsme ho dereferencovali") naopak věci rozbila.

[tom]

Skutecne programy to urcite zrychli, protoze to je genericka optimalizace a funguje tak, ze ke kazde promenne si optimalizator prirazuje hodnoty, kterych muze nabyvat. A protoze pricitanim kladneho cisla k signed typu nikdy mensi cislo nevznikne, muze predpokladat, ze stavajici hodnota je nejmensi mozna. Zkuste si prelozit neco vetsiho s -fwrapv a bez -fwrapv a porovnejte si velikost.

[Sten]

Tahle optimalizace kromě vyhození jednoho porovnání a podmíněného skoku u každé iterace umožňuje částečné rozbalení, kdy místo jmp a inkrementace i se může tělo zkopírovat třeba šestkrát, jmp a i += 6, což u hot spotů může dost ovlivnit výkon. Pokud by měl překladač počítat s přetečením, tak to nemůže udělat.

[:::]

Samozrejme ze zrychli. Treba v tomhle konkretnim pripade si prekladac odvodil ze "i > 0" je vzdy true, a proto tu podminku vyhodil a kazda iterace je ted o par instrukci a o podmineny skok rychlejsi

Jinak, jestli te to zajima, tak se podivej do "Dragon book", kapitola o "Symbolic analysis"

Je to optimalizace ktera umozni urcit jak se promenne v cyklu chovaji v zavislosti na poctu iteraci. Tim je mozne odstranit treba nasobeni, indexaci, podminky, ...

Napr. to umozni prepsat tenhle cyklus:

for (m = 10; m < 20; m++) {
    x = m*3;
    A[x] = 0;
}

na:

for (ptr = A+30; ptr <= A+57; ptr += 3) {
    *ptr = 0;
}

[BFU]

> Měl byste se naučit rozlišovat mezi empiricky odpozorovaným chováním jednoho konkrétního

> překladače na jedné konkrétní platformě a tím, co garantuje norma jazyka.

>

> Např. gcc 4.8.1 na x86_64 přeloží s -O3 funkci"

Tady si sam protirecite, nebot pouzivate chovani jednoho konkretniho prekladace na jedne konkretni platforme jako dukaz.

C99 specifikuje int jako znamenkovy typ, takze pokud pretece, podminka se pretoci do < 0 a cyklus skonci. Napr. GCC 6.x to kompiluje korektne, takze to co pozorujete je spis bug v gcc optimizeru.

Podobne empiricky dukaz misto slibu:

$ gcc --version

gcc (Debian 6.2.0-10) 6.2.0 20161027

[...]

$ gcc -o test test.c

test.c: In function ‘main’:

test.c:7:9: warning: implicit declaration of function ‘printf’ [-Wimplicit-function-declaration]

printf("%d\n", i);

^~~~~~

test.c:7:9: warning: incompatible implicit declaration of built-in function ‘printf’

test.c:7:9: note: include ‘stdio.h’ or provide a declaration of ‘printf’

$ ./test

-2147483648

[:::]

u znamenkovych typu norma nedefinuje chovani pri preteceni, takze "pokud pretece, podminka se pretoci" norma nerika

[BFU]

Ah, to je vskutku ohavnost, dik.

[:::]

jj, na jednu stranu je to ohavnost, ale na druhou stranu to umoznuje nektere optimalizace ktere by jinak udelat nesly...

[tom]

Hlavni duvod je ten, ze C dava nekolik moznosti, jak maji byt zaporna cisla implementovana.

[tom]

A to vam doslo ted? Vzdyt jsem ve svem prvnim komentari napsal, ze prekladac muze ocekavat, ze takova situace nenastane.

[Jendа]

Já myslím, že motivace byla, že nikdo neví, jakou reprezentaci záporných čísel bude daná architektura mít (a že dneska má většina lidí dvojkový doplněk je spíš takové štěstí), takže se dá těžko říct, co se při přetečení s registrem vlastně hardwarově stane. (+ ta DSP se saturační aritmetikou a tak)

[tom]

C99 povoluje 3 ruzne implementace znamenka, takze pokud s tim chce program pracovat, muze si snadno zjistit, jaka se pouziva prectenim bitu napriklad v -1.

[Martin Mareš]

Pozor, zase tak jednoduché to s tím zjišťováním není: norma totiž nezaručuje vůbec nic o tom, v jakém pořadí jsou bity čísla a znaménkový bit uložené v paměti; taktéž připouští, aby reprezentace celočíselných typů kromě unsigned charu obsahovala padding.

Aha, ono to nejspíš ani nejde zjistit: norma nebrání (poněkud šílené, ale korektní) reprezentaci, která bude ukládat hodnotu ve dvojkovém doplňku, ovšem ještě bude mít paddingové bity, ve kterých bude tatáž hodnota v jedničkovém doplňku

[Michal Kubeček]

Tady si sam protirecite, nebot pouzivate chovani jednoho konkretniho prekladace na jedne konkretni platforme jako dukaz.

Vůbec ne. Vy jste tvrdil, že to překladač udělat nemůže. To je obecné tvrzení, takže příklad nestačí. Já jsem vám ukázal, že vaše tvrzení obecně neplatí a na to samozřejmě jeden protipříklad stačí.

Já jsem nijak nerozporoval, že existuje nějaký překladač, který s konrétními volbami u optimalizaci neprovede. Ale rozhodně to neplatí pro všechny - a i kdyby náhodoou ano, stejně byste na to nemohl spoléhat, protože norma to chování nezaručuje, takže by se vám to mohlo rozbít hned s následující verzí.

[Michal Kubeček]

Ještě pro pořádek:

C99 specifikuje int jako znamenkovy typ, takze pokud pretece, podminka se pretoci do &lt; 0

A kde konkrétně se to o "přetočení do < 0" v té normě píše?

Napr. GCC 6.x to kompiluje korektne, takze to co pozorujete je spis bug v gcc optimizeru.

gcc6 se chová úplně stejně jako gcc 4.8.1, zkuste si to přeložit s -O3. S -O0 tu optimalizaci neprovede ani gcc 4.8.1, což je celkem logické, když mu řeknete, že optimalizovat nemá.

[tom]

Nemusi, ale protoze spousta lidi s tragickymi znalostmi C si to mysli, gcc na to ma prepinac: -fwrapv.

[Jendа]

Asi mu šlo o to, že to standard nedefinuje. Dokážu si představit třeba nějaké DSP se saturační aritmetikou, kde se tohle nestane.

[wamba]

(a) menší než, (b) rovno nebo (c) větší než nula,

hm, ono je to takhle v dokumentaci a to i pro Perl 5 sort. :) Já měl zafixováno, že by to mělo nabývat jen hodnot -1, 0, 1.

Krásné je v Perlu 6 chování sort, které řadí podle cmp. Chování cmp:

perl6 -e 'say 2 cmp 12, 12 cmp "12a", "12a" cmp 2'
LessLessLess

Pole, kde následující prvek vznikne seřazením předchozího

perl6 -e 'say ((12, 2, "12a"), *.sort ... * ).head(5)'
((12 2 12a) (12a 2 12) (12 12a 2) (2 12 12a) (12a 2 12))

[Kvakor]

Teoreticky by QuickSortu měla stačit funkce, která vrátí jen tři možné hodnoty - větší (1), menší (-1) a stejné (0), protože stačí určit, jestli jde číslo před nebo za pivot. To by mělo fungovat pro libovolně velká čísla (včetně čísel v plovoucí řádové čárce), ukazatele, řetězce ... prostě cokoliv. A podle toho, jak se koukám do kódu GNU libc, tak by mohlo stačit vracet jen menší/větší nula, poněvač všechna porovnávání v kódu jsou jenom "je menší než nula".

Jinak pokud procesor umí saturovanou aritmetiku a existuje pro ní nějaká knihovní či vestavěná funkce (intrinsics), tak by stačilo udělat rozdíl se saturací a ten vrátit.

[kralyk z abclinuxu]

Tohle má Rust ve standardní knihovně. Zajímalo by mě, jak to mají implementováno, aby to fungovalo na všech platformách. Možná to poskytuje LLVM.

[Tomáš]

Nevím, co tady pořád řešíte. Programátor napíše špatně funkci na porovnání, tak to háže špatné výsledky. Je dobře, že to sem autor napsal, ale nevinil byl z chyby funkci qsort (nebo kteroukoliv jinou).

[pavlix]

nevinil byl z chyby funkci qsort

A co je jednodušší než to prostě nedělat?

[Ovrscout]

To důležité bylo řečeno , ale pokud někoho zajímají další informace o podobných záležitostech tak kouzelná slova do google jsou ansi c undefined unspecified behaviour

Celkem dobrý a přehledný zdroj(i když popis UB a US není primární cíl webu), informací je také securecoding.cert.org

[Ondrej Santiago Zajicek]

Az na to, ze v clanku zminovany problem se (narozdil od diskuse) vubec netyka C nedefinovanych ci nespecifikovanych chovani, ale proste toho, ze k preteceni doslo. I kdyz int preteceni dodefinujeme (napr. v GCC pomoci -fwrap), ten kod bude stale spatne.