Optimizacije u Javi

Zoran Budimlić

Java je razvijena u laboratorijama kompanije Sun Microsystems. Originalni projekat se vodio pod nazivom Oak (hrast), a ime je dobio po hrastovom drvetu u dvorištu Sun-ove laboratorije u Palo Altu u Silicijumskoj dolini. Prvobitna namera je bila da se razvije kompaktan jezik koji bi se koristio za programiranje malih elektronskih uređaja - celularnih telefona, tostera, kreditnih kartica... S brzim razvojem Interneta, razvojni tim Oak-a je uvideo mnogo širi potencijal tako dizajniranog jezika, uspeo je da u to ubedi i predsednika Sun-a Scott McNeally-ja, jezik je preimenovan u Java i formirano je odeljenja Sun-a pod imenom JavaSoft. Ostalo je istorija...

Java i drugi jezici

Java je potpuno objektno-orijentisani jezik: sve promenljive su objekti, osim "primitivnih" celih i racionalnih brojeva. Sintaksa je vrlo slična C++-u, ali Java nije nadskup C-a, tj. nema nezavisnih procedura - svaka procedura mora da bude deo objekta, nema pointera ni eksplicitne alokacije i dealokacije memorije (garbage collector se brine o tome umesto programera). U Javi takođe nema preopterećivanja operatora, višestrukog nasleđivanja, šablona (templates) i, što je najvažnije, jezik je potpuno standardizovan, za razliku od C++-a, gde svaki proizvođač kompajlera ima svoju verziju jezika.
Sva ova pojednostavljenja u odnosu na C++ su dovela do ogromne popularnosti Jave u svetu programera: Java olakšava programiranje, ispravljanje grešaka i čini čitav razvojni proces mnogo bržim. Uz to, Java ima ugrađen efikasan mehanizam prekida, kao i podršku za multiprocesni (tačnije multithreaded) rad i sinhronizaciju između paralelnih procesa.

Slika 1

class Test { int x=0; public void runTest(int a[], int N) { for (int i = 0; a[i] < N; i++) { x = 10; a[i] = a[i]+x; } } }

Sve je ovo lepo, reći će mnogi, ali ne donosi ništa suštinski novo u odnosu na već postojeće jezike i nije dovoljan razlog da Java preuzme primat od C++-a u programiranju. Ovo je potpuno tačno i Java sigurno ne bi bila u poziciji u kojoj se nalazi sada da nije njene glavne osobine - potpune prenosivosti kompajliranog koda između različitih mašina i operativnih sistema, kao i mehanizam koji omogućava sigurno i izolovano izvršavanje Java programa (apleta) na njima. Ova lepa osobina je postignuta time što se Java programi kompajliraju u specijanu vrstu koda - bytecodes. Bajtkod je vrsta abstraktnog mašinskog jezika koji se na klijentu (najčešće) interpretira. Postojanje bajtkoda izoluje mašinu na kojoj se kod izvršava od kompajlera, praveći tako apstraktan sloj koji je identičan na svim platformama. Tako je omogućeno da kod koji kompajler generiše može da se izvršava na bilo kojoj platformi, jer posao koji se odnosi na prilagođavanje programa specifičnoj mašini i operativnom sistemu postaje zaduženje interpretera na toj platformi. Ovakav interpreter se naziva virtuelna mašina, jer simulira abstraktnu mašinu koja izvršava bajtkod direktno. Virtuelne Mašine (VM) za Javu danas postoje na svim glavnim platformama (Windows, Mac, Unix), kao i na mnogim manje poznatim sistemima. Postoje i projekti koji implementiraju VM u hardveru t.j. procesori čiji je mašinski jezik identičan Java bajtkodu.
Sama ideja o kompajliranju programa u kvazi-mašinski kod koji bi bio univerzalan za sve platforme i koji bi se interpretirao ili kompajlirao na svakoj od njih nije novost - slični sistemi su predlagani za različite jezike, od kojih je nama najpoznatiji Smalltalk. Međutim, ti projekti nisu naišli na šire prihvatanje jer im bio je potreban katalizator, koji bi opravdao značajan gubitak na performansama u odnosu na klasične jezike. Java je takav katalizator pronašla u Internetu: mogućnost da se programi prenose preko Interneta i bezbedno izvršavaju na praktično svakom kompjuteru na svetu je po značaju uveliko premašila početne, zaista jako slabe performanse Jave (50-tak puta sporije od kompajliranog C++-a). Aplikacije koje koriste ovu osobinu za izvršavanje i prenos podataka između različitih platformi su vrlo brzo našle primenu u bankarstvu, pošti i mnogim geografski rasprostranjenim i hardverski heterogenim kompanijama. Sve veće kompjuterske kompanije, od kojih su najznačajnije IBM, Symantec, Netscape, Oracle, Corel i Microsoft, su licencirale Javu i počele da razvijaju aplikacije i/ili kompajlere za Javu.

