New issue
Advanced search Search tips
Note: Color blocks (like or ) mean that a user may not be available. Tooltip shows the reason.
Starred by 23 users

Issue metadata

Status: Assigned
Owner:
Last visit > 30 days ago
Cc:
Components:
HW: All
NextAction: ----
OS: All
Priority: 2
Type: FeatureRequest

Blocked on:
issue chromium:167529
issue 6808

Blocking:
issue 5267
issue 6019
issue 4869



Sign in to add a comment
link

Issue 2229: Inline array builtins

Reported by ilmari@google.com, Jul 11 2012 Project Member

Issue description

Relevant design document: https://docs.google.com/document/d/1rvLINa8IX3MhubFxdUKYie4ZeEoDF63NkI278XCeHKE

Could methods like

var res = array.map(function(x) { return x * 2; });

be inlined to

var _res = [];
for (var _i = 0; _i < array.length ; _i++) {
  _res[_i] = array[_i] * 2;
}
var res = _res;

?
 

Comment 1 by dslomov@chromium.org, Nov 4 2014

Labels: Type-FeatureRequest Priority-Medium
Owner: dslomov@chromium.org

Comment 2 by hablich@chromium.org, Apr 30 2015

Labels: -Priority-Medium Priority-Low Area-Compiler
Status: Available

Comment 3 by adamk@chromium.org, Jul 17 2015

Owner: ----

Comment 4 by jkummerow@chromium.org, May 25 2016

Cc: cbruni@chromium.org
 Issue 4878  has been merged into this issue.

Comment 5 by jkummerow@chromium.org, May 25 2016

Blocking: 4869

Comment 6 by jkummerow@chromium.org, May 25 2016

 Issue 5041  has been merged into this issue.

Comment 7 by l...@chromium.org, May 25 2016

Cc: l...@chromium.org

Comment 8 by bmeu...@chromium.org, May 27 2016

Labels: Performance TurboFan HelpWanted HW-All OS-All
Owner: bmeu...@chromium.org
TurboFan can do that, the JSCallReducer already does similar things for Function.prototype.call/apply. For the Array builtins, the most difficult thing is the deoptimization story.

For the particular case of Array.prototype.map: Assuming that we know the map of the array, we need to do a map check initially and then load the length, which can use the eager frame state before the builtin call. But then every loop iteration has to have a frame state at the beginning of the loop and right after the call to the user supplied function, so when something causes a deopt we have to continue somewhere in the middle. I think we can model that as magic frame state that calls into a C++ builtin, passing the current index in addition to the rest.

Comment 9 by bmeu...@chromium.org, Aug 5 2016

Blocking: 5267
Status: Assigned (was: Available)

Comment 10 by bugdroid1@chromium.org, Aug 11 2016

Project Member
The following revision refers to this bug:
  https://chromium.googlesource.com/v8/v8.git/+/b8f475045c27536e2666a55d826c556ce4cdbb3e

commit b8f475045c27536e2666a55d826c556ce4cdbb3e
Author: bmeurer <bmeurer@chromium.org>
Date: Thu Aug 11 13:13:05 2016

[turbofan] Add inlined Array.prototype.pop support.

This adds a very first version of inlined Array.prototype.pop into
TurboFan optimized code. We currently limit the inlining to fast
object or smi elements, until the unclear situation around hole NaNs
is resolved and we have a clear semantics inside the compiler.

It's also probably overly defensive in when it's safe to inline
the call to Array.prototype.pop, but we can always extend that
later once we have sufficient trust in the implementation and see
an actual need to extend it.

BUG=v8:2229, v8:3952 ,v8:5267
R=epertoso@chromium.org

