Revision: 12136
Author: [email protected]
Date: Wed Jul 18 08:38:58 2012
Log: Let DescriptorArray::Append insert at proper position, avoiding
need for resorting.
Using insertion-sort won't have too much of an overhead for the short
arrays for bootstrapping (which are probably snapshot anyway).
CopyAppendCallbackDescriptors was extending and sorting the array in a
loop. By using an append that inserts at the right position we do not need
to resort in each iteration.
Additionally remove Sort and rename SortUnchecked to Sort. The
IsSortedNoDuplicates check is moved into InitializeDescriptor.
Review URL: https://chromiumcodereview.appspot.com/10808011
http://code.google.com/p/v8/source/detail?r=12136
Modified:
/branches/bleeding_edge/src/bootstrapper.cc
/branches/bleeding_edge/src/factory.cc
/branches/bleeding_edge/src/factory.h
/branches/bleeding_edge/src/heap.cc
/branches/bleeding_edge/src/objects-inl.h
/branches/bleeding_edge/src/objects.cc
/branches/bleeding_edge/src/objects.h
=======================================
--- /branches/bleeding_edge/src/bootstrapper.cc Wed Jul 18 07:00:58 2012
+++ /branches/bleeding_edge/src/bootstrapper.cc Wed Jul 18 08:38:58 2012
@@ -255,16 +255,16 @@
Handle<Map> CreateFunctionMap(PrototypePropertyMode prototype_mode);
- Handle<DescriptorArray> ComputeFunctionInstanceDescriptor(
- PrototypePropertyMode prototypeMode);
+ void SetFunctionInstanceDescriptor(Handle<Map> map,
+ PrototypePropertyMode prototypeMode);
void MakeFunctionInstancePrototypeWritable();
Handle<Map> CreateStrictModeFunctionMap(
PrototypePropertyMode prototype_mode,
Handle<JSFunction> empty_function);
- Handle<DescriptorArray> ComputeStrictFunctionInstanceDescriptor(
- PrototypePropertyMode propertyMode);
+ void SetStrictFunctionInstanceDescriptor(Handle<Map> map,
+ PrototypePropertyMode
propertyMode);
static bool CompileBuiltin(Isolate* isolate, int index);
static bool CompileExperimentalBuiltin(Isolate* isolate, int index);
@@ -383,8 +383,8 @@
}
-Handle<DescriptorArray> Genesis::ComputeFunctionInstanceDescriptor(
- PrototypePropertyMode prototypeMode) {
+void Genesis::SetFunctionInstanceDescriptor(
+ Handle<Map> map, PrototypePropertyMode prototypeMode) {
int size = (prototypeMode == DONT_ADD_PROTOTYPE) ? 4 : 5;
Handle<DescriptorArray> descriptors(factory()->NewDescriptorArray(size));
PropertyAttributes attribs = static_cast<PropertyAttributes>(
@@ -422,16 +422,13 @@
descriptors->Append(&d, witness);
}
- descriptors->Sort(witness);
- return descriptors;
+ map->set_instance_descriptors(*descriptors);
}
Handle<Map> Genesis::CreateFunctionMap(PrototypePropertyMode
prototype_mode) {
Handle<Map> map = factory()->NewMap(JS_FUNCTION_TYPE, JSFunction::kSize);
- Handle<DescriptorArray> descriptors =
- ComputeFunctionInstanceDescriptor(prototype_mode);
- map->set_instance_descriptors(*descriptors);
+ SetFunctionInstanceDescriptor(map, prototype_mode);
map->set_function_with_prototype(prototype_mode != DONT_ADD_PROTOTYPE);
return map;
}
@@ -487,8 +484,6 @@
global_context()->set_initial_object_prototype(*prototype);
SetPrototype(object_fun, prototype);
- object_function_map->set_instance_descriptors(
- heap->empty_descriptor_array());
}
// Allocate the empty function as the prototype for function ECMAScript
@@ -527,8 +522,8 @@
}
-Handle<DescriptorArray> Genesis::ComputeStrictFunctionInstanceDescriptor(
- PrototypePropertyMode prototypeMode) {
+void Genesis::SetStrictFunctionInstanceDescriptor(
+ Handle<Map> map, PrototypePropertyMode prototypeMode) {
int size = (prototypeMode == DONT_ADD_PROTOTYPE) ? 4 : 5;
Handle<DescriptorArray> descriptors(factory()->NewDescriptorArray(size));
PropertyAttributes attribs = static_cast<PropertyAttributes>(
@@ -567,8 +562,7 @@
descriptors->Append(&d, witness);
}
- descriptors->Sort(witness);
- return descriptors;
+ map->set_instance_descriptors(*descriptors);
}
@@ -596,9 +590,7 @@
PrototypePropertyMode prototype_mode,
Handle<JSFunction> empty_function) {
Handle<Map> map = factory()->NewMap(JS_FUNCTION_TYPE, JSFunction::kSize);
- Handle<DescriptorArray> descriptors =
- ComputeStrictFunctionInstanceDescriptor(prototype_mode);
- map->set_instance_descriptors(*descriptors);
+ SetStrictFunctionInstanceDescriptor(map, prototype_mode);
map->set_function_with_prototype(prototype_mode != DONT_ADD_PROTOTYPE);
map->set_prototype(*empty_function);
return map;
@@ -1000,14 +992,13 @@
writable);
descriptors->Append(&field, witness);
}
- descriptors->Sort(witness);
+ initial_map->set_instance_descriptors(*descriptors);
initial_map->set_inobject_properties(5);
initial_map->set_pre_allocated_property_fields(5);
initial_map->set_unused_property_fields(0);
initial_map->set_instance_size(
initial_map->instance_size() + 5 * kPointerSize);
- initial_map->set_instance_descriptors(*descriptors);
initial_map->set_visitor_id(StaticVisitorBase::GetVisitorId(*initial_map));
// RegExp prototype object is itself a RegExp.
@@ -1141,6 +1132,9 @@
caller->set_getter(*throw_function);
caller->set_setter(*throw_function);
+ // Create the map. Allocate one in-object field for length.
+ Handle<Map> map = factory->NewMap(JS_OBJECT_TYPE,
+ Heap::kArgumentsObjectSizeStrict);
// Create the descriptor array for the arguments object.
Handle<DescriptorArray> descriptors = factory->NewDescriptorArray(3);
DescriptorArray::WhitenessWitness witness(*descriptors);
@@ -1160,12 +1154,8 @@
attributes);
descriptors->Append(&d, witness);
}
- descriptors->Sort(witness);
-
- // Create the map. Allocate one in-object field for length.
- Handle<Map> map = factory->NewMap(JS_OBJECT_TYPE,
- Heap::kArgumentsObjectSizeStrict);
map->set_instance_descriptors(*descriptors);
+
map->set_function_with_prototype(true);
map->set_prototype(global_context()->object_function()->prototype());
map->set_pre_allocated_property_fields(1);
@@ -1487,6 +1477,8 @@
PropertyAttributes attribs =
static_cast<PropertyAttributes>(DONT_ENUM | DONT_DELETE |
READ_ONLY);
+ Handle<Map> script_map = Handle<Map>(script_fun->initial_map());
+
Handle<DescriptorArray> script_descriptors(
factory()->NewDescriptorArray(13));
@@ -1591,9 +1583,6 @@
script_descriptors->Append(&d, witness);
}
- script_descriptors->Sort(witness);
-
- Handle<Map> script_map = Handle<Map>(script_fun->initial_map());
script_map->set_instance_descriptors(*script_descriptors);
// Allocate the empty script.
@@ -1663,8 +1652,7 @@
array_descriptors->Append(&d, witness);
}
- array_function->initial_map()->set_instance_descriptors(
- *array_descriptors);
+
array_function->initial_map()->set_instance_descriptors(*array_descriptors);
global_context()->set_internal_array_function(*array_function);
}
@@ -1775,12 +1763,11 @@
NONE);
reresult_descriptors->Append(&input_field, witness);
}
- reresult_descriptors->Sort(witness);
+ initial_map->set_instance_descriptors(*reresult_descriptors);
initial_map->set_inobject_properties(2);
initial_map->set_pre_allocated_property_fields(2);
initial_map->set_unused_property_fields(0);
- initial_map->set_instance_descriptors(*reresult_descriptors);
global_context()->set_regexp_result_map(*initial_map);
}
=======================================
--- /branches/bleeding_edge/src/factory.cc Wed Jul 18 07:00:58 2012
+++ /branches/bleeding_edge/src/factory.cc Wed Jul 18 08:38:58 2012
@@ -892,9 +892,9 @@
}
-Handle<DescriptorArray> Factory::CopyAppendCallbackDescriptors(
- Handle<DescriptorArray> array,
- Handle<Object> descriptors) {
+void Factory::CopyAppendCallbackDescriptors(Handle<Map> map,
+ Handle<Object> descriptors) {
+ Handle<DescriptorArray> array(map->instance_descriptors());
v8::NeanderArray callbacks(descriptors);
int nof_callbacks = callbacks.length();
int descriptor_count = array->number_of_descriptors();
@@ -922,10 +922,7 @@
Handle<String> key =
SymbolFromString(Handle<String>(String::cast(entry->name())));
// Check if a descriptor with this name already exists before writing.
- if (LinearSearch(*result,
- EXPECT_UNSORTED,
- *key,
- result->NumberOfSetDescriptors()) ==
+ if (LinearSearch(*result, *key, result->NumberOfSetDescriptors()) ==
DescriptorArray::kNotFound) {
CallbacksDescriptor desc(*key, *entry, entry->property_attributes());
result->Append(&desc, witness);
@@ -933,8 +930,8 @@
}
int new_number_of_descriptors = result->NumberOfSetDescriptors();
- // Return the old descriptor array if there were no new elements.
- if (new_number_of_descriptors == descriptor_count) return array;
+ // Don't replace the descriptor array if there were no new elements.
+ if (new_number_of_descriptors == descriptor_count) return;
// If duplicates were detected, allocate a result of the right size
// and transfer the elements.
@@ -944,12 +941,11 @@
for (int i = 0; i < new_number_of_descriptors; i++) {
new_result->CopyFrom(i, *result, i, witness);
}
+ new_result->SetLastAdded(result->LastAdded());
result = new_result;
}
- // Sort the result before returning.
- result->Sort(witness);
- return result;
+ map->set_instance_descriptors(*result);
}
@@ -1337,20 +1333,15 @@
result->shared()->DontAdaptArguments();
// Recursively copy parent templates' accessors, 'data' may be modified.
- Handle<DescriptorArray> array =
- Handle<DescriptorArray>(map->instance_descriptors());
while (true) {
Handle<Object> props = Handle<Object>(obj->property_accessors());
if (!props->IsUndefined()) {
- array = CopyAppendCallbackDescriptors(array, props);
+ CopyAppendCallbackDescriptors(map, props);
}
Handle<Object> parent = Handle<Object>(obj->parent_template());
if (parent->IsUndefined()) break;
obj = Handle<FunctionTemplateInfo>::cast(parent);
}
- if (!array->IsEmpty()) {
- map->set_instance_descriptors(*array);
- }
ASSERT(result->shared()->IsApiFunction());
return result;
=======================================
--- /branches/bleeding_edge/src/factory.h Wed Jul 18 07:00:58 2012
+++ /branches/bleeding_edge/src/factory.h Wed Jul 18 08:38:58 2012
@@ -496,9 +496,8 @@
Handle<String> name,
LanguageMode language_mode);
- Handle<DescriptorArray> CopyAppendCallbackDescriptors(
- Handle<DescriptorArray> array,
- Handle<Object> descriptors);
+ void CopyAppendCallbackDescriptors(Handle<Map> map,
+ Handle<Object> descriptors);
// Create a new map cache.
Handle<MapCache> NewMapCache(int at_least_space_for);
=======================================
--- /branches/bleeding_edge/src/heap.cc Wed Jul 18 07:15:02 2012
+++ /branches/bleeding_edge/src/heap.cc Wed Jul 18 08:38:58 2012
@@ -3824,21 +3824,18 @@
// suggested by the function.
int instance_size = fun->shared()->CalculateInstanceSize();
int in_object_properties = fun->shared()->CalculateInObjectProperties();
- Object* map_obj;
- { MaybeObject* maybe_map_obj = AllocateMap(JS_OBJECT_TYPE,
instance_size);
- if (!maybe_map_obj->ToObject(&map_obj)) return maybe_map_obj;
- }
+ Map* map;
+ MaybeObject* maybe_map = AllocateMap(JS_OBJECT_TYPE, instance_size);
+ if (!maybe_map->To(&map)) return maybe_map;
// Fetch or allocate prototype.
Object* prototype;
if (fun->has_instance_prototype()) {
prototype = fun->instance_prototype();
} else {
- { MaybeObject* maybe_prototype = AllocateFunctionPrototype(fun);
- if (!maybe_prototype->ToObject(&prototype)) return maybe_prototype;
- }
- }
- Map* map = Map::cast(map_obj);
+ MaybeObject* maybe_prototype = AllocateFunctionPrototype(fun);
+ if (!maybe_prototype->To(&prototype)) return maybe_prototype;
+ }
map->set_inobject_properties(in_object_properties);
map->set_unused_property_fields(in_object_properties);
map->set_prototype(prototype);
@@ -3857,12 +3854,10 @@
fun->shared()->ForbidInlineConstructor();
} else {
DescriptorArray* descriptors;
- { MaybeObject* maybe_descriptors_obj =
- DescriptorArray::Allocate(count,
DescriptorArray::MAY_BE_SHARED);
- if (!maybe_descriptors_obj->To<DescriptorArray>(&descriptors)) {
- return maybe_descriptors_obj;
- }
- }
+ MaybeObject* maybe_descriptors =
+ DescriptorArray::Allocate(count, DescriptorArray::MAY_BE_SHARED);
+ if (!maybe_descriptors->To(&descriptors)) return maybe_descriptors;
+
DescriptorArray::WhitenessWitness witness(descriptors);
for (int i = 0; i < count; i++) {
String* name = fun->shared()->GetThisPropertyAssignmentName(i);
@@ -3870,7 +3865,7 @@
FieldDescriptor field(name, i, NONE, i + 1);
descriptors->Set(i, &field, witness);
}
- descriptors->SortUnchecked(witness);
+ descriptors->Sort(witness);
// The descriptors may contain duplicates because the compiler does
not
// guarantee the uniqueness of property names (it would have required
@@ -3879,7 +3874,7 @@
if (HasDuplicates(descriptors)) {
fun->shared()->ForbidInlineConstructor();
} else {
- map->set_instance_descriptors(descriptors);
+ map->InitializeDescriptors(descriptors);
map->set_pre_allocated_property_fields(count);
map->set_unused_property_fields(in_object_properties - count);
}
=======================================
--- /branches/bleeding_edge/src/objects-inl.h Wed Jul 18 06:39:53 2012
+++ /branches/bleeding_edge/src/objects-inl.h Wed Jul 18 08:38:58 2012
@@ -1952,12 +1952,12 @@
// Perform a linear search in this fixed array. len is the number of entry
// indices that are valid.
template<typename T>
-int LinearSearch(T* array, SearchMode mode, String* name, int len) {
+int LinearSearch(T* array, String* name, int len) {
uint32_t hash = name->Hash();
for (int number = 0; number < len; number++) {
String* entry = array->GetKey(number);
uint32_t current_hash = entry->Hash();
- if (mode == EXPECT_SORTED && current_hash > hash) break;
+ if (current_hash > hash) break;
if (current_hash == hash && name->Equals(entry)) return number;
}
return T::kNotFound;
@@ -1975,7 +1975,7 @@
// Fast case: do linear search for small arrays.
const int kMaxElementsForLinearSearch = 8;
if (StringShape(name).IsSymbol() && nof < kMaxElementsForLinearSearch) {
- return LinearSearch(array, EXPECT_SORTED, name, nof);
+ return LinearSearch(array, name, nof);
}
// Slow case: perform binary search.
@@ -2115,6 +2115,18 @@
int descriptor_number = NumberOfSetDescriptors();
int enumeration_index = descriptor_number + 1;
desc->SetEnumerationIndex(enumeration_index);
+
+ uint32_t hash = desc->GetKey()->Hash();
+
+ for (; descriptor_number > 0; --descriptor_number) {
+ String* key = GetKey(descriptor_number - 1);
+ if (key->Hash() <= hash) break;
+ Object* value = GetValue(descriptor_number - 1);
+ PropertyDetails details = GetDetails(descriptor_number - 1);
+ Descriptor moved_descriptor(key, value, details);
+ Set(descriptor_number, &moved_descriptor, witness);
+ }
+
Set(descriptor_number, desc, witness);
SetLastAdded(descriptor_number);
}
@@ -3487,6 +3499,39 @@
CONDITIONAL_WRITE_BARRIER(
heap, this, kInstanceDescriptorsOrBackPointerOffset, value, mode);
}
+
+
+void Map::InitializeDescriptors(DescriptorArray* descriptors) {
+ int len = descriptors->number_of_descriptors();
+ SLOW_ASSERT(descriptors->IsSortedNoDuplicates());
+
+#ifdef DEBUG
+ bool* used_indices =
+ reinterpret_cast<bool*>(alloca(sizeof(*used_indices) * len));
+ for (int i = 0; i < len; ++i) used_indices[i] = false;
+
+ // Ensure that all enumeration indexes between 1 and length occur
uniquely in
+ // the descriptor array.
+ for (int i = 0; i < len; ++i) {
+ int enum_index = descriptors->GetDetails(i).index() -
+ PropertyDetails::kInitialIndex;
+ ASSERT(!used_indices[enum_index]);
+ used_indices[enum_index] = true;
+ }
+#endif
+
+ for (int i = 0; i < len; ++i) {
+ if (descriptors->GetDetails(i).index() == len) {
+ descriptors->SetLastAdded(i);
+ break;
+ }
+ }
+
+ ASSERT(len == 0 ||
+ len == descriptors->GetDetails(descriptors->LastAdded()).index());
+
+ set_instance_descriptors(descriptors);
+}
SMI_ACCESSORS(Map, bit_field3, kBitField3Offset)
=======================================
--- /branches/bleeding_edge/src/objects.cc Wed Jul 18 02:20:57 2012
+++ /branches/bleeding_edge/src/objects.cc Wed Jul 18 08:38:58 2012
@@ -5699,22 +5699,21 @@
Descriptor desc(src->GetKey(src_index), value, details);
Set(dst_index, &desc, witness);
}
+
MaybeObject* DescriptorArray::CopyReplace(Descriptor* descriptor,
int insertion_index) {
ASSERT(0 <= insertion_index && insertion_index <
number_of_descriptors());
// Ensure the key is a symbol.
- { MaybeObject* maybe_result = descriptor->KeyToSymbol();
- if (maybe_result->IsFailure()) return maybe_result;
- }
+ MaybeObject* maybe_failure = descriptor->KeyToSymbol();
+ if (maybe_failure->IsFailure()) return maybe_failure;
int size = number_of_descriptors();
DescriptorArray* new_descriptors;
- { MaybeObject* maybe_result = Allocate(size, MAY_BE_SHARED);
- if (!maybe_result->To(&new_descriptors)) return maybe_result;
- }
+ MaybeObject* maybe_descriptors = Allocate(size, MAY_BE_SHARED);
+ if (!maybe_descriptors->To(&new_descriptors)) return maybe_descriptors;
FixedArray::WhitenessWitness witness(new_descriptors);
@@ -5736,8 +5735,8 @@
MaybeObject* DescriptorArray::CopyAdd(Descriptor* descriptor) {
// Ensure the key is a symbol.
- MaybeObject* maybe_result = descriptor->KeyToSymbol();
- if (maybe_result->IsFailure()) return maybe_result;
+ MaybeObject* maybe_failure = descriptor->KeyToSymbol();
+ if (maybe_failure->IsFailure()) return maybe_failure;
String* key = descriptor->GetKey();
ASSERT(Search(key) == kNotFound);
@@ -5792,20 +5791,15 @@
return new_descriptors;
}
+
// We need the whiteness witness since sort will reshuffle the entries in
the
// descriptor array. If the descriptor array were to be black, the
shuffling
// would move a slot that was already recorded as pointing into an
evacuation
// candidate. This would result in missing updates upon evacuation.
-void DescriptorArray::SortUnchecked(const WhitenessWitness& witness) {
+void DescriptorArray::Sort(const WhitenessWitness& witness) {
// In-place heap sort.
int len = number_of_descriptors();
- // Nothing to sort.
- if (len == 0) return;
-
- ASSERT(LastAdded() == kNoneAdded ||
- GetDetails(LastAdded()).index() == number_of_descriptors());
-
// Bottom-up max-heap construction.
// Index of the last node with children
const int max_parent_index = (len / 2) - 1;
@@ -5852,36 +5846,6 @@
parent_index = child_index;
}
}
-
-#ifdef DEBUG
- // Ensure that all enumeration indexes between 1 and length occur
uniquely in
- // the descriptor array.
- for (int i = 1; i <= len; ++i) {
- int j;
- for (j = 0; j < len; ++j) {
- if (GetDetails(j).index() == i) break;
- }
- ASSERT(j != len);
- for (j++; j < len; ++j) {
- ASSERT(GetDetails(j).index() != i);
- }
- }
-#endif
-
- for (int i = 0; i < len; ++i) {
- if (GetDetails(i).index() == len) {
- SetLastAdded(i);
- return;
- }
- }
-
- UNREACHABLE();
-}
-
-
-void DescriptorArray::Sort(const WhitenessWitness& witness) {
- SortUnchecked(witness);
- SLOW_ASSERT(IsSortedNoDuplicates());
}
@@ -12555,10 +12519,10 @@
descriptors->Sort(witness);
// Allocate new map.
Map* new_map;
- MaybeObject* maybe_new_map =
- obj->map()->CopyReplaceDescriptors(descriptors, NULL,
OMIT_TRANSITION);
+ MaybeObject* maybe_new_map = obj->map()->CopyDropDescriptors();
if (!maybe_new_map->To(&new_map)) return maybe_new_map;
+ new_map->InitializeDescriptors(descriptors);
new_map->set_unused_property_fields(unused_property_fields);
// Transform the object.
=======================================
--- /branches/bleeding_edge/src/objects.h Wed Jul 18 06:39:53 2012
+++ /branches/bleeding_edge/src/objects.h Wed Jul 18 08:38:58 2012
@@ -170,14 +170,6 @@
};
-// Indicates whether the search function should expect a sorted or an
unsorted
-// array as input.
-enum SearchMode {
- EXPECT_SORTED,
- EXPECT_UNSORTED
-};
-
-
// Indicates whether transitions can be added to a source map or not.
enum TransitionFlag {
INSERT_TRANSITION,
@@ -2584,11 +2576,6 @@
MUST_USE_RESULT MaybeObject* Copy(SharedMode shared_mode);
// Sort the instance descriptors by the hash codes of their keys.
- // Does not check for duplicates.
- void SortUnchecked(const WhitenessWitness&);
-
- // Sort the instance descriptors by the hash codes of their keys.
- // Checks the result for duplicates.
void Sort(const WhitenessWitness&);
// Search the instance descriptors for given name.
@@ -2714,7 +2701,7 @@
template<typename T>
-inline int LinearSearch(T* array, SearchMode mode, String* name, int len);
+inline int LinearSearch(T* array, String* name, int len);
template<typename T>
@@ -4855,6 +4842,7 @@
// [instance descriptors]: describes the object.
DECL_ACCESSORS(instance_descriptors, DescriptorArray)
+ inline void InitializeDescriptors(DescriptorArray* descriptors);
// Should only be called to clear a descriptor array that was only used
to
// store transitions and does not contain any live transitions anymore.
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
