- Use a hash table to canonicalize instances/arrays to avoid having to iterate over a linear list a…

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/cpu.h"
@@ skipping 686 matching lines @@
   Class::NewTypedDataClass(kTypedDataInt8ArrayCid);
 
   // Allocate and initialize the empty_array instance.
   {
     uword address = heap->Allocate(Array::InstanceSize(0), Heap::kOld);
     InitializeObject(address, kImmutableArrayCid, Array::InstanceSize(0), true);
     Array::initializeHandle(
         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();
   // Allocate and initialize the zero_array instance.
   {
     uword address = heap->Allocate(Array::InstanceSize(1), Heap::kOld);
     InitializeObject(address, kImmutableArrayCid, Array::InstanceSize(1), true);
     Array::initializeHandle(
         zero_array_,
         reinterpret_cast<RawArray*>(address + kHeapObjectTag));
     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.
   {
     uword address = heap->Allocate(ContextScope::InstanceSize(0), Heap::kOld);
     InitializeObject(address,
                      kContextScopeCid,
                      ContextScope::InstanceSize(0),
                      true);
     ContextScope::initializeHandle(
         empty_context_scope_,
         reinterpret_cast<RawContextScope*>(address + kHeapObjectTag));
     empty_context_scope_->StoreNonPointer(
         &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.
   {
     uword address =
         heap->Allocate(ObjectPool::InstanceSize(0), Heap::kOld);
     InitializeObject(address,
                      kObjectPoolCid,
                      ObjectPool::InstanceSize(0),
                      true);
     ObjectPool::initializeHandle(
         empty_object_pool_,
         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.
   {
     uword address = heap->Allocate(PcDescriptors::InstanceSize(0), Heap::kOld);
     InitializeObject(address, kPcDescriptorsCid,
                      PcDescriptors::InstanceSize(0),
                      true);
     PcDescriptors::initializeHandle(
         empty_descriptors_,
         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.
   {
     uword address =
         heap->Allocate(LocalVarDescriptors::InstanceSize(0), Heap::kOld);
     InitializeObject(address,
                      kLocalVarDescriptorsCid,
                      LocalVarDescriptors::InstanceSize(0),
                      true);
     LocalVarDescriptors::initializeHandle(
         empty_var_descriptors_,
         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.
   // The vast majority of all functions do not contain an exception handler
   // and can share this canonical descriptor.
   {
     uword address =
         heap->Allocate(ExceptionHandlers::InstanceSize(0), Heap::kOld);
     InitializeObject(address,
                      kExceptionHandlersCid,
                      ExceptionHandlers::InstanceSize(0),
                      true);
     ExceptionHandlers::initializeHandle(
         empty_exception_handlers_,
         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
   // as we do not have any VM isolate snapshot at this time.
   *vm_isolate_snapshot_object_table_ = Object::empty_array().raw();
 
   cls = Class::New<Instance>(kDynamicCid);
   cls.set_is_abstract();
   cls.set_num_type_arguments(0);
   cls.set_num_own_type_arguments(0);
@@ skipping 3599 matching lines @@
     if (canonical_value.Equals(value)) {
       ASSERT(canonical_value.IsCanonical());
       return canonical_value.raw();
     }
     *index = *index + 1;
   }
   return Bigint::null();
 }
 
 
+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();
+  DISALLOW_COPY_AND_ASSIGN(CanonicalInstanceKey);
+};
+
+
+// Traits for looking up Canonical Instances based on a hash of the fields.
+class CanonicalInstanceTraits {
+ public:
+  // 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();
+  }
+};

[regis, 2016/04/12 21:12:32]

No blank line(s)?

[siva, 2016/04/13 16:52:41]

This seems to be the pattern that everybody has used in all the other places
that hash table typedefs have been defined.

+typedef UnorderedHashSet<CanonicalInstanceTraits> CanonicalInstancesSet;
+
+
 RawInstance* Class::LookupCanonicalInstance(Zone* zone,
-                                            const Instance& value,
-                                            intptr_t* index) const {
+                                            const Instance& value) 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);
-  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;
+  if (this->constants() != Object::empty_array().raw()) {
+    CanonicalInstancesSet constants(zone, this->constants());
+    canonical_value ^= constants.GetOrNull(CanonicalInstanceKey(value));
+    this->set_constants(constants.Release());

[regis, 2016/04/12 21:12:32]

Since you are only doing a lookup in the constants array, it should not change.
So you should be able to replace the last line with an assert:
ASSERT(this->constants() == constants.Release().raw()); 

[siva, 2016/04/13 16:52:41]

The problem is constants.Release() needs to be called to cleanup as the
destructor does nothing, we can't do the Release only in ASSERT.

   }
-  return Instance::null();
+  return canonical_value.raw();
 }
 
 
-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);
+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());
   } else {
-    canonical_list.SetAt(index, constant);
+    CanonicalInstancesSet constants(Thread::Current()->zone(),
+                                    this->constants());
+    canonical_value ^= constants.InsertNewOrGet(CanonicalInstanceKey(constant));
+    this->set_constants(constants.Release());
   }
+  return canonical_value.raw();
 }
 
 
 void Class::InsertCanonicalNumber(Zone* zone,
                                   intptr_t index,
                                   const Number& constant) const {
   // The constant needs to be added to the list. Grow the list if it is full.
   Array& canonical_list = Array::Handle(zone, constants());
   const intptr_t list_len = canonical_list.Length();
   if (index >= list_len) {
@@ skipping 10218 matching lines @@
     return true;  // "===".
   }
 
   if (other.IsNull() || (this->clazz() != other.clazz())) {
     return false;
   }
 
   {
     NoSafepointScope no_safepoint;
     // Raw bits compare.
-    const intptr_t instance_size = Class::Handle(this->clazz()).instance_size();
+    const intptr_t instance_size = SizeFromClass();
     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();
          offset < instance_size;
          offset += kWordSize) {
       if ((*reinterpret_cast<RawObject**>(this_addr + offset)) !=
           (*reinterpret_cast<RawObject**>(other_addr + offset))) {
         return false;
       }
     }
   }
   return true;
 }
 
 
+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 >> 3));

