Sharing of descriptor arrays.

src/objects-inl.h

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 1895 matching lines @@
     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.
-template<typename T>
-int LinearSearch(T* array, String* name, int len) {
+template<SearchMode search_mode, typename T>
+int LinearSearch(T* array, String* name, int len, int valid_entries) {
   uint32_t hash = name->Hash();
-  for (int number = 0; number < len; 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 && entry->Equals(name)) return sorted_index;
+  if (search_mode == ALL_ENTRIES) {
+    for (int number = 0; number < len; 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 && entry->Equals(name)) return sorted_index;
+    }
+  } else {
+    ASSERT(len >= valid_entries);
+    for (int number = 0; number < valid_entries; number++) {
+      String* entry = array->GetKey(number);
+      uint32_t current_hash = entry->Hash();
+      if (current_hash == hash && entry->Equals(name)) return number;
+    }
   }
   return T::kNotFound;
 }
 
 
-template<typename T>
-int Search(T* array, String* name) {
-  SLOW_ASSERT(array->IsSortedNoDuplicates());
+template<SearchMode search_mode, typename T>
+int Search(T* array, String* name, int valid_entries) {
+  if (search_mode == VALID_ENTRIES) {
+    SLOW_ASSERT(array->IsSortedNoDuplicates(valid_entries));
+  } else {
+    SLOW_ASSERT(array->IsSortedNoDuplicates());
+  }
 
   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 (nof < kMaxElementsForLinearSearch) {
-    return LinearSearch(array, name, nof);
+  if (search_mode == VALID_ENTRIES ||
+      (search_mode == ALL_ENTRIES && nof < kMaxElementsForLinearSearch)) {
+    return LinearSearch<search_mode>(array, name, nof, valid_entries);
   }
 
   // Slow case: perform binary search.
   return BinarySearch(array, name, 0, nof - 1);
 }
 
 
-int DescriptorArray::Search(String* name) {
-  return internal::Search(this, name);
+int DescriptorArray::Search(String* name, int valid_descriptors) {
+  return internal::Search<VALID_ENTRIES>(this, name, valid_descriptors);
 }
 
 
-int DescriptorArray::SearchWithCache(String* name) {
-  if (number_of_descriptors() == 0) return kNotFound;
+int DescriptorArray::SearchWithCache(String* name, Map* map) {
+  // name->PrintLn();

[Jakob Kummerow, 2012/09/11 14:24:25]

nit: leftover?

[Toon Verwaest, 2012/09/11 14:49:23]

Done.

+  int number_of_own_descriptors = map->NumberOfOwnDescriptors();
+  if (number_of_own_descriptors == 0) return kNotFound;
 
   DescriptorLookupCache* cache = GetIsolate()->descriptor_lookup_cache();
-  int number = cache->Lookup(this, name);
+  int number = cache->Lookup(map, name);
 
   if (number == DescriptorLookupCache::kAbsent) {
-    number = Search(name);
-    cache->Update(this, name, number);
+    number = Search(name, number_of_own_descriptors);
+    cache->Update(map, name, number);
   }
 
   return number;
 }
 
 
 void Map::LookupDescriptor(JSObject* holder,
                            String* name,
                            LookupResult* result) {
   DescriptorArray* descriptors = this->instance_descriptors();
-  int number = descriptors->SearchWithCache(name);
+  int number = descriptors->SearchWithCache(name, this);
   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();
@@ skipping 23 matching lines @@
 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());
+void DescriptorArray::SetSortedKey(int descriptor_index, int pointer) {
+  PropertyDetails details = GetDetails(descriptor_index);
+  set(ToDetailsIndex(descriptor_index), details.set_pointer(pointer).AsSmi());
 }
 
 
 Object** DescriptorArray::GetValueSlot(int descriptor_number) {
   ASSERT(descriptor_number < number_of_descriptors());
   return HeapObject::RawField(
       reinterpret_cast<HeapObject*>(this),
       OffsetOfElementAt(ToValueIndex(descriptor_number)));
 }
 
@@ skipping 63 matching lines @@
                                desc->GetValue());
   NoIncrementalWriteBarrierSet(this,
                                ToDetailsIndex(descriptor_number),
                                desc->GetDetails().AsSmi());
 }
 
 
 void DescriptorArray::Append(Descriptor* desc,
                              const WhitenessWitness& witness,
                              int number_of_set_descriptors) {
-  int enumeration_index = number_of_set_descriptors + 1;
+  int descriptor_number = number_of_set_descriptors;
+  int enumeration_index = descriptor_number + 1;
   desc->SetEnumerationIndex(enumeration_index);
-  Set(number_of_set_descriptors, desc, witness);
+  Set(descriptor_number, desc, witness);
 
   uint32_t hash = desc->GetKey()->Hash();
 
   int insertion;
 
-  for (insertion = number_of_set_descriptors; insertion > 0; --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, number_of_set_descriptors);
+  SetSortedKey(insertion, descriptor_number);
 }
 
 
 void DescriptorArray::SwapSortedKeys(int first, int second) {
   int first_key = GetSortedKeyIndex(first);
   SetSortedKey(first, GetSortedKeyIndex(second));
   SetSortedKey(second, first_key);
 }
 
 
@@ skipping 878 matching lines @@
 JSFunction* Map::unchecked_constructor() {
   return reinterpret_cast<JSFunction*>(READ_FIELD(this, kConstructorOffset));
 }
 
 
 Code::Flags Code::flags() {
   return static_cast<Flags>(READ_INT_FIELD(this, kFlagsOffset));
 }
 
 
+void Map::SetOwnsDescriptors(bool is_shared) {

[Jakob Kummerow, 2012/09/11 14:24:25]

nit: for consistency, these two methods should be in unix_hacker_style.

[Toon Verwaest, 2012/09/11 14:49:23]

Done.

+  set_bit_field3(OwnsDescriptors::update(bit_field3(), is_shared));
+}
+
+
+bool Map::OwnsDescriptors() {
+  return OwnsDescriptors::decode(bit_field3());
+}
+
+
 void Code::set_flags(Code::Flags flags) {
   STATIC_ASSERT(Code::NUMBER_OF_KINDS <= KindField::kMax + 1);
   // Make sure that all call stubs have an arguments count.
   ASSERT((ExtractKindFromFlags(flags) != CALL_IC &&
           ExtractKindFromFlags(flags) != KEYED_CALL_IC) ||
          ExtractArgumentsCountFromFlags(flags) >= 0);
   WRITE_INT_FIELD(this, kFlagsOffset, flags);
 }
 
 
@@ skipping 416 matching lines @@
 
 
 void Map::set_prototype(Object* value, WriteBarrierMode mode) {
   ASSERT(value->IsNull() || value->IsJSReceiver());
   WRITE_FIELD(this, kPrototypeOffset, value);
   CONDITIONAL_WRITE_BARRIER(GetHeap(), this, kPrototypeOffset, value, mode);
 }
 
 
 DescriptorArray* Map::instance_descriptors() {
-  if (!HasTransitionArray()) return GetHeap()->empty_descriptor_array();
-  return transitions()->descriptors();
+  if (HasTransitionArray()) return transitions()->descriptors();
+  Object* back_pointer = GetBackPointer();
+  if (!back_pointer->IsMap()) return GetHeap()->empty_descriptor_array();
+  return Map::cast(back_pointer)->instance_descriptors();
 }
 
 
 // If the descriptor is using the empty transition array, install a new empty
 // transition array that will have place for an element transition.
 static MaybeObject* EnsureHasTransitionArray(Map* map) {
   if (map->HasTransitionArray()) return map;
 
   TransitionArray* transitions;
-  MaybeObject* maybe_transitions = TransitionArray::Allocate(0);
+  JSGlobalPropertyCell* pointer = map->RetrieveDescriptorsPointer();
+  MaybeObject* maybe_transitions = TransitionArray::Allocate(0, pointer);
   if (!maybe_transitions->To(&transitions)) return maybe_transitions;
+
+  transitions->set_back_pointer_storage(map->GetBackPointer());
   map->set_transitions(transitions);
   return transitions;
 }
 
 
-MaybeObject* Map::SetDescriptors(DescriptorArray* value,
-                                 WriteBarrierMode mode) {
+MaybeObject* Map::SetDescriptors(DescriptorArray* value) {
   ASSERT(!is_shared());
   MaybeObject* maybe_failure = EnsureHasTransitionArray(this);
   if (maybe_failure->IsFailure()) return maybe_failure;
 
-  transitions()->set_descriptors(value, mode);
+  ASSERT(NumberOfOwnDescriptors() <= value->number_of_descriptors());
+  transitions()->set_descriptors(value);
   return this;
 }
 
 
 MaybeObject* Map::InitializeDescriptors(DescriptorArray* descriptors) {
+  int len = descriptors->number_of_descriptors();
 #ifdef DEBUG
-  int len = descriptors->number_of_descriptors();
   ASSERT(len <= DescriptorArray::kMaxNumberOfDescriptors);
-  SLOW_ASSERT(descriptors->IsSortedNoDuplicates());
 
   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).descriptor_index() -
                      PropertyDetails::kInitialIndex;
     ASSERT(0 <= enum_index && enum_index < len);
     ASSERT(!used_indices[enum_index]);
     used_indices[enum_index] = true;
   }
 #endif
 
   MaybeObject* maybe_failure = SetDescriptors(descriptors);
   if (maybe_failure->IsFailure()) return maybe_failure;
 
-  SetNumberOfOwnDescriptors(descriptors->number_of_descriptors());
-
+  SetNumberOfOwnDescriptors(len);
   return this;
 }
 
 
 SMI_ACCESSORS(Map, bit_field3, kBitField3Offset)
 
 
 void Map::ClearTransitions(Heap* heap, WriteBarrierMode mode) {
   Object* back_pointer = GetBackPointer();
 #ifdef DEBUG
@@ skipping 48 matching lines @@
 
 
 bool Map::CanHaveMoreTransitions() {
   if (!HasTransitionArray()) return true;
   return FixedArray::SizeFor(transitions()->length() +
                              TransitionArray::kTransitionSize)
       <= Page::kMaxNonCodeHeapObjectSize;
 }
 
 
+JSGlobalPropertyCell* Map::RetrieveDescriptorsPointer() {
+  if (!OwnsDescriptors()) return NULL;
+  Object* back_pointer = GetBackPointer();
+  if (back_pointer->IsUndefined()) return NULL;
+  Map* map = Map::cast(back_pointer);
+  ASSERT(map->HasTransitionArray());
+  return map->transitions()->descriptors_pointer();
+}
+
+
 MaybeObject* Map::AddTransition(String* key, Map* target) {
   if (HasTransitionArray()) return transitions()->CopyInsert(key, target);
-  return TransitionArray::NewWith(key, target);
+  JSGlobalPropertyCell* descriptors_pointer = RetrieveDescriptorsPointer();
+  return TransitionArray::NewWith(
+      key, target, descriptors_pointer, GetBackPointer());
 }
 
 
 void Map::SetTransition(int transition_index, Map* target) {
   transitions()->SetTarget(transition_index, target);
 }
 
 
 MaybeObject* Map::set_elements_transition_map(Map* transitioned_map) {
   MaybeObject* allow_elements = EnsureHasTransitionArray(this);
@@ skipping 33 matching lines @@
 
 TransitionArray* Map::transitions() {
   ASSERT(HasTransitionArray());
   Object* object = READ_FIELD(this, kTransitionsOrBackPointerOffset);
   return TransitionArray::cast(object);
 }
 
 
 void Map::set_transitions(TransitionArray* transition_array,
                           WriteBarrierMode mode) {
-  transition_array->set_descriptors(instance_descriptors());
-  transition_array->set_back_pointer_storage(GetBackPointer());
 #ifdef DEBUG
   if (HasTransitionArray()) {
     ASSERT(transitions() != transition_array);
     ZapTransitions();
   }
 #endif
 
   WRITE_FIELD(this, kTransitionsOrBackPointerOffset, transition_array);
   CONDITIONAL_WRITE_BARRIER(
       GetHeap(), this, kTransitionsOrBackPointerOffset, transition_array, mode);
@@ skipping 1767 matching lines @@
 #undef WRITE_UINT32_FIELD
 #undef READ_SHORT_FIELD
 #undef WRITE_SHORT_FIELD
 #undef READ_BYTE_FIELD
 #undef WRITE_BYTE_FIELD
 
 
 } }  // namespace v8::internal
 
 #endif  // V8_OBJECTS_INL_H_