RuleSet causes 600 kB of memory fragmentation

RuleSet causes 600 kB of memory fragmentation

RuleSet stores data as a HashMap from AtomicStringImpls to Vector<RuleData>.
When each CSS rule has a different class selector, each Vector is populated
with a single value. When you add the first value to a Vector, the Vector
pre-allocates 16 slots, which means there's 15 * sizeof(RuleData) wasted space.
We're smart and shrink these Vectors down to size, but that shrinkage doesn't
actually results in freeing up memory because of heap fragmentation.

This CL changes how we constructo RuleSet objects. During construction, we use
a LinkedStack, which lets us build each HashMap entry incrementally without
needing to preallocate a large number of moderately sized chunks. After we're
done building the RuleSet, we compact the representation back into Vectors. At
that time, we know exactly how large each Vector needs to be and we can size
them precisely to meet our needs.

This CL has two effects on memory usage:

1) Lower peek memory usage. When building the RuleSet, we no longer
   pre-allocate megabytes of Vector buffers.
2) Lower heap fragmentation. When compacting the RuleSet, we no longer leave
   thousands of holes in the heap.

I measured the impact of this change using CSS extracted from Mobile Gmail. On
the Mobile Gmail CSS, the VmRSS of the content_shell render process is 200 kB
smaller after this CL (measured on Linux).

Additionally, I wrote some synthetic CSS that contained 2000 empty CSS rules
with unique class name selectors. On that case, the VmRSS of the content_shell
render process after loading the page shrinks by 676 kB.

I also measured that the peek memory usage improvement was of a similar scale,
but I unfortunately don't have the data anymore.

R=ojan

Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=152839

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

Awesome! Couple comments...

https://codereview.chromium.org/17314010/diff/1/Source/core/css/RuleSet.cpp
File Source/core/css/RuleSet.cpp (right):

https://codereview.chromium.org/17314010/diff/1/Source/core/css/RuleSet.cpp#n...
Source/core/css/RuleSet.cpp:389: void
RuleSet::compactPendingRules(PendingRuleMap& pendingMap, CompactRuleMap&
compactMap)
nit: Why isn't this just static in the file? It doesn't seem like it needs to be
a method on the class.

https://codereview.chromium.org/17314010/diff/1/Source/core/css/RuleSet.cpp#n...
Source/core/css/RuleSet.cpp:394: size_t pendingSize = pendingRules->size();
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.

https://codereview.chromium.org/17314010/diff/1/Source/core/css/RuleSet.cpp#n...
Source/core/css/RuleSet.cpp:408: } while (!pendingRules->isEmpty());
I think regular while would be more clear, I don't know if saving the isEmpty()
call matters.

https://codereview.chromium.org/17314010/diff/1/Source/core/css/RuleSet.h
File Source/core/css/RuleSet.h (right):

https://codereview.chromium.org/17314010/diff/1/Source/core/css/RuleSet.h#new...
Source/core/css/RuleSet.h:166: inline void ensurePendingRules();
I don't think the inline here is needed?

https://codereview.chromium.org/17314010/diff/1/Source/wtf/LinkedStack.h
File Source/wtf/LinkedStack.h (right):

https://codereview.chromium.org/17314010/diff/1/Source/wtf/LinkedStack.h#newc...
Source/wtf/LinkedStack.h:31: #ifndef LinkedStack_h
I hate the git diff similarity stuff :/

https://codereview.chromium.org/17314010/diff/1/Source/wtf/LinkedStack.h#newc...
Source/wtf/LinkedStack.h:41: LinkedStack() { }
You can leave this out, we can use the default one.

https://codereview.chromium.org/17314010/diff/1/Source/wtf/LinkedStack.h#newc...
Source/wtf/LinkedStack.h:94: inline size_t LinkedStack<T>::size()
I'd rather we just store the size inside here. Having this thing be a little bit
bigger seems fine.

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

https://codereview.chromium.org/17314010/diff/1/Source/core/css/RuleSet.cpp
File Source/core/css/RuleSet.cpp (right):

