Optimize dictionary enum generation.

src/handles.cc

Index: src/handles.cc
diff --git a/src/handles.cc b/src/handles.cc
index adf435573e75e108c9706f0629200985409be087..3ac6d3df1687e94327e7216158824e25fba111d4 100644
--- a/src/handles.cc
+++ b/src/handles.cc
@@ -771,10 +771,36 @@ Handle<FixedArray> GetEnumPropertyKeys(Handle<JSObject> object,
     }
     return storage;
   } else {
-    int num_enum = object->NumberOfLocalProperties(DONT_ENUM);
-    Handle<FixedArray> storage = isolate->factory()->NewFixedArray(num_enum);
-    Handle<FixedArray> sort_array = isolate->factory()->NewFixedArray(num_enum);
-    object->property_dictionary()->CopyEnumKeysTo(*storage, *sort_array);
+    Handle<StringDictionary> dictionary(object->property_dictionary());
+
+    int length = dictionary->NumberOfElements();
+    if (length == 0) {
+      return Handle<FixedArray>(isolate->heap()->empty_fixed_array());
+    }
+
+    // The enumeration array is generated by allocating an array big enough to
+    // hold all properties that have been seen, whether they are are deleted or
+    // not. Subsequently all visible properties are added to the array. If some
+    // properties were not visible, the array is trimmed so it only contains
+    // visible properties. This improves over adding elements and sorting by
+    // index by having linear complexity rather than n*log(n).
+
+    // By comparing the monotonous NextEnumerationIndex to the NumberOfElements,
+    // we can predict the number of holes in the final array. If there will be
+    // more than 50% holes, regenerate the enumeration indices to reduce the
+    // number of holes to a minimum. This avoids allocating a large array if
+    // many properties were added but subsequently deleted.
+    int next_enumeration = dictionary->NextEnumerationIndex();
+    if (next_enumeration > (length * 3) / 2) {
+      StringDictionary::DoGenerateNewEnumerationIndices(dictionary);
+      next_enumeration = dictionary->NextEnumerationIndex();
+    }
+
+    Handle<FixedArray> storage =
+        isolate->factory()->NewFixedArray(next_enumeration);
+
+    dictionary->CopyEnumKeysTo(*storage);
+    ASSERT(storage->length() == object->NumberOfLocalProperties(DONT_ENUM));
     return storage;
   }
 }