Store canonical type argments in a hash table instead of linear list.

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/bigint_operations.h"
@@ skipping 555 matching lines @@
   // declared in RawArray.
   cls.set_type_arguments_field_offset(Array::type_arguments_offset());
 
   // Set up the growable object array class (Has to be done after the array
   // class is setup as one of its field is an array object).
   cls = Class::New<GrowableObjectArray>();
   object_store->set_growable_object_array_class(cls);
   cls.set_type_arguments_field_offset(
       GrowableObjectArray::type_arguments_offset());
 
-  // canonical_type_arguments_ are NULL terminated.
-  array = Array::New(4);
+  // canonical_type_arguments_ are Smi terminated.
+  // Last element contains the count of used slots.
+  const intptr_t kInitialCanonicalTypeArgumentsSize = 4;
+  array = Array::New(kInitialCanonicalTypeArgumentsSize + 1);
+  array.SetAt(kInitialCanonicalTypeArgumentsSize, Smi::Handle(Smi::New(0)));
   object_store->set_canonical_type_arguments(array);
 
   // Setup type class early in the process.
   cls = Class::New<Type>();
   object_store->set_type_class(cls);
 
   cls = Class::New<TypeParameter>();
   object_store->set_type_parameter_class(cls);
 
   // Pre-allocate the OneByteString class needed by the symbol table.
@@ skipping 1905 matching lines @@
 }
 
 
 bool AbstractTypeArguments::IsUninstantiatedIdentity() const {
   // AbstractTypeArguments is an abstract class.
   UNREACHABLE();
   return false;
 }
 
 