Klasične optimizacije

Ubrzo pošto je razvijen prvi kompajler za Javu, u Sun-u su počeli sa radovima na usavršavanju i unapređivanju koda koji taj kompajler generiše. Nekoliko inženjera je dobilo zadatak da implementira nekoliko "klasičnih" optimizacija, od kojih smo većinu već opisali u prethodnim izdanjima ove naše mini-serije tekstova. U početku je sve izgledalo ružičasto, ali se ispostavilo da Java predstavlja tvrđi orah za optimizaciju nego što bi se to na prvi pogled moglo zaključiti...
Neke od klasičnih optimizacija se mogu sasvim komotno primeniti na Javu: propagacija konstanti, eliminacija "mrtvog" koda, zamena zajedničih podizraza su prve koje padaju na um. I to je otprilike sve: svaka iole naprednija optimizacija se ne može primeniti u originalnom obliku!

Slika 2

class Test { int x = 0; public void runTest(int a[], int N) { x = 10; for (int i = 0; a[i] < N; i++) { a[i] = a[i]+x; } } }

Jedan od glavnih problema sa kojim se susreće pisac kompajlera za Javu je postojanje mehanizma prekida. Ova osobina Jave, koja je vrlo korisna za pisanje čistijih i razumljivijih programa, pa prema tome i za brži razvoj i održavanje softverskih sistema, predstavlja pravu noćnu moru za optimizacione kompajlere. Glavni razlog je to što zvanična specifikacija Jave precizira da mehanizam prekida mora da bude egzaktan, tj. ako se prekid desi, korisnik ne sme da primeti nikakvu razliku u "stanju" programa (vrednosti objekata vidljivih korisniku) u slučaju da se izvršavao optimizovani ili neoptimizovani program. Pogledajmo to na primeru 1: metod runTest dobija dva argumenta, celobrojni niz a[] i ceo broj N. Petlja unutar ovog methoda prolazi kroz niz a[] i dodaje 10 na sve brojeve koji su manji od N, sve dok ne naiđe na element niza koji nije manji od N. Odmah pada u oči (kako čitaocu tako i kompajleru) da naredba dodele vrednosti promenljivoj x unutar petlje ne zavisi od iteracija petlje i da se ona može izbaciti izvan petlje (slika 2).
Ova optimizacija je generisala brži (telo petlje izvršava jednu naredbu umesto dosadašnje dve), ali nažalost nekorektan kod. Pogledajmo šta bi se desilo u slučaju da runTest() dobije prazan niz a[]: test na početku petlje a[i] < N bi izazvao prekid ArrayIndexOutOfBoundsException u prvoj iteraciji, a dodela vrednosti promenljivoj x se nikada ne bi desila u originalnom programu, ali bi se desila u "optimizovanom". U slučaju da je korisnik naše klase Test pozvao runTest iz koda koji ume da prihvati i obradi ovakav prekid, on bi mogao da pročita vrednost promenljive x i da vidi da je ta vrednost 10 umesto korektne vrednosti 0. Zanemarimo u ovom trenutku činjenicu da i u slučaju da niz a[] nije prazan, runTest nije baš najkorektnije napisan metod, pošto će se prekid ArrayIndexOutOfBoundsException svakako desiti u poslednjoj iteraciji petlje u slučaju da su svi elementi niza a[] manji od N.

