Title: [104880] branches/safari-534.54-branch/Source/WebCore
- Revision
- 104880
- Author
- lforsch...@apple.com
- Date
- 2012-01-12 16:31:36 -0800 (Thu, 12 Jan 2012)
Log Message
Merged r103082.
Modified Paths
Diff
Modified: branches/safari-534.54-branch/Source/WebCore/ChangeLog (104879 => 104880)
--- branches/safari-534.54-branch/Source/WebCore/ChangeLog 2012-01-13 00:30:55 UTC (rev 104879)
+++ branches/safari-534.54-branch/Source/WebCore/ChangeLog 2012-01-13 00:31:36 UTC (rev 104880)
@@ -1,5 +1,33 @@
2011-1-12 Lucas Forschler <lforsch...@apple.com>
+ Merge 103082
+
+ 2011-12-15 Alexey Proskuryakov <a...@apple.com>
+
+ Poor XPath performance when evaluating an _expression_ that returns a lot of nodes
+ https://bugs.webkit.org/show_bug.cgi?id=74665
+ <rdar://problem/10517146>
+
+ Reviewed by Darin Adler.
+
+ No change in funcitonality. Well covered by existing tests (ran them with zero cutoff to
+ execute the new code path).
+
+ Our sorting function is optimized for small node sets in large documents, and this is the
+ opposite of it. Added another one that traverses the whole document, adding nodes from the
+ node set to sorted list. That doesn't grow with the number of nodes nearly as fast.
+
+ Cutoff amount chosen for the document referenced in bug - this is roughly where the algorithms
+ have the same performance on it.
+
+ * xml/XPathNodeSet.cpp:
+ (WebCore::XPath::NodeSet::sort):
+ (WebCore::XPath::findRootNode):
+ (WebCore::XPath::NodeSet::traversalSort):
+ * xml/XPathNodeSet.h:
+
+2011-1-12 Lucas Forschler <lforsch...@apple.com>
+
Merge 102024
2011-12-02 Jer Noble <jer.no...@apple.com>
Modified: branches/safari-534.54-branch/Source/WebCore/xml/XPathNodeSet.cpp (104879 => 104880)
--- branches/safari-534.54-branch/Source/WebCore/xml/XPathNodeSet.cpp 2012-01-13 00:30:55 UTC (rev 104879)
+++ branches/safari-534.54-branch/Source/WebCore/xml/XPathNodeSet.cpp 2012-01-13 00:31:36 UTC (rev 104880)
@@ -35,6 +35,10 @@
namespace WebCore {
namespace XPath {
+// When a node set is large, sorting it by traversing the whole document is better (we can
+// assume that we aren't dealing with documents that we cannot even traverse in reasonable time).
+const unsigned traversalSortCutoff = 10000;
+
static inline Node* parentWithDepth(unsigned depth, const Vector<Node*>& parents)
{
ASSERT(parents.size() >= depth + 1);
@@ -142,7 +146,12 @@
const_cast<bool&>(m_isSorted) = true;
return;
}
-
+
+ if (nodeCount > traversalSortCutoff) {
+ traversalSort();
+ return;
+ }
+
bool containsAttributeNodes = false;
Vector<Vector<Node*> > parentMatrix(nodeCount);
@@ -166,9 +175,62 @@
for (unsigned i = 0; i < nodeCount; ++i)
sortedNodes.append(parentMatrix[i][0]);
- const_cast<Vector<RefPtr<Node> >& >(m_nodes).swap(sortedNodes);
+ const_cast<Vector<RefPtr<Node> >&>(m_nodes).swap(sortedNodes);
}
+static Node* findRootNode(Node* node)
+{
+ if (node->isAttributeNode())
+ node = static_cast<Attr*>(node)->ownerElement();
+ if (node->inDocument())
+ node = node->document();
+ else {
+ while (Node* parent = node->parentNode())
+ node = parent;
+ }
+ return node;
+}
+
+void NodeSet::traversalSort() const
+{
+ HashSet<Node*> nodes;
+ bool containsAttributeNodes = false;
+
+ unsigned nodeCount = m_nodes.size();
+ ASSERT(nodeCount > 1);
+ for (unsigned i = 0; i < nodeCount; ++i) {
+ Node* node = m_nodes[i].get();
+ nodes.add(node);
+ if (node->isAttributeNode())
+ containsAttributeNodes = true;
+ }
+
+ Vector<RefPtr<Node> > sortedNodes;
+ sortedNodes.reserveInitialCapacity(nodeCount);
+
+ for (Node* n = findRootNode(m_nodes.first().get()); n; n = n->traverseNextNode()) {
+ if (nodes.contains(n))
+ sortedNodes.append(n);
+
+ if (!containsAttributeNodes || !n->isElementNode())
+ continue;
+
+ NamedNodeMap* attributes = toElement(n)->attributes(true /* read-only */);
+ if (!attributes)
+ continue;
+
+ unsigned attributeCount = attributes->length();
+ for (unsigned i = 0; i < attributeCount; ++i) {
+ Attr* attribute = attributes->attributeItem(i)->attr();
+ if (attribute && nodes.contains(attribute))
+ sortedNodes.append(attribute);
+ }
+ }
+
+ ASSERT(sortedNodes.size() == nodeCount);
+ const_cast<Vector<RefPtr<Node> >&>(m_nodes).swap(sortedNodes);
+}
+
void NodeSet::reverse()
{
if (m_nodes.isEmpty())
Modified: branches/safari-534.54-branch/Source/WebCore/xml/XPathNodeSet.h (104879 => 104880)
--- branches/safari-534.54-branch/Source/WebCore/xml/XPathNodeSet.h 2012-01-13 00:30:55 UTC (rev 104879)
+++ branches/safari-534.54-branch/Source/WebCore/xml/XPathNodeSet.h 2012-01-13 00:31:36 UTC (rev 104880)
@@ -73,6 +73,8 @@
void reverse();
private:
+ void traversalSort() const;
+
bool m_isSorted;
bool m_subtreesAreDisjoint;
Vector<RefPtr<Node> > m_nodes;
_______________________________________________
webkit-changes mailing list
webkit-changes@lists.webkit.org
http://lists.webkit.org/mailman/listinfo.cgi/webkit-changes
