string egyetlen karakteréből egészet

Egy kis elgondolkodtato…
Spolsky altal leirt a problema a sztring hasznalatakor itt:

http://hungarian.joelonsoftware.com/Articles/BacktoBasics.html

Vissza az alapokhoz

Szerző: Joel Spolsky
Fordította: Krisztián Gyuris
2001. December 11.


Általában sok időt töltünk az olyan magasszintű dolgok megvitatásával, mint a .NET és a Java összehasonlítása, XML stratégia, a Lock-In, versenystratégia, szoftver tervezés, architektúra és így tovább. Ezek a dolgok csak egy rétege a tortának, ha úgy tetszik. A legfelsőbb réteg a stratégia. Eggyel alatta az architektúrák vannak pl .NET és ez alatt pedig olyan fejlesztői eszközök, mint a Java vagy platformok, mint a Windows.

Menj lejjebb egy szintet. Dll-k? Objektumok? Eljárások? Nem! Lejjeb! Addig a pontig ahol már a programsorokról van szó.

Még mindig nem elég. Ma a CPU-król szeretnék beszélni. Egy kis darab szilikonmorzsa, amiben bájtok szaladgálnak. Tegyél úgy egy pillanatra mintha kezdő programzó lennél. Felejts el mindent, amit idáig tudsz a programozásról, a menedzsmentről és menj vissza a Neumann féle elmélethez. Felejtsd el a J2EE-t egy pillanatra. Gondolkodj bájtokban.

Miért erre szükség? Azt hiszem néhány hiba, amit az emberek elkövetnek a stratégia szintjén abból fakad, hogy egyes alapelveket nem teljesen vagy egyáltalán nem értenek. Egy gyönyörű palotát építettél, de az épület gyenge alapokon nyugszik. Így aztán egy jó erős beton alap helyett egy gyenge alapra építkezel. A palota jól néz ki, de a csap leesik a a fürdőszobában és gőzöd sincs, hogy miért.

Most vegyünk egy nagy levegőt. Tarts velem, egy kis gyakorlatra.

Emlékszel hogyan működnek a C sztringek: egy csomó bájtot tartalmaznak, amit egy null karakter követ (ennek az értéke nulla). Ennek két nyilvánvaló következménye van:

1.Nem tudjuk megmondani a sztring hosszát anélkül, hogy, végig ne menjünk rajta a null karakterig.

2.Nem lehetnek nullák a sztringben. Tehét bináris állományok, mint például JPEG tárolására nem alkalmas egy C sztring.

Miért működnek a C sztringek így? Azárt mert a PDP-7 mikroprocesszor, amelyen megalkották a UNIX-t és a C programozási nyelvet rendelkezett ASCIIZ sztring típussal ASCIIZ “ASCIIZ Z-vel (zéróval) a végén”.

Ez az egyetlen mód arra, hogy sztringeket tároljunk? Nem, valójában ez az egyik legrosszab megoldás. Egyszerűbb programoknál, programozási felületeknél, operációs rendszereknél, osztálykönyvtáraknál, óvakodnod kell az ASCIIZ sztringektől, mint a pestistől. Miért?

Kezdjük azzal, hogy megirjuk a strcat függvényt, amivel egy függvényt összefűzhetünk egy másikkal.

void strcat( char* dest, char* src )
{
     while (*dest) dest++;
     while (*dest++ = *src++);
}

Ha jobban megnézed a kódot könnyen rájöhetsz hogyan is működik. Elöször, végigmegyünk az első sztringen a nulla karakterig. Amikor megtaláltuk, végigmegyünk a második sztringen, egyenként átmásolva a karaktereket.

Ez a fajta sztring kezelés és összefűzés elég jó Kernighan-nek és Ritchie-nek, de megvannak a hátrányai. Itt van mindjárt egy probléma. Tegyük fel, hogy van egy rakás név, amit egy sztringgé szeretnénk összefűzni:

char bigString[1000];     /* Nem tudom, hogy milyen hosszú lesz... */
bigString[0] = '\\0';
strcat(bigString,"John, ");
strcat(bigString,"Paul, ");
strcat(bigString,"George, ");
strcat(bigString,"Joel ");

Ez így működik ugye? Igen. És egy tiszta és szép megoldás.

Milyen a teljesítménye? Olyan gyors amilyen csak lehet? Jól skálázható? Ha egymillió sztringünk lenne összefűzésre, akkor is ezt a megoldást használnánk?

