966743 - IonMonkey: Modify MArrayPush to accept multiple arguments

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, enhancement, P5)

Description

[Masaya Iseki[:isk](UTC+9)]

Attachment: array_push_bench_arg3.js

Now MArrayPush can accept one argument.
If Array#push has multiple arguments, this method can't inline.
I make benchmark and the result is below.
self-hosting version is in Bug961434

before patch: 1562ms
self-hosting: 1392ms
after patch: 948ms

Comment 1

[Masaya Iseki[:isk](UTC+9)]

Attachment: Bug966743.patch

I make patch.
The result of this patch is in before comment.

Comment 2

[Jan de Mooij [:jandem]]

Comment on attachment 8369184 [details] [diff] [review]
Bug966743.patch

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

::: js/src/jit/MCallOptimize.cpp
@@ +425,5 @@
> +                return InliningStatus_NotInlined;
> +        }
> +
> +        current->push(ins);
> +        if (!resumeAfter(ins))

Unfortunately this is not correct. Let's say we have:

arr.push(1, 2, 3);

We'll add MArrayPush(1), MArrayPush(2), MArrayPush(3). Now let's say the Ion code is invalidated after MArrayPush(2) (this can happen if the array goes from dense to sparse for instance), then we'll resume in the Baseline JIT *after* arr.push(1, 2, 3), but we won't push "3" in that case...

I think you'd need a single MIR instruction for this to work, one that can take more than 1 value. Do you have a real benchmark where this is a problem? If not it's probably not worth the complexity...

Comment 3

[Masaya Iseki[:isk](UTC+9)]

Attachment: Bug966743.patch

(In reply to Jan de Mooij [:jandem] from comment #2)

Thank you for your reviewing.

> Comment on attachment 8369184 [details] [diff] [review]
> Bug966743.patch
> 
> Review of attachment 8369184 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: js/src/jit/MCallOptimize.cpp
> @@ +425,5 @@
> > +                return InliningStatus_NotInlined;
> > +        }
> > +
> > +        current->push(ins);
> > +        if (!resumeAfter(ins))
> 
> Unfortunately this is not correct. Let's say we have:
> 
> arr.push(1, 2, 3);
> 
> We'll add MArrayPush(1), MArrayPush(2), MArrayPush(3). Now let's say the Ion
> code is invalidated after MArrayPush(2) (this can happen if the array goes
> from dense to sparse for instance), then we'll resume in the Baseline JIT
> *after* arr.push(1, 2, 3), but we won't push "3" in that case...

It is because to return not making MArrayPush(3), right?
If so, I think it can avoid to make MIR every MArrayPush.

> I think you'd need a single MIR instruction for this to work, one that can
> take more than 1 value. Do you have a real benchmark where this is a
> problem? If not it's probably not worth the complexity...

I don't have a real benchmark.

Comment 4

[Masaya Iseki[:isk](UTC+9)]

Attachment: Bug966743.patch

(In reply to Jan de Mooij [:jandem] from comment #2)

Thank you for your reviewing.

> Comment on attachment 8369184 [details] [diff] [review]
> Bug966743.patch
> 
> Review of attachment 8369184 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: js/src/jit/MCallOptimize.cpp
> @@ +425,5 @@
> > +                return InliningStatus_NotInlined;
> > +        }
> > +
> > +        current->push(ins);
> > +        if (!resumeAfter(ins))
> 
> Unfortunately this is not correct. Let's say we have:
> 
> arr.push(1, 2, 3);
> 
> We'll add MArrayPush(1), MArrayPush(2), MArrayPush(3). Now let's say the Ion
> code is invalidated after MArrayPush(2) (this can happen if the array goes
> from dense to sparse for instance), then we'll resume in the Baseline JIT
> *after* arr.push(1, 2, 3), but we won't push "3" in that case...

It is because to return not making MArrayPush(3), right?
If so, I think it can avoid to make MIR every MArrayPush.

> I think you'd need a single MIR instruction for this to work, one that can
> take more than 1 value. Do you have a real benchmark where this is a
> problem? If not it's probably not worth the complexity...

I don't have a real benchmark.

Comment 5

[Jan de Mooij [:jandem]]

Comment on attachment 8378134 [details] [diff] [review]
Bug966743.patch

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

::: js/src/jit/MCallOptimize.cpp
@@ +426,5 @@
> +            if (!current->increaseSlots(depth - current->nslots()))
> +                status = InliningStatus_NotInlined;
> +        }
> +        current->push(ins);
> +        if (!resumeAfter(ins))

This doesn't work; you can't add multiple effectful MIR instructions for a single bytecode operations like this JSOP_CALL. The problem is that we can bailout to our Baseline JIT in the middle of these operations and then we will resume after the bytecode op and not execute the other push operations.

