Ensure newly allocated empty Arrays are transitioned to FAST_ELEMENT

src/objects.cc

 // Copyright 2011 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 1159 matching lines @@
       accumulator->Put('>');
       break;
     }
   }
 }
 
 
 void JSObject::PrintElementsTransition(
     FILE* file, ElementsKind from_kind, FixedArrayBase* from_elements,
     ElementsKind to_kind, FixedArrayBase* to_elements) {
+  PrintF(file, "elements transition [");
+  PrintElementsKind(file, from_kind);
+  PrintF(file, " -> ");
+  PrintElementsKind(file, to_kind);
+  PrintF(file, "] in ");
+  JavaScriptFrame::PrintTop(file, false, true);
+  PrintF(file, " for ");
+  ShortPrint(file);
+  PrintF(file, " from ");
+  from_elements->ShortPrint(file);
+  PrintF(file, " to ");
+  to_elements->ShortPrint(file);
+  PrintF(file, "\n");
+}
+
+enum {
+  kFastElementArrayBiasIncrement = 1,
+  kFastElementArrayBiasThreshold = 3,
+  kFastSmiOnlyElementArrayBiasIncrement = -10,
+  kFastSmiOnlyElementArrayBiasThreshold = -30
+};
+
+
+void JSObject::RecordElementsTransition(
+    ElementsKind from_kind, FixedArrayBase* from_elements,
+    ElementsKind to_kind, FixedArrayBase* to_elements) {
   if (from_kind != to_kind) {
-    PrintF(file, "elements transition [");
-    PrintElementsKind(file, from_kind);
-    PrintF(file, " -> ");
-    PrintElementsKind(file, to_kind);
-    PrintF(file, "] in ");
-    JavaScriptFrame::PrintTop(file, false, true);
-    PrintF(file, " for ");
-    ShortPrint(file);
-    PrintF(file, " from ");
-    from_elements->ShortPrint(file);
-    PrintF(file, " to ");
-    to_elements->ShortPrint(file);
-    PrintF(file, "\n");
+    if (FLAG_trace_elements_transitions) {
+      PrintElementsTransition(stdout, from_kind, from_elements,
+                              to_kind, to_elements);
+    }
+  }
+
+  // Use elements transitions to determine whether Array() should by default
+  // return an array of type FAST_SMI_ONLY_ELEMENTS or FAST_ELEMENTS. Defaulting
+  // to FAST_ELEMENTS save the expense of element transition for code that
+  // doesn't make use of double arrays.  More FAST_ELEMENTS transitions than
+  // FAST_DOUBLE_ELEMENTS transitions suggest that Array() should always return
+  // elements kinds of FAST_ELEMENTS. However, FAST_DOUBLE_ELEMENTS
+  // transitions are weighted an order of magnitude heavier than FAST_ELEMENT
+  // transitions, since the savings is in general much greater if the runtime
+  // can recognize and exploit FAST_DOUBLE_ELEMENTS, even at the expense of
+  // extra transitions.
+  Context* global_context = GetIsolate()->context()->global_context();
+  if (global_context->untransitioned_js_array_map() != NULL &&

[Jakob Kummerow, 2012/01/04 20:55:17]

Don't you mean s/NULL/GetHeap()->undefined_value()/? (cf. changes to heap.cc)

+      IsJSArray() && from_kind == FAST_SMI_ONLY_ELEMENTS) {
+    Object* bias_object = global_context->fast_array_element_bias();
+    if (!bias_object->IsUndefined()) {
+      int bias = Smi::cast(bias_object)->value();
+      if (to_kind == FAST_ELEMENTS) {
+        bias += kFastElementArrayBiasIncrement;
+      } else {
+        ASSERT(to_kind == FAST_DOUBLE_ELEMENTS);
+        bias += kFastSmiOnlyElementArrayBiasIncrement;
+      }
+      global_context->set_fast_array_element_bias(Smi::FromInt(bias));
+      if (bias > kFastElementArrayBiasThreshold) {
+        JSFunction* array_function = global_context->array_function();
+        Map* untransitioned_map = Map::cast(
+            global_context->untransitioned_js_array_map());
+        if (untransitioned_map == array_function->initial_map()) {
+          if (untransitioned_map->elements_kind() == FAST_SMI_ONLY_ELEMENTS) {
+            bool dummy;
+            Map* transitioned_map =
+                untransitioned_map->LookupElementsTransitionMap(FAST_ELEMENTS,
+                                                         &dummy);

[Jakob Kummerow, 2012/01/04 20:55:17]

nit: indentation

+            if (transitioned_map != NULL) {
+              array_function->set_initial_map(transitioned_map);
+            }
+          }
+        }
+      } else if (bias < kFastSmiOnlyElementArrayBiasThreshold) {
+        JSFunction* array_function = global_context->array_function();
+        Map* untransitioned_map = Map::cast(
+            global_context->untransitioned_js_array_map());
+        if (!untransitioned_map->IsUndefined() &&
+            untransitioned_map != array_function->initial_map()) {
+          bool dummy;
+          Map* transitioned_map =
+              untransitioned_map->LookupElementsTransitionMap(FAST_ELEMENTS,
+                                                              &dummy);
+          if (transitioned_map == array_function->initial_map()) {
+            array_function->set_initial_map(untransitioned_map);
+          }
+        }
+      }
+    }
   }
 }
 
 
 void HeapObject::HeapObjectShortPrint(StringStream* accumulator) {
   Heap* heap = GetHeap();
   if (!heap->Contains(this)) {
     accumulator->Add("!!!INVALID POINTER!!!");
     return;
   }
@@ skipping 972 matching lines @@
   } else {
     result->NotFound();
   }
 }
 
 
 void Map::LookupInDescriptors(JSObject* holder,
                               String* name,
                               LookupResult* result) {
   DescriptorArray* descriptors = instance_descriptors();
-  DescriptorLookupCache* cache =
-      GetHeap()->isolate()->descriptor_lookup_cache();
-  int number = cache->Lookup(descriptors, name);
-  if (number == DescriptorLookupCache::kAbsent) {
-    number = descriptors->Search(name);
-    cache->Update(descriptors, name, number);
-  }
+  int number = descriptors->SearchWithCache(name);
   if (number != DescriptorArray::kNotFound) {
     result->DescriptorResult(holder, descriptors->GetDetails(number), number);
   } else {
     result->NotFound();
   }
 }
 
 
 static bool ContainsMap(MapHandleList* maps, Handle<Map> map) {
   ASSERT(!map.is_null());
@@ skipping 120 matching lines @@
 
 String* Map::elements_transition_sentinel_name() {
   return GetHeap()->empty_symbol();
 }
 
 
 Object* Map::GetDescriptorContents(String* sentinel_name,
                                    bool* safe_to_add_transition) {
   // Get the cached index for the descriptors lookup, or find and cache it.
   DescriptorArray* descriptors = instance_descriptors();
-  DescriptorLookupCache* cache = GetIsolate()->descriptor_lookup_cache();
-  int index = cache->Lookup(descriptors, sentinel_name);
-  if (index == DescriptorLookupCache::kAbsent) {
-    index = descriptors->Search(sentinel_name);
-    cache->Update(descriptors, sentinel_name, index);
-  }
+  int index = descriptors->SearchWithCache(sentinel_name);
   // If the transition already exists, return its descriptor.
   if (index != DescriptorArray::kNotFound) {
     PropertyDetails details(descriptors->GetDetails(index));
     if (details.type() == ELEMENTS_TRANSITION) {
       return descriptors->GetValue(index);
     } else {
       *safe_to_add_transition = false;
     }
   }
   return NULL;
@@ skipping 5924 matching lines @@
     case EXTERNAL_UNSIGNED_SHORT_ELEMENTS:
     case EXTERNAL_INT_ELEMENTS:
     case EXTERNAL_UNSIGNED_INT_ELEMENTS:
     case EXTERNAL_FLOAT_ELEMENTS:
     case EXTERNAL_DOUBLE_ELEMENTS:
     case EXTERNAL_PIXEL_ELEMENTS:
       UNREACHABLE();
       break;
   }
 
-  if (FLAG_trace_elements_transitions) {
-    PrintElementsTransition(stdout, elements_kind, old_elements_raw,
-                            FAST_ELEMENTS, new_elements);
-  }
+  RecordElementsTransition(elements_kind, old_elements_raw,
+                           FAST_ELEMENTS, new_elements);
 
   // Update the length if necessary.
   if (IsJSArray()) {
     JSArray::cast(this)->set_length(Smi::FromInt(length));
   }
 
   return new_elements;
 }
 
 
