[V8] Vastly simplify V8GCController's NodeVisitor
authorabarth@webkit.org <abarth@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 22 Oct 2012 18:50:11 +0000 (18:50 +0000)
committerabarth@webkit.org <abarth@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 22 Oct 2012 18:50:11 +0000 (18:50 +0000)
https://bugs.webkit.org/show_bug.cgi?id=99884

Reviewed by Kentaro Hara.

PerformanceTests:

Adds some performance tests for the garbage collector.

* Bindings/gc-forest.html: Added.
* Bindings/gc-mini-tree.html: Added.
* Bindings/gc-tree.html: Added.

Source/WebCore:

NodeVisitor was vastly more complicated than necessary.

This patch improve performance on these new gc benchmarks:

gc-forest: 1.14% better
gc-mini-tree: 5.09% better
gc-tree: 4.60% better

* bindings/v8/V8GCController.cpp:
(WebCore::ObjectVisitor::visitDOMWrapper):
(WebCore::addImplicitReferencesForNodeWithEventListeners):
(WebCore::rootForGC):
(WebCore::NodeVisitor::visitDOMWrapper):
(WebCore::NodeVisitor::applyGrouping):
(NodeVisitor):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@132114 268f45cc-cd09-0410-ab3c-d52691b4dbfc

PerformanceTests/Bindings/gc-forest.html [new file with mode: 0644]
PerformanceTests/Bindings/gc-mini-tree.html [new file with mode: 0644]
PerformanceTests/Bindings/gc-tree.html [new file with mode: 0644]
PerformanceTests/ChangeLog
Source/WebCore/ChangeLog
Source/WebCore/bindings/v8/V8GCController.cpp

diff --git a/PerformanceTests/Bindings/gc-forest.html b/PerformanceTests/Bindings/gc-forest.html
new file mode 100644 (file)
index 0000000..d18fe15
--- /dev/null
@@ -0,0 +1,13 @@
+<!DOCTYPE html>
+<body>
+<script src="../resources/runner.js"></script>
+<script>
+PerfTestRunner.measureTime({run: function() {
+    (function() {
+        for (var i = 0; i < 1000000; i++)
+            document.createElement("div");
+    })();
+    PerfTestRunner.gc();
+}});
+</script>
+</body>
diff --git a/PerformanceTests/Bindings/gc-mini-tree.html b/PerformanceTests/Bindings/gc-mini-tree.html
new file mode 100644 (file)
index 0000000..b030769
--- /dev/null
@@ -0,0 +1,13 @@
+<!DOCTYPE html>
+<body>
+<script src="../resources/runner.js"></script>
+<script>
+PerfTestRunner.measureTime({run: function() {
+    (function() {
+        for (var i = 0; i < 500000; i++)
+            document.createElement("div").appendChild(document.createElement("span"));
+    })();
+    PerfTestRunner.gc();
+}});
+</script>
+</body>
diff --git a/PerformanceTests/Bindings/gc-tree.html b/PerformanceTests/Bindings/gc-tree.html
new file mode 100644 (file)
index 0000000..d996288
--- /dev/null
@@ -0,0 +1,14 @@
+<!DOCTYPE html>
+<body>
+<script src="../resources/runner.js"></script>
+<script>
+PerfTestRunner.measureTime({run: function() {
+    (function() {
+        var root = document.createElement("div");
+        for (var i = 0; i < 1000000; i++)
+            root.appendChild(document.createElement("div"));
+    })();
+    PerfTestRunner.gc();
+}});
+</script>
+</body>
index 91f0c17..570e49f 100644 (file)
@@ -1,3 +1,16 @@
+2012-10-22  Adam Barth  <abarth@webkit.org>
+
+        [V8] Vastly simplify V8GCController's NodeVisitor
+        https://bugs.webkit.org/show_bug.cgi?id=99884
+
+        Reviewed by Kentaro Hara.
+
+        Adds some performance tests for the garbage collector.
+
+        * Bindings/gc-forest.html: Added.
+        * Bindings/gc-mini-tree.html: Added.
+        * Bindings/gc-tree.html: Added.
+
 2012-10-17  Ryosuke Niwa  <rniwa@webkit.org>
 
         Bump up the number of iterations of html5-full-render to 5
index a242689..3dc6324 100644 (file)
@@ -1,3 +1,26 @@
+2012-10-22  Adam Barth  <abarth@webkit.org>
+
+        [V8] Vastly simplify V8GCController's NodeVisitor
+        https://bugs.webkit.org/show_bug.cgi?id=99884
+
+        Reviewed by Kentaro Hara.
+
+        NodeVisitor was vastly more complicated than necessary.
+
+        This patch improve performance on these new gc benchmarks:
+
+        gc-forest: 1.14% better
+        gc-mini-tree: 5.09% better
+        gc-tree: 4.60% better
+
+        * bindings/v8/V8GCController.cpp:
+        (WebCore::ObjectVisitor::visitDOMWrapper):
+        (WebCore::addImplicitReferencesForNodeWithEventListeners):
+        (WebCore::rootForGC):
+        (WebCore::NodeVisitor::visitDOMWrapper):
+        (WebCore::NodeVisitor::applyGrouping):
+        (NodeVisitor):
+
 2012-10-22  Emil A Eklund  <eae@chromium.org>
 
         Change baselinePosition and maxAscent/maxDescent to int
