Optimize dictionary enum generation.

src/handles.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 753 matching lines @@
     DescriptorArray* desc = object->map()->instance_descriptors();
     desc->SetEnumCache(*bridge_storage,
                        *storage,
                        indices.is_null() ? Object::cast(Smi::FromInt(0))
                                          : Object::cast(*indices));
     if (cache_result) {
       object->map()->SetEnumLength(index);
     }
     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;
   }
 }
 
 
 Handle<ObjectHashSet> ObjectHashSetAdd(Handle<ObjectHashSet> table,
                                        Handle<Object> key) {
   CALL_HEAP_FUNCTION(table->GetIsolate(),
                      table->Add(*key),
                      ObjectHashSet);
@@ skipping 212 matching lines @@
   data->next = prev_next_;
   data->limit = prev_limit_;
 #ifdef DEBUG
   handles_detached_ = true;
 #endif
   return deferred;
 }
 
 
 } }  // namespace v8::internal