https://codereview.chromium.org/17314010/diff/1/Source/core/css/RuleSet.cpp#n...
Source/core/css/RuleSet.cpp:213: bool RuleSet::findBestRuleSetAndAdd(const
CSSSelector* component, RuleData& ruleData)
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.

[ojan, 2013-06-20 22:39:03]

lgtm

[ojan, 2013-06-20 22:39:36]

On 2013/06/20 22:39:03, ojan wrote:
> lgtm

not lgtm

whoops, didn't see elliots comments.

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

https://codereview.chromium.org/17314010/diff/1/Source/core/css/RuleSet.cpp
File Source/core/css/RuleSet.cpp (right):

https://codereview.chromium.org/17314010/diff/1/Source/core/css/RuleSet.cpp#n...
Source/core/css/RuleSet.cpp:213: bool RuleSet::findBestRuleSetAndAdd(const
CSSSelector* component, RuleData& ruleData)
On 2013/06/20 22:38:45, ojan wrote:
> Should we ASSERT(m_pendingRules) here and in other places where we use it?

The ASSERT isn't really needed because the code will crash if m_pendingRules
isn't around.  :)

> Alternately, you could make ensurePendingRules return the m_pendingRules and
> have all the callers call ensurePendingRules. Not sure if the extra branching
> matters.

Yeah, I can do that if you like.

https://codereview.chromium.org/17314010/diff/1/Source/core/css/RuleSet.cpp#n...
Source/core/css/RuleSet.cpp:389: void
RuleSet::compactPendingRules(PendingRuleMap& pendingMap, CompactRuleMap&
compactMap)
On 2013/06/20 22:29:52, esprehn wrote:
> nit: Why isn't this just static in the file? It doesn't seem like it needs to
be
> a method on the class.

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.

https://codereview.chromium.org/17314010/diff/1/Source/core/css/RuleSet.cpp#n...
Source/core/css/RuleSet.cpp:394: size_t pendingSize = pendingRules->size();
On 2013/06/20 22:29:52, esprehn wrote:
> 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.

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

https://codereview.chromium.org/17314010/diff/1/Source/core/css/RuleSet.cpp#n...
Source/core/css/RuleSet.cpp:408: } while (!pendingRules->isEmpty());
On 2013/06/20 22:29:52, esprehn wrote:
> I think regular while would be more clear, I don't know if saving the
isEmpty()
> call matters.

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

https://codereview.chromium.org/17314010/diff/1/Source/core/css/RuleSet.h
File Source/core/css/RuleSet.h (right):

https://codereview.chromium.org/17314010/diff/1/Source/core/css/RuleSet.h#new...
Source/core/css/RuleSet.h:166: inline void ensurePendingRules();
On 2013/06/20 22:29:52, esprehn wrote:
> I don't think the inline here is needed?

The function is called in addRule.  I don't know whether it's needed, but I
might as well encourage the compiler to inline the function.  :)

https://codereview.chromium.org/17314010/diff/1/Source/wtf/LinkedStack.h
File Source/wtf/LinkedStack.h (right):

https://codereview.chromium.org/17314010/diff/1/Source/wtf/LinkedStack.h#newc...
Source/wtf/LinkedStack.h:41: LinkedStack() { }
On 2013/06/20 22:29:52, esprehn wrote:
> You can leave this out, we can use the default one.

Very true.

https://codereview.chromium.org/17314010/diff/1/Source/wtf/LinkedStack.h#newc...
Source/wtf/LinkedStack.h:94: inline size_t LinkedStack<T>::size()
On 2013/06/20 22:29:52, esprehn wrote:
> I'd rather we just store the size inside here. Having this thing be a little
bit
> bigger seems fine.

Ok.

[esprehn, 2013-06-20 22:57:14]

On 2013/06/20 22:52:31, abarth wrote:
> ...
> 
> 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.

Ah yeah, lets leave it as a member then.

> 
>
https://codereview.chromium.org/17314010/diff/1/Source/core/css/RuleSet.cpp#n...
> Source/core/css/RuleSet.cpp:394: size_t pendingSize = pendingRules->size();
> On 2013/06/20 22:29:52, esprehn wrote:
> > 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.
> 
> Sure, I can do that.  My thinking was that we're going to walk the whole list
> anyway in a moment.

