Bug 86434

Summary: RuleSet::addToRuleSet wastes a bit of Vector capacity
Product: WebKit Reporter: Simon Fraser (smfr) <simon.fraser>
Component: CSSAssignee: Nobody <webkit-unassigned>
Status: RESOLVED FIXED    
Severity: Normal CC: darin, kling, koivisto, macpherson, menard, simon.fraser, webkit.review.bot
Priority: P2    
Version: 528+ (Nightly build)   
Hardware: Unspecified   
OS: Unspecified   
Bug Depends on:    
Bug Blocks: 86281    
Attachments:
Description Flags
Proposed patch koivisto: review+

Description Simon Fraser (smfr) 2012-05-14 21:40:53 PDT
Data collected via bug 86281 show that RuleSet::addToRuleSet() is the most wasteful call site for excess vector capacity.
Comment 1 Andreas Kling 2012-05-14 21:44:18 PDT
Hm. This is somewhat surprising since we shrinkToFit() most of the vectors in RuleSet::shrinkToFit(). Something must be going wrong here. :/
Comment 2 Antti Koivisto 2012-05-15 01:30:28 PDT
Simon, does your logging work correctly when shrinkToFit is used?
Comment 3 Simon Fraser (smfr) 2012-05-15 08:14:07 PDT
Apparently not (you can see the patch in bug 86281).
Comment 4 Simon Fraser (smfr) 2012-05-15 08:44:31 PDT
Previous data was not taking shrinkToFit into account. New data shows addToRuleSet() to be a lot less wasteful, but there is one stack that shows up in the top 20:

117 vectors, 7.11KB used of 73.12KB, 66.02KB wasted at:
1   0x108c1a255 WTF::Vector<WebCore::RuleData, 0ul>::Vector()
2   0x108c07a55 WTF::Vector<WebCore::RuleData, 0ul>::Vector()
3   0x108bfb4e1 WebCore::RuleSet::addToRuleSet(WTF::AtomicStringImpl*, WTF::HashMap<WTF::AtomicStringImpl*, WTF::OwnPtr<WTF::Vector<WebCore::RuleData, 0ul> >, WTF::PtrHash<WTF::AtomicStringImpl*>, WTF::HashTraits<WTF::AtomicStringImpl*>, WTF::HashTraits<WTF::OwnPtr<WTF::Vector<WebCore::RuleData, 0ul> > > >&, WebCore::RuleData const&)
4   0x108bfb6fb WebCore::RuleSet::addRule(WebCore::StyleRule*, WebCore::CSSSelector*, bool, bool, bool)
5   0x108beac71 _ZN7WebCoreL11makeRuleSetERKN3WTF6VectorINS_13StyleResolver11RuleFeatureELm0EEE
Comment 5 Andreas Kling 2012-05-15 08:52:28 PDT
Created attachment 141983 [details]
Proposed patch
Comment 6 Antti Koivisto 2012-05-15 09:09:01 PDT
Comment on attachment 141983 [details]
Proposed patch

View in context: https://bugs.webkit.org/attachment.cgi?id=141983&action=review

r=me

> Source/WebCore/ChangeLog:3
> +        RuleSet::addToRuleSet wastes a lot of Vector capacity.

You might want to update the title. This hardly wastes "a lot".
Comment 7 Andreas Kling 2012-05-15 09:45:35 PDT
Committed r117084: <http://trac.webkit.org/changeset/117084>
Comment 8 Darin Adler 2012-05-15 09:50:22 PDT
In cases like this where we know the size the RuleSet will be before we create it, it would be more efficient to reserve capacity than to shrink to fit. All we’d have to do is make a RuleSet::create function overload that takes a capacity.

What do you guys think of that idea?
Comment 9 Darin Adler 2012-05-15 09:54:45 PDT
Well maybe this is the only call site like that; the point is that you save more memory by not allocating the larger block and shrinking. I suspect that in many cases the memory saved by shrinking after the fact can’t be reused due to fragmentation.
Comment 10 Andreas Kling 2012-05-15 09:58:42 PDT
(In reply to comment #8)
> In cases like this where we know the size the RuleSet will be before we create it, it would be more efficient to reserve capacity than to shrink to fit. All we’d have to do is make a RuleSet::create function overload that takes a capacity.
> 
> What do you guys think of that idea?

I like the idea in principle. If you look at the implementation of RuleSet::shrinkToFit() however, it's nontrivial to predict at RuleSet::create() time how big each subvector should be.
Comment 11 Darin Adler 2012-05-15 10:03:28 PDT
OK. Got it.
Comment 12 Darin Adler 2012-05-15 10:03:59 PDT
One last thought on this: The prediction can be wrong some of the time as long as it’s right most of the time.