Another try at creating havoc.

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.

3 Replies to “Another try at creating havoc.”

Leave a Reply

Your email address will not be published. Required fields are marked *