Avoid numerous type allocations by caching the canonical type of a class, which

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/cpu.h"
@@ skipping 1066 matching lines @@
   object_store->set_empty_context(context);
 
   // Now that the symbol table is initialized and that the core dictionary as
   // well as the core implementation dictionary have been setup, preallocate
   // remaining classes and register them by name in the dictionaries.
   String& name = String::Handle(isolate);
   cls = object_store->array_class();  // Was allocated above.
   RegisterPrivateClass(cls, Symbols::_List(), core_lib);
   pending_classes.Add(cls);
   // We cannot use NewNonParameterizedType(cls), because Array is parameterized.
+  // Warning: class _List has not been patched yet. Its declared number of type
+  // parameters is still 0. It will become 1 after patching. The array type
+  // allocated below represents the raw type _List and not _List<E> as we
+  // could expect. Use with caution.
   type ^= Type::New(Object::Handle(isolate, cls.raw()),
                     TypeArguments::Handle(isolate),
                     Scanner::kNoSourcePos);
   type.SetIsFinalized();
   type ^= type.Canonicalize();
   object_store->set_array_type(type);
 
   cls = object_store->growable_object_array_class();  // Was allocated above.
   RegisterPrivateClass(cls, Symbols::_GrowableList(), core_lib);
   pending_classes.Add(cls);
@@ skipping 770 matching lines @@
   const Function& function = Function::Handle(signature_function());
   ASSERT(!function.IsNull());
   if (function.signature_class() != raw()) {
     // This class is a function type alias. Return the canonical signature type.
     const Class& canonical_class = Class::Handle(function.signature_class());
     return canonical_class.SignatureType();
   }
   // Return the first canonical signature type if already computed at class
   // finalization time. The optimizer may canonicalize instantiated function
   // types of the same signature class, but these will be added after the
-  // uninstantiated signature class at index 0.
+  // uninstantiated signature class at index 1.
   Array& signature_types = Array::Handle();
   signature_types ^= canonical_types();
   if (signature_types.IsNull()) {
     set_canonical_types(empty_array());
     signature_types ^= canonical_types();
   }
   // The canonical_types array is initialized to the empty array.
   ASSERT(!signature_types.IsNull());
   if (signature_types.Length() > 0) {
+    ASSERT(signature_types.Length() > 1);
     Type& signature_type = Type::Handle();
-    signature_type ^= signature_types.At(0);
+    signature_type ^= signature_types.At(1);
     ASSERT(!signature_type.IsNull());
     return signature_type.raw();
   }
   // A signature class extends class Instance and is parameterized in the same
   // way as the owner class of its non-static signature function.
   // It is not type parameterized if its signature function is static.
   // See Class::NewSignatureClass() for the setup of its type parameters.
   // During type finalization, the type arguments of the super class of the
   // owner class of its signature function will be prepended to the type
   // argument vector. Therefore, we only need to set the type arguments
@@ skipping 1697 matching lines @@
   return raw_ptr()->canonical_types_;
 }
 
 
 void Class::set_canonical_types(const Object& value) const {
   ASSERT(!value.IsNull());
   StorePointer(&raw_ptr()->canonical_types_, value.raw());
 }
 
 
