Optimize Map/Set.prototype.forEach

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/v8.h"
 
 #include "src/accessors.h"
 #include "src/allocation-site-scopes.h"
 #include "src/api.h"
 #include "src/arguments.h"
@@ skipping 16368 matching lines @@
   int index = table->AddEntry(hash->value());
   table->set(index, *key);
   table->set(index + kValueOffset, *value);
   return table;
 }
 
 
 template<class Derived, class TableType>
 Handle<JSObject> OrderedHashTableIterator<Derived, TableType>::Next(
     Handle<Derived> iterator) {
-  Isolate* isolate = iterator->GetIsolate();
-  Factory* factory = isolate->factory();
+  Factory* factory = iterator->GetIsolate()->factory();
 
-  Handle<Object> maybe_table(iterator->table(), isolate);
-  if (!maybe_table->IsUndefined()) {
-    iterator->Transition();
-
-    Handle<TableType> table(TableType::cast(iterator->table()), isolate);
-    int index = Smi::cast(iterator->index())->value();
-    int used_capacity = table->UsedCapacity();
-
-    while (index < used_capacity && table->KeyAt(index)->IsTheHole()) {
-      index++;
-    }
-
-    if (index < used_capacity) {
-      int entry_index = table->EntryToIndex(index);
-      Handle<Object> value =
-          Derived::ValueForKind(iterator, entry_index);
-      iterator->set_index(Smi::FromInt(index + 1));
-      return factory->NewIteratorResultObject(value, false);
-    }
-
-    iterator->set_table(iterator->GetHeap()->undefined_value());
+  if (HasMore(iterator)) {
+    Handle<Object> value = Derived::CurrentIteratorResultValue(iterator);
+    iterator->MoveNext();
+    return factory->NewIteratorResultObject(value, false);
   }
 
   return factory->NewIteratorResultObject(factory->undefined_value(), true);
 }
 
 
 template<class Derived, class TableType>
 void OrderedHashTableIterator<Derived, TableType>::Transition() {
   Isolate* isolate = GetIsolate();
   Handle<TableType> table(TableType::cast(this->table()), isolate);
@@ skipping 20 matching lines @@
     }
 
     table = next_table;
   }
 
   set_table(*table);
   set_index(Smi::FromInt(index));
 }
 
 
+template<class Derived, class TableType>
+bool OrderedHashTableIterator<Derived, TableType>::HasMore(

[adamk, 2014/06/16 22:13:57]

On second reading, does HasMore() ever do allocation? Perhaps it could be made
an instance method too...though you might want to wait to see if mstarzinger has
an opinion before doing that.

[arv (Not doing code reviews), 2014/06/16 23:53:09]

The only one that does allocation is Next (to create the iterator result
objects).

+    Handle<Derived> iterator) {
+  Isolate* isolate = iterator->GetIsolate();
+
+  if (iterator->table()->IsUndefined()) {
+    return false;
+  }
+
+  iterator->Transition();

[adamk, 2014/06/16 22:13:57]

This is the only bit that suggests that HasMore uses handles, since Transition()
uses Handles internally. But looking at the implementation of Transition() I
think that might be bogus, too (Handles in an instance method are always
scary-looking, since if the Handles are actually needed to protect against GC,
|this| could become invalid).

[arv (Not doing code reviews), 2014/06/16 23:53:09]

I think I misunderstood this. Only allocations can cause GC. Correct? I was
thinking that clearing references could cause GC but I'm pretty sure that is not
the case any more.

+
+  Handle<TableType> table(TableType::cast(iterator->table()), isolate);
+  int index = Smi::cast(iterator->index())->value();
+  int used_capacity = table->UsedCapacity();
+
+  while (index < used_capacity && table->KeyAt(index)->IsTheHole()) {
+    index++;
+  }
+
+  iterator->set_index(Smi::FromInt(index));
+
+  if (index < used_capacity) {
+    return true;
+  }
+
+  iterator->set_table(iterator->GetHeap()->undefined_value());
+  return false;
+}
+
+
 template Handle<JSObject>
 OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::Next(
     Handle<JSSetIterator> iterator);
 
