New growth strategy for growable arrays

runtime/vm/object.cc

Index: runtime/vm/object.cc
diff --git a/runtime/vm/object.cc b/runtime/vm/object.cc
index 728e2ffe6446a8833d056194b9aef8d727408440..0999b999ca98f421c00ab3ff3d3c3c304750d938 100644
--- a/runtime/vm/object.cc
+++ b/runtime/vm/object.cc
@@ -22066,19 +22066,30 @@ RawArray* Array::Grow(const Array& source,
 }
 
 
-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);
@@ -22157,8 +22168,7 @@ RawImmutableArray* ImmutableArray::New(intptr_t len, Heap::Space 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();
@@ -22195,7 +22205,9 @@ RawObject* GrowableObjectArray::RemoveLast() const {
 
 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);
 }