[regis, 2016/04/12 21:12:32]

If the field is a Smi, you ignore 2 bits of its value. Is that OK?

[siva, 2016/04/13 16:52:41]

Removed teh shift as discussed offline.

+  }
+  return FinalizeHash(hash);
+}
+
+
 #if defined(DEBUG)
 class CheckForPointers : public ObjectPointerVisitor {
  public:
   explicit CheckForPointers(Isolate* isolate)
       : ObjectPointerVisitor(isolate), has_pointers_(false) {}
 
   bool has_pointers() const { return has_pointers_; }
 
   void VisitPointers(RawObject** first, RawObject** last) {
     if (first != last) {
       has_pointers_ = true;
     }
   }
 
  private:
   bool has_pointers_;
 
   DISALLOW_COPY_AND_ASSIGN(CheckForPointers);
 };
 #endif  // DEBUG
 
 
-bool Instance::CheckAndCanonicalizeFields(Zone* zone,
+bool Instance::CheckAndCanonicalizeFields(Thread* thread,
                                           const char** error_str) const {
-  const Class& cls = Class::Handle(zone, this->clazz());
-  if (cls.id() >= kNumPredefinedCids) {
+  if (GetClassId() >= 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 = cls.instance_size() - kWordSize;
+    intptr_t end_field_offset = SizeFromClass() - 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(NULL);
+          obj = Instance::Cast(obj).CheckAndCanonicalize(thread, NULL);
           ASSERT(!obj.IsNull());
           this->SetFieldAtOffset(field_offset, obj);
         } else {
           ASSERT(error_str != NULL);
           char* chars = OS::SCreate(zone, "field: %s\n", obj.ToCString());
           *error_str = chars;
           return false;
         }
       }
     }
   } else {
 #if defined(DEBUG)
     // Make sure that we are not missing any fields.
     CheckForPointers has_pointers(Isolate::Current());
     this->raw()->VisitPointers(&has_pointers);
     ASSERT(!has_pointers.has_pointers());
 #endif  // DEBUG
   }
   return true;
 }
 
 
