Revert "- Use a hash table to canonicalize instances/arrays to avoid having to iterate over a linea…

runtime/vm/object.cc

Index: runtime/vm/object.cc
diff --git a/runtime/vm/object.cc b/runtime/vm/object.cc
index 3b16b3312b2132d24fca362b319be54eab98ed61..4ceb70f39407412a19e071aa0682b219e3ba3f94 100644
--- a/runtime/vm/object.cc
+++ b/runtime/vm/object.cc
@@ -705,7 +705,6 @@ void Object::InitOnce(Isolate* isolate) {
         empty_array_,
         reinterpret_cast<RawArray*>(address + kHeapObjectTag));
     empty_array_->StoreSmi(&empty_array_->raw_ptr()->length_, Smi::New(0));
-    empty_array_->SetCanonical();
   }
 
   Smi& smi = Smi::Handle();
@@ -719,7 +718,6 @@ void Object::InitOnce(Isolate* isolate) {
     zero_array_->StoreSmi(&zero_array_->raw_ptr()->length_, Smi::New(1));
     smi = Smi::New(0);
     zero_array_->SetAt(0, smi);
-    zero_array_->SetCanonical();
   }
 
   // Allocate and initialize the canonical empty context scope object.
@@ -736,7 +734,6 @@ void Object::InitOnce(Isolate* isolate) {
         &empty_context_scope_->raw_ptr()->num_variables_, 0);
     empty_context_scope_->StoreNonPointer(
         &empty_context_scope_->raw_ptr()->is_implicit_, true);
-    empty_context_scope_->SetCanonical();
   }
 
   // Allocate and initialize the canonical empty object pool object.
@@ -752,7 +749,6 @@ void Object::InitOnce(Isolate* isolate) {
         reinterpret_cast<RawObjectPool*>(address + kHeapObjectTag));
     empty_object_pool_->StoreNonPointer(
         &empty_object_pool_->raw_ptr()->length_, 0);
-    empty_object_pool_->SetCanonical();
   }
 
   // Allocate and initialize the empty_descriptors instance.
@@ -766,7 +762,6 @@ void Object::InitOnce(Isolate* isolate) {
         reinterpret_cast<RawPcDescriptors*>(address + kHeapObjectTag));
     empty_descriptors_->StoreNonPointer(&empty_descriptors_->raw_ptr()->length_,
                                         0);
-    empty_descriptors_->SetCanonical();
   }
 
   // Allocate and initialize the canonical empty variable descriptor object.
@@ -782,7 +777,6 @@ void Object::InitOnce(Isolate* isolate) {
         reinterpret_cast<RawLocalVarDescriptors*>(address + kHeapObjectTag));
     empty_var_descriptors_->StoreNonPointer(
         &empty_var_descriptors_->raw_ptr()->num_entries_, 0);
-    empty_var_descriptors_->SetCanonical();
   }
 
   // Allocate and initialize the canonical empty exception handler info object.
@@ -800,7 +794,6 @@ void Object::InitOnce(Isolate* isolate) {
         reinterpret_cast<RawExceptionHandlers*>(address + kHeapObjectTag));
     empty_exception_handlers_->StoreNonPointer(
         &empty_exception_handlers_->raw_ptr()->num_entries_, 0);
-    empty_exception_handlers_->SetCanonical();
   }
 
   // The VM isolate snapshot object table is initialized to an empty array
@@ -4428,88 +4421,44 @@ RawBigint* Class::LookupCanonicalBigint(Zone* zone,
 }
 
 
