Let us see if it will swallow this copy/paste:
Trace-basedJust-in-TimeTypeSpecializationforDynamic
Languages
AndreasGal
∗+
,BrendanEich
∗
,MikeShaver
∗
,DavidAnderson
∗
,DavidMandelin
∗
,
MohammadR.Haghighat
$
,BlakeKaplan
∗
,GraydonHoare
∗
,BorisZbarsky
∗
,JasonOrendorff
∗
,
JesseRuderman
∗
,EdwinSmith
#
,RickReitmaier
#
,MichaelBebenita
+
,MasonChang
+#
,MichaelFranz
+
MozillaCorporation
∗
{gal,brendan,shaver,danderson,dmandelin,mrbkap,graydon,bz,jorendorff,jruderman}@mozilla.com
AdobeCorporation
#
{edwsmith,rreitmai}@adobe.com
IntelCorporation
$
{mohammad.r.haghighat}@intel.com
UniversityofCalifornia,Irvine
+
{mbebenit,changm,franz}@uci.edu
Abstract
DynamiclanguagessuchasJavaScriptaremoredifficulttocom-
pilethanstaticallytypedones.Sincenoconcretetypeinformation
isavailable,traditionalcompilersneedtoemitgenericcodethatcan
handleallpossibletypecombinationsatruntime.Wepresentanal-
ternativecompilationtechniquefordynamically-typedlanguages
thatidentifiesfrequentlyexecutedlooptracesatrun-timeandthen
generatesmachinecodeontheflythatisspecializedfortheac-
tualdynamictypesoccurringoneachpaththroughtheloop.Our
methodprovidescheapinter-proceduraltypespecialization,andan
elegantandefficientwayofincrementallycompilinglazilydiscov-
eredalternativepathsthroughnestedloops.Wehaveimplemented
adynamiccompilerforJavaScriptbasedonourtechniqueandwe
havemeasuredspeedupsof10xandmoreforcertainbenchmark
programs.
CategoriesandSubjectDescriptorsD.3.4[ProgrammingLan-
guages]:Processors—Incrementalcompilers,codegeneration.
GeneralTermsDesign,Experimentation,Measurement,Perfor-
mance.
KeywordsJavaScript,just-in-timecompilation,tracetrees.
1.Introduction
DynamiclanguagessuchasJavaScript,Python,andRuby,arepop-
ularsincetheyareexpressive,accessibletonon-experts,andmake
deploymentaseasyasdistributingasourcefile.Theyareusedfor
smallscriptsaswellasforcomplexapplications.JavaScript,for
example,isthedefactostandardforclient-sidewebprogramming
Permissiontomakedigitalorhardcopiesofallorpartofthisworkforpersonalor
classroomuseisgrantedwithoutfeeprovidedthatcopiesarenotmadeordistributed
forprofitorcommercialadvantageandthatcopiesbearthisnoticeandthefullcitation
onthefirstpage.Tocopyotherwise,torepublish,topostonserversortoredistribute
tolists,requirespriorspecificpermissionand/orafee.
PLDI’09,June15–20,2009,Dublin,Ireland.
Copyright
c
2009ACM978-1-60558-392-1/09/06…$5.00
andisusedfortheapplicationlogicofbrowser-basedproductivity
applicationssuchasGoogleMail,GoogleDocsandZimbraCol-
laborationSuite.Inthisdomain,inordertoprovideafluiduser
experienceandenableanewgenerationofapplications,virtualma-
chinesmustprovidealowstartuptimeandhighperformance.
Compilersforstaticallytypedlanguagesrelyontypeinforma-
tiontogenerateefficientmachinecode.Inadynamicallytypedpro-
gramminglanguagesuchasJavaScript,thetypesofexpressions
mayvaryatruntime.Thismeansthatthecompilercannolonger
easilytransformoperationsintomachineinstructionsthatoperate
ononespecifictype.Withoutexacttypeinformation,thecompiler
mustemitslowergeneralizedmachinecodethatcandealwithall
potentialtypecombinations.Whilecompile-timestatictypeinfer-
encemightbeabletogathertypeinformationtogenerateopti-
mizedmachinecode,traditionalstaticanalysisisveryexpensive
andhencenotwellsuitedforthehighlyinteractiveenvironmentof
awebbrowser.
Wepresentatrace-basedcompilationtechniquefordynamic
languagesthatreconcilesspeedofcompilationwithexcellentper-
formanceofthegeneratedmachinecode.Oursystemusesamixed-
modeexecutionapproach:thesystemstartsrunningJavaScriptina
fast-startingbytecodeinterpreter.Astheprogramruns,thesystem
identifieshot(frequentlyexecuted)bytecodesequences,records
them,andcompilesthemtofastnativecode.Wecallsuchase-
quenceofinstructionsatrace.
Unlikemethod-baseddynamiccompilers,ourdynamiccom-
pileroperatesatthegranularityofindividualloops.Thisdesign
choiceisbasedontheexpectationthatprogramsspendmostof
theirtimeinhotloops.Evenindynamicallytypedlanguages,we
expecthotloopstobemostlytype-stable,meaningthatthetypesof
valuesareinvariant.(12)Forexample,wewouldexpectloopcoun-
tersthatstartasintegerstoremainintegersforalliterations.When
bothoftheseexpectationshold,atrace-basedcompilercancover
theprogramexecutionwithasmallnumberoftype-specialized,ef-
ficientlycompiledtraces.
Eachcompiledtracecoversonepaththroughtheprogramwith
onemappingofvaluestotypes.WhentheVMexecutesacompiled
trace,itcannotguaranteethatthesamepathwillbefollowed
orthatthesametypeswilloccurinsubsequentloopiterations.
