Optimize Map/Set.prototype.forEach

src/objects.cc

Index: src/objects.cc
diff --git a/src/objects.cc b/src/objects.cc
index 274749d568393b95300ba9a666a57e3b4f32c08b..1fd264026ef0a0f409c7005534476143d417a54f 100644
--- a/src/objects.cc
+++ b/src/objects.cc
@@ -16386,30 +16386,12 @@ Handle<OrderedHashMap> OrderedHashMap::Put(Handle<OrderedHashMap> table,
 template<class Derived, class TableType>
 Handle<JSObject> OrderedHashTableIterator<Derived, TableType>::Next(
     Handle<Derived> iterator) {
-  Isolate* isolate = iterator->GetIsolate();
-  Factory* factory = isolate->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();
+  Factory* factory = iterator->GetIsolate()->factory();
 
-    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);
@@ -16450,10 +16432,50 @@ void OrderedHashTableIterator<Derived, TableType>::Transition() {
 }
 
 
+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();
 
@@ -16462,63 +16484,64 @@ template Handle<JSObject>
 OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::Next(
     Handle<JSMapIterator> iterator);
 
+template bool
+OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::HasMore(
+    Handle<JSMapIterator> iterator);
+
 template void
-OrderedHashTableIterator<JSMapIterator, OrderedHashMap>::Transition();
+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();
 }