Optimize Map/Set.prototype.forEach

Optimize Map/Set.prototype.forEach

Instead of using an iterator result object and an entries array
(for Map) we call multiple runtime functions that returns the values
without wrapping them in temporary objects.

This gives a 85% performance increase for Map.prototype.forEach as
well as 13% and 8% perf increase overall on the Map and Set tests.

BUG=None
LOG=Y

[arv (Not doing code reviews), 2014-06-11 18:42:31]

Add the runtime-gen files

[arv (Not doing code reviews), 2014-06-11 18:50:26]

PTAl

[adamk, 2014-06-16 20:37:46]

https://codereview.chromium.org/329253004/diff/40001/src/objects-inl.h
File src/objects-inl.h (right):

https://codereview.chromium.org/329253004/diff/40001/src/objects-inl.h#newcod...
src/objects-inl.h:6963: TableType* table(TableType::cast(iterator->table()));
The use of a raw pointer in a handlified function looks wrong. Can CurrentKey()
just be an instance method instead of a static, and operate on raw pointers? It
doesn't look like it needs to do any allocation.

https://codereview.chromium.org/329253004/diff/40001/src/objects-inl.h#newcod...
src/objects-inl.h:6971: Handle<Object>
JSMapIterator::CurrentValue(Handle<JSMapIterator> iterator) {
Same as above, but less scary. Seems like this could be an instance method?

https://codereview.chromium.org/329253004/diff/40001/src/runtime.cc
File src/runtime.cc (right):

https://codereview.chromium.org/329253004/diff/40001/src/runtime.cc#newcode1614
src/runtime.cc:1614: HandleScope scope(isolate);
If you make CurrentKey/CurrentValue instance functions that don't operate on
handles, you should be able to use a SealHandleScope instead here, which should
be slightly faster.

[arv (Not doing code reviews), 2014-06-16 21:28:35]

Unhandlify

[arv (Not doing code reviews), 2014-06-16 21:57:21]

All done

https://codereview.chromium.org/329253004/diff/40001/src/objects-inl.h
File src/objects-inl.h (right):

https://codereview.chromium.org/329253004/diff/40001/src/objects-inl.h#newcod...
src/objects-inl.h:6963: TableType* table(TableType::cast(iterator->table()));
On 2014/06/16 20:37:46, adamk wrote:
> The use of a raw pointer in a handlified function looks wrong. Can
CurrentKey()
> just be an instance method instead of a static, and operate on raw pointers?
It
> doesn't look like it needs to do any allocation.

Done.

https://codereview.chromium.org/329253004/diff/40001/src/objects-inl.h#newcod...
src/objects-inl.h:6971: Handle<Object>
JSMapIterator::CurrentValue(Handle<JSMapIterator> iterator) {
On 2014/06/16 20:37:46, adamk wrote:
> Same as above, but less scary. Seems like this could be an instance method?

Done.

https://codereview.chromium.org/329253004/diff/40001/src/runtime.cc
File src/runtime.cc (right):

https://codereview.chromium.org/329253004/diff/40001/src/runtime.cc#newcode1614
src/runtime.cc:1614: HandleScope scope(isolate);
On 2014/06/16 20:37:46, adamk wrote:
> If you make CurrentKey/CurrentValue instance functions that don't operate on
> handles, you should be able to use a SealHandleScope instead here, which
should
> be slightly faster.

Done.

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

More handlification comments...

https://codereview.chromium.org/329253004/diff/50001/src/objects.cc
File src/objects.cc (right):

https://codereview.chromium.org/329253004/diff/50001/src/objects.cc#newcode16436
src/objects.cc:16436: bool OrderedHashTableIterator<Derived,
TableType>::HasMore(
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.

https://codereview.chromium.org/329253004/diff/50001/src/objects.cc#newcode16444
src/objects.cc:16444: iterator->Transition();
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).

https://codereview.chromium.org/329253004/diff/50001/src/runtime.cc
File src/runtime.cc (right):

https://codereview.chromium.org/329253004/diff/50001/src/runtime.cc#newcode1616
src/runtime.cc:1616: CONVERT_ARG_HANDLE_CHECKED(JSSetIterator, holder, 0);
This should just be CONVERT_ARG_CHECKED() (no "HANDLE") now.

https://codereview.chromium.org/329253004/diff/50001/src/runtime.cc#newcode1745
src/runtime.cc:1745: CONVERT_ARG_HANDLE_CHECKED(JSMapIterator, holder, 0);
ditto, and lots more below.

Basically, SealHandleScope should be paired with CONVERT_ARG_CHECKED(), while
HandleScope should be paired with CONVERT_ARG_HANDLE_CHECKED(). Similarly, if
your Runtime function uses Handles at all, it should have a HandleScope, not a
SealHandleScope.

V8 folks, please correct me if I'm providing poor advice here. My understanding
is that V8's not abandoning raw pointers altogether, only in those cases that
previously required MaybeObjects.

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

https://codereview.chromium.org/329253004/diff/50001/src/objects.cc
File src/objects.cc (right):

https://codereview.chromium.org/329253004/diff/50001/src/objects.cc#newcode16436
src/objects.cc:16436: bool OrderedHashTableIterator<Derived,
TableType>::HasMore(
On 2014/06/16 22:13:57, adamk wrote:
> 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.

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

https://codereview.chromium.org/329253004/diff/50001/src/objects.cc#newcode16444
src/objects.cc:16444: iterator->Transition();
On 2014/06/16 22:13:57, adamk wrote:
> 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).

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.

[arv (Not doing code reviews), 2014-06-17 16:52:40]

It all makes sense now

[arv (Not doing code reviews), 2014-06-17 16:58:55]

Update count to fix merge issue

[arv (Not doing code reviews), 2014-06-17 18:00:04]

PTAL

[adamk, 2014-06-18 17:09:29]

lgtm, hopefully my advice matches current v8 practice :)

[arv (Not doing code reviews), 2014-06-18 18:22:56]

Michael, can you also take a look?

Thanks.

[arv (Not doing code reviews), 2014-06-23 19:10:52]

Adding Andreas since Michael is not responding.

[Michael Starzinger, 2014-06-23 19:51:52]

Handing off to either Andreas or Danno.

https://codereview.chromium.org/329253004/diff/90001/src/collection.js
File src/collection.js (right):

https://codereview.chromium.org/329253004/diff/90001/src/collection.js#newcode87
src/collection.js:87: %SetIteratorMoveNext(iterator);
I am _very_ surprised that this is faster. How are three runtime calls faster
than one? Don't get me wrong, I trust your measurements, but is this a good
optimization in the long run?

[arv (Not doing code reviews), 2014-06-23 20:31:52]

In the long run we should find a way to optimize away objects that are directly
used with destructuring.

We've also done experiments with self hosted Map and Set which looked like it
would have had large payoff, especially for forEach but our results have been
pretty disappointing.

https://codereview.chromium.org/329253004/diff/90001/src/collection.js
File src/collection.js (right):

https://codereview.chromium.org/329253004/diff/90001/src/collection.js#newcode87
src/collection.js:87: %SetIteratorMoveNext(iterator);
On 2014/06/23 19:51:52, Michael Starzinger wrote:
> I am _very_ surprised that this is faster. How are three runtime calls faster
> than one? Don't get me wrong, I trust your measurements, but is this a good
> optimization in the long run?

The cost of 1 call vs 3 calls is not so large. Since we have 1 this code does
not get optimized so we are already paying the overhead of runtime calls, this
just makes that overhead 3x larger (same order of magnitude).

The main reason why this is faster is that creating the iterator result object
and then extracting the data is a lot of overhead. For Map.prototype.forEach we
also had to create temporary array and extract that data from that too.

[danno, 2014-06-23 20:47:27]

On 2014/06/23 19:51:52, Michael Starzinger wrote:
> Handing off to either Andreas or Danno.
> 
> https://codereview.chromium.org/329253004/diff/90001/src/collection.js
> File src/collection.js (right):
> 
>
https://codereview.chromium.org/329253004/diff/90001/src/collection.js#newcode87
> src/collection.js:87: %SetIteratorMoveNext(iterator);
> I am _very_ surprised that this is faster. How are three runtime calls faster
> than one? Don't get me wrong, I trust your measurements, but is this a good
> optimization in the long run?

NOT LGTM

Replacing one runtime function with three might provide a win in some situations
(how did you measure it?), but I am a concerned that this is not the way to go
if you are wanting to optimize this for the long run. If you really want a fast
implementation, you long-term aim should be to remove the runtime call
altogether (which is possible, e.g. with a Hydrogen stub, but obviously more
work). Your proposed solution relies too much on C++ machinery in order to make
forEach faster and moves further away from the ideal solution, so it doesn't
really match current v8 practice.

What exactly is causing the existing function to be slow? Did you measure it? Is
it the allocation for every iteration? Or something else?

If it's the allocation, I can think of another, simpler ways to improve this.
For example, this particular use case doesn't expose the entry object
externally, so a _much_ faster approach is to turn %XXXIteratorNext into
%XXXIteratorNextObject (or whatever appropriate name) that either returns the
next object, or a special sentinel for done. You can call that new version
directly from the forEach implementation, removing all allocation and doing the
job with only a single runtime function. 

If you do it right, I think you might be able get rid of the nastiness with the
special casing of the entry object and its map in the runtime, turning the
creating of the externally-visible entry into pure JS something like this: 

function SetIteratorNext() { 
  var next = %SetIteratorNextObject();
  var is_done = next == __some_sentinel;
  return { value: (is_done ? undefined  : next), done: is_done }
}

[arv (Not doing code reviews), 2014-06-23 21:00:04]

On 2014/06/23 at 20:47:27, danno wrote:
> On 2014/06/23 19:51:52, Michael Starzinger wrote:
> > Handing off to either Andreas or Danno.
> > 
> > https://codereview.chromium.org/329253004/diff/90001/src/collection.js
> > File src/collection.js (right):
> > 
> >
https://codereview.chromium.org/329253004/diff/90001/src/collection.js#newcode87
> > src/collection.js:87: %SetIteratorMoveNext(iterator);
> > I am _very_ surprised that this is faster. How are three runtime calls
faster
> > than one? Don't get me wrong, I trust your measurements, but is this a good
> > optimization in the long run?
> 
> NOT LGTM
> 
> Replacing one runtime function with three might provide a win in some
situations (how did you measure it?),

Using the tests that we added to golem

> but I am a concerned that this is not the way to go if you are wanting to
optimize this for the long run. If you really want a fast implementation, you
long-term aim should be to remove the runtime call altogether (which is
possible, e.g. with a Hydrogen stub, but obviously more work).

We have explored this path. There was a concern that we should not write
hydrogen for too specialized code. And I also wrote a self hosted version of Map
and Set where the only runtime call was to get the hash code. This, however
turned out to be a lot slower so it was decided not to pursue this path for now.

> Your proposed solution relies too much on C++ machinery in order to make
forEach faster and moves further away from the ideal solution, so it doesn't
really match current v8 practice.
> 
> What exactly is causing the existing function to be slow? Did you measure it?
Is it the allocation for every iteration? Or something else?

> If it's the allocation, I can think of another, simpler ways to improve this.
For example, this particular use case doesn't expose the entry object
externally, so a _much_ faster approach is to turn %XXXIteratorNext into
%XXXIteratorNextObject (or whatever appropriate name) that either returns the
next object, or a special sentinel for done. You can call that new version
directly from the forEach implementation, removing all allocation and doing the
job with only a single runtime function. 
> 
> If you do it right, I think you might be able get rid of the nastiness with
the special casing of the entry object and its map in the runtime, turning the
creating of the externally-visible entry into pure JS something like this: 
> 
> function SetIteratorNext() { 
>   var next = %SetIteratorNextObject();
>   var is_done = next == __some_sentinel;
>   return { value: (is_done ? undefined  : next), done: is_done }
> }

Thanks for the feedback Danno. Much appreciated.

The sentinel solution works for Set.prototype.forEach but not for
Map.prototype.forEach which needs both key and value.

[danno, 2014-06-23 22:04:39]

On 2014/06/23 21:00:04, arv wrote:
> On 2014/06/23 at 20:47:27, danno wrote:
> > On 2014/06/23 19:51:52, Michael Starzinger wrote:
> > > Handing off to either Andreas or Danno.
> > > 
> > > https://codereview.chromium.org/329253004/diff/90001/src/collection.js
> > > File src/collection.js (right):
> > > 
> > >
>
https://codereview.chromium.org/329253004/diff/90001/src/collection.js#newcode87
> > > src/collection.js:87: %SetIteratorMoveNext(iterator);
> > > I am _very_ surprised that this is faster. How are three runtime calls
> faster
> > > than one? Don't get me wrong, I trust your measurements, but is this a
good
> > > optimization in the long run?
> > 
> > NOT LGTM
> > 
> > Replacing one runtime function with three might provide a win in some
> situations (how did you measure it?),
> 
> Using the tests that we added to golem
> 
> > but I am a concerned that this is not the way to go if you are wanting to
> optimize this for the long run. If you really want a fast implementation, you
> long-term aim should be to remove the runtime call altogether (which is
> possible, e.g. with a Hydrogen stub, but obviously more work).
> 
> We have explored this path. There was a concern that we should not write
> hydrogen for too specialized code. And I also wrote a self hosted version of
Map
> and Set where the only runtime call was to get the hash code. This, however
> turned out to be a lot slower so it was decided not to pursue this path for
now.

I am not sure if the concern is with hydrogen stubs in general for optimization
here, I would rather frame it this way: code generation is not a very subtle
tool and should be used sparingly and as the final step in the optimization
process. Before you consider Hydrogen stub generation, the other bottlenecks
should be reduced and massaged so that when the last little bit needs to be
squeezed out with code generation, it can be done minimally intrusively. Given
we just started with the optimization process, let's focus on the low-hanging
fruits first (as you have conceptually done), but not design out the path to the
high-hanging ones like Hydrogen stubs eventually. The means incrementally
teasing out more and more functionality of the native runtime call in JavaScript
(which get's turned into highly optimized code via Crankshaft "for free") so
that the code that remains in C++ is easy and concise  to implement in Hydrogen.


> 
> > Your proposed solution relies too much on C++ machinery in order to make
> forEach faster and moves further away from the ideal solution, so it doesn't
> really match current v8 practice.
> > 
> > What exactly is causing the existing function to be slow? Did you measure
it?
> Is it the allocation for every iteration? Or something else?
> 
> > If it's the allocation, I can think of another, simpler ways to improve
this.
> For example, this particular use case doesn't expose the entry object
> externally, so a _much_ faster approach is to turn %XXXIteratorNext into
> %XXXIteratorNextObject (or whatever appropriate name) that either returns the
> next object, or a special sentinel for done. You can call that new version
> directly from the forEach implementation, removing all allocation and doing
the
> job with only a single runtime function. 
> > 
> > If you do it right, I think you might be able get rid of the nastiness with
> the special casing of the entry object and its map in the runtime, turning the
> creating of the externally-visible entry into pure JS something like this: 
> > 
> > function SetIteratorNext() { 
> >   var next = %SetIteratorNextObject();
> >   var is_done = next == __some_sentinel;
> >   return { value: (is_done ? undefined  : next), done: is_done }
> > }
> 
> Thanks for the feedback Danno. Much appreciated.
> 
> The sentinel solution works for Set.prototype.forEach but not for
> Map.prototype.forEach which needs both key and value.

Yes, but consider this variant of that approach:

function MapIteratorNext() { 
  var entry = { key: undefined, value: undefined, done: false };
  %MapIteratorNextWithEntry(iterator, entry);
}

In the forEach case, you can allocate a single entry and pass it into multiple
calls of the %MapIteratorNextWithEntry, reducing the overhead (one allocation
vs. n)

[danno, 2014-06-23 23:25:45]

On 2014/06/23 22:04:39, danno wrote:
> On 2014/06/23 21:00:04, arv wrote:
> > On 2014/06/23 at 20:47:27, danno wrote:
> > > On 2014/06/23 19:51:52, Michael Starzinger wrote:
> > > > Handing off to either Andreas or Danno.
> > > > 
> > > > https://codereview.chromium.org/329253004/diff/90001/src/collection.js
> > > > File src/collection.js (right):
> > > > 
> > > >
> >
>
https://codereview.chromium.org/329253004/diff/90001/src/collection.js#newcode87
> > > > src/collection.js:87: %SetIteratorMoveNext(iterator);
> > > > I am _very_ surprised that this is faster. How are three runtime calls
> > faster
> > > > than one? Don't get me wrong, I trust your measurements, but is this a
> good
> > > > optimization in the long run?
> > > 
> > > NOT LGTM
> > > 
> > > Replacing one runtime function with three might provide a win in some
> > situations (how did you measure it?),
> > 
> > Using the tests that we added to golem
> > 
> > > but I am a concerned that this is not the way to go if you are wanting to
> > optimize this for the long run. If you really want a fast implementation,
you
> > long-term aim should be to remove the runtime call altogether (which is
> > possible, e.g. with a Hydrogen stub, but obviously more work).
> > 
> > We have explored this path. There was a concern that we should not write
> > hydrogen for too specialized code. And I also wrote a self hosted version of
> Map
> > and Set where the only runtime call was to get the hash code. This, however
> > turned out to be a lot slower so it was decided not to pursue this path for
> now.
> 
> I am not sure if the concern is with hydrogen stubs in general for
optimization
> here, I would rather frame it this way: code generation is not a very subtle
> tool and should be used sparingly and as the final step in the optimization
> process. Before you consider Hydrogen stub generation, the other bottlenecks
> should be reduced and massaged so that when the last little bit needs to be
> squeezed out with code generation, it can be done minimally intrusively. Given
> we just started with the optimization process, let's focus on the low-hanging
> fruits first (as you have conceptually done), but not design out the path to
the
> high-hanging ones like Hydrogen stubs eventually. The means incrementally
> teasing out more and more functionality of the native runtime call in
JavaScript
> (which get's turned into highly optimized code via Crankshaft "for free") so
> that the code that remains in C++ is easy and concise  to implement in
Hydrogen.
> 
> 
> > 
> > > Your proposed solution relies too much on C++ machinery in order to make
> > forEach faster and moves further away from the ideal solution, so it doesn't
> > really match current v8 practice.
> > > 
> > > What exactly is causing the existing function to be slow? Did you measure
> it?
> > Is it the allocation for every iteration? Or something else?
> > 
> > > If it's the allocation, I can think of another, simpler ways to improve
> this.
> > For example, this particular use case doesn't expose the entry object
> > externally, so a _much_ faster approach is to turn %XXXIteratorNext into
> > %XXXIteratorNextObject (or whatever appropriate name) that either returns
the
> > next object, or a special sentinel for done. You can call that new version
> > directly from the forEach implementation, removing all allocation and doing
> the
> > job with only a single runtime function. 
> > > 
> > > If you do it right, I think you might be able get rid of the nastiness
with
> > the special casing of the entry object and its map in the runtime, turning
the
> > creating of the externally-visible entry into pure JS something like this: 
> > > 
> > > function SetIteratorNext() { 
> > >   var next = %SetIteratorNextObject();
> > >   var is_done = next == __some_sentinel;
> > >   return { value: (is_done ? undefined  : next), done: is_done }
> > > }
> > 
> > Thanks for the feedback Danno. Much appreciated.
> > 
> > The sentinel solution works for Set.prototype.forEach but not for
> > Map.prototype.forEach which needs both key and value.
> 
> Yes, but consider this variant of that approach:
> 
> function MapIteratorNext() { 
>   var entry = { key: undefined, value: undefined, done: false };
>   %MapIteratorNextWithEntry(iterator, entry);
> }
> 
> In the forEach case, you can allocate a single entry and pass it into multiple
> calls of the %MapIteratorNextWithEntry, reducing the overhead (one allocation
> vs. n)

Interesting, but that doesn't settle it, there's deeper digging that needs to be
done. The next thing to do is to determine exactly where the time is going in
the single runtime call. Without the allocation, the raw computation needed to
calculate the result for the single-call and three-call versions should be the
same, I suspect the discrepancy is coming from something non-obvious. 

Can you please run the benchmark with the perf tool on linux?

tools/run-llprof.sh out/ia32.release/d8 your_benchmark.js 

then use 

tools/ll_prof.py

to get a list the hotspots

[danno, 2014-06-24 16:54:00]

On 2014/06/23 23:25:45, danno wrote:
> On 2014/06/23 22:04:39, danno wrote:
> > On 2014/06/23 21:00:04, arv wrote:
> > > On 2014/06/23 at 20:47:27, danno wrote:
> > > > On 2014/06/23 19:51:52, Michael Starzinger wrote:
> > > > > Handing off to either Andreas or Danno.
> > > > > 
> > > > > https://codereview.chromium.org/329253004/diff/90001/src/collection.js
> > > > > File src/collection.js (right):
> > > > > 
> > > > >
> > >
> >
>
https://codereview.chromium.org/329253004/diff/90001/src/collection.js#newcode87
> > > > > src/collection.js:87: %SetIteratorMoveNext(iterator);
> > > > > I am _very_ surprised that this is faster. How are three runtime calls
> > > faster
> > > > > than one? Don't get me wrong, I trust your measurements, but is this a
> > good
> > > > > optimization in the long run?
> > > > 
> > > > NOT LGTM
> > > > 
> > > > Replacing one runtime function with three might provide a win in some
> > > situations (how did you measure it?),
> > > 
> > > Using the tests that we added to golem
> > > 
> > > > but I am a concerned that this is not the way to go if you are wanting
to
> > > optimize this for the long run. If you really want a fast implementation,
> you
> > > long-term aim should be to remove the runtime call altogether (which is
> > > possible, e.g. with a Hydrogen stub, but obviously more work).
> > > 
> > > We have explored this path. There was a concern that we should not write
> > > hydrogen for too specialized code. And I also wrote a self hosted version
of
> > Map
> > > and Set where the only runtime call was to get the hash code. This,
however
> > > turned out to be a lot slower so it was decided not to pursue this path
for
> > now.
> > 
> > I am not sure if the concern is with hydrogen stubs in general for
> optimization
> > here, I would rather frame it this way: code generation is not a very subtle
> > tool and should be used sparingly and as the final step in the optimization
> > process. Before you consider Hydrogen stub generation, the other bottlenecks
> > should be reduced and massaged so that when the last little bit needs to be
> > squeezed out with code generation, it can be done minimally intrusively.
Given
> > we just started with the optimization process, let's focus on the
low-hanging
> > fruits first (as you have conceptually done), but not design out the path to
> the
> > high-hanging ones like Hydrogen stubs eventually. The means incrementally
> > teasing out more and more functionality of the native runtime call in
> JavaScript
> > (which get's turned into highly optimized code via Crankshaft "for free") so
> > that the code that remains in C++ is easy and concise  to implement in
> Hydrogen.
> > 
> > 
> > > 
> > > > Your proposed solution relies too much on C++ machinery in order to make
> > > forEach faster and moves further away from the ideal solution, so it
doesn't
> > > really match current v8 practice.
> > > > 
> > > > What exactly is causing the existing function to be slow? Did you
measure
> > it?
> > > Is it the allocation for every iteration? Or something else?
> > > 
> > > > If it's the allocation, I can think of another, simpler ways to improve
> > this.
> > > For example, this particular use case doesn't expose the entry object
> > > externally, so a _much_ faster approach is to turn %XXXIteratorNext into
> > > %XXXIteratorNextObject (or whatever appropriate name) that either returns
> the
> > > next object, or a special sentinel for done. You can call that new version
> > > directly from the forEach implementation, removing all allocation and
doing
> > the
> > > job with only a single runtime function. 
> > > > 
> > > > If you do it right, I think you might be able get rid of the nastiness
> with
> > > the special casing of the entry object and its map in the runtime, turning
> the
> > > creating of the externally-visible entry into pure JS something like this:

> > > > 
> > > > function SetIteratorNext() { 
> > > >   var next = %SetIteratorNextObject();
> > > >   var is_done = next == __some_sentinel;
> > > >   return { value: (is_done ? undefined  : next), done: is_done }
> > > > }
> > > 
> > > Thanks for the feedback Danno. Much appreciated.
> > > 
> > > The sentinel solution works for Set.prototype.forEach but not for
> > > Map.prototype.forEach which needs both key and value.
> > 
> > Yes, but consider this variant of that approach:
> > 
> > function MapIteratorNext() { 
> >   var entry = { key: undefined, value: undefined, done: false };
> >   %MapIteratorNextWithEntry(iterator, entry);
> > }
> > 
> > In the forEach case, you can allocate a single entry and pass it into
multiple
> > calls of the %MapIteratorNextWithEntry, reducing the overhead (one
allocation
> > vs. n)
> 
> Interesting, but that doesn't settle it, there's deeper digging that needs to
be
> done. The next thing to do is to determine exactly where the time is going in
> the single runtime call. Without the allocation, the raw computation needed to
> calculate the result for the single-call and three-call versions should be the
> same, I suspect the discrepancy is coming from something non-obvious. 
> 
> Can you please run the benchmark with the perf tool on linux?
> 
> tools/run-llprof.sh out/ia32.release/d8 your_benchmark.js 
> 
> then use 
> 
> tools/ll_prof.py
> 
> to get a list the hotspots

Ah. I think I know what's going on. 

The reason your new Map iterator is slow--granted, this is speculation not
having seen your code--is that I suspect now you pass in the entry object all
the way down to NewIteratorResultObject (or some new equivalent), and then you
call SetProperty on that object, which has to do expensive property lookups each
time you set the property.

Looking at the code, however, I am confused why the Map iterator needs to be any
different than the Set iterator with respect to optimizations, since the
ValueForKind utility called by Next works in exactly the same way. It looks like
for both the Set and Map iterators, the entry is still always of the form {
value: XXXX, done: XXXX }, but values has a different form depending on whether
one is iterating keys, values or entries. if you are iterating entries, then the
entry takes the form { value: [key, actual_value], done: XXX }. Which means that
I don't understand why you can't use the trick that I originally proposed, i.e.
the %SetIteratorNextObject/%MapIteratorNextObject return the "value" property
from the runtime function, either the key, the value, the array [key, value] or
the done sentinel.

This will avoid all the property lookups in the native code that you are
currently doing on entry objects: the value store to the entry object in JS will
use an IC and therefore will be quite fast.

[arv (Not doing code reviews), 2014-06-24 22:40:24]

I'm closing this CL in favor of https://codereview.chromium.org/355663002/