New growth strategy for growable arrays

runtime/vm/object.cc

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #include "vm/object.h"
 
 #include "include/dart_api.h"
 #include "platform/assert.h"
 #include "vm/assembler.h"
 #include "vm/become.h"
@@ skipping 3002 matching lines @@
       // Do not preserve the original implicit constructor, if any.
       orig_implicit_ctor = Function::null();
     }
     func.set_owner(patch_class);
     new_functions.Add(func);
   }
   if (!orig_implicit_ctor.IsNull()) {
     // Preserve the original implicit constructor.
     new_functions.Add(orig_implicit_ctor);
   }
-  Array& new_list = Array::Handle(Array::MakeArray(new_functions));
+  Array& new_list = Array::Handle(Array::MakeFixedLength(new_functions));
   SetFunctions(new_list);
 
   // Merge the two list of fields. Raise an error when duplicates are found or
   // when a public field is being added.
   orig_list = fields();
   orig_len = orig_list.Length();
   patch_list = patch.fields();
   patch_len = patch_list.Length();
 
   Field& field = Field::Handle();
@@ skipping 43 matching lines @@
   for (intptr_t i = 0; i < num_formals; i++) {
     if (i > 0) {
       src_pieces.Add(Symbols::CommaSpace());
     }
     piece ^= formal_params.At(i);
     src_pieces.Add(piece);
   }
   src_pieces.Add(Symbols::RParenArrow());
   src_pieces.Add(expr);
   src_pieces.Add(Symbols::Semicolon());
-  return String::ConcatAll(Array::Handle(Array::MakeArray(src_pieces)));
+  return String::ConcatAll(Array::Handle(Array::MakeFixedLength(src_pieces)));
 }
 
 
 RawFunction* Function::EvaluateHelper(const Class& cls,
                                       const String& expr,
                                       const Array& param_names,
                                       bool is_static) {
   const String& func_src =
       String::Handle(BuildClosureSource(param_names, expr));
   Script& script = Script::Handle();
@@ skipping 5574 matching lines @@
     if (curr == Token::kNEWLINE) {
       for (int i = 0; i < indent; i++) {
         literals.Add(Symbols::TwoSpaces());
       }
     }
 
     // Setup for next iteration.
     prev = curr;
     curr = next;
   }
-  const Array& source = Array::Handle(Array::MakeArray(literals));
+  const Array& source = Array::Handle(Array::MakeFixedLength(literals));
   return String::ConcatAll(source);
 }
 
 
 intptr_t TokenStream::ComputeSourcePosition(TokenPosition tok_pos) const {
   Zone* zone = Thread::Current()->zone();
   Iterator iterator(zone, *this, TokenPosition::kMinSource,
                     Iterator::kAllTokens);
   intptr_t src_pos = 0;
   Token::Kind kind = iterator.CurrentTokenKind();
@@ skipping 700 matching lines @@
     token_pos = Smi::New(0);
     line_starts_list.Add(token_pos);
     while (tkit.CurrentTokenKind() != Token::kEOS) {
       if (tkit.CurrentTokenKind() == Token::kNEWLINE) {
         cur_line++;
         token_pos = Smi::New(tkit.CurrentPosition().value() + 1);
         line_starts_list.Add(token_pos);
       }
       tkit.Advance();
     }
-    line_starts_array = Array::MakeArray(line_starts_list);
+    line_starts_array = Array::MakeFixedLength(line_starts_list);
     set_line_starts(line_starts_array);
   }
 
   ASSERT(line_starts_array.Length() > 0);
   intptr_t offset = target_token_pos.Pos();
   intptr_t min = 0;
   intptr_t max = line_starts_array.Length() - 1;
 
   // Binary search to find the line containing this offset.
   while (min < max) {
@@ skipping 1227 matching lines @@
       for (intptr_t j = 0; j < functions.Length(); j++) {
         func ^= functions.At(j);
         if (func.is_external()) {
           owner_script = func.script();
           AddScriptIfUnique(scripts, owner_script);
         }
       }
     }
 
     // Create the array of scripts and cache it in loaded_scripts_.
-    const Array& scripts_array = Array::Handle(Array::MakeArray(scripts));
+    const Array& scripts_array = Array::Handle(Array::MakeFixedLength(scripts));
     StorePointer(&raw_ptr()->loaded_scripts_, scripts_array.raw());
   }
   return loaded_scripts();
 }
 
 
 // TODO(hausner): we might want to add a script dictionary to the
 // library class to make this lookup faster.
 RawScript* Library::LookupScript(const String& url) const {
   const intptr_t url_length = url.Length();
@@ skipping 11397 matching lines @@
   ASSERT(new_length != len);  // Unnecessary copying of array.
   PassiveObject& obj = PassiveObject::Handle(zone);
   for (int i = 0; i < len; i++) {
     obj = source.At(i);
     result.SetAt(i, obj);
   }
   return result.raw();
 }
 
 
