RuleSet causes 600 kB of memory fragmentation

Source/core/css/RuleSet.cpp

 /*
  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
  *           (C) 2004-2005 Allan Sandfeld Jensen (kde@carewolf.com)
  * Copyright (C) 2006, 2007 Nicholas Shanks (webkit@nickshanks.com)
  * Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012 Apple Inc. All rights reserved.
  * Copyright (C) 2007 Alexey Proskuryakov <ap@webkit.org>
  * Copyright (C) 2007, 2008 Eric Seidel <eric@webkit.org>
  * Copyright (C) 2008, 2009 Torch Mobile Inc. All rights reserved. (http://www.torchmobile.com/)
  * Copyright (c) 2011, Code Aurora Forum. All rights reserved.
  * Copyright (C) Research In Motion Limited 2011. All rights reserved.
@@ skipping 182 matching lines @@
             }
         } else if (!foundSiblingSelector && selector->isSiblingSelector())
             foundSiblingSelector = true;
     }
     if (foundSiblingSelector)
         features.siblingRules.append(RuleFeature(ruleData.rule(), ruleData.selectorIndex(), ruleData.hasDocumentSecurityOrigin()));
     if (ruleData.containsUncommonAttributeSelector())
         features.uncommonAttributeRules.append(RuleFeature(ruleData.rule(), ruleData.selectorIndex(), ruleData.hasDocumentSecurityOrigin()));
 }
     
-void RuleSet::addToRuleSet(AtomicStringImpl* key, AtomRuleMap& map, const RuleData& ruleData)
+void RuleSet::addToRuleSet(AtomicStringImpl* key, PendingRuleMap& map, const RuleData& ruleData)
 {
     if (!key)
         return;
-    OwnPtr<Vector<RuleData> >& rules = map.add(key, nullptr).iterator->value;
+    OwnPtr<LinkedStack<RuleData> >& rules = map.add(key, nullptr).iterator->value;
     if (!rules)
-        rules = adoptPtr(new Vector<RuleData>);
-    rules->append(ruleData);
+        rules = adoptPtr(new LinkedStack<RuleData>);
+    rules->push(ruleData);
 }
 
 bool RuleSet::findBestRuleSetAndAdd(const CSSSelector* component, RuleData& ruleData)

[ojan, 2013/06/20 22:38:45]

Should we ASSERT(m_pendingRules) here and in other places where we use it?
Alternately, you could make ensurePendingRules return the m_pendingRules and
have all the callers call ensurePendingRules. Not sure if the extra branching
matters.

[abarth-chromium, 2013/06/20 22:52:32]

The ASSERT isn't really needed because the code will crash if m_pendingRules
isn't around.  :)
Yeah, I can do that if you like.

 {
     if (component->m_match == CSSSelector::Id) {
-        addToRuleSet(component->value().impl(), m_idRules, ruleData);
+        addToRuleSet(component->value().impl(), m_pendingRules->idRules, ruleData);
         return true;
     }
     if (component->m_match == CSSSelector::Class) {
-        addToRuleSet(component->value().impl(), m_classRules, ruleData);
+        addToRuleSet(component->value().impl(), m_pendingRules->classRules, ruleData);
         return true;
     }
     if (component->isCustomPseudoElement()) {
-        addToRuleSet(component->value().impl(), m_shadowPseudoElementRules, ruleData);
+        addToRuleSet(component->value().impl(), m_pendingRules->shadowPseudoElementRules, ruleData);
         return true;
     }
     if (component->pseudoType() == CSSSelector::PseudoCue) {
         m_cuePseudoRules.append(ruleData);
         return true;
     }
     if (SelectorChecker::isCommonPseudoClassSelector(component)) {
         switch (component->pseudoType()) {
         case CSSSelector::PseudoLink:
         case CSSSelector::PseudoVisited:
@@ skipping 10 matching lines @@
     }
 
     if (component->m_match == CSSSelector::Tag) {
         if (component->tagQName().localName() != starAtom) {
             // If this is part of a subselector chain, recurse ahead to find a narrower set (ID/class.)
             if (component->relation() == CSSSelector::SubSelector
                 && (component->tagHistory()->m_match == CSSSelector::Class || component->tagHistory()->m_match == CSSSelector::Id || SelectorChecker::isCommonPseudoClassSelector(component->tagHistory()))
                 && findBestRuleSetAndAdd(component->tagHistory(), ruleData))
                 return true;
 
-            addToRuleSet(component->tagQName().localName().impl(), m_tagRules, ruleData);
+            addToRuleSet(component->tagQName().localName().impl(), m_pendingRules->tagRules, ruleData);
             return true;
         }
     }
     return false;
 }
 
 void RuleSet::addRule(StyleRule* rule, unsigned selectorIndex, AddRuleFlags addRuleFlags)
 {
-    m_hasDirtyRules = true;
+    ensurePendingRules();
     RuleData ruleData(rule, selectorIndex, m_ruleCount++, addRuleFlags);
     collectFeaturesFromRuleData(m_features, ruleData);
 
     if (!findBestRuleSetAndAdd(ruleData.selector(), ruleData)) {
         // If we didn't find a specialized map to stick it in, file under universal rules.
         m_universalRules.append(ruleData);
     }
 }
 
 void RuleSet::addPageRule(StyleRulePage* rule)
 {
-    m_hasDirtyRules = true;
+    ensurePendingRules();
     m_pageRules.append(rule);
 }
 
 void RuleSet::addRegionRule(StyleRuleRegion* regionRule, bool hasDocumentSecurityOrigin)
 {
-    m_hasDirtyRules = true;
+    ensurePendingRules();
     OwnPtr<RuleSet> regionRuleSet = RuleSet::create();
     // The region rule set should take into account the position inside the parent rule set.
     // Otherwise, the rules inside region block might be incorrectly positioned before other similar rules from
     // the stylesheet that contains the region block.
     regionRuleSet->m_ruleCount = m_ruleCount;
 
     // Collect the region rules into a rule set
     // FIXME: Should this add other types of rules? (i.e. use addChildRules() directly?)
     const Vector<RefPtr<StyleRuleBase> >& childRules = regionRule->childRules();
     AddRuleFlags addRuleFlags = hasDocumentSecurityOrigin ? RuleHasDocumentSecurityOrigin : RuleHasNoSpecialState;
@@ skipping 79 matching lines @@
 
     addChildRules(sheet->childRules(), medium, resolver, scope, hasDocumentSecurityOrigin, addRuleFlags);
 }
 
 void RuleSet::addStyleRule(StyleRule* rule, AddRuleFlags addRuleFlags)
 {
     for (size_t selectorIndex = 0; selectorIndex != notFound; selectorIndex = rule->selectorList().indexOfNextSelectorAfter(selectorIndex))
         addRule(rule, selectorIndex, addRuleFlags);
 }
 
-void RuleSet::shrinkMapVectorsToFit(AtomRuleMap& map)
+void RuleSet::ensurePendingRules()
 {
-    RuleSet::AtomRuleMap::iterator end = map.end();
-    for (RuleSet::AtomRuleMap::iterator it = map.begin(); it != end; ++it)
-        it->value->shrinkToFit();
+    if (m_pendingRules)
+        return;
+    m_pendingRules = adoptPtr(new PendingRuleMaps);
 }
 
-void RuleSet::shrinkToFit()
+void RuleSet::compactPendingRules(PendingRuleMap& pendingMap, CompactRuleMap& compactMap)

[esprehn, 2013/06/20 22:29:52]

nit: Why isn't this just static in the file? It doesn't seem like it needs to be
a method on the class.

[abarth-chromium, 2013/06/20 22:52:32]

The PendingRuleMap and CompactRuleMap types are private to the class.  I could
make them non-private or make this function a friend, but having it a member
seemed easier.

 {
-    m_hasDirtyRules = false;
-    shrinkMapVectorsToFit(m_idRules);
-    shrinkMapVectorsToFit(m_classRules);
-    shrinkMapVectorsToFit(m_tagRules);
-    shrinkMapVectorsToFit(m_shadowPseudoElementRules);
+    PendingRuleMap::iterator end = pendingMap.end();
+    for (PendingRuleMap::iterator it = pendingMap.begin(); it != end; ++it) {
+        OwnPtr<LinkedStack<RuleData> > pendingRules = it->value.release();
+        size_t pendingSize = pendingRules->size();

[esprehn, 2013/06/20 22:29:52]

This is O(n), why not just keep the size of the linked stack inside the
LinkedStack? We don't care about the minor memory usage from that.

[abarth-chromium, 2013/06/20 22:52:32]

Sure, I can do that.  My thinking was that we're going to walk the whole list
anyway in a moment.

+        ASSERT(pendingSize);
+
+        OwnPtr<Vector<RuleData> >& compactRules = compactMap.add(it->key, nullptr).iterator->value;
+        if (!compactRules) {
+            compactRules = adoptPtr(new Vector<RuleData>);
+            compactRules->reserveInitialCapacity(pendingSize);
+        } else {
+            compactRules->reserveCapacity(pendingRules->size() + pendingSize);
+        }
+
+        do {
+            compactRules->append(pendingRules->peek());
+            pendingRules->pop();
+        } while (!pendingRules->isEmpty());

[esprehn, 2013/06/20 22:29:52]

I think regular while would be more clear, I don't know if saving the isEmpty()
call matters.

[abarth-chromium, 2013/06/20 22:52:32]

Will fix.  I was excited to be able to use a do...while loop.  They're so rare!

+
+        ASSERT(compactRules->size() == compactRules->capacity());
+    }
+}
+
+void RuleSet::compactRules()
+{
+    OwnPtr<PendingRuleMaps> pendingRules = m_pendingRules.release();
+    compactPendingRules(pendingRules->idRules, m_idRules);
+    compactPendingRules(pendingRules->classRules, m_classRules);
+    compactPendingRules(pendingRules->tagRules, m_tagRules);
+    compactPendingRules(pendingRules->shadowPseudoElementRules, m_shadowPseudoElementRules);
     m_linkPseudoClassRules.shrinkToFit();
     m_cuePseudoRules.shrinkToFit();
     m_focusPseudoClassRules.shrinkToFit();
     m_universalRules.shrinkToFit();
     m_pageRules.shrinkToFit();
 }
 
 } // namespace WebCore