Speedup JSReceiver::GetKeys

src/objects.cc

Index: src/objects.cc
diff --git a/src/objects.cc b/src/objects.cc
index 9bf72a68d7e42349c821d6883578f0725a6d8c13..98a53f03c537715ee61e84e06d7b00ef7272b44c 100644
--- a/src/objects.cc
+++ b/src/objects.cc
@@ -6480,11 +6480,124 @@ Handle<FixedArray> JSObject::GetEnumPropertyKeys(Handle<JSObject> object,
 }
 
 
+Handle<FixedArray> KeyAccumulator::GetKeys() {
+  if (keys_.is_null()) {
+    return isolate_->factory()->empty_fixed_array();
+  }
+  keys_->Shrink(GetLength());
+  return keys_;
+}
+
+
+int KeyAccumulator::GetLength() { return length_; }
+
+
+void KeyAccumulator::AddKey(Handle<Object> key) {
+  if (!set_.is_null()) {
+    set_ = ObjectHashTable::Put(isolate_, set_, key, key);
+  }
+  EnsureCapacity(length_);
+  keys_->set(length_, *key);
+  length_++;
+}
+
+
+bool KeyAccumulator::HasKey(Handle<Object> key, int limit) {
+  if (!set_.is_null()) {
+    return set_->HasKey(isolate_, key);
+  }
+  // simple fallback in case we didn't use the set_ yet
+  limit = Min(limit, length_);
+  for (int i = 0; i < limit; i++) {
+    Object* current = keys_->get(i);
+    if (current->KeyEquals(*key)) return true;
+  }
+  return false;
+}
+
+
+void KeyAccumulator::AddKeys(Handle<FixedArray> array,
+                             FixedArray::KeyFilter filter) {
+  int add_length = array->length();
+  if (add_length == 0) return;
+  if (keys_.is_null() && filter == FixedArray::ALL_KEYS) {
+    keys_ = array;
+    length_ = keys_->length();
+    return;
+  }
+  PrepareForComparisons(add_length);
+  int previous_key_count = length_;
+  for (int i = 0; i < add_length; i++) {
+    Handle<Object> current(array->get(i), isolate_);
+    if (HasKey(current, previous_key_count)) continue;
+    AddKey(current);
+  }
+}
+
+
+void KeyAccumulator::AddKeys(Handle<JSObject> array_like,
+                             FixedArray::KeyFilter filter) {
+  DCHECK(array_like->IsJSArray() || array_like->HasSloppyArgumentsElements());
+  ElementsAccessor* accessor = array_like->GetElementsAccessor();
+  accessor->AddElementsToFixedArrayWithAccumulator(array_like, this, filter);
+#ifdef ENABLE_SLOW_DCHECKS
+  if (FLAG_enable_slow_asserts) {
+    DisallowHeapAllocation no_allocation;
+    for (int i = 0; i < GetLength(); i++) {
+      Object* current = keys_->get(i);
+      DCHECK(current->IsNumber() || current->IsName());
+    }
+  }
+#endif
+}
+
+
+void KeyAccumulator::PrepareForComparisons(int count) {
+  // Depending on how many comparisons we do we should switch to the
+  // hash-table-based checks which have a high one-time overhead
+  if (!set_.is_null()) return;
+  // This is an unscientific guess for the threshold when we should
+  // switch to the hash-table
+  if (length_ * count < 100) return;

[Camillo Bruni, 2015/09/14 07:34:04]

I tried a bit with different values and 100 turned out to be roughly ok...

+  set_ = ObjectHashTable::New(isolate_, length_);

[Camillo Bruni, 2015/09/14 07:34:04]

Technically this should be a set but we only have a reasonable dict
implementation. So we waste a bit of memory here in the case we fall back to
dict.

+  for (int i = 0; i < length_; i++) {
+    Handle<Object> value(keys_->get(i), isolate_);
+    set_ = ObjectHashTable::Put(isolate_, set_, value, value);
+  }
+}
+
+
+void KeyAccumulator::EnsureCapacity(int capacity) {
+  if (keys_.is_null() || keys_->length() <= capacity) {
+    Grow();
+  }
+}
+
+
+void KeyAccumulator::Grow() {
+  int capacity = keys_.is_null() ? 16 : keys_->length() * 2 + 16;
+  Handle<FixedArray> new_keys = isolate_->factory()->NewFixedArray(capacity);
+  if (keys_.is_null()) {
+    keys_ = new_keys;
+    return;
+  }
+  int buffer_length = keys_->length();
+  {
+    DisallowHeapAllocation no_gc;
+    WriteBarrierMode mode = new_keys->GetWriteBarrierMode(no_gc);
+    for (int i = 0; i < buffer_length; i++) {
+      new_keys->set(i, keys_->get(i), mode);
+    }
+  }
+  keys_ = new_keys;
+}
+
+
 MaybeHandle<FixedArray> JSReceiver::GetKeys(Handle<JSReceiver> object,
                                             KeyCollectionType type) {
   USE(ContainsOnlyValidKeys);
   Isolate* isolate = object->GetIsolate();
-  Handle<FixedArray> content = isolate->factory()->empty_fixed_array();
+  KeyAccumulator accumulator(isolate);
   Handle<JSFunction> arguments_function(
       JSFunction::cast(isolate->sloppy_arguments_map()->GetConstructor()));
 
@@ -6507,11 +6620,8 @@ MaybeHandle<FixedArray> JSReceiver::GetKeys(Handle<JSReceiver> object,
                           arraysize(args),
                           args),
           FixedArray);