-RawArray* Array::MakeArray(const GrowableObjectArray& growable_array) {
+RawArray* Array::MakeFixedLength(const GrowableObjectArray& growable_array,
+                                 bool unique) {
   ASSERT(!growable_array.IsNull());
+  Thread* thread = Thread::Current();
+  Zone* zone = thread->zone();
   intptr_t used_len = growable_array.Length();
   // Get the type arguments and prepare to copy them.
   const TypeArguments& type_arguments =
       TypeArguments::Handle(growable_array.GetTypeArguments());
-  if ((used_len == 0) && (type_arguments.IsNull())) {
-    // This is a raw List (as in no type arguments), so we can return the
-    // simple empty array.
-    return Object::empty_array().raw();
+  if (used_len == 0) {
+    if (type_arguments.IsNull() && !unique) {
+      // This is a raw List (as in no type arguments), so we can return the
+      // simple empty array.
+      return Object::empty_array().raw();
+    }
+
+    // The backing array may be a shared instance, or may not have correct
+    // type parameters. Create a new empty array.
+    Heap::Space space = thread->IsMutatorThread() ? Heap::kNew : Heap::kOld;
+    Array& array = Array::Handle(zone, Array::New(0, space));
+    array.SetTypeArguments(type_arguments);
+    return array.raw();
   }
   intptr_t capacity_len = growable_array.Capacity();
-  Zone* zone = Thread::Current()->zone();
   const Array& array = Array::Handle(zone, growable_array.data());
   array.SetTypeArguments(type_arguments);
   intptr_t capacity_size = Array::InstanceSize(capacity_len);
   intptr_t used_size = Array::InstanceSize(used_len);
   NoSafepointScope no_safepoint;
 
   // If there is any left over space fill it with either an Array object or
   // just a plain object (depending on the amount of left over space) so
   // that it can be traversed over successfully during garbage collection.
   Object::MakeUnusedSpaceTraversable(array, capacity_size, used_size);
@@ skipping 58 matching lines @@
 RawImmutableArray* ImmutableArray::New(intptr_t len, Heap::Space space) {
   ASSERT(Isolate::Current()->object_store()->immutable_array_class() !=
          Class::null());
   return reinterpret_cast<RawImmutableArray*>(Array::New(kClassId, len, space));
 }
 
 
 void GrowableObjectArray::Add(const Object& value, Heap::Space space) const {
   ASSERT(!IsNull());
   if (Length() == Capacity()) {
-    // TODO(Issue 2500): Need a better growth strategy.
-    intptr_t new_capacity = (Capacity() == 0) ? 4 : Capacity() * 2;
+    // Grow from 0 to 3, and then double + 1.
+    intptr_t new_capacity = (Capacity() * 2) | 3;
     if (new_capacity <= Capacity()) {
       Exceptions::ThrowOOM();
       UNREACHABLE();
     }
     Grow(new_capacity, space);
   }
   ASSERT(Length() < Capacity());
   intptr_t index = Length();
   SetLength(index + 1);
   SetAt(index, value);
@@ skipping 16 matching lines @@
   const Array& contents = Array::Handle(data());
   const PassiveObject& obj = PassiveObject::Handle(contents.At(index));
   contents.SetAt(index, Object::null_object());
   SetLength(index);
   return obj.raw();
 }
 
 
 RawGrowableObjectArray* GrowableObjectArray::New(intptr_t capacity,
                                                  Heap::Space space) {
-  const Array& data = Array::Handle(Array::New(capacity, space));
+  RawArray* raw_data = (capacity == 0) ? Object::empty_array().raw()
+                                       : Array::New(capacity, space);
+  const Array& data = Array::Handle(raw_data);
   return New(data, space);
 }
 
 
 RawGrowableObjectArray* GrowableObjectArray::New(const Array& array,
                                                  Heap::Space space) {
   ASSERT(Isolate::Current()->object_store()->growable_object_array_class() !=
          Class::null());
   GrowableObjectArray& result = GrowableObjectArray::Handle();
   {
@@ skipping 1210 matching lines @@
   return UserTag::null();
 }
 
 
 const char* UserTag::ToCString() const {
   const String& tag_label = String::Handle(label());
   return tag_label.ToCString();
 }
 
 }  // namespace dart