Joel on Software

Joel on Software   Joel, szoftverekről

 

További "Joel on Software" cikkek magyar nyelven

További "Joel on Software" cikkek angol nyelven

E-mail a szerzőnek (angol nyelven)

 

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 Vancouver BCszü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!"

kansas(Egy kis agytorna, mik a valódi számok a viccben ?) Ez a gyenge vicc azt hivat
ott 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.

[Image]Múlt héten arról irtam, hogy miért nem lehetséges a SELECT author FROM books SQL lekérdezést kellően gyorsra implementálni, ha az adatok XML formátumba tárolódnak. Ha valaki nem értené, hogy ez hogyan illeszkedik a CPU-khoz és a bájtokhoz olvasson tovább, hamarosan kiderül.

Hogyan valósítják meg egy relációs adatbázissal a SELECT author FROM books lekérdezést? Egy relációs adatbázisban minden sor a táblában (esetünkben a books táblában)  ugyanolyan hosszúságú és minden mező pontosan ugyanolyan távolságra van a rekord elejétől. Tehát ha minden rekord a books táblában pontosan 100 byte hosszú és az author mező a 23 byte-tól kezdődik, akkor az author mezőket a 23, 123, 223, 323 helyeken találjuk meg. Hogyan lehetne implementálni  a következő mezőre ugrást az eredményben? A következő képpen:

pointer += 100;

Egy CPU utasítás. Gyooorsssssss.

Most nézzük meg a Book táblát az XML file-ban.

<?xml bla bla>
<books>
     <book>
          <title>UI Design for Programmers</title>
          <author>Joel Spolsky</author>
     </book>
     <book>
          <title>The Chop Suey Club</title>
          <author>Bruce Weber</author>
     </book>
</books>

Egy gyors kérdés. Hogyan lehet lekódolni a következő rekordra mozgást?

Hoppá...

Ebben a helyzetben egy jó programozó azt mondaná, hogy olvassuk be az XML-t egy fába, amivel sokkal gyorsabban tudunk dolgozni. Amennyit a SELECT author FROM books végrehajtásához a CPU-nak dolgoznia kell könnyfakasztó. Bármelyik fordító írásában jártas ember megmondhatja, hogy a lexikális elemzés és a (parsing) forrás fileo-k beolvasása a leglassab része a fordítási folyamatnak. Ez a része a dolognak ( amikor megpróbáljuk a szintaxis fát felépíteni a memóriában) nagyon sok sztring művelettel jár - ami mint tudjuk nagyon lassú – és sok memória foglalással is - ami szintén igen lassú. Ami azt is feltételezi, hogy van elég memóriánk ahhoz, hogy ezt egyszerre megtegyük. A relációs adatbázisban egy rekordról a masikra mozgás az fix és ez egy CPU utasítás. Ez a tervezésből adódik. És hála a memory mapped file-oknak csak azokat a részeket kell a memóriában tartani, amelyekre ténylegesen szükségünk van. Az XML esetében hogyha előre olvasod a file-t akkor a rekordra való mozgás konstans de, az előolvasás nagyon hosszú, ha nem hajtod verge az előolvasást  akkor a rekordról rekordra mozgás változó lesz a hosztól függően és többszáz CPU ciklus költségű.

Mit jelent ez? Azt hogy nem használhatsz XML-t ha gyors kódot akarsz és sok adatod van. Ha csak kevés adatot akarsz kezelni, vagy nem számít a sebesség az XML tökéletes választás. És ha ötvözni akarod a két féle megközelítés előnyös tulajdonságait, akkor szükséged lesz valamiféle módszerre a metaadat eltárolására az XML-ről, valami hasonlóra mint a Pascal sztringek első bájtja, ami valamiféle információt ad arról, hogy mi hol található a file-ban, így aztán nem kell előreolvasnod. Persze így nem használhatsz szövegszerkesztőt a file editálására mivel elrontja a metaadatot, így hát a metaadattal turbózott fileunk már nem is igazán XML.

Az a három ember pedig, akik idáig velem tartottak, remélem tanultak valami újat vagy elrágodtak a dolgon. Remélem,hogy az ilyen első évfolyamon tanított dolgokról való eszmefutatásom, mint strcat és a malloc függvények működése új szempontokat adhat a magasabb szintű, stratégia és architektúra szintű döntések meghozatalánál és az olyan technológiák helyes kezeléséhez, mint például az XML. Házifeladatként pedig gondolkozzunk el azon hogy miért fognak a Transmeta chipek mindig lassúnak tűnni a legtöbb embernek. Vagy, hogy a korai HTML TABLE specifikáció miért lett, annyira rosszul megtervezve, hogy a nagyobb táblákat tartalmazó HTML oldalakat nem lehett gyorsan megjeleniteni a modems kapcsolattal rendelkező felhasználok gépein. Vagy miért olyan gyors a COM mint amilyen és miért nem gyors, ha processz határokat lépsz át vele. Vagy hogy az NT tervezői miért tették a megjelenítés kódját a kernelbe a felhasználói terület helyett.

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.

Emacs



A fordítás alapjául szolgáló angol cikk címe: Back to Basics  

Joel Spolsky a Fog Creek Software alapítója. A Fog Creek egy apró szoftvercég, székhelye New York City. Joel a Yale egyetemen végzett, majd programozóként és menedzserként dolgozott a Microsoftnál, a Viacomnál és a Junonál.


Az itt olvasható oldalak egyetlen személy véleményét tükrözik.
Minden itt megjelenő tartalom ©1999-2005 Joel Spolsky. Minden jog fenntartva.

FogBUGZ | CityDesk | Fog Creek Software | Joel Spolsky