1014813 - Holes before spread operator are ignored if nothing is spreaded.

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect)

Description

[Tooru Fujisawa [:arai]]

User Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.9; rv:30.0) Gecko/20100101 Firefox/30.0 (Beta/Release)
Build ID: 20140520115057

Steps to reproduce:

1. run Nightly 2014-05-22 with clean profile
2. open Web Console
3. evaluate following code:
  [...[1, 2, 3], , , , ...[]]



Actual results:

Output is following:
>  Array [ 1, 2, 3 ]




Expected results:

Output should be following:
>  Array [ 1, 2, 3, , ,  ]

This problem exists from Firefox 16, both in Interpreter and Baseline execution.

SetLengthProperty is called only if JSOP_INITELEM_INC is the last element.
  http://dxr.mozilla.org/mozilla-central/source/js/src/vm/Interpreter-inl.h#495
But in this case, last element is spread, and it does not update the length if nothing is spreaded.
So array length stays the value of |min(initial length, length without trailing holes)|,
here initial length is the number of non-spread elements.

Comment 1

[Tooru Fujisawa [:arai]]

Possible solutions are following:

1. emit JSOP_SETPROP "length" or something instead of JSOP_POP (which pops index) before JSOP_ENDINIT,
   if array has hole and it is last non-spread element.
2. update array length in SpreadOperation if nothing is spreaded

How do you think?

Comment 2

[Tooru Fujisawa [:arai]]

Oops, sorry, expected result should be following:
>  Array [ 1, 2, 3, , , , ]

Comment 3

[Tooru Fujisawa [:arai]]

> So array length stays the value of |min(initial length, length without trailing holes)|,
one more mistake, it's |max(initial length, length without trailing holes)|.

Comment 4

[Tooru Fujisawa [:arai]]

I got second thoughts.

The problem is caused by optimization inside VM, and it's not a problem of bytecode itself.
so it should be fixed in VM's side (thus solution 1 in comment 1 is wrong approach).

Simplest solution will be de-optimizing InitArrayElemOperation for JSOP_INITELEM_INC with hole,
and always call SetLengthProperty.

Comment 5

[Jan de Mooij [:jandem]]

Nice find!

Doing this in the VM feels like the right approach to me too. Does that fix the problem?

Comment 6

[Tooru Fujisawa [:arai]]

Attachment: Always set array length in JSOP_INITELEM_INC with hole.

Thanks!
Yes, de-optimizing InitArrayElemOperation fixes the problem.
Following test is passed when I apply this patch.
> assertEqArray([...[1, 2, 3],,,,...[]], [1,2,3,,,,]);

Hole inside spread-array is much rarer case than spreading empty iterable
(I cannot find actual case of "hole inside spread-array" in mozilla-central tree,
except for test case of spread-array and reflect-parse).
So de-optimizing InitArrayElemOperation will have less impact on entire performance
than checking the number of spreaded items in SpreadOperation every time.
Besides, it's more straightforward solution.

jstests and jit-test(--tbpl) are passed on Mac OS X 10.9.3 64bit.

Comment 7

[Tooru Fujisawa [:arai]]

Attachment: (just for test) Set array length if nothing is spreaded.

Just for performance comparison.

This patch checks the number of spreaded items and call SetLengthProperty if it's 0.
This patch also fixed the problem, but former patch may be better.

Comment 8

[Tooru Fujisawa [:arai]]

Attachment: Performance comparison

Here is performance comparison.

patch A is "Always set array length in JSOP_INITELEM_INC with hole" patch (attachment 8431308 [details] [diff] [review]).
patch B is "Set array length if nothing is spreaded." patch (attachment 8431309 [details] [diff] [review]).

[JSOP_INITELEM_INC with hole]
  Code:
    let a = []; let s = elapsed(); for (let i = 0; i < 200000; i ++) [...a] print(elapsed() - s);
    let a = []; let s = elapsed(); for (let i = 0; i < 200000; i ++) [, ...a] print(elapsed() - s);
    let a = []; let s = elapsed(); for (let i = 0; i < 200000; i ++) [,, ...a] print(elapsed() - s);
    ...
  Result:
    Single JSOP_INITELEM_INC in patch A is 3~11 times slower than original one.
    (however, this is rare case, as I noted above :)

