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,27 @@
 }
 
 
+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();
+  for (intptr_t i = 0; i < num_types; i++) {
+    result += AbstractType::Handle(TypeAt(i)).Hash();

[regis, 2012/12/11 19:04:04]

You should move the Handle out of the loop, not to create a Handle per
iteration.

[Florian Schneider, 2012/12/12 14:58:40]

Thanks. Done.

+    result += result << 10;
+    result ^= result >> 6;
+  }
+  return FinalizeHash(result);
+}
+
+
 RawString* AbstractTypeArguments::SubvectorName(
     intptr_t from_index,
     intptr_t len,
@@ -2709,7 +2733,7 @@
     return "NULL AbstractTypeArguments";
   }
   UNREACHABLE();
-  return "AbstractTypeArguments";
+  return NULL;
 }
 
 
@@ -2833,36 +2857,106 @@
 }
 
 
+static void GrowCanonicalTypeArguments(Isolate* isolate, const Array& table) {
+  // 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;
+  ASSERT(Utils::IsPowerOfTwo(new_table_size));
+  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();
+      intptr_t index = static_cast<uword>(hash) % new_table_size;

[Ivan Posva, 2012/12/11 14:54:52]

Since you know you have a power of two. Please do a & mask. You can precalculate
the mask before entering the loop. This should avoid two things: Having to
static_cast to uword and a lengthy division.

+      new_element = new_table.At(index);
+      while (!new_element.IsNull()) {
+        index = (index + 1) % new_table_size;  // 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,
+                                             const Array& table,
+                                             const TypeArguments& arguments,
+                                             intptr_t index) {
+  // Last element of the array is the number of used elements.
+  intptr_t table_size = table.Length() - 1;
+  arguments.SetCanonical();  // Mark object as being canonical.
+  table.SetAt(index, arguments);  // Remember the new element.
+  Smi& used = Smi::Handle(isolate);
+  used ^= table.At(table_size);
+  intptr_t used_elements = used.Value() + 1;  // One more element added.
+  used = Smi::New(used_elements);
+  table.SetAt(table_size, used);  // Update used count.
+
+  // Rehash if table is 75% full.
+  if (used_elements > ((table_size / 4) * 3)) {
+    GrowCanonicalTypeArguments(isolate, table);
+  }
+}
+
+
+static intptr_t FindIndexInCanonicalTypeArguments(
+    Isolate* isolate,
+    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;
+  intptr_t index = static_cast<uword>(hash) % table_size;

[Ivan Posva, 2012/12/11 14:54:52]

ditto: power of two assertion, & mask, uword cast.

+
+  TypeArguments& current = TypeArguments::Handle(isolate);
+  current ^= table.At(index);
+  while (!current.IsNull() && !current.Equals(arguments)) {
+    index = (index + 1) % table_size;  // 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());
+  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();
+    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 +8808,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 +9089,15 @@
 }
 
 
+uword Type::Hash() const {

[regis, 2012/12/11 19:04:04]

ASSERT(IsFinalized());

[Florian Schneider, 2012/12/12 14:58:40]

Done.

+  uword result = 1;
+  result <<= IsMalformed() ? 10 : 0;
+  result += Class::Handle(type_class()).id();

[regis, 2012/12/11 19:04:04]

A malformed type may not have a type_class. You will assert fault if you try to
get to it. You should return immediately if it is malformed, since it will not
get canonicalized anyway.

[Florian Schneider, 2012/12/12 14:58:40]

Done.

+  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());
@@ -9129,6 +9239,16 @@
 }
 
 
+uword TypeParameter::Hash() const {

[regis, 2012/12/11 19:04:04]

ASSERT(IsFinalized());

[Florian Schneider, 2012/12/12 14:58:40]

Done.

+  uword result = 0;
+  result += Class::Handle(parameterized_class()).id();
+  result <<= index();
+  result ^= String::Handle(name()).Hash();

[regis, 2012/12/11 19:04:04]

You do not need the name. It is only used for error reporting and debugging
purpose after parsing. It is redundant with the index.

[Florian Schneider, 2012/12/12 14:58:40]

Ok, then I'd like to remove from TypeParameter::Equals as well. For Hash() I
used the attributes that are tested in Equals. If it's only used for
debugging/printing and does not matter for equality, then it can be safely
removed in both places.

[regis, 2012/12/12 18:36:48]

Yes, it is safe, because Equals returns false if one TypeParameter is finalized
while the other is not. It is therefore OK to compare the indices (adjusted or
not) and ignore the names in Equals.

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

Done.

+  result += IsFinalized() ? 1 : 0;
+  return FinalizeHash(result);
+}
+
+
 RawTypeParameter* TypeParameter::New() {
   ASSERT(Isolate::Current()->object_store()->type_parameter_class() !=
          Class::null());