Grow various arrays geometrically rather than linearly.

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 4503 matching lines @@
 }
 
 
 void Class::InsertCanonicalNumber(Zone* zone,
                                   intptr_t index,
                                   const Number& constant) const {
   // The constant needs to be added to the list. Grow the list if it is full.
   Array& canonical_list = Array::Handle(zone, constants());
   const intptr_t list_len = canonical_list.Length();
   if (index >= list_len) {
-    const intptr_t new_length = (list_len == 0) ? 4 : list_len + 4;
+    const intptr_t new_length = list_len + 4 + (list_len >> 2);

[regis, 2017/04/24 16:08:07]

Why a factor of 5? How many canonical numbers are you seeing inserted in this
array?

[regis, 2017/04/24 17:18:14]

As Martin pointed out, this is a right shift, so %25 increase.

     canonical_list ^= Array::Grow(canonical_list, new_length, Heap::kOld);
     set_constants(canonical_list);
   }
   canonical_list.SetAt(index, constant);
 }
 
 
 void Class::RehashConstants(Zone* zone) const {
   intptr_t cid = id();
   if ((cid == kMintCid) || (cid == kBigintCid) || (cid == kDoubleCid)) {
@@ skipping 546 matching lines @@
   }
   // Instantiation did not result in bound error. Canonicalize type arguments.
   result = result.Canonicalize();
   // InstantiateAndCanonicalizeFrom is not reentrant. It cannot have been called
   // indirectly, so the prior_instantiations array cannot have grown.
   ASSERT(prior_instantiations.raw() == instantiations());
   // Add instantiator and function type args and result to instantiations array.
   intptr_t length = prior_instantiations.Length();
   if ((index + StubCode::kInstantiationSizeInWords) >= length) {
     // TODO(regis): Should we limit the number of cached instantiations?
-    // Grow the instantiations array.
+    // Grow the instantiations array by about 50%, but at least by 1.

[regis, 2017/04/24 16:08:07]

50%? Your change looks rather like a factor 2 to me, i.e. 100%. Also, do you
really need the division? Previous measurements showed a very limited number of
instantiations. Does this change with fasta?

[regis, 2017/04/24 17:18:14]

Never mind. Right shift again.

     // The initial array is Object::zero_array() of length 1.
-    length = (length > 64)
-                 ? (length + 64)
-                 : ((length == 1) ? StubCode::kInstantiationSizeInWords + 1
-                                  : ((length - 1) * 2 + 1));
+    intptr_t entries = (length - 1) / StubCode::kInstantiationSizeInWords;
+    intptr_t new_entries = entries + (entries >> 1) + 1;
+    length = new_entries * StubCode::kInstantiationSizeInWords + 1;
     prior_instantiations =
         Array::Grow(prior_instantiations, length, Heap::kOld);
     set_instantiations(prior_instantiations);
     ASSERT((index + StubCode::kInstantiationSizeInWords) < length);
   }
   prior_instantiations.SetAt(index + 0, instantiator_type_arguments);
   prior_instantiations.SetAt(index + 1, function_type_arguments);
   prior_instantiations.SetAt(index + 2, result);
   prior_instantiations.SetAt(index + 3,
                              Smi::Handle(Smi::New(StubCode::kNoInstantiator)));
@@ skipping 5759 matching lines @@
   StorePointer(&raw_ptr()->resolved_names_, Array::null());
   StorePointer(&raw_ptr()->exported_names_, Array::null());
   StorePointer(&raw_ptr()->loaded_scripts_, Array::null());
 }
 
 
 void Library::AddImport(const Namespace& ns) const {
   Array& imports = Array::Handle(this->imports());
   intptr_t capacity = imports.Length();
   if (num_imports() == capacity) {
-    capacity = capacity + kImportsCapacityIncrement;
+    capacity = capacity + kImportsCapacityIncrement + (capacity >> 2);

[regis, 2017/04/24 16:08:07]

Factor 3?

[regis, 2017/04/24 17:18:14]

No.

     imports = Array::Grow(imports, capacity);
     StorePointer(&raw_ptr()->imports_, imports.raw());
   }
   intptr_t index = num_imports();
   imports.SetAt(index, ns);
   set_num_imports(index + 1);
 }
 
 
 // Convenience function to determine whether the export list is
@@ skipping 539 matching lines @@
   intptr_t num_current_imports = num_imports();
 
   // Prefixes with deferred libraries can only contain one library.
   ASSERT((num_current_imports == 0) || !is_deferred_load());
 
   // The library needs to be added to the list.
   Array& imports = Array::Handle(this->imports());
   const intptr_t length = (imports.IsNull()) ? 0 : imports.Length();
   // Grow the list if it is full.
   if (num_current_imports >= length) {
-    const intptr_t new_length = length + kIncrementSize;
+    const intptr_t new_length = length + kIncrementSize + (length >> 2);

[regis, 2017/04/24 16:08:07]

ditto

     imports = Array::Grow(imports, new_length, Heap::kOld);
     set_imports(imports);
   }
   imports.SetAt(num_current_imports, import);
   set_num_imports(num_current_imports + 1);
 }
 
 
 RawObject* LibraryPrefix::LookupObject(const String& name) const {
   if (!is_loaded() && !FLAG_load_deferred_eagerly) {
@@ skipping 11850 matching lines @@
   return UserTag::null();
 }
 
 
 const char* UserTag::ToCString() const {
   const String& tag_label = String::Handle(label());
   return tag_label.ToCString();
 }
 
 }  // namespace dart