[builtins] implement Array.prototype.includes in TurboFan

src/elements.cc

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/elements.h"
 
 #include "src/arguments.h"
 #include "src/conversions.h"
 #include "src/factory.h"
 #include "src/isolate-inl.h"
@@ skipping 450 matching lines @@
   } cmp;
   Object** start =
       reinterpret_cast<Object**>(indices->GetFirstElementAddress());
   std::sort(start, start + sort_size, cmp);
   if (write_barrier_mode != SKIP_WRITE_BARRIER) {
     FIXED_ARRAY_ELEMENTS_WRITE_BARRIER(indices->GetIsolate()->heap(), *indices,
                                        0, sort_size);
   }
 }
 
+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
 // implementation differs from the base class implementation.
 //
 // This class is intended to be used in the following way:
 //
 //   class SomeElementsAccessor :
 //       public ElementsAccessorBase<SomeElementsAccessor,
 //                                   BackingStoreClass> {
@@ skipping 558 matching lines @@
 
   static uint32_t GetCapacityImpl(JSObject* holder,
                                   FixedArrayBase* backing_store) {
     return backing_store->length();
   }
 
   uint32_t GetCapacity(JSObject* holder, FixedArrayBase* backing_store) final {
     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;
   }
 
   static uint32_t GetEntryForIndexImpl(JSObject* holder,
                                        FixedArrayBase* backing_store,
                                        uint32_t index, PropertyFilter filter) {
     if (IsHoleyElementsKind(kind())) {
       return index < Subclass::GetCapacityImpl(holder, backing_store) &&
@@ skipping 316 matching lines @@
       if (k == *undefined) continue;
       if (k == *the_hole) continue;
       if (dictionary->IsDeleted(i)) continue;
       Object* value = dictionary->ValueAt(i);
       DCHECK(!value->IsTheHole(isolate));
       DCHECK(!value->IsAccessorPair());
       DCHECK(!value->IsAccessorInfo());
       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);
+  }
 };
 
 
 // Super class for all fast element arrays.
 template <typename Subclass, typename KindTraits>
 class FastElementsAccessor : public ElementsAccessorBase<Subclass, KindTraits> {
  public:
   explicit FastElementsAccessor(const char* name)
       : ElementsAccessorBase<Subclass, KindTraits>(name) {}
 
@@ skipping 340 matching lines @@
         DisallowHeapAllocation no_gc;
         heap->MoveElements(FixedArray::cast(*dst_elms), dst_index, src_index,
                            len);
       }
     }
     if (hole_start != hole_end) {
       dst_elms->FillWithHoles(hole_start, hole_end);
     }
   }
 
+  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,
                                Handle<FixedArrayBase> backing_store,
                                uint32_t start, uint32_t delete_count,
                                uint32_t add_count, uint32_t len,
                                uint32_t new_length) {
     const int move_left_count = len - delete_count - start;
     const int move_left_dst_index = start + add_count;
     Subclass::MoveElements(isolate, receiver, backing_store,
@@ skipping 668 matching lines @@
         list->set(insertion_index, Smi::FromInt(i), SKIP_WRITE_BARRIER);
       }
       insertion_index++;
     }
 
     Handle<FixedArrayBase> store(FixedArrayBase::cast(parameter_map->get(1)));
     return ArgumentsAccessor::DirectCollectElementIndicesImpl(
         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);
+  }
 };
 
 
 class SlowSloppyArgumentsElementsAccessor
     : public SloppyArgumentsElementsAccessor<
           SlowSloppyArgumentsElementsAccessor, DictionaryElementsAccessor,
           ElementsKindTraits<SLOW_SLOPPY_ARGUMENTS_ELEMENTS> > {
  public:
   explicit SlowSloppyArgumentsElementsAccessor(const char* name)
       : SloppyArgumentsElementsAccessor<
@@ skipping 587 matching lines @@
     insertion_index += len;
   }
 
   DCHECK_EQ(insertion_index, result_len);
   return result_array;
 }
 
 ElementsAccessor** ElementsAccessor::elements_accessors_ = NULL;
 }  // namespace internal
 }  // namespace v8