ES6 Map/Set iterators/forEach improvements

ES6 Map/Set iterators/forEach improvements

This changes how Map/Set interacts with its iterators. When the
underlying table is rehashed or cleared, we create a new table (like
before) but we add a reference from the old table to the new table. We
also add an array describing how to transition the iterator from the
old table to the new table.

When Next is called on the iterator it checks if there is a newer table
that it should transition to. If there is, it updates the index based
on the previously recorded changes and finally changes itself to point
at the new table.

With these changes Map/Set no longer keeps the iterators alive. Also,
as before, the iterators keep the underlying table(s) alive but not the
actual Map/Set.

BUG=v8:1793
LOG=Y
R=mstarzinger@chromium.org, rossberg@chromium.org

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

[arv (Not doing code reviews), 2014-05-13 22:26:12]

Comment improvements

[arv (Not doing code reviews), 2014-05-13 22:27:42]

Thanks Andreas for all the help. This turned out to be a lot simpler than I
first anticipated.

[rossberg, 2014-05-14 12:13:46]

This looks good already. But I wonder if we can do even better and avoid
allocating the extra array for changes? It seems like it should be possible to
just reuse the existing data table slots for that. In particular, you are
guaranteed that the changes index moves slower than the old_entry index, so is
always less-or-equal to it. Hence you even should be able to read entries and
write changes in the same iteration.

https://codereview.chromium.org/289503002/diff/20001/src/objects.cc
File src/objects.cc (right):

