874580 - IonMonkey: Optimize for .. of

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, defect, P3)

Description

[Tom S [:evilpie]]

Attachment: really a wip

If we want people to use ES6, we should also make it fast! I wrote a WIP patch that works only on x64 and without OSR. It also only handles Arrays as the target object of the ElementIteratorClass instance. Handling for example strings should be relatively forward, but might blow up the code. For better code we we need some analysis that tells us the target object of an iterator, so that we can hoist bounds check and do typed loads etc. Maybe at some point we can generate code that is on par with:
for (var i = 0; i < a.length; i++) { a[i] }

Comment 1

[Tom S [:evilpie]]

Attachment: WIP x64

I think this patch now has correct behavior, but is still x64. I introduced GetIteratorFlag, which tries to find the matching IteratorStart for some IteratorNext or IteratorMore. I also corrected the class checks to be correct.

Comment 2

[Tom S [:evilpie]]

Attachment: test case

Performance before:
--no-ion --no-baseline 1s
--no-ion 0.6s
--ion --baseline 0.57
After:
--ion --baseline 0.099s

Comment 3

[Tom S [:evilpie]]

Attachment: v1

So I got this working on x86 and x64, which makes me believe that it is going to work on arm. I think this is pretty straightforward and should be correct. I hope Jason can make a short sanity check there. This is only done for arrays at the moment, because there we can assume that a length property exists. I would like to work on some further optimization so that we can optimize based on the target object.

Comment 4

[Jason Orendorff [:jorendorff]]

Comment on attachment 753473 [details] [diff] [review]
v1

Review of attachment 753473 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/ion/CodeGenerator.cpp
@@ +4919,5 @@
> +        return false;
> +
> +    // Check if this is really an ElementIterator
> +    masm.branchTestObjClass(Assembler::NotEqual, obj, temp, &js::ElementIteratorClass,
> +                            ool->entry());

I think we also have to check that the .next method is what we expect.

And don't we also have to store the index back into the iterator object, in case we bail out and have to resume in the interpreter or whatever?

We need tests for both those things, if they are actual bugs and the existing tests didn't catch them!

I'm not sure this is the right long-term approach. I think we should change the bytecode to make it look more like a desugaring of for-of in terms of method calls.

But there's nothing preventing us from doing this now and doing that later.

Comment 5

[Jan de Mooij [:jandem]]

Comment on attachment 753473 [details] [diff] [review]
v1

Review of attachment 753473 [details] [diff] [review]:
-----------------------------------------------------------------

Thanks for looking into this! Resetting review flag per our IRC conversation last week: use TI so that you statically know the Class (TypeObject determines Class nowadays) and whether the "next" method is sane.

