IonMonkey: Modify MArrayPush to accept multiple arguments

RESOLVED FIXED in Firefox 57

Status

()

Core
JavaScript Engine: JIT
P5
enhancement
RESOLVED FIXED
4 years ago
3 months ago

People

(Reporter: isk, Assigned: nbp)

Tracking

({perf})

Trunk
mozilla57
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(firefox57 fixed)

Details

Attachments

(2 attachments, 5 obsolete attachments)

(Reporter)

Description

4 years ago
Created attachment 8369179 [details]
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
(Reporter)

Comment 1

4 years ago
Created attachment 8369184 [details] [diff] [review]
Bug966743.patch

I make patch.
The result of this patch is in before comment.
Attachment #8369184 - Flags: review?(jdemooij)
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...
Attachment #8369184 - Flags: review?(jdemooij)
(Reporter)

Comment 3

4 years ago
Created attachment 8378132 [details] [diff] [review]
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.
Attachment #8369184 - Attachment is obsolete: true
Attachment #8378132 - Flags: review?(jdemooij)
(Reporter)

Comment 4

4 years ago
Created attachment 8378134 [details] [diff] [review]
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.
Attachment #8378134 - Flags: review?(jdemooij)
(Reporter)

Updated

4 years ago
Attachment #8378132 - Flags: review?(jdemooij)
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.
Attachment #8378134 - Flags: review?(jdemooij)
(Reporter)

Comment 6

4 years ago
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).
(Assignee)

Comment 7

a year ago
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.
Keywords: perf
Priority: -- → P5

Updated

7 months ago
Blocks: 1386001
(Assignee)

Comment 8

6 months ago
I will take over this optimization, as this seems to be blocking Speedometer, and there is no activity on this bug since many years.
Assignee: iseki.m.aa → nicolas.b.pierron
Status: NEW → ASSIGNED
(Assignee)

Comment 9

6 months ago
Created attachment 8899891 [details] [diff] [review]
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)
Attachment #8899891 - Flags: review?(jdemooij)
(Assignee)

Updated

6 months ago
Attachment #8378132 - Attachment is obsolete: true
Attachment #8378134 - Attachment is obsolete: true
(Assignee)

Comment 10

6 months ago
(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 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.
(Assignee)

Comment 12

6 months ago
(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.
(Assignee)

Comment 13

6 months ago
(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.
(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 on attachment 8899891 [details] [diff] [review]
Inline Array.prototype.push with more than one argument.

Clearing r? for now :)
Attachment #8899891 - Flags: review?(jdemooij)
(Assignee)

Comment 16

6 months ago
Created attachment 8904236 [details] [diff] [review]
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.
Attachment #8904236 - Flags: review?(jdemooij)
(Assignee)

Updated

6 months ago
Attachment #8899891 - Attachment is obsolete: true
(Assignee)

Comment 17

6 months ago
Created attachment 8904250 [details] [diff] [review]
Inline Array.prototype.push with more than one argument.

Delta:
 - Add a test case for frozen arrays case. (non writable length)
Attachment #8904250 - Flags: review?(jdemooij)
(Assignee)

Updated

6 months ago
Attachment #8904236 - Attachment is obsolete: true
Attachment #8904236 - Flags: review?(jdemooij)
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.
Attachment #8904250 - Flags: review?(jdemooij) → review+
(Assignee)

Updated

6 months ago
Keywords: checkin-needed
(Assignee)

Updated

6 months ago
Keywords: checkin-needed

Comment 20

6 months ago
Pushed by npierron@mozilla.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/8b1881ead0b6
Inline Array.prototype.push with more than one argument. r=jandem
https://hg.mozilla.org/mozilla-central/rev/8b1881ead0b6
Status: ASSIGNED → RESOLVED
Last Resolved: 6 months ago
status-firefox57: --- → fixed
Resolution: --- → FIXED
Target Milestone: --- → mozilla57
(Assignee)

Updated

5 months ago
Depends on: 1398105
Depends on: 1412653
(Assignee)

Updated

3 months ago
Duplicate of this bug: 1386001
You need to log in before you can comment on or make changes to this bug.