index 9007dab..95d91e2 100644 (file)
@@ -101,199 +101,108 @@ public:
     }
 };
 
-// Implements v8::RetainedObjectInfo.
-class UnspecifiedGroup : public RetainedObjectInfo {
+class ObjectVisitor : public DOMWrapperMap<void>::Visitor {
 public:
-    explicit UnspecifiedGroup(void* object)
-        : m_object(object)
-    {
-        ASSERT(m_object);
-    }
-    
-    virtual void Dispose() { delete this; }
-  
-    virtual bool IsEquivalent(v8::RetainedObjectInfo* other)
-    {
-        ASSERT(other);
-        return other == this || static_cast<WebCore::RetainedObjectInfo*>(other)->GetEquivalenceClass() == this->GetEquivalenceClass();
-    }
-
-    virtual intptr_t GetHash()
-    {
-        return PtrHash<void*>::hash(m_object);
-    }
-    
-    virtual const char* GetLabel()
-    {
-        return "Object group";
-    }
-
-    virtual intptr_t GetEquivalenceClass()
+    void visitDOMWrapper(DOMDataStore* store, void* object, v8::Persistent<v8::Object> wrapper)
     {
-        return reinterpret_cast<intptr_t>(m_object);
+        V8DOMWrapper::domWrapperType(wrapper)->visitDOMWrapper(store, object, wrapper);
     }
-
-private:
-    void* m_object;
 };
 
-class GroupId {
-public:
-    GroupId() : m_type(NullType), m_groupId(0) {}
-    GroupId(Node* node) : m_type(NodeType), m_node(node) {}
-    GroupId(void* other) : m_type(OtherType), m_other(other) {}
-    bool operator!() const { return m_type == NullType; }
-    uintptr_t groupId() const { return m_groupId; }
-    RetainedObjectInfo* createRetainedObjectInfo() const
-    {
-        switch (m_type) {
-        case NullType:
-            return 0;
-        case NodeType:
-            return new RetainedDOMInfo(m_node);
-        case OtherType:
-            return new UnspecifiedGroup(m_other);
-        default:
-            return 0;
-        }
+static void addImplicitReferencesForNodeWithEventListeners(Node* node, v8::Persistent<v8::Object> wrapper)
+{
+    ASSERT(node->hasEventListeners());
+
+    Vector<v8::Persistent<v8::Value> > listeners;
+
+    EventListenerIterator iterator(node);
+    while (EventListener* listener = iterator.nextListener()) {
+        if (listener->type() != EventListener::JSEventListenerType)
+            continue;
+        V8AbstractEventListener* v8listener = static_cast<V8AbstractEventListener*>(listener);
+        if (!v8listener->hasExistingListenerObject())
+            continue;
+        listeners.append(v8listener->existingListenerObjectPersistentHandle());
     }
-    
-private:
-    enum Type {
-        NullType,
-        NodeType,
-        OtherType
-    };
-    Type m_type;
-    union {
-        uintptr_t m_groupId;
-        Node* m_node;
-        void* m_other;
-    };
-};
-
-class GrouperItem {
-public:
-    GrouperItem(GroupId groupId, v8::Persistent<v8::Object> wrapper) : m_groupId(groupId), m_wrapper(wrapper) {}
-    uintptr_t groupId() const { return m_groupId.groupId(); }
-    RetainedObjectInfo* createRetainedObjectInfo() const { return m_groupId.createRetainedObjectInfo(); }
-    v8::Persistent<v8::Object> wrapper() const { return m_wrapper; }
 
-private:
-    GroupId m_groupId;
-    v8::Persistent<v8::Object> m_wrapper;
-};
+    if (listeners.isEmpty())
+        return;
 
-bool operator<(const GrouperItem& a, const GrouperItem& b)
-{
-    return a.groupId() < b.groupId();
+    v8::V8::AddImplicitReferences(wrapper, listeners.data(), listeners.size());
 }
 
-typedef Vector<GrouperItem> GrouperList;
-
-// If the node is in document, put it in the ownerDocument's object group.
-//
-// If an image element was created by JavaScript "new Image",
-// it is not in a document. However, if the load event has not
-// been fired (still onloading), it is treated as in the document.
-//
-// Otherwise, the node is put in an object group identified by the root
-// element of the tree to which it belongs.
-static GroupId calculateGroupId(Node* node)
+static Node* rootForGC(Node* node)
 {
     if (node->inDocument() || (node->hasTagName(HTMLNames::imgTag) && static_cast<HTMLImageElement*>(node)->hasPendingActivity()))
-        return GroupId(node->document());
+        return node->document();
 
-    Node* root = node;
     if (node->isAttributeNode()) {
-        root = static_cast<Attr*>(node)->ownerElement();
-        // If the attribute has no element, no need to put it in the group,
-        // because it'll always be a group of 1.
-        if (!root)
-            return GroupId();
+        node = static_cast<Attr*>(node)->ownerElement();
+        if (!node)
+            return 0;
     }
-    while (Node* parent = root->parentOrHostNode())
-        root = parent;
 
-    return GroupId(root);
+    while (Node* parent = node->parentOrHostNode())
+        node = parent;
+
+    return node;
 }
 
-class ObjectVisitor : public DOMWrapperMap<void>::Visitor {
+class ImplicitConnection {
 public:
-    void visitDOMWrapper(DOMDataStore* store, void* object, v8::Persistent<v8::Object> wrapper)
+    ImplicitConnection(Node* root, v8::Persistent<v8::Value> wrapper)
+        : m_root(root)
+        , m_wrapper(wrapper)
     {
-        V8DOMWrapper::domWrapperType(wrapper)->visitDOMWrapper(store, object, wrapper);
     }
+
+    Node* root() const { return m_root; }
+    v8::Persistent<v8::Value> wrapper() const { return m_wrapper; }
+
+public:
+    Node* m_root;
+    v8::Persistent<v8::Value> m_wrapper;
 };
 
+bool operator<(const ImplicitConnection& left, const ImplicitConnection& right)
+{
+    return left.root() < right.root();
+}
+
 class NodeVisitor : public DOMWrapperMap<Node>::Visitor {
 public:
     void visitDOMWrapper(DOMDataStore*, Node* node, v8::Persistent<v8::Object> wrapper)
     {
-        if (node->hasEventListeners()) {
-            Vector<v8::Persistent<v8::Value> > listeners;
-            EventListenerIterator iterator(node);
-            while (EventListener* listener = iterator.nextListener()) {
-                if (listener->type() != EventListener::JSEventListenerType)
-                    continue;
-                V8AbstractEventListener* v8listener = static_cast<V8AbstractEventListener*>(listener);
-                if (!v8listener->hasExistingListenerObject())
-                    continue;
-                listeners.append(v8listener->existingListenerObjectPersistentHandle());
-            }
-            if (!listeners.isEmpty())
-                v8::V8::AddImplicitReferences(wrapper, listeners.data(), listeners.size());
-        }
+        if (node->hasEventListeners())
+            addImplicitReferencesForNodeWithEventListeners(node, wrapper);
 
-        GroupId groupId = calculateGroupId(node);
-        if (!groupId)
+        Node* root = rootForGC(node);
+        if (!root)
             return;
-        m_grouper.append(GrouperItem(groupId, wrapper));
+        m_connections.append(ImplicitConnection(root, wrapper));
     }
 
     void applyGrouping()
     {
-        // Group by sorting by the group id.
-        std::sort(m_grouper.begin(), m_grouper.end());
-
-        for (size_t i = 0; i < m_grouper.size(); ) {
-            // Seek to the next key (or the end of the list).
-            size_t nextKeyIndex = m_grouper.size();
-            for (size_t j = i; j < m_grouper.size(); ++j) {
-                if (m_grouper[i].groupId() != m_grouper[j].groupId()) {
-                    nextKeyIndex = j;
-                    break;
-                }
-            }
-
-            ASSERT(nextKeyIndex > i);
+        std::sort(m_connections.begin(), m_connections.end());
+        Vector<v8::Persistent<v8::Value> > group;
+        size_t i = 0;
+        while (i < m_connections.size()) {
+            Node* root = m_connections[i].root();
 
-            // We only care about a group if it has more than one object. If it only
-            // has one object, it has nothing else that needs to be kept alive.
-            if (nextKeyIndex - i <= 1) {
-                i = nextKeyIndex;
-                continue;
-            }
-
-            size_t rootIndex = i;
-            
-            Vector<v8::Persistent<v8::Value> > group;
-            group.reserveCapacity(nextKeyIndex - i);
-            for (; i < nextKeyIndex; ++i) {
-                v8::Persistent<v8::Value> wrapper = m_grouper[i].wrapper();
-                if (!wrapper.IsEmpty())
-                    group.append(wrapper);
-            }
+            do {
+                group.append(m_connections[i++].wrapper());
+            } while (i < m_connections.size() && root == m_connections[i].root());
 
             if (group.size() > 1)
-                v8::V8::AddObjectGroup(&group[0], group.size(), m_grouper[rootIndex].createRetainedObjectInfo());
+                v8::V8::AddObjectGroup(group.data(), group.size(), new RetainedDOMInfo(root));
 
-            ASSERT(i == nextKeyIndex);
+            group.shrink(0);
         }
     }
 
 private:
-    GrouperList m_grouper;
+    Vector<ImplicitConnection> m_connections;
 };
 
 // Create object groups for DOM tree nodes.