Kääntäjäbugi

Seuraa 
Viestejä45973
Liittynyt3.9.2015

C:tä on pääasiassa vääntänyt ensimmäisestä Turbo C:stä lähtien. Kaikissa C/C++ kääntäjissä on näemmä qsort -funktiobugi:

Kun sortataan taulukon rivejä, ja joka sorttausaskeleella sortataan ko. sarakkeet, qsort kaatuu.

Höh. qsort-funktiolle annetaan haluttu vertailufunktio, ja se on sitten ikäänkuin yksi ja ainut vertailufunktio, joka on kaikkialla ohjelmassa globaalina.

Vittu, kun C:ssä muuten pyritään parametrien kanssa paikallisuuteen, ja sitä kautta koodin tehokkuuteen, kompaktisuuteen ja helppolukuisuuteen.

Niin, tämä on mainitsemisen arvoista, koska perus C (~ peruslogiikka ~ standardifunktiot ~ siirrettävät funktiot) ei saisi bugittaa lainkaan.

Kommentit (15)

abskissa
Seuraa 
Viestejä3654
Liittynyt9.10.2008

Lajittelu edellyttänee sitä, että vertailufunktio säilyttää järjestyksen. Kävisikö nyt niin, että kun roplaat sarakkeita kesken rivisortin, niin tuo vaatimus ei täytykään?

We're all mad here.

Vierailija

No pitää ajatella vähän niin kuin lajittelun lajitteluna. Voihan sortattavilla olioilla olla sisäisesti sortattavia listoja, olioita, ja mitä vain. joista seuraa ylempien olioiden keskinäinen järjestys.

Kummallista, että C-kielen qsort kaatuu tällaisessa tilanteessa. Pitää tehdä koko funktio uudelleen, joka tukee tällaisia rekursio-tapauksia.

Toisekseen funktiosta kannattaa tehdä puolta nopeampi, niin sen tekemisessä on jotain mieltä. Projekti voi kestää päivistä kuukausiin, mutta heitän sitten koodinpläjäyksen tänekkin.

Vierailija

Pistäisitkö esimerkkikoodin, jossa qsort kaatuu?

Googlettelin, että C++:lla kanattaisi käyttää std::sort:ia.

abskissa
Seuraa 
Viestejä3654
Liittynyt9.10.2008
_jone_
Voihan sortattavilla olioilla olla sisäisesti sortattavia listoja, olioita, ja mitä vain.

Juu, toki voi. Vertailufunktion pitää silti toimia johdonmukaisesti koko lajittelun ajan. Jos lajiteltavat oliot muuttuvat lennossa niin, että vertailuperusteetkin muuttuvat, lajittelualgoritmi ei toimi. Se joko kaatuu tai lajittelee väärin. Sama pätee kaikkiin "comparison sort" -algoritmeihin -- ei pelkästään quicksortiin eikä pelkästään C-kieleen.

Kirjastojen bugittomuudesta tuli mieleen tällainen haaste: kirjoita efektiivinen ja bugiton toteutus kahden kokonaisluvun keskiarvon laskennalle:

int keskiarvo(int a, int b)

Laskettava siis keskiarvo nollaa kohti pyöristäen. Haaste liittyy yhteen yllättävään tosielämän standardikirjastobugiin.

We're all mad here.

Vierailija

Elikkäs tuossa koodissa sortataan (lotto)haravan rivikandinaatteja, muttei vielä pääse sorttaamista edemmäs asiassa, kun mainin ok1 ja ok2 välillä kaatuu.

[code:p9p1a5yj]#include
#include
#include
#include
#include

#define KPL 15380937

class row
{
public:

row(void);
~row(void);
void set(int*);
void mkRnd(void);
void setDelta(void);

/* private: */

char n[8];
int kpl;
int *D;
};

row::row(void)
{
}

row::~row(void)
{
}

void row::set(int *r)
{
for (int i=0; i<7; i++)
n[i]=(char)r[i];
}