+template bool
+OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::HasMore(
+    Handle<JSSetIterator> iterator);
+
+template void
+OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::MoveNext();
+
+template Object*
+OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::CurrentKey();
+
 template void
 OrderedHashTableIterator<JSSetIterator, OrderedHashSet>::Transition();
 
 
 template Handle<JSObject>
 OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::Next(
     Handle<JSMapIterator> iterator);
 
+template bool
+OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::HasMore(
+    Handle<JSMapIterator> iterator);
+
+template void
+OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::MoveNext();
+
+template Object*
+OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::CurrentKey();
+
 template void
 OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::Transition();
 
 
-Handle<Object> JSSetIterator::ValueForKind(
-    Handle<JSSetIterator> iterator, int entry_index) {
-  int kind = iterator->kind()->value();
-  // Set.prototype only has values and entries.
-  ASSERT(kind == kKindValues || kind == kKindEntries);
-
+Handle<Object> JSSetIterator::CurrentIteratorResultValue(
+    Handle<JSSetIterator> iterator) {
   Isolate* isolate = iterator->GetIsolate();
-  Factory* factory = isolate->factory();
-
-  Handle<OrderedHashSet> table(
-      OrderedHashSet::cast(iterator->table()), isolate);
-  Handle<Object> value = Handle<Object>(table->get(entry_index), isolate);
+  int kind = Smi::cast(iterator->kind())->value();
+  Handle<Object> value(iterator->CurrentKey(), isolate);
 
   if (kind == kKindEntries) {
+    Factory* factory = isolate->factory();
     Handle<FixedArray> array = factory->NewFixedArray(2);
     array->set(0, *value);
     array->set(1, *value);
     return factory->NewJSArrayWithElements(array);
   }
 
+  // Set.prototype only has values and entries.
+  ASSERT(kind == kKindValues);
+
   return value;
 }
 
 
-Handle<Object> JSMapIterator::ValueForKind(
-    Handle<JSMapIterator> iterator, int entry_index) {
-  int kind = iterator->kind()->value();
-  ASSERT(kind == kKindKeys || kind == kKindValues || kind == kKindEntries);
-
+Handle<Object> JSMapIterator::CurrentIteratorResultValue(
+    Handle<JSMapIterator> iterator) {
   Isolate* isolate = iterator->GetIsolate();
   Factory* factory = isolate->factory();
 
-  Handle<OrderedHashMap> table(
-      OrderedHashMap::cast(iterator->table()), isolate);
-
+  int kind = Smi::cast(iterator->kind())->value();
   switch (kind) {
     case kKindKeys:
-      return Handle<Object>(table->get(entry_index), isolate);
+      return handle(iterator->CurrentKey(), isolate);
 
     case kKindValues:
-      return Handle<Object>(table->get(entry_index + 1), isolate);
+      return handle(iterator->CurrentValue(), isolate);
 
     case kKindEntries: {
-      Handle<Object> key(table->get(entry_index), isolate);
-      Handle<Object> value(table->get(entry_index + 1), isolate);
       Handle<FixedArray> array = factory->NewFixedArray(2);
-      array->set(0, *key);
-      array->set(1, *value);
+      array->set(0, iterator->CurrentKey());
+      array->set(1, iterator->CurrentValue());
       return factory->NewJSArrayWithElements(array);
     }
   }
 
   UNREACHABLE();
+
   return factory->undefined_value();
 }
 
 
 DeclaredAccessorDescriptorIterator::DeclaredAccessorDescriptorIterator(
     DeclaredAccessorDescriptor* descriptor)
     : array_(descriptor->serialized_data()->GetDataStartAddress()),
       length_(descriptor->serialized_data()->length()),
       offset_(0) {
 }
@@ skipping 576 matching lines @@
 #define ERROR_MESSAGES_TEXTS(C, T) T,
   static const char* error_messages_[] = {
       ERROR_MESSAGES_LIST(ERROR_MESSAGES_TEXTS)
   };
 #undef ERROR_MESSAGES_TEXTS
   return error_messages_[reason];
 }
 
 
 } }  // namespace v8::internal