https://codereview.chromium.org/289503002/diff/20001/src/objects.cc#newcode16513
src/objects.cc:16513: if (entry_index < index) {
Instead, you can break the loop when reaching 'index', which saves some time.

https://codereview.chromium.org/289503002/diff/20001/src/objects.h
File src/objects.h (right):

https://codereview.chromium.org/289503002/diff/20001/src/objects.h#newcode10026
src/objects.h:10026: Handle<TableType> TransitionIterator(Handle<TableType>
table);
Rename to just Transition (or Sync?).

Also, is this ever going to be called with anything other than this->table()? If
so, we should drop the parameter. Likewise for the result, actually -- just make
this void-to-void and call it in Next before even looking at table().

[arv (Not doing code reviews), 2014-05-14 13:55:46]

partial code review feedback update

[arv (Not doing code reviews), 2014-05-14 14:02:31]

On 2014/05/14 12:13:46, rossberg wrote:
> This looks good already. But I wonder if we can do even better and avoid
> allocating the extra array for changes? It seems like it should be possible to
> just reuse the existing data table slots for that. In particular, you are
> guaranteed that the changes index moves slower than the old_entry index, so is
> always less-or-equal to it. Hence you even should be able to read entries and
> write changes in the same iteration.

I see two potential problems with that approach:

1. Iterating through entire existing data table on transition is a lot more work
than only iterating through the holes. The question is what we want to optimize
for? I think that changes during iteration will be rare so this should not
happen often but add always creating the extra changes array on rehash will
happen often.

2. We still need a special signal for Clear.

Conclusion:

1. Remove the changes array
2. Add a single entry describing the changes. This be used for "clear" but it
could also be used for "no holes".

WDYT?

[arv (Not doing code reviews), 2014-05-14 14:02:38]

https://codereview.chromium.org/289503002/diff/20001/src/objects.cc
File src/objects.cc (right):

https://codereview.chromium.org/289503002/diff/20001/src/objects.cc#newcode16513
src/objects.cc:16513: if (entry_index < index) {
On 2014/05/14 12:13:46, rossberg wrote:
> Instead, you can break the loop when reaching 'index', which saves some time.

Done.

https://codereview.chromium.org/289503002/diff/20001/src/objects.h
File src/objects.h (right):

https://codereview.chromium.org/289503002/diff/20001/src/objects.h#newcode10026
src/objects.h:10026: Handle<TableType> TransitionIterator(Handle<TableType>
table);
On 2014/05/14 12:13:46, rossberg wrote:
> Rename to just Transition (or Sync?).
> 
> Also, is this ever going to be called with anything other than this->table()?
If
> so, we should drop the parameter. Likewise for the result, actually -- just
make
> this void-to-void and call it in Next before even looking at table().

The idea was to minimize read and writes but reading and writing the field
should be fast. I'll change it to void-to-void.

https://codereview.chromium.org/289503002/diff/20001/src/objects.h#newcode10026
src/objects.h:10026: Handle<TableType> TransitionIterator(Handle<TableType>
table);
On 2014/05/14 12:13:46, rossberg wrote:
> Rename to just Transition (or Sync?).
> 
> Also, is this ever going to be called with anything other than this->table()?
If
> so, we should drop the parameter. Likewise for the result, actually -- just
make
> this void-to-void and call it in Next before even looking at table().

Done.

[rossberg, 2014-05-14 14:23:31]

On 2014/05/14 14:02:31, arv wrote:
> On 2014/05/14 12:13:46, rossberg wrote:
> > This looks good already. But I wonder if we can do even better and avoid
> > allocating the extra array for changes? It seems like it should be possible
to
> > just reuse the existing data table slots for that. In particular, you are
> > guaranteed that the changes index moves slower than the old_entry index, so
is
> > always less-or-equal to it. Hence you even should be able to read entries
and
> > write changes in the same iteration.
> 
> I see two potential problems with that approach:
> 
> 1. Iterating through entire existing data table on transition is a lot more
work
> than only iterating through the holes. The question is what we want to
optimize
> for? I think that changes during iteration will be rare so this should not
> happen often but add always creating the extra changes array on rehash will
> happen often.

Sure, but what I meant is to still have the changes array, but store it over the
previous data table (which is no longer needed, and always large enough). And as
I tried to argue above, writing that should be possible to do within the same
loop that copies the entries over (i.e., the code remains almost the same).

I think we can also reuse one of the element count fields for the forward
pointer to the new table (i.e., the table is valid if that contains a smi, and
deprecated otherwise). The other count field could be recycled to hold the
number of change entries.

> 2. We still need a special signal for Clear.

That's easy as well, just use a sentinel value for the number of changes, i.e.,
-1.

Shouldn't that work? Everything would be just as efficient as now, but without
using extra space.

[rossberg, 2014-05-14 14:27:25]

https://codereview.chromium.org/289503002/diff/40001/src/objects.cc
File src/objects.cc (right):

https://codereview.chromium.org/289503002/diff/40001/src/objects.cc#newcode16513
src/objects.cc:16513: if (entry_index < index) {
You can simplify this slightly to

  if (entry_index >= index) break;
  --index;

[arv (Not doing code reviews), 2014-05-14 14:42:47]

On 2014/05/14 14:23:31, rossberg wrote:
> On 2014/05/14 14:02:31, arv wrote:
> > On 2014/05/14 12:13:46, rossberg wrote:
> > > This looks good already. But I wonder if we can do even better and avoid
> > > allocating the extra array for changes? It seems like it should be
possible
> to
> > > just reuse the existing data table slots for that. In particular, you are
> > > guaranteed that the changes index moves slower than the old_entry index,
so
> is
> > > always less-or-equal to it. Hence you even should be able to read entries
> and
> > > write changes in the same iteration.
> > 
> > I see two potential problems with that approach:
> > 
> > 1. Iterating through entire existing data table on transition is a lot more
> work
> > than only iterating through the holes. The question is what we want to
> optimize
> > for? I think that changes during iteration will be rare so this should not
> > happen often but add always creating the extra changes array on rehash will
> > happen often.
> 
> Sure, but what I meant is to still have the changes array, but store it over
the
> previous data table (which is no longer needed, and always large enough). And
as
> I tried to argue above, writing that should be possible to do within the same
> loop that copies the entries over (i.e., the code remains almost the same).

That makes sense.

> I think we can also reuse one of the element count fields for the forward
> pointer to the new table (i.e., the table is valid if that contains a smi, and
> deprecated otherwise). The other count field could be recycled to hold the
> number of change entries.

That too.

> > 2. We still need a special signal for Clear.
> 
> That's easy as well, just use a sentinel value for the number of changes,
i.e.,
> -1.
> 
> Shouldn't that work? Everything would be just as efficient as now, but without
> using extra space.

Thanks. That is indeed a more efficient solution. It is less clean but it is
surely worth it.

[arv (Not doing code reviews), 2014-05-14 16:25:37]

Store the removed indexes in the old table

[arv (Not doing code reviews), 2014-05-14 16:42:14]

Ready for review again

[arv (Not doing code reviews), 2014-05-14 16:42:48]

PTAL

[rossberg, 2014-05-14 17:21:36]

Looks pretty good now.

One thing: do we have tests for the edge cases? In particular, the case where
everything up to (and including) the iterator position is deleted, so that the
write is maximally close to the read in the loop.

https://codereview.chromium.org/289503002/diff/100001/src/objects.cc
File src/objects.cc (right):

https://codereview.chromium.org/289503002/diff/100001/src/objects.cc#newcode1...
src/objects.cc:16301: 
Add an assertion here that removed_holes_index == nod.

https://codereview.chromium.org/289503002/diff/100001/src/objects.cc#newcode1...
src/objects.cc:16518: index = 0;
At this point we can actually break the outer loop.

In fact, we can always do that when index becomes 0. Maybe simply add "index > 0
&&" to the while condition instead of inserting a break here.

https://codereview.chromium.org/289503002/diff/100001/src/objects.h
File src/objects.h (right):

https://codereview.chromium.org/289503002/diff/100001/src/objects.h#newcode4229
src/objects.h:4229: bool IsDeprecated() {
We have a concept of "deprecation" for maps, which is unrelated. Just to avoid
confusion, maybe we should use a different name here (e.g. IsOutdated or
IsRehashed).

https://codereview.chromium.org/289503002/diff/100001/src/objects.h#newcode4230
src/objects.h:4230: return !get(kNumberOfElementsIndex)->IsSmi();
We could define a separate constant for this (and other slots), that just alias
the one it's overlaying.

[arv (Not doing code reviews), 2014-05-14 17:50:53]

Rename and more

[arv (Not doing code reviews), 2014-05-14 17:51:23]

I'll expand on the tests. Make sure all code paths are covered.

https://codereview.chromium.org/289503002/diff/100001/src/objects.cc
File src/objects.cc (right):

https://codereview.chromium.org/289503002/diff/100001/src/objects.cc#newcode1...
src/objects.cc:16301: 
On 2014/05/14 17:21:36, rossberg wrote:
> Add an assertion here that removed_holes_index == nod.

Done.

https://codereview.chromium.org/289503002/diff/100001/src/objects.cc#newcode1...
src/objects.cc:16518: index = 0;
On 2014/05/14 17:21:36, rossberg wrote:
> At this point we can actually break the outer loop.

No. We need to update the table field to point to the newest table.

> In fact, we can always do that when index becomes 0. Maybe simply add "index >
0
> &&" to the while condition instead of inserting a break here.

I'll add an index == 0 check though.

https://codereview.chromium.org/289503002/diff/100001/src/objects.h
File src/objects.h (right):

https://codereview.chromium.org/289503002/diff/100001/src/objects.h#newcode4229
src/objects.h:4229: bool IsDeprecated() {
On 2014/05/14 17:21:36, rossberg wrote:
> We have a concept of "deprecation" for maps, which is unrelated. Just to avoid
> confusion, maybe we should use a different name here (e.g. IsOutdated or
> IsRehashed).

IsObsolete

https://codereview.chromium.org/289503002/diff/100001/src/objects.h#newcode4230
src/objects.h:4230: return !get(kNumberOfElementsIndex)->IsSmi();
On 2014/05/14 17:21:36, rossberg wrote:
> We could define a separate constant for this (and other slots), that just
alias
> the one it's overlaying.

Done.

[arv (Not doing code reviews), 2014-05-14 20:31:03]

Expanded tests and fixed edge case

[arv (Not doing code reviews), 2014-05-14 20:36:36]

PTAL

https://codereview.chromium.org/289503002/diff/140001/src/objects.cc
File src/objects.cc (right):

https://codereview.chromium.org/289503002/diff/140001/src/objects.cc#newcode1...
src/objects.cc:16244: if (nof >= (capacity >> 2)) return table;
Since kMinCapacity is 4 we end up with nof=1 not being enough to prevent a
shrink which lead us to shrink this to 2 which is not desirable.

Another option would be to do:

if (capacity == kMinCapacity || nof >= (capacity >> 2)) return table;

https://codereview.chromium.org/289503002/diff/140001/src/objects.cc#newcode1...
src/objects.cc:16527: if (removed_index >= old_index) break;
This was wrong before. We need to compare with the index before we decremented
index.

[rossberg, 2014-05-15 09:09:34]

The implementation looks good to go, but it would be preferable to also have
separate tests where

- the iterator ends up not having any next element anymore after the resync

- the new table ends up being entirely empty (but through individual deletes
only)

- a non-trivial transition chain with length > 1 is created (esp. one that does
not leave the iterator at index 0, i.e., does not involve clear)

[arv (Not doing code reviews), 2014-05-15 16:26:14]

Add more tests

[arv (Not doing code reviews), 2014-05-15 16:26:59]

Add more tests

[arv (Not doing code reviews), 2014-05-15 16:29:14]

On 2014/05/15 09:09:34, rossberg wrote:
> The implementation looks good to go, but it would be preferable to also have
> separate tests where
> 
> - the iterator ends up not having any next element anymore after the resync
> 
> - the new table ends up being entirely empty (but through individual deletes
> only)
> 
> - a non-trivial transition chain with length > 1 is created (esp. one that
does
> not leave the iterator at index 0, i.e., does not involve clear)

I added tests for these cases too. It was not easy to construct tests that hits
these cases so I instrumented my code to make sure I got into the desired state.

[Michael Starzinger, 2014-05-15 18:23:56]

LGTM on the implementation. I like this approach! I'll leave judgment of the
test coverage up to Andreas.

https://codereview.chromium.org/289503002/diff/180001/src/objects.h
File src/objects.h (right):

https://codereview.chromium.org/289503002/diff/180001/src/objects.h#newcode10036
src/objects.h:10036: void Transition();
nit: Can we have a short one-liner comment that this transitions the iterator to
the first non-obsolete backing store and is a NOP otherwise?

[arv (Not doing code reviews), 2014-05-15 18:33:45]

Add comment for Transition

[arv (Not doing code reviews), 2014-05-15 18:34:23]

Thanks Michael.

https://codereview.chromium.org/289503002/diff/180001/src/objects.h
File src/objects.h (right):

https://codereview.chromium.org/289503002/diff/180001/src/objects.h#newcode10036
src/objects.h:10036: void Transition();
On 2014/05/15 18:23:57, Michael Starzinger wrote:
> nit: Can we have a short one-liner comment that this transitions the iterator
to
> the first non-obsolete backing store and is a NOP otherwise?

Done.

[rossberg, 2014-05-16 16:10:18]

https://codereview.chromium.org/289503002/diff/200001/test/mjsunit/harmony/co...
File test/mjsunit/harmony/collections.js (right):

https://codereview.chromium.org/289503002/diff/200001/test/mjsunit/harmony/co...
test/mjsunit/harmony/collections.js:922: map.delete(v + 1);
If I read this correctly, this only ever deletes to the right of the iterator,
which means that it never needs to adjust to a different index. Can you tweak
the test such that the iterator actually has to change, preferably at each step
of the multi-transition?

[arv (Not doing code reviews), 2014-05-20 00:00:33]

Updated test

[arv (Not doing code reviews), 2014-05-20 00:16:25]

git rebase to fix merge conflict

[arv (Not doing code reviews), 2014-05-20 00:29:58]

PTAL

https://codereview.chromium.org/289503002/diff/200001/test/mjsunit/harmony/co...
File test/mjsunit/harmony/collections.js (right):

https://codereview.chromium.org/289503002/diff/200001/test/mjsunit/harmony/co...
test/mjsunit/harmony/collections.js:922: map.delete(v + 1);
On 2014/05/16 16:10:18, rossberg wrote:
> If I read this correctly, this only ever deletes to the right of the iterator,
> which means that it never needs to adjust to a different index. Can you tweak
> the test such that the iterator actually has to change, preferably at each
step
> of the multi-transition?

Changed this test. It now has a 4 iteration transition where it has to update
the index in 3 of those 4 transitions.

[rossberg, 2014-05-20 12:14:20]

Thanks, LGTM

[adamk, 2014-05-20 14:22:24]

Committed patchset #11 manually as r21389 (presubmit successful).