void row::mkRnd(void)
{
char *m=(char*)this;
int i=0x0000, j=sizeof(row);
for (; i
}

int i_vert(const void *aa, const void *bb)
{
int a = *(int*)aa;
int b = *(int*)bb;

return a==b? 0:
(a < b? -1: 1);
}

int* __xx_new(void)
{
static int M[4096];
static int os=-128;

if ((os+=128)==4096)
{
os=0;
}

return M+os;
}

void row::setDelta(void)
{
int i, j, k=0;
D=__xx_new();

for (i=0; i<7; i++)
for (j=0; j<7; j++)
if (i!=j)
{
int a=n[i];
int b=n[j];
D[k]=abs(a-b);
++k;
}

if (k!=42) assert(0);
qsort(D, k, sizeof(int), i_vert);
}

void prog_init(row *R)
{
int r[8];
int kpl=0;

for (r[0]=0x0001; r[0]<=39; r[0]++)
for (r[1]=r[0]+1; r[1]<=39; r[1]++)
for (r[2]=r[1]+1; r[2]<=39; r[2]++)
for (r[3]=r[2]+1; r[3]<=39; r[3]++)
for (r[4]=r[3]+1; r[4]<=39; r[4]++)
for (r[5]=r[4]+1; r[5]<=39; r[5]++)
for (r[6]=r[5]+1; r[6]<=39; r[6]++)
{
R[kpl].set(r);
++kpl;
}

if (kpl!=KPL)
assert(0x00);
}

int sort_delta(const void *aa, const void *bb)
{
row *a=(row*)aa;
row *b=(row*)bb;

a->setDelta();
b->setDelta();

for (int i=0; i<42; i++)
if (a->D[i]!=b->D[i])
{
return a->D[i]D[i]? -1: 1;
}

return 0;
}

void main(void)
{
row *R=new row[KPL+8];

char *m=(char*)R;

int j=sizeof(row)*(KPL+8);

for (int i=0; i
m[i]=(char)random(256);

prog_init(R);

printf("ok1...\n");

qsort(R, KPL, sizeof(row), sort_delta);

printf("ok2...\n");

delete[] R;
}
[/code:p9p1a5yj]

Vierailija

Jos olioiden ominaisuudet jo määräävät niiden järjestyksen niin miksi niitä tarvitsee 'ulkopuolelta' sortata? Vai ymmärsinköhän vähän väärin ...

Muistaakseni qsort jo on varsin nopea ... yleensä, keskimäärin, mikä ei tarkoita, etteikö erikoistapauksissa jokin toinen tapa voisi olla nopeampi. Eikö qsort (kuten moni muu) kuitenkin käytä ns. puolitushakua? Joka on yleistapauksissa varsin nopea tapa.

abskissa
Seuraa 
Viestejä3654
Liittynyt9.10.2008

Pikasilmäyksellä ja C:tä pahemmin tuntematta bugi näyttää olevan siinä, että sort_delta:ssa muutetaan lennossa vertailuperusteita (eli D-taulukoiden sisältöä) setDelta:lla. Se ei ole sallittua. Sivuvaikutuksien ujuttaminen vertailufunktioon tuntuu muutenkin kikkailulta.

Standardikirjastojen dokumentaatiossa sanotaan vertailufunktiosta näin:

The function must not modify the objects passed to it.



Kirjoittamasi sort_delta rikkoo tuota sääntöä.

We're all mad here.

Vierailija
abskissa
Kirjastojen bugittomuudesta tuli mieleen tällainen haaste: kirjoita efektiivinen ja bugiton toteutus kahden kokonaisluvun keskiarvon laskennalle:

int keskiarvo(int a, int b)

Laskettava siis keskiarvo nollaa kohti pyöristäen. Haaste liittyy yhteen yllättävään tosielämän standardikirjastobugiin.




Mulla oli kerran melkein vastaavanlainen ongelma äänenpakkauksessa, jossa arvoja oli n kappaletta, mutta kahden tapauksessa on:

[code:32fzk415]int keskiarvo(int a, int b)
{
register int sum=a+b;

if (sum)
{
if (sum<0)
return (sum-1)>>1;
else
return (sum+1)>>1;
}
else
{
return 0;
}
}[/code:32fzk415]

abskissa
Seuraa 
Viestejä3654
Liittynyt9.10.2008
_jone_

Mulla oli kerran melkein vastaavanlainen ongelma äänenpakkauksessa, jossa arvoja oli n kappaletta, mutta kahden tapauksessa on:

[code:27swt0p1]int keskiarvo(int a, int b)
{
register int sum=a+b;

if (sum)
{
if (sum<0)
return (sum-1)>>1;
else
return (sum+1)>>1;
}
else
{
return 0;
}
}[/code:27swt0p1]


Koodiisi taisi lipahtaa bugi. Huomaatko mihin? Toimiiko kaikilla int:eillä?

We're all mad here.

MaKo71
Seuraa 
Viestejä1467
Liittynyt15.11.2006

Jeps, qsortin (tai yleensä ottaen minkään sortin) vertailufunktion ei pitäisi muokata aineistoa. Sorttausalgoritmeja koetetaan optimoida siten, että ne vertailevat kahta alkiota toisiinsa mielellään vain kerran. Jos alkioihin tulee muutoksia eivätkä vanhat vertailut enää ole paikkansa pitäviä, algoritmi ei toimi.

Jos lajittelun yhteydessä on pakko muokata aineistoa, niin pitää kirjoittaa oma sorttausfunktio, joka tietää, milloin aineistoa ei enää tarvitse muokata ja saatu järjestys on lopullinen.

abskissa

Kirjastojen bugittomuudesta tuli mieleen tällainen haaste: kirjoita efektiivinen ja bugiton toteutus kahden kokonaisluvun keskiarvon laskennalle:



Äkikseltään jotenkin näin:

[code:25ppmjxu]
int keskiarvo(int a, int b)
{
return ((long long)a + (long long)b) / 2;
}
[/code:25ppmjxu]

Tuo long long -castaus (64-bit) sen takia, että jos intit (32-bit) on isoja, niin ei tule ylivuotoja. Muunnoksen takaisin intiksi tekee kääntäjä automaattisesti, tosin se taitaa valittaa, joten voisi siihen liittää ihan eksplisiittisen muunnoksen...

Vierailija

No, ei tuossa dataa muokata lainkaan. Ongelma on siinä, että muisti loppuu, jos joka olion deltalle varaa konkreettisen muistialkion (42 kpl per rivi).

Ratkaisuna tuo deltta-data palautetaan sitten vasta vertailuvaiheessa. Vittu, kun menee vaikeaksi...

...setDelta() palauttaa virtuaaliseen D -lohkoon konkreettisen delta datan, kun sitä vertailussa kysytään. Ei qsortin pitäisi tuollaisessa kaatua, muuta kaatuu kumminkin.

joo...

((long long)a + (long long)b) / 2 antaa eri tuloksen, kuin

((long long)a + (long long)b) >> 1

Kääntäjä nimittäin käyttää aritmeettista siirtoa etumerkillisillä kokonaisluvuilla.

Kuudenneksi, tuo mun esittämäni innovaatio on vielä kaukana toimivuudesta. Vittu, että ÖTK voi olla vaikeata. Korvaavasta vertailufunktiosta on vasta usvaisia kuvia...

Vittu

MaKo71
Seuraa 
Viestejä1467
Liittynyt15.11.2006
_jone_

((long long)a + (long long)b) / 2 antaa eri tuloksen, kuin

((long long)a + (long long)b) >> 1

Kääntäjä nimittäin käyttää aritmeettista siirtoa etumerkillisillä kokonaisluvuilla.




Jeps. Muutenhan kakkosella jaon voisi korvata artimeettisella siirrolla, mutta vikatilanne tulee, jos yhteenlaskun tulos on -1. Tällöin jakolasku palauttaa oikein (tehtävässä pyydettiin pyöristämään nollaa kohti) nollan ja shiftaus puolestaan -1:n. Näin ainakin GCC:n versiolla 4.0.2.

Tuskailin joskus tuon shiftauksen ominaisuuden kanssa (ts. -1 jaettuna millä tahansa kakkosen potenssilla on edelleen -1) ja olen sen jälkeen käyttänyt suosiolla jakolaskua ja antanut kääntäjän keksiä, optimoidako vai eikö.

Vierailija
Carloz
Mistä saisi hyvän ja ilmaisen C/C++-kääntäjän Windows Vistalle?



Lataile suorilta vain Qt. En äkkiä keksi miellyttävämpää ympäristöä ja lisäksi Qt itsessään tarjoaa ehkä maailman parhaan reference-manualin.

Uusimmat

Suosituimmat