[builtins] Improve performance of array.prototype.filter and map

src/builtins/builtins-array-gen.cc

Index: src/builtins/builtins-array-gen.cc
diff --git a/src/builtins/builtins-array-gen.cc b/src/builtins/builtins-array-gen.cc
index 6a51a4ac36e02255bec75da15be8c6baa9b1a747..9b78a4602b8672216c0eb35afca4477b6532d7a7 100644
--- a/src/builtins/builtins-array-gen.cc
+++ b/src/builtins/builtins-array-gen.cc
@@ -24,7 +24,7 @@ class ArrayBuiltinCodeStubAssembler : public CodeStubAssembler {
       BuiltinResultIndexInitializer;
 
   typedef std::function<Node*(ArrayBuiltinCodeStubAssembler* masm,
-                              Node* k_value, Node* k)>
+                              ElementsKind o_kind, Node* k_value, Node* k)>
       CallResultProcessor;
 
   typedef std::function<void(ArrayBuiltinCodeStubAssembler* masm)>
@@ -32,7 +32,7 @@ class ArrayBuiltinCodeStubAssembler : public CodeStubAssembler {
 
   Node* ForEachResultGenerator() { return UndefinedConstant(); }
 
-  Node* ForEachProcessor(Node* k_value, Node* k) {
+  Node* ForEachProcessor(ElementsKind o_kind, Node* k_value, Node* k) {
     CallJS(CodeFactory::Call(isolate()), context(), callbackfn(), this_arg(),
            k_value, k, o());
     return a();
@@ -40,7 +40,7 @@ class ArrayBuiltinCodeStubAssembler : public CodeStubAssembler {
 
   Node* SomeResultGenerator() { return FalseConstant(); }
 
-  Node* SomeProcessor(Node* k_value, Node* k) {
+  Node* SomeProcessor(ElementsKind o_kind, Node* k_value, Node* k) {
     Node* value = CallJS(CodeFactory::Call(isolate()), context(), callbackfn(),
                          this_arg(), k_value, k, o());
     Label false_continue(this), return_true(this);
@@ -53,7 +53,7 @@ class ArrayBuiltinCodeStubAssembler : public CodeStubAssembler {
 
   Node* EveryResultGenerator() { return TrueConstant(); }
 
-  Node* EveryProcessor(Node* k_value, Node* k) {
+  Node* EveryProcessor(ElementsKind o_kind, Node* k_value, Node* k) {
     Node* value = CallJS(CodeFactory::Call(isolate()), context(), callbackfn(),
                          this_arg(), k_value, k, o());
     Label true_continue(this), return_false(this);
@@ -98,7 +98,7 @@ class ArrayBuiltinCodeStubAssembler : public CodeStubAssembler {
     return a.value();
   }
 
-  Node* ReduceProcessor(Node* k_value, Node* k) {
+  Node* ReduceProcessor(ElementsKind o_kind, Node* k_value, Node* k) {
     Variable result(this, MachineRepresentation::kTagged);
     Label done(this, {&result}), initial(this);
     GotoIf(WordEqual(a(), TheHoleConstant()), &initial);
@@ -128,22 +128,68 @@ class ArrayBuiltinCodeStubAssembler : public CodeStubAssembler {
     return ArraySpeciesCreate(context(), o(), SmiConstant(0));
   }
 
-  Node* FilterProcessor(Node* k_value, Node* k) {
+  Node* FilterProcessor(ElementsKind o_kind, Node* k_value, Node* k) {
     // ii. Let selected be ToBoolean(? Call(callbackfn, T, kValue, k, O)).
     Node* selected = CallJS(CodeFactory::Call(isolate()), context(),
                             callbackfn(), this_arg(), k_value, k, o());
     Label true_continue(this, &to_), false_continue(this);
     BranchIfToBooleanIsTrue(selected, &true_continue, &false_continue);
     Bind(&true_continue);
-    // iii. If selected is true, then...
     {
+      // iii. If selected is true, then...
+      Label after_work(this, &to_);
+      if (o_kind < DICTIONARY_ELEMENTS) {

[danno, 2017/04/03 15:35:27]

Please use the predicates in elements-kind.h, e.g. IsFastElementKind().

[mvstanton, 2017/04/06 08:57:36]

Per our discussion, I'll just remove the o_kind parameter (still, good
suggestion!).

+        Node* kind = nullptr;
+
+        // If a() is a JSArray, we can have a fast path.
+        Label fast(this);
+        Label runtime(this);
+        Label object_push_pre(this), object_push(this), double_push(this);

[danno, 2017/04/03 15:35:27]

I think you can make this slightly better. Since you have the elements kind, you
only have to generate the code for either FAST_ELEMENTS or FAST_DOUBLE_ELEMENTS
at compile time.

[mvstanton, 2017/04/06 08:57:36]

Right, because of the vagaries of what can happen with the species constructor,
I'm compelled to handle all cases. There might be some improvements available at
the margin for later.

+        BranchIfFastJSArray(a(), context(), FastJSArrayAccessMode::ANY_ACCESS,
+                            &fast, &runtime);
+
+        Bind(&fast);
+        {
+          kind = EnsureArrayPushable(a(), &runtime);
+          GotoIf(Int32GreaterThan(kind, Int32Constant(FAST_HOLEY_SMI_ELEMENTS)),
+                 &object_push_pre);
+
+          BuildAppendJSArray(FAST_SMI_ELEMENTS, a(), k_value, &runtime);
+          Goto(&after_work);
+        }
+
+        Bind(&object_push_pre);
+        {
+          Branch(Int32GreaterThan(kind, Int32Constant(FAST_HOLEY_ELEMENTS)),
+                 &double_push, &object_push);
+        }
+
+        Bind(&object_push);
+        {
+          BuildAppendJSArray(FAST_ELEMENTS, a(), k_value, &runtime);
+          Goto(&after_work);
+        }
+
+        Bind(&double_push);
+        {
+          BuildAppendJSArray(FAST_DOUBLE_ELEMENTS, a(), k_value, &runtime);
+          Goto(&after_work);
+        }
+
+        Bind(&runtime);
+      }
+
       // 1. Perform ? CreateDataPropertyOrThrow(A, ToString(to), kValue).
       CallRuntime(Runtime::kCreateDataProperty, context(), a(), to_.value(),
                   k_value);
+      Goto(&after_work);
 
-      // 2. Increase to by 1.
-      to_.Bind(NumberInc(to_.value()));
-      Goto(&false_continue);
+      Bind(&after_work);
+      {
+        // 2. Increase to by 1.
+        to_.Bind(NumberInc(to_.value()));
+        Goto(&false_continue);
+      }
     }
     Bind(&false_continue);
     return a();
@@ -154,14 +200,66 @@ class ArrayBuiltinCodeStubAssembler : public CodeStubAssembler {
     return ArraySpeciesCreate(context(), o(), len_);
   }
 
-  Node* MapProcessor(Node* k_value, Node* k) {
+  Node* MapProcessor(ElementsKind o_kind, Node* k_value, Node* k) {
     //  i. Let kValue be ? Get(O, Pk). Performed by the caller of MapProcessor.
     // ii. Let mappedValue be ? Call(callbackfn, T, kValue, k, O).
     Node* mappedValue = CallJS(CodeFactory::Call(isolate()), context(),
                                callbackfn(), this_arg(), k_value, k, o());
 
+    Label finished(this);
+    if (o_kind < DICTIONARY_ELEMENTS) {
+      Node* kind = nullptr;
+      Node* elements = nullptr;
+
+      // If a() is a JSArray, we can have a fast path.
+      // mode is SMI_PARAMETERS because k has tagged representation.
+      ParameterMode mode = SMI_PARAMETERS;
+      Label fast(this);
+      Label runtime(this);
+      Label object_push_pre(this), object_push(this), double_push(this);
+      BranchIfFastJSArray(a(), context(), FastJSArrayAccessMode::ANY_ACCESS,
+                          &fast, &runtime);
+
+      Bind(&fast);
+      {
+        kind = EnsureArrayPushable(a(), &runtime);
+        elements = LoadElements(a());
+        GotoIf(Int32GreaterThan(kind, Int32Constant(FAST_HOLEY_SMI_ELEMENTS)),

[danno, 2017/04/03 15:35:27]

Consider adding/using existing predicates in code-stub-assembler.h like
"IsFastElementsKind" and "IsHoleyFastElementsKind".

[mvstanton, 2017/04/06 08:57:36]

I use a "greater than" metaphor to avoid multiple comparisons.

+               &object_push_pre);
+
+        TryStoreArrayElement(FAST_SMI_ELEMENTS, mode, &runtime, elements, k,
+                             mappedValue);
+        Goto(&finished);
+      }
+
+      Bind(&object_push_pre);
+      {
+        Branch(Int32GreaterThan(kind, Int32Constant(FAST_HOLEY_ELEMENTS)),
+               &double_push, &object_push);
+      }
+
+      Bind(&object_push);
+      {
+        TryStoreArrayElement(FAST_ELEMENTS, mode, &runtime, elements, k,
+                             mappedValue);
+        Goto(&finished);
+      }
+
+      Bind(&double_push);
+      {
+        TryStoreArrayElement(FAST_DOUBLE_ELEMENTS, mode, &runtime, elements, k,
+                             mappedValue);
+        Goto(&finished);
+      }
+
+      Bind(&runtime);
+    }
+
     // iii. Perform ? CreateDataPropertyOrThrow(A, Pk, mappedValue).
     CallRuntime(Runtime::kCreateDataProperty, context(), a(), k, mappedValue);
+    Goto(&finished);
+
+    Bind(&finished);
     return a();
   }
 
@@ -420,7 +518,7 @@ class ArrayBuiltinCodeStubAssembler : public CodeStubAssembler {
 
       // iii. Let funcResult be Call(callbackfn, T, «kValue, k, O»).
       // iv. ReturnIfAbrupt(funcResult).
-      a_.Bind(processor(this, k_value, k()));
+      a_.Bind(processor(this, DICTIONARY_ELEMENTS, k_value, k()));

[danno, 2017/04/03 15:35:27]

Although I know what you mean here, the elements may not be dictionary at this
point. In fact, they can be anything. I am leaning towards adding a new
ElementsKind kind of like "NO_ELEMENTS", but called "UNKNOWN_ELEMENTS" and to
pass that here.

       Goto(&done_element);
 
       Bind(&done_element);
@@ -473,7 +571,7 @@ class ArrayBuiltinCodeStubAssembler : public CodeStubAssembler {
       Node* value = LoadFixedTypedArrayElementAsTagged(data_ptr, index, kind,
                                                        SMI_PARAMETERS);
       k_.Bind(index);
-      a_.Bind(processor(this, value, index));
+      a_.Bind(processor(this, kind, value, index));
     };
     BuildFastLoop(list, SmiConstant(0), len_, body, 1,
                   ParameterMode::SMI_PARAMETERS, IndexAdvanceMode::kPost);
@@ -529,7 +627,7 @@ class ArrayBuiltinCodeStubAssembler : public CodeStubAssembler {
                 LoadDoubleWithHoleCheck(elements, offset, &hole_element);
             value = AllocateHeapNumberWithValue(double_value);
           }
-          a_.Bind(processor(this, value, k()));
+          a_.Bind(processor(this, kind, value, k()));
           Goto(&one_element_done);
 
           Bind(&hole_element);
@@ -632,39 +730,13 @@ TF_BUILTIN(FastArrayPush, CodeStubAssembler) {
 
   Bind(&fast);
   {
-    // Disallow pushing onto prototypes. It might be the JSArray prototype.
-    // Disallow pushing onto non-extensible objects.
-    Comment("Disallow pushing onto prototypes");
-    Node* map = LoadMap(receiver);
-    Node* bit_field2 = LoadMapBitField2(map);
-    int mask = static_cast<int>(Map::IsPrototypeMapBits::kMask) |
-               (1 << Map::kIsExtensible);
-    Node* test = Word32And(bit_field2, Int32Constant(mask));
-    GotoIf(Word32NotEqual(test, Int32Constant(1 << Map::kIsExtensible)),
-           &runtime);
-
-    // Disallow pushing onto arrays in dictionary named property mode. We need
-    // to figure out whether the length property is still writable.
-    Comment("Disallow pushing onto arrays in dictionary named property mode");
-    GotoIf(IsDictionaryMap(map), &runtime);
-
-    // Check whether the length property is writable. The length property is the
-    // only default named property on arrays. It's nonconfigurable, hence is
-    // guaranteed to stay the first property.
-    Node* descriptors = LoadMapDescriptors(map);
-    Node* details =
-        LoadFixedArrayElement(descriptors, DescriptorArray::ToDetailsIndex(0));
-    GotoIf(IsSetSmi(details, PropertyDetails::kAttributesReadOnlyMask),
-           &runtime);
-
     arg_index.Bind(IntPtrConstant(0));
-    kind = DecodeWord32<Map::ElementsKindBits>(bit_field2);
-
+    kind = EnsureArrayPushable(receiver, &runtime);
     GotoIf(Int32GreaterThan(kind, Int32Constant(FAST_HOLEY_SMI_ELEMENTS)),
            &object_push_pre);
 
-    Node* new_length = BuildAppendJSArray(FAST_SMI_ELEMENTS, context, receiver,
-                                          args, arg_index, &smi_transition);
+    Node* new_length = BuildAppendJSArray(FAST_SMI_ELEMENTS, receiver, args,
+                                          arg_index, &smi_transition);
     args.PopAndReturn(new_length);
   }
 
@@ -702,16 +774,15 @@ TF_BUILTIN(FastArrayPush, CodeStubAssembler) {
 
   Bind(&object_push);
   {
-    Node* new_length = BuildAppendJSArray(FAST_ELEMENTS, context, receiver,
-                                          args, arg_index, &default_label);
+    Node* new_length = BuildAppendJSArray(FAST_ELEMENTS, receiver, args,
+                                          arg_index, &default_label);
     args.PopAndReturn(new_length);
   }
 
   Bind(&double_push);
   {
-    Node* new_length =
-        BuildAppendJSArray(FAST_DOUBLE_ELEMENTS, context, receiver, args,
-                           arg_index, &double_transition);
+    Node* new_length = BuildAppendJSArray(FAST_DOUBLE_ELEMENTS, receiver, args,
+                                          arg_index, &double_transition);
     args.PopAndReturn(new_length);
   }