469347 - TM: for loop with i<sarr.length slower with jit enabled

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect, P2)

Description

[Dorus Peelen]

User-Agent:       Mozilla/5.0 (Windows; U; Windows NT 6.0; nl; rv:1.9.0.4) Gecko/2008102920 Firefox/3.0.4
Build Identifier: Mozilla/5.0 (Windows; U; Windows NT 6.0; en-US; rv:1.9.2a1pre) Gecko/20081212 Minefield/3.2a1pre

As a follow up of bug 451974, here some more for loop problems.

Both 

var f=function(x){}; for (var i=0, len=sarr.length; i<len; i++) { f(sarr[i]); }

And

for (var i=0; i<hColl.length; i++) { }

are 1.5x to 2x slower with JIT enabled then with JIT disabled. As i got the idea these 2 problems are related, i put them in one bug for now.

Reproducible: Always

Comment 1

[Dorus Peelen]

Attachment: Somewhat minimized testcase

Comment 2

[Dorus Peelen]

Yay me for copying exactly the 2 lines that where supposed to go into the other bug. Anyway, here i'm talking about these:

for (var i=0; i<sarr.length; i++) { }

And

var i = 0; while (i < sarr.length) { i++; }

Not the 2 mentioned in the first report.

Comment 3

[Jason Orendorff [:jorendorff]]

If sarr is a dense array, the loop is about 15x faster with JIT.

In the testcase, it is a sparse array. record_JSOP_LENGTH aborts if we're taking the length of anything other than a string or dense array.  This should be fixed.  If we're going to trace the DOM someday soon, we need to be able to trace `nodelist.length`.

Comment 4

[Boris Zbarsky [:bzbarsky]]

Again, shouldn't we be blacklisting?

Comment 5

[Boris Zbarsky [:bzbarsky]]

The testcase in bug 469351 in fact hits the nodelist case.

Comment 6

[Damon Sicore (:damons)]

P2.

Comment 7

[Damon Sicore (:damons)]

blocking1.9.1+

Comment 8

[David Mandelin [:dmandelin]]

It looks like we could trace JSOP_LENGTH on a sparse array fairly easily if we just use a guard on "being a sparse array".

Comment 9

[Jeff Walden [:Waldo]]

Attachment: Patch

I was confused by record_JSOP_GETPROP for awhile because I assumed it looked at the atom argument to that opcode in bytecode, when in reality it leans quite heavily on the property cache.


find-waldo-now:~/moz/js-tm/js/src jwalden$ cat /tmp/slow.js 
var a = [];
a[9999999] = 0;
for (var i = 0; i < a.length; i++);

find-waldo-now:~/moz/js-tm/js/src jwalden$ time ../../obj-i386-apple-darwin8.11.1/dist/bin/js /tmp/slow.js 

real    0m3.262s
user    0m2.696s
sys     0m0.048s
find-waldo-now:~/moz/js-tm/js/src jwalden$ time ../../obj-i386-apple-darwin8.11.1/dist/bin/js -j /tmp/slow.js 

real    0m0.086s
user    0m0.063s
sys     0m0.014s
find-waldo-now:~/moz/js-tm/js/src jwalden$ cat /tmp/object.js 
var a = {};
a.length = 9999999;
for (var i = 0; i < a.length; i++);

find-waldo-now:~/moz/js-tm/js/src jwalden$ time ../../obj-i386-apple-darwin8.11.1/dist/bin/js /tmp/object.js 

real    0m3.528s
user    0m3.294s
sys     0m0.049s
find-waldo-now:~/moz/js-tm/js/src jwalden$ time ../../obj-i386-apple-darwin8.11.1/dist/bin/js -j /tmp/object.js 

real    0m0.266s
user    0m0.168s
sys     0m0.016s

Comment 10

[Brendan Eich [:brendan]]

Comment on attachment 367159 [details] [diff] [review]
Patch

No factoring required beyond what's already there, since the property cache test path computes atom correctly for JSOP_LENGTH. It has to, because the do_getprop_with_lval: code is shared in the interpreter for JSOP_LENGTH on values other than strings and dense arrays.

