Speedup JSReceiver::GetKeys

src/objects.cc

 // Copyright 2013 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.
 
 #include "src/objects.h"
 
 #include <iomanip>
 #include <sstream>
 
 #include "src/accessors.h"
@@ skipping 7897 matching lines @@
     DisallowHeapAllocation no_allocation;
     for (int i = 0; i < result->length(); i++) {
       Object* current = result->get(i);
       DCHECK(current->IsNumber() || current->IsName());
     }
   }
 #endif
   return result;
 }
 
+namespace {
 
-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();
+inline MaybeHandle<FixedArray> LinearUnionOfKeys(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());
-  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);
     }
   }
 
   result->Shrink(pos);
   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;
   WriteBarrierMode mode = dest->GetWriteBarrierMode(no_gc);
   for (int index = 0; index < len; index++) {
     dest->set(dest_pos+index, get(pos+index), mode);
   }
 }
 
 
@@ skipping 7108 matching lines @@
   }
   return Lookup(isolate, key, Smi::cast(hash)->value());
 }
 
 
 Object* ObjectHashTable::Lookup(Handle<Object> key, int32_t hash) {
   return Lookup(GetIsolate(), key, 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) {
   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();
 
@@ skipping 18 matching lines @@
     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::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) {
   DCHECK(table->IsKey(*key));
 
   Object* hash = key->GetHash();
   if (hash->IsUndefined()) {
     *was_present = false;
     return table;
   }
@@ skipping 1043 matching lines @@
   if (cell->value() != *new_value) {
     cell->set_value(*new_value);
     Isolate* isolate = cell->GetIsolate();
     cell->dependent_code()->DeoptimizeDependentCodeGroup(
         isolate, DependentCode::kPropertyCellChangedGroup);
   }
 }
 
 }  // namespace internal
 }  // namespace v8