+static uword FinalizeHash(uword hash) {
+  hash += hash << 3;
+  hash ^= hash >> 11;
+  hash += hash << 15;
+  return hash;
+}
+
+
+uword AbstractTypeArguments::Hash() const {
+  if (IsNull()) return 0;
+  uword result = 0;
+  intptr_t num_types = Length();
+  AbstractType& type = AbstractType::Handle();
+  for (intptr_t i = 0; i < num_types; i++) {
+    type = TypeAt(i);
+    result += type.Hash();
+    result += result << 10;
+    result ^= result >> 6;
+  }
+  return FinalizeHash(result);
+}
+
+
 RawString* AbstractTypeArguments::SubvectorName(
     intptr_t from_index,
     intptr_t len,
     NameVisibility name_visibility) const {
   ASSERT(from_index + len <= Length());
   String& name = String::Handle();
   const intptr_t num_strings = 2*len + 1;  // "<""T"", ""T"">".
   const Array& strings = Array::Handle(Array::New(num_strings));
   intptr_t s = 0;
   strings.SetAt(s++, String::Handle(Symbols::New("<")));
@@ skipping 189 matching lines @@
 }
 
 
 const char* AbstractTypeArguments::ToCString() const {
   // AbstractTypeArguments is an abstract class, valid only for representing
   // null.
   if (IsNull()) {
     return "NULL AbstractTypeArguments";
   }
   UNREACHABLE();
-  return "AbstractTypeArguments";
+  return NULL;

[Ivan Posva, 2012/12/12 21:25:10]

Please leave this as it was. All other abstract classes keep returning the name.

[Florian Schneider, 2012/12/13 11:59:45]

Fine.

 }
 
 
 intptr_t TypeArguments::Length() const {
   ASSERT(!IsNull());
   return Smi::Value(raw_ptr()->length_);
 }
 
 
 RawAbstractType* TypeArguments::TypeAt(intptr_t index) const {
@@ skipping 103 matching lines @@
 
 
 void TypeArguments::SetLength(intptr_t value) const {
   ASSERT(!IsCanonical());
   // This is only safe because we create a new Smi, which does not cause
   // heap allocation.
   raw_ptr()->length_ = Smi::New(value);
 }
 
 
+static void GrowCanonicalTypeArguments(Isolate* isolate, const Array& table) {

[Ivan Posva, 2012/12/12 21:25:10]

Do not pass Isolate as a parameter unless it is a very frequently called
function as it pollutes the API.

+  // Last element of the array is the number of used elements.
+  intptr_t table_size = table.Length() - 1;
+  intptr_t new_table_size = table_size * 2;
+  Array& new_table = Array::Handle(isolate, Array::New(new_table_size + 1));
+  // Copy all elements from the original table to the newly allocated
+  // array.
+  TypeArguments& element = TypeArguments::Handle(isolate);
+  Object& new_element = Object::Handle(isolate);
+  for (intptr_t i = 0; i < table_size; i++) {
+    element ^= table.At(i);
+    if (!element.IsNull()) {
+      intptr_t hash = element.Hash();
+      ASSERT(Utils::IsPowerOfTwo(new_table_size));
+      intptr_t index = hash & (new_table_size - 1);
+      new_element = new_table.At(index);
+      while (!new_element.IsNull()) {
+        index = (index + 1) & (new_table_size - 1);  // Move to next element.
+        new_element = new_table.At(index);
+      }
+      new_table.SetAt(index, element);
+    }
+  }
+  // Copy used count.
+  new_element = table.At(table_size);
+  new_table.SetAt(new_table_size, new_element);
+  // Remember the new table now.
+  isolate->object_store()->set_canonical_type_arguments(new_table);
+}
+
+
+static void InsertIntoCanonicalTypeArguments(Isolate* isolate,

[Ivan Posva, 2012/12/12 21:25:10]

ditto

+                                             const Array& table,
+                                             const TypeArguments& arguments,
+                                             intptr_t index) {
+  arguments.SetCanonical();  // Mark object as being canonical.
+  table.SetAt(index, arguments);  // Remember the new element.
+  // Update used count.
+  // Last element of the array is the number of used elements.
+  intptr_t table_size = table.Length() - 1;
+  Smi& used = Smi::Handle(isolate);
+  used ^= table.At(table_size);
+  intptr_t used_elements = used.Value() + 1;
+  used = Smi::New(used_elements);
+  table.SetAt(table_size, used);
+
+  // Rehash if table is 75% full.
+  if (used_elements > ((table_size / 4) * 3)) {
+    GrowCanonicalTypeArguments(isolate, table);
+  }
+}
+
+
+static intptr_t FindIndexInCanonicalTypeArguments(
+    Isolate* isolate,

[Ivan Posva, 2012/12/12 21:25:10]

ditto

[Florian Schneider, 2012/12/13 11:59:45]

This is frequently called in checked mode. The two other functions here are also
local helpers for TypeArguments::Canonicalize, so I'm not worried about
pollution here.

+    const Array& table,
+    const TypeArguments& arguments,
+    intptr_t hash) {
+  // Last element of the array is the number of used elements.
+  intptr_t table_size = table.Length() - 1;
+  ASSERT(Utils::IsPowerOfTwo(table_size));
+  intptr_t index = hash & (table_size - 1);
+
+  TypeArguments& current = TypeArguments::Handle(isolate);
+  current ^= table.At(index);
+  while (!current.IsNull() && !current.Equals(arguments)) {
+    index = (index + 1) & (table_size - 1);  // Move to next element.
+    current ^= table.At(index);
+  }
+  return index;  // Index of element if found or slot into which to add it.
+}
+
+
 RawAbstractTypeArguments* TypeArguments::Canonicalize() const {
   if (IsNull() || IsCanonical()) {
     ASSERT(IsOld());
     return this->raw();
   }
-  ObjectStore* object_store = Isolate::Current()->object_store();
-  // 'table' must be null terminated.
-  Array& table = Array::Handle(object_store->canonical_type_arguments());
+  Isolate* isolate = Isolate::Current();
+  ObjectStore* object_store = isolate->object_store();
+  const Array& table = Array::Handle(isolate,
+                                     object_store->canonical_type_arguments());
   ASSERT(table.Length() > 0);
-  intptr_t index = 0;
-  TypeArguments& result = TypeArguments::Handle();
+  TypeArguments& self = TypeArguments::Handle(isolate, this->raw());

[Ivan Posva, 2012/12/12 21:25:10]

Why do you need to allocate a new handle here? this is a handle already.

[Florian Schneider, 2012/12/13 11:59:45]

Done.

+  intptr_t index = FindIndexInCanonicalTypeArguments(isolate,
+                                                     table,
+                                                     self,
+                                                     Hash());
+  TypeArguments& result = TypeArguments::Handle(isolate);
   result ^= table.At(index);
-  while (!result.IsNull()) {
-    if (this->Equals(result)) {
-      return result.raw();
+  if (result.IsNull()) {
+    // Make sure we have an old space object and add it to the table.
+    result ^= this->raw();

[Ivan Posva, 2012/12/12 21:25:10]

if (this->IsNew()) {
  result ^= Object::Clone(...);
} else {
  result ^= this->raw();
}
ASSERT(...);
InsertIntoCanonicalTypeArguments(...);

[Florian Schneider, 2012/12/13 11:59:45]

Done.

+    if (result.IsNew()) {
+      result ^= Object::Clone(result, Heap::kOld);
     }
-    result ^= table.At(++index);
+    ASSERT(result.IsOld());
+    InsertIntoCanonicalTypeArguments(isolate, table, result, index);
   }
-  // Not found. Add 'this' to table.
-  result ^= this->raw();
-  if (result.IsNew()) {
-    result ^= Object::Clone(result, Heap::kOld);
-  }
-  ASSERT(result.IsOld());
-  if (index == table.Length() - 1) {
-    table = Array::Grow(table, table.Length() + 4, Heap::kOld);
-    object_store->set_canonical_type_arguments(table);
-  }
-  table.SetAt(index, result);
-  result.SetCanonical();
+  ASSERT(result.Equals(self));
+  ASSERT(!result.IsNull());
+  ASSERT(result.IsTypeArguments());
   return result.raw();
 }
 
 
 const char* TypeArguments::ToCString() const {
   if (IsNull()) {
     return "NULL TypeArguments";
   }
   const char* format = "%s [%s]";
   const char* prev_cstr = "TypeArguments:";
@@ skipping 5831 matching lines @@
   }
   const Class& cls = Class::Handle(type_class());
   return cls.TypeTest(test_kind,
                       AbstractTypeArguments::Handle(arguments()),
                       Class::Handle(other.type_class()),
                       AbstractTypeArguments::Handle(other.arguments()),
                       malformed_error);
 }
 
 
+uword AbstractType::Hash() const {
+  // AbstractType is an abstract class.
+  UNREACHABLE();
+  return 0;
+}
+
+
 const char* AbstractType::ToCString() const {
   // AbstractType is an abstract class.
   UNREACHABLE();
   return "AbstractType";
 }
 
 
 RawType* Type::NullType() {
   return Isolate::Current()->object_store()->null_type();
 }
@@ skipping 254 matching lines @@
     new_canonical_types.SetAt(index, *this);
   } else {
     canonical_types.SetAt(index, *this);
   }
   ASSERT(IsOld());
   SetCanonical();
   return this->raw();
 }
 
 
