1235092 - Can we optimize spread call with rest parameter?

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Tooru Fujisawa [:arai]]

Currently spread call creates new array regardless of arguments, but following case should be common, and in that case we could use |rest| array directly, instead of cloning it.

  function f(...rest) {
    g(...rest);
  }

There are some restriction to do so.
  * the array should not have modified @@iterator
  * the array's prototype should be Array.prototype
  * Array.prototype[@@iterator] should not be modified
  * %ArrayIteratorPrototype%.next should not be modified

those condition are already used in ForOfPIC, so we could re-use it.

anyway, above conditions could be changed on runtime, so we cannot optimize the spread operation away when generating bytecodes.  We might need an extra bytecode to check those conditions.

Comment 1

[Tooru Fujisawa [:arai]]

one more condition due to spread call operation:
  * the array has no hole

that means we should check all elements of the argument.

Comment 2

[Tooru Fujisawa [:arai]]

Attachment: Performance comparison

Here's rough plan:

When following conditions are met, emit bytecodes for optimization:
  * there is only one argument in spread call
  * spread operand is a PNK_NAME node
  * there is no enclosing with scope
Those mean accessing the variable has no side-effect.
If those are not met, this patch does nothing.

Bytecodes for optimization are following:
  JSOP_GETARG 0  (or similar thing for PNK_NAME node)
  JSOP_OPTIMIZE_SPREADCALL
  JSOP_IFNE [END]
  JSOP_POP

  <spread the argument here>

  [END]:
  JSOP_SPREADCALL

So, before spreading argument, check if the argument can be optimized, and if so, jump to JSOP_SPREADCALL without doing spread operation.

JSOP_OPTIMIZE_SPREADCALL checks the top stack value and pushes a boolean value that indicates the top stack value satisfies following conditions:
  * the value is an array
  * the array has no hole
  * array[@@iterator] is not modified
  * the array's prototype is Array.prototype
  * Array.prototype[@@iterator] is not modified
  * %ArrayIteratorPrototype%.next is not modified


Attached performance comparison for optimizable cases and not-optimizable-but-affected cases.
For optimizable cases (first 6 cases), it's 2x or more faster.
other 2 cases meet the conditions for emitting bytecode, but they're not optimizable.  There are up to 10% performance regression due to additional bytecodes.

Maybe we should apply this optimization only when the PNK_NAME is rest parameter?


try is running: https://treeherder.mozilla.org/#/jobs?repo=try&revision=a20442c2fe73

Comment 3

[Tooru Fujisawa [:arai]]

Attachment: Performance comparison

Changed conditions for emitting bytecode to following:
  * there is only one argument in spread call
  * spread operand is rest parameter

no other changes.

So, now not-optimizable-but-affected case means that rest parameter is somehow modified (assigned another thing, or the array is modified)
In the attached graph, it still shows up to 10% performance regression in those cases, but they should be negligible.

https://treeherder.mozilla.org/#/jobs?repo=try&revision=7318ea432388

Comment 4

[Tooru Fujisawa [:arai]]

Attachment: Optimize spread call with rest parameter.

Here's a patch for comment #3.

Comment 5

[Tooru Fujisawa [:arai]]

Attachment: Part 2: Support allowContentSpread in the optimization for spread call with rest parameter.

This will be needed for default derived ctor in bug 1234702, as the spread operand is not directly rest parameter, but enclosed by allowContentSpread call.

Comment 6

[Boris Zbarsky [:bzbarsky]]

Do we create this array object ourselves?  If so, why do we need to check that "array[@@iterator] is not modified" or that there are no holes?

If we did NOT create this array object ourselves, then we have other problems like accessor props whose getter invalidates our assumptions, right?

Comment 7

[Tooru Fujisawa [:arai]]

We create the rest parameter array and the array itself has no problem at the beginning of the function.
The problems are following:

1. Rest parameter's array can be modified:

  function f1(...args) {
    args.length = 10;
    g(...args);
  }
  function f2(...args) {
    args[Symbol.iterator] = function*(){ yield 10; };
    g(...args);
  }

or, generally:

  function f3(...args) {
    some_function_that_modifies_array(args);
    g(...args);
  }


2. Rest parameter's slot can be overwritten:

  function f4(...args) {
    args = [1, ,,, 2];
    g(...args);
  }


So, we should detect those cases and avoid optimizing spread operation out then.

maybe, we could skip some checks when the access to the rest parameter is literally first one (or only one) in the function.
not sure if it worth doing so tho.

Comment 8

[Boris Zbarsky [:bzbarsky]]

Ah, right, someone else can touch the array.  If so, you really need to either make sure that it only has dense elements or do something else to handle the accessor property issue.

I _think_ that's the only way things can go bad, since we never claim we can optimize in tryOptimizeArray if Array.prototype[Symbol.iterator] is not a slotful property or if ArrayIterator.prototype.next is not a slotful property.

Comment 9

[Eric Faust [:efaust]]

Comment on attachment 8703243 [details] [diff] [review]
Optimize spread call with rest parameter.

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

This looks great. Thanks for being patient while I worked through all the gotchas :)

::: js/src/vm/Interpreter.cpp
@@ +4629,5 @@
> +    }
> +
> +    for (uint32_t i = 0; i < length; i++) {
> +        if (aobj->getDenseElement(i).isMagic()) {
> +            *optimized = false;

As discussed on IRC, we can avoid this loop via the check for the "packed" attribute. See the IsPackedArray intrinsic for help. Perhaps a refactor.

Comment 10

[Tooru Fujisawa [:arai]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/33600326da21be6564e6ee4e9b0394a48891d645
Bug 1235092 - Part 1: Optimize spread call with rest parameter. r=efaust

https://hg.mozilla.org/integration/mozilla-inbound/rev/cb21170160235213bfc831886b033e296f07951a
Bug 1235092 - Part 2: Support allowContentSpread in the optimization for spread call with rest parameter. r=efaust

Comment 11

[Tooru Fujisawa [:arai]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/068ab119a0f781ba85e34ec25e55efde1ca733ec
Bug 1235092 - Part 3: Root function in BytecodeEmitter::isRestParameter. r=bustage

Comment 12

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/33600326da21
https://hg.mozilla.org/mozilla-central/rev/cb2117016023
https://hg.mozilla.org/mozilla-central/rev/068ab119a0f7