Walking the list twice is seems less expensive than doing it once (I'd assume?),
but maybe these lists are so small it doesn't matter. Whatever you think is
best.

> 
>
https://codereview.chromium.org/17314010/diff/1/Source/core/css/RuleSet.cpp#n...
> Source/core/css/RuleSet.cpp:408: } while (!pendingRules->isEmpty());
> On 2013/06/20 22:29:52, esprehn wrote:
> > I think regular while would be more clear, I don't know if saving the
> isEmpty()
> > call matters.
> 
> Will fix.  I was excited to be able to use a do...while loop.  They're so
rare!

Haha, you can leave if you'd like.

> 
> https://codereview.chromium.org/17314010/diff/1/Source/core/css/RuleSet.h
> File Source/core/css/RuleSet.h (right):
> 
>
https://codereview.chromium.org/17314010/diff/1/Source/core/css/RuleSet.h#new...
> Source/core/css/RuleSet.h:166: inline void ensurePendingRules();
> On 2013/06/20 22:29:52, esprehn wrote:
> > I don't think the inline here is needed?
> 
> The function is called in addRule.  I don't know whether it's needed, but I
> might as well encourage the compiler to inline the function.  :)

Can we put the implementation in the header file then?

[abarth-chromium, 2013-06-20 23:00:23]

On 2013/06/20 22:57:14, esprehn wrote:
> On 2013/06/20 22:52:31, abarth wrote:
> > The function is called in addRule.  I don't know whether it's needed, but I
> > might as well encourage the compiler to inline the function.  :)
> 
> Can we put the implementation in the header file then?

Sure.

[adamk, 2013-06-20 23:05:29]

On 2013/06/20 23:00:23, abarth wrote:
> On 2013/06/20 22:57:14, esprehn wrote:
> > On 2013/06/20 22:52:31, abarth wrote:
> > > The function is called in addRule.  I don't know whether it's needed, but
I
> > > might as well encourage the compiler to inline the function.  :)
> > 
> > Can we put the implementation in the header file then?
> 
> Sure.

Sorry for the drive-by, but why move it to the header? In general, it seems like
we should prefer code in .cpp to code in .h files. I'm confused about how this
line of thought went.

[abarth-chromium, 2013-06-20 23:10:48]

On 2013/06/20 23:05:29, adamk wrote:
> Sorry for the drive-by, but why move it to the header? In general, it seems
like
> we should prefer code in .cpp to code in .h files. I'm confused about how this
> line of thought went.

Apparently the "inline" keyword means that you promise the compiler that the
definition is available in the translation unit (at least according to
jyasskin).  Putting the definition in the CPP is kind of cheating the system,
but the compiler lets you get away with it as long as you don't try to call the
function from another translation unit.

[adamk, 2013-06-20 23:11:40]

On 2013/06/20 23:05:29, adamk wrote:
> On 2013/06/20 23:00:23, abarth wrote:
> > On 2013/06/20 22:57:14, esprehn wrote:
> > > On 2013/06/20 22:52:31, abarth wrote:
> > > > The function is called in addRule.  I don't know whether it's needed,
but
> I
> > > > might as well encourage the compiler to inline the function.  :)
> > > 
> > > Can we put the implementation in the header file then?
> > 
> > Sure.
> 
> Sorry for the drive-by, but why move it to the header? In general, it seems
like
> we should prefer code in .cpp to code in .h files. I'm confused about how this
> line of thought went.

After in-person discussion with esprehn, it seems he's mostly worried about
weird linker errors in the future if someone manages to call this method from a
different source file (say, if someone else becomes a friend of this class).
Seems reasonable to me, linker errors can indeed be mysterious.

[abarth-chromium, 2013-06-20 23:12:43]

PTAL

[ojan, 2013-06-20 23:29:25]

lgtm

[commit-bot: I haz the power, 2013-06-20 23:31:42]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/abarth@chromium.org/17314010/18001

[commit-bot: I haz the power, 2013-06-21 01:03:28]

Change committed as 152839