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 22048 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::MakeArray(const GrowableObjectArray& growable_array,

[erikcorry, 2017/06/21 09:06:01]

Perhaps call this MakeNongrowableArray?

[Lasse Reichstein Nielsen, 2017/06/21 09:14:15]

Or MakeArrayNongrowable, which doesn't sound as if "Make" means "Create" (which
it does when followed by a noun phrase).

[Aske Simon Christensen, 2017/06/21 12:19:33]

Array::MakeFixedLength corresponds to the Dart-side makeListFixedLength which is
a wrapper for it.

+                           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

[Lasse Reichstein Nielsen, 2017/06/21 07:36:21]

This function isn't talking about "backing arrays" otherwise, so it's unclear
what it means here. I assume this function handles all allocation of
fixed-length lists (_List instances), not just backing arrays of growable
arrays.

[erikcorry, 2017/06/21 07:58:31]

The naming of this method is terrible.  It's not used for all allocation of
fixed-length lists.  What this tricky method does is to take a growable list
(list object with fixed length backing list) and returns a non-growable list. 
Usually it does this by extracting and trimming the backing and returning that.

[Lasse Reichstein Nielsen, 2017/06/21 09:14:15]

ACK, my bad. I actually recognized that at the call point and promptly forgot it
again when I got here.

+    // 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;
+    intptr_t new_capacity = (Capacity() == 0) ? 3 : Capacity() * 2 + 1;

[erikcorry, 2017/06/21 09:06:01]

Lasse's trick for branchless calculations works here too.

     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