Nem. Ez a kód a “Shlemiel féle festő algoritmust” használja. Ki az a Schemiel? Ime a vicc:

Schemielt felveszik útkarbantartónak, Neki kell az elvalasztóvonalat festeni az út közepére. Az első napon magához vesz egy vödör festéket és a nap végére 300 méternyi vonalat fest fel az útra. "Ez kiváló!" mondja a főnöke, "kiváló munkaerő vagy!" és ad neki egy dollárt.

A következő napon, csak 150 méter vonalat fest. "Nos, ez nem olyan sok mint tegnap, de még mindig elégedett vagyok. 150 méter igen szép teljesítmény." és add neki egy dollárt.

A következő nap Schemiel csak 30 méterrel végez. "Csak 30 méter!" ordít a főnök. "Ez elfogadhatatlan! Ez első napon tízszer ennyit festetél! Mi folyik itt?"

"Nem tehetek róla, uram" válaszolja Schemiel. "Minden nap messzebre és messzebre kerülök a festékes vödörtől!"

(Egy kis agytorna, mik a valódi számok a viccben ?) Ez a gyenge vicc azt hivatott illusztrálni mi megy végbe, amikor az strcat függvényt használod. Mivel az strcat függvénynek végig kell menni a cél sztringen minden esetben, a zéro karakter miatt újra és újra, ezért nagyon lassú lesz a fent mutatott ejárás és nem skálázható jól. Nagyon sok mindennap használt kódnak ez a baja. Nagyon sok file rendszert implementáltak úgy, hogy a teljesitmeny drámaian csökken ha több ezer file van egy könyvtárban. Próbálj megnyitni egy telepakolt Windows szemetest, hogy lásd ezt a hatást a gyakorlatban is – perceket vesz igénybe amig feljön az ablak, ami nincsen lineáris kapcsolatban a fileok számával. Valahol elrejtve ott dolgozik egy “Schemiel féle festő algoritmus”. Bármikor amikor úgy tűnik, hogy lineáris kapcsolat kell, hogy legyen és ehelyett négyzetes adódik, keress rejtett Schemieleket. Gyakran a programozói könyvtárakban van elrejtve. Egy sor strcat-ról vagy egy strcat ciklusbamagban nem ordít négyzetes teljesítményről, pedig erről van szó.

Hogyan lehet ezt kiküszöbölni? Néhány eszes C programozó megalkotta a saját strcat függvényét, ime:

char* mystrcat( char* dest, char* src )
{
     while (*dest) dest++;
     while (*dest++ = *src++);
     return --dest;
}

Mit is értünk el itt? Nagyon kis többlet munkával visszaadjuk az új hosszú sztring végét. Igy az ezt használó kód hozzá tud illeszteni egy új sztringet, anélkül hogy újra végig kellene menni az egész sztringen:

char bigString[1000];     /* Nem tudom, hogy milyen hosszú lesz... */
char *p = bigString;
bigString[0] = '\\0';
p = mystrcat(p,"John, ");
p = mystrcat(p,"Paul, ");
p = mystrcat(p,"George, ");
p = mystrcat(p,"Joel ");

Ez igy, természetesen, lineáris teljesítményt eredményez, négyzetes helyett, így hát nem lassul le hogyha nagyon sok sztringet kell összefűzni.

A Pascal nyelv tervezői tudtak erről a problémáról és „megoldották” a problémát úgy, hogy az első bájton tárolták el a sztring hosszát. Ezt a fajta sztringet Pascal sztringnek nevezzük. Tartalmazhatnak nullákat és nem nullára végződnek. Mivel a bájt csak 0 és 255 között képes számokat ábrázolni ezért a Pascal sztring nem lehet 255-nél hosszabb, mivel a Pascal sztring nem tartalmaz nulla karaktert ezért pontosan ugyanakkora helyet foglal el mint egy 255 karakter hosszú ASCIZ sztring. A nagy erőssége a Pascal sztringnek az hogy nem kell végigszaladni rajta, hogy meg tudjuk mondani a hosszát. A hossz információ költsége egy Pasal sztring esetében egyetlen utasítás szemben egy ciklussal. Ez sokkal gyorsabb.

A régi Machintos operációs rendszer Pascal sztringeket használt. Nagyon sok C programozó más platformokon Pascal típusú sztringeket használt a sebbeségük miatt. Az Excel Pascal sztringeket használ belső műveletekhez ez az amiért néhány helyen a sztringek hossza 255 karakter lehet maximum, és ez az egyik ok amiért az Excel nagyon gyors.