Slika 3

class Test { int x = 0; public void runTest(int a[], int N) { int i = 0; if (a[0] < N) { x = 10; a[0] = a[0]+x; for (i = 1; a[i] < N; i++) { a[i] = a[i]+x; } } } }

Kompajleru posebno "ide na živce" činjenica da je ovakav scenario jako redak: u najvećem broju slučajeva runTest će dobiti neprazan niz, a optimizovani kod će raditi identično originalu (samo brže, naravno). Čak i kada runTest dobije prazan niz, u najvećem broju slučajeva korisnik neće imati mehanizam koji "hvata" pomenuti prekid i ispituje vrednost promenljive x, već će mehanizam prekida prijaviti istu grešku i izaći u operativni sistem u oba slučaja. Mehanizam prekida se najčešće koristi za vanredne situacije, kada se nešto dešava u jako malom broju slučajeva, a ne kao generalna alatka za programiranje (osim ako niste pisac test programa koji pokušavaju da "uhvate" ovakve pogrešne optimizacije u kompajlerima). Nažalost, ne postoji kategorija za "99.9% korektne" optimizacije, pa se opisana ideja, ma koliko izgledala privlačno, ne može primeniti.

Dokaži ako umeš

Srećom, nije sve tako crno: problem se može jednostavno rešiti tzv. "ljuštenjem" prve iteracije petlje sa slike 3 - to je optimizacija koja se vrlo često primenjuje u kompajlerima za paralelne računare. Prva iterakcija petlje je na ovaj način izdvojena od ostatka petlje, tako da se prekid koji se ranije dešavao u prvoj iteraciji petlje sada dešava u okviru if naredbe. U slučaju da je niz a[] prazan, prekid će se desiti prilikom izvršavanja testa a[0] < N i vrednost promenljive x će ostati netaknuta.
Pokušaj da se ovaj postupak generalizuje dovodi nas do ozbiljnijih problema. Optimizacija koja premešta kod (a to je svaka ozbiljnija optimizacija koja donosi značajne dobitke u brzini) mora da vodi računa o prekidima. Jedno od mogućih rešenja smo već opisali: kompajler mora da osigura da naredbe koje potencijalno mogu da izazovu prekid budu premeštene zajedno sa kodom koji se premešta kao posledica optimizacije, ili da ubacuje naredbe koje će izazvati prekid uvek kada i naredbe preko kojih se premešta kod, osiguravajući na taj način da se u slučaju prekida program nađe u korektnom stanju. Ovo, naravno nije uvek moguće niti profitabilno uraditi.
Za prethodnu tehniku je jako korisno uraditi jedan pretprolaz, koji će ispitati sve naredbe u programu i pokušati da dokaže da mnoge od njih neće izazvati prekid prilikom izvršavanja datog programa, iako te naredbe same po sebi mogu da izazovu prekid. Naprimer, naredbe [1] sa slike 4 sama po sebi može potencijalno da izazove prekid NullPointerException, pošto pristupa objektu a. Međutim, pažljiva analiza programa može da dokaže da objekat a nikada nije null prilikom izvršavanja naredbe [1], jer je promenljivoj a dodeljena vrednost na početku metoda runTest, a svi putevi do naredbe [1] zadržavaju tu vrednost.

Klin se klinom izbija

