Title: [135689] trunk/Source/WebCore
- Revision
- 135689
- Author
- shin...@chromium.org
- Date
- 2012-11-26 01:07:19 -0800 (Mon, 26 Nov 2012)
Log Message
[Shadow] Attaching children of a shadow host takes O(N^2) where N is the number of host children
https://bugs.webkit.org/show_bug.cgi?id=103017
Reviewed by Hajime Morita.
Since ContentDistribution was just a Vector, ContentDistribution::find() took O(N). Each child of shadow host calls it.
As a result, attaching children of shadow host takes O(N^2) at all.
In this patch, we make ContentDistribution::find() O(1) amortizedly. We introduce HashMap from a Node to Vector index,
and use it for ContentDistribution::find().
No new tests, covered by existing tests.
* html/shadow/ContentDistributor.cpp:
(WebCore::ContentDistribution::swap):
(WebCore):
(WebCore::ContentDistribution::append):
(WebCore::ContentDistribution::find):
(WebCore::ContentDistributor::distributeSelectionsTo):
* html/shadow/ContentDistributor.h:
(ContentDistribution): ContentDistribution now contains Vector and a reverse map.
(WebCore::ContentDistribution::first):
(WebCore::ContentDistribution::last):
(WebCore::ContentDistribution::at):
(WebCore::ContentDistribution::size):
(WebCore::ContentDistribution::isEmpty):
(WebCore::ContentDistribution::clear):
(WebCore::ContentDistribution::contains):
(WebCore::ContentDistribution::nodes):
Modified Paths
Diff
Modified: trunk/Source/WebCore/ChangeLog (135688 => 135689)
--- trunk/Source/WebCore/ChangeLog 2012-11-26 08:31:18 UTC (rev 135688)
+++ trunk/Source/WebCore/ChangeLog 2012-11-26 09:07:19 UTC (rev 135689)
@@ -1,3 +1,35 @@
+2012-11-26 Shinya Kawanaka <shin...@chromium.org>
+
+ [Shadow] Attaching children of a shadow host takes O(N^2) where N is the number of host children
+ https://bugs.webkit.org/show_bug.cgi?id=103017
+
+ Reviewed by Hajime Morita.
+
+ Since ContentDistribution was just a Vector, ContentDistribution::find() took O(N). Each child of shadow host calls it.
+ As a result, attaching children of shadow host takes O(N^2) at all.
+
+ In this patch, we make ContentDistribution::find() O(1) amortizedly. We introduce HashMap from a Node to Vector index,
+ and use it for ContentDistribution::find().
+
+ No new tests, covered by existing tests.
+
+ * html/shadow/ContentDistributor.cpp:
+ (WebCore::ContentDistribution::swap):
+ (WebCore):
+ (WebCore::ContentDistribution::append):
+ (WebCore::ContentDistribution::find):
+ (WebCore::ContentDistributor::distributeSelectionsTo):
+ * html/shadow/ContentDistributor.h:
+ (ContentDistribution): ContentDistribution now contains Vector and a reverse map.
+ (WebCore::ContentDistribution::first):
+ (WebCore::ContentDistribution::last):
+ (WebCore::ContentDistribution::at):
+ (WebCore::ContentDistribution::size):
+ (WebCore::ContentDistribution::isEmpty):
+ (WebCore::ContentDistribution::clear):
+ (WebCore::ContentDistribution::contains):
+ (WebCore::ContentDistribution::nodes):
+
2012-11-26 Dan Carney <dcar...@google.com>
[V8] Give isolated shells a lifecycle like that of main shells
Modified: trunk/Source/WebCore/html/shadow/ContentDistributor.cpp (135688 => 135689)
--- trunk/Source/WebCore/html/shadow/ContentDistributor.cpp 2012-11-26 08:31:18 UTC (rev 135688)
+++ trunk/Source/WebCore/html/shadow/ContentDistributor.cpp 2012-11-26 09:07:19 UTC (rev 135689)
@@ -36,6 +36,28 @@
namespace WebCore {
+void ContentDistribution::swap(ContentDistribution& other)
+{
+ m_nodes.swap(other.m_nodes);
+ m_indices.swap(other.m_indices);
+}
+
+void ContentDistribution::append(PassRefPtr<Node> node)
+{
+ size_t size = m_nodes.size();
+ m_indices.set(node.get(), size);
+ m_nodes.append(node);
+}
+
+size_t ContentDistribution::find(const Node* node) const
+{
+ HashMap<const Node*, size_t>::const_iterator it = m_indices.find(node);
+ if (it == m_indices.end())
+ return notFound;
+
+ return it.get()->value;
+}
+
ContentDistributor::ContentDistributor()
: m_validity(Undetermined)
{
@@ -156,10 +178,10 @@
if (distributed[i])
continue;
- if (!query.matches(pool, i))
+ if (!query.matches(pool.nodes(), i))
continue;
- Node* child = pool[i].get();
+ Node* child = pool.at(i).get();
distribution.append(child);
m_nodeToInsertionPoint.add(child, insertionPoint);
distributed[i] = true;
Modified: trunk/Source/WebCore/html/shadow/ContentDistributor.h (135688 => 135689)
--- trunk/Source/WebCore/html/shadow/ContentDistributor.h 2012-11-26 08:31:18 UTC (rev 135688)
+++ trunk/Source/WebCore/html/shadow/ContentDistributor.h 2012-11-26 09:07:19 UTC (rev 135689)
@@ -44,8 +44,30 @@
class Node;
class ShadowRoot;
-typedef Vector<RefPtr<Node> > ContentDistribution;
+class ContentDistribution {
+public:
+ PassRefPtr<Node> first() const { return m_nodes.first(); }
+ PassRefPtr<Node> last() const { return m_nodes.last(); }
+ PassRefPtr<Node> at(size_t index) const { return m_nodes.at(index); }
+ size_t size() const { return m_nodes.size(); }
+ bool isEmpty() const { return m_nodes.isEmpty(); }
+
+ void append(PassRefPtr<Node>);
+ void clear() { m_nodes.clear(); m_indices.clear(); }
+
+ bool contains(const Node* node) const { return m_indices.contains(node); }
+ size_t find(const Node*) const;
+
+ void swap(ContentDistribution& other);
+
+ const Vector<RefPtr<Node> >& nodes() const { return m_nodes; }
+
+private:
+ Vector<RefPtr<Node> > m_nodes;
+ HashMap<const Node*, size_t> m_indices;
+};
+
class ContentDistributor {
WTF_MAKE_NONCOPYABLE(ContentDistributor);
public:
_______________________________________________
webkit-changes mailing list
webkit-changes@lists.webkit.org
http://lists.webkit.org/mailman/listinfo/webkit-changes
