Syötteen lukeminen c:llä yhtenäiseen merkkijonoon

[samja]

Miten luetaan tehokkaasti stdin kokonaan yhtenäiseen merkkijonoon?
Ongelma on se, ettei tiedä, että kuinka paljon resursseja pitäisi varata mallocilla.

Yksi mahdollisuus on, että tekee linkatun listan node-koolla nbytes(esim 1000), ja aina kun yksi tulee täyteen, hankkii täytettäväksi uuden listajäsenen. Ongelmana on tällöin se, että merkkijono pirstoutuu satunnaisesta kohdista ja operoiminen on vaikeampaa kuin yhtenäisen merkkijonon tapauksessa. Jos linkatun listan yhtenäistää kokonaan uuteen isoon merkkijonoon, menee muistia kaksinkertainen määrä syötteeseen nähden ja jos syöte on iso, voi tulla ongelmia ja muutenkin resursseja kuluu.

Toinen vaihtoehto on ohjata syöte väliaikaistiedostoon, josta sen voi lukea takaisin sopivasti varattuun muistilohkoon. Tämä on mm vähän hidasta.

Onko jotain kätevää ratkaisua ongelmaan?

[_Pete_]

Miten luetaan tehokkaasti stdin kokonaan yhtenäiseen merkkijonoon?
Ongelma on se, ettei tiedä, että kuinka paljon resursseja pitäisi varata mallocilla.

Yksi mahdollisuus on, että tekee linkatun listan node-koolla nbytes(esim 1000), ja aina kun yksi tulee täyteen, hankkii täytettäväksi uuden listajäsenen. Ongelmana on tällöin se, että merkkijono pirstoutuu satunnaisesta kohdista ja operoiminen on vaikeampaa kuin yhtenäisen merkkijonon tapauksessa. Jos linkatun listan yhtenäistää kokonaan uuteen isoon merkkijonoon, menee muistia kaksinkertainen määrä syötteeseen nähden ja jos syöte on iso, voi tulla ongelmia ja muutenkin resursseja kuluu.

Toinen vaihtoehto on ohjata syöte väliaikaistiedostoon, josta sen voi lukea takaisin sopivasti varattuun muistilohkoon. Tämä on mm vähän hidasta.

Onko jotain kätevää ratkaisua ongelmaan?

Itse tekisin niin että varataan aluksi muistialue. Sitten jos syöte on isompi, tehdään realloc + memcpy (+free vanhalle).

Jos siis tosiaankin on pakko pitäytyä yhdessä ja samassa "dynaamisesti" kasvavassa bufferissa.

[samja]

Tuo edellinen ehdotus lienee passeli. Toteutan sen varmaan seuraavaksi jos osaa...


Olen nyt tekemässä linkattua listaa, jonka nodet pitävät sisällään 4095 tavua.

Tietorakenne:

typedef struct blocknode *ptrBlocknode;
typedef struct block *ptrBlock;
typedef struct bstr *ptrBstr;
typedef struct blocknode { char *s; int len; ptrBlocknode next; } BLOCKNODE;
typedef struct block { int nblocks, bytes, nbstrs; ptrBstr *bstrs; ptrBlocknode *blocks; } BLOCK;
typedef struct bstr { int size, width; ptrBlocknode alkub, loppub; char *alkus, *loppus; } BSTR;

Jos resursseja varatessa tulee stoppi ja poistuu exit(1):llä, niin jääkö jo varatut resurssit vapautumatta? Jos exit-vaihtoehto toteutuu, olisi systeemi sen jälkeen ongelmissa. Onko?

[Tommi S.]

Jos resursseja varatessa tulee stoppi ja poistuu exit(1):llä, niin jääkö jo varatut resurssit vapautumatta? Jos exit-vaihtoehto toteutuu, olisi systeemi sen jälkeen ongelmissa. Onko?

Ohjelma ajetaan omassa prosessissaan, ja prosessilla on oma muistialue jota se voi käyttää. Prosessien muistialueet on eristetty toisistaan niin että yksi prosessi ei voi sotkea muiden prosessien toimintaa. Jos prosessin muistialue käy liian pieneksi, ja se haluaa lisää muistia käyttöönsä, niin se voi pyytää kerneliä laajentamaan muistialuettaan esim. juuri malloc komennolla.

Kun prosessi jostain syystä loppuu, joko se poistuu exit(x):llä tai tulee jokin virhe yms., niin kerneli automaattisesti siivoaa käyttämättömän muistialueen pois, eli muistiresurssit eivät jää ohjelman loputtua kummittelemaan varattuina vaikka niille ei tekisikään free:tä. Toinen asia on sitten jos ohjelma esim. luo tiedostoja, näitäkin voidaan kutsua resursseiksi, ja ne eivät automaattisesti poistu.