-intptr_t Class::NumCanonicalTypes() const {
-  if (CanonicalType() != Type::null()) {
-    return 1;
+RawType* Class::CanonicalType() const {
+  if ((NumTypeArguments() == 0) && !IsSignatureClass()) {
+    return reinterpret_cast<RawType*>(raw_ptr()->canonical_types_);
   }
-  const Object& types = Object::Handle(canonical_types());
-  if (types.IsNull()) {
-    return 0;
+  Array& types = Array::Handle();
+  types ^= canonical_types();
+  if (!types.IsNull() && types.Length() > 0) {

[srdjan, 2015/08/21 05:02:20]

Add parenthesis.

[regis, 2015/08/21 15:38:21]

Done.

+    return reinterpret_cast<RawType*>(types.At(0));
   }
-  intptr_t num_types = Array::Cast(types).Length();
-  while ((num_types > 0) &&
-         (Array::Cast(types).At(num_types - 1) == Type::null())) {
-    num_types--;
-  }
-  return num_types;
+  return reinterpret_cast<RawType*>(Object::null());
 }
 
 
+void Class::SetCanonicalType(const Type& type) const {
+  ASSERT(type.IsCanonical());
+  if ((NumTypeArguments() == 0) && !IsSignatureClass()) {

[srdjan, 2015/08/21 05:02:20]

Should we factor out this test? Only if we can come up with a descriptive name
that is shorter than this test :-).

[regis, 2015/08/21 15:38:21]

I cannot think of a good name :-)
In any case, I think it is only needed here and in the setter above. I will try
to remove it from other places where I do not think it is necessary.

+    ASSERT((canonical_types() == Object::null() ||
+           (canonical_types() == type.raw())));  // Set during own finalization.
+    set_canonical_types(type);

[srdjan, 2015/08/21 05:02:20]

Can we clear it ever, i.e., type -> null ? If it is the same, maybe skip writing
it? Is that check worth it?

[regis, 2015/08/21 15:38:21]

No, we cannot clear it. However, from the time we notice it was null and start
computing it, it may have been set via recursion.
I think it would be bad if it set to a different type than the one we just
calculated.

+  } else {
+    Array& types = Array::Handle();
+    types ^= canonical_types();
+    ASSERT(!types.IsNull() && (types.Length() > 1));
+    ASSERT((types.At(0) == Object::null()) || (types.At(0) == type.raw()));
+    types.SetAt(0, type);
+  }
+}
+
+
 intptr_t Class::FindCanonicalTypeIndex(const Type& needle) const {
   Isolate* isolate = Isolate::Current();
   if (EnsureIsFinalized(isolate) != Error::null()) {
     return -1;
   }
   if (needle.raw() == CanonicalType()) {
+    // For a generic type or signature type, there exists another index with the
+    // same type. It will never be returned by this function.
     return 0;
   }
   REUSABLE_OBJECT_HANDLESCOPE(isolate);
   Object& types = isolate->ObjectHandle();
   types = canonical_types();
   if (types.IsNull()) {
     return -1;
   }
   const intptr_t len = Array::Cast(types).Length();
   REUSABLE_ABSTRACT_TYPE_HANDLESCOPE(isolate);
@@ skipping 10745 matching lines @@
   result.SetCanonical();
   return result.raw();
 }
 
 
 RawType* Instance::GetType() const {
   if (IsNull()) {
     return Type::NullType();
   }
   const Class& cls = Class::Handle(clazz());
-  Type& type = Type::Handle(cls.CanonicalType());
+  Type& type = Type::Handle();
+  if (cls.NumTypeArguments() == 0) {
+    type = cls.CanonicalType();
+  }
   if (type.IsNull()) {
     TypeArguments& type_arguments = TypeArguments::Handle();
     if (cls.NumTypeArguments() > 0) {
       type_arguments = GetTypeArguments();
     }
     type = Type::New(cls, type_arguments, Scanner::kNoSourcePos);
     type.SetIsFinalized();
     type ^= type.Canonicalize();
   }
   return type.raw();
@@ skipping 1254 matching lines @@
   Array& canonical_types = Array::Handle(isolate);
   canonical_types ^= cls.canonical_types();
   if (canonical_types.IsNull()) {
     canonical_types = empty_array().raw();
   }
   intptr_t length = canonical_types.Length();
   // Linear search to see whether this type is already present in the
   // list of canonicalized types.
   // TODO(asiva): Try to re-factor this lookup code to make sharing
   // easy between the 4 versions of this loop.
-  intptr_t index = 0;
+  intptr_t index = 1;  // Slot 0 is reserved for CanonicalType().
   while (index < length) {
     type ^= canonical_types.At(index);
     if (type.IsNull()) {
       break;
     }
     ASSERT(type.IsFinalized());
     if (this->Equals(type)) {
       ASSERT(type.IsCanonical());
       return type.raw();
     }
@@ skipping 23 matching lines @@
     }
     ASSERT(type.IsFinalized());
     if (this->Equals(type)) {
       ASSERT(type.IsCanonical());
       return type.raw();
     }
     index++;
   }
 
   // The type needs to be added to the list. Grow the list if it is full.
-  if (index == length) {
+  if (index >= length) {
+    ASSERT((index == length) || ((index == 1) && (length == 0)));
     const intptr_t new_length = (length > 64) ?
         (length + 64) :
-        ((length == 0) ? 1 : (length * 2));
+        ((length == 0) ? 2 : (length * 2));
     const Array& new_canonical_types = Array::Handle(
         isolate, Array::Grow(canonical_types, new_length, Heap::kOld));
     cls.set_canonical_types(new_canonical_types);
     new_canonical_types.SetAt(index, *this);
   } else {
     canonical_types.SetAt(index, *this);
   }
 #ifdef DEBUG
-  if ((index == 0) && cls.IsCanonicalSignatureClass()) {
+  if ((index == 1) && cls.IsCanonicalSignatureClass()) {
     // Verify that the first canonical type is the signature type by checking
     // that the type argument vector of the canonical type ends with the
     // uninstantiated type parameters of the signature class. Note that these
     // type parameters may be bounded if the super class of the owner class
     // declares bounds.
     // The signature type is finalized during class finalization, before the
     // optimizer may canonicalize instantiated function types of the same
     // signature class.
     // Although the signature class extends class Instance, the type arguments
     // of the super class of the owner class of its signature function will be
@@ skipping 5679 matching lines @@
   return tag_label.ToCString();
 }
 
 
 void UserTag::PrintJSONImpl(JSONStream* stream, bool ref) const {
   Instance::PrintJSONImpl(stream, ref);
 }
 
 
 }  // namespace dart