+uword Type::Hash() const {
+  ASSERT(IsFinalized());
+  uword result = 1;
+  if (IsMalformed()) return result;
+  result += Class::Handle(type_class()).id();
+  result += AbstractTypeArguments::Handle(arguments()).Hash();
+  return FinalizeHash(result);
+}
+
+
 void Type::set_type_class(const Object& value) const {
   ASSERT(!value.IsNull() && (value.IsClass() || value.IsUnresolvedClass()));
   StorePointer(&raw_ptr()->type_class_, value.raw());
 }
 
 
 void Type::set_arguments(const AbstractTypeArguments& value) const {
   StorePointer(&raw_ptr()->arguments_, value.raw());
 }
 
@@ skipping 83 matching lines @@
   const TypeParameter& other_type_param = TypeParameter::Cast(other);
   if (IsFinalized() != other_type_param.IsFinalized()) {
     return false;
   }
   if (parameterized_class() != other_type_param.parameterized_class()) {
     return false;
   }
   if (index() != other_type_param.index()) {
     return false;
   }
-  const String& type_param_name = String::Handle(name());
-  const String& other_type_param_name = String::Handle(other_type_param.name());
-  return type_param_name.Equals(other_type_param_name);
+  return true;

[Ivan Posva, 2012/12/12 21:25:10]

Thanks for simplifying this.

 }
 
 
 void TypeParameter::set_parameterized_class(const Class& value) const {
   // Set value may be null.
   StorePointer(&raw_ptr()->parameterized_class_, value.raw());
 }
 
 
 void TypeParameter::set_index(intptr_t value) const {
@@ skipping 15 matching lines @@
 RawAbstractType* TypeParameter::InstantiateFrom(
     const AbstractTypeArguments& instantiator_type_arguments) const {
   ASSERT(IsFinalized());
   if (instantiator_type_arguments.IsNull()) {
     return Type::DynamicType();
   }
   return instantiator_type_arguments.TypeAt(index());
 }
 
 
+uword TypeParameter::Hash() const {
+  ASSERT(IsFinalized());
+  uword result = 0;
+  result += Class::Handle(parameterized_class()).id();
+  result <<= index();
+  return FinalizeHash(result);
+}
+
+
 RawTypeParameter* TypeParameter::New() {
   ASSERT(Isolate::Current()->object_store()->type_parameter_class() !=
          Class::null());
   RawObject* raw = Object::Allocate(TypeParameter::kClassId,
                                     TypeParameter::InstanceSize(),
                                     Heap::kOld);
   return reinterpret_cast<RawTypeParameter*>(raw);
 }
 
 
@@ skipping 3157 matching lines @@
   }
   return result.raw();
 }
 
 
 const char* WeakProperty::ToCString() const {
   return "_WeakProperty";
 }
 
 }  // namespace dart