Review-Url: https://codereview.chromium.org/2239703002
Cr-Commit-Position: refs/heads/master@{#38578}

[modify] https://crrev.com/b8f475045c27536e2666a55d826c556ce4cdbb3e/src/compiler/access-builder.cc
[modify] https://crrev.com/b8f475045c27536e2666a55d826c556ce4cdbb3e/src/compiler/access-builder.h
[modify] https://crrev.com/b8f475045c27536e2666a55d826c556ce4cdbb3e/src/compiler/js-builtin-reducer.cc
[modify] https://crrev.com/b8f475045c27536e2666a55d826c556ce4cdbb3e/src/compiler/js-builtin-reducer.h
[modify] https://crrev.com/b8f475045c27536e2666a55d826c556ce4cdbb3e/src/compiler/pipeline.cc
[modify] https://crrev.com/b8f475045c27536e2666a55d826c556ce4cdbb3e/src/type-cache.h
[add] https://crrev.com/b8f475045c27536e2666a55d826c556ce4cdbb3e/test/mjsunit/compiler/inlined-array-pop-getter1.js
[add] https://crrev.com/b8f475045c27536e2666a55d826c556ce4cdbb3e/test/mjsunit/compiler/inlined-array-pop-getter2.js
[add] https://crrev.com/b8f475045c27536e2666a55d826c556ce4cdbb3e/test/mjsunit/compiler/inlined-array-pop-opt.js
[modify] https://crrev.com/b8f475045c27536e2666a55d826c556ce4cdbb3e/test/unittests/compiler/js-builtin-reducer-unittest.cc

Comment 11 by bugdroid1@chromium.org, Aug 12 2016

Project Member
The following revision refers to this bug:
  https://chromium.googlesource.com/v8/v8.git/+/50f223e47eafdf4fccc0108b03affca9e3d892b1

commit 50f223e47eafdf4fccc0108b03affca9e3d892b1
Author: bmeurer <bmeurer@chromium.org>
Date: Fri Aug 12 08:59:20 2016

[turbofan] Add inlined Array.prototype.push support.

This adds a very first version of inlined Array.prototype.push into
TurboFan optimized code. The current inlined version has a potential
deopt loop, but it's unlikely that we hit it currently (Crankshaft
suffers from an even worse problem). Once we have a way to learn from
deopts we can fix this deopt loops.

It's also probably overly defensive in when it's safe to inline
the call to Array.prototype.push, but we can always extend that
later once we have sufficient trust in the implementation and see
an actual need to extend it.

BUG=v8:2229, v8:3952 ,v8:5267
R=jarin@chromium.org

