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

runtime/vm/object.cc

Index: runtime/vm/object.cc
===================================================================
--- runtime/vm/object.cc	(revision 15913)
+++ runtime/vm/object.cc	(working copy)
@@ -573,8 +573,11 @@
   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.
@@ -2500,6 +2503,29 @@
 }
 
 
+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,
@@ -2709,7 +2735,7 @@
     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.

 }
 
 
@@ -2833,36 +2859,108 @@
 }
 
 
+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();
 }
 
@@ -8714,6 +8812,13 @@
 }
 
 
+uword AbstractType::Hash() const {
+  // AbstractType is an abstract class.
+  UNREACHABLE();
+  return 0;
+}
+
+
 const char* AbstractType::ToCString() const {
   // AbstractType is an abstract class.
   UNREACHABLE();
@@ -8988,6 +9093,16 @@
 }
 
 
+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());
@@ -9091,9 +9206,7 @@
   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.

 }
 
 
@@ -9129,6 +9242,15 @@
 }
 
 
+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());