Revision: 12385
Author: [email protected]
Date: Mon Aug 27 06:47:34 2012
Log: Make order of addition the primary order of descriptor arrays.
The order by name is maintained as secondary order by using unused bits in
the property details.
This is preliminary work towards sharing descriptors arrays.
The change allows us
- to get rid of the LastAdded bits in the map, binding it to the number of
valid descriptors for the given map
- to avoid resorting by enumeration index to create the cache
- (maybe in the future, depending on performance) to get rid of the
enumeration cache altogether.
Although generally the number_of_descriptors equals the
NumberOfOwnDescriptors in the current version, this is preliminary work
towards sharing descriptors, where maps may have more descriptors than
are valid for the map.
Review URL: https://chromiumcodereview.appspot.com/10879013
http://code.google.com/p/v8/source/detail?r=12385
Modified:
/branches/bleeding_edge/src/bootstrapper.cc
/branches/bleeding_edge/src/handles.cc
/branches/bleeding_edge/src/heap.cc
/branches/bleeding_edge/src/objects-debug.cc
/branches/bleeding_edge/src/objects-inl.h
/branches/bleeding_edge/src/objects.cc
/branches/bleeding_edge/src/objects.h
/branches/bleeding_edge/src/property-details.h
/branches/bleeding_edge/src/property.cc
/branches/bleeding_edge/src/property.h
/branches/bleeding_edge/src/runtime.cc
/branches/bleeding_edge/src/transitions-inl.h
/branches/bleeding_edge/src/transitions.h
=======================================
--- /branches/bleeding_edge/src/bootstrapper.cc Mon Aug 20 04:35:50 2012
+++ /branches/bleeding_edge/src/bootstrapper.cc Mon Aug 27 06:47:34 2012
@@ -2221,8 +2221,9 @@
// Add to dictionary.
Handle<String> key = Handle<String>(descs->GetKey(i));
Handle<Object> callbacks(descs->GetCallbacksObject(i));
- PropertyDetails d =
- PropertyDetails(details.attributes(), CALLBACKS,
details.index());
+ PropertyDetails d = PropertyDetails(details.attributes(),
+ CALLBACKS,
+ details.descriptor_index());
JSObject::SetNormalizedProperty(to, key, callbacks, d);
break;
}
=======================================
--- /branches/bleeding_edge/src/handles.cc Fri Aug 17 02:03:08 2012
+++ /branches/bleeding_edge/src/handles.cc Mon Aug 27 06:47:34 2012
@@ -701,7 +701,6 @@
Handle<FixedArray> GetEnumPropertyKeys(Handle<JSObject> object,
bool cache_result) {
- int index = 0;
Isolate* isolate = object->GetIsolate();
if (object->HasFastProperties()) {
if (object->map()->instance_descriptors()->HasEnumCache()) {
@@ -715,44 +714,34 @@
int num_enum = object->NumberOfLocalProperties(DONT_ENUM);
Handle<FixedArray> storage =
isolate->factory()->NewFixedArray(num_enum);
- Handle<FixedArray> sort_array =
isolate->factory()->NewFixedArray(num_enum);
-
Handle<FixedArray> indices;
- Handle<FixedArray> sort_array2;
if (cache_result) {
indices = isolate->factory()->NewFixedArray(num_enum);
- sort_array2 = isolate->factory()->NewFixedArray(num_enum);
}
Handle<DescriptorArray> descs =
Handle<DescriptorArray>(object->map()->instance_descriptors(),
isolate);
+ int index = 0;
for (int i = 0; i < descs->number_of_descriptors(); i++) {
if (!descs->GetDetails(i).IsDontEnum()) {
storage->set(index, descs->GetKey(i));
PropertyDetails details = descs->GetDetails(i);
- sort_array->set(index, Smi::FromInt(details.index()));
if (!indices.is_null()) {
if (details.type() != FIELD) {
indices = Handle<FixedArray>();
- sort_array2 = Handle<FixedArray>();
} else {
int field_index =
Descriptor::IndexFromValue(descs->GetValue(i));
if (field_index >= map->inobject_properties()) {
field_index = -(field_index - map->inobject_properties() +
1);
}
indices->set(index, Smi::FromInt(field_index));
- sort_array2->set(index, Smi::FromInt(details.index()));
}
}
index++;
}
}
- storage->SortPairs(*sort_array, sort_array->length());
- if (!indices.is_null()) {
- indices->SortPairs(*sort_array2, sort_array2->length());
- }
if (cache_result) {
Handle<FixedArray> bridge_storage =
isolate->factory()->NewFixedArray(
=======================================
--- /branches/bleeding_edge/src/heap.cc Mon Aug 27 02:40:26 2012
+++ /branches/bleeding_edge/src/heap.cc Mon Aug 27 06:47:34 2012
@@ -2050,9 +2050,8 @@
MaybeObject* Heap::AllocatePartialMap(InstanceType instance_type,
int instance_size) {
Object* result;
- { MaybeObject* maybe_result = AllocateRawMap();
- if (!maybe_result->ToObject(&result)) return maybe_result;
- }
+ MaybeObject* maybe_result = AllocateRawMap();
+ if (!maybe_result->ToObject(&result)) return maybe_result;
// Map::cast cannot be used due to uninitialized map field.
reinterpret_cast<Map*>(result)->set_map(raw_unchecked_meta_map());
@@ -2065,8 +2064,7 @@
reinterpret_cast<Map*>(result)->set_unused_property_fields(0);
reinterpret_cast<Map*>(result)->set_bit_field(0);
reinterpret_cast<Map*>(result)->set_bit_field2(0);
- reinterpret_cast<Map*>(result)->set_bit_field3(
- Map::LastAddedBits::encode(Map::kNoneAdded));
+ reinterpret_cast<Map*>(result)->set_bit_field3(0);
return result;
}
@@ -2093,7 +2091,7 @@
map->set_unused_property_fields(0);
map->set_bit_field(0);
map->set_bit_field2(1 << Map::kIsExtensible);
- map->set_bit_field3(Map::LastAddedBits::encode(Map::kNoneAdded));
+ map->set_bit_field3(0);
map->set_elements_kind(elements_kind);
// If the map object is aligned fill the padding area with Smi 0 objects.
@@ -3890,7 +3888,7 @@
FieldDescriptor field(name, i, NONE, i + 1);
descriptors->Set(i, &field, witness);
}
- descriptors->Sort(witness);
+ descriptors->Sort();
// The descriptors may contain duplicates because the compiler does
not
// guarantee the uniqueness of property names (it would have required
@@ -4162,8 +4160,9 @@
for (int i = 0; i < descs->number_of_descriptors(); i++) {
PropertyDetails details = descs->GetDetails(i);
ASSERT(details.type() == CALLBACKS); // Only accessors are expected.
- PropertyDetails d =
- PropertyDetails(details.attributes(), CALLBACKS, details.index());
+ PropertyDetails d = PropertyDetails(details.attributes(),
+ CALLBACKS,
+ details.descriptor_index());
Object* value = descs->GetCallbacksObject(i);
MaybeObject* maybe_value = AllocateJSGlobalPropertyCell(value);
if (!maybe_value->ToObject(&value)) return maybe_value;
=======================================
--- /branches/bleeding_edge/src/objects-debug.cc Mon Aug 27 02:40:26 2012
+++ /branches/bleeding_edge/src/objects-debug.cc Mon Aug 27 06:47:34 2012
@@ -302,11 +302,9 @@
instance_size() < HEAP->Capacity()));
VerifyHeapPointer(prototype());
VerifyHeapPointer(instance_descriptors());
- if (instance_descriptors()->number_of_descriptors() == 0) {
- ASSERT(LastAdded() == kNoneAdded);
- } else {
- ASSERT(instance_descriptors()->GetDetails(LastAdded()).index() ==
- instance_descriptors()->number_of_descriptors());
+ DescriptorArray* descriptors = instance_descriptors();
+ for (int i = 0; i < NumberOfOwnDescriptors(); ++i) {
+ ASSERT_EQ(i, descriptors->GetDetails(i).descriptor_index() - 1);
}
SLOW_ASSERT(instance_descriptors()->IsSortedNoDuplicates());
if (HasTransitionArray()) {
@@ -907,13 +905,13 @@
String* current_key = NULL;
uint32_t current = 0;
for (int i = 0; i < number_of_descriptors(); i++) {
- String* key = GetKey(i);
+ String* key = GetSortedKey(i);
if (key == current_key) {
PrintDescriptors();
return false;
}
current_key = key;
- uint32_t hash = GetKey(i)->Hash();
+ uint32_t hash = GetSortedKey(i)->Hash();
if (hash < current) {
PrintDescriptors();
return false;
@@ -928,13 +926,13 @@
String* current_key = NULL;
uint32_t current = 0;
for (int i = 0; i < number_of_transitions(); i++) {
- String* key = GetKey(i);
+ String* key = GetSortedKey(i);
if (key == current_key) {
PrintTransitions();
return false;
}
current_key = key;
- uint32_t hash = GetKey(i)->Hash();
+ uint32_t hash = GetSortedKey(i)->Hash();
if (hash < current) {
PrintTransitions();
return false;
=======================================
--- /branches/bleeding_edge/src/objects-inl.h Mon Aug 27 02:40:26 2012
+++ /branches/bleeding_edge/src/objects-inl.h Mon Aug 27 06:47:34 2012
@@ -1877,15 +1877,6 @@
this == HEAP->empty_descriptor_array());
return length() < kFirstIndex;
}
-
-
-void DescriptorArray::NoIncrementalWriteBarrierSwap(FixedArray* array,
- int first,
- int second) {
- Object* tmp = array->get(first);
- NoIncrementalWriteBarrierSet(array, first, array->get(second));
- NoIncrementalWriteBarrierSet(array, second, tmp);
-}
// Perform a binary search in a fixed array. Low and high are entry
indices. If
@@ -1900,7 +1891,7 @@
while (low != high) {
int mid = (low + high) / 2;
- String* mid_name = array->GetKey(mid);
+ String* mid_name = array->GetSortedKey(mid);
uint32_t mid_hash = mid_name->Hash();
if (mid_hash >= hash) {
@@ -1910,13 +1901,15 @@
}
}
- for (; low <= limit && array->GetKey(low)->Hash() == hash; ++low) {
- if (array->GetKey(low)->Equals(name)) return low;
+ for (; low <= limit; ++low) {
+ int sort_index = array->GetSortedKeyIndex(low);
+ String* entry = array->GetKey(sort_index);
+ if (entry->Hash() != hash) break;
+ if (entry->Equals(name)) return sort_index;
}
return T::kNotFound;
}
-
// Perform a linear search in this fixed array. len is the number of entry
// indices that are valid.
@@ -1924,10 +1917,11 @@
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);
+ int sorted_index = array->GetSortedKeyIndex(number);
+ String* entry = array->GetKey(sorted_index);
uint32_t current_hash = entry->Hash();
if (current_hash > hash) break;
- if (current_hash == hash && name->Equals(entry)) return number;
+ if (current_hash == hash && entry->Equals(name)) return sorted_index;
}
return T::kNotFound;
}
@@ -1937,13 +1931,12 @@
int Search(T* array, String* name) {
SLOW_ASSERT(array->IsSortedNoDuplicates());
- // Check for empty descriptor array.
int nof = array->number_of_entries();
if (nof == 0) return T::kNotFound;
// Fast case: do linear search for small arrays.
const int kMaxElementsForLinearSearch = 8;
- if (StringShape(name).IsSymbol() && nof < kMaxElementsForLinearSearch) {
+ if (nof < kMaxElementsForLinearSearch) {
return LinearSearch(array, name, nof);
}
@@ -1958,14 +1951,42 @@
int DescriptorArray::SearchWithCache(String* name) {
+ if (number_of_descriptors() == 0) return kNotFound;
+
DescriptorLookupCache* cache = GetIsolate()->descriptor_lookup_cache();
int number = cache->Lookup(this, name);
+
if (number == DescriptorLookupCache::kAbsent) {
- number = internal::Search(this, name);
+ number = Search(name);
cache->Update(this, name, number);
}
+
return number;
}
+
+
+void Map::LookupDescriptor(JSObject* holder,
+ String* name,
+ LookupResult* result) {
+ DescriptorArray* descriptors = this->instance_descriptors();
+ int number = descriptors->SearchWithCache(name);
+ if (number == DescriptorArray::kNotFound) return result->NotFound();
+ result->DescriptorResult(holder, descriptors->GetDetails(number),
number);
+}
+
+
+void Map::LookupTransition(JSObject* holder,
+ String* name,
+ LookupResult* result) {
+ if (HasTransitionArray()) {
+ TransitionArray* transition_array = transitions();
+ int number = transition_array->Search(name);
+ if (number != TransitionArray::kNotFound) {
+ return result->TransitionResult(holder, number);
+ }
+ }
+ result->NotFound();
+}
Object** DescriptorArray::GetKeySlot(int descriptor_number) {
@@ -1980,6 +2001,23 @@
ASSERT(descriptor_number < number_of_descriptors());
return String::cast(get(ToKeyIndex(descriptor_number)));
}
+
+
+int DescriptorArray::GetSortedKeyIndex(int descriptor_number) {
+ return GetDetails(descriptor_number).pointer();
+}
+
+
+String* DescriptorArray::GetSortedKey(int descriptor_number) {
+ return GetKey(GetSortedKeyIndex(descriptor_number));
+}
+
+
+void DescriptorArray::SetSortedKey(int pointer, int descriptor_number) {
+ int details_index = ToDetailsIndex(pointer);
+ PropertyDetails details = PropertyDetails(Smi::cast(get(details_index)));
+ set_unchecked(details_index,
details.set_pointer(descriptor_number).AsSmi());
+}
Object** DescriptorArray::GetValueSlot(int descriptor_number) {
@@ -2043,8 +2081,9 @@
const WhitenessWitness&) {
// Range check.
ASSERT(descriptor_number < number_of_descriptors());
- ASSERT(desc->GetDetails().index() <= number_of_descriptors());
- ASSERT(desc->GetDetails().index() > 0);
+ ASSERT(desc->GetDetails().descriptor_index() <=
+ number_of_descriptors());
+ ASSERT(desc->GetDetails().descriptor_index() > 0);
NoIncrementalWriteBarrierSet(this,
ToKeyIndex(descriptor_number),
@@ -2058,38 +2097,31 @@
}
-int DescriptorArray::Append(Descriptor* desc,
- const WhitenessWitness& witness,
- int number_of_set_descriptors) {
- int descriptor_number = number_of_set_descriptors;
- int enumeration_index = descriptor_number + 1;
+void DescriptorArray::Append(Descriptor* desc,
+ const WhitenessWitness& witness,
+ int number_of_set_descriptors) {
+ int enumeration_index = number_of_set_descriptors + 1;
desc->SetEnumerationIndex(enumeration_index);
+ Set(number_of_set_descriptors, desc, witness);
uint32_t hash = desc->GetKey()->Hash();
- for (; descriptor_number > 0; --descriptor_number) {
- String* key = GetKey(descriptor_number - 1);
+ int insertion;
+
+ for (insertion = number_of_set_descriptors; insertion > 0; --insertion) {
+ String* key = GetSortedKey(insertion - 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);
+ SetSortedKey(insertion, GetSortedKeyIndex(insertion - 1));
}
- Set(descriptor_number, desc, witness);
- return descriptor_number;
+ SetSortedKey(insertion, number_of_set_descriptors);
}
-void DescriptorArray::NoIncrementalWriteBarrierSwapDescriptors(
- int first, int second) {
- NoIncrementalWriteBarrierSwap(this, ToKeyIndex(first),
ToKeyIndex(second));
- NoIncrementalWriteBarrierSwap(this,
- ToValueIndex(first),
- ToValueIndex(second));
- NoIncrementalWriteBarrierSwap(this,
- ToDetailsIndex(first),
- ToDetailsIndex(second));
+void DescriptorArray::SwapSortedKeys(int first, int second) {
+ int first_key = GetSortedKeyIndex(first);
+ SetSortedKey(first, GetSortedKeyIndex(second));
+ SetSortedKey(second, first_key);
}
@@ -3447,18 +3479,18 @@
MaybeObject* Map::InitializeDescriptors(DescriptorArray* descriptors) {
+#ifdef DEBUG
int len = descriptors->number_of_descriptors();
ASSERT(len <= DescriptorArray::kMaxNumberOfDescriptors);
SLOW_ASSERT(descriptors->IsSortedNoDuplicates());
-#ifdef DEBUG
bool used_indices[DescriptorArray::kMaxNumberOfDescriptors];
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() -
+ int enum_index = descriptors->GetDetails(i).descriptor_index() -
PropertyDetails::kInitialIndex;
ASSERT(0 <= enum_index && enum_index < len);
ASSERT(!used_indices[enum_index]);
@@ -3469,14 +3501,8 @@
MaybeObject* maybe_failure = SetDescriptors(descriptors);
if (maybe_failure->IsFailure()) return maybe_failure;
- for (int i = 0; i < len; ++i) {
- if (descriptors->GetDetails(i).index() == len) {
- SetLastAdded(i);
- return this;
- }
- }
+ SetNumberOfOwnDescriptors(descriptors->number_of_descriptors());
- ASSERT(len == 0 && LastAdded() == kNoneAdded);
return this;
}
@@ -3503,9 +3529,10 @@
void Map::AppendDescriptor(Descriptor* desc,
const DescriptorArray::WhitenessWitness&
witness) {
DescriptorArray* descriptors = instance_descriptors();
- int set_descriptors = NumberOfSetDescriptors();
- int new_last_added = descriptors->Append(desc, witness, set_descriptors);
- SetLastAdded(new_last_added);
+ int number_of_own_descriptors = NumberOfOwnDescriptors();
+ ASSERT(number_of_own_descriptors < descriptors->number_of_descriptors());
+ descriptors->Append(desc, witness, number_of_own_descriptors);
+ SetNumberOfOwnDescriptors(number_of_own_descriptors + 1);
}
@@ -4993,7 +5020,9 @@
Object* key,
Object* value,
PropertyDetails details) {
- ASSERT(!key->IsString() || details.IsDeleted() || details.index() > 0);
+ ASSERT(!key->IsString() ||
+ details.IsDeleted() ||
+ details.dictionary_index() > 0);
int index = HashTable<Shape, Key>::EntryToIndex(entry);
AssertNoAllocation no_gc;
WriteBarrierMode mode = FixedArray::GetWriteBarrierMode(no_gc);
=======================================
--- /branches/bleeding_edge/src/objects.cc Wed Aug 22 08:44:17 2012
+++ /branches/bleeding_edge/src/objects.cc Mon Aug 27 06:47:34 2012
@@ -483,9 +483,11 @@
return value;
}
// Preserve enumeration index.
- details = PropertyDetails(details.attributes(),
- details.type(),
-
property_dictionary()->DetailsAt(entry).index());
+ details = PropertyDetails(
+ details.attributes(),
+ details.type(),
+ property_dictionary()->DetailsAt(entry).dictionary_index());
+
if (IsGlobalObject()) {
JSGlobalPropertyCell* cell =
JSGlobalPropertyCell::cast(property_dictionary()->ValueAt(entry));
@@ -1732,7 +1734,7 @@
int new_enumeration_index = 0; // 0 means "Use the next available
index."
if (old_index != -1) {
// All calls to ReplaceSlowProperty have had all transitions removed.
- new_enumeration_index = dictionary->DetailsAt(old_index).index();
+ new_enumeration_index =
dictionary->DetailsAt(old_index).dictionary_index();
}
PropertyDetails new_details(attributes, NORMAL, new_enumeration_index);
@@ -2078,33 +2080,6 @@
}
return heap->the_hole_value();
}
-
-
-void Map::LookupDescriptor(JSObject* holder,
- String* name,
- LookupResult* result) {
- DescriptorArray* descriptors = this->instance_descriptors();
- int number = descriptors->SearchWithCache(name);
- if (number != DescriptorArray::kNotFound) {
- result->DescriptorResult(holder, descriptors->GetDetails(number),
number);
- } else {
- result->NotFound();
- }
-}
-
-
-void Map::LookupTransition(JSObject* holder,
- String* name,
- LookupResult* result) {
- if (HasTransitionArray()) {
- TransitionArray* transition_array = transitions();
- int number = transition_array->Search(name);
- if (number != TransitionArray::kNotFound) {
- return result->TransitionResult(holder, number);
- }
- }
- result->NotFound();
-}
enum RightTrimMode { FROM_GC, FROM_MUTATOR };
@@ -2202,14 +2177,14 @@
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 (LinearSearch(*result, key, map->NumberOfSetDescriptors()) ==
+ if (LinearSearch(*result, key, map->NumberOfOwnDescriptors()) ==
DescriptorArray::kNotFound) {
CallbacksDescriptor desc(key, entry, entry->property_attributes());
map->AppendDescriptor(&desc, witness);
}
}
- int new_number_of_descriptors = map->NumberOfSetDescriptors();
+ int new_number_of_descriptors = map->NumberOfOwnDescriptors();
// Reinstall the original descriptor array if no new elements were added.
if (new_number_of_descriptors == descriptor_count) {
Map::SetDescriptors(map, array);
@@ -3300,8 +3275,9 @@
PropertyDetails details = descs->GetDetails(i);
switch (details.type()) {
case CONSTANT_FUNCTION: {
- PropertyDetails d =
- PropertyDetails(details.attributes(), NORMAL, details.index());
+ PropertyDetails d = PropertyDetails(details.attributes(),
+ NORMAL,
+ details.descriptor_index());
Object* value = descs->GetConstantFunction(i);
MaybeObject* maybe_dictionary =
dictionary->Add(descs->GetKey(i), value, d);
@@ -3309,8 +3285,9 @@
break;
}
case FIELD: {
- PropertyDetails d =
- PropertyDetails(details.attributes(), NORMAL, details.index());
+ PropertyDetails d = PropertyDetails(details.attributes(),
+ NORMAL,
+ details.descriptor_index());
Object* value = FastPropertyAt(descs->GetFieldIndex(i));
MaybeObject* maybe_dictionary =
dictionary->Add(descs->GetKey(i), value, d);
@@ -3683,10 +3660,15 @@
// hidden symbols hash code is zero (and no other string has hash
// code zero) it will always occupy the first entry if present.
DescriptorArray* descriptors = this->map()->instance_descriptors();
- if ((descriptors->number_of_descriptors() > 0) &&
- (descriptors->GetKey(0) == GetHeap()->hidden_symbol())) {
- ASSERT(descriptors->GetType(0) == FIELD);
- inline_value = this->FastPropertyAt(descriptors->GetFieldIndex(0));
+ if (descriptors->number_of_descriptors() > 0) {
+ int sorted_index = descriptors->GetSortedKeyIndex(0);
+ if (descriptors->GetKey(sorted_index) == GetHeap()->hidden_symbol())
{
+ ASSERT(descriptors->GetType(sorted_index) == FIELD);
+ inline_value = this->FastPropertyAt(
+ descriptors->GetFieldIndex(sorted_index));
+ } else {
+ inline_value = GetHeap()->undefined_value();
+ }
} else {
inline_value = GetHeap()->undefined_value();
}
@@ -3746,11 +3728,14 @@
// hidden symbols hash code is zero (and no other string has hash
// code zero) it will always occupy the first entry if present.
DescriptorArray* descriptors = this->map()->instance_descriptors();
- if ((descriptors->number_of_descriptors() > 0) &&
- (descriptors->GetKey(0) == GetHeap()->hidden_symbol())) {
- ASSERT(descriptors->GetType(0) == FIELD);
- this->FastPropertyAtPut(descriptors->GetFieldIndex(0), value);
- return this;
+ if (descriptors->number_of_descriptors() > 0) {
+ int sorted_index = descriptors->GetSortedKeyIndex(0);
+ if (descriptors->GetKey(sorted_index) == GetHeap()->hidden_symbol())
{
+ ASSERT(descriptors->GetType(sorted_index) == FIELD);
+ this->FastPropertyAtPut(descriptors->GetFieldIndex(sorted_index),
+ value);
+ return this;
+ }
}
}
MaybeObject* store_result =
@@ -4863,7 +4848,7 @@
result->set_bit_field(bit_field());
result->set_bit_field2(bit_field2());
result->set_bit_field3(bit_field3());
- result->SetLastAdded(kNoneAdded);
+ result->SetNumberOfOwnDescriptors(0);
return result;
}
@@ -4915,20 +4900,15 @@
MaybeObject* Map::CopyReplaceDescriptors(DescriptorArray* descriptors,
String* name,
- int last_added,
TransitionFlag flag) {
Map* result;
MaybeObject* maybe_result = CopyDropDescriptors();
if (!maybe_result->To(&result)) return maybe_result;
- if (last_added == kNoneAdded) {
- ASSERT(descriptors->number_of_descriptors() == 0);
- } else {
- ASSERT(descriptors->GetDetails(last_added).index() ==
- descriptors->number_of_descriptors());
+ if (descriptors->number_of_descriptors() != 0) {
MaybeObject* maybe_failure = result->SetDescriptors(descriptors);
if (maybe_failure->IsFailure()) return maybe_failure;
- result->SetLastAdded(last_added);
+
result->SetNumberOfOwnDescriptors(descriptors->number_of_descriptors());
}
if (flag == INSERT_TRANSITION && CanHaveMoreTransitions()) {
@@ -4982,23 +4962,14 @@
Map* map = ctor->initial_map();
DescriptorArray* descriptors = map->instance_descriptors();
- int last_added = map->LastAdded();
-
- return CopyReplaceDescriptors(descriptors, NULL, last_added,
OMIT_TRANSITION);
+ return CopyReplaceDescriptors(descriptors, NULL, OMIT_TRANSITION);
}
MaybeObject* Map::Copy() {
DescriptorArray* descriptors = instance_descriptors();
- int last_added = LastAdded();
-
- return CopyReplaceDescriptors(descriptors, NULL, last_added,
OMIT_TRANSITION);
+ return CopyReplaceDescriptors(descriptors, NULL, OMIT_TRANSITION);
}
-
-
-static bool InsertionPointFound(String* key1, String* key2) {
- return key1->Hash() > key2->Hash() || key1 == key2;
-}
MaybeObject* Map::CopyAddDescriptor(Descriptor* descriptor,
@@ -5022,26 +4993,15 @@
FixedArray::WhitenessWitness witness(new_descriptors);
// Copy the descriptors, inserting a descriptor.
- int insertion_index = -1;
- int to = 0;
- for (int from = 0; from < old_size; ++from) {
- if (insertion_index < 0 &&
- InsertionPointFound(descriptors->GetKey(from), key)) {
- insertion_index = to++;
- }
- new_descriptors->CopyFrom(to++, descriptors, from, witness);
+ for (int i = 0; i < old_size; ++i) {
+ new_descriptors->CopyFrom(i, descriptors, i, witness);
}
- if (insertion_index < 0) insertion_index = to++;
- ASSERT(to == new_size);
- ASSERT(new_size == descriptors->NextEnumerationIndex());
-
- descriptor->SetEnumerationIndex(new_size);
- new_descriptors->Set(insertion_index, descriptor, witness);
+ new_descriptors->Append(descriptor, witness, old_size);
SLOW_ASSERT(new_descriptors->IsSortedNoDuplicates());
- return CopyReplaceDescriptors(new_descriptors, key, insertion_index,
flag);
+ return CopyReplaceDescriptors(new_descriptors, key, flag);
}
@@ -5088,13 +5048,15 @@
new_descriptors->CopyFrom(index, descriptors, index, witness);
}
- descriptor->SetEnumerationIndex(
- descriptors->GetDetails(insertion_index).index());
+ PropertyDetails original_details =
descriptors->GetDetails(insertion_index);
+ descriptor->SetEnumerationIndex(original_details.descriptor_index());
+ descriptor->SetSortedKey(original_details.pointer());
+
new_descriptors->Set(insertion_index, descriptor, witness);
SLOW_ASSERT(new_descriptors->IsSortedNoDuplicates());
- return CopyReplaceDescriptors(new_descriptors, key, LastAdded(), flag);
+ return CopyReplaceDescriptors(new_descriptors, key, flag);
}
@@ -5920,27 +5882,29 @@
// 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::Sort(const WhitenessWitness& witness) {
+void DescriptorArray::Sort() {
// In-place heap sort.
int len = number_of_descriptors();
+ // Reset sorting since the descriptor array might contain invalid
pointers.
+ for (int i = 0; i < len; ++i) SetSortedKey(i, i);
// Bottom-up max-heap construction.
// Index of the last node with children
const int max_parent_index = (len / 2) - 1;
for (int i = max_parent_index; i >= 0; --i) {
int parent_index = i;
- const uint32_t parent_hash = GetKey(i)->Hash();
+ const uint32_t parent_hash = GetSortedKey(i)->Hash();
while (parent_index <= max_parent_index) {
int child_index = 2 * parent_index + 1;
- uint32_t child_hash = GetKey(child_index)->Hash();
+ uint32_t child_hash = GetSortedKey(child_index)->Hash();
if (child_index + 1 < len) {
- uint32_t right_child_hash = GetKey(child_index + 1)->Hash();
+ uint32_t right_child_hash = GetSortedKey(child_index + 1)->Hash();
if (right_child_hash > child_hash) {
child_index++;
child_hash = right_child_hash;
}
}
if (child_hash <= parent_hash) break;
- NoIncrementalWriteBarrierSwapDescriptors(parent_index, child_index);
+ SwapSortedKeys(parent_index, child_index);
// Now element at child_index could be < its children.
parent_index = child_index; // parent_hash remains correct.
}
@@ -5949,23 +5913,23 @@
// Extract elements and create sorted array.
for (int i = len - 1; i > 0; --i) {
// Put max element at the back of the array.
- NoIncrementalWriteBarrierSwapDescriptors(0, i);
+ SwapSortedKeys(0, i);
// Shift down the new top element.
int parent_index = 0;
- const uint32_t parent_hash = GetKey(parent_index)->Hash();
+ const uint32_t parent_hash = GetSortedKey(parent_index)->Hash();
const int max_parent_index = (i / 2) - 1;
while (parent_index <= max_parent_index) {
int child_index = parent_index * 2 + 1;
- uint32_t child_hash = GetKey(child_index)->Hash();
+ uint32_t child_hash = GetSortedKey(child_index)->Hash();
if (child_index + 1 < i) {
- uint32_t right_child_hash = GetKey(child_index + 1)->Hash();
+ uint32_t right_child_hash = GetSortedKey(child_index + 1)->Hash();
if (right_child_hash > child_hash) {
child_index++;
child_hash = right_child_hash;
}
}
if (child_hash <= parent_hash) break;
- NoIncrementalWriteBarrierSwapDescriptors(parent_index, child_index);
+ SwapSortedKeys(parent_index, child_index);
parent_index = child_index;
}
}
@@ -7310,11 +7274,7 @@
instance_type() == other->instance_type() &&
bit_field() == other->bit_field() &&
bit_field2() == other->bit_field2() &&
- static_cast<uint32_t>(bit_field3()) ==
- LastAddedBits::update(
- IsShared::update(DictionaryMap::update(other->bit_field3(),
true),
- true),
- kNoneAdded);
+ function_with_prototype() == other->function_with_prototype();
}
@@ -9425,7 +9385,8 @@
// is read-only (a declared const that has not been initialized).
If a
// value is being defined we skip attribute checks completely.
if (set_mode == DEFINE_PROPERTY) {
- details = PropertyDetails(attributes, NORMAL, details.index());
+ details = PropertyDetails(
+ attributes, NORMAL, details.dictionary_index());
dictionary->DetailsAtPut(entry, details);
} else if (details.IsReadOnly() && !element->IsTheHole()) {
if (strict_mode == kNonStrictMode) {
@@ -12193,7 +12154,8 @@
int pos = 0;
for (int i = 0; i < capacity; i++) {
if (Dictionary<Shape, Key>::IsKey(Dictionary<Shape, Key>::KeyAt(i))) {
- enumeration_order->set(pos++, Smi::FromInt(DetailsAt(i).index()));
+ enumeration_order->set(
+ pos++, Smi::FromInt(DetailsAt(i).dictionary_index()));
}
}
@@ -12319,7 +12281,8 @@
uint32_t entry = Dictionary<Shape, Key>::FindInsertionEntry(hash);
// Insert element at empty or deleted entry
- if (!details.IsDeleted() && details.index() == 0 &&
Shape::kIsEnumerable) {
+ if (!details.IsDeleted() &&
+ details.dictionary_index() == 0 && Shape::kIsEnumerable) {
// Assign an enumeration index to the property and update
// SetNextEnumerationIndex.
int index = NextEnumerationIndex();
@@ -12410,7 +12373,7 @@
// Preserve enumeration index.
details = PropertyDetails(details.attributes(),
details.type(),
- DetailsAt(entry).index());
+ DetailsAt(entry).dictionary_index());
MaybeObject* maybe_object_key =
SeededNumberDictionaryShape::AsObject(key);
Object* object_key;
if (!maybe_object_key->ToObject(&object_key)) return maybe_object_key;
@@ -12492,7 +12455,7 @@
PropertyDetails details = DetailsAt(i);
if (details.IsDeleted() || details.IsDontEnum()) continue;
storage->set(index, k);
- sort_array->set(index, Smi::FromInt(details.index()));
+ sort_array->set(index, Smi::FromInt(details.dictionary_index()));
index++;
}
}
@@ -12617,7 +12580,6 @@
if (!maybe_fields->To(&fields)) return maybe_fields;
// Fill in the instance descriptor and the fields.
- int next_descriptor = 0;
int current_offset = 0;
for (int i = 0; i < capacity; i++) {
Object* k = KeyAt(i);
@@ -12629,14 +12591,15 @@
if (!maybe_key->To(&key)) return maybe_key;
PropertyDetails details = DetailsAt(i);
+ int enumeration_index = details.dictionary_index();
PropertyType type = details.type();
if (value->IsJSFunction() && !heap->InNewSpace(value)) {
ConstantFunctionDescriptor d(key,
JSFunction::cast(value),
details.attributes(),
- details.index());
- descriptors->Set(next_descriptor, &d, witness);
+ enumeration_index);
+ descriptors->Set(enumeration_index - 1, &d, witness);
} else if (type == NORMAL) {
if (current_offset < inobject_props) {
obj->InObjectPropertyAtPut(current_offset,
@@ -12649,23 +12612,22 @@
FieldDescriptor d(key,
current_offset++,
details.attributes(),
- details.index());
- descriptors->Set(next_descriptor, &d, witness);
+ enumeration_index);
+ descriptors->Set(enumeration_index - 1, &d, witness);
} else if (type == CALLBACKS) {
CallbacksDescriptor d(key,
value,
details.attributes(),
- details.index());
- descriptors->Set(next_descriptor, &d, witness);
+ enumeration_index);
+ descriptors->Set(enumeration_index - 1, &d, witness);
} else {
UNREACHABLE();
}
- ++next_descriptor;
}
}
ASSERT(current_offset == number_of_fields);
- descriptors->Sort(witness);
+ descriptors->Sort();
MaybeObject* maybe_failure = new_map->InitializeDescriptors(descriptors);
if (maybe_failure->IsFailure()) return maybe_failure;
=======================================
--- /branches/bleeding_edge/src/objects.h Mon Aug 27 02:40:26 2012
+++ /branches/bleeding_edge/src/objects.h Mon Aug 27 06:47:34 2012
@@ -2515,17 +2515,22 @@
inline Object* GetCallbacksObject(int descriptor_number);
inline AccessorDescriptor* GetCallbacks(int descriptor_number);
+ inline String* GetSortedKey(int descriptor_number);
+ inline int GetSortedKeyIndex(int descriptor_number);
+ inline void SetSortedKey(int pointer, int descriptor_number);
+
// Accessor for complete descriptor.
inline void Get(int descriptor_number, Descriptor* desc);
inline void Set(int descriptor_number,
Descriptor* desc,
const WhitenessWitness&);
+
// 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 int Append(Descriptor* desc,
- const WhitenessWitness&,
- int number_of_set_descriptors);
+ inline void Append(Descriptor* desc,
+ const WhitenessWitness&,
+ int number_of_set_descriptors);
// Transfer a complete descriptor from the src descriptor array to this
// descriptor array.
@@ -2535,7 +2540,8 @@
const WhitenessWitness&);
// Sort the instance descriptors by the hash codes of their keys.
- void Sort(const WhitenessWitness&);
+ void Sort();
+ inline void SwapSortedKeys(int first, int second);
// Search the instance descriptors for given name.
INLINE(int Search(String* name));
@@ -4657,10 +4663,10 @@
inline int bit_field3();
inline void set_bit_field3(int value);
- class IsShared: public BitField<bool, 0, 1> {};
- class FunctionWithPrototype: public BitField<bool, 1, 1> {};
- class DictionaryMap: public BitField<bool, 2, 1> {};
- class LastAddedBits: public BitField<int, 3, 11> {};
+ class NumberOfOwnDescriptorsBits: public BitField<int, 0, 11> {};
+ class IsShared: public BitField<bool, 11, 1> {};
+ class FunctionWithPrototype: public BitField<bool, 12, 1> {};
+ class DictionaryMap: public BitField<bool, 13, 1> {};
// Tells whether the object in the prototype property will be used
// for instances created from this function. If the prototype
@@ -4885,31 +4891,31 @@
// Lookup in the map's instance descriptors and fill out the result
// with the given holder if the name is found. The holder may be
// NULL when this function is used from the compiler.
- void LookupDescriptor(JSObject* holder,
- String* name,
- LookupResult* result);
+ inline void LookupDescriptor(JSObject* holder,
+ String* name,
+ LookupResult* result);
- void LookupTransition(JSObject* holder,
- String* name,
- LookupResult* result);
+ inline void LookupTransition(JSObject* holder,
+ String* name,
+ LookupResult* result);
// The size of transition arrays are limited so they do not end up in
large
// object space. Otherwise ClearNonLiveTransitions would leak memory
while
// applying in-place right trimming.
inline bool CanHaveMoreTransitions();
- void SetLastAdded(int index) {
- set_bit_field3(LastAddedBits::update(bit_field3(), index));
+ int LastAdded() {
+ int number_of_own_descriptors = NumberOfOwnDescriptors();
+ ASSERT(number_of_own_descriptors > 0);
+ return number_of_own_descriptors - 1;
}
- int LastAdded() {
- return LastAddedBits::decode(bit_field3());
+ int NumberOfOwnDescriptors() {
+ return NumberOfOwnDescriptorsBits::decode(bit_field3());
}
- int NumberOfSetDescriptors() {
- ASSERT(!instance_descriptors()->IsEmpty());
- if (LastAdded() == kNoneAdded) return 0;
- return instance_descriptors()->GetDetails(LastAdded()).index();
+ void SetNumberOfOwnDescriptors(int number) {
+ set_bit_field3(NumberOfOwnDescriptorsBits::update(bit_field3(),
number));
}
MUST_USE_RESULT MaybeObject* RawCopy(int instance_size);
@@ -4918,7 +4924,6 @@
MUST_USE_RESULT MaybeObject* CopyReplaceDescriptors(
DescriptorArray* descriptors,
String* name,
- int last_added,
TransitionFlag flag);
MUST_USE_RESULT MaybeObject* CopyAddDescriptor(Descriptor* descriptor,
TransitionFlag flag);
@@ -5052,9 +5057,6 @@
static const int kMaxPreAllocatedPropertyFields = 255;
- // Constant for denoting that the LastAdded field was not yet set.
- static const int kNoneAdded = LastAddedBits::kMax;
-
// Layout description.
static const int kInstanceSizesOffset = HeapObject::kHeaderSize;
static const int kInstanceAttributesOffset = kInstanceSizesOffset +
kIntSize;
@@ -5130,11 +5132,6 @@
static_cast<int8_t>((FAST_HOLEY_SMI_ELEMENTS + 1) <<
Map::kElementsKindShift) - 1;
- // Bit positions for bit field 3
- static const int kIsShared = 0;
- static const int kFunctionWithPrototype = 1;
- static const int kDictionaryMap = 2;
-
typedef FixedBodyDescriptor<kPointerFieldsBeginOffset,
kPointerFieldsEndOffset,
kSize> BodyDescriptor;
=======================================
--- /branches/bleeding_edge/src/property-details.h Thu Jul 5 06:54:20 2012
+++ /branches/bleeding_edge/src/property-details.h Mon Aug 27 06:47:34 2012
@@ -77,18 +77,18 @@
PropertyDetails(PropertyAttributes attributes,
PropertyType type,
int index = 0) {
- ASSERT(TypeField::is_valid(type));
- ASSERT(AttributesField::is_valid(attributes));
- ASSERT(StorageField::is_valid(index));
-
value_ = TypeField::encode(type)
| AttributesField::encode(attributes)
- | StorageField::encode(index);
+ | DictionaryStorageField::encode(index);
ASSERT(type == this->type());
ASSERT(attributes == this->attributes());
- ASSERT(index == this->index());
+ ASSERT(index == this->dictionary_index());
}
+
+ int pointer() { return DescriptorPointer::decode(value_); }
+
+ PropertyDetails set_pointer(int i) { return PropertyDetails(value_, i); }
// Conversion for storing details as Object*.
explicit inline PropertyDetails(Smi* smi);
@@ -98,12 +98,18 @@
PropertyAttributes attributes() { return
AttributesField::decode(value_); }
- int index() { return StorageField::decode(value_); }
+ int dictionary_index() {
+ return DictionaryStorageField::decode(value_);
+ }
+
+ int descriptor_index() {
+ return DescriptorStorageField::decode(value_);
+ }
inline PropertyDetails AsDeleted();
static bool IsValidIndex(int index) {
- return StorageField::is_valid(index);
+ return DictionaryStorageField::is_valid(index);
}
bool IsReadOnly() { return (attributes() & READ_ONLY) != 0; }
@@ -113,14 +119,20 @@
// Bit fields in value_ (type, shift, size). Must be public so the
// constants can be embedded in generated code.
- class TypeField: public BitField<PropertyType, 0, 3> {};
- class AttributesField: public BitField<PropertyAttributes, 3, 3> {};
- class DeletedField: public BitField<uint32_t, 6, 1> {};
- class StorageField: public BitField<uint32_t, 7, 32-7> {};
+ class TypeField: public BitField<PropertyType, 0,
3> {};
+ class AttributesField: public BitField<PropertyAttributes, 3,
3> {};
+ class DeletedField: public BitField<uint32_t, 6,
1> {};
+ class DictionaryStorageField: public BitField<uint32_t, 7,
24> {};
+ class DescriptorStorageField: public BitField<uint32_t, 7,
11> {};
+ class DescriptorPointer: public BitField<uint32_t, 18,
11> {};
static const int kInitialIndex = 1;
private:
+ PropertyDetails(int value, int pointer) {
+ value_ = DescriptorPointer::update(value, pointer);
+ }
+
uint32_t value_;
};
=======================================
--- /branches/bleeding_edge/src/property.cc Thu Jul 5 06:54:20 2012
+++ /branches/bleeding_edge/src/property.cc Mon Aug 27 06:47:34 2012
@@ -112,7 +112,7 @@
GetKey()->ShortPrint(out);
PrintF(out, " @ ");
GetValue()->ShortPrint(out);
- PrintF(out, " %d\n", GetDetails().index());
+ PrintF(out, " %d\n", GetDetails().descriptor_index());
}
=======================================
--- /branches/bleeding_edge/src/property.h Wed Jul 18 02:20:57 2012
+++ /branches/bleeding_edge/src/property.h Mon Aug 27 06:47:34 2012
@@ -65,9 +65,10 @@
#endif
void SetEnumerationIndex(int index) {
- ASSERT(PropertyDetails::IsValidIndex(index));
details_ = PropertyDetails(details_.attributes(), details_.type(),
index);
}
+
+ void SetSortedKey(int index) { details_ = details_.set_pointer(index); }
private:
String* key_;
=======================================
--- /branches/bleeding_edge/src/runtime.cc Mon Aug 27 02:40:26 2012
+++ /branches/bleeding_edge/src/runtime.cc Mon Aug 27 06:47:34 2012
@@ -2166,14 +2166,14 @@
// Construct a new field descriptor with updated attributes.
DescriptorArray* instance_desc =
function->map()->instance_descriptors();
- int index = instance_desc->Search(name);
+ int index = instance_desc->SearchWithCache(name);
ASSERT(index != DescriptorArray::kNotFound);
PropertyDetails details = instance_desc->GetDetails(index);
CallbacksDescriptor new_desc(name,
instance_desc->GetValue(index),
static_cast<PropertyAttributes>(details.attributes() | READ_ONLY),
- details.index());
+ details.descriptor_index());
// Create a new map featuring the new field descriptors array.
Map* new_map;
@@ -2191,7 +2191,7 @@
PropertyDetails new_details(
static_cast<PropertyAttributes>(details.attributes() | READ_ONLY),
details.type(),
- details.index());
+ details.dictionary_index());
function->property_dictionary()->DetailsAtPut(entry, new_details);
}
return function;
@@ -10530,7 +10530,8 @@
RUNTIME_FUNCTION(MaybeObject*, Runtime_DebugPropertyIndexFromDetails) {
ASSERT(args.length() == 1);
CONVERT_PROPERTY_DETAILS_CHECKED(details, 0);
- return Smi::FromInt(details.index());
+ // TODO(verwaest): Depends on the type of details.
+ return Smi::FromInt(details.dictionary_index());
}
=======================================
--- /branches/bleeding_edge/src/transitions-inl.h Mon Aug 13 01:43:16 2012
+++ /branches/bleeding_edge/src/transitions-inl.h Mon Aug 27 06:47:34 2012
@@ -187,7 +187,6 @@
Map* map = GetTarget(transition_number);
DescriptorArray* descriptors = map->instance_descriptors();
int descriptor = map->LastAdded();
- ASSERT(descriptor != Map::kNoneAdded);
return descriptors->GetDetails(descriptor);
}
=======================================
--- /branches/bleeding_edge/src/transitions.h Mon Aug 13 01:43:16 2012
+++ /branches/bleeding_edge/src/transitions.h Mon Aug 27 06:47:34 2012
@@ -53,6 +53,11 @@
inline String* GetKey(int transition_number);
inline void SetKey(int transition_number, String* value);
inline Object** GetKeySlot(int transition_number);
+ int GetSortedKeyIndex(int transition_number) { return transition_number;
}
+
+ String* GetSortedKey(int transition_number) {
+ return GetKey(transition_number);
+ }
inline Map* GetTarget(int transition_number);
inline void SetTarget(int transition_number, Map* target);
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
