Back to site
Since 2004, our University project has become the Internet's most widespread web hosting directory. Here we like to talk a lot about web servers, web development, networking and security services. It is, after all, our expertise. To make things better we've launched this science section with the free access to educational resources and important scientific material translated to different languages.

Obilazak V8: kompletni compiler

Tokom poslednjih pet godine, JavaScript performanse su se povećale neverovatnom brzinom, uglavnom zahvaljujući prelasku sa prevođenja (interpretation) na JIT popunjavanje (compilation) u JavaScript virtuelnim mašinama. Ovo je mnogo povećalo korisnost JavaScript-a i web aplikacija uopšteno. Kao rezultat, JavaScript je sada pokretačka snaga HTML5, sledećeg talasa web tehnologija. Jedan od prvih JavaScript motora koji su generisali i sprovodili originalni kod (native code) bio je V8, koji se koristi u Google Chrome, Android pretraživaču, WebOS i drugim projektima, kao što je Node.js.

Pre nešto više od godinu dana, pridružio sam se timu u mojoj kompaniji koji optimizuje V8 za našu posebnu ARM mikroarhitekturu. Od tada, video sam da se performansa SunSpider-a duplira, i da se V8 benchmark performansa povećava za oko 50%, zahvaljujući doprinosima i hardware-a i software-a.

V8 je veoma interesantan projekat za rad, ali na žalost, dokumentacija za njega je malo rasuta. U narednih nekoliko članaka, pružiću pregled visokog nivoa, koji će, nadam se, biti interesantan za svakoga ko je zainteresovan za unutrašnjost virtuelnih mašina ili compiler-a.

Arhitektura visokog nivoa

V8 popunjava sav JavaScript u izvorni kod pre izvođenja. Nema prevođenja niti bytecode-a. Popunjavanje se sprovodi jedna po jedna funkcija (suprotno popunjavanju na osnovu tragova (trace-based) koje se koristi u TraceMonkey, starom FireFox VM). Obično, funkcije se zapravo ne popunjavaju sve do prvog puta kada su pozvane, tako da ako uljučite veliku skriptu biblioteke (library script), VM neće gubiti vreme na popunjavanje njenih delova koji se ne koriste.

V8 zapravo koristi dva različita JavaScript compiler-a. Volim da mislim o njima kao o jednostavnom compiler-u i pomoćnom compiler-u. Kompletni compiler (koji je u fokusu ovog članka) je neoptimizirajući compiler. Njegov posao je da proizvede izvorni kod što je brže moguće, što je važno da vreme učitavanja strane bude što kraće. Crankshaft je optimizirajući compiler. V8 popunjava sve prvo sa kompletnim compiler-om, zatim koristi ugrađeni compiler da selektuje “vruće” funkcije koje će optimizovati Crankshaft. S obzirm da je V8 uglavnom single-threaded (od verzije 3.14), izvođenje se pauzira dok radi bilo koji od compiler-a. Shodno tome, oba compiler-a su dizarnirana da brzo proizvedu kod umesto da troše dosta vremena na proizvodnju veoma efikasnog koda. U budućim verzijama V8, Crankshaft (ili bar njegov deo) će raditi u posebnom thread-u, istovremeno sa izvođenjem JavaScript-a, omogućavajući skuplju optimizaciju.

Zašto nema bytecode-a?

Većina VM-ova sadrži prevodilac bytecode-a, ali to primetno nedostaje u V8. Možete se zapitati zašto postoji kompletan compiler kada može biti lakše popuniti bytecode i to sprovesti. Ispostavilo se da popunjavanje do neoptimizovanog izvornog koda nije zapravo toliko skuplje od popunjavanja do bytecode-a. Pogledajte procese popunjavanja za oba:

