537084 - TM: Avoid perf regressions by better handling of code that doesn't trace well

Status: RESOLVED INVALID

(Core :: JavaScript Engine, defect)

Description

[Duncan Loveday]

User-Agent:       Mozilla/5.0 (Windows; U; Windows NT 5.1; en-GB; rv:1.9.1.6) Gecko/20091201 Firefox/3.5.6 (.NET CLR 2.0.50727)
Build Identifier: M-C

See Bug 535925 comment 11. There are a number of reasons why code does not always trace well in TM including too many branches (Bug 516264) and too many type maps (Bug 535925). In the longer term these will get fixed but at the moment these examples can suffer a significant performance *penalty* with JIT enabled, arising from large numbers of premature trace exits. In the short term it would be good if this could be avoided so that something close to interpreter performance levels was obtained.

From Bug 535925 comment 11: Once the system has stopped recording traces, whether due to branchiness or too many type maps or any other reason, keep stats on trace entries vs exits. If the percentage of bad exits exceeds a threshold, delete all the compiled traces and black list the loop.

Crude but would allow code that can't currently be traced well to revert to
interpreter performance rather than suffer a drop in performance due to
continual exits.


Reproducible: Always

Steps to Reproduce:
1. See test cases in bug 535925, 516264, others where TM causes a slowdown.
2.
3.
Actual Results:  
JIT makes these cases run more slowly.

Expected Results:  
In the short term, TM should detect that it is unable to trace these cases well and defer to the interpreter.

IMHO this would be a big win. TM is still a WIP. It performs brilliantly on very simple control structures but the gains quickly evaporate for code of even modest complexity. By fixing this bug you can have all of the current benefits for code that traces well and never cause a significant slowdown for code that doesn't. As TM improves over the medium to long term this change would become less and less necessary but it's still a good backstop to have.

Comment 1

[David Mandelin [:dmandelin]]

Duncan, this is a good idea. I also wanted to point out that we are working on stuff that will help these hard cases over in bug 536277.

Comment 2

[Duncan Loveday]

This might be a duplicate of Bug 504881 and/or Bug 479102

Comment 3

[Duncan Loveday]

Attachment: Test case

This is based on David Anderson's pathological branchy loop test case in Bug 516264. I extended it to show what happens when a loop has 2, 4, 8, 16, ..., 4096 branches. You can see how the big win from JIT turns into a loss as soon as there are more than 32 branches.

You do say "patches are welcome" don't you ? I have a little patch in my tree that relies on the simple heuristic that if MAX_BRANCHES is ever reached for a given loop then that loop is "too branchy" and the system should revert to the interpreter.

