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();
+  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,
     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;
 }
 
 
 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) {
+  // 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();
 }
 
 
 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 {

[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());
 }
 
 
 void Type::set_arguments(const AbstractTypeArguments& value) const {
   StorePointer(&raw_ptr()->arguments_, value.raw());
 }
 
@@ skipping 121 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 {

[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());
   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