[builtins] implement Array.prototype.includes in TurboFan

src/elements.cc

Index: src/elements.cc
diff --git a/src/elements.cc b/src/elements.cc
index 3cf8378162844a1fc00525e3ccacdb6f47406ac5..b9dfe8ce2b6c5f6b3ffc574fdd16528c887df3ec 100644
--- a/src/elements.cc
+++ b/src/elements.cc
@@ -468,6 +468,27 @@ static void SortIndices(
   }
 }
 
+static Maybe<bool> IncludesValueSlowPath(Isolate* isolate,
+                                         Handle<JSObject> receiver,
+                                         Handle<Object> value,
+                                         uint32_t start_from, uint32_t length) {
+  bool search_for_hole = value->IsUndefined(isolate);
+  for (uint32_t k = start_from; k < length; ++k) {
+    LookupIterator it(isolate, receiver, k);
+    if (!it.IsFound()) {
+      if (search_for_hole) return Just(true);
+      continue;
+    }
+    Handle<Object> element_k;
+    ASSIGN_RETURN_ON_EXCEPTION_VALUE(isolate, element_k,
+                                     Object::GetProperty(&it), Nothing<bool>());
+
+    if (value->SameValueZero(*element_k)) return Just(true);
+  }
+
+  return Just(false);
+}
+
 // Base class for element handler implementations. Contains the
 // the common logic for objects with different ElementsKinds.
 // Subclasses must specialize method for which the element
@@ -1046,6 +1067,20 @@ class ElementsAccessorBase : public ElementsAccessor {
     return Subclass::GetCapacityImpl(holder, backing_store);
   }
 
+  static Maybe<bool> IncludesValueImpl(Isolate* isolate,
+                                       Handle<JSReceiver> receiver,
+                                       Handle<Object> value,
+                                       uint32_t start_from, uint32_t length) {
+    UNREACHABLE();

[caitp, 2016/07/21 03:28:55]

mostly for debugging, could make this fall back to the SlowPath when not
implemented

+  }
+
+  Maybe<bool> IncludesValue(Isolate* isolate, Handle<JSObject> receiver,
+                            Handle<Object> value, uint32_t start_from,
+                            uint32_t length) final {
+    return Subclass::IncludesValueImpl(isolate, receiver, value, start_from,
+                                       length);
+  }
+
   static uint32_t GetIndexForEntryImpl(FixedArrayBase* backing_store,
                                        uint32_t entry) {
     return entry;
@@ -1382,6 +1417,57 @@ class DictionaryElementsAccessor
       accumulator->AddKey(value, convert);
     }
   }
+
+  static Maybe<bool> IncludesValueImpl(Isolate* isolate,
+                                       Handle<JSObject> receiver,
+                                       Handle<Object> value,
+                                       uint32_t start_from, uint32_t length) {
+    Handle<SeededNumberDictionary> dictionary(
+        SeededNumberDictionary::cast(receiver->elements()), isolate);
+
+    Handle<Map> original_map = handle(receiver->map(), isolate);
+
+    bool search_for_hole = value->IsUndefined(isolate);
+
+    // Iterate through entire range, as accessing elements out of order is
+    // observable
+    for (uint32_t k = start_from; k < length; ++k) {

[caitp, 2016/07/21 03:28:55]

This comment _may_ be wrong --- if there's some sort of guarantee that indexes
will always be in order, then I'm sure we can actually just iterate over the
occupied slots in the dictionary

[Camillo Bruni, 2016/07/21 08:01:55]

Right, this is probably tricky to get fast always. Dictionary are unsorted and
cause quite a bit of pain (see the KeyAccumulator which has to sort a temp array
for dict-elements).

You can iterate all the dictionary entries directly as long as you don't see a
accessor. The moment you see an accessor you have to restart the search using
your approach. This might be slightly slower for the accessor case than your
approach but would speed up the normal dictionary-elements case (not sure by how
much).

+      int entry = dictionary->FindEntry(k);
+      if (entry == SeededNumberDictionary::kNotFound) {
+        if (search_for_hole) return Just(true);
+        continue;
+      }
+
+      PropertyDetails details = GetDetailsImpl(receiver->elements(), entry);
+      switch (details.kind()) {
+        case kData: {
+          Object* element_k = dictionary->ValueAt(entry);
+          if (value->SameValueZero(element_k)) return Just(true);
+          break;
+        }
+        case kAccessor: {
+          LookupIterator it(isolate, receiver, k, LookupIterator::OWN);
+          DCHECK(it.IsFound());
+          DCHECK_EQ(it.state(), LookupIterator::ACCESSOR);
+          Handle<Object> element_k;
+
+          ASSIGN_RETURN_ON_EXCEPTION_VALUE(
+              isolate, element_k, JSObject::GetPropertyWithAccessor(&it),
+              Nothing<bool>());
+
+          if (value->SameValueZero(*element_k)) return Just(true);
+
+          if (receiver->map() != *original_map) {
+            // Some mutation occurred in accessor. Abort "fast" path
+            return IncludesValueSlowPath(isolate, receiver, value, k + 1,
+                                         length);
+          }
+          break;
+        }
+      }
+    }
+    return Just(false);
+  }
 };
 
 
