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.

[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.
   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 2114 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/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.

 }
 
 
 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(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();
 }
 
 
 const char* TypeArguments::ToCString() const {
   if (IsNull()) {
     return "NULL TypeArguments";
   }
   const char* format = "%s [%s]";
   const char* prev_cstr = "TypeArguments:";
@@ skipping 7117 matching lines @@
 static intptr_t HashImpl(const T* characters, intptr_t len) {
   ASSERT(len >= 0);
   StringHasher hasher;
   for (intptr_t i = 0; i < len; i++) {
     hasher.Add(characters[i]);
   }
   return hasher.Finalize(String::kHashBits);
 }
 
 
+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);
 }
 
 
 intptr_t String::Hash(const uint16_t* characters, intptr_t len) {
   StringHasher hasher;
   intptr_t i = 0;
   while (i < len) {
     hasher.Add(Utf16::Next(characters, &i, len));
@@ skipping 2286 matching lines @@
   }
   return result.raw();
 }
 
 
 const char* WeakProperty::ToCString() const {
   return "_WeakProperty";
 }
 
 }  // namespace dart