[samja]

Kun prosessi jostain syystä loppuu, joko se poistuu exit(x):llä tai tulee jokin virhe yms., niin kerneli automaattisesti siivoaa käyttämättömän muistialueen pois, eli muistiresurssit eivät jää ohjelman loputtua kummittelemaan varattuina vaikka niille ei tekisikään free:tä.

Kiitos, hyvä tietää.

Miten käy jos esim malloc-funktio ei palauta muistia eikä muista tarkistaa paluu-osoitetta vaan kirjoittaa sopimattomaan paikkaan, jolloin ohjelma kaatuu. Siivoaako kerneli jäljet myös siinä tapauksessa?

Tein harjoitus-ohjelman aiheesta:
http://ajatusmylly.net/index.php?topic=1239.msg27970#msg27970
Käytetty linkattua listaa.

[Tommi S.]

Kun prosessi jostain syystä loppuu, joko se poistuu exit(x):llä tai tulee jokin virhe yms., niin kerneli automaattisesti siivoaa käyttämättömän muistialueen pois, eli muistiresurssit eivät jää ohjelman loputtua kummittelemaan varattuina vaikka niille ei tekisikään free:tä.

Kiitos, hyvä tietää.

Miten käy jos esim malloc-funktio ei palauta muistia eikä muista tarkistaa paluu-osoitetta vaan kirjoittaa sopimattomaan paikkaan, jolloin ohjelma kaatuu. Siivoaako kerneli jäljet myös siinä tapauksessa?

Joo, aina kun prosessi päättyy mistä tahansa syystä niin kerneli siivoa kaiken siihen liittyvän pois.

Tässä esimerkki reallocilla ja memcpy:llä, joita _Pete_ ehdotti aiemmin. Saattaa olla yksinkertaisempi kuin linkitetty lista. En ole testannut tätä ollenkaan joten joitain bugeja voi olla, mutta perusperiaate pitäisi selvitä:

Koodia: [Valitse]

// jonon koko voi olla pienempikin, sitä kasvatetaan tarvittaessa
int jonon_koko = 1000;

int luetut_merkit = 0;
int puskuriin_luetut_merkit = 0;

char *merkkijono = malloc(jonon_koko * sizeof(char));
char puskuri[100];

while((puskuriin_luetut_merkit = read(STDIN, puskuri, 100)) != 0) {
  // jos meinataan kirjoittaa merkkijonoon enemmän kuin sinne mahtuu niin
  // tuplataan merkkijonon pituus reallocilla
  if ((luetut_merkit+puskuriin_luetut_merkit) > jonon_koko) {
    jonon_koko *= 2;
    merkkijono = realloc(merkkijono, jonon_koko * sizeof(char));
  }
  // kopioidaan puskurin sisältö merkkijonon loppuun
  memcpy(merkkijono+luetut_merkit, puskuri, puskuriin_luetut_merkit);
  luetut_merkit += puskuriin_luetut_merkit;
}

// Merkkijono sisältää nyt stdinin sisällön kokonaisuudessaan.
// Merkkijonon loppuun voisi ehkä vielä lisätä tyhjän merkin
// jotta C-kielen merkkijonofunktiot osaavat käsitellä sitä oikein.

[samja]

Toteutin Tommi S. :n ehdotuksen eräällä testi-ohjelmalla:
http://ajatusmylly.net/index.php?topic=1239.msg28021#msg28021
Hyvin toimi.

Vertailin ratkaisuja ...

Linkitetyn listan versio v2 oli pienillä syötteillä hitaampi kuin suoraa muistilohkoa käyttävä versio v3. Ero tasoittui jos syötteen koko kasvoi. Linkitetty lista voi olla nopeampi jos listasolmujen kokoa kasvatetaan aina tuplaksi, mikäli uutta tarvitaan. En tiedä varmaa, sillä en kokeillut tätä enää.

Erot tulevat siinä, millä menetelmällä syöte luetaan prosessiin. Jos syötettä joutuu käsittelemään monimutkaisesti, niin linkitetty lista syötteen varastoimisessa on varmasti kömpelöä ja hitaampaa myös suuremmilla syötteillä.

[samja]

Tein syötteen lukemisesta testiä:


juha@ape ~/mycode/c $ wc i20.txt
  522560  2619560 18647740 i20.txt