-class CanonicalInstanceKey {
- public:
-  explicit CanonicalInstanceKey(const Instance& key) : key_(key) {
-    ASSERT(!(key.IsString() || key.IsInteger() || key.IsAbstractType()));
-  }
-  bool Matches(const Instance& obj) const {
-    ASSERT(!(obj.IsString() || obj.IsInteger() || obj.IsAbstractType()));
-    if (key_.CanonicalizeEquals(obj)) {
-      ASSERT(obj.IsCanonical());
-      return true;
-    }
-    return false;
-  }
-  uword Hash() const {
-    return key_.ComputeCanonicalTableHash();
-  }
-  const Instance& key_;
-
- private:
-  DISALLOW_ALLOCATION();
-};
-
-
-// Traits for looking up Canonical Instances based on a hash of the fields.
-class CanonicalInstanceTraits {
- public:
-  static const char* Name() { return "CanonicalInstanceTraits"; }
-  static bool ReportStats() { return false; }
-
-  // Called when growing the table.
-  static bool IsMatch(const Object& a, const Object& b) {
-    ASSERT(!(a.IsString() || a.IsInteger() || a.IsAbstractType()));
-    ASSERT(!(b.IsString() || b.IsInteger() || b.IsAbstractType()));
-    return a.raw() == b.raw();
-  }
-  static bool IsMatch(const CanonicalInstanceKey& a, const Object& b) {
-    return a.Matches(Instance::Cast(b));
-  }
-  static uword Hash(const Object& key) {
-    ASSERT(!(key.IsString() || key.IsNumber() || key.IsAbstractType()));
-    ASSERT(key.IsInstance());
-    return Instance::Cast(key).ComputeCanonicalTableHash();
-  }
-  static uword Hash(const CanonicalInstanceKey& key) {
-    return key.Hash();
-  }
-  static RawObject* NewKey(const CanonicalInstanceKey& obj) {
-    return obj.key_.raw();
-  }
-};
-typedef UnorderedHashSet<CanonicalInstanceTraits> CanonicalInstancesSet;
-
-
 RawInstance* Class::LookupCanonicalInstance(Zone* zone,
-                                            const Instance& value) const {
+                                            const Instance& value,
+                                            intptr_t* index) const {
   ASSERT(this->raw() == value.clazz());
+  const Array& constants = Array::Handle(zone, this->constants());
+  const intptr_t constants_len = constants.Length();
+  // Linear search to see whether this value is already present in the
+  // list of canonicalized constants.
   Instance& canonical_value = Instance::Handle(zone);
-  if (this->constants() != Object::empty_array().raw()) {
-    CanonicalInstancesSet constants(zone, this->constants());
-    canonical_value ^= constants.GetOrNull(CanonicalInstanceKey(value));
-    this->set_constants(constants.Release());
+  while (*index < constants_len) {
+    canonical_value ^= constants.At(*index);
+    if (canonical_value.IsNull()) {
+      break;
+    }
+    if (value.CanonicalizeEquals(canonical_value)) {
+      ASSERT(canonical_value.IsCanonical());
+      return canonical_value.raw();
+    }
+    *index = *index + 1;
   }
-  return canonical_value.raw();
+  return Instance::null();
 }
 
 
-RawInstance* Class::InsertCanonicalConstant(Zone* zone,
-                                            const Instance& constant) const {
-  ASSERT(this->raw() == constant.clazz());
-  Instance& canonical_value = Instance::Handle(zone);
-  if (this->constants() == Object::empty_array().raw()) {
-    CanonicalInstancesSet constants(
-        HashTables::New<CanonicalInstancesSet>(128, Heap::kOld));
-    canonical_value ^= constants.InsertNewOrGet(CanonicalInstanceKey(constant));
-    this->set_constants(constants.Release());
+void Class::InsertCanonicalConstant(intptr_t index,
+                                    const Instance& constant) const {
+  // The constant needs to be added to the list. Grow the list if it is full.
+  Array& canonical_list = Array::Handle(constants());
+  const intptr_t list_len = canonical_list.Length();
+  if (index >= list_len) {
+    const intptr_t new_length = (list_len == 0) ? 4 : list_len + 4;
+    const Array& new_canonical_list =
+        Array::Handle(Array::Grow(canonical_list, new_length, Heap::kOld));
+    set_constants(new_canonical_list);
+    new_canonical_list.SetAt(index, constant);
   } else {
-    CanonicalInstancesSet constants(Thread::Current()->zone(),
-                                    this->constants());
-    canonical_value ^= constants.InsertNewOrGet(CanonicalInstanceKey(constant));
-    this->set_constants(constants.Release());
+    canonical_list.SetAt(index, constant);
   }
-  return canonical_value.raw();
 }
 
 
@@ -14805,13 +14754,8 @@ bool Instance::CanonicalizeEquals(const Instance& other) const {
   {
     NoSafepointScope no_safepoint;
     // Raw bits compare.
-    const intptr_t instance_size = SizeFromClass();
+    const intptr_t instance_size = Class::Handle(this->clazz()).instance_size();
     ASSERT(instance_size != 0);
-    const intptr_t other_instance_size = other.SizeFromClass();
-    ASSERT(other_instance_size != 0);
-    if (instance_size != other_instance_size) {
-      return false;
-    }
     uword this_addr = reinterpret_cast<uword>(this->raw_ptr());
     uword other_addr = reinterpret_cast<uword>(other.raw_ptr());
     for (intptr_t offset = Instance::NextFieldOffset();
@@ -14827,24 +14771,6 @@ bool Instance::CanonicalizeEquals(const Instance& other) const {
 }
 
 
-uword Instance::ComputeCanonicalTableHash() const {
-  ASSERT(!IsNull());
-  NoSafepointScope no_safepoint;
-  const intptr_t instance_size = SizeFromClass();
-  ASSERT(instance_size != 0);
-  uword hash = instance_size;
-  uword this_addr = reinterpret_cast<uword>(this->raw_ptr());
-  for (intptr_t offset = Instance::NextFieldOffset();
-       offset < instance_size;
-       offset += kWordSize) {
-    uword value = reinterpret_cast<uword>(
-        *reinterpret_cast<RawObject**>(this_addr + offset));
-    hash = CombineHashes(hash, value);
-  }
-  return FinalizeHash(hash);
-}
-
-
 #if defined(DEBUG)
 class CheckForPointers : public ObjectPointerVisitor {
  public:
@@ -14867,21 +14793,21 @@ class CheckForPointers : public ObjectPointerVisitor {
 #endif  // DEBUG
 
 
-bool Instance::CheckAndCanonicalizeFields(Thread* thread,
+bool Instance::CheckAndCanonicalizeFields(Zone* zone,
                                           const char** error_str) const {
-  if (GetClassId() >= kNumPredefinedCids) {
+  const Class& cls = Class::Handle(zone, this->clazz());
+  if (cls.id() >= kNumPredefinedCids) {
     // Iterate over all fields, canonicalize numbers and strings, expect all
     // other instances to be canonical otherwise report error (return false).
-    Zone* zone = thread->zone();
     Object& obj = Object::Handle(zone);
-    intptr_t end_field_offset = SizeFromClass() - kWordSize;
+    intptr_t end_field_offset = cls.instance_size() - kWordSize;
     for (intptr_t field_offset = 0;
          field_offset <= end_field_offset;
          field_offset += kWordSize) {
       obj = *this->FieldAddrAtOffset(field_offset);
       if (obj.IsInstance() && !obj.IsSmi() && !obj.IsCanonical()) {
         if (obj.IsNumber() || obj.IsString()) {
-          obj = Instance::Cast(obj).CheckAndCanonicalize(thread, NULL);
+          obj = Instance::Cast(obj).CheckAndCanonicalize(NULL);
           ASSERT(!obj.IsNull());
           this->SetFieldAtOffset(field_offset, obj);
         } else {
@@ -14904,35 +14830,46 @@ bool Instance::CheckAndCanonicalizeFields(Thread* thread,
 }
 
 
-RawInstance* Instance::CheckAndCanonicalize(Thread* thread,
-                                            const char** error_str) const {
+RawInstance* Instance::CheckAndCanonicalize(const char** error_str) const {
   ASSERT(!IsNull());
   if (this->IsCanonical()) {
     return this->raw();
   }
-  if (!CheckAndCanonicalizeFields(thread, error_str)) {
+  Thread* thread = Thread::Current();
+  Zone* zone = thread->zone();
+  if (!CheckAndCanonicalizeFields(zone, error_str)) {
     return Instance::null();
   }
-  Zone* zone = thread->zone();
   Isolate* isolate = thread->isolate();
   Instance& result = Instance::Handle(zone);
   const Class& cls = Class::Handle(zone, this->clazz());
+  intptr_t index = 0;
+  result ^= cls.LookupCanonicalInstance(zone, *this, &index);
+  if (!result.IsNull()) {
+    return result.raw();
+  }
   {
     SafepointMutexLocker ml(isolate->constant_canonicalization_mutex());
-    if (IsNew()) {
-      result ^= cls.LookupCanonicalInstance(zone, *this);
+    // Retry lookup.
+    {
+      result ^= cls.LookupCanonicalInstance(zone, *this, &index);
       if (!result.IsNull()) {
         return result.raw();
       }
-      ASSERT((isolate == Dart::vm_isolate()) || !InVMHeap());
+    }
+
+    // The value needs to be added to the list. Grow the list if
+    // it is full.
+    result ^= this->raw();
+    ASSERT((isolate == Dart::vm_isolate()) || !result.InVMHeap());
+    if (result.IsNew()) {
       // Create a canonical object in old space.
-      result ^= Object::Clone(*this, Heap::kOld);
-    } else {
-      result ^= this->raw();
+      result ^= Object::Clone(result, Heap::kOld);
     }
     ASSERT(result.IsOld());
     result.SetCanonical();
-    return cls.InsertCanonicalConstant(zone, result);
+    cls.InsertCanonicalConstant(index, result);
+    return result.raw();
   }
 }
 
@@ -17554,8 +17491,7 @@ RawMixinAppType* MixinAppType::New(const AbstractType& super_type,
 }
 
 
-RawInstance* Number::CheckAndCanonicalize(Thread* thread,
-                                          const char** error_str) const {
+RawInstance* Number::CheckAndCanonicalize(const char** error_str) const {
   intptr_t cid = GetClassId();
   switch (cid) {
     case kSmiCid:
@@ -17565,9 +17501,10 @@ RawInstance* Number::CheckAndCanonicalize(Thread* thread,
     case kDoubleCid:
       return Double::NewCanonical(Double::Cast(*this).value());
     case kBigintCid: {
+      Thread* thread = Thread::Current();
       Zone* zone = thread->zone();
       Isolate* isolate = thread->isolate();
-      if (!CheckAndCanonicalizeFields(thread, error_str)) {
+      if (!CheckAndCanonicalizeFields(zone, error_str)) {
         return Instance::null();
       }
       Bigint& result = Bigint::Handle(zone);
@@ -18320,16 +18257,15 @@ bool Bigint::Equals(const Instance& other) const {
 }
 
 
-bool Bigint::CheckAndCanonicalizeFields(Thread* thread,
+bool Bigint::CheckAndCanonicalizeFields(Zone* zone,
                                         const char** error_str) const {
-  Zone* zone = thread->zone();
   // Bool field neg should always be canonical.
   ASSERT(Bool::Handle(zone, neg()).IsCanonical());
   // Smi field used is canonical by definition.
   if (Used() > 0) {
     // Canonicalize TypedData field digits.
     TypedData& digits_ = TypedData::Handle(zone, digits());
-    digits_ ^= digits_.CheckAndCanonicalize(thread, NULL);
+    digits_ ^= digits_.CheckAndCanonicalize(NULL);
     ASSERT(!digits_.IsNull());
     set_digits(digits_);
   } else {
@@ -19301,8 +19237,7 @@ bool String::StartsWith(const String& other) const {
 }
 
 
-RawInstance* String::CheckAndCanonicalize(Thread* thread,
-                                          const char** error_str) const {
+RawInstance* String::CheckAndCanonicalize(const char** error_str) const {
   if (IsCanonical()) {
     return this->raw();
   }
@@ -20759,9 +20694,6 @@ bool Array::CanonicalizeEquals(const Instance& other) const {
   }
 
   // Now check if both arrays have the same type arguments.
-  if (GetTypeArguments() == other.GetTypeArguments()) {
-    return true;
-  }
   const TypeArguments& type_args = TypeArguments::Handle(GetTypeArguments());
   const TypeArguments& other_type_args = TypeArguments::Handle(
       other.GetTypeArguments());
@@ -20772,20 +20704,6 @@ bool Array::CanonicalizeEquals(const Instance& other) const {
 }
 
 
-uword Array::ComputeCanonicalTableHash() const {
-  ASSERT(!IsNull());
-  intptr_t len = Length();
-  uword hash = len;
-  uword value = reinterpret_cast<uword>(GetTypeArguments());
-  hash = CombineHashes(hash, value);
-  for (intptr_t i = 0; i < len; i++) {
-    value = reinterpret_cast<uword>(At(i));
-    hash = CombineHashes(hash, value);
-  }
-  return FinalizeHash(hash);
-}
-
-
 RawArray* Array::New(intptr_t len, Heap::Space space) {
   ASSERT(Isolate::Current()->object_store()->array_class() != Class::null());
   return New(kClassId, len, space);
@@ -20927,28 +20845,24 @@ RawArray* Array::MakeArray(const GrowableObjectArray& growable_array) {
 }
 
 
-bool Array::CheckAndCanonicalizeFields(Thread* thread,
+bool Array::CheckAndCanonicalizeFields(Zone* zone,
                                        const char** error_str) const {
-  intptr_t len = Length();
-  if (len > 0) {
-    Zone* zone = thread->zone();
-    Object& obj = Object::Handle(zone);
-    // Iterate over all elements, canonicalize numbers and strings, expect all
-    // other instances to be canonical otherwise report error (return false).
-    for (intptr_t i = 0; i < len; i++) {
-      obj = At(i);
-      if (obj.IsInstance() && !obj.IsSmi() && !obj.IsCanonical()) {
-        if (obj.IsNumber() || obj.IsString()) {
-          obj = Instance::Cast(obj).CheckAndCanonicalize(thread, NULL);
-          ASSERT(!obj.IsNull());
-          this->SetAt(i, obj);
-        } else {
-          ASSERT(error_str != NULL);
-          char* chars = OS::SCreate(
-              zone, "element at index %" Pd ": %s\n", i, obj.ToCString());
-          *error_str = chars;
-          return false;
-        }
+  Object& obj = Object::Handle(zone);
+  // Iterate over all elements, canonicalize numbers and strings, expect all
+  // other instances to be canonical otherwise report error (return false).
+  for (intptr_t i = 0; i < Length(); i++) {
+    obj = At(i);
+    if (obj.IsInstance() && !obj.IsSmi() && !obj.IsCanonical()) {
+      if (obj.IsNumber() || obj.IsString()) {
+        obj = Instance::Cast(obj).CheckAndCanonicalize(NULL);
+        ASSERT(!obj.IsNull());
+        this->SetAt(i, obj);
+      } else {
+        ASSERT(error_str != NULL);
+        char* chars = OS::SCreate(Thread::Current()->zone(),
+            "element at index %" Pd ": %s\n", i, obj.ToCString());
+        *error_str = chars;
+        return false;
       }
     }
   }
@@ -21432,17 +21346,6 @@ bool TypedData::CanonicalizeEquals(const Instance& other) const {
 }
 
 
-uword TypedData::ComputeCanonicalTableHash() const {
-  const intptr_t len = this->LengthInBytes();
-  ASSERT(len != 0);
-  uword hash = len;
-  for (intptr_t i = 0; i < len; i++) {
-    hash = CombineHashes(len, GetUint8(i));
-  }
-  return FinalizeHash(hash);
-}
-
-
 RawTypedData* TypedData::New(intptr_t class_id,
                              intptr_t len,
                              Heap::Space space) {