$ diff -u10 jstracer.cpp.orig jstracer.cpp
--- jstracer.cpp.orig   2009-12-30 23:48:59.916067000 +0000
+++ jstracer.cpp        2009-12-31 00:21:34.055506300 +0000
@@ -6556,20 +6556,25 @@
 static JS_REQUIRES_STACK VMSideExit*
 ExecuteTree(JSContext* cx, TreeFragment* f, uintN& inlineCallCount,
             VMSideExit** innermostNestedGuardp)
 {
 #ifdef MOZ_TRACEVIS
     TraceVisStateObj tvso(cx, S_EXECUTE);
 #endif
     JS_ASSERT(f->root == f && f->code());
     JSTraceMonitor* tm = &JS_TRACE_MONITOR(cx);
 
+// If we've hit MAX_BRANCHES for this loop, assume
+// it's too branchy to trace well and ignore the
+// compiled trace...
+if (f->branchCount >= MAX_BRANCHES) return NULL;
+
     if (!ScopeChainCheck(cx, f))
         return NULL;
 
     /* Initialize trace state. */
     InterpState state(cx, tm, f, inlineCallCount, innermostNestedGuardp);
     double* stack = tm->storage.stack();
     double* global = tm->storage.global();
     JSObject* globalObj = f->globalObj;
     unsigned ngslots = f->globalSlots->length();
     uint16* gslots = f->globalSlots->data();
$ 

Here's the pre- and post-patch versions running

Pre-patch, no JIT
=================

$ ./jsOld merge.js
Time2=4750(i=1000000)
Time4=5859(i=1000000)
Time8=7328(i=1000000)
Time16=8328(i=1000000)
Time32=9025(i=1000000)
Time64=607(i=100000)
Time128=594(i=100000)
Time256=873(i=100000)
Time512=936(i=100000)
Time1024=1341(i=100000)
Time2048=1416(i=100000)
Time4096=1508(i=100000)
$ 

Pre-patch, JIT
==============

$ ./jsOld -j merge.js
Time2=31(i=1000000)
Time4=31(i=1000000)
Time8=31(i=1000000)
Time16=63(i=1000000)
Time32=70(i=1000000)
Time64=6365(i=100000)
Time128=10930(i=100000)
Time256=16631(i=100000)
Time512=18663(i=100000)
Time1024=22021(i=100000)
Time2048=24115(i=100000)
Time4096=23596(i=100000)
recorder: started(12), aborted(0), completed(293), different header(0), trees trashed(12), slot promoted(0), unstable loop variable(0), breaks(0), returns(0), merged loop exits(281), unstableInnerCalls(0), blacklisted(0)
monitor: exits(597951), BRANCH(597944), CASE(0), DEFAULT(0), LOOP(7), NESTED(0), MISMATCH(0), OOM(0), OVERFLOW(0), UNSTABLE_LOOP(0), TIMEOUT(0), DEEP_BAIL(0), STATUS(0), RECURSIVE_UNLINKED(0), RECURSIVE_LOOP(0), RECURSIVE_MISMATCH(0), RECURSIVE_EMPTY_RP(0), RECURSIVE_SLURP_FAIL(0), RECURSIVE_SLURP_MISMATCH(0), timeouts(0), type mismatch(0), triggered(597951), global mismatch(0), flushed(1)
$ 

Post-patch, JIT
===============
$ ./js -j merge.js
Time2=16(i=1000000)
Time4=31(i=1000000)
Time8=16(i=1000000)
Time16=47(i=1000000)
Time32=38(i=1000000)
Time64=712(i=100000)
Time128=721(i=100000)
Time256=1042(i=100000)
Time512=1347(i=100000)
Time1024=1602(i=100000)
Time2048=1701(i=100000)
Time4096=1796(i=100000)
recorder: started(12), aborted(0), completed(293), different header(0), trees trashed(12), slot promoted(0), unstable loop variable(0), breaks(0), returns(0), merged loop exits(281), unstableInnerCalls(0), blacklisted(0)
monitor: exits(780), BRANCH(775), CASE(0), DEFAULT(0), LOOP(5), NESTED(0), MISMATCH(0), OOM(0), OVERFLOW(0), UNSTABLE_LOOP(0), TIMEOUT(0), DEEP_BAIL(0), STATUS(0), RECURSIVE_UNLINKED(0), RECURSIVE_LOOP(0), RECURSIVE_MISMATCH(0), RECURSIVE_EMPTY_RP(0), RECURSIVE_SLURP_FAIL(0), RECURSIVE_SLURP_MISMATCH(0), timeouts(0), type mismatch(0), triggered(780), global mismatch(0), flushed(1)
$ 


With the patch, performance up to 32 branches is about the same as the pre-patch version with JIT. Performance over 32 branches is slower but of the same order as the pre-patch version without JIT.

Is this worth pursuing ?

Comment 4

[Duncan Loveday]

This is invalid. The big jump in execution time as we pass the 32 branch limit is an artefact of debug builds. Repeating the test above with an optimised build shows no clear benefit even for the most branchy case.

$ ./jsOldOpt -j  merge.js
Time2=31(i=1000000)
Time4=31(i=1000000)
Time8=31(i=1000000)
Time16=47(i=1000000)
Time32=47(i=1000000)
Time64=60(i=100000)
Time128=105(i=100000)
Time256=132(i=100000)
Time512=158(i=100000)
Time1024=173(i=100000)
Time2048=195(i=100000)
Time4096=216(i=100000)
$ ./jsOpt -j  merge.js
Time2=31(i=1000000)
Time4=31(i=1000000)
Time8=31(i=1000000)
Time16=47(i=1000000)
Time32=46(i=1000000)
Time64=129(i=100000)
Time128=148(i=100000)
Time256=167(i=100000)
Time512=188(i=100000)
Time1024=201(i=100000)
Time2048=220(i=100000)
Time4096=236(i=100000)
$