Refactored iterative map traversal.

src/objects.cc

Index: src/objects.cc
diff --git a/src/objects.cc b/src/objects.cc
index 0941e792f04e98f3391c5a8757da74902d74e21e..c4f87c4b91a738edb00d54fd7e64e1650b404293 100644
--- a/src/objects.cc
+++ b/src/objects.cc
@@ -4935,75 +4935,190 @@ void Map::RemoveFromCodeCache(String* name, Code* code, int index) {
 }
 
 
-void Map::TraverseTransitionTree(TraverseCallback callback, void* data) {
-  // Traverse the transition tree without using a stack.  We do this by
-  // reversing the pointers in the maps and descriptor arrays.
-  Map* current = this;
-  Map* meta_map = GetHeap()->meta_map();
-  Object** map_or_index_field = NULL;
-  while (current != meta_map) {
-    DescriptorArray* d = reinterpret_cast<DescriptorArray*>(
-        *RawField(current, Map::kInstanceDescriptorsOrBitField3Offset));
-    if (!d->IsEmpty()) {
-      FixedArray* contents = reinterpret_cast<FixedArray*>(
-          d->get(DescriptorArray::kContentArrayIndex));
-      map_or_index_field = RawField(contents, HeapObject::kMapOffset);
-      Object* map_or_index = *map_or_index_field;
-      bool map_done = true;  // Controls a nested continue statement.
-      for (int i = map_or_index->IsSmi() ? Smi::cast(map_or_index)->value() : 0;
-           i < contents->length();
-           i += 2) {
-        PropertyDetails details(Smi::cast(contents->get(i + 1)));
-        if (details.IsTransition()) {
-          // Found a map in the transition array.  We record our progress in
-          // the transition array by recording the current map in the map field
-          // of the next map and recording the index in the transition array in
-          // the map field of the array.
-          Map* next = Map::cast(contents->get(i));
-          next->set_map_no_write_barrier(current);
-          *map_or_index_field = Smi::FromInt(i + 2);
-          current = next;
-          map_done = false;
-          break;
-        }
-      }
-      if (!map_done) continue;
-    } else {
-      map_or_index_field = NULL;
-    }
-    // That was the regular transitions, now for the prototype transitions.
-    FixedArray* prototype_transitions =
-        current->unchecked_prototype_transitions();
-    Object** proto_map_or_index_field =
-        RawField(prototype_transitions, HeapObject::kMapOffset);
-    Object* map_or_index = *proto_map_or_index_field;
-    const int start = kProtoTransitionHeaderSize + kProtoTransitionMapOffset;
-    int i = map_or_index->IsSmi() ? Smi::cast(map_or_index)->value() : start;
-    if (i < prototype_transitions->length()) {
-      // Found a map in the prototype transition array.  Record progress in
-      // an analogous way to the regular transitions array above.
-      Object* perhaps_map = prototype_transitions->get(i);
-      if (perhaps_map->IsMap()) {
-        Map* next = Map::cast(perhaps_map);
-        next->set_map_no_write_barrier(current);
-        *proto_map_or_index_field =
-            Smi::FromInt(i + kProtoTransitionElementsPerEntry);
-        current = next;
-        continue;
+// An iterator over all map transitions in an descriptor array, reusing the map
+// field of the contens array while it is running.
+class IterableDescriptorArray : public DescriptorArray {
+ public:
+  void Start() {
+    ASSERT(!IsRunning());
+    if (HasContentArray()) *ContentHeader() = Smi::FromInt(0);
+  }
+
+  bool IsRunning() {

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

I find the name confusing because descriptor itself is not running anywhere it's
the process of iteration that is running.

[Sven Panne, 2012/01/20 13:15:33]

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?

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

IsIterating sounds fine.

+    return HasContentArray() && (*ContentHeader())->IsSmi();
+  }
+
+  Map* Next() {
+    ASSERT(IsRunning());
+    FixedArray* contents = ContentArray();
+    int index = Smi::cast(*ContentHeader())->value();
+    while (index < contents->length()) {
+      int next_index = index + 2;
+      PropertyDetails details(Smi::cast(contents->get(index + 1)));
+      if (details.IsTransition()) {
+        *ContentHeader() = Smi::FromInt(next_index);
+        return static_cast<Map*>(contents->get(index));
       }
+      index = next_index;
+    }
+    *ContentHeader() = GetHeap()->fixed_array_map();
+    return NULL;
+  }
+
+ private:
+  bool HasContentArray() { return length() > kContentArrayIndex; }
+
+  FixedArray* ContentArray() {
+    return static_cast<FixedArray*>(get(kContentArrayIndex));
+  }
+
+  Object** ContentHeader() {
+    return RawField(ContentArray(), kMapOffset);
+  }
+};
+
+
+// An iterator over all prototype transitions, reusing the map field of the
+// underlying array while it is running.
+class IterablePrototypeTransitions : public FixedArray {

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

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();
};

[Sven Panne, 2012/01/20 13:15:33]

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.

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

* 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:

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

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 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...
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. :)

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

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.
Agreed.
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.
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).

+ public:
+  void Start() {
+    ASSERT(!IsRunning());
+    if (HasTransitions()) *Header() = Smi::FromInt(0);
+  }
+
+  bool IsRunning() {
+    return HasTransitions() && (*Header())->IsSmi();
+  }
+
+  Map* Next() {
+    ASSERT(IsRunning());
+    int index = Smi::cast(*Header())->value();
+    if (index < NumberOfTransitions()) {
+      *Header() = Smi::FromInt(index + 1);
+      return GetTransition(index);
+    }
+    *Header() = GetHeap()->fixed_array_map();
+    return NULL;
+  }
+
+ private:
+  bool HasTransitions() { return length() >= Map::kProtoTransitionHeaderSize; }
+
+  Object** Header() {
+    return RawField(this, kMapOffset);
+  }
+
+  int NumberOfTransitions() {
+    return Smi::cast(get(Map::kProtoTransitionNumberOfEntriesOffset))->value();
+  }
+
+  Map* GetTransition(int transitionNumber) {
+    return Map::cast(
+        get(Map::kProtoTransitionHeaderSize +
+            Map::kProtoTransitionMapOffset +
+            transitionNumber * Map::kProtoTransitionElementsPerEntry));
+  }
+};
+
+
+// To traverse the transition tree iteratively, we have to store two kinds of
+// information in a map: The parent map in the traversal and which children of a
+// node have already been visited. To do this without additional memory, we
+// temporarily reuse two maps with known values:
+//
+//  (1) The map of the map temporarily holds the parent, and is restored to the
+//      meta map afterwards.
+//
+//  (2) The info which children have already been visited depends on which part
+//      of the map we currently iterate:
+//
+//    (a) If we currently follow normal map transitions, we temporarily store
+//        the current index in the map of the FixedArray of the desciptor
+//        array's contents, and restore it to the fixed array map afterwards.
+//        Note that a single descriptor can have 0, 1, or 2 transitions.
+//
+//    (b) If we currently follow prototype transitions, we temporarily store
+//        the current index in the map of the FixedArray holding the prototype
+//        transitions, and restore it to the fixed array map afterwards.
+//
+// Note that the child iterator is just a concatenation of two iterators: One
+// iterating over map transitions and one iterating over prototype transisitons.
+class IterableMap : public Map {
+ public:
+  // Record the parent in the traversal within this map. Note that this destroys
+  // this map's map!
+  void setParent(IterableMap* parent) { set_map_no_write_barrier(parent); }

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

naming convention: first letter capital

+
+  // Reset the current map's map, returning the parent previously stored in it.
+  IterableMap* getAndResetParent() {

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

naming convention: first letter capital

+    IterableMap* old_parent = static_cast<IterableMap*>(map());
+    set_map_no_write_barrier(GetHeap()->meta_map());
+    return old_parent;
+  }
+
+  // Start iterating over this map's children, possibly destroying a FixedArray
+  // map (see explanation above).
+  void childIteratorStart() {

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

naming convention: first letter capital

+    iterable_descriptor_array()->Start();
+    iterable_prototype_transitions()->Start();
+  }
+
+  // If we have an unvisited child map, return that one and advance. If we have
+  // none, return NULL and reset any destroyed FixedArray maps.
+  IterableMap* childIteratorNext() {

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

naming convention: first letter capital

+    if (iterable_descriptor_array()->IsRunning()) {
+      Map* next = iterable_descriptor_array()->Next();
+      if (next != NULL) return static_cast<IterableMap*>(next);
     }
-    *proto_map_or_index_field = GetHeap()->fixed_array_map();
-    if (map_or_index_field != NULL) {
-      *map_or_index_field = GetHeap()->fixed_array_map();
+    if (iterable_prototype_transitions()->IsRunning()) {
+      Map* next = iterable_prototype_transitions()->Next();
+      if (next != NULL) return static_cast<IterableMap*>(next);
     }
+    return NULL;
+  }
+
+ private:
+  IterableDescriptorArray* iterable_descriptor_array() {
+    return static_cast<IterableDescriptorArray*>(instance_descriptors());
+  }
+
+  IterablePrototypeTransitions* iterable_prototype_transitions() {
+    return static_cast<IterablePrototypeTransitions*>(
+        unchecked_prototype_transitions());
+  }
+};
+
 
-    // The callback expects a map to have a real map as its map, so we save
-    // the map field, which is being used to track the traversal and put the
-    // correct map (the meta_map) in place while we do the callback.
-    Map* prev = current->map();
-    current->set_map_no_write_barrier(meta_map);
-    callback(current, data);
-    current = prev;
+// Traverse the transition tree in postorder without using the C++ stack. We can
+// deduce the algorithm below using the following steps:
+//
+//   (1) Implement the recursive textbook algorithm for visiting a tree.

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

I don't think these 4 steps make algorithm any clearer than it is already they
just confuse.

[Sven Panne, 2012/01/20 13:15:33]

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... ;-)

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

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.

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

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. :)

+//
+//   (2) Transform that into an iterative version using an explicit stack, where
+//       each stack entry contains a pair of values: Which tree node do we
+//       currently visit and info about which children of this node have already
+//       been visited.
+//
+//   (3) Use local variables for the top of stack pair.
+//
+//   (4) Put the stack entry pair directly into the nodes, correctly resetting
+//       any overwritten parts after the visit.
+void Map::TraverseTransitionTree(TraverseCallback callback, void* data) {
+  IterableMap* current = static_cast<IterableMap*>(this);
+  current->childIteratorStart();
+  while (true) {

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

can it be changed into do { } while (current != metamap) to avoid having break
in the middle of the if?

[Sven Panne, 2012/01/20 13:15:33]

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.

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

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.

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

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]

I consider loops with no special exits easier to read.

+    IterableMap* child = current->childIteratorNext();

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

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:33]

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]

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

+    if (child != NULL) {
+      child->childIteratorStart();
+      child->setParent(current);
+      current = child;
+    } else {
+      IterableMap* parent = current->getAndResetParent();
+      callback(current, data);
+      if (current == this) break;
+      current = parent;
+    }
   }
 }