::: js/src/ion/IonBuilder.cpp
@@ +8034,5 @@
>  }
>  
> +// Find the matching JSOP_ITER flags, OSR values can be ignored.
> +uint8_t
> +GetIteratorFlags(MDefinition *iter) {

It may be simpler to store the flags in the CFGState, or get it from one of the pc's already stored in it if possible?

Comment 6

[Tom S [:evilpie]]

For of is now desugared to some method calls. I believe most of the work is now based on potentially inlining the next() function, especially in the array case. An other area would be avoiding the allocation of the result object. Till or maybe shu and other PJS guys are probably better suited for this.

Comment 7

[Jason Orendorff [:jorendorff]]

Would love to get someone to look at this briefly.

According to this nonsense:
  http://jsperf.com/for-of-vs-for-loop
for-of is currently about 6x slower than an ordinary for loop.

But in the shell:

  $ ./r-objdir/js --ion-eager
  js> var m = []; for (var i = 0; i < 10000000; i++) m[i] = i;
  9999999
  js> var t0 = Date.now(); var total = 0; for (var j = 0; j < m.length; j++) total += m[j]; Date.now() - t0;
  584
  js> var t0 = Date.now(); var total = 0; for (var e of m) total += e; Date.now() - t0;
  849

This is one of those cases where jsperf's result seems more likely to me, but it might be wiser to trust neither...

Comment 8

[Jason Orendorff [:jorendorff]]

function make() {
    var arr = [];
    for (var i = 0; i < 10000000; i++)
        arr[i] = i;
    return arr;
}

function loop1(arr) {
    var t0 = Date.now();
    var total = 0;
    for (var i = 0; i < arr.length; i++)
        total += arr[i];
    print(Date.now() - t0);
    assertEq(total, arr.length * (arr.length - 1) / 2);
}

function loop2(arr) {
    var t0 = Date.now();
    var total = 0;
    for (var e of arr)
        total += e;
    print(Date.now() - t0);
    assertEq(total, arr.length * (arr.length - 1) / 2);
}

var a = make();
for (var k = 0; k < 5; k++) {
    loop1(a);
    loop2(a);
}


Results: for-of is about 35x slower.
13
534
9
405
10
360
9
348
10
352

Comment 9

[Kohei Yoshino]

Like like Bug 927079, people may stop using for...of loops unless the performance issue is resolved. It would be nice if you could fix it before the release of 27.

Comment 10

[bhavana bajaj [:bajaj]]

(In reply to Kohei Yoshino [:kohei] from comment #9)
> Like like Bug 927079, people may stop using for...of loops unless the
> performance issue is resolved. It would be nice if you could fix it before
> the release of 27.

This does not look like a bug we track as this is not a recent regression/stability issue/new feature fallout which are the kind of bugs we typically track for release.Feel free to renom if anything was not interpreted correctly.

If this is RESOLVED before end on this cycle, you can always request uplift on Fx27 by using the approval-mozilla-aurora and depending on the risk/reward we can approve it

Comment 11

[Jan de Mooij [:jandem]]

I looked into this a bit. We can make this faster by inlining the IsArrayIterator intrinsic (bug 932714), but the main problem is GC since ArrayIteratorNext returns a new object every time it's called.

Comment 12

[Dave Garrett]

Attachment: another test case

I just happened to be curious as to the perf issues with for loops today and found this bug after a little bit of research. Might as well add what little bit of info I learned here in case it might be useful. I wrote a quick and dirty test case which I've attached.

"for (var i=0; i<array.length; i++): 1168 thousand ops/sec"
"for (let i=0; i<array.length; i++): 1168 thousand ops/sec"
"for (i=0; i<array.length; i++): 711 thousand ops/sec"
"for (var i in array): 658 thousand ops/sec"
"for (let i in array): 762 thousand ops/sec"
"for (i in array): 623 thousand ops/sec"
"for (var i of array): 285 thousand ops/sec"
"for (let i of array): 286 thousand ops/sec"
"for (i of array): 253 thousand ops/sec"

(just adding up the values of a 10 million element array with each element set to its index)

So yeah, it looks like for..of is slow, for..in is also somewhat slow, for i<length with a global 'i' is also slow, and for i<length with local 'i' is fastest. (and 'let i in array' is a bit faster than var or global, for some reason)

This quick test was with the current Nightly via dumping some code into the browser console.

(In reply to Jason Orendorff [:jorendorff] from comment #7)
> According to this nonsense:
>   http://jsperf.com/for-of-vs-for-loop
> for-of is currently about 6x slower than an ordinary for loop.

Not sure how trustworthy jsperf is, however that test shows for..of to be in the same ballpark as for i<length for me, whilst this one has for..of and for..in showing as slower by orders of magnitude:
http://jsperf.com/for-of-vs-standard-for

For this laptop in a new profile with the current nightly:
for i<length: 68,600 ops/sec
for..of: 1,745 ops/sec
for..in: 250 ops/sec

No idea how it's that bad there.

Comment 13

[Dave Garrett]

(in comment 12 I really should have said iterations per second, rather than operations)

Comment 14

[Boris Zbarsky [:bzbarsky]]

Using the testcase from comment 8, I see numbers like so on tip (with bug 1110871 fixed):

33
381
11
160
12
160
9
150
9
149

so about a 15x slowdown.

With the various patches that just got added as dependencies, I see numbers like:

37
319
11
112
9
113
11
113
8
112

so down to only about 10x slower, yay?

The real issue is the object allocation we end up having to do....

Comment 15

[Nicolas B. Pierron [:nbp]]

This issue got fixed by the addition of Scalar Replacement (Bug 992845) and Branch Pruning (Bug 1229813)