@@ -1742,6 +1828,128 @@ class FastElementsAccessor : public ElementsAccessorBase<Subclass, KindTraits> {
     }
   }
 
+  static Maybe<bool> IncludesValueImpl(Isolate* isolate,
+                                       Handle<JSObject> receiver,
+                                       Handle<Object> search_value,
+                                       uint32_t start_from, uint32_t length) {
+    DisallowHeapAllocation no_gc;
+    FixedArrayBase* elements_base = receiver->elements();
+    Object* the_hole = isolate->heap()->the_hole_value();
+    Object* undefined = isolate->heap()->undefined_value();
+    Object* value = *search_value;
+
+    // Elements beyond the capacity of the backing store treated as undefined.
+    if (value == undefined && elements_base->length() < length) {

[caitp, 2016/07/21 03:28:55]

I think this assumption holds if there are no elements in the prototype chain

+      return Just(true);
+    }
+
+    if (start_from >= length) return Just(false);
+
+    if (!value->IsNumber()) {

[caitp, 2016/07/21 03:28:55]

I prefer not to add these sorts of fast paths in a C++ version of this, because
it looks like a pile of tech debt, even if it is faster. Maybe the TF and
Crankshaft versions can be complicated like this, but maybe not the
ElementsAccessor?

[Camillo Bruni, 2016/07/21 08:01:55]

I'd vouch for exactly the opposite. TF and Crankshaft are terrible to debug :)
if we get a crash in there it takes significantly longer to find out what went
wrong. For C++ we get a nice stack trace :P + it's way easier to understand.

[caitp, 2016/07/21 20:32:29]

Maybe the way to do this is to have just a C++ builtin, and a crankshaft inlined
version for certain fast cases. Otherwise, it seems like the C++ code is
starting to do a lot of the same stuff the TF version is doing.

My goal here is to get the performance of A.p.includes more or less on par with
indexOf (for the typical use-case), and possibly reduce startup time for V8 a
little bit as a bonus. I don't think we want to have to implement a whole bunch
of implementations of the same thing just to accomplish those goals.

+      if (value == undefined) {
+        // Only FAST_ELEMENTS, FAST_HOLEY_ELEMENTS, FAST_HOLEY_SMI_ELEMENTS, and
+        // FAST_HOLEY_DOUBLE_ELEMENTS can have `undefined` as a value.
+        if (!IsFastObjectElementsKind(KindTraits::Kind) &&
+            !IsFastHoleyElementsKind(KindTraits::Kind)) {
+          return Just(false);
+        }
+        if (IsFastSmiOrObjectElementsKind(KindTraits::Kind)) {
+          auto elements = FixedArray::cast(receiver->elements());
+
+          for (uint32_t k = start_from; k < length; ++k) {
+            Object* element_k = elements->get(k);
+
+            if (IsFastHoleyElementsKind(KindTraits::Kind) &&
+                element_k == the_hole) {
+              return Just(true);
+            }
+            if (IsFastObjectElementsKind(KindTraits::Kind) &&
+                element_k == undefined) {
+              return Just(true);
+            }
+          }
+          return Just(false);
+        } else {
+          // Loop searching for non-Number, non-Undefined elements
+          auto elements = FixedDoubleArray::cast(receiver->elements());
+
+          for (uint32_t k = start_from; k < length; ++k) {
+            if (IsFastHoleyElementsKind(KindTraits::Kind) &&
+                elements->is_the_hole(k)) {
+              return Just(true);
+            }
+          }
+          return Just(false);
+        }
+      } else if (!IsFastObjectElementsKind(KindTraits::Kind)) {
+        // Only Numbers can be represented as packed Smi or Double elements
+        return Just(false);
+      } else {
+        auto elements = FixedArray::cast(receiver->elements());
+
+        for (uint32_t k = start_from; k < length; ++k) {
+          Object* element_k = elements->get(k);
+          if (IsFastHoleyElementsKind(KindTraits::Kind) &&
+              element_k == the_hole) {
+            continue;
+          }
+
+          if (value->SameValueZero(element_k)) return Just(true);
+        }
+        return Just(false);
+      }
+    } else {
+      if (!value->IsNaN()) {
+        double search_value = value->Number();
+        if (IsFastDoubleElementsKind(KindTraits::Kind)) {
+          auto elements = FixedDoubleArray::cast(receiver->elements());
+
+          for (uint32_t k = start_from; k < length; ++k) {
+            if (IsFastHoleyElementsKind(KindTraits::Kind) &&
+                elements->is_the_hole(k)) {
+              continue;
+            }
+            if (elements->get_scalar(k) == search_value) return Just(true);
+          }
+          return Just(false);
+        } else {
+          auto elements = FixedArray::cast(receiver->elements());
+
+          for (uint32_t k = start_from; k < length; ++k) {
+            Object* element_k = elements->get(k);
+            if (element_k->IsNumber() && element_k->Number() == search_value) {
+              return Just(true);
+            }
+          }
+          return Just(false);
+        }
+      } else {
+        // NaN cannot be represented with Smi elements
+        if (IsFastSmiElementsKind(KindTraits::Kind)) return Just(false);
+
+        if (IsFastDoubleElementsKind(KindTraits::Kind)) {
+          auto elements = FixedDoubleArray::cast(receiver->elements());
+
+          for (uint32_t k = start_from; k < length; ++k) {
+            if (IsFastHoleyElementsKind(KindTraits::Kind) &&
+                elements->is_the_hole(k)) {
+              continue;
+            }
+            if (std::isnan(elements->get_scalar(k))) return Just(true);
+          }
+          return Just(false);
+        } else {
+          auto elements = FixedArray::cast(receiver->elements());
+
+          for (uint32_t k = start_from; k < length; ++k) {
+            if (elements->get(k)->IsNaN()) return Just(true);
+          }
+          return Just(false);
+        }
+      }
+    }
+  }
+
  private:
   // SpliceShrinkStep might modify the backing_store.
   static void SpliceShrinkStep(Isolate* isolate, Handle<JSArray> receiver,
@@ -2430,6 +2638,45 @@ class SloppyArgumentsElementsAccessor
         isolate, object, store, convert, filter, list, nof_indices,
         insertion_index);
   }