Review-Url: https://codereview.chromium.org/2245533003
Cr-Commit-Position: refs/heads/master@{#38603}

[modify] https://crrev.com/50f223e47eafdf4fccc0108b03affca9e3d892b1/src/compiler/access-builder.cc
[modify] https://crrev.com/50f223e47eafdf4fccc0108b03affca9e3d892b1/src/compiler/js-builtin-reducer.cc
[modify] https://crrev.com/50f223e47eafdf4fccc0108b03affca9e3d892b1/src/compiler/js-builtin-reducer.h

Comment 12 by bmeu...@chromium.org, Aug 16 2016

Blockedon: chromium:167529

Comment 13 by bmeu...@chromium.org, Feb 28 2017

Blocking: 6019

Comment 14 by bmeu...@chromium.org, Mar 6 2017

Description: Show this description

Comment 15 by bmeu...@chromium.org, Mar 6 2017

Cc: mvstan...@chromium.org
Status: Available (was: Assigned)

Comment 16 by bmeu...@chromium.org, Mar 6 2017

Labels: -Priority-Low Priority-Medium
Owner: danno@chromium.org
Status: Assigned (was: Available)

Comment 17 by hablich@chromium.org, Mar 23 2017

Labels: Priority-2

Comment 18 by bugdroid1@chromium.org, Jul 4 2017

Project Member
The following revision refers to this bug:
  https://chromium.googlesource.com/v8/v8.git/+/aa5852a294612471baf26c7b6bdece3055b1933b

commit aa5852a294612471baf26c7b6bdece3055b1933b
Author: Mike Stanton <mvstanton@chromium.org>
Date: Tue Jul 04 09:10:01 2017

Add JSPerf tests for more 2nd-order Array builtins

Every, Some, Reduce, ReduceRight. Added a test that should improve
when TurboFan inlines these builtins. Updated Map and Filter tests
to include a TurboFan inline test.

Bug: v8:2229
Change-Id: Ie84d414fdcccea23c734caca55a3344f9442547f
Reviewed-on: https://chromium-review.googlesource.com/558935
Reviewed-by: Benedikt Meurer <bmeurer@chromium.org>
Commit-Queue: Michael Stanton <mvstanton@chromium.org>
Cr-Commit-Position: refs/heads/master@{#46395}
[add] https://crrev.com/aa5852a294612471baf26c7b6bdece3055b1933b/test/js-perf-test/Array/every.js
[modify] https://crrev.com/aa5852a294612471baf26c7b6bdece3055b1933b/test/js-perf-test/Array/filter.js
[modify] https://crrev.com/aa5852a294612471baf26c7b6bdece3055b1933b/test/js-perf-test/Array/map.js
[add] https://crrev.com/aa5852a294612471baf26c7b6bdece3055b1933b/test/js-perf-test/Array/reduce-right.js
[add] https://crrev.com/aa5852a294612471baf26c7b6bdece3055b1933b/test/js-perf-test/Array/reduce.js
[modify] https://crrev.com/aa5852a294612471baf26c7b6bdece3055b1933b/test/js-perf-test/Array/run.js
[add] https://crrev.com/aa5852a294612471baf26c7b6bdece3055b1933b/test/js-perf-test/Array/some.js
[modify] https://crrev.com/aa5852a294612471baf26c7b6bdece3055b1933b/test/js-perf-test/JSTests.json

Comment 19 by bugdroid1@chromium.org, Jul 10 2017

Project Member
The following revision refers to this bug:
  https://chromium.googlesource.com/v8/v8.git/+/1edb46cc04912689fa6790a1e20177b1f0c8d30e

commit 1edb46cc04912689fa6790a1e20177b1f0c8d30e
Author: Benedikt Meurer <bmeurer@chromium.org>
Date: Mon Jul 10 19:16:38 2017

[turbofan] Widen the fast-path for JSCreateArray.

This improves the general Array constructor call performance (w/o
usable AllocationSite feedback) in TurboFan by ~2x, i.e. for example
invoking the Array constructor like this

  var a = Array.call(undefined, n);

instead of

  var a = Array(n);

such that the CallIC doesn't know that it's eventually calling the
Array constructor.

It also thus changes the single argument Array constructor to always
return holey arrays. Previously the single argument case for the Array
constructor was somehow trying to dynamically detect 0 and in that case
returned a packed array instead of a holey one. That adds quite a lot
of churn, and doesn't seem to be very useful, especially since this
might lead to unnecessary feedback pollution later.

R=mvstanton@chromium.org

Bug: v8:2229, v8:5269, v8:6399
Change-Id: I3d7cb9bd975ec0e491e3cdbcf1230185cfd1e3de
Reviewed-on: https://chromium-review.googlesource.com/565721
Reviewed-by: Michael Stanton <mvstanton@chromium.org>
Reviewed-by: Benedikt Meurer <bmeurer@chromium.org>
Commit-Queue: Benedikt Meurer <bmeurer@chromium.org>
Cr-Commit-Position: refs/heads/master@{#46538}
[modify] https://crrev.com/1edb46cc04912689fa6790a1e20177b1f0c8d30e/src/arm/code-stubs-arm.cc
[modify] https://crrev.com/1edb46cc04912689fa6790a1e20177b1f0c8d30e/src/arm64/code-stubs-arm64.cc
[modify] https://crrev.com/1edb46cc04912689fa6790a1e20177b1f0c8d30e/src/compiler/js-create-lowering.cc
[modify] https://crrev.com/1edb46cc04912689fa6790a1e20177b1f0c8d30e/src/compiler/js-generic-lowering.cc
[modify] https://crrev.com/1edb46cc04912689fa6790a1e20177b1f0c8d30e/src/compiler/js-graph.cc
[modify] https://crrev.com/1edb46cc04912689fa6790a1e20177b1f0c8d30e/src/compiler/js-graph.h
[modify] https://crrev.com/1edb46cc04912689fa6790a1e20177b1f0c8d30e/src/compiler/pipeline.cc
[modify] https://crrev.com/1edb46cc04912689fa6790a1e20177b1f0c8d30e/src/ia32/code-stubs-ia32.cc
[modify] https://crrev.com/1edb46cc04912689fa6790a1e20177b1f0c8d30e/src/mips/code-stubs-mips.cc
[modify] https://crrev.com/1edb46cc04912689fa6790a1e20177b1f0c8d30e/src/mips64/code-stubs-mips64.cc
[modify] https://crrev.com/1edb46cc04912689fa6790a1e20177b1f0c8d30e/src/x64/code-stubs-x64.cc
[modify] https://crrev.com/1edb46cc04912689fa6790a1e20177b1f0c8d30e/test/mjsunit/allocation-site-info.js
[modify] https://crrev.com/1edb46cc04912689fa6790a1e20177b1f0c8d30e/test/mjsunit/array-constructor-feedback.js
[modify] https://crrev.com/1edb46cc04912689fa6790a1e20177b1f0c8d30e/test/mjsunit/array-feedback.js
[modify] https://crrev.com/1edb46cc04912689fa6790a1e20177b1f0c8d30e/test/mjsunit/regress/regress-crbug-245480.js

Comment 20 by math...@qiwi.be, Sep 9 2017

Cc: mathias@chromium.org
Is `Array.prototype.push` with multiple arguments inlined too? This is a common pattern in Ember (see `addToListeners`, `pushUniqueListener`, and `pushUniqueWithGrid`).

FWIW, SpiderMonkey just implemented this, and JavaScriptCore plans on doing the same.

https://twitter.com/SpiderMonkeyJS/status/906528938452832257
https://bugs.webkit.org/show_bug.cgi?id=175823

Comment 21 by bmeu...@chromium.org, Sep 9 2017

Blockedon: 6808

Comment 22 by bugdroid1@chromium.org, Sep 11 2017

Project Member
The following revision refers to this bug:
  https://chromium.googlesource.com/v8/v8.git/+/68e4d86c6e909093bcdea3efb3f91914529e9314

commit 68e4d86c6e909093bcdea3efb3f91914529e9314
Author: Benedikt Meurer <bmeurer@chromium.org>
Date: Mon Sep 11 10:52:29 2017

[turbofan] Inline multi-parameter Array#push.

TurboFan wasn't able to inline calls to Array.prototype.push which
didn't have exactly one parameter. This was a rather artifical
limitation and was mostly due to the way the MaybeGrowFastElements
operator was implemented (which was not ideal by itself). Refactoring
this a bit, allows us to inline the operation in general, independent
of the number of values to push.

Array#push with multiple parameters is used quite a lot inside Ember (as
discovered by Apple, i.e. https://bugs.webkit.org/show_bug.cgi?id=175823)
and is also dominating the Six-Speed/SpreadLiterals/ES5 benchmark (see
https://twitter.com/SpiderMonkeyJS/status/906528938452832257 from the
SpiderMonkey folks). The micro-benchmark mentioned in the tracking bug
(v8:6808) improves from

  arrayPush0: 2422 ms.
  arrayPush1: 2567 ms.
  arrayPush2: 4092 ms.
  arrayPush3: 4308 ms.

to

  arrayPush0: 798 ms.
  arrayPush1: 2563 ms.
  arrayPush2: 2623 ms.
  arrayPush3: 2773 ms.

with this change, effectively removing the odd 50-60% performance
cliff that was associated with going from one parameter to two or
more.

Bug: v8:2229,  v8:6808 
Change-Id: Iffe4c1233903c04c3dc2062aad39d99769c8ab57
Reviewed-on: https://chromium-review.googlesource.com/657582
Reviewed-by: Jaroslav Sevcik <jarin@chromium.org>
Commit-Queue: Benedikt Meurer <bmeurer@chromium.org>
Cr-Commit-Position: refs/heads/master@{#47940}
[modify] https://crrev.com/68e4d86c6e909093bcdea3efb3f91914529e9314/src/compiler/effect-control-linearizer.cc
[modify] https://crrev.com/68e4d86c6e909093bcdea3efb3f91914529e9314/src/compiler/js-builtin-reducer.cc
[modify] https://crrev.com/68e4d86c6e909093bcdea3efb3f91914529e9314/src/compiler/js-native-context-specialization.cc
[modify] https://crrev.com/68e4d86c6e909093bcdea3efb3f91914529e9314/src/compiler/load-elimination.cc
[modify] https://crrev.com/68e4d86c6e909093bcdea3efb3f91914529e9314/src/compiler/simplified-operator.cc
[modify] https://crrev.com/68e4d86c6e909093bcdea3efb3f91914529e9314/src/compiler/simplified-operator.h
[add] https://crrev.com/68e4d86c6e909093bcdea3efb3f91914529e9314/test/mjsunit/compiler/array-push-1.js
[add] https://crrev.com/68e4d86c6e909093bcdea3efb3f91914529e9314/test/mjsunit/compiler/array-push-2.js
[add] https://crrev.com/68e4d86c6e909093bcdea3efb3f91914529e9314/test/mjsunit/compiler/array-push-3.js

Comment 23 by ras...@mindplay.dk, Dec 2 2017

Here's a couple of benchmarks demonstrating a 300-400% speed increase by inlining calls to Array.filter()

https://jsperf.com/array-filtering

https://jsperf.com/array-filtering-function

Any idea when these optimizations will land in Chrome? I feel shame every time I write a long-form filter loop, and generally encourage people to use filter/map/etc. but it's currently no good for tight, performance-critical loops.

Comment 24 by danno@chromium.org, Dec 4 2017

Inlining of Array.p.filter with full TurboFan support landed in V8 6.4 and is scheduled roll out with Chrome 64. You should see performance improvements with the order of magnitude as you observe with your hand-inlined example. Let us know if that's not the case. For more details please see the Array builtin optimization tracking bug: https://bugs.chromium.org/p/v8/issues/detail?id=1956.

Sign in to add a comment