79334 - Possible speed up of style data sharing

Status: RESOLVED FIXED

(Core :: CSS Parsing and Computation, defect)

Description

[rbs]

[Assigning to marc since pierre is away]

The current model of style data sharing that pierre implemented is limited
along descendants, i.e., a child style data can only inherit in the line of its
ancestors. Despite this apparent limited scope of sharing, the observed savings
have proved to be substantial, and pierre noted in bug 43457 that a further area
of investigation could be to see if more savings can be achieved by allowing
style data sharing on the overall style tree.

There is however an element in pierre's current implementation that is worthy
of consideration at this stage: looking at the code of the present model, by
convention, the inheritance is encoded by setting the child style data pointer
to null. So, whenever a style data pointer is null, it means that there is an
inheritance (or sharing) from the ancestor context for which the style data
pointer is non null. This means that to recover the actual values (during style
resolution or layout/paint), one has to grovel the style tree using the walking
function FetchInheritedStyle(), and I wonder if that function isn't showing up
high in the perf radar? There are thousands of style data and frames/reflows,
and everytime you do GetStyleData(color | display | etc.), up you go, grovelling
the style tree to fetch the values.

A possible alternative could be to alter the convention so that: 'sharing means
my data pointer is identical to my parent.' This way, the fetching functions
could become O(1).

Comment 1

[Marc Attinasi]

I'd love to see how FetchInheritedStyle shows up on a profile of a
style-intensive page...

Also, can't we actually pull shared data from some ancestor other than the
parent? If so,  how is storing the parent pointer going to help get us to O(1)?
We would still have to walk up an ancestor tree, looking for pointers that are
not equal to the parent, no? Maybe I'm confused...

Comment 2

[rbs]

>Also, can't we actually pull shared data from some ancestor other than the
>parent?

If that is the _current_ plan (sharing across the entire tree using a hash), 
then this bug is moot. But if that is a _future_ plan, then this bug is saying: 
"hmm... is there a low hanging fruit there while waiting for the grand plan?". 
But of course, if the cummulative time taken by the FetchInheritedStyleXXX isn't 
significant then the bug is already moot. And it would have only served the 
purpose of being filed in bugzilla for the record of attempted efforts to 
speedup Mozilla.

For clarification: this bug amounts to saying that, in the code-section that 
is testing for sharing, when the equality is detected between a parent data and 
a child data, set the child data pointer to the parent data pointer. This way, 
lookups at reflow/paint, which happen more than other things, will only "read" 
what has been resolved there. (But the burden is placed on the style resolution 
process which will have to kept the pointers up-to-date when changes occur.)

What the current scheme is doing is to set the child data pointer to null. And 
that's why one has to grovel the style tree to (re)fetch that pointer which was 
readily available at style resolution and could have been stashed away at that 
time.

Comment 3

[rbs]

Note: in my post "parent" doesn't necessarily mean the direct parent.

Given a style sub-tree:

anscestor -> grandparent -> parent -> child

If a style data (e.g., padding) is the same, the current code will do:

child.paddingPtr = parent.paddingPtr = grandparent.paddingPtr = null;
anscestor.paddingPtr = the-non-null-ptr; //from where the resolved values will
be fetched.

Hence, as more savings are made, longer the walk becomes. Whereas an alternative
could be to immediately set:

child.paddingPtr = parent.paddingPtr = grandparent.paddingPtr =
anscestor.paddingPtr = the-non-null-ptr //from where everybody will "read" the
resolved values.

Comment 4

[Marc Attinasi]

rbs, thanks for that last clarification, I understand now. I was thrown off by 
the term parent, but I get it. A tricky remaining issues now is that once an 
ancestor who's style is being shared is changed, all of the decendents that have 
that data ptr have to be nulled out or otherwise maintained (which I think you 
alluded to in your 2001-05-08 14:28 post).

I'd love to take a stab at this, as it would give me a chance to learn what 
Pierre did in more detail, and it could speed things up (depending on how the 
profiles show the fetching impact), but to be frank, I am swamped in more 
serious layout bugs at this time. I'll leave this in my list, but as NEW, in 
case some other brave soul wants to jump in and try it. Also, CC'ing glazman 
since he may be that brave soul...

Comment 5

[Hixie (not reading bugmail)]

Hyatt's changes are likely to make this irrelevant, no? We're already low enough
on manpower, I really think we should avoid working on anything that is likely
to become obsolete...

Comment 6

[rbs]

Agreed. hyatt appears to have made significant progress in his new scheme to
the point that it might be ready for general use soon. Time to give him
support/encouragements before PDT steps along and says "freeze", "no space left
on device... err... for crash landings", "time to ship", "high risk", (or other
keywords :-)

There may still be room for a style data library in hyatt's scheme, in the sense
that different rules may well generate the same data, i.e., "same" crc, meaning
only "one" atomic style data could be kept in the system at any one time,
especially in the context of multi-document sharing as marc once envisaged. This
will entail an additional cost (hashtables) but could guarantee that the memory
taken by the style system in most situations would grow mostly linearly, if at
all, no matter the number of open windows.

But as hixie rightly says, with the shrinking Gecko group, this time is best
used to focus on rewarding deliverables. Speculation is not for now. Let's dump
this bug in the "Future" bucket in case someone later wants to mutate the bug
into the exploration of the style data library idea.

Comment 7

[Pierre Saslawsky]

Made obsolete by bug 78695