Revision: 12426
Author: [email protected]
Date: Mon Sep 3 05:31:24 2012
Log: Optimize dictionary enum generation.
Review URL: https://chromiumcodereview.appspot.com/10916076
http://code.google.com/p/v8/source/detail?r=12426
Modified:
/branches/bleeding_edge/src/handles.cc
/branches/bleeding_edge/src/objects.cc
/branches/bleeding_edge/src/objects.h
=======================================
--- /branches/bleeding_edge/src/handles.cc Tue Aug 28 07:20:50 2012
+++ /branches/bleeding_edge/src/handles.cc Mon Sep 3 05:31:24 2012
@@ -771,10 +771,36 @@
}
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;
}
}
=======================================
--- /branches/bleeding_edge/src/objects.cc Fri Aug 31 11:12:25 2012
+++ /branches/bleeding_edge/src/objects.cc Mon Sep 3 05:31:24 2012
@@ -12149,6 +12149,12 @@
return obj;
}
+
+void StringDictionary::DoGenerateNewEnumerationIndices(
+ Handle<StringDictionary> dictionary) {
+ CALL_HEAP_FUNCTION_VOID(dictionary->GetIsolate(),
+ dictionary->GenerateNewEnumerationIndices());
+}
template<typename Shape, typename Key>
MaybeObject* Dictionary<Shape, Key>::GenerateNewEnumerationIndices() {
@@ -12468,23 +12474,43 @@
}
-void StringDictionary::CopyEnumKeysTo(FixedArray* storage,
- FixedArray* sort_array) {
- ASSERT(storage->length() >= NumberOfEnumElements());
+void StringDictionary::CopyEnumKeysTo(FixedArray* storage) {
+ int length = storage->length();
+ ASSERT(length >= NumberOfEnumElements());
+ Heap* heap = GetHeap();
+ Object* undefined_value = heap->undefined_value();
int capacity = Capacity();
- int index = 0;
+ int properties = 0;
+
+ // Fill in the enumeration array by assigning enumerable keys at their
+ // enumeration index. This will leave holes in the array if there are
keys
+ // that are deleted or not enumerable.
for (int i = 0; i < capacity; i++) {
Object* k = KeyAt(i);
if (IsKey(k)) {
PropertyDetails details = DetailsAt(i);
if (details.IsDeleted() || details.IsDontEnum()) continue;
- storage->set(index, k);
- sort_array->set(index, Smi::FromInt(details.dictionary_index()));
- index++;
+ properties++;
+ storage->set(details.dictionary_index() - 1, k);
+ if (properties == length) break;
}
}
- storage->SortPairs(sort_array, sort_array->length());
- ASSERT(storage->length() >= index);
+
+ // There are holes in the enumeration array if less properties were
assigned
+ // than the length of the array. If so, crunch all the existing
properties
+ // together by shifting them to the left (maintaining the enumeration
order),
+ // and trimming of the right side of the array.
+ if (properties < length) {
+ properties = 0;
+ for (int i = 0; i < length; ++i) {
+ Object* value = storage->get(i);
+ if (value != undefined_value) {
+ storage->set(properties, value);
+ ++properties;
+ }
+ }
+ RightTrimFixedArray<FROM_MUTATOR>(heap, storage, length - properties);
+ }
}
=======================================
--- /branches/bleeding_edge/src/objects.h Tue Aug 28 07:20:50 2012
+++ /branches/bleeding_edge/src/objects.h Mon Sep 3 05:31:24 2012
@@ -3128,7 +3128,9 @@
}
// Copies enumerable keys to preallocated fixed array.
- void CopyEnumKeysTo(FixedArray* storage, FixedArray* sort_array);
+ void CopyEnumKeysTo(FixedArray* storage);
+ static void DoGenerateNewEnumerationIndices(
+ Handle<StringDictionary> dictionary);
// For transforming properties of a JSObject.
MUST_USE_RESULT MaybeObject* TransformPropertiesToFastFor(
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