Hosszú időn keresztül, ha Pascal sztringet akartál C-ben használni, valami ilyesmit kellett csinálni:

char* str = "\\006Hello!";

Igen, a bájtokat saját magadnak kellett megszámolni és bedrótoznod a sztring első bájtjába. Egy lusta programozó ezt így oldaná meg, egy lassú programot kapva végeredményként:

char* str = "*Hello!";
str[0] = strlen(str) - 1;

Észrevehetjük, hogy ez a sztring tulajdonképpen egy nulla terminált sztring (a fordítónak köszönhetően) és Pascal sztring is. Ezeket a sztringeket elcseszett sztringeknek kerszteltem el magamban, mivel könnyebb kimondani, mint azt hogy nulla végű pascal sztring, de mivel ez egy korhatár nélküli website így kénytelenek leszünk a hosszabb nevet használni.

Kihagytam egy fontos dolgot az előbb. Emlékszel még erre?

char bigString[1000]; /* Nem tudom, hogy milyen hosszú lesz... */

Mivel ma a bitekről és bájtokról beszélünk ezt nem lett volna szabad kihagynom. Helyesen kellett volna eljárnom: kitalálni hogy mennyi bájtra van szükségem és pontosan annyit foglalni le a memóriából.

Ugye?

Mivel másképpen, egy ügyes hacker a kódból kitalálhatja, hogy 1000 karaktert foglaltam - remélve, hogy elég lesz - és találna valami ügyes módot arra, hogy valahogy egy 1100 bájt hosszú sztringet irjon az 1000 bájt hosszú sztringem helyett, ezzel felül írva a stacket és megváltoztatva a visszatérés címét. Amikor aztán ez a függvény befejezi a futást, lehetőség nyílhat a hacker által irt kód futtatására. Ezt a jelenséget hívják buffer overflow-nak. Régebben ez volt az elsőszámú módszere a hackereknek és féreg programoknak, hogy hozzáférjenek más rendszerekhez, mielőtt az Outlook segítségével széles rétegek számára elérhetővé vált az illegális kód futtatása más gépeken.
Rendben, tehát minden programozó lusta. Ki kellett volna találniuk, hogy mennyi memóriát kellett volna lefoglalni.
De valójában, a C nem könnyíti meg a dolgunkat. Térjünk vissza a Beatles-s példánkra:

char bigString[1000];     /* Nem tudom, hogy milyen hosszú lesz... */
char *p = bigString;
bigString[0] = '\\0';
p = mystrcat(p,"John, ");
p = mystrcat(p,"Paul, ");
p = mystrcat(p,"George, ");
p = mystrcat(p,"Joel ");

Mennyi memóriát kellene lefoglalnunk? Próbáljuk meg most “A Helyes Utat”.

char* bigString;
int i = 0;
i = strlen("John, ")
     + strlen("Paul, ")
     + strlen("George, ")
     + strlen("Joel ");
bigString = (char*) malloc (i + 1);
/* plussz egy byte a null karakternek! */
...

Lassan kezdek elfáradni. Valószínűleg már te is rég magamra hagytál. Nem is hibáztatlak ezért, de tarts velem, mert innentől kezd érdekes lenni.

Mindig végig kell futnunk a sztringen egyszer azért, hogy megmondjuk a hosszát, aztán újra végigfutunk, hogy összefűzzük. Ha Pascal sztringet használunk, akkor legalább a strlen művelet az gyors. Esetleg írhatnánk egy olyan strcat függvényt, amely lefoglalja és hozzádja a szükséges memóriát a cél sztringhez.

