Reviewers: Vyacheslav Egorov, Michael Starzinger,
Description:
Refactored iterative map traversal.
The main goal is to cleanly separate between the traversal algorithm itself
and
the state information held by Map and its associated objects. The former is
quite straightforward, while the latter is rather tricky due the way we
currently store map/prototype transitions in a Map.
Currently this is only a skeleton, just to get some feedback and see if
we're
heading into the right direction...
Please review this at https://chromiumcodereview.appspot.com/9252007/
SVN Base: https://v8.googlecode.com/svn/branches/bleeding_edge
Affected files:
M src/objects.cc
Index: src/objects.cc
diff --git a/src/objects.cc b/src/objects.cc
index
0941e792f04e98f3391c5a8757da74902d74e21e..33e7c6b006ad0d2a972db32e90e925cdfeb7ad9e
100644
--- a/src/objects.cc
+++ b/src/objects.cc
@@ -4935,6 +4935,79 @@ void Map::RemoveFromCodeCache(String* name, Code*
code, int index) {
}
+#if 0
+// 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.
+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) { }
+
+ // Reset the current map's map, returning the parent previously stored
in it.
+ IterableMap* getAndResetParent() { return NULL; }
+
+ // Start iterating over this map's children, possibly destroying a
FixedArray
+ // map (see explanation above).
+ void childIteratorStart() { }
+
+ // 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() { return NULL; }
+};
+
+
+// Traverse the transition tree 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.
+//
+// (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) {
+ IterableMap* child = current->childIteratorNext();
+ if (child != NULL) {
+ child->childIteratorStart();
+ child->setParent(current);
+ current = child;
+ } else {
+ IterableMap* parent = current->getAndResetParent();
+ callback(current, data);
+ if (current == this) break;
+ current = parent;
+ }
+ }
+}
+
+#else
+
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.
@@ -5006,6 +5079,7 @@ void Map::TraverseTransitionTree(TraverseCallback
callback, void* data) {
current = prev;
}
}
+#endif
MaybeObject* CodeCache::Update(String* name, Code* code) {
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
