RuleSet causes 600 kB of memory fragmentation

Source/core/css/RuleSet.cpp

Index: Source/core/css/RuleSet.cpp
diff --git a/Source/core/css/RuleSet.cpp b/Source/core/css/RuleSet.cpp
index a08c06c7676b3fd6617e5eb3798d7bf6fe4e6724..3ea0504d4ebd207d96cd4ed8dbc0bf21049c1331 100644
--- a/Source/core/css/RuleSet.cpp
+++ b/Source/core/css/RuleSet.cpp
@@ -200,28 +200,28 @@ static void collectFeaturesFromRuleData(RuleFeatureSet& features, const RuleData
         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) {
@@ -252,7 +252,7 @@ bool RuleSet::findBestRuleSetAndAdd(const CSSSelector* component, RuleData& rule
                 && 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;
         }
     }
@@ -261,7 +261,7 @@ bool RuleSet::findBestRuleSetAndAdd(const CSSSelector* component, RuleData& rule
 
 void RuleSet::addRule(StyleRule* rule, unsigned selectorIndex, AddRuleFlags addRuleFlags)
 {
-    m_hasDirtyRules = true;
+    ensurePendingRules();
     RuleData ruleData(rule, selectorIndex, m_ruleCount++, addRuleFlags);
     collectFeaturesFromRuleData(m_features, ruleData);
 
@@ -273,13 +273,13 @@ void RuleSet::addRule(StyleRule* rule, unsigned selectorIndex, AddRuleFlags addR
 
 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
@@ -379,20 +379,45 @@ void RuleSet::addStyleRule(StyleRule* rule, AddRuleFlags addRuleFlags)
         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::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.

+{
+    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::shrinkToFit()
+void RuleSet::compactRules()
 {
-    m_hasDirtyRules = false;
-    shrinkMapVectorsToFit(m_idRules);
-    shrinkMapVectorsToFit(m_classRules);
-    shrinkMapVectorsToFit(m_tagRules);
-    shrinkMapVectorsToFit(m_shadowPseudoElementRules);
+    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();