Refactored iterative map traversal.

Refactored iterative map traversal.

The main goal is to cleanly separate between the several parts involved in the traversal:

 * iterating over all transitions in a descriptor array

 * iterating over all prototype transitions

 * storing the parent and the current local traversal position in a map

 * the iterative traversal algorithm itself

The previous algorithm for iterating over prototype transitions did a little bit too much here, iterating over the whole array instead only the filled part. This has been fixed on the way, too.

With this CL, it will be much easier to make the necessary changes to the descriptor array iterator to correctly handle map transitions for accessor properties. Furthermore, perhaps we represent transitions a bit different in the future, making finding them a bit easier. This would make some code in this CL (and elsewhere) quite a bit shorter and more efficient.

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

[Sven Panne, 2012-01-19 14:03:45]

Fully implemented and commented now, PTAL.

[Vyacheslav Egorov (Chromium), 2012-01-20 12:04:54]

https://chromiumcodereview.appspot.com/9252007/diff/3001/src/objects.cc
File src/objects.cc (right):

https://chromiumcodereview.appspot.com/9252007/diff/3001/src/objects.cc#newco...
src/objects.cc:4947: bool IsRunning() {
I find the name confusing because descriptor itself is not running anywhere it's
the process of iteration that is running.

https://chromiumcodereview.appspot.com/9252007/diff/3001/src/objects.cc#newco...
src/objects.cc:4983: class IterablePrototypeTransitions : public FixedArray {
I think parts IterableDescriptorArray & IterablePrototypeTransitions that are
responsible for storing iteration index and ending iteration can be factored out
into something like IterableFixedArray.

The name is a bit confusing though. I would call it IntrusiveIterator or
something like that and i don't think it has to inherit from FixedArray itself
(the same applies for Map).

How about:
class IntrusiveFixedArrayIterator {
 public:
  IntrusiveFixedArrayIterator(FixedArray* array) : array_(array) {}

  void Start();  // store initial iteration state into the object
  bool IsIterating();  // return true if object contains iteration state
  int GetIndex();
  int SetIndex();
  void Stop();  // remove iteration state from the object

 private:
  FixedArray* array;
};

class IntrusiveMapIterator {
 public:
  IntrusiveMapIterator(Map* map) : map_(map) {}

  // Start map iteration. Store iteration state and parent in the map.
  void Start(Map* parent) {
    if (something)
IntrusiveFixedArrayIterator(map_->instance_descriptors()).Start();
    if (something_else)
IntrusiveFixedArrayIterator(map_->prototype_transitions()).Start();
  }

  Map* Next() {
    IntrusiveFixedArrayIterator descriptors_it (map_->instance_descriptors());
    if (descriptors_it.IsRunning()) {
      int idx = descriptors_it.GetIndex();
      // see if we can advance
      // ...
    }
  }

  bool IsIterating();

  // Remove map iteration state from the map and return parent that was stored
there.
  Map* Stop();
};

https://chromiumcodereview.appspot.com/9252007/diff/3001/src/objects.cc#newco...
src/objects.cc:5096: //   (1) Implement the recursive textbook algorithm for
visiting a tree.
I don't think these 4 steps make algorithm any clearer than it is already they
just confuse.

https://chromiumcodereview.appspot.com/9252007/diff/3001/src/objects.cc#newco...
src/objects.cc:5110: while (true) {
can it be changed into do { } while (current != metamap) to avoid having break
in the middle of the if?

https://chromiumcodereview.appspot.com/9252007/diff/3001/src/objects.cc#newco...
src/objects.cc:5111: IterableMap* child = current->childIteratorNext();
I think it might be more clear to have descendIntoNextChild() which would also
do childIteratorStart and will setParent appropriately.

[Sven Panne, 2012-01-20 13:15:32]

https://chromiumcodereview.appspot.com/9252007/diff/3001/src/objects.cc
File src/objects.cc (right):

https://chromiumcodereview.appspot.com/9252007/diff/3001/src/objects.cc#newco...
src/objects.cc:4947: bool IsRunning() {
On 2012/01/20 12:04:54, Vyacheslav Egorov wrote:
> I find the name confusing because descriptor itself is not running anywhere
it's
> the process of iteration that is running.

If we really wanted to be clean, we should introduce a pure abstract class
(a.k.a. interface) for the iterator here, with 3 methods Start/IsRunning/Next.
IterableDescriptorArray, IterablePrototypeTransitions and IterableMap would all
inherit from this, so the names would be just right. But we had discussions
about multiple inheritance before, and I wanted to avoid re-joining that battle.

Which name would you prefer? IsIterating?

https://chromiumcodereview.appspot.com/9252007/diff/3001/src/objects.cc#newco...
src/objects.cc:4983: class IterablePrototypeTransitions : public FixedArray {
On 2012/01/20 12:04:54, Vyacheslav Egorov wrote:
> I think parts IterableDescriptorArray & IterablePrototypeTransitions that are
> responsible for storing iteration index and ending iteration can be factored
out
> into something like IterableFixedArray. [...]

There are several reasons why I would prefer to avoid the introduction of a
class like IntrusiveFixedArrayIterator:

 * It is by pure accident that the descriptor array and the prototype
transitions are fixed arrays, both (ab)used in "interesting" ways. In a better
world with nicer types and more compile time safety, which we might have not too
far into the future, neither of these would be a fixed array. We are using
FixedArrays far too often already, and I would really like to steer away from
that.

 * Using the IntrusiveFixedArrayIterator constructor plus the array field is
basically just hiding an explicit cast and cheating about the fact that the
iterator and the object it is iterating over are not independent at all. Because
of this (inherent) dependence, I think deriving the iterator from the object is
exactly the right thing to do, as strange  as it might initially look.

https://chromiumcodereview.appspot.com/9252007/diff/3001/src/objects.cc#newco...
src/objects.cc:5096: //   (1) Implement the recursive textbook algorithm for
visiting a tree.
On 2012/01/20 12:04:54, Vyacheslav Egorov wrote:
> I don't think these 4 steps make algorithm any clearer than it is already they
> just confuse.

I can easily live without the comment, but this would really set a precedent:
Removing one of the rare correct comments from v8's source code... ;-)

https://chromiumcodereview.appspot.com/9252007/diff/3001/src/objects.cc#newco...
src/objects.cc:5110: while (true) {
On 2012/01/20 12:04:54, Vyacheslav Egorov wrote:
> can it be changed into do { } while (current != metamap) to avoid having break
> in the middle of the if?

I would prefer to leave it as it is, because using meta_map here would break the
abstraction between this traversal algorithm and the map iterator and the change
wouldn't really improve things.

https://chromiumcodereview.appspot.com/9252007/diff/3001/src/objects.cc#newco...
src/objects.cc:5111: IterableMap* child = current->childIteratorNext();
On 2012/01/20 12:04:54, Vyacheslav Egorov wrote:
> I think it might be more clear to have descendIntoNextChild() which would also
> do childIteratorStart and will setParent appropriately.

I think merging those calls together will make things actually worse: The
current code is very explicit about when to move "horizontally" in the tree and
when to move "vertically". Merging doesn't really gain anything and will break
the nice explicit symmetry.

[Vyacheslav Egorov (Chromium), 2012-01-20 13:59:50]

https://chromiumcodereview.appspot.com/9252007/diff/3001/src/objects.cc
File src/objects.cc (right):

https://chromiumcodereview.appspot.com/9252007/diff/3001/src/objects.cc#newco...
src/objects.cc:4947: bool IsRunning() {
On 2012/01/20 13:15:33, Sven wrote:
> On 2012/01/20 12:04:54, Vyacheslav Egorov wrote:
> > I find the name confusing because descriptor itself is not running anywhere
> it's
> > the process of iteration that is running.
> 
> If we really wanted to be clean, we should introduce a pure abstract class
> (a.k.a. interface) for the iterator here, with 3 methods Start/IsRunning/Next.
> IterableDescriptorArray, IterablePrototypeTransitions and IterableMap would
all
> inherit from this, so the names would be just right. But we had discussions
> about multiple inheritance before, and I wanted to avoid re-joining that
battle.
> 
> Which name would you prefer? IsIterating?

IsIterating sounds fine.

https://chromiumcodereview.appspot.com/9252007/diff/3001/src/objects.cc#newco...
src/objects.cc:4983: class IterablePrototypeTransitions : public FixedArray {
* Yes, it is a pure accident that both are fixed arrays. But _currently_ they
are fixed arrays and I see no benefit in not sharing code. Actually I think it's
more likely that we would merge prototype transitions into all other transitions
 than that we would change the type of descriptor array and leave prototype
transitions intact.

* It's inheritance vs. aggregation. If you inherit Iterator from the FixedArray
it makes one think that Iterator is going to act (and to be used) AS FixedArray
which is largely irrelevant. Iterator does not act as FixedArray. Iterator is
not FixedArray. Iterator just builds some iteration logic externally to the
FixedArray and uses FixedArray to store it's iteration state. I think
aggregation shows it much more clearly. I might be wrong, but I strongly favor
aggregation in this particular case.


On 2012/01/20 13:15:33, Sven wrote:
> On 2012/01/20 12:04:54, Vyacheslav Egorov wrote:
> > I think parts IterableDescriptorArray & IterablePrototypeTransitions that
are
> > responsible for storing iteration index and ending iteration can be factored
> out
> > into something like IterableFixedArray. [...]
> 
> There are several reasons why I would prefer to avoid the introduction of a
> class like IntrusiveFixedArrayIterator:
> 
>  * It is by pure accident that the descriptor array and the prototype
> transitions are fixed arrays, both (ab)used in "interesting" ways. In a better
> world with nicer types and more compile time safety, which we might have not
too
> far into the future, neither of these would be a fixed array. We are using
> FixedArrays far too often already, and I would really like to steer away from
> that.
> 
>  * Using the IntrusiveFixedArrayIterator constructor plus the array field is
> basically just hiding an explicit cast and cheating about the fact that the
> iterator and the object it is iterating over are not independent at all.
Because
> of this (inherent) dependence, I think deriving the iterator from the object
is
> exactly the right thing to do, as strange  as it might initially look.

https://chromiumcodereview.appspot.com/9252007/diff/3001/src/objects.cc#newco...
src/objects.cc:5096: //   (1) Implement the recursive textbook algorithm for
visiting a tree.
On 2012/01/20 13:15:33, Sven wrote:
> On 2012/01/20 12:04:54, Vyacheslav Egorov wrote:
> > I don't think these 4 steps make algorithm any clearer than it is already
they
> > just confuse.
> 
> I can easily live without the comment, but this would really set a precedent:
> Removing one of the rare correct comments from v8's source code... ;-)

I agree that this comment is absolutely correct, and will be useful here. My
only concern was that it explains how to derive algorithm, not how to understand
what's happening below.

https://chromiumcodereview.appspot.com/9252007/diff/3001/src/objects.cc#newco...
src/objects.cc:5110: while (true) {
On 2012/01/20 13:15:33, Sven wrote:
> On 2012/01/20 12:04:54, Vyacheslav Egorov wrote:
> > can it be changed into do { } while (current != metamap) to avoid having
break
> > in the middle of the if?
> 
> I would prefer to leave it as it is, because using meta_map here would break
the
> abstraction between this traversal algorithm and the map iterator and the
change
> wouldn't really improve things.

It would streamline control-flow (I would read this loop as
while(we-still-have-maps-to-visit) { visit them }). Actually comparison with
metamap can be moved into iterator to keep this loop isolated for iterator
logic:

while (IntrusiveMapIterator(current).HasNext()) { }

where HasNext compares current with metamap.

https://chromiumcodereview.appspot.com/9252007/diff/3001/src/objects.cc#newco...
src/objects.cc:5111: IterableMap* child = current->childIteratorNext();
On 2012/01/20 13:15:33, Sven wrote:
> On 2012/01/20 12:04:54, Vyacheslav Egorov wrote:
> > I think it might be more clear to have descendIntoNextChild() which would
also
> > do childIteratorStart and will setParent appropriately.
> 
> I think merging those calls together will make things actually worse: The
> current code is very explicit about when to move "horizontally" in the tree
and
> when to move "vertically". Merging doesn't really gain anything and will break
> the nice explicit symmetry.

I have to agree that merging things together might make direction of our
movement less unclear.

[Sven Panne, 2012-01-20 14:54:50]

https://chromiumcodereview.appspot.com/9252007/diff/3001/src/objects.cc
File src/objects.cc (right):

https://chromiumcodereview.appspot.com/9252007/diff/3001/src/objects.cc#newco...
src/objects.cc:4983: class IterablePrototypeTransitions : public FixedArray {
On 2012/01/20 13:59:50, Vyacheslav Egorov wrote:
> * Yes, it is a pure accident that both are fixed arrays. But _currently_ they
> are fixed arrays and I see no benefit in not sharing code. 

What code would actually be shared? The structure of the descriptor array and
the prototype transitions are vastly different, the index has a different
meaning, the index is stored in different places, the Next method is completely
different (and will become even more so).

> Actually I think it's
> more likely that we would merge prototype transitions into all other
transitions
>  than that we would change the type of descriptor array and leave prototype
> transitions intact.

Actually my gut feeling is exactly the opposite, but what we will actually do
here will have a lot of implications and should be considered carefully in
detail later. Everything else is just wild guesses...

> * It's inheritance vs. aggregation. [...]

And that's exactly why I've chosen inheritance here: In general I'm very
strongly against implementation inheritance, delegation is far better most of
the time. But in our case the iterator IS-A FixedArray, the iterator does not
CONTAIN-A FixedArray, that's plainly wrong because they are one and the same.
Put another way, this inheritance makes it utterly clear what a big hack pointer
reversal is, namely merging two different structures together. :)

https://chromiumcodereview.appspot.com/9252007/diff/3001/src/objects.cc#newco...
src/objects.cc:5096: //   (1) Implement the recursive textbook algorithm for
visiting a tree.
On 2012/01/20 13:59:50, Vyacheslav Egorov wrote:
> On 2012/01/20 13:15:33, Sven wrote:
> > On 2012/01/20 12:04:54, Vyacheslav Egorov wrote:
> > > I don't think these 4 steps make algorithm any clearer than it is already
> they
> > > just confuse.
> > 
> > I can easily live without the comment, but this would really set a
precedent:
> > Removing one of the rare correct comments from v8's source code... ;-)
> 
> I agree that this comment is absolutely correct, and will be useful here. My
> only concern was that it explains how to derive algorithm, not how to
understand
> what's happening below.

Understanding the derivation of a non-trivial algorithm from a trivial one
normally helps me to understand the former one, but as I said: I'll happily
remove it and assume that everybody who later reads the code knows that this
code could be derived quite mechanically. :)

https://chromiumcodereview.appspot.com/9252007/diff/3001/src/objects.cc#newco...
src/objects.cc:5110: while (true) {
On 2012/01/20 13:59:50, Vyacheslav Egorov wrote:
> On 2012/01/20 13:15:33, Sven wrote:
> > On 2012/01/20 12:04:54, Vyacheslav Egorov wrote:
> > > can it be changed into do { } while (current != metamap) to avoid having
> break
> > > in the middle of the if?
> > 
> > I would prefer to leave it as it is, because using meta_map here would break
> the
> > abstraction between this traversal algorithm and the map iterator and the
> change
> > wouldn't really improve things.
> 
> It would streamline control-flow (I would read this loop as
> while(we-still-have-maps-to-visit) { visit them }). Actually comparison with
> metamap can be moved into iterator to keep this loop isolated for iterator
> logic:
> 
> while (IntrusiveMapIterator(current).HasNext()) { }
> 
> where HasNext compares current with metamap.

HasNext would complicate the currently easy iterator protocol and its
implementation: The current index could point to a non-transition, so one has to
search for the next transition and remember that to avoid repeating that work in
Next. Of course this could be factored out into a separate method, but the net
effect would reduce readability, not improve it.

Furthermore, having a loop with the exit in the middle is IMHO a common control
structure and has been proposed decades ago
(http://en.wikipedia.org/wiki/Control_flow#Loop_with_test_in_the_middle).
Current mainstream programming languages happily ignore this programmer need,
though...

[Vyacheslav Egorov (Chromium), 2012-01-20 16:30:10]

https://chromiumcodereview.appspot.com/9252007/diff/3001/src/objects.cc
File src/objects.cc (right):

https://chromiumcodereview.appspot.com/9252007/diff/3001/src/objects.cc#newco...
src/objects.cc:4983: class IterablePrototypeTransitions : public FixedArray {
On 2012/01/20 14:54:50, Sven wrote:
> On 2012/01/20 13:59:50, Vyacheslav Egorov wrote:
> > * Yes, it is a pure accident that both are fixed arrays. But _currently_
they
> > are fixed arrays and I see no benefit in not sharing code. 
> 
> What code would actually be shared? 

I outlined what I think can be shared in my intrusive-iterator proposal:

  void Start();
  bool IsIterating();
  int GetIndex();
  int SetIndex();
  void Stop();

In short: index storage and predicates like IsIterating can be shared.

> Everything else is just wild guesses...

Agreed.

> 
> > * It's inheritance vs. aggregation. [...]
> 
> And that's exactly why I've chosen inheritance here: In general I'm very
> strongly against implementation inheritance, delegation is far better most of
> the time. But in our case the iterator IS-A FixedArray, the iterator does not
> CONTAIN-A FixedArray, that's plainly wrong because they are one and the same.

I don't agree that they are one and the same. Iterator iterates. FixedArray does
not, it just exists in the heap and just happens to store some of the iterator's
state. And vice versa: iterator is not going to be used _as_ fixed array e.g.
code like:

FixedArray* normal_arr;
IterableFixedArray* it_arr;
normal_arr->set(0, it_arr);

has very little sense.

> Put another way, this inheritance makes it utterly clear what a big hack
pointer
> reversal is, namely merging two different structures together. :)

I think aggregation (together with appropriate name) also does it.

To make my suggestion more constructive I have sketched the code:
https://chromiumcodereview.appspot.com/9226017 (it runs and passes all tests).

https://chromiumcodereview.appspot.com/9252007/diff/3001/src/objects.cc#newco...
src/objects.cc:5051: void setParent(IterableMap* parent) {
set_map_no_write_barrier(parent); }
naming convention: first letter capital

https://chromiumcodereview.appspot.com/9252007/diff/3001/src/objects.cc#newco...
src/objects.cc:5054: IterableMap* getAndResetParent() {
naming convention: first letter capital

https://chromiumcodereview.appspot.com/9252007/diff/3001/src/objects.cc#newco...
src/objects.cc:5062: void childIteratorStart() {
naming convention: first letter capital

https://chromiumcodereview.appspot.com/9252007/diff/3001/src/objects.cc#newco...
src/objects.cc:5069: IterableMap* childIteratorNext() {
naming convention: first letter capital

https://chromiumcodereview.appspot.com/9252007/diff/3001/src/objects.cc#newco...
src/objects.cc:5110: while (true) {
On 2012/01/20 14:54:50, Sven wrote:
> On 2012/01/20 13:59:50, Vyacheslav Egorov wrote:
> > On 2012/01/20 13:15:33, Sven wrote:
> > > On 2012/01/20 12:04:54, Vyacheslav Egorov wrote:
> > > > can it be changed into do { } while (current != metamap) to avoid having
> > break
> > > > in the middle of the if?
> > > 
> > > I would prefer to leave it as it is, because using meta_map here would
break
> > the
> > > abstraction between this traversal algorithm and the map iterator and the
> > change
> > > wouldn't really improve things.
> > 
> > It would streamline control-flow (I would read this loop as
> > while(we-still-have-maps-to-visit) { visit them }). Actually comparison with
> > metamap can be moved into iterator to keep this loop isolated for iterator
> > logic:
> > 
> > while (IntrusiveMapIterator(current).HasNext()) { }
> > 
> > where HasNext compares current with metamap.
> 
> HasNext would complicate the currently easy iterator protocol and its
> implementation: The current index could point to a non-transition, so one has
to
> search for the next transition and remember that to avoid repeating that work
in
> Next. Of course this could be factored out into a separate method, but the net
> effect would reduce readability, not improve it.
> 
> Furthermore, having a loop with the exit in the middle is IMHO a common
control
> structure and has been proposed decades ago
> (http://en.wikipedia.org/wiki/Control_flow#Loop_with_test_in_the_middle).
> Current mainstream programming languages happily ignore this programmer need,
> though...

I consider loops with no special exits easier to read.

[Sven Panne, 2012-01-23 10:32:58]

I've removed the most controversial point, namely the inheritance of the
iterators for map/proto transitions. In addition, some renaming has been done.

PTAL

[Vyacheslav Egorov (Chromium), 2012-01-23 10:43:09]

lgtm

https://chromiumcodereview.appspot.com/9252007/diff/9001/src/objects.cc
File src/objects.cc (right):

https://chromiumcodereview.appspot.com/9252007/diff/9001/src/objects.cc#newco...
src/objects.cc:5066: class TraversableMap : public Map {
inheritance still.