Closed Bug 1235092 Opened 4 years ago Closed 4 years ago

Can we optimize spread call with rest parameter?

Categories

(Core :: JavaScript Engine, defect)

defect
Not set

Tracking

()

RESOLVED FIXED
mozilla46
Tracking Status
firefox46 --- fixed

People

(Reporter: arai, Assigned: arai)

Details

Attachments

(3 files, 1 obsolete file)

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.
one more condition due to spread call operation:
  * the array has no hole

that means we should check all elements of the argument.
Attached image Performance comparison (obsolete) —
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
Assignee: nobody → arai.unmht
Attached image 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
Attachment #8701877 - Attachment is obsolete: true
Here's a patch for comment #3.
Attachment #8703243 - Flags: review?(efaustbmo)
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.
Attachment #8703760 - Flags: review?(efaustbmo)
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?
Flags: needinfo?(arai.unmht)
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.
Flags: needinfo?(arai.unmht)
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 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.
Attachment #8703243 - Flags: review?(efaustbmo) → review+
Attachment #8703760 - Flags: review?(efaustbmo) → review+
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
https://hg.mozilla.org/integration/mozilla-inbound/rev/068ab119a0f781ba85e34ec25e55efde1ca733ec
Bug 1235092 - Part 3: Root function in BytecodeEmitter::isRestParameter. r=bustage
You need to log in before you can comment on or make changes to this bug.