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

runtime/vm/object.h

 // 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.
 
 #ifndef VM_OBJECT_H_
 #define VM_OBJECT_H_
 
 #include "include/dart_api.h"
 #include "platform/assert.h"
 #include "platform/utils.h"
@@ skipping 1195 matching lines @@
   // - constants_list_ position of found element, or
   // - constants_list_ position where new canonical can be inserted.
   RawDouble* LookupCanonicalDouble(Zone* zone,
                                    double value, intptr_t* index) const;
   RawMint* LookupCanonicalMint(Zone* zone,
                                int64_t value, intptr_t* index) const;
   RawBigint* LookupCanonicalBigint(Zone* zone,
                                    const Bigint& value, intptr_t* index) const;
   // The methods above are more efficient than this generic one.
   RawInstance* LookupCanonicalInstance(Zone* zone,
-                                       const Instance& value,
-                                       intptr_t* index) const;
+                                       const Instance& value) const;
 
-  void InsertCanonicalConstant(intptr_t index, const Instance& constant) const;
+  RawInstance* InsertCanonicalConstant(Zone* zone,
+                                       const Instance& constant) const;
   void InsertCanonicalNumber(Zone* zone,
                              intptr_t index,
                              const Number& constant) const;
 
   intptr_t FindCanonicalTypeIndex(const AbstractType& needle) const;
   RawAbstractType* CanonicalTypeFromIndex(intptr_t idx) const;
 
   static intptr_t InstanceSize() {
     return RoundedAllocationSize(sizeof(RawClass));
   }
@@ skipping 3916 matching lines @@
   // Equality and identity testing.
   // 1. OperatorEquals: true iff 'this == other' is true in Dart code.
   // 2. IsIdenticalTo: true iff 'identical(this, other)' is true in Dart code.
   // 3. CanonicalizeEquals: used to canonicalize compile-time constants, e.g.,
   //    using bitwise equality of fields and list elements.
   // Subclasses where 1 and 3 coincide may also define a plain Equals, e.g.,
   // String and Integer.
   virtual bool OperatorEquals(const Instance& other) const;
   bool IsIdenticalTo(const Instance& other) const;
   virtual bool CanonicalizeEquals(const Instance& other) const;
+  virtual uword ComputeCanonicalTableHash() const;
+
+  intptr_t SizeFromClass() const {
+#if defined(DEBUG)
+    const Class& cls = Class::Handle(clazz());
+    ASSERT(cls.is_finalized() || cls.is_prefinalized());
+#endif
+    return (clazz()->ptr()->instance_size_in_words_ * kWordSize);
+  }
 
   // Returns Instance::null() if instance cannot be canonicalized.
   // Any non-canonical number of string will be canonicalized here.
   // An instance cannot be canonicalized if it still contains non-canonical
   // instances in its fields.
   // Returns error in error_str, pass NULL if an error cannot occur.
-  virtual RawInstance* CheckAndCanonicalize(const char** error_str) const;
+  virtual RawInstance* CheckAndCanonicalize(Thread* thread,
+                                            const char** error_str) const;
 
   // Returns true if all fields are OK for canonicalization.
