From 5bf15c5d6c0e3851c392e0122dde94bae8727b8b Mon Sep 17 00:00:00 2001 From: "verwaest@chromium.org" Date: Tue, 18 Sep 2012 13:25:12 +0000 Subject: [PATCH] Preallocate space in descriptor arrays. Review URL: https://chromiumcodereview.appspot.com/10916336 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@12538 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/bootstrapper.cc | 21 ++++--- src/factory.cc | 23 +++++++- src/factory.h | 3 +- src/objects-debug.cc | 2 +- src/objects-inl.h | 56 +++++++++++++++++-- src/objects.cc | 140 ++++++++++++++++++++++++++-------------------- src/objects.h | 36 ++++++++---- test/cctest/test-alloc.cc | 2 +- 8 files changed, 192 insertions(+), 91 deletions(-) diff --git a/src/bootstrapper.cc b/src/bootstrapper.cc index 9de1058..9fb79e7 100644 --- a/src/bootstrapper.cc +++ b/src/bootstrapper.cc @@ -384,7 +384,7 @@ static Handle InstallFunction(Handle target, void Genesis::SetFunctionInstanceDescriptor( Handle map, PrototypePropertyMode prototypeMode) { int size = (prototypeMode == DONT_ADD_PROTOTYPE) ? 4 : 5; - Handle descriptors(factory()->NewDescriptorArray(size)); + Handle descriptors(factory()->NewDescriptorArray(0, size)); DescriptorArray::WhitenessWitness witness(*descriptors); Handle length(factory()->NewForeign(&Accessors::FunctionLength)); @@ -525,7 +525,7 @@ Handle Genesis::CreateEmptyFunction(Isolate* isolate) { void Genesis::SetStrictFunctionInstanceDescriptor( Handle map, PrototypePropertyMode prototypeMode) { int size = (prototypeMode == DONT_ADD_PROTOTYPE) ? 4 : 5; - Handle descriptors(factory()->NewDescriptorArray(size)); + Handle descriptors(factory()->NewDescriptorArray(0, size)); DescriptorArray::WhitenessWitness witness(*descriptors); Handle length(factory()->NewForeign(&Accessors::FunctionLength)); @@ -868,7 +868,8 @@ bool Genesis::InitializeGlobal(Handle inner_global, array_function->shared()->set_length(1); Handle initial_map(array_function->initial_map()); - Handle array_descriptors(factory->NewDescriptorArray(1)); + Handle array_descriptors( + factory->NewDescriptorArray(0, 1)); DescriptorArray::WhitenessWitness witness(*array_descriptors); Handle array_length(factory->NewForeign(&Accessors::ArrayLength)); @@ -915,7 +916,8 @@ bool Genesis::InitializeGlobal(Handle inner_global, Handle string_map = Handle(native_context()->string_function()->initial_map()); - Handle string_descriptors(factory->NewDescriptorArray(1)); + Handle string_descriptors( + factory->NewDescriptorArray(0, 1)); DescriptorArray::WhitenessWitness witness(*string_descriptors); Handle string_length( @@ -956,7 +958,7 @@ bool Genesis::InitializeGlobal(Handle inner_global, PropertyAttributes final = static_cast(DONT_ENUM | DONT_DELETE | READ_ONLY); - Handle descriptors = factory->NewDescriptorArray(5); + Handle descriptors = factory->NewDescriptorArray(0, 5); DescriptorArray::WhitenessWitness witness(*descriptors); Map::SetDescriptors(initial_map, descriptors); @@ -1140,7 +1142,7 @@ bool Genesis::InitializeGlobal(Handle inner_global, Handle map = factory->NewMap(JS_OBJECT_TYPE, Heap::kArgumentsObjectSizeStrict); // Create the descriptor array for the arguments object. - Handle descriptors = factory->NewDescriptorArray(3); + Handle descriptors = factory->NewDescriptorArray(0, 3); DescriptorArray::WhitenessWitness witness(*descriptors); Map::SetDescriptors(map, descriptors); @@ -1487,7 +1489,7 @@ bool Genesis::InstallNatives() { Handle script_map = Handle(script_fun->initial_map()); Handle script_descriptors( - factory()->NewDescriptorArray(13)); + factory()->NewDescriptorArray(0, 13)); DescriptorArray::WhitenessWitness witness(*script_descriptors); Handle script_source( @@ -1665,7 +1667,8 @@ bool Genesis::InstallNatives() { // Make "length" magic on instances. Handle initial_map(array_function->initial_map()); - Handle array_descriptors(factory()->NewDescriptorArray(1)); + Handle array_descriptors( + factory()->NewDescriptorArray(0, 1)); DescriptorArray::WhitenessWitness witness(*array_descriptors); Handle array_length(factory()->NewForeign( @@ -1765,7 +1768,7 @@ bool Genesis::InstallNatives() { // Update map with length accessor from Array and add "index" and "input". Handle reresult_descriptors = - factory()->NewDescriptorArray(3); + factory()->NewDescriptorArray(0, 3); DescriptorArray::WhitenessWitness witness(*reresult_descriptors); Map::SetDescriptors(initial_map, reresult_descriptors); diff --git a/src/factory.cc b/src/factory.cc index 462af59..a2bb939 100644 --- a/src/factory.cc +++ b/src/factory.cc @@ -112,10 +112,11 @@ Handle Factory::NewObjectHashTable(int at_least_space_for) { } -Handle Factory::NewDescriptorArray(int number_of_descriptors) { +Handle Factory::NewDescriptorArray(int number_of_descriptors, + int slack) { ASSERT(0 <= number_of_descriptors); CALL_HEAP_FUNCTION(isolate(), - DescriptorArray::Allocate(number_of_descriptors), + DescriptorArray::Allocate(number_of_descriptors, slack), DescriptorArray); } @@ -1284,10 +1285,26 @@ Handle Factory::CreateApiFunction( result->shared()->DontAdaptArguments(); // Recursively copy parent templates' accessors, 'data' may be modified. + int max_number_of_additional_properties = 0; + FunctionTemplateInfo* info = *obj; + while (true) { + Object* props = info->property_accessors(); + if (!props->IsUndefined()) { + Handle props_handle(props); + NeanderArray props_array(props_handle); + max_number_of_additional_properties += props_array.length(); + } + Object* parent = info->parent_template(); + if (parent->IsUndefined()) break; + info = FunctionTemplateInfo::cast(parent); + } + + Map::EnsureDescriptorSlack(map, max_number_of_additional_properties); + while (true) { Handle props = Handle(obj->property_accessors()); if (!props->IsUndefined()) { - Map::CopyAppendCallbackDescriptors(map, props); + Map::AppendCallbackDescriptors(map, props); } Handle parent = Handle(obj->parent_template()); if (parent->IsUndefined()) break; diff --git a/src/factory.h b/src/factory.h index e617abb..51065aa 100644 --- a/src/factory.h +++ b/src/factory.h @@ -66,7 +66,8 @@ class Factory { Handle NewObjectHashTable(int at_least_space_for); - Handle NewDescriptorArray(int number_of_descriptors); + Handle NewDescriptorArray(int number_of_descriptors, + int slack = 0); Handle NewDeoptimizationInputData( int deopt_entry_count, PretenureFlag pretenure); diff --git a/src/objects-debug.cc b/src/objects-debug.cc index d569161..6195bf5 100644 --- a/src/objects-debug.cc +++ b/src/objects-debug.cc @@ -905,7 +905,7 @@ bool DescriptorArray::IsSortedNoDuplicates(int valid_entries) { if (valid_entries == -1) valid_entries = number_of_descriptors(); String* current_key = NULL; uint32_t current = 0; - for (int i = 0; i < valid_entries; i++) { + for (int i = 0; i < number_of_descriptors(); i++) { String* key = GetSortedKey(i); if (key == current_key) { PrintDescriptors(); diff --git a/src/objects-inl.h b/src/objects-inl.h index 36d0b6c..c5ea5dc 100644 --- a/src/objects-inl.h +++ b/src/objects-inl.h @@ -1906,6 +1906,12 @@ bool DescriptorArray::IsEmpty() { } +void DescriptorArray::SetNumberOfDescriptors(int number_of_descriptors) { + WRITE_FIELD( + this, kDescriptorLengthOffset, Smi::FromInt(number_of_descriptors)); +} + + // Perform a binary search in a fixed array. Low and high are entry indices. If // there are three entries in this array it should be called with low=0 and // high=2. @@ -2138,11 +2144,30 @@ void DescriptorArray::Set(int descriptor_number, } +void DescriptorArray::Set(int descriptor_number, Descriptor* desc) { + // Range check. + ASSERT(descriptor_number < number_of_descriptors()); + ASSERT(desc->GetDetails().descriptor_index() <= + number_of_descriptors()); + ASSERT(desc->GetDetails().descriptor_index() > 0); + + set(ToKeyIndex(descriptor_number), desc->GetKey()); + set(ToValueIndex(descriptor_number), desc->GetValue()); + set(ToDetailsIndex(descriptor_number), desc->GetDetails().AsSmi()); +} + + +void DescriptorArray::EraseDescriptor(Heap* heap, int descriptor_number) { + set_null_unchecked(heap, ToKeyIndex(descriptor_number)); + set_null_unchecked(heap, ToValueIndex(descriptor_number)); +} + + void DescriptorArray::Append(Descriptor* desc, - const WhitenessWitness& witness, - int number_of_set_descriptors) { - int descriptor_number = number_of_set_descriptors; + const WhitenessWitness& witness) { + int descriptor_number = number_of_descriptors(); int enumeration_index = descriptor_number + 1; + SetNumberOfDescriptors(descriptor_number + 1); desc->SetEnumerationIndex(enumeration_index); Set(descriptor_number, desc, witness); @@ -2160,6 +2185,27 @@ void DescriptorArray::Append(Descriptor* desc, } +void DescriptorArray::Append(Descriptor* desc) { + int descriptor_number = number_of_descriptors(); + int enumeration_index = descriptor_number + 1; + SetNumberOfDescriptors(descriptor_number + 1); + desc->SetEnumerationIndex(enumeration_index); + Set(descriptor_number, desc); + + uint32_t hash = desc->GetKey()->Hash(); + + int insertion; + + for (insertion = descriptor_number; insertion > 0; --insertion) { + String* key = GetSortedKey(insertion - 1); + if (key->Hash() <= hash) break; + SetSortedKey(insertion, GetSortedKeyIndex(insertion - 1)); + } + + SetSortedKey(insertion, descriptor_number); +} + + void DescriptorArray::SwapSortedKeys(int first, int second) { int first_key = GetSortedKeyIndex(first); SetSortedKey(first, GetSortedKeyIndex(second)); @@ -3591,8 +3637,8 @@ void Map::AppendDescriptor(Descriptor* desc, const DescriptorArray::WhitenessWitness& witness) { DescriptorArray* descriptors = instance_descriptors(); int number_of_own_descriptors = NumberOfOwnDescriptors(); - ASSERT(number_of_own_descriptors < descriptors->number_of_descriptors()); - descriptors->Append(desc, witness, number_of_own_descriptors); + ASSERT(descriptors->number_of_descriptors() == number_of_own_descriptors); + descriptors->Append(desc, witness); SetNumberOfOwnDescriptors(number_of_own_descriptors + 1); } diff --git a/src/objects.cc b/src/objects.cc index d9e8b8b..12aeef7 100644 --- a/src/objects.cc +++ b/src/objects.cc @@ -2218,14 +2218,31 @@ static void RightTrimFixedArray(Heap* heap, FixedArray* elms, int to_trim) { } -void Map::CopyAppendCallbackDescriptors(Handle map, - Handle descriptors) { +void Map::EnsureDescriptorSlack(Handle map, int slack) { + Handle descriptors(map->instance_descriptors()); + if (slack <= descriptors->NumberOfSlackDescriptors()) return; + int number_of_descriptors = descriptors->number_of_descriptors(); + Isolate* isolate = map->GetIsolate(); + Handle new_descriptors = + isolate->factory()->NewDescriptorArray(number_of_descriptors, slack); + DescriptorArray::WhitenessWitness witness(*new_descriptors); + + for (int i = 0; i < number_of_descriptors; ++i) { + new_descriptors->CopyFrom(i, *descriptors, i, witness); + } + + Map::SetDescriptors(map, new_descriptors); +} + + +void Map::AppendCallbackDescriptors(Handle map, + Handle descriptors) { Isolate* isolate = map->GetIsolate(); Handle array(map->instance_descriptors()); - v8::NeanderArray callbacks(descriptors); + NeanderArray callbacks(descriptors); int nof_callbacks = callbacks.length(); - int descriptor_count = array->number_of_descriptors(); - ASSERT(descriptor_count == map->NumberOfOwnDescriptors()); + + ASSERT(array->NumberOfSlackDescriptors() >= nof_callbacks); // Ensure the keys are symbols before writing them into the instance // descriptor. Since it may cause a GC, it has to be done before we @@ -2238,51 +2255,23 @@ void Map::CopyAppendCallbackDescriptors(Handle map, entry->set_name(*key); } - Handle result = - isolate->factory()->NewDescriptorArray(descriptor_count + nof_callbacks); - - // Ensure that marking will not progress and change color of objects. - DescriptorArray::WhitenessWitness witness(*result); - - // Copy the descriptors from the array. - for (int i = 0; i < descriptor_count; i++) { - result->CopyFrom(i, *array, i, witness); - } - - // After this point the GC is not allowed to run anymore until the map is in a - // consistent state again, i.e., all the descriptors are appended and the - // descriptor array is trimmed to the right size. - Map::SetDescriptors(map, result); + int nof = map->NumberOfOwnDescriptors(); // Fill in new callback descriptors. Process the callbacks from // back to front so that the last callback with a given name takes // precedence over previously added callbacks with that name. - int nof = descriptor_count; for (int i = nof_callbacks - 1; i >= 0; i--) { AccessorInfo* entry = AccessorInfo::cast(callbacks.get(i)); String* key = String::cast(entry->name()); // Check if a descriptor with this name already exists before writing. - if (result->Search(key, nof) == DescriptorArray::kNotFound) { + if (array->Search(key, nof) == DescriptorArray::kNotFound) { CallbacksDescriptor desc(key, entry, entry->property_attributes()); - map->AppendDescriptor(&desc, witness); + array->Append(&desc); nof += 1; } } - ASSERT(nof == map->NumberOfOwnDescriptors()); - - // Reinstall the original descriptor array if no new elements were added. - if (nof == descriptor_count) { - Map::SetDescriptors(map, array); - return; - } - - // If duplicates were detected, trim the descriptor array to the right size. - int new_array_size = DescriptorArray::LengthFor(nof); - if (new_array_size < result->length()) { - RightTrimFixedArray( - isolate->heap(), *result, result->length() - new_array_size); - } + map->SetNumberOfOwnDescriptors(nof); } @@ -5018,25 +5007,37 @@ MaybeObject* Map::ShareDescriptor(Descriptor* descriptor) { int old_size = descriptors->number_of_descriptors(); DescriptorArray* new_descriptors; - MaybeObject* maybe_descriptors = DescriptorArray::Allocate(old_size + 1); - if (!maybe_descriptors->To(&new_descriptors)) return maybe_descriptors; - DescriptorArray::WhitenessWitness witness(new_descriptors); - for (int i = 0; i < old_size; ++i) { - new_descriptors->CopyFrom(i, descriptors, i, witness); - } - new_descriptors->Append(descriptor, witness, old_size); + if (descriptors->NumberOfSlackDescriptors() > 0) { + new_descriptors = descriptors; + new_descriptors->Append(descriptor); + } else { + // Descriptor arrays grow by 50%. + MaybeObject* maybe_descriptors = DescriptorArray::Allocate( + old_size, old_size < 4 ? 1 : old_size / 2); + if (!maybe_descriptors->To(&new_descriptors)) return maybe_descriptors; + + DescriptorArray::WhitenessWitness witness(new_descriptors); + + // Copy the descriptors, inserting a descriptor. + for (int i = 0; i < old_size; ++i) { + new_descriptors->CopyFrom(i, descriptors, i, witness); + } + + new_descriptors->Append(descriptor, witness); - // If the source descriptors had an enum cache we copy it. This ensures that - // the maps to which we push the new descriptor array back can rely on a - // cache always being available once it is set. If the map has more - // enumerated descriptors than available in the original cache, the cache - // will be lazily replaced by the extended cache when needed. - if (descriptors->HasEnumCache()) { - new_descriptors->CopyEnumCacheFrom(descriptors); + // If the source descriptors had an enum cache we copy it. This ensures that + // the maps to which we push the new descriptor array back can rely on a + // cache always being available once it is set. If the map has more + // enumerated descriptors than available in the original cache, the cache + // will be lazily replaced by the extended cache when needed. + if (descriptors->HasEnumCache()) { + new_descriptors->CopyEnumCacheFrom(descriptors); + } } transitions->set_descriptors(new_descriptors); + set_transitions(transitions); result->SetBackPointer(this); set_owns_descriptors(false); @@ -5207,7 +5208,7 @@ MaybeObject* Map::CopyAddDescriptor(Descriptor* descriptor, } DescriptorArray* new_descriptors; - MaybeObject* maybe_descriptors = DescriptorArray::Allocate(old_size + 1); + MaybeObject* maybe_descriptors = DescriptorArray::Allocate(old_size, 1); if (!maybe_descriptors->To(&new_descriptors)) return maybe_descriptors; DescriptorArray::WhitenessWitness witness(new_descriptors); @@ -5217,10 +5218,17 @@ MaybeObject* Map::CopyAddDescriptor(Descriptor* descriptor, new_descriptors->CopyFrom(i, descriptors, i, witness); } - new_descriptors->Set(old_size, descriptor, witness); - new_descriptors->Sort(); + if (old_size != descriptors->number_of_descriptors()) { + new_descriptors->SetNumberOfDescriptors(new_size); + new_descriptors->Set(old_size, descriptor, witness); + new_descriptors->Sort(); + } else { + new_descriptors->Append(descriptor, witness); + } - return CopyReplaceDescriptors(new_descriptors, descriptor->GetKey(), flag); + String* key = descriptor->GetKey(); + + return CopyReplaceDescriptors(new_descriptors, key, flag); } @@ -6071,16 +6079,17 @@ bool FixedArray::IsEqualTo(FixedArray* other) { #endif -MaybeObject* DescriptorArray::Allocate(int number_of_descriptors) { +MaybeObject* DescriptorArray::Allocate(int number_of_descriptors, int slack) { Heap* heap = Isolate::Current()->heap(); // Do not use DescriptorArray::cast on incomplete object. + int size = number_of_descriptors + slack; + if (size == 0) return heap->empty_descriptor_array(); FixedArray* result; - if (number_of_descriptors == 0) return heap->empty_descriptor_array(); // Allocate the array of keys. - MaybeObject* maybe_array = - heap->AllocateFixedArray(LengthFor(number_of_descriptors)); + MaybeObject* maybe_array = heap->AllocateFixedArray(LengthFor(size)); if (!maybe_array->To(&result)) return maybe_array; + result->set(kDescriptorLengthIndex, Smi::FromInt(number_of_descriptors)); result->set(kEnumCacheIndex, Smi::FromInt(0)); return result; } @@ -7495,8 +7504,17 @@ void Map::ClearNonLiveTransitions(Heap* heap) { int number_of_descriptors = descriptors->number_of_descriptors(); int to_trim = number_of_descriptors - number_of_own_descriptors; if (to_trim > 0) { - RightTrimFixedArray( - heap, descriptors, to_trim * DescriptorArray::kDescriptorSize); + // Maximally keep 50% of unused descriptors. + int keep = Min(to_trim, number_of_own_descriptors / 2); + for (int i = number_of_own_descriptors; + i < number_of_own_descriptors + keep; + ++i) { + descriptors->EraseDescriptor(heap, i); + } + if (to_trim > keep) { + RightTrimFixedArray(heap, descriptors, to_trim - keep); + } + descriptors->SetNumberOfDescriptors(number_of_own_descriptors); if (descriptors->HasEnumCache()) { int live_enum = NumberOfDescribedProperties(OWN_DESCRIPTORS, DONT_ENUM); diff --git a/src/objects.h b/src/objects.h index be25736..a4653aa 100644 --- a/src/objects.h +++ b/src/objects.h @@ -2484,9 +2484,19 @@ class DescriptorArray: public FixedArray { int number_of_descriptors() { ASSERT(length() >= kFirstIndex || IsEmpty()); int len = length(); - return len <= kFirstIndex ? 0 : (len - kFirstIndex) / kDescriptorSize; + return len == 0 ? 0 : Smi::cast(get(kDescriptorLengthIndex))->value(); } + int number_of_descriptors_storage() { + int len = length(); + return len == 0 ? 0 : (len - kFirstIndex) / kDescriptorSize; + } + + int NumberOfSlackDescriptors() { + return number_of_descriptors_storage() - number_of_descriptors(); + } + + inline void SetNumberOfDescriptors(int number_of_descriptors); inline int number_of_entries() { return number_of_descriptors(); } bool HasEnumCache() { @@ -2538,13 +2548,14 @@ class DescriptorArray: public FixedArray { inline void Set(int descriptor_number, Descriptor* desc, const WhitenessWitness&); + inline void Set(int descriptor_number, Descriptor* desc); + inline void EraseDescriptor(Heap* heap, int descriptor_number); // Append automatically sets the enumeration index. This should only be used // to add descriptors in bulk at the end, followed by sorting the descriptor // array. - inline void Append(Descriptor* desc, - const WhitenessWitness&, - int number_of_set_descriptors); + inline void Append(Descriptor* desc, const WhitenessWitness&); + inline void Append(Descriptor* desc); // Transfer a complete descriptor from the src descriptor array to this // descriptor array. @@ -2567,7 +2578,8 @@ class DescriptorArray: public FixedArray { // Allocates a DescriptorArray, but returns the singleton // empty descriptor array object if number_of_descriptors is 0. - MUST_USE_RESULT static MaybeObject* Allocate(int number_of_descriptors); + MUST_USE_RESULT static MaybeObject* Allocate(int number_of_descriptors, + int slack = 0); // Casting. static inline DescriptorArray* cast(Object* obj); @@ -2575,8 +2587,9 @@ class DescriptorArray: public FixedArray { // Constant for denoting key was not found. static const int kNotFound = -1; - static const int kEnumCacheIndex = 0; - static const int kFirstIndex = 1; + static const int kDescriptorLengthIndex = 0; + static const int kEnumCacheIndex = 1; + static const int kFirstIndex = 2; // The length of the "bridge" to the enum cache. static const int kEnumCacheBridgeLength = 2; @@ -2584,7 +2597,8 @@ class DescriptorArray: public FixedArray { static const int kEnumCacheBridgeIndicesCacheIndex = 1; // Layout description. - static const int kEnumCacheOffset = FixedArray::kHeaderSize; + static const int kDescriptorLengthOffset = FixedArray::kHeaderSize; + static const int kEnumCacheOffset = kDescriptorLengthOffset + kPointerSize; static const int kFirstOffset = kEnumCacheOffset + kPointerSize; // Layout description for the bridge array. @@ -5011,8 +5025,10 @@ class Map: public HeapObject { // Extend the descriptor array of the map with the list of descriptors. // In case of duplicates, the latest descriptor is used. - static void CopyAppendCallbackDescriptors(Handle map, - Handle descriptors); + static void AppendCallbackDescriptors(Handle map, + Handle descriptors); + + static void EnsureDescriptorSlack(Handle map, int slack); // Returns the found code or undefined if absent. Object* FindInCodeCache(String* name, Code::Flags flags); diff --git a/test/cctest/test-alloc.cc b/test/cctest/test-alloc.cc index 50e60da..24c7f1f 100644 --- a/test/cctest/test-alloc.cc +++ b/test/cctest/test-alloc.cc @@ -155,7 +155,7 @@ TEST(StressJS) { FACTORY->NewStringFromAscii(Vector("get", 3)); ASSERT(instance_descriptors->IsEmpty()); - Handle new_descriptors = FACTORY->NewDescriptorArray(1); + Handle new_descriptors = FACTORY->NewDescriptorArray(0, 1); v8::internal::DescriptorArray::WhitenessWitness witness(*new_descriptors); v8::internal::Map::SetDescriptors(map, new_descriptors); -- 2.7.4