You'd have to guarantee bailout/invalidation is not possible for these MArrayPush instructions, but that's hard: as I mentioned in comment 2, push operations may make the array sparse and hence trigger an invalidation bailout.

Comment 6

[Masaya Iseki[:isk](UTC+9)]

I have misunderstood.

I thought the means of "Ion code is invalidated" is that |inlineArrayPush| return "InliningStatus_NotInlined" or "InliningStatus_Error". But this means is "bailout" or "On Stack Invalidation",right?

> Unfortunately this is not correct. Let's say we have:
> 
> arr.push(1, 2, 3);
> 
> We'll add MArrayPush(1), MArrayPush(2), MArrayPush(3). Now let's say the Ion
> code is invalidated after MArrayPush(2) (this can happen if the array goes
> from dense to sparse for instance), then we'll resume in the Baseline JIT
> *after* arr.push(1, 2, 3), but we won't push "3" in that case...

I can't still understand about this part.
This patch add MResumePoint by |resumeAfter| each MArrayPush. So If Ion code is invalidated after MArrayPush(2), we'll resume after MArrayPush(2). I can't understand why resume after arr.push(1, 2, 3).

Comment 7

[Nicolas B. Pierron [:nbp]]

As Jan described it, by translating  `arr.push(1,2,3)`  into  

  arr.push(1)
  arr.push(2)  // --> bailout here
  arr.push(3)

There is not code to go back to if the Ion generated code does not handle all cases.  Which implies that we would have [1,2] or [1,2,1,2,3] depending where you resume the execution.

To handle that properly today, you would have to resume before, but with recover instruction to unwind the changes made to the array.

Comment 8

[Nicolas B. Pierron [:nbp]]

I will take over this optimization, as this seems to be blocking Speedometer, and there is no activity on this bug since many years.

Comment 9

[Nicolas B. Pierron [:nbp]]

Attachment: Inline Array.prototype.push with more than one argument.

This patch inline Array.prototype.push, even if more than 1 argument is
provided.  It uses MArrayPush instruction, in order to push each element
individually.

This patch works, by recording the original length, and attach a
MSetArrayLength instruction on all MArrayPush's resume points to unwind and
truncate the array in case of failure.

The test case is verified to work, but as we have no proper way of recording
which failure path got taken, I went to spam the bailouts a bit, which
basically hit each of the 10 MarrayPush 3 times. (This actually caught one
issue, about dealing with the last MarrayPush instruction, which should also
resume before)

Comment 10

[Nicolas B. Pierron [:nbp]]

(In reply to Nicolas B. Pierron [:nbp] from comment #9)
> Created attachment 8899891 [details] [diff] [review]
> Inline Array.prototype.push with more than one argument.

On the benchmark provided in comment 0, which sequences of pushes with 3 arguments:
  before: 1023.988 ms
  after:  280.867 ms

Comment 11

[Jan de Mooij [:jandem]]

Comment on attachment 8899891 [details] [diff] [review]
Inline Array.prototype.push with more than one argument.

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

It will be great to have this fixed, but some questions below.

::: js/src/jit-test/tests/ion/array-push-multiple.js
@@ +21,5 @@
> +}
> +
> +if (!("oomAtAllocation" in this))
> +  quit();
> +if (canIoncompile() != true)

Why shouldn't we run this test with --no-ion? Often tests that were originally for Ion bugs/features find issues when working on other parts of the code.