+
+  static Maybe<bool> IncludesValueImpl(Isolate* isolate,
+                                       Handle<JSObject> object,
+                                       Handle<Object> value,
+                                       uint32_t start_from, uint32_t length) {
+    Handle<Map> original_map = handle(object->map(), isolate);
+    FixedArray* parameter_map = FixedArray::cast(object->elements());
+    bool search_for_hole = value->IsUndefined(isolate);
+
+    for (uint32_t k = start_from; k < length; ++k) {
+      uint32_t entry =
+          GetEntryForIndexImpl(*object, parameter_map, k, ALL_PROPERTIES);
+      if (entry == kMaxUInt32) {
+        if (search_for_hole) return Just(true);
+        continue;
+      }
+
+      Handle<Object> element_k = GetImpl(parameter_map, entry);
+
+      if (element_k->IsAccessorPair()) {
+        LookupIterator it(isolate, object, k, LookupIterator::OWN);
+        DCHECK(it.IsFound());
+        DCHECK_EQ(it.state(), LookupIterator::ACCESSOR);
+        ASSIGN_RETURN_ON_EXCEPTION_VALUE(isolate, element_k,
+                                         Object::GetPropertyWithAccessor(&it),
+                                         Nothing<bool>());
+
+        if (value->SameValueZero(*element_k)) return Just(true);
+
+        if (object->map() != *original_map) {
+          // Some mutation occurred in accessor. Abort "fast" path
+          return IncludesValueSlowPath(isolate, object, value, k + 1, length);

[caitp, 2016/07/21 03:28:55]

I don't think a map check is really adequate for this (or for the similar
DICTIONARY_ELEMENTS case), in case there are changes higher in the prototype
chain. Is there a better way that doesn't totally sacrifice performance? Maybe
just always bail out to the slow path after calling an accessor?

[Camillo Bruni, 2016/07/21 08:01:55]

You can only have a dictionary (with potential accessors) in the
SlowSloppyArguments case.

Maybe duplicate the IncludesValueImpl for the two arguments subclasses, this way
you might be able to share the dictionary part with the normal
DICTIONARY_ELEMENTS case.

[caitp, 2016/07/21 20:32:29]

I agree that it only applies to the SlowArgumentsCase --- I think it might not
be worth distinguishing between them, since this operation on Arguments objects
is probably not going to be very common in the future (similarly,
`Array.prototype.indexOf.call(arguments, ...)` is probably not very common
pattern today).

What do you think?

Anyways, my question was really about whether a map check is enough to know if
it's safe to continue on the "fast" path (where the prototype is assumed to have
no elements). Is it possible for the map to remain the same even if the elements
backing store changes? Or even if some map higher in the prototype chain is
changed? Or if <receiver>.[[Prototype]] itself changes? It seems like there are
a lot of things that invalidate the fast path, and checking them all could be
more expensive than it's worth

[caitp, 2016/07/26 21:09:45]

the map-check was not enough --- I changed it to a
`JSObject::PrototypeHasNoElements()` check. I think it should be fast enough
most of the time, but it might be better to just leave and go to the proper slow
path right away without the prototype elements test.

+        }
+      } else if (value->SameValueZero(*element_k)) {
+        return Just(true);
+      }
+    }
+    return Just(false);
+  }
 };