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 15892)
+++ runtime/vm/object.cc	(working copy)
@@ -574,7 +574,10 @@
       GrowableObjectArray::type_arguments_offset());
 
   // canonical_type_arguments_ are NULL terminated.

[Ivan Posva, 2012/12/10 20:07:52]

Comment out of date.

[srdjan, 2012/12/10 21:19:37]

Fix comment: Smi terminated.

[Florian Schneider, 2012/12/11 12:23:04]

Done.

[Florian Schneider, 2012/12/11 12:23:04]

Done.

[Florian Schneider, 2012/12/11 12:23:04]

Done.

-  array = Array::New(4);
+  const intptr_t kInitialCanonicalTypeArgumentsSize = 4;

[srdjan, 2012/12/10 21:19:37]

Seems too small as initial size.

[Florian Schneider, 2012/12/11 12:23:04]

I don't want to wast space for programs that don't use type arguments. For
HelloWorld, the table never grows beyond 4.

+  array = Array::New(kInitialCanonicalTypeArgumentsSize + 1);
+  // Last element contains the count of used slots.
+  array.SetAt(kInitialCanonicalTypeArgumentsSize, Smi::Handle(Smi::New(0)));
   object_store->set_canonical_type_arguments(array);
 
   // Setup type class early in the process.
@@ -2709,7 +2712,7 @@
     return "NULL AbstractTypeArguments";
   }
   UNREACHABLE();
-  return "AbstractTypeArguments";
+  return NULL;

[Ivan Posva, 2012/12/10 20:07:52]

This seems very unconnected to the change at hand?

[Florian Schneider, 2012/12/11 12:23:04]

I think it still makes sense, but I can put it into a separate CL if necessary.

 }
 
 
@@ -2833,36 +2836,104 @@
 }
 
 
+static void GrowCanonicalTypeArguments(const Array& table, Isolate* isolate) {
+  // Last element of the array is the number of used elements.

[srdjan, 2012/12/10 21:19:37]

Pass isolate as first argument (as done in other places in this code).

[Florian Schneider, 2012/12/11 12:23:04]

Done.

+  intptr_t table_size = table.Length() - 1;
+  intptr_t new_table_size = table_size * 2;

[srdjan, 2012/12/10 21:19:37]

Can you check on dart2js, checked mode, how much the table grows. The growth
policy seems aggressive for large tables.

[Florian Schneider, 2012/12/11 12:23:04]

The max table size in dart2js is 1024 with ~50% occupation. I don't think that
this is too much.

+  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);
+  dart::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 = hash % new_table_size;

[srdjan, 2012/12/10 21:19:37]

new_table_size should be power of 2 for performance reasons. Maybe add an
assert?

[Florian Schneider, 2012/12/11 12:23:04]

Done.

+      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(const Array& table,
+                                             const TypeArguments& arguments,
+                                             intptr_t index,
+                                             Isolate* isolate) {

[srdjan, 2012/12/10 21:19:37]

'isolate' as first argument.

[Florian Schneider, 2012/12/11 12:23:04]

Done.

+  // 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.
+  dart::Smi& used = Smi::Handle(isolate);

[srdjan, 2012/12/10 21:19:37]

s/dart::Smi/Smi/ I do not think there is a conflicting Smi definition around.

[Florian Schneider, 2012/12/11 12:23:04]

Done.

+  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(table, isolate);
+  }
+}
+
+
+intptr_t FindIndexInCanonicalTypeArguments(const Array& table,
+                                           const TypeArguments& arguments,
+                                           intptr_t hash,
+                                           Isolate* isolate) {

[srdjan, 2012/12/10 21:19:37]

ditto

[Florian Schneider, 2012/12/11 12:23:04]

Done.

+  // Last element of the array is the number of used elements.
+  intptr_t table_size = table.Length() - 1;
+  intptr_t index = hash % table_size;
+
+  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(table,
+                                                     self,
+                                                     Hash(),
+                                                     isolate);
+  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(table, result, index, isolate);
   }
-  // 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();
 }
 
@@ -10000,6 +10071,12 @@
 }
 
 
+intptr_t TypeArguments::Hash() const {
+  const char* characters = ToCString();

[Ivan Posva, 2012/12/10 20:07:52]

This seems very fragile to me and as you are not caching this anywhere making
this rather expensive. Consider an alternative hash function which relies on the
participating class ids? Regis?

[regis, 2012/12/11 01:37:15]

Yes, for efficiency, the hash of a TypeArguments vector should depend on the
hash of its constituent element types. Each element type is either a Type or a
TypeParameter. A Type has a type class (class id is an integer) and a type
argument vector. A type parameter refers to a class (integer class id) and has
an index (integer); its name is not relevant here. So the hash can be calculated
from integers only. This should be much more efficient than computing the name.

Now, you need to pay attention to malformed types, but we do not canonicalize
them, if I remember correctly.

[Florian Schneider, 2012/12/11 12:23:04]

Done. Added ::Hash() for Type, TypeParameter and AbstractTypeArguments based on
class-ids.

Malformed type are not equal to any other type, so their hash code can be
anything. I doubt that they are important for performance though.

+  return HashImpl(characters, strlen(characters));
+}
+
+
 intptr_t String::Hash(const uint8_t* characters, intptr_t len) {
   return HashImpl(characters, len);
 }