Reviewers: Toon Verwaest,
Message:
PTAL
Description:
Simplify GetEnumPropertyKeys and avoid trimming fixed arrays in large object
space.
BUG=352070
LOG=N
Please review this at https://codereview.chromium.org/198943002/
SVN Base: https://v8.googlecode.com/svn/branches/bleeding_edge
Affected files (+23, -53 lines):
M src/handles.cc
M src/objects.h
M src/objects.cc
Index: src/handles.cc
diff --git a/src/handles.cc b/src/handles.cc
index
899f9bfb5c8d0d15c1e5fb578670b09848c09835..398a68265cdf1c65d2b98a4d459ab972bbe34cef
100644
--- a/src/handles.cc
+++ b/src/handles.cc
@@ -712,35 +712,12 @@ Handle<FixedArray>
GetEnumPropertyKeys(Handle<JSObject> object,
return ReduceFixedArrayTo(storage, enum_size);
} else {
Handle<NameDictionary> dictionary(object->property_dictionary());
-
- int length = dictionary->NumberOfElements();
+ int length = dictionary->NumberOfEnumElements();
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 (!object->IsGlobalObject() && next_enumeration > (length * 3) / 2) {
- NameDictionary::DoGenerateNewEnumerationIndices(dictionary);
- next_enumeration = dictionary->NextEnumerationIndex();
- }
-
- Handle<FixedArray> storage =
- isolate->factory()->NewFixedArray(next_enumeration);
-
- storage = Handle<FixedArray>(dictionary->CopyEnumKeysTo(*storage));
- ASSERT(storage->length() ==
object->NumberOfLocalProperties(DONT_SHOW));
+ Handle<FixedArray> storage = isolate->factory()->NewFixedArray(length);
+ dictionary->CopyEnumKeysTo(*storage);
return storage;
}
}
Index: src/objects.cc
diff --git a/src/objects.cc b/src/objects.cc
index
27987f59e8d68cbe43bd183eb97a42df02219202..8b0acc2cfda25584a760138500265d0742199730
100644
--- a/src/objects.cc
+++ b/src/objects.cc
@@ -15529,45 +15529,38 @@ void Dictionary<Shape, Key>::CopyKeysTo(
}
-FixedArray* NameDictionary::CopyEnumKeysTo(FixedArray* storage) {
+struct EnumIndexComparator {
+ explicit EnumIndexComparator(NameDictionary* dict) : dict(dict) { }
+ bool operator() (Smi* a, Smi* b) {
+ PropertyDetails da(dict->DetailsAt(a->value()));
+ PropertyDetails db(dict->DetailsAt(b->value()));
+ return da.dictionary_index() < db.dictionary_index();
+ }
+ NameDictionary* dict;
+};
+
+
+void NameDictionary::CopyEnumKeysTo(FixedArray* storage) {
int length = storage->length();
- ASSERT(length >= NumberOfEnumElements());
- Heap* heap = GetHeap();
- Object* undefined_value = heap->undefined_value();
int capacity = Capacity();
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) && !k->IsSymbol()) {
PropertyDetails details = DetailsAt(i);
if (details.IsDeleted() || details.IsDontEnum()) continue;
+ storage->set(properties, Smi::FromInt(i));
properties++;
- storage->set(details.dictionary_index() - 1, k);
if (properties == length) break;
}
}
-
- // 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) {
- if (properties == 0) return heap->empty_fixed_array();
- 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);
+ EnumIndexComparator cmp(this);
+ Smi** start = reinterpret_cast<Smi**>(storage->GetFirstElementAddress());
+ std::sort(start, start + length, cmp);
+ for (int i = 0; i < length; i++) {
+ int index = Smi::cast(storage->get(i))->value();
+ storage->set(i, KeyAt(index));
}
- return storage;
}
Index: src/objects.h
diff --git a/src/objects.h b/src/objects.h
index
2521d83b7d37a067867ea39fa754c58e085187fd..ad58d37ab34a2bd8f68576b8e9c560a781bf31e0
100644
--- a/src/objects.h
+++ b/src/objects.h
@@ -4016,7 +4016,7 @@ class NameDictionary: public
Dictionary<NameDictionaryShape, Name*> {
}
// Copies enumerable keys to preallocated fixed array.
- FixedArray* CopyEnumKeysTo(FixedArray* storage);
+ void CopyEnumKeysTo(FixedArray* storage);
static void DoGenerateNewEnumerationIndices(
Handle<NameDictionary> dictionary);
--
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
---
You received this message because you are subscribed to the Google Groups "v8-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/d/optout.
