pdf2htmlEX/demo/demo9.page

<div class="pd w0 h0"><div id="pf9" class="pf" data-page-no="9"><div class="pc pc9"><div class="t m0 x34 h5 y5b ff2 fs3 fc0 sc0 ls0 ws0">When<span class="_ _6"> </span>a<span class="_ _6"> </span>trace<span class="_ _6"> </span>call<span class="_ _6"> </span>returns,<span class="_ _6"> </span>the<span class="_ _6"> </span>monitor<span class="_ _6"> </span>restores<span class="_ _6"> </span>the<span class="_ _6"> </span>interpreter</div><div class="t m0 x2f h5 y5c ff2 fs3 fc0 sc0 ls0 ws0">state.<span class="_ _8"> </span>First,<span class="_ _8"> </span>the<span class="_ _8"> </span>monitor<span class="_ _8"> </span>checks<span class="_ _8"> </span>the<span class="_ _8"> </span>reason<span class="_ _8"> </span>for<span class="_ _8"> </span>the<span class="_ _d"> </span>trace<span class="_ _6"> </span>exit<span class="_ _8"> </span>and</div><div class="t m0 x2f h5 y5d ff2 fs3 fc0 sc0 ls0 ws0">applies<span class="_ _6"> </span>blacklisting<span class="_ _6"> </span>if<span class="_ _6"> </span>needed.<span class="_ _6"> </span>Then,<span class="_ _6"> </span>it<span class="_ _6"> </span>pops<span class="_ _6"> </span>or<span class="_ _6"> </span>synthesizes<span class="_ _6"> </span>inter-</div><div class="t m0 x2f h5 y5e ff2 fs3 fc0 sc0 ls0 ws0">preter<span class="_ _3"> </span>Ja<span class="_ _2"></span>v<span class="_ _2"></span>aScript<span class="_ _5"> </span>call<span class="_ _3"> </span>stack<span class="_ _5"> </span>frames<span class="_ _3"> </span>as<span class="_ _5"> </span>needed.<span class="_ _3"> </span>Finally<span class="_ _b"></span>,<span class="_ _3"> </span>it<span class="_ _5"> </span>copies<span class="_ _3"> </span>the</div><div class="t m0 x2f h5 y5f ff2 fs3 fc0 sc0 ls0 ws0">imported<span class="_ _3"> </span>v<span class="_ _2"></span>ariables<span class="_ _3"> </span>back<span class="_ _3"> </span>from<span class="_ _5"> </span>the<span class="_ _3"> </span>trace<span class="_ _3"> </span>acti<span class="_ _2"></span>v<span class="_ _2"></span>ation<span class="_ _3"> </span>record<span class="_ _3"> </span>to<span class="_ _5"> </span>the<span class="_ _3"> </span>in-</div><div class="t m0 x2f h5 y60 ff2 fs3 fc0 sc0 ls0 ws0">terpreter<span class="_ _5"> </span>state.</div><div class="t m0 x34 h5 y61 ff2 fs3 fc0 sc0 ls0 ws0">At<span class="_ _3"> </span>least<span class="_ _3"> </span>in<span class="_ _3"> </span>the<span class="_ _5"> </span>current<span class="_ _3"> </span>implementation,<span class="_ _3"> </span>these<span class="_ _3"> </span>steps<span class="_ _3"> </span>ha<span class="_ _2"></span>ve<span class="_ _3"> </span>a<span class="_ _5"> </span>non-</div><div class="t m0 x2f h5 y62 ff2 fs3 fc0 sc0 ls0 ws0">negligible<span class="_ _3"> </span>runtime<span class="_ _6"> </span>cost,<span class="_ _3"> </span>so<span class="_ _3"> </span>minimizing<span class="_ _6"> </span>the<span class="_ _3"> </span>number<span class="_ _6"> </span>of<span class="_ _3"> </span>interpreter-</div><div class="t m0 x2f h5 y63 ff2 fs3 fc0 sc0 ls0 ws0">to-trace<span class="_ _6"> </span>and<span class="_ _6"> </span>trace-to-interpreter<span class="_ _3"> </span>transitions<span class="_ _6"> </span>is<span class="_ _6"> </span>essential<span class="_ _6"> </span>for<span class="_ _6"> </span>perfor<span class="_ _2"></span>-</div><div class="t m0 x2f h5 y7 ff2 fs3 fc0 sc0 ls0 ws0">mance.<span class="_ _d"> </span>(see<span class="_ _8"> </span>also<span class="_ _d"> </span>Section<span class="_ _d"> </span>3.3).<span class="_ _8"> </span>Our<span class="_ _d"> </span>experiments<span class="_ _8"> </span>(see<span class="_ _d"> </span>Figure<span class="_ _8"> </span>12)</div><div class="t m0 x2f h5 y64 ff2 fs3 fc0 sc0 ls0 ws0">show<span class="_ _8"> </span>that<span class="_ _d"> </span>for<span class="_ _8"> </span>programs<span class="_ _d"> </span>we<span class="_ _8"> </span>can<span class="_ _d"> </span>trace<span class="_ _8"> </span>well<span class="_ _d"> </span>such<span class="_ _8"> </span>transitions<span class="_ _d"> </span>hap-</div><div class="t m0 x2f h5 y66 ff2 fs3 fc0 sc0 ls0 ws0">pen<span class="_ _3"> </span>infrequently<span class="_ _3"> </span>and<span class="_ _3"> </span>hence<span class="_ _3"> </span>do<span class="_ _3"> </span>not<span class="_ _3"> </span>contribute<span class="_ _3"> </span>significantly<span class="_ _3"> </span>to<span class="_ _3"> </span>total</div><div class="t m0 x2f h5 y67 ff2 fs3 fc0 sc0 ls0 ws0">runtime.<span class="_ _6"> </span>In<span class="_ _6"> </span>a<span class="_ _6"> </span>few<span class="_ _6"> </span>programs,<span class="_ _6"> </span>where<span class="_ _6"> </span>the<span class="_ _6"> </span>system<span class="_ _6"> </span>is<span class="_ _6"> </span>prev<span class="_ _2"></span>ented<span class="_ _6"> </span>from</div><div class="t m0 x2f h5 y68 ff2 fs3 fc0 sc0 ls0 ws0">recording<span class="_ _6"> </span>branch<span class="_ _3"> </span>traces<span class="_ _6"> </span>for<span class="_ _6"> </span>hot<span class="_ _3"> </span>side<span class="_ _6"> </span>exits<span class="_ _3"> </span>by<span class="_ _6"> </span>aborts,<span class="_ _6"> </span>this<span class="_ _3"> </span>cost<span class="_ _6"> </span>can</div><div class="t m0 x2f h5 y69 ff2 fs3 fc0 sc0 ls0 ws0">rise<span class="_ _5"> </span>to<span class="_ _5"> </span>up<span class="_ _3"> </span>to<span class="_ _5"> </span>10%<span class="_ _5"> </span>of<span class="_ _5"> </span>total<span class="_ _5"> </span>execution<span class="_ _5"> </span>time.</div><div class="t m0 x2f hc y233 ff1 fs3 fc0 sc0 ls0 ws0">6.2<span class="_ _9"> </span>T<span class="_ _b"></span>race<span class="_ _5"> </span>Stitching</div><div class="t m0 x2f h5 y198 ff2 fs3 fc0 sc0 ls0 ws0">T<span class="_ _2"></span>ransitions<span class="_ _3"> </span>from<span class="_ _6"> </span>a<span class="_ _3"> </span>trace<span class="_ _6"> </span>to<span class="_ _6"> </span>a<span class="_ _3"> </span>branch<span class="_ _6"> </span>trace<span class="_ _3"> </span>at<span class="_ _6"> </span>a<span class="_ _3"> </span>side<span class="_ _6"> </span>exit<span class="_ _3"> </span>av<span class="_ _2"></span>oid<span class="_ _6"> </span>the</div><div class="t m0 x2f h5 y199 ff2 fs3 fc0 sc0 ls0 ws0">costs<span class="_ _6"> </span>of<span class="_ _6"> </span>calling<span class="_ _3"> </span>traces<span class="_ _6"> </span>from<span class="_ _6"> </span>the<span class="_ _6"> </span>monitor<span class="_ _2"></span>,<span class="_ _6"> </span>in<span class="_ _6"> </span>a<span class="_ _3"> </span>feature<span class="_ _6"> </span>called<span class="_ _6"> </span><span class="ffa">trace</span></div><div class="t m0 x2f h5 y19a ffa fs3 fc0 sc0 ls0 ws0">stitching<span class="ff2">.<span class="_ _3"> </span>At<span class="_ _3"> </span>a<span class="_ _6"> </span>side<span class="_ _3"> </span>exit,<span class="_ _6"> </span>the<span class="_ _3"> </span>exiting<span class="_ _3"> </span>trace<span class="_ _6"> </span>only<span class="_ _3"> </span>needs<span class="_ _3"> </span>to<span class="_ _6"> </span>write<span class="_ _3"> </span>live</span></div><div class="t m0 x2f h5 y234 ff2 fs3 fc0 sc0 ls0 ws0">register<span class="_ _2"></span>-carried<span class="_ _5"> </span>v<span class="_ _2"></span>alues<span class="_ _5"> </span>back<span class="_ _5"> </span>to<span class="_ _7"> </span>its<span class="_ _5"> </span>trace<span class="_ _5"> </span>acti<span class="_ _2"></span>v<span class="_ _2"></span>ation<span class="_ _5"> </span>record.<span class="_ _5"> </span>In<span class="_ _7"> </span>our<span class="_ _5"> </span>im-</div><div class="t m0 x2f h5 y235 ff2 fs3 fc0 sc0 ls0 ws0">plementation,<span class="_ _3"> </span>identical<span class="_ _3"> </span>type<span class="_ _5"> </span>maps<span class="_ _3"> </span>yield<span class="_ _3"> </span>identical<span class="_ _3"> </span>acti<span class="_ _2"></span>v<span class="_ _2"></span>ation<span class="_ _3"> </span>record</div><div class="t m0 x2f h5 y236 ff2 fs3 fc0 sc0 ls0 ws0">layouts,<span class="_ _6"> </span>so<span class="_ _3"> </span>the<span class="_ _6"> </span>trace<span class="_ _6"> </span>activ<span class="_ _2"></span>ation<span class="_ _3"> </span>record<span class="_ _6"> </span>can<span class="_ _6"> </span>be<span class="_ _6"> </span>reused<span class="_ _3"> </span>immediately</div><div class="t m0 x2f h5 y237 ff2 fs3 fc0 sc0 ls0 ws0">by<span class="_ _5"> </span>the<span class="_ _5"> </span>branch<span class="_ _3"> </span>trace.</div><div class="t m0 x34 h5 y238 ff2 fs3 fc0 sc0 ls0 ws0">In<span class="_ _6"> </span>programs<span class="_ _8"> </span>with<span class="_ _8"> </span>branchy<span class="_ _8"> </span>trace<span class="_ _8"> </span>trees<span class="_ _6"> </span>with<span class="_ _8"> </span>small<span class="_ _8"> </span>traces,<span class="_ _8"> </span>trace</div><div class="t m0 x2f h5 y1f2 ff2 fs3 fc0 sc0 ls0 ws0">stitching<span class="_ _6"> </span>has<span class="_ _6"> </span>a<span class="_ _6"> </span>noticeable<span class="_ _8"> </span>cost.<span class="_ _6"> </span>Although<span class="_ _6"> </span>writing<span class="_ _6"> </span>to<span class="_ _8"> </span>memory<span class="_ _6"> </span>and</div><div class="t m0 x2f h5 y21c ff2 fs3 fc0 sc0 ls0 ws0">then<span class="_ _1"> </span>soon<span class="_ _d"> </span>reading<span class="_ _1"> </span>back<span class="_ _1"> </span>w<span class="_ _2"></span>ould<span class="_ _d"> </span>be<span class="_ _1"> </span>expected<span class="_ _d"> </span>to<span class="_ _1"> </span>hav<span class="_ _2"></span>e<span class="_ _1"> </span>a<span class="_ _d"> </span>high<span class="_ _1"> </span>L1</div><div class="t m0 x2f h5 y21d ff2 fs3 fc0 sc0 ls0 ws0">cache<span class="_ _3"> </span>hit<span class="_ _3"> </span>rate,<span class="_ _3"> </span>for<span class="_ _3"> </span>small<span class="_ _3"> </span>traces<span class="_ _3"> </span>the<span class="_ _3"> </span>increased<span class="_ _3"> </span>instruction<span class="_ _6"> </span>count<span class="_ _3"> </span>has</div><div class="t m0 x2f h5 y21e ff2 fs3 fc0 sc0 ls0 ws0">a<span class="_ _1"> </span>noticeable<span class="_ _d"> </span>cost.<span class="_ _1"> </span>Also,<span class="_ _1"> </span>if<span class="_ _d"> </span>the<span class="_ _1"> </span>writes<span class="_ _d"> </span>and<span class="_ _1"> </span>reads<span class="_ _1"> </span>are<span class="_ _d"> </span>very<span class="_ _1"> </span>close</div><div class="t m0 x2f h5 y21f ff2 fs3 fc0 sc0 ls0 ws0">in<span class="_ _1"> </span>the<span class="_ _1"> </span>dynam<span class="_ _2"></span>ic<span class="_ _1"> </span>instruction<span class="_ _d"> </span>stream,<span class="_ _1"> </span>we<span class="_ _1"> </span>ha<span class="_ _2"></span>ve<span class="_ _1"> </span>found<span class="_ _d"> </span>that<span class="_ _1"> </span>current</div><div class="t m0 x2f h5 y220 ff2 fs3 fc0 sc0 ls0 ws0">x86<span class="_ _6"> </span>processors<span class="_ _6"> </span>often<span class="_ _6"> </span>incur<span class="_ _6"> </span>penalties<span class="_ _6"> </span>of<span class="_ _6"> </span>6<span class="_ _8"> </span>cycles<span class="_ _6"> </span>or<span class="_ _6"> </span>more<span class="_ _6"> </span>(e.g.,<span class="_ _6"> </span>if</div><div class="t m0 x2f h5 y221 ff2 fs3 fc0 sc0 ls0 ws0">the<span class="_ _3"> </span>instructions<span class="_ _6"> </span>use<span class="_ _3"> </span>different<span class="_ _3"> </span>base<span class="_ _3"> </span>registers<span class="_ _6"> </span>with<span class="_ _3"> </span>equal<span class="_ _3"> </span>values,<span class="_ _3"> </span>the</div><div class="t m0 x2f h5 y222 ff2 fs3 fc0 sc0 ls0 ws0">processor<span class="_ _5"> </span>may<span class="_ _5"> </span>not<span class="_ _3"> </span>be<span class="_ _5"> </span>able<span class="_ _5"> </span>to<span class="_ _5"> </span>detect<span class="_ _5"> </span>that<span class="_ _5"> </span>the<span class="_ _3"> </span>addresses<span class="_ _5"> </span>are<span class="_ _5"> </span>the<span class="_ _5"> </span>same</div><div class="t m0 x2f h5 y223 ff2 fs3 fc0 sc0 ls0 ws0">right<span class="_ _5"> </span>away).</div><div class="t m0 x34 h5 y224 ff2 fs3 fc0 sc0 ls0 ws0">The<span class="_ _3"> </span>alternate<span class="_ _3"> </span>solution<span class="_ _3"> </span>is<span class="_ _3"> </span>to<span class="_ _3"> </span>recompile<span class="_ _3"> </span>an<span class="_ _3"> </span>entire<span class="_ _3"> </span>trace<span class="_ _6"> </span>tree,<span class="_ _3"> </span>thus</div><div class="t m0 x2f h5 y225 ff2 fs3 fc0 sc0 ls0 ws0">achieving<span class="_ _3"> </span>inter-trace<span class="_ _6"> </span>register<span class="_ _3"> </span>allocation<span class="_ _6"> </span>(10).<span class="_ _6"> </span>The<span class="_ _6"> </span>disadvantage<span class="_ _6"> </span>is</div><div class="t m0 x2f h5 y226 ff2 fs3 fc0 sc0 ls0 ws0">that<span class="_ _5"> </span>tree<span class="_ _7"> </span>recompilation<span class="_ _5"> </span>tak<span class="_ _2"></span>es<span class="_ _5"> </span>time<span class="_ _7"> </span>quadratic<span class="_ _5"> </span>in<span class="_ _7"> </span>the<span class="_ _5"> </span>number<span class="_ _5"> </span>of<span class="_ _7"> </span>traces.</div><div class="t m0 x2f h5 y227 ff2 fs3 fc0 sc0 ls0 ws0">W<span class="_ _b"></span>e<span class="_ _d"> </span>believ<span class="_ _2"></span>e<span class="_ _d"> </span>that<span class="_ _8"> </span>the<span class="_ _d"> </span>cost<span class="_ _d"> </span>of<span class="_ _d"> </span>recompiling<span class="_ _8"> </span>a<span class="_ _d"> </span>trace<span class="_ _d"> </span>tree<span class="_ _d"> </span>e<span class="_ _2"></span>very<span class="_ _8"> </span>time</div><div class="t m0 x2f h5 y228 ff2 fs3 fc0 sc0 ls0 ws0">a<span class="_ _8"> </span>branch<span class="_ _8"> </span>is<span class="_ _d"> </span>added<span class="_ _6"> </span>would<span class="_ _8"> </span>be<span class="_ _d"> </span>prohibiti<span class="_ _2"></span>ve.<span class="_ _6"> </span>That<span class="_ _8"> </span>problem<span class="_ _d"> </span>might<span class="_ _8"> </span>be</div><div class="t m0 x2f h5 y229 ff2 fs3 fc0 sc0 ls0 ws0">mitigated<span class="_ _6"> </span>by<span class="_ _6"> </span>recompiling<span class="_ _6"> </span>only<span class="_ _6"> </span>at<span class="_ _8"> </span>certain<span class="_ _6"> </span>points,<span class="_ _6"> </span>or<span class="_ _6"> </span>only<span class="_ _6"> </span>for<span class="_ _8"> </span>very</div><div class="t m0 x2f h5 y22a ff2 fs3 fc0 sc0 ls0 ws0">hot,<span class="_ _5"> </span>stable<span class="_ _5"> </span>trees.</div><div class="t m0 x34 h5 y22b ff2 fs3 fc0 sc0 ls0 ws0">In<span class="_ _6"> </span>the<span class="_ _8"> </span>future,<span class="_ _8"> </span>multicore<span class="_ _8"> </span>hardware<span class="_ _6"> </span>is<span class="_ _8"> </span>expected<span class="_ _6"> </span>to<span class="_ _8"> </span>be<span class="_ _8"> </span>common,</div><div class="t m0 x2f h5 y22c ff2 fs3 fc0 sc0 ls0 ws0">making<span class="_ _6"> </span>background<span class="_ _3"> </span>tree<span class="_ _6"> </span>recompilation<span class="_ _6"> </span>attractiv<span class="_ _2"></span>e.<span class="_ _6"> </span>In<span class="_ _3"> </span>a<span class="_ _6"> </span>closely<span class="_ _6"> </span>re-</div><div class="t m0 x2f h5 y22d ff2 fs3 fc0 sc0 ls0 ws0">lated<span class="_ _6"> </span>project<span class="_ _6"> </span>(13)<span class="_ _8"> </span>background<span class="_ _6"> </span>recompilation<span class="_ _6"> </span>yielded<span class="_ _8"> </span>speedups<span class="_ _6"> </span>of</div><div class="t m0 x2f h5 y22e ff2 fs3 fc0 sc0 ls0 ws0">up<span class="_ _6"> </span>to<span class="_ _3"> </span>1.25x<span class="_ _6"> </span>on<span class="_ _6"> </span>benchmarks<span class="_ _3"> </span>with<span class="_ _6"> </span>many<span class="_ _3"> </span>branch<span class="_ _6"> </span>traces.<span class="_ _6"> </span>W<span class="_ _b"></span>e<span class="_ _6"> </span>plan<span class="_ _3"> </span>to</div><div class="t m0 x2f h5 y22f ff2 fs3 fc0 sc0 ls0 ws0">apply<span class="_ _5"> </span>this<span class="_ _5"> </span>technique<span class="_ _3"> </span>to<span class="_ _5"> </span>T<span class="_ _2"></span>raceMonk<span class="_ _2"></span>ey<span class="_ _5"> </span>as<span class="_ _5"> </span>future<span class="_ _5"> </span>work.</div><div class="t m0 x2f hc y239 ff1 fs3 fc0 sc0 ls0 ws0">6.3<span class="_ _9"> </span>T<span class="_ _b"></span>race<span class="_ _5"> </span>Recording</div><div class="t m0 x2f h5 ycd ff2 fs3 fc0 sc0 ls0 ws0">The<span class="_ _5"> </span>job<span class="_ _7"> </span>of<span class="_ _5"> </span>the<span class="_ _7"> </span>trace<span class="_ _5"> </span>recorder<span class="_ _5"> </span>is<span class="_ _7"> </span>to<span class="_ _5"> </span>emit<span class="_ _7"> </span>LIR<span class="_ _5"> </span>with<span class="_ _7"> </span>identical<span class="_ _5"> </span>semantics</div><div class="t m0 x2f h5 yce ff2 fs3 fc0 sc0 ls0 ws0">to<span class="_ _3"> </span>the<span class="_ _3"> </span>currently<span class="_ _3"> </span>running<span class="_ _5"> </span>interpreter<span class="_ _3"> </span>bytecode<span class="_ _3"> </span>trace.<span class="_ _3"> </span>A<span class="_ _3"> </span>good<span class="_ _5"> </span>imple-</div><div class="t m0 x2f h5 ycf ff2 fs3 fc0 sc0 ls0 ws0">mentation<span class="_ _3"> </span>should<span class="_ _6"> </span>ha<span class="_ _2"></span>ve<span class="_ _3"> </span>low<span class="_ _3"> </span>impact<span class="_ _3"> </span>on<span class="_ _3"> </span>non-tracing<span class="_ _6"> </span>interpreter<span class="_ _3"> </span>per-</div><div class="t m0 x2f h5 y12e ff2 fs3 fc0 sc0 ls0 ws0">formance<span class="_ _3"> </span>and<span class="_ _6"> </span>a<span class="_ _3"> </span>conv<span class="_ _2"></span>enient<span class="_ _3"> </span>way<span class="_ _6"> </span>for<span class="_ _3"> </span>implementers<span class="_ _6"> </span>to<span class="_ _3"> </span>maintain<span class="_ _6"> </span>se-</div><div class="t m0 x2f h5 yd1 ff2 fs3 fc0 sc0 ls0 ws0">mantic<span class="_ _5"> </span>equiv<span class="_ _2"></span>alence.</div><div class="t m0 x34 h5 yd2 ff2 fs3 fc0 sc0 ls0 ws0">In<span class="_ _5"> </span>our<span class="_ _5"> </span>implementation,<span class="_ _5"> </span>the<span class="_ _5"> </span>only<span class="_ _5"> </span>direct<span class="_ _5"> </span>modification<span class="_ _5"> </span>to<span class="_ _5"> </span>the<span class="_ _5"> </span>inter-</div><div class="t m0 x2f h5 yd3 ff2 fs3 fc0 sc0 ls0 ws0">preter<span class="_ _5"> </span>is<span class="_ _5"> </span>a<span class="_ _5"> </span>call<span class="_ _5"> </span>to<span class="_ _5"> </span>the<span class="_ _5"> </span>trace<span class="_ _7"> </span>monitor<span class="_ _5"> </span>at<span class="_ _5"> </span>loop<span class="_ _5"> </span>edges.<span class="_ _5"> </span>In<span class="_ _5"> </span>our<span class="_ _5"> </span>benchmark</div><div class="t m0 x2f h5 y94 ff2 fs3 fc0 sc0 ls0 ws0">results<span class="_ _3"> </span>(see<span class="_ _6"> </span>Figure<span class="_ _3"> </span>12)<span class="_ _6"> </span>the<span class="_ _3"> </span>total<span class="_ _6"> </span>time<span class="_ _3"> </span>spent<span class="_ _6"> </span>in<span class="_ _3"> </span>the<span class="_ _6"> </span>monitor<span class="_ _3"> </span>(for<span class="_ _6"> </span>all</div><div class="t m0 x2f h5 y95 ff2 fs3 fc0 sc0 ls0 ws0">activities)<span class="_ _3"> </span>is<span class="_ _6"> </span>usually<span class="_ _8"> </span>less<span class="_ _6"> </span>than<span class="_ _6"> </span>5%,<span class="_ _6"> </span>so<span class="_ _6"> </span>we<span class="_ _6"> </span>consider<span class="_ _6"> </span>the<span class="_ _6"> </span>interpreter</div><div class="t m0 x2f h5 y96 ff2 fs3 fc0 sc0 ls0 ws0">impact<span class="_ _6"> </span>requirement<span class="_ _3"> </span>met.<span class="_ _6"> </span>Incrementing<span class="_ _6"> </span>the<span class="_ _3"> </span>loop<span class="_ _6"> </span>hit<span class="_ _6"> </span>counter<span class="_ _3"> </span>is<span class="_ _6"> </span>ex-</div><div class="t m0 x2f h5 y97 ff2 fs3 fc0 sc0 ls0 ws0">pensiv<span class="_ _2"></span>e<span class="_ _5"> </span>because<span class="_ _7"> </span>it<span class="_ _5"> </span>requires<span class="_ _5"> </span>us<span class="_ _7"> </span>to<span class="_ _5"> </span>look<span class="_ _5"> </span>up<span class="_ _7"> </span>the<span class="_ _5"> </span>loop<span class="_ _5"> </span>in<span class="_ _7"> </span>the<span class="_ _5"> </span>trace<span class="_ _7"> </span>cache,</div><div class="t m0 x2f h5 y98 ff2 fs3 fc0 sc0 ls0 ws0">but<span class="_ _5"> </span>we<span class="_ _3"> </span>hav<span class="_ _2"></span>e<span class="_ _5"> </span>tuned<span class="_ _3"> </span>our<span class="_ _3"> </span>loops<span class="_ _5"> </span>to<span class="_ _3"> </span>become<span class="_ _5"> </span>hot<span class="_ _3"> </span>and<span class="_ _3"> </span>trace<span class="_ _5"> </span>very<span class="_ _3"> </span>quickly</div><div class="t m0 x2f h5 y99 ff2 fs3 fc0 sc0 ls0 ws0">(on<span class="_ _5"> </span>the<span class="_ _3"> </span>second<span class="_ _5"> </span>iteration).<span class="_ _5"> </span>The<span class="_ _3"> </span>hit<span class="_ _5"> </span>counter<span class="_ _3"> </span>implementation<span class="_ _5"> </span>could<span class="_ _5"> </span>be</div><div class="t m0 x2f h5 y9a ff2 fs3 fc0 sc0 ls0 ws0">improv<span class="_ _2"></span>ed,<span class="_ _3"> </span>which<span class="_ _3"> </span>might<span class="_ _3"> </span>give<span class="_ _3"> </span>us<span class="_ _3"> </span>a<span class="_ _3"> </span>small<span class="_ _3"> </span>increase<span class="_ _3"> </span>in<span class="_ _3"> </span>ov<span class="_ _2"></span>erall<span class="_ _3"> </span>perfor-</div><div class="t m0 x2f h5 y9b ff2 fs3 fc0 sc0 ls0 ws0">mance,<span class="_ _3"> </span>as<span class="_ _3"> </span>well<span class="_ _3"> </span>as<span class="_ _3"> </span>more<span class="_ _3"> </span>flexibility<span class="_ _3"> </span>with<span class="_ _3"> </span>tuning<span class="_ _3"> </span>hotness<span class="_ _6"> </span>thresholds.</div><div class="t m0 x2f h5 y9c ff2 fs3 fc0 sc0 ls0 ws0">Once<span class="_ _3"> </span>a<span class="_ _3"> </span>loop<span class="_ _5"> </span>is<span class="_ _3"> </span>blacklisted<span class="_ _3"> </span>we<span class="_ _3"> </span>ne<span class="_ _2"></span>v<span class="_ _2"></span>er<span class="_ _3"> </span>call<span class="_ _3"> </span>into<span class="_ _5"> </span>the<span class="_ _3"> </span>trace<span class="_ _3"> </span>monitor<span class="_ _3"> </span>for</div><div class="t m0 x2f h5 y9d ff2 fs3 fc0 sc0 ls0 ws0">that<span class="_ _5"> </span>loop<span class="_ _5"> </span>(see<span class="_ _3"> </span>Section<span class="_ _5"> </span>3.3).</div><div class="t m0 x33 h5 y5b ff2 fs3 fc0 sc0 ls0 ws0">Recording<span class="_ _d"> </span>is<span class="_ _8"> </span>activated<span class="_ _8"> </span>by<span class="_ _d"> </span>a<span class="_ _d"> </span>pointer<span class="_ _d"> </span>sw<span class="_ _2"></span>ap<span class="_ _d"> </span>that<span class="_ _8"> </span>sets<span class="_ _d"> </span>the<span class="_ _d"> </span>inter-</div><div class="t m0 x32 h5 y5c ff2 fs3 fc0 sc0 ls0 ws0">preter’<span class="_ _2"></span>s<span class="_ _6"> </span>dispatch<span class="_ _6"> </span>table<span class="_ _8"> </span>to<span class="_ _8"> </span>call<span class="_ _6"> </span>a<span class="_ _8"> </span>single<span class="_ _6"> </span>“interrupt”<span class="_ _8"> </span>routine<span class="_ _8"> </span>for<span class="_ _6"> </span>ev-</div><div class="t m0 x32 h5 y5d ff2 fs3 fc0 sc0 ls0 ws0">ery<span class="_ _6"> </span>bytecode.<span class="_ _6"> </span>The<span class="_ _6"> </span>interrupt<span class="_ _6"> </span>routine<span class="_ _6"> </span>first<span class="_ _8"> </span>calls<span class="_ _6"> </span>a<span class="_ _6"> </span>bytecode-specific</div><div class="t m0 x32 h5 y5e ff2 fs3 fc0 sc0 ls0 ws0">recording<span class="_ _6"> </span>routine.<span class="_ _8"> </span>Then,<span class="_ _8"> </span>it<span class="_ _6"> </span>turns<span class="_ _8"> </span>off<span class="_ _6"> </span>recording<span class="_ _8"> </span>if<span class="_ _6"> </span>necessary<span class="_ _8"> </span>(e.g.,</div><div class="t m0 x32 h5 y5f ff2 fs3 fc0 sc0 ls0 ws0">the<span class="_ _3"> </span>trace<span class="_ _3"> </span>ended).<span class="_ _5"> </span>Finally<span class="_ _2"></span>,<span class="_ _3"> </span>it<span class="_ _5"> </span>jumps<span class="_ _3"> </span>to<span class="_ _3"> </span>the<span class="_ _3"> </span>standard<span class="_ _5"> </span>interpreter<span class="_ _3"> </span>byte-</div><div class="t m0 x32 h5 y60 ff2 fs3 fc0 sc0 ls0 ws0">code<span class="_ _5"> </span>implementation.<span class="_ _7"> </span>Some<span class="_ _5"> </span>bytecodes<span class="_ _7"> </span>ha<span class="_ _2"></span>ve<span class="_ _7"> </span>effects<span class="_ _5"> </span>on<span class="_ _7"> </span>the<span class="_ _7"> </span>type<span class="_ _5"> </span>map</div><div class="t m0 x32 h5 y61 ff2 fs3 fc0 sc0 ls0 ws0">that<span class="_ _3"> </span>cannot<span class="_ _3"> </span>be<span class="_ _3"> </span>predicted<span class="_ _3"> </span>before<span class="_ _3"> </span>executing<span class="_ _3"> </span>the<span class="_ _3"> </span>bytecode<span class="_ _3"> </span>(e.g.,<span class="_ _3"> </span>call-</div><div class="t m0 x32 h5 y62 ff2 fs3 fc0 sc0 ls0 ws0">ing<span class="_ _3"> </span><span class="ff7">String.charCodeAt</span>,<span class="_ _3"> </span>which<span class="_ _3"> </span>returns<span class="_ _3"> </span>an<span class="_ _3"> </span>inte<span class="_ _2"></span>ger<span class="_ _3"> </span>or<span class="_ _3"> </span><span class="ffa">NaN<span class="_ _6"> </span></span>if<span class="_ _3"> </span>the</div><div class="t m0 x32 h5 y63 ff2 fs3 fc0 sc0 ls0 ws0">index<span class="_ _5"> </span>ar<span class="_ _2"></span>gument<span class="_ _5"> </span>is<span class="_ _5"> </span>out<span class="_ _7"> </span>of<span class="_ _5"> </span>range).<span class="_ _5"> </span>For<span class="_ _5"> </span>these,<span class="_ _5"> </span>we<span class="_ _7"> </span>arrange<span class="_ _5"> </span>for<span class="_ _5"> </span>the<span class="_ _5"> </span>inter<span class="_ _2"></span>-</div><div class="t m0 x32 h5 y7 ff2 fs3 fc0 sc0 ls0 ws0">preter<span class="_ _3"> </span>to<span class="_ _3"> </span>call<span class="_ _3"> </span>into<span class="_ _3"> </span>the<span class="_ _3"> </span>recorder<span class="_ _3"> </span>again<span class="_ _3"> </span>after<span class="_ _3"> </span>executing<span class="_ _3"> </span>the<span class="_ _3"> </span>bytecode.</div><div class="t m0 x32 h5 y64 ff2 fs3 fc0 sc0 ls0 ws0">Since<span class="_ _3"> </span>such<span class="_ _3"> </span>hooks<span class="_ _3"> </span>are<span class="_ _3"> </span>relati<span class="_ _2"></span>vely<span class="_ _3"> </span>rare,<span class="_ _3"> </span>we<span class="_ _3"> </span>embed<span class="_ _5"> </span>them<span class="_ _3"> </span>directly<span class="_ _3"> </span>into</div><div class="t m0 x32 h5 y66 ff2 fs3 fc0 sc0 ls0 ws0">the<span class="_ _3"> </span>interpreter,<span class="_ _3"> </span>with<span class="_ _3"> </span>an<span class="_ _3"> </span>additional<span class="_ _3"> </span>runtime<span class="_ _6"> </span>check<span class="_ _3"> </span>to<span class="_ _3"> </span>see<span class="_ _6"> </span>whether<span class="_ _3"> </span>a</div><div class="t m0 x32 h5 y67 ff2 fs3 fc0 sc0 ls0 ws0">recorder<span class="_ _5"> </span>is<span class="_ _5"> </span>currently<span class="_ _3"> </span>acti<span class="_ _2"></span>v<span class="_ _2"></span>e.</div><div class="t m0 x33 h5 y68 ff2 fs3 fc0 sc0 ls0 ws0">While<span class="_ _5"> </span>separating<span class="_ _5"> </span>the<span class="_ _5"> </span>interpreter<span class="_ _5"> </span>from<span class="_ _5"> </span>the<span class="_ _5"> </span>recorder<span class="_ _3"> </span>reduces<span class="_ _5"> </span>indi-</div><div class="t m0 x32 h5 y69 ff2 fs3 fc0 sc0 ls0 ws0">vidual<span class="_ _5"> </span>code<span class="_ _7"> </span>complexity<span class="_ _2"></span>,<span class="_ _7"> </span>it<span class="_ _5"> </span>also<span class="_ _5"> </span>requires<span class="_ _7"> </span>careful<span class="_ _5"> </span>implementation<span class="_ _5"> </span>and</div><div class="t m0 x32 h5 y6a ff2 fs3 fc0 sc0 ls0 ws0">extensi<span class="_ _2"></span>ve<span class="_ _5"> </span>testing<span class="_ _5"> </span>to<span class="_ _5"> </span>achiev<span class="_ _2"></span>e<span class="_ _5"> </span>semantic<span class="_ _5"> </span>equiv<span class="_ _2"></span>alence.</div><div class="t m0 x33 h5 y6b ff2 fs3 fc0 sc0 ls0 ws0">In<span class="_ _3"> </span>some<span class="_ _3"> </span>cases<span class="_ _3"> </span>achie<span class="_ _2"></span>ving<span class="_ _3"> </span>this<span class="_ _3"> </span>equi<span class="_ _2"></span>v<span class="_ _2"></span>alence<span class="_ _3"> </span>is<span class="_ _3"> </span>dif<span class="_ _2"></span>ficult<span class="_ _3"> </span>since<span class="_ _3"> </span>Spi-</div><div class="t m0 x32 h5 y6c ff2 fs3 fc0 sc0 ls0 ws0">derMonkey<span class="_ _3"> </span>follo<span class="_ _2"></span>ws<span class="_ _3"> </span>a<span class="_ _3"> </span><span class="ffa">fat-bytecode<span class="_ _3"> </span></span>design,<span class="_ _3"> </span>which<span class="_ _3"> </span>was<span class="_ _3"> </span>found<span class="_ _3"> </span>to<span class="_ _6"> </span>be</div><div class="t m0 x32 h5 y6d ff2 fs3 fc0 sc0 ls0 ws0">beneficial<span class="_ _5"> </span>to<span class="_ _5"> </span>pure<span class="_ _3"> </span>interpreter<span class="_ _5"> </span>performance.</div><div class="t m0 x33 h5 y6e ff2 fs3 fc0 sc0 ls0 ws0">In<span class="_ _d"> </span>fat-bytecode<span class="_ _8"> </span>designs,<span class="_ _d"> </span>individual<span class="_ _d"> </span>bytecodes<span class="_ _8"> </span>can<span class="_ _d"> </span>implement</div><div class="t m0 x32 h5 y6f ff2 fs3 fc0 sc0 ls0 ws0">complex<span class="_ _d"> </span>processing<span class="_ _d"> </span>(e.g.,<span class="_ _d"> </span>the<span class="_ _d"> </span><span class="ff7">getprop<span class="_ _1"> </span></span>bytecode,<span class="_ _8"> </span>which<span class="_ _1"> </span>imple-</div><div class="t m0 x32 h5 y70 ff2 fs3 fc0 sc0 ls0 ws0">ments<span class="_ _5"> </span>full<span class="_ _5"> </span>Ja<span class="_ _2"></span>v<span class="_ _2"></span>aScript<span class="_ _5"> </span>property<span class="_ _7"> </span>value<span class="_ _5"> </span>access,<span class="_ _7"> </span>including<span class="_ _5"> </span>special<span class="_ _5"> </span>cases</div><div class="t m0 x32 h5 y71 ff2 fs3 fc0 sc0 ls0 ws0">for<span class="_ _5"> </span>cached<span class="_ _5"> </span>and<span class="_ _3"> </span>dense<span class="_ _5"> </span>array<span class="_ _5"> </span>access).</div><div class="t m0 x33 h5 y72 ff2 fs3 fc0 sc0 ls0 ws0">Fat<span class="_ _d"> </span>bytecodes<span class="_ _1"> </span>ha<span class="_ _2"></span>v<span class="_ _2"></span>e<span class="_ _d"> </span>two<span class="_ _1"> </span>adv<span class="_ _2"></span>antages:<span class="_ _d"> </span>fewer<span class="_ _d"> </span>bytecodes<span class="_ _d"> </span>means</div><div class="t m0 x32 h5 y74 ff2 fs3 fc0 sc0 ls0 ws0">lower<span class="_ _5"> </span>dispatch<span class="_ _5"> </span>cost,<span class="_ _5"> </span>and<span class="_ _3"> </span>bigger<span class="_ _5"> </span>bytecode<span class="_ _5"> </span>implementations<span class="_ _5"> </span>give<span class="_ _5"> </span>the</div><div class="t m0 x32 h5 y75 ff2 fs3 fc0 sc0 ls0 ws0">compiler<span class="_ _5"> </span>more<span class="_ _5"> </span>opportunities<span class="_ _3"> </span>to<span class="_ _5"> </span>optimize<span class="_ _5"> </span>the<span class="_ _5"> </span>interpreter<span class="_ _2"></span>.</div><div class="t m0 x33 h5 y76 ff2 fs3 fc0 sc0 ls0 ws0">Fat<span class="_ _d"> </span>bytecodes<span class="_ _d"> </span>are<span class="_ _d"> </span>a<span class="_ _d"> </span>problem<span class="_ _d"> </span>for<span class="_ _d"> </span>T<span class="_ _2"></span>raceMonk<span class="_ _2"></span>ey<span class="_ _d"> </span>because<span class="_ _d"> </span>the<span class="_ _2"></span>y</div><div class="t m0 x32 h5 y77 ff2 fs3 fc0 sc0 ls0 ws0">require<span class="_ _8"> </span>the<span class="_ _d"> </span>recorder<span class="_ _8"> </span>to<span class="_ _d"> </span>reimplement<span class="_ _8"> </span>the<span class="_ _8"> </span>same<span class="_ _d"> </span>special<span class="_ _8"> </span>case<span class="_ _d"> </span>logic</div><div class="t m0 x32 h5 y78 ff2 fs3 fc0 sc0 ls0 ws0">in<span class="_ _d"> </span>the<span class="_ _d"> </span>same<span class="_ _d"> </span>way<span class="_ _b"></span>.<span class="_ _d"> </span>Also,<span class="_ _d"> </span>the<span class="_ _d"> </span>advantages<span class="_ _8"> </span>are<span class="_ _d"> </span>reduced<span class="_ _d"> </span>because<span class="_ _d"> </span>(a)</div><div class="t m0 x32 h5 y79 ff2 fs3 fc0 sc0 ls0 ws0">dispatch<span class="_ _6"> </span>costs<span class="_ _8"> </span>are<span class="_ _6"> </span>eliminated<span class="_ _8"> </span>entirely<span class="_ _8"> </span>in<span class="_ _6"> </span>compiled<span class="_ _8"> </span>traces,<span class="_ _8"> </span>(b)<span class="_ _6"> </span>the</div><div class="t m0 x32 h5 y7a ff2 fs3 fc0 sc0 ls0 ws0">traces<span class="_ _d"> </span>contain<span class="_ _1"> </span>only<span class="_ _d"> </span>one<span class="_ _d"> </span>special<span class="_ _1"> </span>case,<span class="_ _d"> </span>not<span class="_ _d"> </span>the<span class="_ _1"> </span>interpreter’<span class="_ _b"></span>s<span class="_ _1"> </span>lar<span class="_ _2"></span>ge</div><div class="t m0 x32 h5 y7b ff2 fs3 fc0 sc0 ls0 ws0">chunk<span class="_ _3"> </span>of<span class="_ _5"> </span>code,<span class="_ _3"> </span>and<span class="_ _3"> </span>(c)<span class="_ _5"> </span>TraceMonk<span class="_ _2"></span>ey<span class="_ _5"> </span>spends<span class="_ _3"> </span>less<span class="_ _3"> </span>time<span class="_ _5"> </span>running<span class="_ _3"> </span>the</div><div class="t m0 x32 h5 y7c ff2 fs3 fc0 sc0 ls0 ws0">base<span class="_ _5"> </span>interpreter<span class="_ _2"></span>.</div><div class="t m0 x33 h5 y7d ff2 fs3 fc0 sc0 ls0 ws0">One<span class="_ _5"> </span>way<span class="_ _5"> </span>we<span class="_ _5"> </span>have<span class="_ _5"> </span>mitigated<span class="_ _5"> </span>these<span class="_ _5"> </span>problems<span class="_ _5"> </span>is<span class="_ _5"> </span>by<span class="_ _5"> </span>implementing</div><div class="t m0 x32 h5 y7e ff2 fs3 fc0 sc0 ls0 ws0">certain<span class="_ _3"> </span>complex<span class="_ _3"> </span>bytecodes<span class="_ _3"> </span>in<span class="_ _3"> </span>the<span class="_ _3"> </span>recorder<span class="_ _3"> </span>as<span class="_ _3"> </span>sequences<span class="_ _6"> </span>of<span class="_ _3"> </span>simple</div><div class="t m0 x32 h5 y7f ff2 fs3 fc0 sc0 ls0 ws0">bytecodes.<span class="_ _7"> </span>Expressing<span class="_ _5"> </span>the<span class="_ _7"> </span>original<span class="_ _7"> </span>semantics<span class="_ _5"> </span>this<span class="_ _7"> </span>way<span class="_ _7"> </span>is<span class="_ _5"> </span>not<span class="_ _7"> </span>too<span class="_ _7"> </span>dif-</div><div class="t m0 x32 h5 y80 ff2 fs3 fc0 sc0 ls0 ws0">ficult,<span class="_ _5"> </span>and<span class="_ _5"> </span>recording<span class="_ _5"> </span>simple<span class="_ _3"> </span>bytecodes<span class="_ _5"> </span>is<span class="_ _5"> </span>much<span class="_ _5"> </span>easier<span class="_ _2"></span>.<span class="_ _5"> </span>This<span class="_ _5"> </span>enables</div><div class="t m0 x32 h5 y81 ff2 fs3 fc0 sc0 ls0 ws0">us<span class="_ _5"> </span>to<span class="_ _5"> </span>retain<span class="_ _5"> </span>the<span class="_ _5"> </span>adv<span class="_ _2"></span>antages<span class="_ _5"> </span>of<span class="_ _5"> </span>f<span class="_ _2"></span>at<span class="_ _5"> </span>bytecodes<span class="_ _5"> </span>while<span class="_ _5"> </span>a<span class="_ _2"></span>v<span class="_ _2"></span>oiding<span class="_ _5"> </span>some<span class="_ _5"> </span>of</div><div class="t m0 x32 h5 y82 ff2 fs3 fc0 sc0 ls0 ws0">their<span class="_ _5"> </span>problems<span class="_ _5"> </span>for<span class="_ _3"> </span>trace<span class="_ _5"> </span>recording.<span class="_ _5"> </span>This<span class="_ _5"> </span>is<span class="_ _5"> </span>particularly<span class="_ _3"> </span>ef<span class="_ _2"></span>fecti<span class="_ _2"></span>v<span class="_ _2"></span>e<span class="_ _5"> </span>for</div><div class="t m0 x32 h5 y83 ff2 fs3 fc0 sc0 ls0 ws0">fat<span class="_ _3"> </span>bytecodes<span class="_ _5"> </span>that<span class="_ _3"> </span>recurse<span class="_ _3"> </span>back<span class="_ _3"> </span>into<span class="_ _5"> </span>the<span class="_ _3"> </span>interpreter<span class="_ _2"></span>,<span class="_ _3"> </span>for<span class="_ _5"> </span>example<span class="_ _3"> </span>to</div><div class="t m0 x32 h5 y84 ff2 fs3 fc0 sc0 ls0 ws0">con<span class="_ _2"></span>vert<span class="_ _5"> </span>an<span class="_ _3"> </span>object<span class="_ _3"> </span>into<span class="_ _3"> </span>a<span class="_ _5"> </span>primitive<span class="_ _5"> </span>value<span class="_ _3"> </span>by<span class="_ _5"> </span>inv<span class="_ _2"></span>oking<span class="_ _3"> </span>a<span class="_ _5"> </span>well-known</div><div class="t m0 x32 h5 y85 ff2 fs3 fc0 sc0 ls0 ws0">method<span class="_ _5"> </span>on<span class="_ _5"> </span>the<span class="_ _3"> </span>object,<span class="_ _5"> </span>since<span class="_ _5"> </span>it<span class="_ _5"> </span>lets<span class="_ _5"> </span>us<span class="_ _5"> </span>inline<span class="_ _5"> </span>this<span class="_ _3"> </span>function<span class="_ _5"> </span>call.</div><div class="t m0 x33 h5 y86 ff2 fs3 fc0 sc0 ls0 ws0">It<span class="_ _3"> </span>is<span class="_ _5"> </span>important<span class="_ _5"> </span>to<span class="_ _3"> </span>note<span class="_ _5"> </span>that<span class="_ _3"> </span>we<span class="_ _5"> </span>split<span class="_ _3"> </span>f<span class="_ _2"></span>at<span class="_ _5"> </span>opcodes<span class="_ _3"> </span>into<span class="_ _5"> </span>thinner<span class="_ _3"> </span>op-</div><div class="t m0 x32 h5 y87 ff2 fs3 fc0 sc0 ls0 ws0">codes<span class="_ _5"> </span>only<span class="_ _3"> </span>during<span class="_ _5"> </span>recording.<span class="_ _5"> </span>When<span class="_ _5"> </span>running<span class="_ _3"> </span>purely<span class="_ _5"> </span>interpretati<span class="_ _2"></span>vely</div><div class="t m0 x32 h5 y88 ff2 fs3 fc0 sc0 ls0 ws0">(i.e.<span class="_ _5"> </span>code<span class="_ _3"> </span>that<span class="_ _5"> </span>has<span class="_ _5"> </span>been<span class="_ _3"> </span>blacklisted),<span class="_ _5"> </span>the<span class="_ _5"> </span>interpreter<span class="_ _5"> </span>directly<span class="_ _3"> </span>and<span class="_ _5"> </span>ef-</div><div class="t m0 x32 h5 y89 ff2 fs3 fc0 sc0 ls0 ws0">ficiently<span class="_ _5"> </span>executes<span class="_ _5"> </span>the<span class="_ _5"> </span>fat<span class="_ _5"> </span>opcodes.</div><div class="t m0 x32 hc y23a ff1 fs3 fc0 sc0 ls0 ws0">6.4<span class="_ _9"> </span>Pr<span class="_ _2"></span>eemption</div><div class="t m0 x32 h5 yce ff2 fs3 fc0 sc0 ls0 ws0">SpiderMonkey<span class="_ _b"></span>,<span class="_ _5"> </span>like<span class="_ _5"> </span>man<span class="_ _2"></span>y<span class="_ _5"> </span>VMs,<span class="_ _7"> </span>needs<span class="_ _5"> </span>to<span class="_ _5"> </span>preempt<span class="_ _5"> </span>the<span class="_ _7"> </span>user<span class="_ _5"> </span>program</div><div class="t m0 x32 h5 ycf ff2 fs3 fc0 sc0 ls0 ws0">periodically<span class="_ _2"></span>.<span class="_ _8"> </span>The<span class="_ _d"> </span>main<span class="_ _d"> </span>reasons<span class="_ _1"> </span>are<span class="_ _8"> </span>to<span class="_ _d"> </span>prevent<span class="_ _d"> </span>infinitely<span class="_ _d"> </span>looping</div><div class="t m0 x32 h5 y12e ff2 fs3 fc0 sc0 ls0 ws0">scripts<span class="_ _5"> </span>from<span class="_ _5"> </span>locking<span class="_ _3"> </span>up<span class="_ _5"> </span>the<span class="_ _5"> </span>host<span class="_ _5"> </span>system<span class="_ _5"> </span>and<span class="_ _5"> </span>to<span class="_ _5"> </span>schedule<span class="_ _3"> </span>GC.</div><div class="t m0 x33 h5 yd1 ff2 fs3 fc0 sc0 ls0 ws0">In<span class="_ _3"> </span>the<span class="_ _5"> </span>interpreter<span class="_ _2"></span>,<span class="_ _5"> </span>this<span class="_ _3"> </span>had<span class="_ _3"> </span>been<span class="_ _5"> </span>implemented<span class="_ _3"> </span>by<span class="_ _5"> </span>setting<span class="_ _3"> </span>a<span class="_ _5"> </span>“pre-</div><div class="t m0 x32 h5 yd2 ff2 fs3 fc0 sc0 ls0 ws0">empt<span class="_ _6"> </span>now”<span class="_ _6"> </span>flag<span class="_ _6"> </span>that<span class="_ _6"> </span>was<span class="_ _6"> </span>checked<span class="_ _3"> </span>on<span class="_ _8"> </span>e<span class="_ _2"></span>very<span class="_ _6"> </span>backward<span class="_ _6"> </span>jump.<span class="_ _6"> </span>This</div><div class="t m0 x32 h5 yd3 ff2 fs3 fc0 sc0 ls0 ws0">strategy<span class="_ _5"> </span>carried<span class="_ _5"> </span>ov<span class="_ _2"></span>er<span class="_ _5"> </span>into<span class="_ _5"> </span>T<span class="_ _2"></span>raceMonkey:<span class="_ _5"> </span>the<span class="_ _5"> </span>VM<span class="_ _5"> </span>inserts<span class="_ _5"> </span>a<span class="_ _5"> </span>guard<span class="_ _5"> </span>on</div><div class="t m0 x32 h5 y94 ff2 fs3 fc0 sc0 ls0 ws0">the<span class="_ _6"> </span>preemption<span class="_ _3"> </span>flag<span class="_ _6"> </span>at<span class="_ _6"> </span>ev<span class="_ _2"></span>ery<span class="_ _6"> </span>loop<span class="_ _3"> </span>edge.<span class="_ _6"> </span>W<span class="_ _b"></span>e<span class="_ _6"> </span>measured<span class="_ _6"> </span>less<span class="_ _6"> </span>than<span class="_ _6"> </span>a</div><div class="t m0 x32 h5 y95 ff2 fs3 fc0 sc0 ls0 ws0">1%<span class="_ _3"> </span>increase<span class="_ _6"> </span>in<span class="_ _3"> </span>runtime<span class="_ _6"> </span>on<span class="_ _3"> </span>most<span class="_ _6"> </span>benchmarks<span class="_ _3"> </span>for<span class="_ _6"> </span>this<span class="_ _3"> </span>extra<span class="_ _3"> </span>guard.</div><div class="t m0 x32 h5 y96 ff2 fs3 fc0 sc0 ls0 ws0">In<span class="_ _5"> </span>practice,<span class="_ _5"> </span>the<span class="_ _5"> </span>cost<span class="_ _5"> </span>is<span class="_ _5"> </span>detectable<span class="_ _5"> </span>only<span class="_ _5"> </span>for<span class="_ _5"> </span>programs<span class="_ _5"> </span>with<span class="_ _5"> </span>v<span class="_ _2"></span>ery<span class="_ _5"> </span>short</div><div class="t m0 x32 h5 y97 ff2 fs3 fc0 sc0 ls0 ws0">loops.</div><div class="t m0 x33 h5 y98 ff2 fs3 fc0 sc0 ls0 ws0">W<span class="_ _b"></span>e<span class="_ _8"> </span>tested<span class="_ _8"> </span>and<span class="_ _8"> </span>rejected<span class="_ _d"> </span>a<span class="_ _6"> </span>solution<span class="_ _8"> </span>that<span class="_ _8"> </span>avoided<span class="_ _6"> </span>the<span class="_ _8"> </span>guards<span class="_ _8"> </span>by</div><div class="t m0 x32 h5 y99 ff2 fs3 fc0 sc0 ls0 ws0">compiling<span class="_ _6"> </span>the<span class="_ _6"> </span>loop<span class="_ _6"> </span>edge<span class="_ _8"> </span>as<span class="_ _6"> </span>an<span class="_ _6"> </span>unconditional<span class="_ _6"> </span>jump,<span class="_ _8"> </span>and<span class="_ _6"> </span>patching</div><div class="t m0 x32 h5 y9a ff2 fs3 fc0 sc0 ls0 ws0">the<span class="_ _8"> </span>jump<span class="_ _d"> </span>target<span class="_ _8"> </span>to<span class="_ _d"> </span>an<span class="_ _8"> </span>exit<span class="_ _8"> </span>routine<span class="_ _d"> </span>when<span class="_ _8"> </span>preemption<span class="_ _d"> </span>is<span class="_ _8"> </span>required.</div><div class="t m0 x32 h5 y9b ff2 fs3 fc0 sc0 ls0 ws0">This<span class="_ _8"> </span>solution<span class="_ _8"> </span>can<span class="_ _8"> </span>make<span class="_ _8"> </span>the<span class="_ _8"> </span>normal<span class="_ _d"> </span>case<span class="_ _6"> </span>slightly<span class="_ _d"> </span>f<span class="_ _2"></span>aster<span class="_ _2"></span>,<span class="_ _8"> </span>but<span class="_ _6"> </span>then</div><div class="t m0 x32 h5 y9c ff2 fs3 fc0 sc0 ls0 ws0">preemption<span class="_ _5"> </span>becomes<span class="_ _3"> </span>v<span class="_ _2"></span>ery<span class="_ _5"> </span>slow<span class="_ _b"></span>.<span class="_ _5"> </span>The<span class="_ _3"> </span>implementation<span class="_ _5"> </span>was<span class="_ _5"> </span>also<span class="_ _5"> </span>very</div><div class="t m0 x32 h5 y9d ff2 fs3 fc0 sc0 ls0 ws0">complex,<span class="_ _7"> </span>especially<span class="_ _5"> </span>trying<span class="_ _7"> </span>to<span class="_ _5"> </span>restart<span class="_ _7"> </span>execution<span class="_ _7"> </span>after<span class="_ _5"> </span>the<span class="_ _7"> </span>preemption.</div></div><div class="pi" data-data='{"ctm":[1.673203,0.000000,0.000000,1.673203,0.000000,0.000000]}'></div></div></div>