Optimize Map/Set.prototype.forEach

Optimize Map/Set.prototype.forEach

Instead of using an iterator result object and an entries array
(for Map) we introduce a new runtime function that uses an array
as an out param.

On the Map ForEach perf test this leads to a 2.5x performance
improvement. On the overall Map and Set tests this leads to a 18%
and 13% improvement respectively.


BUG=None
LOG=Y
R=danno@chromium.org

Committed: https://code.google.com/p/v8/source/detail?r=22027

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

Danno,

Since the MapIterator.prototype.next and SetIterator.prototype.next always needs
to generate a new array if the iterator kind is entries, and since we do not
know the kind we need on the JS side I ended up keeping the original Next()
method.

[danno, 2014-06-24 23:00:42]

On 2014/06/24 22:18:53, arv wrote:
> Danno,
> 
> Since the MapIterator.prototype.next and SetIterator.prototype.next always
needs
> to generate a new array if the iterator kind is entries, and since we do not
> know the kind we need on the JS side I ended up keeping the original Next()
> method.

I think you can still unify this with the next() implementation. Make
XXXNextForEach return an integer value { DONE = 0, KEY = 1,  VALUE = 2, ENTRY =
3 }. The forEach implementation stays essentially the same, simply checking for
0 rather than boolean true.

next() then looks something like this:

var entry = { value: [UNDEFINED, UNDEFINED], done: false };
switch (%XXXNextForEach(iterator, entry.value)) {
  case 0:
    entry.value = undefined;
    entry.done = true;
    return entry;
  case 1:
    entry.value = entry.value[0];
    return entry;
  case 2:
    entry.value = entry.value[1];
    return entry;
  case 3:
    return entry;
}

I suspect this will be much faster than allocating the entry in the runtime and
the array allocation will get folded into the entry literal allocation in
optimized code.

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

On 2014/06/24 at 23:00:42, danno wrote:
> I suspect this will be much faster than allocating the entry in the runtime
and the array allocation will get folded into the entry literal allocation in
optimized code.

That is good to know. So, even with the extra .value, it is preferred to put the
array in the object literal?

It would be good to get back to one runtime function again so it seems like a
good plan.

[danno, 2014-06-25 00:41:03]

On 2014/06/24 23:06:23, arv wrote:
> On 2014/06/24 at 23:00:42, danno wrote:
> > I suspect this will be much faster than allocating the entry in the runtime
> and the array allocation will get folded into the entry literal allocation in
> optimized code.
> 
> That is good to know. So, even with the extra .value, it is preferred to put
the
> array in the object literal?

You can separate it out and make it two literals, too, probably it's worth
micro-benchmarking to measure what's better, e.g. 

var value_array = [UNDEFINED, UNDEFINED];
var entry = { value: value_array, done: false };
...

Just make sure both allocations are done before the runtime call, otherwise they
can't be folded together (allocation folding will also work with separate
objects as long as we can prove there is no GC between).
 
> It would be good to get back to one runtime function again so it seems like a
> good plan.

[arv (Not doing code reviews), 2014-06-25 19:50:37]

Use same Next method for iterator next as well

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

Also get rid of NewIteratorResultObject since there are no more users of it

[arv (Not doing code reviews), 2014-06-25 20:13:45]

Cleanup

[arv (Not doing code reviews), 2014-06-25 20:17:54]

This is now ready for another review.

PTAL

https://codereview.chromium.org/355663002/diff/60001/src/collection-iterator.js
File src/collection-iterator.js (right):

https://codereview.chromium.org/355663002/diff/60001/src/collection-iterator....
src/collection-iterator.js:26: var entry = {value: value_array, done: false};
I benchmarked this and the following code has no noticeable performance
difference.

var entry = {value: [UNDEFINED, UNDEFINED], done: false};
var value_array = entry.value;

[danno, 2014-06-25 23:27:40]

I like this a lot. LGTM, I will land this for you. Thanks for the patch.

[danno, 2014-06-26 00:41:10]

Committed patchset #5 manually as r22027 (presubmit successful).