[JSOP_INITELEM_INC with non-hole]
  Code:
    let a = []; let s = elapsed(); for (let i = 0; i < 200000; i ++) [...a] print(elapsed() - s);
    let a = []; let s = elapsed(); for (let i = 0; i < 200000; i ++) [1, ...a] print(elapsed() - s);
    let a = []; let s = elapsed(); for (let i = 0; i < 200000; i ++) [1, 2, ...a] print(elapsed() - s);
    ...
  Result:
    No notable performance changes.
    (There are regression in patch B, but it's caused by JSOP_SPREAD, not JSOP_INITELEM_INC)

[JSOP_SPREAD with empty array]
  Code:
    let a = []; let s = elapsed(); for (let i = 0; i < 200000; i ++) [...a] print(elapsed() - s);
    let a = []; let s = elapsed(); for (let i = 0; i < 200000; i ++) [...a, ...a] print(elapsed() - s);
    let a = []; let s = elapsed(); for (let i = 0; i < 200000; i ++) [...a, ...a, ...a] print(elapsed() - s);
    ...
  Result:
    Single JSOP_SPREAD in patch B is 2x slower than original one.

[JSOP_SPREAD with non-empty array]
  Code:
    let a = [1]; let s = elapsed(); for (let i = 0; i < 200000; i ++) [...a] print(elapsed() - s);
    let a = [1]; let s = elapsed(); for (let i = 0; i < 200000; i ++) [...a, ...a] print(elapsed() - s);
    let a = [1]; let s = elapsed(); for (let i = 0; i < 200000; i ++) [...a, ...a, ...a] print(elapsed() - s);
    ...
  Result:
    No notable performance changes.

Comment 9

[Jan de Mooij [:jandem]]

Comment on attachment 8431308 [details] [diff] [review]
Always set array length in JSOP_INITELEM_INC with hole.

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

Nice work, just some minor comment nits. If you can post an updated patch I'll push it to Try (with your other patch in bug 923028).

Do you have access to the Try server? If you want to contribute more patches you should consider requesting it so that you can do this yourself :)

See http://www.mozilla.org/hacking/committer/ or ask on IRC for more info.

::: js/src/vm/Interpreter-inl.h
@@ +486,5 @@
> +     * JSObject::defineElement. In this case, if it is the last element
> +     * initialiser, set the array length to one greater than id.
> +     *
> +     * If val is a hole and current op is JSOP_INITELEM_INC, always call
> +     * JSObject::defineElement even if it is not the last element initialiser,

Nit: s/JSObject::defineElement/SetLengthProperty

@@ +487,5 @@
> +     * initialiser, set the array length to one greater than id.
> +     *
> +     * If val is a hole and current op is JSOP_INITELEM_INC, always call
> +     * JSObject::defineElement even if it is not the last element initialiser,
> +     * because JSOP_SPREAD will not set the array length if nothing is spreaded.

Nit: ...because it may be followed by JSOP_SPREAD, which will not set the array length if nothing is spreaded.

Comment 10

[Tooru Fujisawa [:arai]]

Attachment: Always set array length in JSOP_INITELEM_INC with hole.

Thank you again!

> Do you have access to the Try server? If you want to contribute more patches
> you should consider requesting it so that you can do this yourself :)
> 
> See http://www.mozilla.org/hacking/committer/ or ask on IRC for more info.

I'll follow the instructions, thanks!

> ::: js/src/vm/Interpreter-inl.h
> @@ +486,5 @@
> > +     * JSObject::defineElement. In this case, if it is the last element
> > +     * initialiser, set the array length to one greater than id.
> > +     *
> > +     * If val is a hole and current op is JSOP_INITELEM_INC, always call
> > +     * JSObject::defineElement even if it is not the last element initialiser,
> 
> Nit: s/JSObject::defineElement/SetLengthProperty

Oops, I totally misread the original comment.
Changes to first paragprah should be reverted.

Comment 11

[Jan de Mooij [:jandem]]

Comment on attachment 8431516 [details] [diff] [review]
Always set array length in JSOP_INITELEM_INC with hole.

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

Perfect, thanks. I'll send your two patches to Try now.

Comment 12

[Jan de Mooij [:jandem]]

https://tbpl.mozilla.org/?tree=Try&rev=6f2067b4d7b5

Comment 13

[Jan de Mooij [:jandem]]

Try was green so:

https://hg.mozilla.org/integration/mozilla-inbound/rev/dae53a38052e

Thanks for fixing this!

Comment 14

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/dae53a38052e

Comment 15

[alan2loin]

[bugday-20140820]
I reproduced the bug with the Nightly 22-05-2014 version
The fix is verified with the Nightly 20-08-2014 version
Actual result :
Array [ 1, 2, 3, <3 empty slots> ]

Comment 16

[Andrei Vaida [:avaida]]

This is now verified fixed based on Comment 15. I also managed to confirm the fix on Nightly 34.0a1 (2014-08-20) using Windows 7 64-bit.

Comment 17

[alan2loin]

Verification made on Windows 7 64-bits
Firefox Nightly 20-08-2014 win32 version