@@ skipping 32 matching lines @@
     }
     case DICTIONARY_ELEMENTS: {
       elems->Initialize(NumberDictionary::cast(old_elements));
       break;
     }
     default:
       UNREACHABLE();
       break;
   }
 
-  if (FLAG_trace_elements_transitions) {
-    PrintElementsTransition(stdout, elements_kind, old_elements,
-                            FAST_DOUBLE_ELEMENTS, elems);
-  }
+  RecordElementsTransition(elements_kind, old_elements,
+                           FAST_DOUBLE_ELEMENTS, elems);
 
   ASSERT(new_map->has_fast_double_elements());
   set_map(new_map);
   ASSERT(elems->IsFixedDoubleArray());
   set_elements(elems);
 
   if (IsJSArray()) {
     JSArray::cast(this)->set_length(Smi::FromInt(length));
   }
 
@@ skipping 758 matching lines @@
   // Convert to fast double elements if appropriate.
   if (HasFastSmiOnlyElements() && !value->IsSmi() && value->IsNumber()) {
     MaybeObject* maybe =
         SetFastDoubleElementsCapacityAndLength(new_capacity, array_length);
     if (maybe->IsFailure()) return maybe;
     FixedDoubleArray::cast(elements())->set(index, value->Number());
     return value;
   }
   // Change elements kind from SMI_ONLY to generic FAST if necessary.
   if (HasFastSmiOnlyElements() && !value->IsSmi()) {
-    MaybeObject* maybe_new_map = GetElementsTransitionMap(FAST_ELEMENTS);
-    Map* new_map;
-    if (!maybe_new_map->To<Map>(&new_map)) return maybe_new_map;
-    set_map(new_map);
-    if (FLAG_trace_elements_transitions) {
-      PrintElementsTransition(stdout, FAST_SMI_ONLY_ELEMENTS, elements(),
-                              FAST_ELEMENTS, elements());
-    }
+    MaybeObject* maybe = TransitionElementsKind(FAST_ELEMENTS);
+    if (maybe->IsFailure()) return maybe;
   }
   // Increase backing store capacity if that's been decided previously.
   if (new_capacity != capacity) {
     Object* new_elements;
     SetFastElementsCapacityMode set_capacity_mode =
         value->IsSmi() && HasFastSmiOnlyElements()
             ? kAllowSmiOnlyElements
             : kDontAllowSmiOnlyElements;
     MaybeObject* maybe =
         SetFastElementsCapacityAndLength(new_capacity,
@@ skipping 348 matching lines @@
   // All possible cases have been handled above. Add a return to avoid the
   // complaints from the compiler.
   UNREACHABLE();
   return isolate->heap()->null_value();
 }
 
 
 MUST_USE_RESULT MaybeObject* JSObject::TransitionElementsKind(
     ElementsKind to_kind) {
   ElementsKind from_kind = map()->elements_kind();
+  if (from_kind == to_kind) return this;
+
   FixedArrayBase* elms = FixedArrayBase::cast(elements());
   uint32_t capacity = static_cast<uint32_t>(elms->length());
   uint32_t length = capacity;
 
   if (IsJSArray()) {
     Object* raw_length = JSArray::cast(this)->length();
     if (raw_length->IsUndefined()) {
       // If length is undefined, then JSArray is being initialized and has no
       // elements, assume a length of zero.
       length = 0;
     } else {
       CHECK(JSArray::cast(this)->length()->ToArrayIndex(&length));
     }
   }
 
   if ((from_kind == FAST_SMI_ONLY_ELEMENTS && to_kind == FAST_ELEMENTS) ||
       (length == 0)) {
     MaybeObject* maybe_new_map = GetElementsTransitionMap(to_kind);
     Map* new_map;
     if (!maybe_new_map->To(&new_map)) return maybe_new_map;
-    if (FLAG_trace_elements_transitions) {
-      PrintElementsTransition(stdout, from_kind, elms, to_kind, elms);
-    }
+    RecordElementsTransition(from_kind, elms, to_kind, elms);
     set_map(new_map);
     return this;
   }
 
   if (from_kind == FAST_SMI_ONLY_ELEMENTS &&
       to_kind == FAST_DOUBLE_ELEMENTS) {
     MaybeObject* maybe_result =
         SetFastDoubleElementsCapacityAndLength(capacity, length);
     if (maybe_result->IsFailure()) return maybe_result;
     return this;
@@ skipping 3042 matching lines @@
   if (break_point_objects()->IsUndefined()) return 0;
   // Single break point.
   if (!break_point_objects()->IsFixedArray()) return 1;
   // Multiple break points.
   return FixedArray::cast(break_point_objects())->length();
 }
 #endif  // ENABLE_DEBUGGER_SUPPORT
 
 
 } }  // namespace v8::internal