-  virtual bool CheckAndCanonicalizeFields(Zone* zone,
+  virtual bool CheckAndCanonicalizeFields(Thread* thread,
                                           const char** error_str) const;
 
   RawObject* GetField(const Field& field) const {
     return *FieldAddr(field);
   }
 
   void SetField(const Field& field, const Object& value) const {
     field.RecordStore(value);
     StorePointer(FieldAddr(field), value.raw());
   }
@@ skipping 199 matching lines @@
   virtual RawAbstractType* CloneUnfinalized() const;
 
   // Return a clone of this uninstantiated type where all references to type
   // parameters are replaced with references to type parameters of the same name
   // but belonging to the new owner class.
   // Apply recursively to type arguments, i.e. instantiated type arguments of
   // an uninstantiated type are not cloned, but shared.
   virtual RawAbstractType* CloneUninstantiated(
       const Class& new_owner, TrailPtr trail = NULL) const;
 
-  virtual RawInstance* CheckAndCanonicalize(const char** error_str) const {
+  virtual RawInstance* CheckAndCanonicalize(Thread* thread,
+                                            const char** error_str) const {
     return Canonicalize();
   }
 
   // Return the canonical version of this type.
   virtual RawAbstractType* Canonicalize(TrailPtr trail = NULL) const;
 
   // Return the object associated with the receiver in the trail or
   // AbstractType::null() if the receiver is not contained in the trail.
   RawAbstractType* OnlyBuddyInTrail(TrailPtr trail) const;
 
@@ skipping 548 matching lines @@
   friend class Class;
 };
 
 
 class Number : public Instance {
  public:
   // TODO(iposva): Add more useful Number methods.
   RawString* ToString(Heap::Space space) const;
 
   // Numbers are canonicalized differently from other instances/strings.
-  virtual RawInstance* CheckAndCanonicalize(const char** error_str) const;
+  virtual RawInstance* CheckAndCanonicalize(Thread* thread,
+                                            const char** error_str) const;
 
  private:
   OBJECT_IMPLEMENTATION(Number, Instance);
 
   friend class Class;
 };
 
 
 class Integer : public Number {
  public:
   static RawInteger* New(const String& str, Heap::Space space = Heap::kNew);
   static RawInteger* NewFromUint64(uint64_t value,
                                    Heap::Space space = Heap::kNew);
 
   // Returns a canonical Integer object allocated in the old gen space.
   static RawInteger* NewCanonical(const String& str);
 
   static RawInteger* New(int64_t value, Heap::Space space = Heap::kNew);
 
   virtual bool OperatorEquals(const Instance& other) const {
     return Equals(other);
   }
   virtual bool CanonicalizeEquals(const Instance& other) const {
     return Equals(other);
   }
+  virtual uword ComputeCanonicalTableHash() const {
+    UNREACHABLE();
+    return 0;
+  }
   virtual bool Equals(const Instance& other) const;
 
   virtual RawObject* HashCode() const { return raw(); }
 
   virtual bool IsZero() const;
   virtual bool IsNegative() const;
 
   virtual double AsDoubleValue() const;
   virtual int64_t AsInt64Value() const;
   virtual int64_t AsTruncatedInt64Value() const {
@@ skipping 165 matching lines @@
   virtual bool IsNegative() const { return Neg(); }
   virtual bool Equals(const Instance& other) const;
 
   virtual double AsDoubleValue() const;
   virtual int64_t AsInt64Value() const;
   virtual int64_t AsTruncatedInt64Value() const;
   virtual uint32_t AsTruncatedUint32Value() const;
 
   virtual int CompareWith(const Integer& other) const;
 
-  virtual bool CheckAndCanonicalizeFields(Zone* zone,
+  virtual bool CheckAndCanonicalizeFields(Thread* thread,
                                           const char** error_str) const;
 
   virtual bool FitsIntoSmi() const;
   bool FitsIntoInt64() const;
   bool FitsIntoUint64() const;
   uint64_t AsUint64Value() const;
 
   static intptr_t InstanceSize() {
     return RoundedAllocationSize(sizeof(RawBigint));
   }
@@ skipping 71 matching lines @@
 // abstract class double in corelib.
 class Double : public Number {
  public:
   double value() const {
     return raw_ptr()->value_;
   }
 
   bool BitwiseEqualsToDouble(double value) const;
   virtual bool OperatorEquals(const Instance& other) const;
   virtual bool CanonicalizeEquals(const Instance& other) const;
+  virtual uword ComputeCanonicalTableHash() const {
+    UNREACHABLE();
+    return 0;
+  }
 
   static RawDouble* New(double d, Heap::Space space = Heap::kNew);
 
   static RawDouble* New(const String& str, Heap::Space space = Heap::kNew);
 
   // Returns a canonical double object allocated in the old gen space.
   static RawDouble* NewCanonical(double d);
 
   // Returns a canonical double object (allocated in the old gen space) or
   // Double::null() if str points to a string that does not convert to a
@@ skipping 130 matching lines @@
 
   // True iff this string equals str1 + str2.
   bool EqualsConcat(const String& str1, const String& str2) const;
 
   virtual bool OperatorEquals(const Instance& other) const {
     return Equals(other);
   }
   virtual bool CanonicalizeEquals(const Instance& other) const {
     return Equals(other);
   }
+  virtual uword ComputeCanonicalTableHash() const {
+    UNREACHABLE();
+    return 0;
+  }
   virtual bool Equals(const Instance& other) const;
 
   intptr_t CompareTo(const String& other) const;
 
   bool StartsWith(const String& other) const;
 
   // Strings are canonicalized using the symbol table.
-  virtual RawInstance* CheckAndCanonicalize(const char** error_str) const;
+  virtual RawInstance* CheckAndCanonicalize(Thread* thread,
+                                            const char** error_str) const;
 
   bool IsSymbol() const { return raw()->IsCanonical(); }
 
   bool IsOneByteString() const {
     return raw()->GetClassId() == kOneByteStringCid;
   }
 
   bool IsTwoByteString() const {
     return raw()->GetClassId() == kTwoByteStringCid;
   }
@@ skipping 661 matching lines @@
     // argument vector of the instantiator.
     ASSERT(value.IsNull() ||
            ((value.Length() >= 1) &&
             value.IsInstantiated() /*&& value.IsCanonical()*/));
     // TODO(asiva): Values read from a message snapshot are not properly marked
     // as canonical. See for example tests/isolate/mandel_isolate_test.dart.
     StorePointer(&raw_ptr()->type_arguments_, value.raw());
   }
 
   virtual bool CanonicalizeEquals(const Instance& other) const;
+  virtual uword ComputeCanonicalTableHash() const;
 
   static const intptr_t kBytesPerElement = kWordSize;
   static const intptr_t kMaxElements = kSmiMax / kBytesPerElement;
 
   static intptr_t type_arguments_offset() {
     return OFFSET_OF(RawArray, type_arguments_);
   }
 
   static intptr_t InstanceSize() {
     ASSERT(sizeof(RawArray) == OFFSET_OF_RETURNED_VALUE(RawArray, data));
     return 0;
   }
 
   static intptr_t InstanceSize(intptr_t len) {
     // Ensure that variable length data is not adding to the object length.
     ASSERT(sizeof(RawArray) == (sizeof(RawInstance) + (2 * kWordSize)));
     ASSERT(0 <= len && len <= kMaxElements);
     return RoundedAllocationSize(sizeof(RawArray) + (len * kBytesPerElement));
   }
 
   // Returns true if all elements are OK for canonicalization.
-  virtual bool CheckAndCanonicalizeFields(Zone* zone,
+  virtual bool CheckAndCanonicalizeFields(Thread* thread,
                                           const char** error_str) const;
 
   // Make the array immutable to Dart code by switching the class pointer
   // to ImmutableArray.
   void MakeImmutable() const;
 
   static RawArray* New(intptr_t len, Heap::Space space = Heap::kNew);
 
   // Creates and returns a new array with 'new_length'. Copies all elements from
   // 'source' to the new array. 'new_length' must be greater than or equal to
@@ skipping 131 matching lines @@
     const Array& contents = Array::Handle(data());
     contents.SetTypeArguments(value);
     StorePointer(&raw_ptr()->type_arguments_, value.raw());
   }
 
   // We don't expect a growable object array to be canonicalized.
   virtual bool CanonicalizeEquals(const Instance& other) const {
     UNREACHABLE();
     return false;
   }
+  virtual uword ComputeCanonicalTableHash() const {
+    UNREACHABLE();
+    return 0;
+  }
 
   // We don't expect a growable object array to be canonicalized.
-  virtual RawInstance* CheckAndCanonicalize(const char** error_str) const {
+  virtual RawInstance* CheckAndCanonicalize(Thread* thread,
+                                            const char** error_str) const {
     UNREACHABLE();
     return Instance::null();
   }
 
   static intptr_t type_arguments_offset() {
     return OFFSET_OF(RawGrowableObjectArray, type_arguments_);
   }
 
   static intptr_t length_offset() {
     return OFFSET_OF(RawGrowableObjectArray, length_);
@@ skipping 153 matching lines @@
   }
 
   void* DataAddr(intptr_t byte_offset) const {
     ASSERT((byte_offset == 0) ||
            ((byte_offset > 0) && (byte_offset < LengthInBytes())));
     return reinterpret_cast<void*>(
         UnsafeMutableNonPointer(raw_ptr()->data()) + byte_offset);
   }
 
   virtual bool CanonicalizeEquals(const Instance& other) const;
+  virtual uword ComputeCanonicalTableHash() const;
 
 #define TYPED_GETTER_SETTER(name, type)                                        \
   type Get##name(intptr_t byte_offset) const {                                 \
     NoSafepointScope no_safepoint;                                             \
     return *reinterpret_cast<type*>(DataAddr(byte_offset));                    \
   }                                                                            \
   void Set##name(intptr_t byte_offset, type value) const {                     \
     NoSafepointScope no_safepoint;                                             \
     *reinterpret_cast<type*>(DataAddr(byte_offset)) = value;                   \
   }
@@ skipping 495 matching lines @@
 
   static intptr_t type_arguments_offset() {
     return OFFSET_OF(RawClosure, type_arguments_);
   }
 
   static intptr_t InstanceSize() {
     return RoundedAllocationSize(sizeof(RawClosure));
   }
 
   // Returns true if all elements are OK for canonicalization.
-  virtual bool CheckAndCanonicalizeFields(Zone* zone,
+  virtual bool CheckAndCanonicalizeFields(Thread* thread,
                                           const char** error_str) const {
     // None of the fields of a closure are instances.
     return true;
   }
 
   static RawClosure* New(const Function& function,
                          const Context& context,
                          Heap::Space space = Heap::kNew);
 
  private:
@@ skipping 484 matching lines @@
 
 
 RawObject* MegamorphicCache::GetTargetFunction(const Array& array,
                                                intptr_t index) {
   return array.At((index * kEntryLength) + kTargetFunctionIndex);
 }
 
 }  // namespace dart
 
 #endif  // VM_OBJECT_H_