restaurantagave.com Open in urlscan Pro
2607:f748:1301:0:184:107:112:60  Public Scan

Form analysis
0 forms found in the DOM

Text Content

Thumbnails Document Outline Attachments


Previous

Next
Highlight all Match case
Whole words

Presentation Mode Open Print Download Current View

Go to First Page Go to Last Page

Rotate Clockwise Rotate Counterclockwise

Text Selection Tool Hand Tool

Vertical Scrolling Horizontal Scrolling Wrapped Scrolling

No Spreads Odd Spreads Even Spreads

Document Properties…
Toggle Sidebar

Find
Previous

Next
of 14
Presentation Mode Open Print Download Current View

Tools
Zoom Out

Zoom In
Automatic Zoom Actual Size Page Fit Page Width 50% 75% 100% 125% 150% 200% 300%
400%

Trace-based Just-in-Time Type Specialization for DynamicLanguagesAndreas Gal∗+,
Brendan Eich∗, Mike Shaver∗, David Anderson∗, David Mandelin∗,Mohammad R.
Haghighat$, Blake Kaplan∗, Graydon Hoare∗, Boris Zbarsky∗, Jason
Orendorff∗,Jesse Ruderman∗, Edwin Smith#, Rick Reitmaier#, Michael Bebenita+,
Mason Chang+#, Michael Franz+Mozilla
Corporation∗{gal,brendan,shaver,danderson,dmandelin,mrbkap,graydon,bz,jorendorff,jruderman}@mozilla.comAdobe
Corporation#{edwsmith,rreitmai}@adobe.comIntel
Corporation${mohammad.r.haghighat}@intel.comUniversity of California,
Irvine+{mbebenit,changm,franz}@uci.eduAbstractDynamic languages such as
JavaScript are more difficult to com-pile than statically typed ones. Since no
concrete type informationis available, traditional compilers need to emit
generic code that canhandle all possible type combinations at runtime. We
present an al-ternative compilation technique for dynamically-typed
languagesthat identifies frequently executed loop traces at run-time and
thengenerates machine code on the fly that is specialized for the ac-tual
dynamic types occurring on each path through the loop. Ourmethod provides cheap
inter-procedural type specialization, and anelegant and efficient way of
incrementally compiling lazily discov-ered alternative paths through nested
loops. We have implementeda dynamic compiler for JavaScript based on our
technique and wehave measured speedups of 10x and more for certain
benchmarkprograms.Categories and Subject DescriptorsD.3.4 [Programming
Lan-guages]: Processors —Incremental compilers, code generation.General
TermsDesign, Experimentation, Measurement, Perfor-mance.KeywordsJavaScript,
just-in-time compilation, trace trees.1. IntroductionDynamic languagessuch as
JavaScript, Python, and Ruby, are pop-ular since they are expressive, accessible
to non-experts, and makedeployment as easy as distributing a source file. They
are used forsmall scripts as well as for complex applications. JavaScript,
forexample, is the de facto standard for client-side web programmingPermission
to make digital or hard copies of all or part of this work for personal
orclassroom use is granted without fee provided that copies are not made or
distributedfor profit or commercial advantage and that copies bear this notice
and the full citationon the first page. To copy otherwise, to republish, to post
on servers or to redistributeto lists, requires prior specific permission and/or
a fee.PLDI’09,June 15–20, 2009, Dublin, Ireland.Copyrightc©2009 ACM
978-1-60558-392-1/09/06. . . $5.00and is used for the application logic of
browser-based productivityapplications such as Google Mail, Google Docs and
Zimbra Col-laboration Suite. In this domain, in order to provide a fluid
userexperience and enable a new generation of applications, virtual ma-chines
must provide a low startup time and high performance.Compilers for statically
typed languages rely on type informa-tion to generate efficient machine code. In
a dynamically typed pro-gramming language such as JavaScript, the types of
expressionsmay vary at runtime. This means that the compiler can no longereasily
transform operations into machine instructions that operateon one specific type.
Without exact type information, the compilermust emit slower generalized machine
code that can deal with allpotential type combinations. While compile-time
static type infer-ence might be able to gather type information to generate
opti-mized machine code, traditional static analysis is very expensiveand hence
not well suited for the highly interactive environment ofa web browser.We
present a trace-based compilation technique for dynamiclanguages that reconciles
speed of compilation with excellent per-formance of the generated machine code.
Our system uses a mixed-mode execution approach: the system starts running
JavaScript in afast-starting bytecode interpreter. As the program runs, the
systemidentifieshot(frequently executed) bytecode sequences, recordsthem, and
compiles them to fast native code. We call such a se-quence of instructions
atrace.Unlike method-based dynamic compilers, our dynamic com-piler operates at
the granularity of individual loops. This designchoice is based on the
expectation that programs spend most oftheir time in hot loops. Even in
dynamically typed languages, weexpect hot loops to be mostlytype-stable, meaning
that the types ofvalues are invariant. (12) For example, we would expect loop
coun-ters that start as integers to remain integers for all iterations. Whenboth
of these expectations hold, a trace-based compiler can coverthe program
execution with a small number of type-specialized, ef-ficiently compiled
traces.Each compiled trace covers one path through the program withone mapping
of values to types. When the VM executes a compiledtrace, it cannot guarantee
that the same path will be followedor that the same types will occur in
subsequent loop iterations.