U nekim slučajevima ne može da se dokaže da neka naredba neće izazvati prekid (bilo zbog toga što ta naredba zaista izaziva prekid pod nekim okolnostima, ili zato što kompajler nije dovoljno "pametan" da izvede dokaz), a nije moguće ili nije profitabilno da se veštački ubacuju naredbe koje će izazvati prekid umesto nje. U tom slučaju se i dalje mogu vršiti optimizacije koje premeštaju kod preko te naredbe, naravno uz dodatne komplikacije. Čitavo telo metoda koji se optimizuje se obavije try konstrukcijom, a svi prekidi koji nastanu unutar metoda se "hvataju" specijalnim kodom (exception handler) koji je generisao kompajler. U taj kod je ugrađeno znanje o svim optimizacijama koje su izvršene unutar metoda i svim naredbama koje su "preskočene", iako mogu da izazovu prekid. Ovaj specijalni kod zatim ispituje generisani prekid, utvrđuje da li je izazvan od strane naredbe koja je "preskočena" prilikom optimizacije i u tom slučaju izvrši potrebne modifikacije u stanju sistema, dovede program u korektno stanje (ono stanje u kojem bi bio da nije bilo nikakvih optimizacija) i prosledi prekid dalje na obradu od strane korisnika. Tako smo iskoristili sam mehanizam prekida da rešimo problem koji je na prvom mestu i bio izazvan postojanjem tog mehanizma. Klin se klinom izbija...

Slika 4

public void runTest() { Integer a = new Integer(10); ... x = a.intValue(); // [1] ... }

Ova tehnika se isplati samo ako programer koristi mehanizam prekida za obradu vanrednih situacija, tj. ako se prekidi u programu dešavaju vrlo retko. Tada optimizovani program radi brže od originalnog, prekidi se retko dešavaju, pa se retko dolazi u situaciju da mora da se izvrši (skupa) rekonstrukcija stanja programa... svi su srećni i zadovoljni! Ako je program napisan tako da obilato koristi prekide, može se desiti da se optimizovana varijanta izvršava sporije od originala, ali će se i dalje izvršavati korektno tj. korisnik neće moći da primeti razliku (osim u brzini) između izvršavanja optimizovanog i neoptimizovanog programa.
Slične tehnike se primenjuju prilikom debagovanja optimizovanih programa. U nekim specifičnim situacijama (programi koji vrše real-time obradu, programi koji su suviše veliki ili se suviše dugo izvršavaju da bi se mogli debagovati neoptimizovani) neophodno je koristiti optimizovanu verziju programa prilikom debagovanja. Kada korisnik specificira tačku u kojoj program treba da se zaustavi (breakpoint), debager se susreće sa problemom: neke naredbe su, kao posledica optimizacije premeštene ispred ili iza tačke u kojoj je program zaustavljen, imajući kao posledicu to da neke promenljive u programu imaju nekorektnu (različitu od one koju bi imale u slučaju da je neoptimizovan program zaustavljen u istoj tački) vrednost.
Debager, znajući koje su optimizacije izvršene na datom programu, rekonstruiše korektno stanja programa i prijavljuje korisniku vrednosti promenljivih koje bi one imale da program nije optimizovan. Postoji ipak jedna bitna razlika između debagovanja optimizovanih programa i rekonstrukcije stanja programa koristeći mehanizam prekida. Debager je alatka - ako nije u stanju da odredi korektnu vrednost promenljive, on će to saopštiti korisniku, a korisnik će, uz manje ili veće probleme, nastaviti debagovanje. U našem slučaju kompajler vrši izmene na samom programu i mora da obezbedi mehanizam rekonstrukcije korektnih vrednosti za sve promenljive, inače ne sme primenjivati optimizacije koje bi dovele do nekorektnog stanja. Ovo čini stvari mnogo komplikovanijim i interesantnijim, praveći jako zgodnu oblast za istraživanja.
Sve u svemu, umereno korisna osobina programskih jezika kao što je mehanizam prekida može ozbiljno da zagorča život autorima kompajlera. Ovi potonji, budući jedna dosta bistra grupacija ljudi, brzo pronalaze rešenja koja prevazilaze nastale probleme, što dalje inspiriše tvorce programskih jezika da komplikuju stvari, i tako u nedogled. A sve to za dobrobit programera, što lakše pisanje programa, naklonost korisnika i, naročito, njihova platežna sredstva u obliku zelenih novčanica, kreditnih kartica i čekova. Dobrobit nauke? A da, i to...