>+    if (OBJ_IS_ARRAY(cx, obj)) {
>+        if (OBJ_IS_DENSE_ARRAY(cx, obj)) {
>+            if (!guardDenseArray(obj, obj_ins))
>+                ABORT_TRACE("OBJ_IS_DENSE_ARRAY but not?!?");
>+        } else {
>+            if (!guardClass(obj, obj_ins, &js_SlowArrayClass, snapshot(MISMATCH_EXIT)))
>+                ABORT_TRACE("can't trace length property access on non-array");
>+        }
>+        v_ins = lir->ins1(LIR_i2f, stobj_get_fslot(obj_ins, JSSLOT_ARRAY_LENGTH));

The guardDenseArray and guardClass could use BRANCH_EXIT not MISMATCH_EXIT since you cover both paths here, and arrays do sometimes go from dense to slow. Why not?

/be

Comment 11

[Jeff Walden [:Waldo]]

Attachment: With branch exits

(In reply to comment #10)
 The guardDenseArray and guardClass could use BRANCH_EXIT not MISMATCH_EXIT
> since you cover both paths here, and arrays do sometimes go from dense to slow.
> Why not?

No particular reason other than unlikeliness.

Comment 12

[Andreas Gal :gal]

Could you add an testcase for this transition?

Comment 13

[Jeff Walden [:Waldo]]

Attachment: With some transition testing from native code

I could probably reason out the exact side-exit count, but this works and is much easier to do.  Adding any one of the three objects to the end of the array doesn't change the triggers/exit counts in jitstats, which should be good enough for verification purposes, I think.

Comment 14

[Andreas Gal :gal]

Comment on attachment 367938 [details] [diff] [review]
With some transition testing from native code

>From: Jeff Walden <[e-mail]>
>
>Bug 469347 - TM: obj.length and slowArray.length don't trace.  NOT REVIEWED YET
>
>diff --git a/js/src/jstracer.cpp b/js/src/jstracer.cpp
>--- a/js/src/jstracer.cpp
>+++ b/js/src/jstracer.cpp
>@@ -9431,11 +9431,22 @@ TraceRecorder::record_JSOP_LENGTH()
>     }
> 
>     JSObject* obj = JSVAL_TO_OBJECT(l);
>-    if (!OBJ_IS_DENSE_ARRAY(cx, obj))
>-        ABORT_TRACE("only dense arrays supported");
>-    if (!guardDenseArray(obj, get(&l)))
>-        ABORT_TRACE("OBJ_IS_DENSE_ARRAY but not?!?");
>-    LIns* v_ins = lir->ins1(LIR_i2f, stobj_get_fslot(get(&l), JSSLOT_ARRAY_LENGTH));
>+    LIns* obj_ins = get(&l);
>+    LIns* v_ins;
>+    if (OBJ_IS_ARRAY(cx, obj)) {
>+        if (OBJ_IS_DENSE_ARRAY(cx, obj)) {
>+            if (!guardDenseArray(obj, obj_ins, BRANCH_EXIT))
>+                ABORT_TRACE("OBJ_IS_DENSE_ARRAY but not?!?");

Nit: maybe JS_NOT_REACHED?

>+        } else {
>+            if (!guardClass(obj, obj_ins, &js_SlowArrayClass, snapshot(BRANCH_EXIT)))
>+                ABORT_TRACE("can't trace length property access on non-array");
>+        }
>+        v_ins = lir->ins1(LIR_i2f, stobj_get_fslot(obj_ins, JSSLOT_ARRAY_LENGTH));
>+    } else {
>+        if (!OBJ_IS_NATIVE(obj))
>+            ABORT_TRACE("can't trace length property access on non-array, non-native object");
>+        return getProp(obj, obj_ins);
>+    }
>     set(&l, v_ins);
>     return true;
> }
>diff --git a/js/src/trace-test.js b/js/src/trace-test.js
>--- a/js/src/trace-test.js
>+++ b/js/src/trace-test.js
>@@ -4567,6 +4567,79 @@ function testLengthInString()
> testLengthInString.expected = true;
> test(testLengthInString);
> 
>+function testSlowArrayLength()
>+{
>+  var counter = 0;
>+  var a = [];
>+  a[10000000 - 1] = 0;
>+  for (var i = 0; i < a.length; i++)
>+    counter++;
>+  return counter;
>+}
>+testSlowArrayLength.expected = 10000000;
>+testSlowArrayLength.jitstats = {
>+  recorderStarted: 1,
>+  recorderAborted: 0,
>+  sideExitIntoInterpreter: 1
>+};
>+test(testSlowArrayLength);
>+
>+function testObjectLength()
>+{
>+  var counter = 0;
>+  var a = {};
>+  a.length = 10000000;
>+  for (var i = 0; i < a.length; i++)
>+    counter++;
>+  return counter;
>+}
>+testObjectLength.expected = 10000000;
>+testObjectLength.jitstats = {
>+  recorderStarted: 1,
>+  recorderAborted: 0,
>+  sideExitIntoInterpreter: 1
>+};
>+test(testObjectLength);
>+
>+function testChangingObjectWithLength()
>+{
>+  var obj = { length: 10 };
>+  var dense = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
>+  var slow = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]; slow.slow = 5;
>+
>+  /*
>+   * The elements of objs constitute a De Bruijn sequence repeated 4x to trace
>+   * and run native code for every object and transition.
>+   */
>+  var objs = [obj, obj, obj, obj,
>+              obj, obj, obj, obj,
>+              dense, dense, dense, dense,
>+              obj, obj, obj, obj,
>+              slow, slow, slow, slow,
>+              dense, dense, dense, dense,
>+              dense, dense, dense, dense,
>+              slow, slow, slow, slow,
>+              slow, slow, slow, slow,
>+              obj, obj, obj, obj];
>+
>+  var counter = 0;
>+
>+  for (var i = 0, sz = objs.length; i < sz; i++)
>+  {
>+    var o = objs[i];
>+    for (var j = 0; j < o.length; j++)
>+      counter++;
>+  }
>+
>+  return counter;
>+}
>+testChangingObjectWithLength.expected = 400;
>+testChangingObjectWithLength.jitstats = {
>+  recorderAborted: 0,
>+  sideExitIntoInterpreter: 15 // empirically determined
>+};
>+test(testChangingObjectWithLength);
>+
> 
> /*****************************************************************************
>  *                                                                           *

Comment 15

[Robert Sayre]

http://hg.mozilla.org/mozilla-central/rev/b3b8454e003d

Comment 16

[Jeff Walden [:Waldo]]

http://hg.mozilla.org/tracemonkey/rev/b3b8454e003d for the original TM push

Comment 17

[Robert Sayre]

fixed1.9.1 long ago:
http://hg.mozilla.org/releases/mozilla-1.9.1/rev/df512fe9d7ef

Comment 18

[Aakash Desai [:aakashd]]

    verified FIXED on builds:

    Mozilla/5.0 (Windows; U; Windows NT 6.0; en-US; rv:1.9.1pre) Gecko/20090601
    Shiretoko/3.5pre (.NET CLR 3.5.30729) ID:20090601044045

    and

    Mozilla/5.0 (Windows; U; Windows NT 6.0; en-US; rv:1.9.2a1pre) Gecko/20090601
    Minefield/3.6a1pre (.NET CLR 3.5.30729) ID:20090601041706

    There's a subsequent bug (bug 496377) when MozMill is installed onto any
    profile (via any platform and whether or not jit is enabled/disabled).

Comment 19

[Bob Clary [:bc] (inactive)]

cvsroot/mozilla/js/tests/js1_8_1/trace/trace-test.js,v  <--  trace-test.js
new revision: 1.14; previous revision: 1.13

/cvsroot/mozilla/js/tests/shell.js,v  <--  shell.js

Comment 20

[Bob Clary [:bc] (inactive)]

testSlowArrayLength|testObjectLength|testChangingObjectWithLength