Hence, recording and compiling a tracespeculatesthat the path andtyping will be
exactly as they were during recording for subsequentiterations of the loop.Every
compiled trace contains all theguards(checks) requiredto validate the
speculation. If one of the guards fails (if controlflow is different, or a value
of a different type is generated), thetrace exits. If an exit becomes hot, the
VM can record abranchtracestarting at the exit to cover the new path. In this
way, the VMrecords atrace treecovering all the hot paths through the loop.Nested
loops can be difficult to optimize for tracing VMs. Ina na ̈ıve implementation,
inner loops would become hot first, andthe VM would start tracing there. When
the inner loop exits, theVM would detect that a different branch was taken. The
VM wouldtry to record a branch trace, and find that the trace reaches not
theinner loop header, but the outer loop header. At this point, the VMcould
continue tracing until it reaches the inner loop header again,thus tracing the
outer loop inside a trace tree for the inner loop.But this requires tracing a
copy of the outer loop for every side exitand type combination in the inner
loop. In essence, this is a formof unintended tail duplication, which can easily
overflow the codecache. Alternatively, the VM could simply stop tracing, and
give upon ever tracing outer loops.We solve the nested loop problem by
recordingnested tracetrees. Our system traces the inner loop exactly as the na
̈ıve version.The system stops extending the inner tree when it reaches an
outerloop, but then it starts a new trace at the outer loop header. Whenthe
outer loop reaches the inner loop header, the system tries to callthe trace tree
for the inner loop. If the call succeeds, the VM recordsthe call to the inner
tree as part of the outer trace and finishesthe outer trace as normal. In this
way, our system can trace anynumber of loops nested to any depth without causing
excessive tailduplication.These techniques allow a VM to dynamically translate a
pro-gram to nested, type-specialized trace trees. Because traces cancross
function call boundaries, our techniques also achieve the ef-fects of inlining.
Because traces have no internal control-flow joins,they can be optimized in
linear time by a simple compiler (10).Thus, our tracing VM efficiently performs
the same kind of op-timizations that would require interprocedural analysis in a
staticoptimization setting. This makes tracing an attractive and effectivetool
to type specialize even complex function call-rich code.We implemented these
techniques for an existing JavaScript in-terpreter, SpiderMonkey. We call the
resulting tracing VMTrace-Monkey. TraceMonkey supports all the JavaScript
features of Spi-derMonkey, with a 2x-20x speedup for traceable programs.This
paper makes the following contributions:•We explain an algorithm for dynamically
forming trace trees tocover a program, representing nested loops as nested trace
trees.•We explain how to speculatively generate efficient type-specializedcode
for traces from dynamic language programs.•We validate our tracing techniques in
an implementation basedon the SpiderMonkey JavaScript interpreter, achieving
2x-20xspeedups on many programs.The remainder of this paper is organized as
follows. Section 3 isa general overview of trace tree based compilation we use
to cap-ture and compile frequently executed code regions. In Section 4we
describe our approach of covering nested loops using a num-ber of individual
trace trees. In Section 5 we describe our trace-compilation based speculative
type specialization approach we useto generate efficient machine code from
recorded bytecode traces.Our implementation of a dynamic type-specializing
compiler forJavaScript is described in Section 6. Related work is discussed
inSection 8. In Section 7 we evaluate our dynamic compiler based on1 for (var i
= 2; i < 100; ++i) {2 if (!primes[i])3 continue;4 for (var k = i + i; i < 100; k
+= i)5 primes[k] = false;6 }Figure 1. Sample program: sieve of
Eratosthenes.primesisinitialized to an array of 100falsevalues on entry to this
codesnippet.InterpretBytecodesMonitorRecordLIR TraceExecuteCompiled
TraceEnterCompiled TraceCompileLIR TraceLeaveCompiled Traceloop
edgehotloop/exitabort recordingfinish at loop
headercold/blacklistedloop/exitcompiled trace readyloop edge with same typesside
exit to existing traceside exit,no existing
traceOverheadInterpretingNativeSymbol KeyFigure 2.State machine describing the
major activities of Trace-Monkey and the conditions that cause transitions to a
new activ-ity. In the dark box, TM executes JS as compiled traces. In thelight
gray boxes, TM executes JS in the standard interpreter. Whiteboxes are overhead.
Thus, to maximize performance, we need tomaximize time spent in the darkest box
and minimize time spent inthe white boxes. The best case is a loop where the
types at the loopedge are the same as the types on entry–then TM can stay in
nativecode until the loop is done.a set of industry benchmarks. The paper ends
with conclusions inSection 9 and an outlook on future work is presented in
Section 10.2. Overview: Example Tracing RunThis section provides an overview of
our system by describinghow TraceMonkey executes an example program. The
exampleprogram, shown in Figure 1, computes the first 100 prime numberswith
nested loops. The narrative should be read along with Figure 2,which describes
the activities TraceMonkey performs and when ittransitions between the
loops.TraceMonkey always begins executing a program in the byte-code
interpreter. Every loop back edge is a potential trace point.When the
interpreter crosses a loop edge, TraceMonkey invokesthetrace monitor, which may
decide to record or execute a nativetrace. At the start of execution, there are
no compiled traces yet, sothe trace monitor counts the number of times each loop
back edge isexecuted until a loop becomeshot, currently after 2 crossings.
Notethat the way our loops are compiled, the loop edge is crossed beforeentering
the loop, so the second crossing occurs immediately afterthe first
iteration.Here is the sequence of events broken down by outer loopiteration:













More Information Less Information
Close


Enter the password to open this PDF file.


Cancel OK
File name:

-

File size:

-


Title:

-

Author:

-

Subject:

-

Keywords:

-

Creation Date:

-

Modification Date:

-

Creator:

-


PDF Producer:

-

PDF Version:

-

Page Count:

-

Page Size:

-


Fast Web View:

-

Close
Preparing document for printing…
0%
Cancel