Revert "Replace style sharing cousin list search with LRU"
This reverts commit r156070 because of a performance regression.
BUG=273605
TBR=esprehn
Review URL: https://chromiumcodereview.appspot.com/22966004
git-svn-id: svn://svn.chromium.org/blink/trunk@156247 bbb929c8-8fbe-4397-9dbb-9b2b20218538
diff --git a/Source/core/css/resolver/SharedStyleFinder.cpp b/Source/core/css/resolver/SharedStyleFinder.cpp
index d3899ad..ee83ce2 100644
--- a/Source/core/css/resolver/SharedStyleFinder.cpp
+++ b/Source/core/css/resolver/SharedStyleFinder.cpp
@@ -56,11 +56,64 @@
using namespace HTMLNames;
+static const unsigned cStyleSearchThreshold = 10;
+static const unsigned cStyleSearchLevelThreshold = 10;
+
static inline bool parentElementPreventsSharing(const Element* parentElement)
{
+ if (!parentElement)
+ return false;
return parentElement->hasFlagsSetDuringStylingOfChildren();
}
+Node* SharedStyleFinder::locateCousinList(Element* parent, unsigned& visitedNodeCount) const
+{
+ if (visitedNodeCount >= cStyleSearchThreshold * cStyleSearchLevelThreshold)
+ return 0;
+ if (!parent || !parent->isStyledElement())
+ return 0;
+ if (parent->hasScopedHTMLStyleChild())
+ return 0;
+ if (parent->inlineStyle())
+ return 0;
+ if (parent->isSVGElement() && toSVGElement(parent)->animatedSMILStyleProperties())
+ return 0;
+ if (parent->hasID() && m_features.idsInRules.contains(parent->idForStyleResolution().impl()))
+ return 0;
+ if (isShadowHost(parent) && parent->shadow()->containsActiveStyles())
+ return 0;
+
+ RenderStyle* parentStyle = parent->renderStyle();
+ unsigned subcount = 0;
+ Node* thisCousin = parent;
+ Node* currentNode = parent->previousSibling();
+
+ // Reserve the tries for this level. This effectively makes sure that the algorithm
+ // will never go deeper than cStyleSearchLevelThreshold levels into recursion.
+ visitedNodeCount += cStyleSearchThreshold;
+ while (thisCousin) {
+ while (currentNode) {
+ ++subcount;
+ if (!currentNode->hasScopedHTMLStyleChild() && currentNode->renderStyle() == parentStyle && currentNode->lastChild()
+ && currentNode->isElementNode() && !parentElementPreventsSharing(toElement(currentNode))
+ && !toElement(currentNode)->shadow()
+ ) {
+ // Adjust for unused reserved tries.
+ visitedNodeCount -= cStyleSearchThreshold - subcount;
+ return currentNode->lastChild();
+ }
+ if (subcount >= cStyleSearchThreshold)
+ return 0;
+ currentNode = currentNode->previousSibling();
+ }
+ currentNode = locateCousinList(thisCousin->parentElement(), visitedNodeCount);
+ thisCousin = currentNode;
+ }
+
+ return 0;
+}
+
+
bool SharedStyleFinder::canShareStyleWithControl(const ElementResolveContext& context, Element* element) const
{
if (!element->hasTagName(inputTag) || !context.element()->hasTagName(inputTag))
@@ -161,16 +214,9 @@
bool SharedStyleFinder::canShareStyleWithElement(const ElementResolveContext& context, Element* element) const
{
- if (context.element() == element)
- return false;
- Element* parent = element->parentElement();
RenderStyle* style = element->renderStyle();
if (!style)
return false;
- if (!parent)
- return false;
- if (context.element()->parentElement()->renderStyle() != parent->renderStyle())
- return false;
if (style->unique())
return false;
if (style->hasUniquePseudoStyle())
@@ -250,24 +296,22 @@
return false;
}
- if (context.element()->parentElement() != parent) {
- if (!parent->isStyledElement())
- return false;
- if (parent->hasScopedHTMLStyleChild())
- return false;
- if (parent->inlineStyle())
- return false;
- if (parent->isSVGElement() && toSVGElement(parent)->animatedSMILStyleProperties())
- return false;
- if (parent->hasID() && m_features.idsInRules.contains(parent->idForStyleResolution().impl()))
- return false;
- if (parentElementPreventsSharing(parent))
- return false;
- }
-
return true;
}
+inline Element* SharedStyleFinder::findSiblingForStyleSharing(const ElementResolveContext& context, Node* node, unsigned& count) const
+{
+ for (; node; node = node->previousSibling()) {
+ if (!node->isStyledElement())
+ continue;
+ if (canShareStyleWithElement(context, toElement(node)))
+ break;
+ if (count++ == cStyleSearchThreshold)
+ return 0;
+ }
+ return toElement(node);
+}
+
#ifdef STYLE_STATS
Element* SharedStyleFinder::searchDocumentForSharedStyle(const ElementResolveContext& context) const
{
@@ -279,28 +323,10 @@
}
#endif
-inline Element* SharedStyleFinder::findElementForStyleSharing(const ElementResolveContext& context) const
-{
- StyleSharingList& styleSharingList = m_styleResolver->styleSharingList();
- for (StyleSharingList::iterator iter = styleSharingList.begin(); iter != styleSharingList.end(); ++iter) {
- if (canShareStyleWithElement(context, *iter)) {
- Element* element = *iter;
- if (iter != styleSharingList.begin()) {
- // Move the element to the front of the LRU
- styleSharingList.remove(iter);
- styleSharingList.prepend(element);
- }
- return element;
- }
- }
- m_styleResolver->addToStyleSharingList(context.element());
- return 0;
-}
-
RenderStyle* SharedStyleFinder::locateSharedStyle(const ElementResolveContext& context, RenderStyle* newStyle)
{
STYLE_STATS_ADD_SEARCH();
- if (!context.element() || !context.element()->isStyledElement() || !context.element()->parentElement())
+ if (!context.element() || !context.element()->isStyledElement())
return 0;
// If the element has inline style it is probably unique.
@@ -344,7 +370,17 @@
// FIXME: This should be an explicit out parameter, instead of a member variable.
m_elementAffectedByClassRules = context.element() && context.element()->hasClass() && classNamesAffectedByRules(context.element()->classNames());
- Element* shareElement = findElementForStyleSharing(context);
+ // Check previous siblings and their cousins.
+ unsigned count = 0;
+ unsigned visitedNodeCount = 0;
+ Element* shareElement = 0;
+ Node* cousinList = context.element()->previousSibling();
+ while (cousinList) {
+ shareElement = findSiblingForStyleSharing(context, cousinList, count);
+ if (shareElement)
+ break;
+ cousinList = locateCousinList(cousinList->parentElement(), visitedNodeCount);
+ }
#ifdef STYLE_STATS
// FIXME: these stats don't to into account whether or not sibling/attribute
diff --git a/Source/core/css/resolver/SharedStyleFinder.h b/Source/core/css/resolver/SharedStyleFinder.h
index d407279..7734c36 100644
--- a/Source/core/css/resolver/SharedStyleFinder.h
+++ b/Source/core/css/resolver/SharedStyleFinder.h
@@ -51,7 +51,8 @@
RenderStyle* locateSharedStyle(const ElementResolveContext&, RenderStyle* newStyle);
private:
- Element* findElementForStyleSharing(const ElementResolveContext&) const;
+ Node* locateCousinList(Element* parent, unsigned& visitedNodeCount) const;
+ Element* findSiblingForStyleSharing(const ElementResolveContext&, Node*, unsigned& count) const;
// Only used when we're collecting stats on styles
Element* searchDocumentForSharedStyle(const ElementResolveContext&) const;
diff --git a/Source/core/css/resolver/StyleResolver.cpp b/Source/core/css/resolver/StyleResolver.cpp
index 8070d0f..9c2ca3b 100644
--- a/Source/core/css/resolver/StyleResolver.cpp
+++ b/Source/core/css/resolver/StyleResolver.cpp
@@ -243,18 +243,6 @@
m_uncommonAttributeRuleSet = makeRuleSet(m_features.uncommonAttributeRules);
}
-void StyleResolver::addToStyleSharingList(Element* element)
-{
- if (m_styleSharingList.size() >= styleSharingListSize)
- m_styleSharingList.remove(--m_styleSharingList.end());
- m_styleSharingList.prepend(element);
-}
-
-void StyleResolver::clearStyleSharingList()
-{
- m_styleSharingList.clear();
-}
-
void StyleResolver::pushParentElement(Element* parent)
{
const ContainerNode* parentsParent = parent->parentOrShadowHostElement();
diff --git a/Source/core/css/resolver/StyleResolver.h b/Source/core/css/resolver/StyleResolver.h
index 15db7d4..a8fd43f 100644
--- a/Source/core/css/resolver/StyleResolver.h
+++ b/Source/core/css/resolver/StyleResolver.h
@@ -36,7 +36,6 @@
#include "core/css/resolver/StyleBuilder.h"
#include "core/css/resolver/StyleResolverState.h"
#include "core/css/resolver/StyleResourceLoader.h"
-#include "wtf/Deque.h"
#include "wtf/HashMap.h"
#include "wtf/HashSet.h"
#include "wtf/RefPtr.h"
@@ -86,9 +85,6 @@
MatchOnlyUserAgentRules,
};
-const unsigned styleSharingListSize = 20;
-typedef WTF::Deque<Element*, styleSharingListSize> StyleSharingList;
-
#undef STYLE_STATS
#ifdef STYLE_STATS
@@ -279,11 +275,6 @@
const RuleFeatureSet& ruleFeatureSet() const { return m_features; }
- StyleSharingList& styleSharingList() { return m_styleSharingList; }
-
- void addToStyleSharingList(Element*);
- void clearStyleSharingList();
-
#ifdef STYLE_STATS
ALWAYS_INLINE static StyleSharingStats& styleSharingStats() { return m_styleSharingStats; }
#endif
@@ -367,8 +358,6 @@
StyleResourceLoader m_styleResourceLoader;
- StyleSharingList m_styleSharingList;
-
#ifdef STYLE_STATS
static StyleSharingStats m_styleSharingStats;
#endif
diff --git a/Source/core/dom/ContainerNode.cpp b/Source/core/dom/ContainerNode.cpp
index 0fb80f0..1b26b71 100644
--- a/Source/core/dom/ContainerNode.cpp
+++ b/Source/core/dom/ContainerNode.cpp
@@ -25,7 +25,6 @@
#include "bindings/v8/ExceptionState.h"
#include "bindings/v8/ExceptionStatePlaceholder.h"
-#include "core/css/resolver/StyleResolver.h"
#include "core/dom/ChildListMutationScope.h"
#include "core/dom/ContainerNodeAlgorithms.h"
#include "core/dom/EventNames.h"
@@ -683,8 +682,6 @@
if (s_postAttachCallbackQueue)
dispatchPostAttachCallbacks();
- if (StyleResolver* resolver = document()->styleResolverIfExists())
- resolver->clearStyleSharingList();
}
--s_attachDepth;
}
@@ -1039,8 +1036,6 @@
child->lazyAttach();
else
child->attach();
- if (StyleResolver* resolver = parent->document()->document()->styleResolverIfExists())
- resolver->clearStyleSharingList();
}
dispatchChildInsertionEvents(child);
diff --git a/Source/core/dom/Document.cpp b/Source/core/dom/Document.cpp
index 7be6a8e..9abe48b 100644
--- a/Source/core/dom/Document.cpp
+++ b/Source/core/dom/Document.cpp
@@ -1679,10 +1679,8 @@
m_inStyleRecalc = false;
// Pseudo element removal and similar may only work with these flags still set. Reset them after the style recalc.
- if (m_styleResolver) {
+ if (m_styleResolver)
m_styleSheetCollection->resetCSSFeatureFlags(m_styleResolver->ruleFeatureSet());
- m_styleResolver->clearStyleSharingList();
- }
if (frameView) {
frameView->resumeScheduledEvents();
diff --git a/Source/core/dom/Element.cpp b/Source/core/dom/Element.cpp
index 01190e0..a108336 100644
--- a/Source/core/dom/Element.cpp
+++ b/Source/core/dom/Element.cpp
@@ -1514,9 +1514,6 @@
change = Force;
else if (change != Force)
change = localChange;
- } else {
- // We still want to seed the style sharing list when just walking the tree to maximize sharing.
- document()->styleResolver()->addToStyleSharingList(this);
}
StyleResolverParentPusher parentPusher(this);
