Lazy frame construction
Boris Zbarsky
It's common for tests and webpages to bounce a single DOM node in and
out of the tree a bunch of times in a row. Right now we
construct/destroy frames for it each time it's inserted/removed. It
would be nice to not do that.
Webkit implements a limited form of laziness in creating its
RenderObjects. If the insertion is via a DOM call from JS (as opposed
to from the parser, say), then instead of creating a RenderObject they
just flag the node as needing a renderobject created, flag its ancestors
as having such a descendant, and return. At least as far as I can tell.
Then later they walk the tree, limiting to subtrees that have a
descendant needing RenderObject creation, and create the RenderObjects.
It looks like this is the way they handle style changes in general,
actually; the "needs creation" is just a style change value.
In Gecko, style changes are instead handled via a hashtable of objects
to style changes. When it comes to processing the style changes, we
enumerate the hashtable. So order is not guaranteed in particular.
Implementation thoughts on lazy frame construction:
We could adopt an approach similar to webkit's: When a node is inserted
(esp. via the DOM from JS), just post a "create a frame" restyle event,
then process it as normal when processing restyles. This might lead to
lots of restyle events, and frames being constructed in sub-optimal
orders. So it would be nice to coalesce the construction operations
somehow. The questions then are:
1) How to keep track of which nodes need frames constructed?
2) How to actually construct the frames reasonably?
3) Which set of DOM mutations to apply all this to (e.g., should we
coalesce stuff that comes in from the parser?).
-Boris
Robert O'Callahan
remove the element from mPendingRestyles immediately? Right now it looks
like the element is kept alive until we next process restyles, which
could cause an arbitrary amount of memory overhead.
Another question: does mPendingRestyles have any advantages over the
Webkit approach? I guess DOM tree traversal might be a little slower
when you have elements with many children and only a few nodes to
restyle. And I guess it wouldn't work with the way we currently do
native anonymous content. But does it matter? I guess it also wouldn't
work with multiple presentations, but Olli's patch to make that go away
is nearly finished.
A related question: right now, is there anything that quashes restyling
of an element when it has an ancestor that has reconstructed (or will
reconstruct) its frame subtree?
On 19/09/09 5:50 AM, Boris Zbarsky wrote:
> 1) How to keep track of which nodes need frames constructed?
> 2) How to actually construct the frames reasonably?
Currently we walk mPendingRestyles and copy the elements into a list.
While we're doing that, we could populate an auxiliary hashtable that
maps an element to a set of its children which may need frame creation.
Then we could walk that hashtable and for each element, scan its child
list locating the indices of the children needing frame creation, and
issuing ContentInserted or ContentAppended notifications along the way.
I presume because we sometimes need to reconstruct frames for
containers, e.g. WipeContainingBlock, there is a preferred order to
visit the elements whose children need frame creation, but what is that
order? Maybe it's not worth computing.
Rob
Boris Zbarsky
> One question: when an element is removed from the document, should we
> remove the element from mPendingRestyles immediately? Right now it looks
> like the element is kept alive until we next process restyles, which
> could cause an arbitrary amount of memory overhead.
I think we should do that, yes. That won't help if the element's
_parent_ is removed, but it should help the common "bounce an element in
and out of the DOM" case.
> Another question: does mPendingRestyles have any advantages over the
> Webkit approach?
This is a really really good question. ;) I don't know. They have
very different pathological behaviors. I would not be averse to trying
the webkit approach, in general, and seeing what things look like.
> And I guess it wouldn't work with the way we currently do
> native anonymous content. But does it matter?
I suspect no; we shouldn't really be directly restyling native anon
content, I would think... That's not to say someone like editor doesn't
do it, of course.
We'd need to walk the XBL flattened tree, of course, not just the DOM.
That makes the traversal a little slower, but hopefully not much.
> I guess it also wouldn't
> work with multiple presentations, but Olli's patch to make that go away
> is nearly finished.
Right.
> A related question: right now, is there anything that quashes restyling
> of an element when it has an ancestor that has reconstructed (or will
> reconstruct) its frame subtree?
We quash restyling due to possible style changes (as in, we don't
ReResolveStyleContext on subtrees rooted at elements that ended up with
a reconstruct hint), but we don't quash explicitly-posted hints of the
sort that I was thinking of here.
Note also https://bugzilla.mozilla.org/show_bug.cgi?id=479655#c0 might
be relevant here.
> Currently we walk mPendingRestyles and copy the elements into a list.
> While we're doing that, we could populate an auxiliary hashtable that
> maps an element to a set of its children which may need frame creation.
Sorted in content order or something?
> Then we could walk that hashtable and for each element, scan its child
> list locating the indices of the children needing frame creation, and
> issuing ContentInserted or ContentAppended notifications along the way.
Hey, if we switched DOM's child storage we wouldn't need the "locating
the indices" bit... ;)
But yes, this could work; I just worry about the performance. I guess
it might not be any worse than the simple thing.
> I presume because we sometimes need to reconstruct frames for
> containers, e.g. WipeContainingBlock, there is a preferred order to
> visit the elements whose children need frame creation, but what is that
> order? Maybe it's not worth computing.
That's hard, yeah. I think the only things we need to make sure of if
we want to do coalescing "right" are:
1) We construct frames for kids of a given node in DOM order.
2) We have a ContentInserted version that inserts a range of nodes,
not just a single node (just like ContentAppended, and with similar
fallbacks if there are multiple insertion points, etc).
#1 is basically needed to make #2 work reasonably.
-Boris
Robert O'Callahan
> On 9/18/09 5:17 PM, Robert O'Callahan wrote:
>> One question: when an element is removed from the document, should we
>> remove the element from mPendingRestyles immediately? Right now it looks
>> like the element is kept alive until we next process restyles, which
>> could cause an arbitrary amount of memory overhead.
>
> I think we should do that, yes. That won't help if the element's
> _parent_ is removed, but it should help the common "bounce an element in
> and out of the DOM" case.
The "restyle by traversing the DOM tree" approach would completely solve
this problem.
>> Another question: does mPendingRestyles have any advantages over the
>> Webkit approach?
>
> This is a really really good question. ;) I don't know. They have very
> different pathological behaviors. I would not be averse to trying the
> webkit approach, in general, and seeing what things look like.
Right now it seems to me the only disadvantage of traversing the DOM
tree is that you have to examine every child of an element that has only
a small number of children that need restyling. But generally speaking
when we reflow or repaint we will examine all those children's frames
anyway, so avoiding looking at those child nodes doesn't seem like a
major win.
>> And I guess it wouldn't work with the way we currently do
>> native anonymous content. But does it matter?
>
> I suspect no; we shouldn't really be directly restyling native anon
> content, I would think... That's not to say someone like editor doesn't
> do it, of course.
A text input's anonymous DIV can be restyled. So can generated content.
But I think it would be very reasonable to provide a way to access the
native anonymous children of a node (perhaps via an extension of
ChildIterator).
>> Currently we walk mPendingRestyles and copy the elements into a list.
>> While we're doing that, we could populate an auxiliary hashtable that
>> maps an element to a set of its children which may need frame creation.
>
> Sorted in content order or something?
No, I was thinking of deferring sorting until we actually perform the
restyling.
But I think I like the idea of flags in the DOM tree much better.
Rob
L. David Baron
>> This is a really really good question. ;) I don't know. They have very
>> different pathological behaviors. I would not be averse to trying the
>> webkit approach, in general, and seeing what things look like.
>
> Right now it seems to me the only disadvantage of traversing the DOM
> tree is that you have to examine every child of an element that has only
> a small number of children that need restyling. But generally speaking
> when we reflow or repaint we will examine all those children's frames
> anyway, so avoiding looking at those child nodes doesn't seem like a
> major win.
We could avoid this relatively easily by using an out-of-band tree
(much like the reflow tree that we had before the reflow branch
landed). This is what I propose in
https://bugzilla.mozilla.org/show_bug.cgi?id=479655
(Another advantage such an approach might have is that we'd have
more room for storing the various types of restyling we might want
to do, if we want to differentiate more cases in order to optimize
them.)
-David
--
L. David Baron http://dbaron.org/
Mozilla Corporation http://www.mozilla.com/
Boris Zbarsky
>> I think we should do that, yes. That won't help if the element's
>> _parent_ is removed, but it should help the common "bounce an element in
>> and out of the DOM" case.
>
> The "restyle by traversing the DOM tree" approach would completely solve
> this problem.
Right.
> Right now it seems to me the only disadvantage of traversing the DOM
> tree is that you have to examine every child of an element that has only
> a small number of children that need restyling.
That seems to be the main issue, yes. Plus the need to add a bit more
storage to every node to track the restyle hint, etc.
> But generally speaking when we reflow or repaint we will examine all those children's frames
> anyway, so avoiding looking at those child nodes doesn't seem like a
> major win.
That sort of depends on the exact DOM tree... A full DOM traversal
takes order of 10-20ms on a largish page (e.g. the HTML5 single-page
spec), so it might be ok no matter what.
>>> Currently we walk mPendingRestyles and copy the elements into a list.
>>> While we're doing that, we could populate an auxiliary hashtable that
>>> maps an element to a set of its children which may need frame creation.
>>
>> Sorted in content order or something?
>
> No, I was thinking of deferring sorting until we actually perform the
> restyling.
Sure. We just need to sort before we do frame construction, if we're
trying to coalesce there.
> But I think I like the idea of flags in the DOM tree much better.
I do have to admit it has its benefits; this is why I mentioned it. ;)
-Boris
Boris Zbarsky
>> Right now it seems to me the only disadvantage of traversing the DOM
>> tree is that you have to examine every child of an element that has only
>> a small number of children that need restyling. But generally speaking
>> when we reflow or repaint we will examine all those children's frames
>> anyway, so avoiding looking at those child nodes doesn't seem like a
>> major win.
>
> We could avoid this relatively easily by using an out-of-band tree
> (much like the reflow tree that we had before the reflow branch
> landed). This is what I propose in
> https://bugzilla.mozilla.org/show_bug.cgi?id=479655
My concern there is that we then have to maintain this out-of-band tree
on DOM mutations. Would it basically consist of a subtree of the
(flattened, with anon content, etc) DOM that contains only nodes needing
restyling or their ancestors? If so, updating on mutations might not be
too bad...
> (Another advantage such an approach might have is that we'd have
> more room for storing the various types of restyling we might want
> to do, if we want to differentiate more cases in order to optimize
> them.)
Right. Webkit stores an enum representing the restyle type in all
nodes, I think. If we want to avoid the word-or-so-per-node cost of
that, we'd need to do it out-of-band.
-Boris
Robert O'Callahan
> We could avoid this relatively easily by using an out-of-band tree
> (much like the reflow tree that we had before the reflow branch
> landed). This is what I propose in
> https://bugzilla.mozilla.org/show_bug.cgi?id=479655
I guess I just worry about the complexity and overhead of maintaining
that separately from the DOM.
> (Another advantage such an approach might have is that we'd have
> more room for storing the various types of restyling we might want
> to do, if we want to differentiate more cases in order to optimize
> them.)
It looks like we have 5 bits free in mFlagsOrSlots. It looks like you
only need 3 or 4 for this. If we need more data we could use node
properties. Or perhaps we could use two bits in mFlagsOrSlots for "needs
restyle" and "descendant needs restyle", and have a node property with
more data for nodes that need restyle.
Rob
Jonas Sicking
Ran into this old thread.
I think adding bits to nodes about what restyling they need is totally
ok. If we need to add another word to all nodes I don't think that's a
big deal (we've been way too conservative about this in the past, we
really don't have that many nodes alive that it's a big concern I'm
pretty sure).
This would actually make it easy to keep a list of nodes that need
restyling. Whenever a node is flagged as needing
restyling/frame-creating of some sort we just add it to a list/hash. If
the node is removed from the document it's easy to make UnbindFromTree
check if there's restyle information and if so have the node remove
itself from the list/hash.
/ Jonas
Boris Zbarsky
> I think adding bits to nodes about what restyling they need is totally
> ok. If we need to add another word to all nodes I don't think that's a
> big deal (we've been way too conservative about this in the past, we
> really don't have that many nodes alive that it's a big concern I'm
> pretty sure).
For what it's worth, I've been thinking about making nsReStyleHint
(currently 2 bits) be closer to 24 bits or so. So at that point we'd
probably just want a dedicated 32-bit int for it.
-Boris