FazBrowse GitHub Viewer | Trending |
URL:
| Home
Tools: [Download Repo ZIP]   [Original HTTPS Page]

deps: cherry-pick 6d38f89 from upstream V8 · nodejs/node@2db2857 · GitHub

/ node Public

Commit 2db2857

Browse files
targos
committed
deps: cherry-pick 6d38f89 from upstream V8
Original commit message: [turbofan] Boost performance of Array.prototype.shift by 4x. For small arrays, it's way faster to just move the elements instead of doing the fairly complex and heavy-weight left-trimming. Crankshaft has had this optimization for small arrays already; this CL more or less ports this functionality to TurboFan, which yields a 4x speed-up when using shift on small arrays (with up to 16 elements). This should recover some of the regressions reported in the Node.js issues #12657 and discovered for the syncthrough module using https://github.com/mcollina/syncthrough/blob/master/benchmarks/basic.js as benchmark. R=jarin@chromium.org BUG=v8:6376 Review-Url: https://codereview.chromium.org/2874453002 Cr-Commit-Position: refs/heads/master@{#45216} PR-URL: #13263 Reviewed-By: Gibson Fahnestock <gibfahn@gmail.com> Reviewed-By: Ben Noordhuis <info@bnoordhuis.nl> Reviewed-By: Franziska Hinkelmann <franziska.hinkelmann@gmail.com> Reviewed-By: Myles Borins <myles.borins@gmail.com>
1 parent 554fa24 commit 2db2857

6 files changed

Lines changed: 242 additions & 1 deletion

File tree

‎deps/v8/src/compiler/graph.h‎

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -104,6 +104,17 @@ class V8_EXPORT_PRIVATE Graph final : public NON_EXPORTED_BASE(ZoneObject) {
104104
Node* nodes[] = {n1, n2, n3, n4, n5, n6, n7, n8, n9};
105105
return NewNode(op, arraysize(nodes), nodes);
106106
}
107+
Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3, Node* n4,
108+
Node* n5, Node* n6, Node* n7, Node* n8, Node* n9, Node* n10) {
109+
Node* nodes[] = {n1, n2, n3, n4, n5, n6, n7, n8, n9, n10};
110+
return NewNode(op, arraysize(nodes), nodes);
111+
}
112+
Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3, Node* n4,
113+
Node* n5, Node* n6, Node* n7, Node* n8, Node* n9, Node* n10,
114+
Node* n11) {
115+
Node* nodes[] = {n1, n2, n3, n4, n5, n6, n7, n8, n9, n10, n11};
116+
return NewNode(op, arraysize(nodes), nodes);
117+
}
107118

108119
// Clone the {node}, and assign a new node id to the copy.
109120
Node* CloneNode(const Node* node);

‎deps/v8/src/compiler/js-builtin-reducer.cc‎

Lines changed: 176 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -5,6 +5,7 @@
55
#include "src/compiler/js-builtin-reducer.h"
66

77
#include "src/base/bits.h"
8+
#include "src/builtins/builtins-utils.h"
89
#include "src/code-factory.h"
910
#include "src/compilation-dependencies.h"
1011
#include "src/compiler/access-builder.h"
@@ -1005,6 +1006,179 @@ Reduction JSBuiltinReducer::ReduceArrayPush(Node* node) {
10051006
return NoChange();
10061007
}
10071008