-      ASSIGN_RETURN_ON_EXCEPTION(
-          isolate, content,
-          FixedArray::AddKeysFromArrayLike(
-              content, Handle<JSObject>::cast(names)),
-          FixedArray);
+      accumulator.AddKeys(Handle<JSObject>::cast(names),
+                          FixedArray::NON_SYMBOL_KEYS);
       break;
     }
 
@@ -6530,23 +6640,17 @@ MaybeHandle<FixedArray> JSReceiver::GetKeys(Handle<JSReceiver> object,
     Handle<FixedArray> element_keys =
         isolate->factory()->NewFixedArray(current->NumberOfEnumElements());
     current->GetEnumElementKeys(*element_keys);
-    ASSIGN_RETURN_ON_EXCEPTION(
-        isolate, content,
-        FixedArray::UnionOfKeys(content, element_keys),
-        FixedArray);
-    DCHECK(ContainsOnlyValidKeys(content));
+    accumulator.AddKeys(element_keys, FixedArray::ALL_KEYS);
+    DCHECK(ContainsOnlyValidKeys(accumulator.GetKeys()));
 
     // Add the element keys from the interceptor.
     if (current->HasIndexedInterceptor()) {
       Handle<JSObject> result;
       if (JSObject::GetKeysForIndexedInterceptor(
               current, object).ToHandle(&result)) {
-        ASSIGN_RETURN_ON_EXCEPTION(
-            isolate, content,
-            FixedArray::AddKeysFromArrayLike(content, result),
-            FixedArray);
+        accumulator.AddKeys(result, FixedArray::ALL_KEYS);
       }
-      DCHECK(ContainsOnlyValidKeys(content));
+      DCHECK(ContainsOnlyValidKeys(accumulator.GetKeys()));
     }
 
     // We can cache the computed property keys if access checks are
@@ -6564,27 +6668,37 @@ MaybeHandle<FixedArray> JSReceiver::GetKeys(Handle<JSReceiver> object,
          !current->IsJSValue() && !current->IsAccessCheckNeeded() &&
          !current->HasNamedInterceptor() && !current->HasIndexedInterceptor());
     // Compute the property keys and cache them if possible.
-    ASSIGN_RETURN_ON_EXCEPTION(
-        isolate, content,
-        FixedArray::UnionOfKeys(
-            content, JSObject::GetEnumPropertyKeys(current, cache_enum_keys)),
-        FixedArray);
-    DCHECK(ContainsOnlyValidKeys(content));
+
+    Handle<FixedArray> enum_keys =
+        JSObject::GetEnumPropertyKeys(current, cache_enum_keys);
+    accumulator.AddKeys(enum_keys, FixedArray::ALL_KEYS);
+    //    ASSIGN_RETURN_ON_EXCEPTION(
+    //        isolate, content,
+    //        FixedArray::UnionOfKeys(
+    //            content, JSObject::GetEnumPropertyKeys(current,
+    //            cache_enum_keys)),
+    //        FixedArray);
+    DCHECK(ContainsOnlyValidKeys(accumulator.GetKeys()));
 
     // Add the non-symbol property keys from the interceptor.
     if (current->HasNamedInterceptor()) {
       Handle<JSObject> result;
       if (JSObject::GetKeysForNamedInterceptor(
               current, object).ToHandle(&result)) {
-        ASSIGN_RETURN_ON_EXCEPTION(
-            isolate, content, FixedArray::AddKeysFromArrayLike(
-                                  content, result, FixedArray::NON_SYMBOL_KEYS),
-            FixedArray);
+        accumulator.AddKeys(result, FixedArray::NON_SYMBOL_KEYS);
+        //        ASSIGN_RETURN_ON_EXCEPTION(
+        //            isolate, content, AddKeysFromArrayLike(
+        //                                  content, result,
+        //                                  FixedArray::NON_SYMBOL_KEYS),
+        //            FixedArray);
       }
-      DCHECK(ContainsOnlyValidKeys(content));
+      DCHECK(ContainsOnlyValidKeys(accumulator.GetKeys()));
     }
   }
