1 0 0 1 54 505.7593 cm
 q .55 0 0 .55 0 0 cm
q
1 0 0 1 -55.1171 -331.3474 cm
/Im8 Do
Q
 Q
1 0 0 1 0 -11.2877 cm
q
[]0 d
0 J
0.3288 w
0 0.1644 m
239.1034 0.1644 l
S
Q
1 0 0 1 -54 -494.4716 cm
BT
/F41 8.9664 Tf 54 484.3088 Td[(Figur)18(e)-281(12.)-500(Fraction)-282(of)-281(time)-282(spent)-281(on)-281(major)-282(VM)-281(acti)10(vities.)]TJ/F42 8.9664 Tf 225.1607 0 Td[(The)]TJ -225.1607 -9.9627 Td[(speedup)-343(vs.)-344(interpreter)-343(is)-343(sho)25(wn)-344(in)-343(parentheses)-344(ne)15(xt)-343(to)-343(each)-344(test.)]TJ 0 -9.9626 Td[(Most)-273(programs)-273(where)-273(the)-273(VM)-273(spends)-273(the)-273(majority)-273(of)-273(its)-273(time)-273(run-)]TJ 0 -9.9627 Td[(ning)-265(nati)25(v)15(e)-265(code)-265(ha)20(v)15(e)-265(a)-265(good)-265(speedup.)-265(Recording)-265(and)-265(compilation)]TJ 0 -9.9626 Td[(costs)-278(can)-278(be)-278(substantial;)-278(speeding)-278(up)-278(those)-278(parts)-279(of)-278(the)-278(implemen-)]TJ 0 -9.9627 Td[(tation)-250(w)10(ould)-250(impro)15(v)15(e)-250(SunSpider)-250(performance.)]TJ 0 -47.2477 Td[(inner)-264(loops)-265(become)-264(hot)-264(\002rst\051,)-264(leading)-265(to)-264(much)-264(greater)-264(tail)-265(duplica-)]TJ 0 -9.9627 Td[(tion.)]TJ 11.9552 -9.9626 Td[(YETI,)-396(from)-397(Zaleski)-396(et)-397(al.)-396(\05019\051)-397(applied)-396(Dynamo-style)-396(tracing)]TJ -11.9552 -9.9626 Td[(to)-466(Ja)20(v)25(a)-467(in)-466(order)-467(to)-466(achie)25(v)15(e)-467(inli)1(ning,)-467(indirect)-466(jump)-467(elimination,)]TJ 0 -9.9627 Td[(and)-289(other)-288(optimizations.)-289(Their)-288(primary)-289(focus)-288(w)10(as)-289(on)-288(designing)-289(an)]TJ 0 -9.9626 Td[(interpreter)-242(that)-241(could)-242(easily)-242(be)-241(gradually)-242(re-engineered)-241(as)-242(a)-242(tracing)]TJ 0 -9.9627 Td[(VM.)]TJ 11.9552 -9.9626 Td[(Sug)5(anuma)-190(et)-190(al.)-190(\05018\051)-190(described)-190(re)15(gion-based)-190(compilation)-190(\050RBC\051,)]TJ -11.9552 -9.9626 Td[(a)-310(relati)25(v)15(e)-309(of)-310(tracing.)-310(A)-309(re)15(gion)-310(is)-310(an)-309(subprogram)-310(w)10(orth)-310(optimizing)]TJ 0 -9.9627 Td[(that)-239(can)-239(include)-239(subsets)-239(of)-239(an)15(y)-239(number)-239(of)-239(methods.)-240(Thus,)-239(the)-239(com-)]TJ 0 -9.9626 Td[(piler)-295(has)-296(more)-295(\003e)15(xibility)-296(and)-295(can)-295(potentially)-296(generate)-295(better)-296(code,)]TJ 0 -9.9627 Td[(b)20(ut)-197(the)-197(pro\002ling)-198(and)-197(compilation)-197(systems)-197(are)-197(correspondingly)-198(more)]TJ 0 -9.9626 Td[(comple)15(x.)]TJ/F41 8.9664 Tf 11.9552 -9.9626 Td[(T)74(ype)-475(specialization)-475(f)25(or)-475(dynamic)-475(languages.)]TJ/F42 8.9664 Tf 176.0768 0 Td[(Dynamic)-475(lan-)]TJ -188.032 -9.9627 Td[(guage)-311(implementors)-310(ha)20(v)15(e)-311(long)-310(recognized)-311(the)-311(im)1(portance)-311(of)-311(type)]TJ 0 -9.9626 Td[(specialization)-217(for)-217(performance.)-217(Most)-217(pre)25(vious)-217(w)10(ork)-217(has)-217(focused)-217(on)]TJ 0 -9.9627 Td[(methods)-250(instead)-250(of)-250(traces.)]TJ 11.9552 -9.9626 Td[(Chambers)-374(et.)-374(al)-373(\0509\051)-374(pioneered)-374(the)-374(idea)-374(of)-374(compiling)-373(multiple)]TJ -11.9552 -9.9626 Td[(v)15(ersions)-320(of)-320(a)-320(procedure)-320(specialized)-320(for)-320(the)-320(input)-320(types)-321(in)-320(the)-320(lan-)]TJ 0 -9.9627 Td[(guage)-391(Self.)-392(In)-391(one)-392(implementation,)-391(the)15(y)-392(generated)-391(a)-392(specialized)]TJ 0 -9.9626 Td[(method)-213(online)-213(each)-213(time)-213(a)-213(method)-213(w)10(as)-213(called)-213(with)-214(ne)25(w)-213(input)-213(types.)]TJ 0 -9.9627 Td[(In)-364(another)40(,)-365(the)15(y)-364(used)-364(an)-365(of)25(\003ine)-364(whole-program)-364(static)-364(analysis)-365(to)]TJ 0 -9.9626 Td[(infer)-302(input)-302(types)-301(and)-302(constant)-302(recei)25(v)15(er)-302(types)-301(at)-302(call)-302(sites.)-302(Interest-)]TJ 0 -9.9626 Td[(ingly)65(,)-250(the)-250(tw)10(o)-250(techniques)-250(produced)-250(nearly)-250(the)-250(same)-250(performance.)]TJ 11.9552 -9.9627 Td[(Salib)-223(\05017\051)-222(designed)-223(a)-223(type)-223(inference)-222(algorithm)-223(for)-223(Python)-222(based)]TJ -11.9552 -9.9626 Td[(on)-239(the)-239(Cartesian)-240(Produc)1(t)-240(Algorithm)-239(and)-239(used)-239(the)-239(results)-240(to)-239(special-)]TJ 0 -9.9627 Td[(ize)-250(on)-250(types)-250(and)-250(translate)-250(the)-250(program)-250(to)-250(C++.)]TJ 11.9552 -9.9626 Td[(McClosk)10(e)15(y)-430(\05014\051)-431(has)-430(w)10(ork)-430(in)-431(progress)-430(based)-431(on)-430(a)-430(language-)]TJ -11.9552 -9.9626 Td[(independent)-473(t)1(ype)-473(inference)-473(that)-472(is)-473(used)-472(to)-473(generate)-472(ef)25(\002cient)-473(C)]TJ 0 -9.9627 Td[(implementations)-250(of)-250(Ja)20(v)25(aScript)-250(and)-250(Python)-250(programs.)]TJ/F41 8.9664 Tf 11.9552 -9.9626 Td[(Nati)10(v)10(e)-268(code)-269(generation)-268(by)-268(inter)10(pr)18(eters.)]TJ/F42 8.9664 Tf 152.2911 0 Td[(The)-268(traditional)-269(inter)20(-)]TJ -164.2463 -9.9627 Td[(preter)-353(design)-354(is)-353(a)-354(virtual)-353(machine)-354(that)-353(directly)-354(e)15(x)15(ecutes)-353(ASTs)-354(or)]TJ 0 -9.9626 Td[(machine-code-lik)10(e)-209(bytecodes.)-209(Researchers)-209(ha)20(v)15(e)-209(sho)25(wn)-209(ho)25(w)-210(to)-209(gen-)]TJ 263.0137 643.5866 Td[(erate)-309(nati)25(v)15(e)-309(code)-308(with)-309(nearly)-309(the)-309(same)-308(structure)-309(b)20(ut)-309(better)-309(perfor)20(-)]TJ 0 -9.9627 Td[(mance.)]TJ 11.9552 -9.9626 Td[(Call)-346(threading,)-345(also)-346(kno)25(wn)-346(as)-345(conte)15(xt)-346(threading)-346(\0508\051,)-345(compiles)]TJ -11.9552 -9.9627 Td[(methods)-400(by)-400(generating)-400(a)-400(nati)25(v)15(e)-400(call)-400(instruction)-400(to)-400(an)-400(interpreter)]TJ 0 -9.9626 Td[(method)-331(for)-331(each)-332(interpreter)-331(bytecode.)-331(A)-331(call-return)-331(pair)-331(has)-332(been)]TJ 0 -9.9627 Td[(sho)25(wn)-247(to)-246(be)-247(a)-247(potentially)-246(much)-247(more)-247(e)1(f)25(\002cient)-247(dispatch)-247(mechanism)]TJ 0 -9.9626 Td[(than)-250(the)-250(indirect)-250(jumps)-250(used)-250(in)-250(standard)-250(bytecode)-250(interpreters.)]TJ 11.9552 -9.9626 Td[(Inline)-360(threading)-360(\05015\051)-360(copies)-360(chunks)-360(of)-360(interpre)1(ter)-360(nati)25(v)15(e)-360(code)]TJ -11.9552 -9.9627 Td[(which)-286(implement)-286(the)-286(required)-286(bytecodes)-286(into)-286(a)-286(nati)25(v)15(e)-286(code)-286(cache,)]TJ 0 -9.9626 Td[(thus)-230(acting)-230(as)-230(a)-230(simple)-230(per)20(-method)-230(JIT)-231(compi)1(ler)-231(that)-230(eliminates)-230(the)]TJ 0 -9.9627 Td[(dispatch)-250(o)15(v)15(erhead.)]TJ 11.9552 -9.9626 Td[(Neither)-209(call)-209(threading)-209(nor)-209(inline)-209(threading)-209(perform)-209(type)-209(special-)]TJ -11.9552 -9.9626 Td[(ization.)]TJ 11.9552 -9.9627 Td[(Apple')55(s)-348(SquirrelFish)-348(Extreme)-348(\0505\051)-348(is)-348(a)-348(Ja)20(v)25(aScript)-348(implementa-)]TJ -11.9552 -9.9626 Td[(tion)-310(based)-311(on)-310(call)-310(threading)-311(with)-310(selecti)25(v)15(e)-310(inline)-310(threading.)-311(Com-)]TJ 0 -9.9627 Td[(bined)-350(with)-349(ef)25(\002cient)-350(interpreter)-350(engineering,)-349(these)-350(threading)-350(tech-)]TJ 0 -9.9626 Td[(niques)-227(ha)20(v)15(e)-226(gi)25(v)15(en)-227(SFX)-227(e)15(xcellent)-226(performance)-227(on)-226(the)-227(standard)-227(Sun-)]TJ 0 -9.9626 Td[(Spider)-250(benchmarks.)]TJ 11.9552 -9.9627 Td[(Google')55(s)-427(V8)-428(is)-427(a)-427(Ja)20(v)25(aScript)-428(implementation)-427(primarily)-427(based)]TJ -11.9552 -9.9626 Td[(on)-470(inline)-469(threading,)-470(with)-470(call)-470(threading)-469(only)-470(for)-470(v)15(ery)-470(comple)15(x)]TJ 0 -9.9627 Td[(operations.)]TJ/F41 10.9589 Tf 0 -21.2536 Td[(9.)-1000(Conclusions)]TJ/F42 8.9664 Tf 0 -13.9477 Td[(This)-284(paper)-284(described)-284(ho)25(w)-283(to)-284(run)-284(dynamic)-284(languages)-284(ef)25(\002ciently)-284(by)]TJ 0 -9.9626 Td[(recording)-360(hot)-360(traces)-360(and)-360(generating)-360(type-specialized)-360(nati)25(v)15(e)-360(code.)]TJ 0 -9.9627 Td[(Our)-292(technique)-292(focuses)-292(on)-292(aggressi)25(v)15(ely)-292(inlined)-292(loops,)-292(and)-293(for)-292(each)]TJ 0 -9.9626 Td[(loop,)-474(it)-474(generates)-474(a)-475(tree)-474(of)-474(nati)25(v)15(e)-474(code)-474(traces)-475(represe)1(nting)-475(the)]TJ 0 -9.9627 Td[(paths)-342(and)-342(v)25(alue)-342(types)-342(through)-342(the)-342(loop)-342(observ)15(ed)-342(at)-343(run)-342(time.)-342(W)80(e)]TJ 0 -9.9626 Td[(e)15(xplained)-325(ho)25(w)-325(to)-325(identify)-324(loop)-325(nesting)-325(relationships)-325(and)-325(generate)]TJ 0 -9.9626 Td[(nested)-480(traces)-481(in)-480(order)-480(to)-480(a)20(v)20(oid)-481(e)15(xcessi)25(v)15(e)-480(code)-480(duplication)-481(due)]TJ 0 -9.9627 Td[(to)-451(the)-451(man)15(y)-451(paths)-451(through)-450(a)-451(loop)-451(nest.)-451(W)80(e)-451(described)-451(our)-451(type)]TJ 0 -9.9626 Td[(specialization)-462(algorithm.)-463(W)80(e)-462(also)-463(des)1(cribed)-463(our)-462(trace)-463(compiler)40(,)]TJ 0 -9.9627 Td[(which)-466(translates)-466(a)-466(trace)-466(from)-466(an)-467(intermediate)-466(representation)-466(to)]TJ 0 -9.9626 Td[(optimized)-250(nati)25(v)15(e)-250(code)-250(in)-250(tw)10(o)-250(linear)-250(passes.)]TJ 11.9552 -9.9626 Td[(Our)-346(e)15(xperimental)-345(results)-346(sho)25(w)-346(that)-345(in)-346(practice)-346(loops)-345(typically)]TJ -11.9552 -9.9627 Td[(are)-314(entered)-313(with)-314(only)-314(a)-313(fe)25(w)-314(dif)25(ferent)-314(combinations)-313(of)-314(v)25(alue)-314(types)]TJ 0 -9.9626 Td[(of)-318(v)25(ariables.)-318(Thus,)-318(a)-318(small)-318(number)-318(of)-318(traces)-318(per)-319(loop)-318(is)-318(suf)25(\002cient)]TJ 0 -9.9627 Td[(to)-388(run)-389(a)-388(program)-389(ef)25(\002)1(ciently)65(.)-389(Our)-388(e)15(xperiments)-389(also)-388(sho)25(w)-388(that)-389(on)]TJ 0 -9.9626 Td[(programs)-250(amenable)-250(to)-250(tracing,)-250(we)-250(achie)25(v)15(e)-250(speedups)-250(of)-250(2x)-250(to)-250(20x.)]TJ/F41 10.9589 Tf 0 -21.2536 Td[(10.)-1000(Futur)18(e)-250(W)75(ork)]TJ/F42 8.9664 Tf 0 -13.9477 Td[(W)80(ork)-426(is)-425(underw)10(ay)-426(in)-425(a)-426(number)-426(of)-425(areas)-426(to)-425(further)-426(impro)15(v)15(e)-426(the)]TJ 0 -9.9627 Td[(performance)-301(of)-301(our)-300(trace-based)-301(Ja)20(v)25(aScript)-301(compiler)55(.)-301(W)80(e)-301(currently)]TJ 0 -9.9626 Td[(do)-407(not)-408(trace)-407(across)-408(recursi)25(v)15(e)-407(function)-408(call)1(s,)-408(b)20(ut)-407(plan)-408(to)-407(add)-408(the)]TJ 0 -9.9626 Td[(support)-305(for)-304(this)-305(capabilit)1(y)-305(in)-305(the)-304(near)-305(term.)-304(W)80(e)-305(are)-304(also)-305(e)15(xploring)]TJ 0 -9.9627 Td[(adoption)-293(of)-293(the)-294(e)15(xist)1(ing)-294(w)10(ork)-293(on)-293(tree)-293(recompilation)-293(in)-294(the)-293(conte)15(xt)]TJ 0 -9.9626 Td[(of)-273(the)-272(presented)-273(dynamic)-273(compiler)-272(in)-273(order)-273(to)-272(minimize)-273(JIT)-273(pause)]TJ 0 -9.9627 Td[(times)-268(and)-268(obtain)-268(the)-268(best)-268(of)-268(both)-268(w)10(orlds,)-268(f)10(ast)-269(tree)-268(stitching)-268(as)-268(well)]TJ 0 -9.9626 Td[(as)-250(the)-250(impro)15(v)15(ed)-250(code)-250(quality)-250(due)-250(to)-250(tree)-250(recompilation.)]TJ 11.9552 -9.9626 Td[(W)80(e)-345(also)-345(plan)-345(on)-345(adding)-345(support)-345(for)-345(tracing)-344(across)-345(re)15(gular)-345(e)15(x-)]TJ -11.9552 -9.9627 Td[(pression)-440(substitutions)-440(using)-440(lambda)-440(functions,)-440(function)-440(applica-)]TJ 0 -9.9626 Td[(tions)-430(and)-430(e)15(xpression)-430(e)25(v)25(aluation)-430(using)]TJ/F33 8.9664 Tf 144.2134 0 Td[(eval)]TJ/F42 8.9664 Tf 18.8292 0 Td[(.)-430(All)-430(these)-430(language)]TJ -163.0426 -9.9627 Td[(constructs)-382(are)-382(currently)-382(e)15(x)15(ecuted)-382(via)-382(interpretation,)-382(which)-382(limits)]TJ 0 -9.9626 Td[(our)-250(performance)-250(for)-250(applications)-250(that)-250(use)-250(those)-250(features.)]TJ/F41 10.9589 Tf 0 -21.2536 Td[(Ackno)10(wledgments)]TJ/F42 8.9664 Tf 0 -13.9477 Td[(P)15(arts)-364(of)-363(this)-364(ef)25(fort)-363(ha)20(v)15(e)-364(been)-363(sponsored)-364(by)-364(the)-363(National)-364(Science)]TJ 0 -9.9626 Td[(F)15(oundation)-229(under)-228(grants)-229(CNS-0615443)-228(and)-229(CNS-0627747,)-228(as)-229(well)]TJ 0 -9.9627 Td[(as)-332(by)-332(the)-331(California)-332(MICR)40(O)-332(Program)-331(and)-332(industrial)-332(sponsor)-332(Sun)]TJ 0 -9.9626 Td[(Microsystems)-250(under)-250(Project)-250(No.)-250(07-127.)]TJ 11.9552 -9.9627 Td[(The)-271(U.S.)-270(Go)15(v)15(ernment)-271(is)-271(authorized)-270(to)-271(reproduce)-271(and)-270(distrib)20(ute)]TJ -11.9552 -9.9626 Td[(reprints)-250(for)-251(Go)15(v)15(ernmental)-250(purposes)-251(notwithstanding)-250(an)15(y)-251(cop)10(yright)]TJ 0 -9.9626 Td[(annotation)-221(thereon.)-221(An)15(y)-221(opinions,)-221(\002ndings,)-221(and)-221(conclusions)-221(or)-221(rec-)]TJ 0 -9.9627 Td[(ommendations)-342(e)15(xpressed)-341(here)-342(are)-342(those)-342(of)-341(the)-342(author)-342(and)-342(should)]TJ
ET