Title: [124990] trunk/Source/WebCore
- Revision
- 124990
- Author
- hara...@chromium.org
- Date
- 2012-08-07 22:38:33 -0700 (Tue, 07 Aug 2012)
Log Message
Optimize ChildNode{Insertion,Removal}Notifier::notify() by lazily taking a snapshot of child nodes
https://bugs.webkit.org/show_bug.cgi?id=92965
Reviewed by Adam Barth.
This patch improves performance of Dromaeo/dom-modify by 8.2% in both Chromium and Safari.
[Mac/Safari] 4590.33 runs/s => 4965.79 runs/s (+8.18%)
[Chromium/Linux] 3970.63 runs/s => 4299.65 runs/s (+8.29%)
notifyDescendantRemovedFromDocument() cannot iterate child nodes in this way:
void notifyDescendantRemovedFromDocument(Node* node) {
for (Node* child = node->firstChild(); child; child = child->nextSibling()) {
...;
notifyNodeRemovedFromDocument(child);
}
}
This is because notifyNodeRemovedFromDocument(child) might dispatch events
and the events might change child trees. To avoid security issues, the current
code takes a snapshot of child nodes before starting the iteration.
void notifyDescendantRemovedFromDocument(Node* node) {
NodeVector children;
getChildNodes(node, children); // Take a snapshot.
for (int i = 0; i < children.size(); i++) {
...;
notifyNodeRemovedFromDocument(children[i]);
}
}
Based on the observation that in almost all cases events won't be dispatched
from inside notifyNodeRemovedFromDocument(), this patch implements
a "lazy" snapshot. The snapshot is taken at the point where
EventDispatcher::dispatchEvent() is invoked. The snapshot is not taken unless
any event is dispatched.
No tests. Confirm that all existing tests pass.
Actually, at present there is (should be) no case where an event is
dispatched from inside notifyNodeRemovedFromDocument(). Even DOMNodeInserted
and DOMNodeRemoved events are not dispatched. Originally the snapshot was
implemented "just in case" to protect the code from future attacks.
I manually confirmed that the lazy snapshot works correctly by inserting
takeChildNodesSnapshot() to notifyDescendantRemovedFromDocument()
in a random manner.
* dom/ContainerNode.cpp:
(WebCore):
* dom/ContainerNode.h:
(ChildNodesLazySnapshot):
(WebCore::ChildNodesLazySnapshot::ChildNodesLazySnapshot):
(WebCore::ChildNodesLazySnapshot::~ChildNodesLazySnapshot):
(WebCore::ChildNodesLazySnapshot::nextNode):
(WebCore::ChildNodesLazySnapshot::takeSnapshot):
(WebCore::ChildNodesLazySnapshot::nextSnapshot):
(WebCore::ChildNodesLazySnapshot::hasSnapshot):
(WebCore::ChildNodesLazySnapshot::takeChildNodesLazySnapshot):
(WebCore):
* dom/ContainerNodeAlgorithms.cpp:
(WebCore::ChildNodeInsertionNotifier::notifyDescendantInsertedIntoDocument):
(WebCore::ChildNodeRemovalNotifier::notifyDescendantRemovedFromDocument):
* dom/EventDispatcher.cpp:
(WebCore::EventDispatcher::dispatchEvent):
Modified Paths
Diff
Modified: trunk/Source/WebCore/ChangeLog (124989 => 124990)
--- trunk/Source/WebCore/ChangeLog 2012-08-08 05:38:28 UTC (rev 124989)
+++ trunk/Source/WebCore/ChangeLog 2012-08-08 05:38:33 UTC (rev 124990)
@@ -1,3 +1,70 @@
+2012-08-07 Kentaro Hara <hara...@chromium.org>
+
+ Optimize ChildNode{Insertion,Removal}Notifier::notify() by lazily taking a snapshot of child nodes
+ https://bugs.webkit.org/show_bug.cgi?id=92965
+
+ Reviewed by Adam Barth.
+
+ This patch improves performance of Dromaeo/dom-modify by 8.2% in both Chromium and Safari.
+
+ [Mac/Safari] 4590.33 runs/s => 4965.79 runs/s (+8.18%)
+ [Chromium/Linux] 3970.63 runs/s => 4299.65 runs/s (+8.29%)
+
+ notifyDescendantRemovedFromDocument() cannot iterate child nodes in this way:
+
+ void notifyDescendantRemovedFromDocument(Node* node) {
+ for (Node* child = node->firstChild(); child; child = child->nextSibling()) {
+ ...;
+ notifyNodeRemovedFromDocument(child);
+ }
+ }
+
+ This is because notifyNodeRemovedFromDocument(child) might dispatch events
+ and the events might change child trees. To avoid security issues, the current
+ code takes a snapshot of child nodes before starting the iteration.
+
+ void notifyDescendantRemovedFromDocument(Node* node) {
+ NodeVector children;
+ getChildNodes(node, children); // Take a snapshot.
+ for (int i = 0; i < children.size(); i++) {
+ ...;
+ notifyNodeRemovedFromDocument(children[i]);
+ }
+ }
+
+ Based on the observation that in almost all cases events won't be dispatched
+ from inside notifyNodeRemovedFromDocument(), this patch implements
+ a "lazy" snapshot. The snapshot is taken at the point where
+ EventDispatcher::dispatchEvent() is invoked. The snapshot is not taken unless
+ any event is dispatched.
+
+ No tests. Confirm that all existing tests pass.
+ Actually, at present there is (should be) no case where an event is
+ dispatched from inside notifyNodeRemovedFromDocument(). Even DOMNodeInserted
+ and DOMNodeRemoved events are not dispatched. Originally the snapshot was
+ implemented "just in case" to protect the code from future attacks.
+ I manually confirmed that the lazy snapshot works correctly by inserting
+ takeChildNodesSnapshot() to notifyDescendantRemovedFromDocument()
+ in a random manner.
+
+ * dom/ContainerNode.cpp:
+ (WebCore):
+ * dom/ContainerNode.h:
+ (ChildNodesLazySnapshot):
+ (WebCore::ChildNodesLazySnapshot::ChildNodesLazySnapshot):
+ (WebCore::ChildNodesLazySnapshot::~ChildNodesLazySnapshot):
+ (WebCore::ChildNodesLazySnapshot::nextNode):
+ (WebCore::ChildNodesLazySnapshot::takeSnapshot):
+ (WebCore::ChildNodesLazySnapshot::nextSnapshot):
+ (WebCore::ChildNodesLazySnapshot::hasSnapshot):
+ (WebCore::ChildNodesLazySnapshot::takeChildNodesLazySnapshot):
+ (WebCore):
+ * dom/ContainerNodeAlgorithms.cpp:
+ (WebCore::ChildNodeInsertionNotifier::notifyDescendantInsertedIntoDocument):
+ (WebCore::ChildNodeRemovalNotifier::notifyDescendantRemovedFromDocument):
+ * dom/EventDispatcher.cpp:
+ (WebCore::EventDispatcher::dispatchEvent):
+
2012-08-07 Ojan Vafai <o...@chromium.org>
percentage margins + flex incorrectly overflows the flexbox
Modified: trunk/Source/WebCore/dom/ContainerNode.cpp (124989 => 124990)
--- trunk/Source/WebCore/dom/ContainerNode.cpp 2012-08-08 05:38:28 UTC (rev 124989)
+++ trunk/Source/WebCore/dom/ContainerNode.cpp 2012-08-08 05:38:33 UTC (rev 124990)
@@ -60,6 +60,8 @@
static size_t s_attachDepth;
static bool s_shouldReEnableMemoryCacheCallsAfterAttach;
+ChildNodesLazySnapshot* ChildNodesLazySnapshot::latestSnapshot = 0;
+
static void collectTargetNodes(Node* node, NodeVector& nodes)
{
if (node->nodeType() != Node::DOCUMENT_FRAGMENT_NODE) {
Modified: trunk/Source/WebCore/dom/ContainerNode.h (124989 => 124990)
--- trunk/Source/WebCore/dom/ContainerNode.h 2012-08-08 05:38:28 UTC (rev 124989)
+++ trunk/Source/WebCore/dom/ContainerNode.h 2012-08-08 05:38:33 UTC (rev 124990)
@@ -27,6 +27,9 @@
#include "ExceptionCodePlaceholder.h"
#include "Node.h"
+#include <wtf/OwnPtr.h>
+#include <wtf/Vector.h>
+
namespace WebCore {
class FloatPoint;
@@ -298,6 +301,73 @@
nodes.append(child);
}
+class ChildNodesLazySnapshot {
+ WTF_MAKE_NONCOPYABLE(ChildNodesLazySnapshot);
+ WTF_MAKE_FAST_ALLOCATED;
+public:
+ explicit ChildNodesLazySnapshot(Node* parentNode)
+ : m_parentNode(parentNode)
+ , m_currentNode(parentNode->firstChild())
+ , m_currentIndex(0)
+ {
+ m_nextSnapshot = latestSnapshot;
+ latestSnapshot = this;
+ }
+
+ ~ChildNodesLazySnapshot()
+ {
+ latestSnapshot = m_nextSnapshot;
+ }
+
+ // Returns 0 if there is no next Node.
+ Node* nextNode()
+ {
+ if (LIKELY(!hasSnapshot())) {
+ Node* node = m_currentNode;
+ if (m_currentNode)
+ m_currentNode = m_currentNode->nextSibling();
+ return node;
+ }
+ Vector<RefPtr<Node> >* nodeVector = m_childNodes.get();
+ if (m_currentIndex >= nodeVector->size())
+ return 0;
+ return (*nodeVector)[m_currentIndex++].get();
+ }
+
+ void takeSnapshot()
+ {
+ if (hasSnapshot())
+ return;
+ m_childNodes = adoptPtr(new Vector<RefPtr<Node> >());
+ Node* node = m_currentNode;
+ while (node) {
+ m_childNodes->append(node);
+ node = node->nextSibling();
+ }
+ }
+
+ ChildNodesLazySnapshot* nextSnapshot() { return m_nextSnapshot; }
+ bool hasSnapshot() { return !!m_childNodes.get(); }
+
+ static void takeChildNodesLazySnapshot()
+ {
+ ChildNodesLazySnapshot* snapshot = latestSnapshot;
+ while (snapshot && !snapshot->hasSnapshot()) {
+ snapshot->takeSnapshot();
+ snapshot = snapshot->nextSnapshot();
+ }
+ }
+
+private:
+ static ChildNodesLazySnapshot* latestSnapshot;
+
+ Node* m_parentNode;
+ Node* m_currentNode;
+ unsigned m_currentIndex;
+ OwnPtr<Vector<RefPtr<Node> > > m_childNodes; // Lazily instantiated.
+ ChildNodesLazySnapshot* m_nextSnapshot;
+};
+
} // namespace WebCore
#endif // ContainerNode_h
Modified: trunk/Source/WebCore/dom/ContainerNodeAlgorithms.cpp (124989 => 124990)
--- trunk/Source/WebCore/dom/ContainerNodeAlgorithms.cpp 2012-08-08 05:38:28 UTC (rev 124989)
+++ trunk/Source/WebCore/dom/ContainerNodeAlgorithms.cpp 2012-08-08 05:38:33 UTC (rev 124990)
@@ -34,16 +34,15 @@
void ChildNodeInsertionNotifier::notifyDescendantInsertedIntoDocument(ContainerNode* node)
{
- NodeVector children;
- getChildNodes(node, children);
- for (size_t i = 0; i < children.size(); ++i) {
+ ChildNodesLazySnapshot snapshot(node);
+ while (Node* child = snapshot.nextNode()) {
// If we have been removed from the document during this loop, then
// we don't want to tell the rest of our children that they've been
// inserted into the document because they haven't.
- if (node->inDocument() && children[i]->parentNode() == node)
- notifyNodeInsertedIntoDocument(children[i].get());
+ if (node->inDocument() && child->parentNode() == node)
+ notifyNodeInsertedIntoDocument(child);
}
-
+
if (!node->isElementNode())
return;
@@ -67,14 +66,13 @@
void ChildNodeRemovalNotifier::notifyDescendantRemovedFromDocument(ContainerNode* node)
{
- NodeVector children;
- getChildNodes(node, children);
- for (size_t i = 0; i < children.size(); ++i) {
+ ChildNodesLazySnapshot snapshot(node);
+ while (Node* child = snapshot.nextNode()) {
// If we have been added to the document during this loop, then we
// don't want to tell the rest of our children that they've been
// removed from the document because they haven't.
- if (!node->inDocument() && children[i]->parentNode() == node)
- notifyNodeRemovedFromDocument(children[i].get());
+ if (!node->inDocument() && child->parentNode() == node)
+ notifyNodeRemovedFromDocument(child);
}
if (!node->isElementNode())
Modified: trunk/Source/WebCore/dom/EventDispatcher.cpp (124989 => 124990)
--- trunk/Source/WebCore/dom/EventDispatcher.cpp 2012-08-08 05:38:28 UTC (rev 124989)
+++ trunk/Source/WebCore/dom/EventDispatcher.cpp 2012-08-08 05:38:33 UTC (rev 124990)
@@ -27,6 +27,7 @@
#include "EventDispatcher.h"
#include "ComposedShadowTreeWalker.h"
+#include "ContainerNode.h"
#include "ElementShadow.h"
#include "EventContext.h"
#include "EventDispatchMediator.h"
@@ -246,6 +247,8 @@
m_eventDispatched = true;
#endif
RefPtr<Event> event = prpEvent;
+ ChildNodesLazySnapshot::takeChildNodesLazySnapshot();
+
event->setTarget(eventTargetRespectingSVGTargetRules(m_node.get()));
ASSERT(!eventDispatchForbidden());
ASSERT(event->target());
_______________________________________________
webkit-changes mailing list
webkit-changes@lists.webkit.org
http://lists.webkit.org/mailman/listinfo/webkit-changes