::: js/src/jit/MCallOptimize.cpp
@@ +787,5 @@
>  
>  IonBuilder::InliningResult
>  IonBuilder::inlineArrayPush(CallInfo& callInfo)
>  {
> +    if (callInfo.argc() < 1 || callInfo.constructing()) {

We should cap this to a reasonable length, let's say 5 or so? To avoid spending a lot of time in PropertyWriteNeedsTypeBarrier and the other code below and in the rest of the compiler if someone does array.push(...list of generated arguments...)

::: js/src/jit/MIR.h
@@ +9102,4 @@
>    public:
>      INSTRUCTION_HEADER(SetArrayLength)
>      TRIVIAL_NEW_WRAPPERS
>      NAMED_OPERANDS((0, elements), (1, index))

Rename this to objectOrElements maybe?

::: js/src/jit/Recover.cpp
@@ +1710,5 @@
> +    RootedValue len(cx, iter.read());
> +
> +    RootedId id(cx, NameToId(cx->names().length));
> +    ObjectOpResult error;
> +    if (!ArraySetLength(cx, obj, id, JSPROP_PERMANENT, len, error))

What happens when the array has a non-writable length or frozen elements?

Non-writable length you can get with something like this:

  Object.defineProperty(arr, "length", {writable: false, value: 5});

Will this throw an exception in ArrayPushDense and then also here? We should have some tests for this.

Comment 12

[Nicolas B. Pierron [:nbp]]

(In reply to Jan de Mooij [:jandem] from comment #11)
> ::: js/src/jit-test/tests/ion/array-push-multiple.js
> @@ +21,5 @@
> > +}
> > +
> > +if (!("oomAtAllocation" in this))
> > +  quit();
> > +if (canIoncompile() != true)
> 
> Why shouldn't we run this test with --no-ion? Often tests that were
> originally for Ion bugs/features find issues when working on other parts of
> the code.

Because the test case checks that we are first inIon, and then checks for a bailout by ensuring that we are no longer inIon.

> ::: js/src/jit/MCallOptimize.cpp
> @@ +787,5 @@
> >  
> >  IonBuilder::InliningResult
> >  IonBuilder::inlineArrayPush(CallInfo& callInfo)
> >  {
> > +    if (callInfo.argc() < 1 || callInfo.constructing()) {
> 
> We should cap this to a reasonable length, let's say 5 or so? To avoid
> spending a lot of time in PropertyWriteNeedsTypeBarrier and the other code
> below and in the rest of the compiler if someone does array.push(...list of
> generated arguments...)

I agree, I should probably benchmark the cliff between inlining this for various length.

> ::: js/src/jit/Recover.cpp
> @@ +1710,5 @@
> > +    RootedValue len(cx, iter.read());
> > +
> > +    RootedId id(cx, NameToId(cx->names().length));
> > +    ObjectOpResult error;
> > +    if (!ArraySetLength(cx, obj, id, JSPROP_PERMANENT, len, error))
> 
> What happens when the array has a non-writable length or frozen elements?
> 
> […]
> 
> Will this throw an exception in ArrayPushDense and then also here? We should
> have some tests for this.

ObjectOpResult is ignored, and (if I am not making any mistake while reading the code) the frozen length manipulation should be reported in the ObjectOpResult.

Thus, if the length is frozen, the generated array push fails, then the recover instruction does nothing and inhibit the error, and baseline should throw the error.

I will note that the array cannot be frozen while we are in the middle of the sequence of ArrayPush, as all these instructions are effectful, and setting the array as frozen is also effectful.  Thus it cannot be moved in-between 2 ArrayPush from the same sequence.

Comment 13

[Nicolas B. Pierron [:nbp]]

(In reply to Jan de Mooij [:jandem] from comment #11)
> What happens when the array has a non-writable length or frozen elements?
> 
> Non-writable length you can get with something like this:
> 
>   Object.defineProperty(arr, "length", {writable: false, value: 5});
> 
> Will this throw an exception in ArrayPushDense and then also here? We should
> have some tests for this.

I just tested locally and this works fine, but I cannot make this a formal test case because test ends with an unhandled OOM issue.

Comment 14

[Jan de Mooij [:jandem]]

(In reply to Nicolas B. Pierron [:nbp] from comment #13)
> I just tested locally and this works fine, but I cannot make this a formal
> test case because test ends with an unhandled OOM issue.

You could add this to the test:

  // |jit-test| allow-unhandlable-oom

Comment 15

[Jan de Mooij [:jandem]]

Comment on attachment 8899891 [details] [diff] [review]
Inline Array.prototype.push with more than one argument.

Clearing r? for now :)

Comment 16

[Nicolas B. Pierron [:nbp]]

Attachment: Inline Array.prototype.push with more than one argument.

Delta:
 - Add a limit to the number of arguments (10) that are inlined with the
   Array.prototype.push function.  Note, there is probably room for
   optimization because the sequence of push is 2x faster than the push
   function for larger number of arguments, such as 200.

Comment 17

[Nicolas B. Pierron [:nbp]]

Attachment: Inline Array.prototype.push with more than one argument.

Delta:
 - Add a test case for frozen arrays case. (non writable length)

Comment 18

[Jan de Mooij [:jandem]]

Comment on attachment 8904250 [details] [diff] [review]
Inline Array.prototype.push with more than one argument.

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

Thanks! limit of 10 sounds good to me.

Comment 19

[Nicolas B. Pierron [:nbp]]

checkin-needed: https://treeherder.mozilla.org/#/jobs?repo=try&revision=d5fe40bd607f62a6294aa419dd168821b9beb395

Comment 20

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/8b1881ead0b6
Inline Array.prototype.push with more than one argument. r=jandem

Comment 21

[Sebastian Hengst [:aryx] (needinfo me if it's about an intermittent or backout)]

https://hg.mozilla.org/mozilla-central/rev/8b1881ead0b6