Bytecode popunjavanje:
  • Analiza sintakse (Syntax analysis (parsing)
  • Analiza svrhe (Scope analysis)
  • Prevođenje drveta sintakse do bytecode-a (Translate syntax tree to bytecode)
Izvorno popunjavanje:
  • Analiza sintakse (Syntax analysis (parsing)
  • Analiza svrhe (Scope analysis)
  • Prevođenje drveta sintakse do izvornog (Translate syntax tree to native)

U oba slučaja, potrebno je da rastavimo izvorni kod i proizvedemo abstraktno sintaksičko drvo (AST). Moramo da sprovedemo analizu svrhe, koja će nam reći da li se svaki simbol odnosi na lokalnu promenjivu, promenjivu konteksta (koju koriste closures) ili globalno vlasništvo. Korak prevođenja je jedini deo koji se razlikuje. Ovde možete uraditi veoma složene stvari, ali ako želite da compiler bude što je moguće brži, potrebno je da izvršite direktno prevođenje: svaki čvor na sintaksičkom drvetu biće preveden u fiksnu sekvencu bytecode-ova ili izvornih instrukcija.

Sada razmislite kako bi ste napisali prevodioca za bytecode. Naivna implementacija bila bi omča koja hvata sledeći bytecode, ulazi u veliki switch statement i izvodi fiksnu sekvencu instrukcija. Postoji nekoliko načina da se ovo poboljša , ali svi se svode na istu strukturu.

Umesto generisanja bytecode-a i korišćenja prevodilačke omče, šta bi bilo da samo izdamo odgovarajuću fiksnu sekvencu instrukcija za svaku operaciju? Zapravo, ovako upravo radi kompletni compiler. Ovo uklanja potrebu za prevodiocem, i pojednostavljuje tranzicije izmedju neoptimizovanog i optimizovanog koda.

Uopšteno, bytecode je koristan u situacijama gde možete uraditi deo posla compiler-a unapred. Ovo nije slučaj unutar web pretraživača, tako da kompletni compiler ima više smisla za V8.

Inline caches: ubrzavanje neoptimizovanog koda

Ukoliko pogledate ECMAScript specifikaciju, naći ćete da je većina operacija apsurdno komplikovana. Uzmite + operatora kao primer. Ukoliko su oba operanda brojevi, ona sprovodi sabiranje. Ukoliko je neki od operanda niz, ona sprovodi povezivanje niza (string concatenation). Ukoliko su operandi nešto drugo osim brojeva ili nizova, neka komplikovana (verovatno definisana od strane korisnika) konverzija ka prostom se odvija pre sabiranja brojeva ili povezivanja nizova. Samo gledanjem izvornog koda, nema načina da se kaže koje instrukcije bi trebalo zadati. Property loads (primer: o.x) su dobar primer još jedne potencijalno komplikovane operacije. Pogledom na kod, ne možete reći da li load-ujete normalnu funkciju u okviru objekta (“sopstvena” funkcija), funkciju prototipa objekta, ‘getter’ metodu, ili neki magični callback definisan pretraživačem. Može se desiti da funkcija čak ni ne postoji. Ukoliko treba da hendlujete sve moguće slučajeve u poptuno popunjenom kodu, i ova jednostavna operacija može da zahteva stotine instrukcija.

Inline caches (ICs) nude elegantno rešenje za ovaj problem. Inline cache je zapravo funkcija sa višestrukim mogućim implementacijama (obično generisan u letu) koji može biti pozvan da reši specifičnu operaciju. Prethodno sam pisao o polymorphic inline caches za pozive funkcija. V8 koristi IC-jeve za mnogo širi set operacija: kompletni compiler koristi IC-jeve za implementaciju load-ova, prodavnica, poziva, binarnih, jednostrukih i uporednih operacija, kao i ToBoolean implicitne operacije.

Implementacija IC-ja se naziva stub. Stub-ovi se ponašaju kao funkcije u smislu da ih pozivate, i oni se vraćaju, ali oni ne set up-uju obavezno stack frame i ne prate potpunu konvenciju pozivanja. Stub-ovi se obično generišu ‘u letu’, ali za uobičajene slučajeve, oni mogu biti cache-irani i ponovo korišćeni od strane više IC-ja. Stub koji implementuje IC, tipično sadrži optimizovan kod koji hendluje tipove operanada sa kojima se taj posebni IC susreo u prošlosti (zato se i zove cache). Ukoliko stub naiđe na slučaj koji nije pripremljen da hendluje, on ‘promašuje’ i poziva C++ runtime kod. Runtime hendluje slučaj, zatim generiše novi stub koji može da hendluje promašeni slučaj (kao i prethodne slučajeve). Poziv na stari stub u kompletnom popunjenom kodu se ponovo ispisuje da poziva novi stub, i izvođenje se nastavlja kao da je stub pozvan normalno.

Hajde da pogledamo jednostavan primer: property load.

function f(o) { return o.x; }

Kada kompletni compiler prvi put generiše kod za ovu funkciju, koristiće IC za load. IC se pokreće u neinicijalizovanom stanju, koristeći trivijalni stub koji ne hendluje ni jedan slučaj. Evo kako kompletni popunjeni kod poziva stub.

;; full compiled call site ldr r0, [fp, #+8] ; load parameter "o" from stack ldr r2, [pc, #+84] ; load string "x" from constant pool ldr ip, [pc, #+84] ; load uninitialized stub from constant pool blx ip ; call the stub ... dd 0xabcdef01 ; address of stub loaded above ; this gets replaced when the stub misses

(Izvinite ako niste upoznati sa sastavljanjem ARM-a. Nadam se da će komentari pojasniti šta se dešava.)

Evo koda za neinicirani stub:

;; uninitialized stub ldr ip, [pc, #8] ; load address of C++ runtime "miss" function bx ip ; tail call it ...

Prvi put kada je ovaj stub pozvan, on će ‘promašiti’, i runtime će generisati kod da hendluje onaj slučaj koji je uzrokovao promašaj. U V8, najčešći način za čuvanje funkcije je na fiksnom offset-u u okviru objekta, tako da pogledajmo primer toga. Svaki objekat ima pointer ka mapi, koja je uglavnom nepromenljiva struktura koja opisuje strukturu objekta. In-object load stub će proveriti mapu objekta u odnosu na poznatu mapu (onu koja se vidi kada neinicirani stub promaši) da brzo proveri da li objekat ima željene karakteristike na pravim pozicijama. Ova provera mape nam omogućava da izbegnemo skupi hash table lookup.

;; monomorphic in-object load stub tst r0, #1 ; test if receiver is an object beq miss ; miss if not ldr r1, [r0, #-1] ; load object's map ldr ip, [pc, #+24] ; load expected map cmp r1, ip ; are they the same? bne miss ; miss if not ldr r0, [r0, #+11] ; load the property bx lr ; return miss: ldr ip, [pc, #+8] ; load code to call the C++ runtime bx ip ; tail call it ...

Dok god ovaj izraz treba da hendluje samo in-object property loads, load može biti izveden brzo bez dodatnog generisanja koda. S obzirom da IC može da hendluje samo jedan slučaj, on je u monomorfnom stanju. Ukoliko se pojavi neki drugi slučaj, i IC opet promaši, biće generisan megamorfni stub koji je uopšteniji.

Nastaviće se...

Kao što možete videti, kompletni compiler ispunjava svoj cilj da brzo generiše solidan baseline kod koji dobro radi. S obzirom da se IC-jevi koriste široko, kompletni popunjeni kod je veoma generičan, što kompletni compiler čini veoma jednostavnim. IC-jevi čine kod veoma fleksibilnim, u stanju da hendluje bilo koji slučaj.

U sledećem članku, pogledaćemo kako V8 predstavlja objekte u memoriji, dozvoljavajući O(1) pristup u većini slučajeva bez bilo kakve strukturne specifikacije od strane programera (kao sto je deklaracija klase).





Published (Last edited): 18-06-2013 , source: http://www.jayconrod.com/posts/51/a-tour-of-v8-full-compiler