juha@ape ~/mycode/c $ i=0; time while [ $i -lt 15 ]; do cat i20.txt | ./test_stdinread 1 >/dev/null; i=`expr $i + 1`; done

real   0m4.520s
user   0m4.172s
sys   0m0.344s


juha@ape ~/mycode/c $ i=0; time while [ $i -lt 15 ]; do cat i20.txt | ./test_stdinread 2 >/dev/null; i=`expr $i + 1`; done

real   0m4.459s
user   0m4.128s
sys   0m0.344s


juha@ape ~/mycode/c $ i=0; time while [ $i -lt 15 ]; do cat i20.txt | ./test_stdinread 3 >/dev/null; i=`expr $i + 1`; done

real   0m4.429s
user   0m4.016s
sys   0m0.464s


juha@ape ~/mycode/c $ i=0; time while [ $i -lt 15 ]; do cat i20.txt | ./test_stdinread 4 >/dev/null; i=`expr $i + 1`; done

real   0m4.467s
user   0m4.108s
sys   0m0.364s


1)  ./test_stdinread 1  Linkitetty lista, jossa lukemiseen erillistä bufferia
2)  ./test_stdinread 2  Syötteen luku suoraan listasolmuihin
3)  ./test_stdinread 3  Syötteen luku suoraan listasolmuihin, joita tuplataan kooltaan
4)  ./test_stdinread 4  Syötteen luku yhtenäiseen muistilohkoon

Tapaus 3 on suuren syötteen tapauksessa nopein ja kaikki linkitetyn listan versiot voittavat yhtenäiseen muistilohkoon lukevan version. Kaikissa tapauksissa syötettä prosessoidaan tulostamisen verran. Jos prosesointia olisi enemmän, niin yhtenäinen muistilohko alkaisi erottua edukseen myös suuremmilla syötteillä.

[odysseus]

Kun prosessi jostain syystä loppuu, joko se poistuu exit(x):llä tai tulee jokin virhe yms., niin kerneli automaattisesti siivoaa käyttämättömän muistialueen pois, eli muistiresurssit eivät jää ohjelman loputtua kummittelemaan varattuina vaikka niille ei tekisikään free:tä.

Kiitos, hyvä tietää.

Miten käy jos esim malloc-funktio ei palauta muistia eikä muista tarkistaa paluu-osoitetta vaan kirjoittaa sopimattomaan paikkaan, jolloin ohjelma kaatuu. Siivoaako kerneli jäljet myös siinä tapauksessa?

Tein harjoitus-ohjelman aiheesta:
http://ajatusmylly.net/index.php?topic=1239.msg27970#msg27970
Käytetty linkattua listaa.

Tähän täytyy kommentoida kolme seikkaa:

1) Älä _koskaan_ oleta, että Kernel tekisi jotain puolestasi. Jos tekee, niin hyvä homma, mutta älä luota siihen. ->Miksi ihmeessä et käyttäisi free() funktiota virhetilanteessa itse kun ja jos voit? -ja virheenkäsittelyfunktio on sitä varten, että voi!
C-kieli on melkolailla universaali, joten et voi olettaa, että jokin muu (kuin Linux) kernel siivoaa jälkensä! Koodia voidaan portata silti lähes mille tahansa alustalle jos se on Ansia.

2) Jos "ei muista tarkistaa paluu-osoitetta vaan kirjoittaa sopimattomaan paikkaan", on alettava C-kielen lisäharjoitukset, jotta muistaa koodata tarkistukset!

3) Jos "malloc-funktio ei palauta muistia", niin ohjelmassa on virhe, joten sen täytyy hallita tilanne ja kertoa käyttäjälle tai kutsuvalle funktiolle, että nyt tehdään (esimerkiksi mahdollisesti muistin loppumisen vuoksi) exit tai palautetaan virhekoodi.

Nuo kolme edellämainittua keinoa ovat ne, joilla saadaan aikaiseksi selkeää ja bugitonta koodia.
Älä ole "java"-mies. Koodaa kuten "C"-mies, eli jos varaat muistia, niin huolehdi itse myös sen vapauttamisesta. Jos teet jotain, niin älä oleta, että joku siivoaa jälkesi.

Mikäli oletat jälkien siivoituvan automaattisesti, niin siinä tapauksessa unohda void pointterit ja castaukset, sillä ohjelma (datan vastaanottava moduli/finktio) ei välttämättä edes tiedä varausyksikön kokoa. Ja unohtamalla void pointterin käytön, menetät lähes kaiken C-kielen eduista.

Muistakaa, että C-kieli on ehdottomasti maailman joustavin, mutta samalla myös vaarallisin ja erittäin virhealtis.