Speedup JSReceiver::GetKeys

src/objects.cc

Index: src/objects.cc
diff --git a/src/objects.cc b/src/objects.cc
index c91ed7c5fd366c24c544b2e4a70637a56e8eabfc..3482271f8170ee50bc4b0bfec4ff0753362133ee 100644
--- a/src/objects.cc
+++ b/src/objects.cc
@@ -7915,25 +7915,27 @@ MaybeHandle<FixedArray> FixedArray::AddKeysFromArrayLike(
   return result;
 }
 
+namespace {
+
+inline MaybeHandle<FixedArray> LinearUnionOfKeys(Isolate* isolate,
+                                                 Handle<FixedArray> first,
+                                                 Handle<FixedArray> second) {
+  int second_length = second->length();
+  int first_length = first->length();
 
-MaybeHandle<FixedArray> FixedArray::UnionOfKeys(Handle<FixedArray> first,
-                                                Handle<FixedArray> second) {
-  if (second->length() == 0) return first;
-  if (first->length() == 0) return second;
-  Isolate* isolate = first->GetIsolate();
   Handle<FixedArray> result =
-      isolate->factory()->NewFixedArray(first->length() + second->length());
-  for (int i = 0; i < first->length(); i++) {
+      isolate->factory()->NewFixedArray(first_length + second_length);
+  for (int i = 0; i < first_length; i++) {
     result->set(i, first->get(i));
   }
-  int pos = first->length();
-  for (int j = 0; j < second->length(); j++) {
+  int pos = first_length;
+  for (int j = 0; j < second_length; j++) {
     Object* current = second->get(j);
     int i;
-    for (i = 0; i < first->length(); i++) {
+    for (i = 0; i < first_length; i++) {
       if (current->KeyEquals(first->get(i))) break;
     }
-    if (i == first->length()) {
+    if (i == first_length) {
       result->set(pos++, current);
     }
   }
@@ -7942,6 +7944,48 @@ MaybeHandle<FixedArray> FixedArray::UnionOfKeys(Handle<FixedArray> first,
   return result;
 }
 
+inline MaybeHandle<FixedArray> SublinearUnionOfKeys(Isolate* isolate,
+                                                    Handle<FixedArray> first,
+                                                    Handle<FixedArray> second) {
+  int second_length = second->length();
+  int first_length = first->length();
+
+  Handle<FixedArray> result =
+      isolate->factory()->NewFixedArray(first_length + second_length);
+  Handle<ObjectHashTable> cache = ObjectHashTable::New(isolate, first_length);
+
+  for (int i = 0; i < first_length; i++) {
+    Handle<Object> value(first->get(i), isolate);
+    result->set(i, *value);
+    ObjectHashTable::Put(isolate, cache, value, value);
+  }
+  int pos = first_length;
+  for (int i = 0; i < second_length; i++) {
+    Handle<Object> current(second->get(i), isolate);
+    if (cache->HasKey(isolate, current)) {
+      result->set(pos++, *current);
+    }
+  }
+
+  result->Shrink(pos);
+  return result;
+}
+
+}  // namespace
+
+MaybeHandle<FixedArray> FixedArray::UnionOfKeys(Handle<FixedArray> first,
+                                                Handle<FixedArray> second) {
+  int second_length = second->length();
+  if (second_length == 0) return first;
+  int first_length = first->length();
+  if (first_length == 0) return second;
+  Isolate* isolate = first->GetIsolate();
+  if (first_length <= 2) {
+    return LinearUnionOfKeys(isolate, first, second);
+  }
+  return SublinearUnionOfKeys(isolate, first, second);
+}
+
 
 void FixedArray::CopyTo(int pos, FixedArray* dest, int dest_pos, int len) {
   DisallowHeapAllocation no_gc;
@@ -15070,6 +15114,18 @@ Object* ObjectHashTable::Lookup(Handle<Object> key, int32_t hash) {
 }
 
 
+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;
+}
+
+
 Handle<ObjectHashTable> ObjectHashTable::Put(Handle<ObjectHashTable> table,
                                              Handle<Object> key,
                                              Handle<Object> value) {
@@ -15108,6 +15164,43 @@ Handle<ObjectHashTable> ObjectHashTable::Put(Handle<ObjectHashTable> table,
 }
 
 
+Handle<ObjectHashTable> ObjectHashTable::Put(Isolate* isolate,

[Camillo Bruni, 2015/09/09 09:34:00]

duplicated for tryout... has to be reverted

+                                             Handle<ObjectHashTable> table,
+                                             Handle<Object> key,
+                                             Handle<Object> value) {
+  DCHECK(table->IsKey(*key));
+  DCHECK(!value->IsTheHole());
+
+  // Make sure the key object has an identity hash code.
+  int32_t hash = Object::GetOrCreateHash(isolate, key)->value();
+
+  return Put(isolate, table, key, value, hash);
+}
+
+
+Handle<ObjectHashTable> ObjectHashTable::Put(Isolate* isolate,
+                                             Handle<ObjectHashTable> table,
+                                             Handle<Object> key,
+                                             Handle<Object> value,
+                                             int32_t hash) {

[Camillo Bruni, 2015/09/09 09:34:00]

again, test duplication

+  DCHECK(table->IsKey(*key));
+  DCHECK(!value->IsTheHole());
+
+  int entry = table->FindEntry(isolate, key, hash);
+
+  // Key is already in table, just overwrite value.
+  if (entry != kNotFound) {
+    table->set(EntryToIndex(entry) + 1, *value);
+    return table;
+  }
+
+  // Check whether the hash table should be extended.
+  table = EnsureCapacity(table, 1, key);
+  table->AddEntry(table->FindInsertionEntry(hash), *key, *value);
+  return table;
+}
+
+
 Handle<ObjectHashTable> ObjectHashTable::Remove(Handle<ObjectHashTable> table,
                                                 Handle<Object> key,
                                                 bool* was_present) {