Speedup JSReceiver::GetKeys

src/objects.h

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #ifndef V8_OBJECTS_H_
 #define V8_OBJECTS_H_
 
 #include <iosfwd>
 
 #include "src/allocation.h"
@@ skipping 2454 matching lines @@
   // Gives access to raw memory which stores the array's data.
   inline Object** data_start();
 
   inline void FillWithHoles(int from, int to);
 
   // Shrink length and insert filler objects.
   void Shrink(int length);
 
   enum KeyFilter { ALL_KEYS, NON_SYMBOL_KEYS };
 
-  // Add the elements of a JSArray to this FixedArray.
-  MUST_USE_RESULT static MaybeHandle<FixedArray> AddKeysFromArrayLike(
-      Handle<FixedArray> content, Handle<JSObject> array,
-      KeyFilter filter = ALL_KEYS);
-
-  // Computes the union of keys and return the result.
-  // Used for implementing "for (n in object) { }"
-  MUST_USE_RESULT static MaybeHandle<FixedArray> UnionOfKeys(
-      Handle<FixedArray> first,
-      Handle<FixedArray> second);
-
   // Copy a sub array from the receiver to dest.
   void CopyTo(int pos, FixedArray* dest, int dest_pos, int len);
 
   // Garbage collection support.
   static int SizeFor(int length) { return kHeaderSize + length * kPointerSize; }
 
   // Code Generation support.
   static int OffsetOfElementAt(int index) { return SizeFor(index); }
 
   // Garbage collection support.
@@ skipping 1158 matching lines @@
   static Handle<Derived> EnsureGrowable(Handle<Derived> table);
 
   // Returns an OrderedHashTable (possibly |table|) that's shrunken
   // if possible.
   static Handle<Derived> Shrink(Handle<Derived> table);
 
   // Returns a new empty OrderedHashTable and records the clearing so that
   // exisiting iterators can be updated.
   static Handle<Derived> Clear(Handle<Derived> table);
 
+  // Returns a true if the OrderedHashTable contains the key
+  static bool HasKey(Handle<Derived> table, Handle<Object> key);
+
   int NumberOfElements() {
     return Smi::cast(get(kNumberOfElementsIndex))->value();
   }
 
   int NumberOfDeletedElements() {
     return Smi::cast(get(kNumberOfDeletedElementsIndex))->value();
   }
 
   int UsedCapacity() { return NumberOfElements() + NumberOfDeletedElements(); }
 
   int NumberOfBuckets() {
     return Smi::cast(get(kNumberOfBucketsIndex))->value();
   }
 
   // Returns an index into |this| for the given entry.
   int EntryToIndex(int entry) {
     return kHashTableStartIndex + NumberOfBuckets() + (entry * kEntrySize);
   }
 
+  int HashToBucket(int hash) { return hash & (NumberOfBuckets() - 1); }
+
+  int HashToEntry(int hash) {
+    int bucket = HashToBucket(hash);
+    Object* entry = this->get(kHashTableStartIndex + bucket);
+    return Smi::cast(entry)->value();
+  }
+
+  int KeyToFirstEntry(Object* key) {
+    Object* hash = key->GetHash();
+    // If the object does not have an identity hash, it was never used as a key
+    if (hash->IsUndefined()) return kNotFound;
+    return HashToEntry(Smi::cast(hash)->value());
+  }
+
+  int NextChainEntry(int entry) {
+    Object* next_entry = get(EntryToIndex(entry) + entrysize);

[Igor Sheludko, 2015/09/17 09:55:12]

s/entrysize/kChainOffset/g (for readability).

+    return Smi::cast(next_entry)->value();
+  }

[Igor Sheludko, 2015/09/17 09:55:12]

Please add a blank line here.

   Object* KeyAt(int entry) { return get(EntryToIndex(entry)); }
 
   bool IsObsolete() {
     return !get(kNextTableIndex)->IsSmi();
   }
 
   // The next newer table. This is only valid if the table is obsolete.
   Derived* NextTable() {
     return Derived::cast(get(kNextTableIndex));
   }
@@ skipping 26 matching lines @@
   static const int kEntrySize = entrysize + 1;
   static const int kChainOffset = entrysize;
 
   static const int kLoadFactor = 2;
 
   // NumberOfDeletedElements is set to kClearedTableSentinel when
   // the table is cleared, which allows iterator transitions to
   // optimize that case.
   static const int kClearedTableSentinel = -1;
 
- private:
+ protected:
   static Handle<Derived> Rehash(Handle<Derived> table, int new_capacity);
 
   void SetNumberOfBuckets(int num) {
     set(kNumberOfBucketsIndex, Smi::FromInt(num));
   }
 
   void SetNumberOfElements(int num) {
     set(kNumberOfElementsIndex, Smi::FromInt(num));
   }
 
@@ skipping 21 matching lines @@
 };
 
 
 class JSSetIterator;
 
 
 class OrderedHashSet: public OrderedHashTable<
     OrderedHashSet, JSSetIterator, 1> {
  public:
   DECLARE_CAST(OrderedHashSet)
+
+  static Handle<OrderedHashSet> Add(Handle<OrderedHashSet> table,
+                                    Handle<Object> value);
 };
 
 
 class JSMapIterator;
 
 
 class OrderedHashMap
     : public OrderedHashTable<OrderedHashMap, JSMapIterator, 2> {
  public:
   DECLARE_CAST(OrderedHashMap)
@@ skipping 6689 matching lines @@
   static inline int set(int value, int bit_position, bool v) {
     if (v) {
       value |= (1 << bit_position);
     } else {
       value &= ~(1 << bit_position);
     }
     return value;
   }
 };
 
+
+class KeyAccumulator final BASE_EMBEDDED {
+ public:
+  explicit KeyAccumulator(Isolate* isolate)
+      : isolate_(isolate), keys_(), set_(), length_(0) {}
+
+  void AddKey(Handle<Object> key, int check_limit);
+  void AddKeys(Handle<FixedArray> array, FixedArray::KeyFilter filter);
+  void AddKeys(Handle<JSObject> array, FixedArray::KeyFilter filter);
+  void PrepareForComparisons(int count);
+  int GetLength();
+  Handle<FixedArray> GetKeys();
+
+ private:
+  void EnsureCapacity(int capacity);
+  void Grow();
+
+  Isolate* isolate_;
+  Handle<FixedArray> keys_;
+  Handle<OrderedHashSet> set_;
+  int length_;
+  DISALLOW_COPY_AND_ASSIGN(KeyAccumulator);
+};
 } }  // namespace v8::internal
 
 #endif  // V8_OBJECTS_H_