242044 - Reduce number of allocations by nsSpaceManager::PushState

Status: RESOLVED FIXED

(Core :: Layout, defect)

Description

[jim_nance]

The following patch reduces the number of memory allocations done by
nsStateManager::PushState.  These allocations where showing up in jprofs I was
doing and the patched code shows a significant reduction in
allocation/deallocation times.

The patch does two things:

1 - We allocate one SpaceManagerState object inside the nsSpaceManager class. 
This drastically reduced our allocations because most of the time the stack only
has a depth of 1.

2 - Instead of freeing each SpaceManagerState which we pop in PopStack, we keep
it on the linked list of states, and just move a pointer back to the prior
object.  This means that if someone then does a PushState, we can just advance
the pointer.  We do not have to do an allocation.

Here are the jprof numbers:

Original:
Total hit count: 7937
Count %Total  Function Name
188   2.4     _int_malloc
182   2.3     nsCellMap::GetDataAt(nsTableCellMap&, int, int, int)
127   1.6     nsStyleContext::GetStyleData(nsStyleStructID)
121   1.5     nsCellMap::GetCellInfoAt(nsTableCellMap&, int, int, int*, int*)
112   1.4     free
107   1.3     __libc_malloc
107   1.3     nsRuleNode::GetStyleData(nsStyleStructID, nsStyleContext*, int)
 91   1.1     SearchTable
 74   0.9     malloc_consolidate
 70   0.9     nsCellMap::GetEffectiveColSpan(nsTableCellMap&, int, int, int&)
 69   0.9     GlobalWindowImpl::QueryInterface(nsID const&, void**)
 68   0.9     nsLineLayout::ReflowFrame(nsIFrame*, unsigned&, nsHTMLReflowMetr

New:
Total hit count: 7493
Count %Total  Function Name
169   2.3     nsCellMap::GetDataAt(nsTableCellMap&, int, int, int)
129   1.7     _int_malloc
112   1.5     nsStyleContext::GetStyleData(nsStyleStructID)
101   1.3     nsCellMap::GetCellInfoAt(nsTableCellMap&, int, int, int*, int*)
 90   1.2     SearchTable
 85   1.1     nsRuleNode::GetStyleData(nsStyleStructID, nsStyleContext*, int)
 85   1.1     __libc_malloc
 74   1.0     malloc_consolidate
 72   1.0     free
 71   0.9     SelectorMatches(RuleProcessorData&, nsCSSSelector*, int, nsIAtom*
 65   0.9     nsLineLayout::ReflowFrame(nsIFrame*, unsigned&, nsHTMLReflowMetri

Note how much lower _int_malloc() and free() appear in the patched jprofs.  I
would like to check this code in.  Who are the appropriate people to ask for
reviews?

Comment 1

[jim_nance]

Attachment: Allocation reduction path

Comment 2

[jim_nance]

I just noticed that the patch changes the code to call maincallback().  This is
debugging code and it should not be in the patch.  I just put it there to give
gdb a place to stop.  I will be removed in the final version.

Comment 3

[Boris Zbarsky [:bzbarsky]]

Jim, this list could get rather long if a page has a lot of nested positioned
blocks...  Perhaps we should flush it on memory pressure notifications?

Comment 4

[jim_nance]

Borris, do you have a page I could test with.  It is certainly possible to do
what you suggest, but there is a definite complexity hit.  How deep do you think
this could get?

Comment 5

[Boris Zbarsky [:bzbarsky]]

As I understand it, we push a new space manager any time we have a nested block
formatting context (see
http://www.w3.org/TR/CSS21/visuren.html#block-formatting).  So theoretically, as
deep as a few hundred entries (that being our limit on frame nesting depth, as I
recall).

dbaron knows this code better than I, which is why I cced him...

Comment 6

[David Baron :dbaron: (⌚️UTC-5, no longer working on Mozilla)]

But that's unrelated to PushState and PopState, which are for when we need to
throw away stuff related to an "unconstrained" reflow -- i.e., one used to
calculate maximum width rather than do layout.  They probably shouldn't ever
*need* to nest (well, they shouldn't need to exist at all), but they do
sometimes.  But I suspect nesting deeply is rare.

Comment 7

[Boris Zbarsky [:bzbarsky]]

Oh, ok.  In that case, disregard comment 3.  ;)

Comment 8

[jim_nance]

Attachment: Patch with debugging code removed

I removed the debugging code from the patch.  I would like to check it in.

Comment 9

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 147355 [details] [diff] [review]
Patch with debugging code removed

Jim, I'm not doing srs actively... this should be just fine with an r+sr from
David.

Comment 10

[jim_nance]

David, given your description of how this code is used, I am supprised that we
are calling it enough for it to show up so promently in the profile.  The test
page is just bonsi output.

Comment 11

[David Baron :dbaron: (⌚️UTC-5, no longer working on Mozilla)]

Pushing and popping once is quite frequent -- it should happen for every table
cell and every 'width: auto' float or positioned element.  pushing and popping
more than one item on the stack should never be needed in theory but we might do
it occasionally.  So I suspect the main win is the single item.

Space managers are also very short-lived (just during reflow), so I'm not sure
whether logic to cache malloced space managers is worth it.  I'm not even sure
if there are any real cases where we'd nest more than one state on the stack,
since most interesting layout cases (table cells, floats, positioned elements)
will create a new space manager.  Putting in a few printfs and browsing through
a few pages might lead to some useful information on which parts of this code
are useful.

Comment 12

[jim_nance]

I put printfs in when I was developing this patch.  As you say, the stack never
gets beyond 1 deep, but we do push it a lot.  The speedup is definitly caused by
having the first stack element inside the class, not by defering the deletion.

Would you like me to remove the defered deletion part of the change?  It is
about the same complexity either way, but it does behave more like the original
w/o that part of the patch.

Comment 13

[jim_nance]

Attachment: Patch that only embeds the first list element in the object

Since we are getting all of our speedup from the portion of the patch which
embeds the first stack element into the class, and none from the part the
changes how deallocations are cached, I have simplified the patch so that it
ONLY does the embeding.  The cache of previously allocated stack elements is
gone.

Comment 14

[David Baron :dbaron: (⌚️UTC-5, no longer working on Mozilla)]

Comment on attachment 148788 [details] [diff] [review]
Patch that only embeds the first list element in the object

>   while (mSavedStates){
>+    if(mSavedStates == &mAutoState)
>+      break;

r+sr=dbaron if you fix this to just be

  while (mSavedStates && mSavedStates != &mAutoState) {

Comment 15

[jim_nance]

Checked in the patch with dbaron's changes