1009+
// ES6 section 22.1.3.22 Array.prototype.shift ( )
1010+
Reduction JSBuiltinReducer::ReduceArrayShift(Node* node) {
1011+
Node* target = NodeProperties::GetValueInput(node, 0);
1012+
Node* receiver = NodeProperties::GetValueInput(node, 1);
1013+
Node* context = NodeProperties::GetContextInput(node);
1014+
Node* frame_state = NodeProperties::GetFrameStateInput(node);
1015+
Node* effect = NodeProperties::GetEffectInput(node);
1016+
Node* control = NodeProperties::GetControlInput(node);
1017+
1018+
// TODO(turbofan): Extend this to also handle fast holey double elements
1019+
// once we got the hole NaN mess sorted out in TurboFan/V8.
1020+
Handle<Map> receiver_map;
1021+
if (GetMapWitness(node).ToHandle(&receiver_map) &&
1022+
CanInlineArrayResizeOperation(receiver_map) &&
1023+
receiver_map->elements_kind() != FAST_HOLEY_DOUBLE_ELEMENTS) {
1024+
// Install code dependencies on the {receiver} prototype maps and the
1025+
// global array protector cell.
1026+
dependencies()->AssumePropertyCell(factory()->array_protector());
1027+
dependencies()->AssumePrototypeMapsStable(receiver_map);
1028+
1029+
// Load length of the {receiver}.
1030+
Node* length = effect = graph()->NewNode(
1031+
simplified()->LoadField(
1032+
AccessBuilder::ForJSArrayLength(receiver_map->elements_kind())),
1033+
receiver, effect, control);
1034+
1035+
// Return undefined if {receiver} has no elements.
1036+
Node* check0 = graph()->NewNode(simplified()->NumberEqual(), length,
1037+
jsgraph()->ZeroConstant());
1038+
Node* branch0 =
1039+
graph()->NewNode(common()->Branch(BranchHint::kFalse), check0, control);
1040+
1041+
Node* if_true0 = graph()->NewNode(common()->IfTrue(), branch0);
1042+
Node* etrue0 = effect;
1043+
Node* vtrue0 = jsgraph()->UndefinedConstant();
1044+
1045+
Node* if_false0 = graph()->NewNode(common()->IfFalse(), branch0);
1046+
Node* efalse0 = effect;
1047+
Node* vfalse0;
1048+
{
1049+
// Check if we should take the fast-path.
1050+
Node* check1 =
1051+
graph()->NewNode(simplified()->NumberLessThanOrEqual(), length,
1052+
jsgraph()->Constant(JSArray::kMaxCopyElements));
1053+
Node* branch1 = graph()->NewNode(common()->Branch(BranchHint::kTrue),
1054+
check1, if_false0);
1055+
1056+
Node* if_true1 = graph()->NewNode(common()->IfTrue(), branch1);
1057+
Node* etrue1 = efalse0;
1058+
Node* vtrue1;
1059+
{
1060+
Node* elements = etrue1 = graph()->NewNode(
1061+
simplified()->LoadField(AccessBuilder::ForJSObjectElements()),
1062+
receiver, etrue1, if_true1);
1063+
1064+
// Load the first element here, which we return below.
1065+
vtrue1 = etrue1 = graph()->NewNode(
1066+
simplified()->LoadElement(AccessBuilder::ForFixedArrayElement(
1067+
receiver_map->elements_kind())),
1068+
elements, jsgraph()->ZeroConstant(), etrue1, if_true1);
1069+
1070+
// Ensure that we aren't shifting a copy-on-write backing store.
1071+
if (IsFastSmiOrObjectElementsKind(receiver_map->elements_kind())) {
1072+
elements = etrue1 =
1073+
graph()->NewNode(simplified()->EnsureWritableFastElements(),
1074+
receiver, elements, etrue1, if_true1);
1075+
}
1076+
1077+
// Shift the remaining {elements} by one towards the start.
1078+
Node* loop = graph()->NewNode(common()->Loop(2), if_true1, if_true1);
1079+
Node* eloop =
1080+
graph()->NewNode(common()->EffectPhi(2), etrue1, etrue1, loop);
1081+
Node* index = graph()->NewNode(
1082+
common()->Phi(MachineRepresentation::kTagged, 2),
1083+
jsgraph()->OneConstant(),
1084+
jsgraph()->Constant(JSArray::kMaxCopyElements - 1), loop);
1085+
1086+
{
1087+
Node* check2 =
1088+
graph()->NewNode(simplified()->NumberLessThan(), index, length);
1089+
Node* branch2 = graph()->NewNode(common()->Branch(), check2, loop);
1090+
1091+
if_true1 = graph()->NewNode(common()->IfFalse(), branch2);
1092+
etrue1 = eloop;
1093+
1094+
Node* control = graph()->NewNode(common()->IfTrue(), branch2);
1095+
Node* effect = etrue1;
1096+
1097+
ElementAccess const access = AccessBuilder::ForFixedArrayElement(
1098+
receiver_map->elements_kind());
1099+
Node* value = effect =
1100+
graph()->NewNode(simplified()->LoadElement(access), elements,
1101+
index, effect, control);
1102+
effect = graph()->NewNode(
1103+
simplified()->StoreElement(access), elements,
1104+
graph()->NewNode(simplified()->NumberSubtract(), index,
1105+
jsgraph()->OneConstant()),
1106+
value, effect, control);
1107+
1108+
loop->ReplaceInput(1, control);
1109+
eloop->ReplaceInput(1, effect);
1110+
index->ReplaceInput(1,
1111+
graph()->NewNode(simplified()->NumberAdd(), index,
1112+
jsgraph()->OneConstant()));
1113+
}
1114+
1115+
// Compute the new {length}.
1116+
length = graph()->NewNode(simplified()->NumberSubtract(), length,
1117+
jsgraph()->OneConstant());
1118+
1119+
// Store the new {length} to the {receiver}.
1120+
etrue1 = graph()->NewNode(
1121+
simplified()->StoreField(
1122+
AccessBuilder::ForJSArrayLength(receiver_map->elements_kind())),
1123+
receiver, length, etrue1, if_true1);
1124+
1125+
// Store a hole to the element we just removed from the {receiver}.
1126+
etrue1 = graph()->NewNode(
1127+
simplified()->StoreElement(AccessBuilder::ForFixedArrayElement(
1128+
GetHoleyElementsKind(receiver_map->elements_kind()))),
1129+
elements, length, jsgraph()->TheHoleConstant(), etrue1, if_true1);
1130+
}
1131+
1132+
Node* if_false1 = graph()->NewNode(common()->IfFalse(), branch1);
1133+
Node* efalse1 = efalse0;
1134+
Node* vfalse1;
1135+
{
1136+
// Call the generic C++ implementation.
1137+
const int builtin_index = Builtins::kArrayShift;
1138+
CallDescriptor const* const desc = Linkage::GetCEntryStubCallDescriptor(
1139+
graph()->zone(), 1, BuiltinArguments::kNumExtraArgsWithReceiver,
1140+
Builtins::name(builtin_index), node->op()->properties(),
1141+
CallDescriptor::kNeedsFrameState);
1142+
Node* stub_code = jsgraph()->CEntryStubConstant(1, kDontSaveFPRegs,
1143+
kArgvOnStack, true);
1144+
Address builtin_entry = Builtins::CppEntryOf(builtin_index);
1145+
Node* entry = jsgraph()->ExternalConstant(
1146+
ExternalReference(builtin_entry, isolate()));
1147+
Node* argc =
1148+
jsgraph()->Constant(BuiltinArguments::kNumExtraArgsWithReceiver);
1149+
if_false1 = efalse1 = vfalse1 =
1150+
graph()->NewNode(common()->Call(desc), stub_code, receiver, argc,
1151+
target, jsgraph()->UndefinedConstant(), entry,
1152+
argc, context, frame_state, efalse1, if_false1);
1153+
}
1154+
1155+
if_false0 = graph()->NewNode(common()->Merge(2), if_true1, if_false1);
1156+
efalse0 =
1157+
graph()->NewNode(common()->EffectPhi(2), etrue1, efalse1, if_false0);
1158+
vfalse0 =
1159+
graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2),
1160+
vtrue1, vfalse1, if_false0);
1161+
}
1162+
1163+
control = graph()->NewNode(common()->Merge(2), if_true0, if_false0);
1164+
effect = graph()->NewNode(common()->EffectPhi(2), etrue0, efalse0, control);
1165+
Node* value =
1166+
graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2),
1167+
vtrue0, vfalse0, control);
1168+
1169+
// Convert the hole to undefined. Do this last, so that we can optimize
1170+
// conversion operator via some smart strength reduction in many cases.
1171+
if (IsFastHoleyElementsKind(receiver_map->elements_kind())) {
1172+
value =
1173+
graph()->NewNode(simplified()->ConvertTaggedHoleToUndefined(), value);
1174+
}
1175+
1176+
ReplaceWithValue(node, value, effect, control);
1177+
return Replace(value);
1178+
}
1179+
return NoChange();
1180+
}
1181+
10081182
namespace {
10091183

10101184
bool HasInstanceTypeWitness(Node* receiver, Node* effect,
@@ -2125,6 +2299,8 @@ Reduction JSBuiltinReducer::Reduce(Node* node) {
21252299
return ReduceArrayPop(node);
21262300
case kArrayPush:
21272301
return ReduceArrayPush(node);
2302+
case kArrayShift:
2303+
return ReduceArrayShift(node);
21282304
case kDateNow:
21292305
return ReduceDateNow(node);
21302306
case kDateGetTime:

‎deps/v8/src/compiler/js-builtin-reducer.h‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -58,6 +58,7 @@ class V8_EXPORT_PRIVATE JSBuiltinReducer final
5858
Reduction ReduceArrayIsArray(Node* node);
5959
Reduction ReduceArrayPop(Node* node);
6060
Reduction ReduceArrayPush(Node* node);
61+
Reduction ReduceArrayShift(Node* node);
6162
Reduction ReduceDateNow(Node* node);
6263
Reduction ReduceDateGetTime(Node* node);
6364
Reduction ReduceGlobalIsFinite(Node* node);

‎deps/v8/src/crankshaft/hydrogen.cc‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -8821,7 +8821,7 @@ bool HOptimizedGraphBuilder::TryInlineBuiltinMethodCall(
88218821
Handle<JSObject>::null(), true);
88228822

88238823
// Threshold for fast inlined Array.shift().
8824-
HConstant* inline_threshold = Add<HConstant>(static_cast<int32_t>(16));
8824+
HConstant* inline_threshold = Add<HConstant>(JSArray::kMaxCopyElements);
88258825

88268826
Drop(args_count_no_receiver);
88278827
HValue* result;

‎deps/v8/src/objects.h‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -9608,6 +9608,9 @@ class JSArray: public JSObject {
96089608
static const int kLengthOffset = JSObject::kHeaderSize;
96099609
static const int kSize = kLengthOffset + kPointerSize;
96109610

9611+
// Max. number of elements being copied in Array builtins.
9612+
static const int kMaxCopyElements = 16;
9613+
96119614
static const int kInitialMaxFastElementArray =
96129615
(kMaxRegularHeapObjectSize - FixedArray::kHeaderSize - kSize -
96139616
AllocationMemento::kSize) /

‎deps/v8/test/mjsunit/array-shift5.js‎

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
// Copyright 2017 the V8 project authors. All rights reserved.
2+
// Use of this source code is governed by a BSD-style license that can be
3+
// found in the LICENSE file.
4+
5+
// Flags: --allow-natives-syntax
6+
7+
(function() {
8+
function doShift(a) { return a.shift(); }
9+
10+
function test() {
11+
var a = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16];
12+
assertEquals(0, doShift(a));
13+
assertEquals([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16], a);
14+
}
15+
16+
test();
17+
test();
18+
%OptimizeFunctionOnNextCall(doShift);
19+
test();
20+
})();
21+
22+
(function() {
23+
function doShift(a) { return a.shift(); }
24+
25+
function test() {
26+
var a = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16.1];
27+
assertEquals(0, doShift(a));
28+
assertEquals([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16.1], a);
29+
}
30+
31+
test();
32+
test();
33+
%OptimizeFunctionOnNextCall(doShift);
34+
test();
35+
})();
36+
37+
(function() {
38+
function doShift(a) { return a.shift(); }
39+
40+
function test() {
41+
var a = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,"16"];
42+
assertEquals(0, doShift(a));
43+
assertEquals([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,"16"], a);
44+
}
45+
46+
test();
47+
test();
48+
%OptimizeFunctionOnNextCall(doShift);
49+
test();
50+
})();

0 commit comments

Comments
 (0)
Back | FazBrowse Home | New Git URL