-RawInstance* Instance::CheckAndCanonicalize(const char** error_str) const {
+RawInstance* Instance::CheckAndCanonicalize(Thread* thread,
+                                            const char** error_str) const {
   ASSERT(!IsNull());
   if (this->IsCanonical()) {
     return this->raw();
   }
-  Thread* thread = Thread::Current();
-  Zone* zone = thread->zone();
-  if (!CheckAndCanonicalizeFields(zone, error_str)) {
+  if (!CheckAndCanonicalizeFields(thread, 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());
-    // Retry lookup.
-    {
-      result ^= cls.LookupCanonicalInstance(zone, *this, &index);
+    if (IsNew()) {
+      result ^= cls.LookupCanonicalInstance(zone, *this);
       if (!result.IsNull()) {
         return result.raw();
       }
-    }
-
-    // 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()) {
+      ASSERT((isolate == Dart::vm_isolate()) || !InVMHeap());
       // Create a canonical object in old space.
-      result ^= Object::Clone(result, Heap::kOld);
+      result ^= Object::Clone(*this, Heap::kOld);
+    } else {
+      result ^= this->raw();
     }
     ASSERT(result.IsOld());
     result.SetCanonical();
-    cls.InsertCanonicalConstant(index, result);
-    return result.raw();
+    return cls.InsertCanonicalConstant(zone, result);
   }
 }
 
 
 RawAbstractType* Instance::GetType() const {
   if (IsNull()) {
     return Type::NullType();
   }
   const Class& cls = Class::Handle(clazz());
   if (cls.IsClosureClass()) {
@@ skipping 2593 matching lines @@
 
 RawMixinAppType* MixinAppType::New(const AbstractType& super_type,
                                    const Array& mixin_types) {
   const MixinAppType& result = MixinAppType::Handle(MixinAppType::New());
   result.set_super_type(super_type);
   result.set_mixin_types(mixin_types);
   return result.raw();
 }
 
 
-RawInstance* Number::CheckAndCanonicalize(const char** error_str) const {
+RawInstance* Number::CheckAndCanonicalize(Thread* thread,
+                                          const char** error_str) const {
   intptr_t cid = GetClassId();
   switch (cid) {
     case kSmiCid:
       return reinterpret_cast<RawSmi*>(raw_value());
     case kMintCid:
       return Mint::NewCanonical(Mint::Cast(*this).value());
     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(zone, error_str)) {
+      if (!CheckAndCanonicalizeFields(thread, error_str)) {
         return Instance::null();
       }
       Bigint& result = Bigint::Handle(zone);
       const Class& cls = Class::Handle(zone, this->clazz());
       intptr_t index = 0;
       result ^= cls.LookupCanonicalBigint(zone, Bigint::Cast(*this), &index);
       if (!result.IsNull()) {
         return result.raw();
       }
       {
@@ skipping 732 matching lines @@
 
   for (intptr_t i = 0; i < used; i++) {
     if (this->DigitAt(i) != other_bgi.DigitAt(i)) {
       return false;
     }
   }
   return true;
 }
 
 
-bool Bigint::CheckAndCanonicalizeFields(Zone* zone,
+bool Bigint::CheckAndCanonicalizeFields(Thread* thread,
                                         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(NULL);
+    digits_ ^= digits_.CheckAndCanonicalize(thread, NULL);
     ASSERT(!digits_.IsNull());
     set_digits(digits_);
   } else {
     ASSERT(digits() == TypedData::EmptyUint32Array(Thread::Current()));
   }
   return true;
 }
 
 
 RawBigint* Bigint::New(Heap::Space space) {
@@ skipping 951 matching lines @@
   intptr_t slen = other.Length();
   for (int i = 0; i < slen; i++) {
     if (this->CharAt(i) != other.CharAt(i)) {
       return false;
     }
   }
   return true;
 }
 
 
-RawInstance* String::CheckAndCanonicalize(const char** error_str) const {
+RawInstance* String::CheckAndCanonicalize(Thread* thread,
+                                          const char** error_str) const {
   if (IsCanonical()) {
     return this->raw();
   }
   return Symbols::New(*this);
 }
 
 
 RawString* String::New(const char* cstr, Heap::Space space) {
   ASSERT(cstr != NULL);
   intptr_t array_len = strlen(cstr);
@@ skipping 1436 matching lines @@
     return false;
   }
 
   for (intptr_t i = 0; i < len; i++) {
     if (this->At(i) != other_arr.At(i)) {
       return false;
     }
   }
 
   // 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());
   if (!type_args.Equals(other_type_args)) {
     return false;
   }
   return true;
 }
 
 
+uword Array::ComputeCanonicalTableHash() const {
+  ASSERT(!IsNull());
+  intptr_t len = Length();
+  uword hash = len;
+  uword value = reinterpret_cast<uword>(GetTypeArguments());
+  hash = CombineHashes(hash, (value >> 3));
+  for (intptr_t i = 0; i < len; i++) {
+    value = reinterpret_cast<uword>(At(i));
+    hash = CombineHashes(hash, (value >> 3));

[regis, 2016/04/12 21:12:32]

Same comment about ignoring 2 bits if the array element is a Smi.

[siva, 2016/04/13 16:52:41]

Done.

+  }
+  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);
 }
 
 
 RawArray* Array::New(intptr_t class_id, intptr_t len, Heap::Space space) {
   if ((len < 0) || (len > Array::kMaxElements)) {
     // This should be caught before we reach here.
     FATAL1("Fatal error in Array::New: invalid len %" Pd "\n", len);
@@ skipping 121 matching lines @@
   array.SetLength(used_len);
 
   // Null the GrowableObjectArray, we are removing its backing array.
   growable_array.SetLength(0);
   growable_array.SetData(Object::empty_array());
 
   return array.raw();
 }
 
 
-bool Array::CheckAndCanonicalizeFields(Zone* zone,
+bool Array::CheckAndCanonicalizeFields(Thread* thread,
                                        const char** error_str) const {
-  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;
+  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;
+        }
       }
     }
   }
   return true;
 }
 
 
 RawImmutableArray* ImmutableArray::New(intptr_t len,
                                        Heap::Space space) {
   ASSERT(Isolate::Current()->object_store()->immutable_array_class() !=
@@ skipping 460 matching lines @@
   const intptr_t len = this->LengthInBytes();
   if (len != other_typed_data.LengthInBytes()) {
     return false;
   }
   NoSafepointScope no_safepoint;
   return (len == 0) ||
       (memcmp(DataAddr(0), other_typed_data.DataAddr(0), len) == 0);
 }
 
 
+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) {
   if (len < 0 || len > TypedData::MaxElements(class_id)) {
     FATAL1("Fatal error in TypedData::New: invalid len %" Pd "\n", len);
   }
   TypedData& result = TypedData::Handle();
   {
     const intptr_t lengthInBytes = len * ElementSizeInBytes(class_id);
     RawObject* raw = Object::Allocate(class_id,
@@ skipping 674 matching lines @@
   return UserTag::null();
 }
 
 
 const char* UserTag::ToCString() const {
   const String& tag_label = String::Handle(label());
   return tag_label.ToCString();
 }
 
 }  // namespace dart