-  return content;
+
+  Handle<FixedArray> keys = accumulator.GetKeys();
+  DCHECK(ContainsOnlyValidKeys(keys));
+  return keys;
 }
 
 
@@ -8085,26 +8199,6 @@ void FixedArray::Shrink(int new_length) {
 }
 
 
-MaybeHandle<FixedArray> FixedArray::AddKeysFromArrayLike(
-    Handle<FixedArray> content, Handle<JSObject> array, KeyFilter filter) {
-  DCHECK(array->IsJSArray() || array->HasSloppyArgumentsElements());
-  ElementsAccessor* accessor = array->GetElementsAccessor();
-  Handle<FixedArray> result =
-      accessor->AddElementsToFixedArray(array, content, filter);
-
-#ifdef ENABLE_SLOW_DCHECKS
-  if (FLAG_enable_slow_asserts) {
-    DisallowHeapAllocation no_allocation;
-    for (int i = 0; i < result->length(); i++) {
-      Object* current = result->get(i);
-      DCHECK(current->IsNumber() || current->IsName());
-    }
-  }
-#endif
-  return result;
-}
-
-
 MaybeHandle<FixedArray> FixedArray::UnionOfKeys(Handle<FixedArray> first,
                                                 Handle<FixedArray> second) {
   if (second->length() == 0) return first;
@@ -15227,6 +15321,19 @@ Object* Dictionary<Derived, Shape, Key>::SlowReverseLookup(Object* value) {
 }
 
 
+bool ObjectHashTable::HasKey(Isolate* isolate, Handle<Object> key) {
+  DisallowHeapAllocation no_gc;
+  DCHECK(IsKey(*key));
+
+  // If the object does not have an identity hash, it was never used as a key.
+  Object* hash = key->GetHash();
+  if (hash->IsUndefined()) return false;
+
+  int entry = FindEntry(isolate, key, Smi::cast(hash)->value());
+  return entry != kNotFound;
+}
+
+
 Object* ObjectHashTable::Lookup(Isolate* isolate, Handle<Object> key,
                                 int32_t hash) {
   DisallowHeapAllocation no_gc;
@@ -15261,14 +15368,21 @@ Object* ObjectHashTable::Lookup(Handle<Object> key, int32_t hash) {
 Handle<ObjectHashTable> ObjectHashTable::Put(Handle<ObjectHashTable> table,
                                              Handle<Object> key,
                                              Handle<Object> value) {
+  return Put(table->GetIsolate(), table, key, value);
+}
+
+
+Handle<ObjectHashTable> ObjectHashTable::Put(Isolate* isolate,
+                                             Handle<ObjectHashTable> table,
+                                             Handle<Object> key,
+                                             Handle<Object> value) {
   DCHECK(table->IsKey(*key));
   DCHECK(!value->IsTheHole());
 
-  Isolate* isolate = table->GetIsolate();
   // Make sure the key object has an identity hash code.
   int32_t hash = Object::GetOrCreateHash(isolate, key)->value();
 
-  return Put(table, key, value, hash);
+  return Put(isolate, table, key, value, hash);
 }
 
 
@@ -15276,11 +15390,18 @@ Handle<ObjectHashTable> ObjectHashTable::Put(Handle<ObjectHashTable> table,
                                              Handle<Object> key,
                                              Handle<Object> value,
                                              int32_t hash) {
+  return Put(table->GetIsolate(), table, key, value, hash);
+}
+
+
+Handle<ObjectHashTable> ObjectHashTable::Put(Isolate* isolate,
+                                             Handle<ObjectHashTable> table,
+                                             Handle<Object> key,
+                                             Handle<Object> value,
+                                             int32_t hash) {
   DCHECK(table->IsKey(*key));
   DCHECK(!value->IsTheHole());
 
-  Isolate* isolate = table->GetIsolate();
-
   int entry = table->FindEntry(isolate, key, hash);
 
   // Key is already in table, just overwrite value.