Object.observe: change array truncation logic to efficiently handle large sparse arrays

src/objects.cc

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 9333 matching lines @@
   return this;
 }
 
 
 void JSArray::Expand(int required_size) {
   GetIsolate()->factory()->SetElementsCapacityAndLength(
       Handle<JSArray>(this), required_size, required_size);
 }
 
 
+// Returns false if the passed-in index is marked non-configurable,
+// which will cause the ES5 truncation operation to halt, and thus
+// no further old values need be collected.
+static bool GetOldValue(Isolate* isolate,
+                        Handle<JSObject> object,
+                        uint32_t index,
+                        List<Handle<Object> >* old_values,
+                        List<Handle<String> >* indices) {
+  PropertyAttributes attributes = object->GetLocalElementAttribute(index);
+  ASSERT(attributes != ABSENT);
+  if (attributes == DONT_DELETE) return false;
+  old_values->Add(object->GetLocalElementAccessorPair(index) == NULL
+      ? Object::GetElement(object, index)
+      : Handle<Object>::cast(isolate->factory()->the_hole_value()));
+  indices->Add(isolate->factory()->Uint32ToString(index));
+  return true;
+}
+
+
 MaybeObject* JSArray::SetElementsLength(Object* len) {
   // We should never end in here with a pixel or external array.
   ASSERT(AllowsSetElementsLength());
   if (!(FLAG_harmony_observation && map()->is_observed()))
     return GetElementsAccessor()->SetLength(this, len);
 
   Isolate* isolate = GetIsolate();
   HandleScope scope(isolate);
   Handle<JSArray> self(this);
   List<Handle<String> > indices;
   List<Handle<Object> > old_values;
   Handle<Object> old_length_handle(self->length());
   Handle<Object> new_length_handle(len);
   uint32_t old_length = 0;
   CHECK(old_length_handle->ToArrayIndex(&old_length));
   uint32_t new_length = 0;
   if (!new_length_handle->ToArrayIndex(&new_length))
     return Failure::InternalError();
 
-  // TODO(adamk): This loop can be very slow for arrays in dictionary mode.
-  // Find another way to iterate over arrays with dictionary elements.
-  for (uint32_t i = old_length - 1; i + 1 > new_length; --i) {
-    PropertyAttributes attributes = self->GetLocalElementAttribute(i);
-    if (attributes == ABSENT) continue;
-    // A non-configurable property will cause the truncation operation to
-    // stop at this index.
-    if (attributes == DONT_DELETE) break;
-    old_values.Add(
-        self->GetLocalElementAccessorPair(i) == NULL
-        ? Object::GetElement(self, i)
-        : Handle<Object>::cast(isolate->factory()->the_hole_value()));
-    indices.Add(isolate->factory()->Uint32ToString(i));
+  // Observed arrays should always be in dictionary mode;
+  // if they were in fast mode, the below is slower than necessary
+  // as it iterates over the array backing store multiple times.
+  ASSERT(self->HasDictionaryElements());
+  static const PropertyAttributes kNoAttrFilter = NONE;
+  int num_elements = self->NumberOfLocalElements(kNoAttrFilter);
+  if (num_elements > 0) {
+    if (old_length == static_cast<uint32_t>(num_elements)) {
+      // Simple case for arrays without holes.
+      for (uint32_t i = old_length - 1; i + 1 > new_length; --i) {
+        if (!GetOldValue(isolate, self, i, &old_values, &indices)) break;
+      }
+    } else {
+      // For sparse arrays, only iterate over existing elements.
+      Handle<FixedArray> keys = isolate->factory()->NewFixedArray(num_elements);
+      self->GetLocalElementKeys(*keys, kNoAttrFilter);
+      while (num_elements-- > 0) {
+        uint32_t index = NumberToUint32(keys->get(num_elements));
+        if (index < new_length) break;
+        if (!GetOldValue(isolate, self, index, &old_values, &indices)) break;
+      }
+    }
   }
 
   MaybeObject* result =
       self->GetElementsAccessor()->SetLength(*self, *new_length_handle);
   Handle<Object> hresult;
   if (!result->ToHandle(&hresult, isolate)) return result;
 
   CHECK(self->length()->ToArrayIndex(&new_length));
   if (old_length != new_length) {
     for (int i = 0; i < indices.length(); ++i) {
@@ skipping 4459 matching lines @@
   set_year(Smi::FromInt(year), SKIP_WRITE_BARRIER);
   set_month(Smi::FromInt(month), SKIP_WRITE_BARRIER);
   set_day(Smi::FromInt(day), SKIP_WRITE_BARRIER);
   set_weekday(Smi::FromInt(weekday), SKIP_WRITE_BARRIER);
   set_hour(Smi::FromInt(hour), SKIP_WRITE_BARRIER);
   set_min(Smi::FromInt(min), SKIP_WRITE_BARRIER);
   set_sec(Smi::FromInt(sec), SKIP_WRITE_BARRIER);
 }
 
 } }  // namespace v8::internal