Ez felvet egy másik érdekes problémát is. Tudod hogyan működik a malloc függvény? A malloc egy láncolt listában tárolja a szabad memória blokkokat. Amikor meghívod a malloc-t, akkor az végigsétál ezen a láncolt listán, addig amíg a kérésnek megfelelő nagyságú memória blokkot (vagy annál nagyobbat) nem talál. Ezután két részre osztja a blokkot – az egyik a kérésnek megfelelő méretű, a másik pedig a maradék, az első lesz a lefoglalt memória terület és a maradékot (ha van) visszateszi a láncolt listába. Amikor a free függvényt hívod meg, akkor hozzáadja a felszabadítani kívánt blokkot a listához. Esetenként a szabad memória területek listája elaprózódik és amikor neked egy nagyobb darabra lenne szükséged előfordulhat, hogy nincsen akkora memória egyben. Ekkor a malloc függvény timeout-t add és elkezdi a szabad memória láncot rendezgetni és a szabad darabokat nagyobb darabokká összeállítani. Ez körübelül 3 és fél napot vesz igénybe. Ebből az egészből az következik, hogy a malloc nem igazán gyors (mindig végigszalad a szabad memória listán), és néha, előrejelezhetetlenül és sokkolóan lelassul, amíg újrarendezi a listát. (Ez véletlenül éppen ugyanazt a teljesítmény profilt mutatja, mint az úgynevezett szemétgyűjtő (garbage collection) rendszerek. Nahát, nahát. Tehát azok, akik az ilyen (garbage collection) rendszerek lassúságát kritizálják nincsen teljesen igazuk, hiszen ez hasonlít a malloc működéséhez, jóllehet ez utóbbi nem annyira erőforrásigényes.)

Okos programozók úgy kerülik el a malloc ezen zavaró viselkedését, hogy mindig 2 hatványával felírható nagyságú memóriát foglalnak le. Tudod, 4 byte, 8 byte, 16 byte, 18446744073709551616 byte, és így tovább. Rgyébb okokból, ami nyilvánvaló kell, hogy legyen annak, aki játszott már LEGO-val, ez lecsökkenti a furcsa töredezettségek számát a szabad láncban. Habár ez a módszer pazarlónak látszik, könnyen belátható, hogy így sohasem pazarlunk el többet mint a lefoglalt memória 50 százaléka. Tehát a programod nem használ többet, mint a szükséges memória kétszerese, ami még elfogadható.

Ha megírtad az intelligens strcat függvényt, ami mindig újra allokálja a cél buffert. Mindig pontosan a szükséges nagyságú memóriát kell lefoglalni? Tanárom és mentorom Stan Eisenstat azt tanácsolja, hogy amikor meghívod a realloc függvényt, mindig az előzőleg lefoglalt memória kétszeresét kell lefoglalnod. Ez azt jelenti, hogy a realloc-t nem kell lg n –nél többször meghívnod, aminek így igen jó lesz a teljesítmény karakterisztikája és nem pazarolsz 50%-nál több memóriát.

Akárhogy is. Az élet egyre és egyre bonyolultabb lesz itt bájtföldön. Hát nem vagy szerencsés, hogy nem kell C-ben kódolnod többé? Ott vannak a Perl és Java, VB és XSLT – nagyszerű nyelvek – soha többet nem kell ilyesféle dolgokon gondolkodnod, mivel ezek a nyelvek megoldják ezt helyetted. De néha elsyabadul a pokol és - csőtörés miatt - a szennyvíz elárasztja a nappalid és olyan dolgokon kell törnünk a fejünket, hogy a String vagy a StringBuilder osztályt használd, vagy hasonló dolgok, mivel a fordítók nem elég okosak ahhoz, hogy megértsék, hogy mit is próbálunk elérni és segíteni abban, hogy ne tegyünk Schemiel féle festő algoritmusokat a kódunkba.
....
....

Az ilyen és hasonló kérdések kívánják meg azt hogy bitekben és bájtokban gondolkozzunk és ezek azok a dolgok amik kihatnak a stratégia és architektúrális szintekre is. Ezért gondolom azt, hogy az elsőéves informatikus halgatóknak C-t kell tanulniuk és az alapoktól (CPU) indulva felfelé építkezni. Személy szerint igen botrányosnak találom, hogy nagyon sok informatikai oktatás a Java-t első nyelvként tanítja, mivel “könnyű” és nem kell mindféle zavaró és unalmas malloc-string dolgokkal foglakozni, hanem rögtön az Objektum Orientált programozást mutatja be, amivel minden eddiginél modulárisabb programok írását teszi lehetővé. Ez az oktatás csődje katsztrófa ami nemsokára bekövetkezik. Frissen végzett generációk jönnek, akik jobbra és balra is “Schemiel Festő algoritmus”-t implementálják, azért mert alapvetően nincsen fogalmuk arról, hogy milyen is például egy sztring megvalósítása a legalacsonyabb szinten. Ha valakit jól meg akarsz tanítani valamire a legegyszerűbb dolgoknál kell kezdeni. Mint a Karate Kölyökben. Wax On, Wax Off. Wax On, Wax Off. Csináld ezt három hétig, kiütni egy másik kölyköt ezután már gyerekjáték.