Benefit of deferred tree mutatition notifications
Henri Sivonen
notifications. This involves bookkeeping and even calls to the system
clock.
What's the benefit of deferring the mutation notifications and then
firing a whole bunch of them in one event loop cycle? Would layout try
to reflow or paint too often otherwise?
The reason I'm asking is that I'm not sure how hard I should try to
defer mutation notifications in HTML5 tree building. (The code I already
have assumes that mutations complete immediately and that there is no
need to keep track of past mutations.)
--
Henri Sivonen
hsiv...@iki.fi
http://hsivonen.iki.fi/
L. David Baron
> Currently, the HTML and XML content sinks try to defer tree mutation
> notifications. This involves bookkeeping and even calls to the system
> clock.
>
> What's the benefit of deferring the mutation notifications and then
> firing a whole bunch of them in one event loop cycle? Would layout try
> to reflow or paint too often otherwise?
It would certainly try to construct frames too often, triggering
O(N^2) behavior in some cases, and probably reflow too often as
well. (Frame construction happens synchronously; reflow and repaint
usually happen asynchronously.) Those problems may not be as bad as
the ones when this code was written, though.
The timers we have gating this behavior are a bit of a mess (and
compete with each other). Hopefully we can come up with something
better (based on a particular refresh rate goal) once we have
Compositor. I'm not sure to what extent doing that is part of roc's
plans for compositor or is something that can happen as followup or
even independently.
-David
--
L. David Baron http://dbaron.org/
Mozilla Corporation http://www.mozilla.com/
Boris Zbarsky
> What's the benefit of deferring the mutation notifications and then
> firing a whole bunch of them in one event loop cycle? Would layout try
> to reflow or paint too often otherwise?
The main benefit currently is that frame construction is amortized
O(N)-ish with this approach in many cases, where it would be O(N^2) with
eager append+notify. Keep in mind that each mutation involves finding
the right place in the frame linked list to insert the new frames; for
appends this is guaranteed to be O(N) per mutation.
There are probably some other mutation observers that have similar
issues, but frame construction is by far the biggest problem.
You might want to talk to sicking about his plans to rip out deferred
notifications and batch together the mutations themselves in the sink.
That might be the way to go in HTML5.
-Boris
Jonas Sicking
As has been pointed out, the notification batching is important to at
least the layout code, and most likely to other code as well, though
perhaps not as critically.
However, one my project this quarter is to remove the notification
batching and replace it with insertion batching. So in other words we'll
hold on to small subtrees as we're parsing. And when we decide it's time
to update what's rendered (probably mostly based on timer) we'll spend
cycles on inserting these subtrees and rendering them.
Things like this is why I think we should keep parsing separated from
the creation and insertion of the nodes into the DOM. That and that
hopefully in the future the html5 parser is a generic library that can
be shared between us and other project the way cairo and libjpg is.
And hopefully that will be your library, hint hint nudge nudge ;)
/ Jonas
Henri Sivonen
deferring to the HTML5 tree building code.
In article <V42dnRRW0sSrwW7V...@mozilla.org>,
Boris Zbarsky <bzba...@mit.edu> wrote:
> Henri Sivonen wrote:
> > What's the benefit of deferring the mutation notifications and then
> > firing a whole bunch of them in one event loop cycle? Would layout try
> > to reflow or paint too often otherwise?
>
> The main benefit currently is that frame construction is amortized
> O(N)-ish with this approach in many cases, where it would be O(N^2) with
> eager append+notify. Keep in mind that each mutation involves finding
> the right place in the frame linked list to insert the new frames; for
> appends this is guaranteed to be O(N) per mutation.
>
> There are probably some other mutation observers that have similar
> issues, but frame construction is by far the biggest problem.
I was thinking of doing the following:
* Maintain a numFlushed integer on each stack node the way existing
sinks do.
* Have a flushing method that traverses the stack towards root and
notifies appends for each node whose child count is greater than
numFlushed.
* On normal append, don't notify by default. Check clock if it is time
to call the flushing method.
* When a node comes off the stack, flush its children.
* For all other mutations, call the flushing method, perform the
mutation and fire the relevant notification immediately.
Would this be sufficient? To me, it seems that the above is pretty close
to what the current sinks do.
I'm not sure if setting attributes on a node before appending it to the
tree requires notifications for the attribute mutations. Does it?
How do current sinks deal with numFlushed getting out of sync if the
tree is mutated for a timeout set by script?
> You might want to talk to sicking about his plans to rip out deferred
> notifications and batch together the mutations themselves in the sink.
> That might be the way to go in HTML5.
In article <XeSdnTe7cf75Im7V...@mozilla.org>,
Jonas Sicking <jo...@sicking.cc> wrote:
> However, one my project this quarter is to remove the notification
> batching and replace it with insertion batching. So in other words we'll
> hold on to small subtrees as we're parsing. And when we decide it's time
> to update what's rendered (probably mostly based on timer) we'll spend
> cycles on inserting these subtrees and rendering them.
>
> Things like this is why I think we should keep parsing separated from
> the creation and insertion of the nodes into the DOM.
In the context of HTML5 parsing, this seems harder than deferring
notifications. The spec assumes synchronous node creation and insertion
to the tree and only requires the parser to hold pointers to element
nodes from the stack nodes. The tree builder code I have follows the
assumptions of the spec very closely here.
Deferring notifications adds flushing counts to the stack nodes. What
kind of data structure would be suitable for keeping track of
uncommitted insertions? Would the deferred insertions be committed
whenever the next tree mutation is not a simple append to the current
node? How would things work if a script used a timeout to change the
tree during parse?
> That and that
> hopefully in the future the html5 parser is a generic library that can
> be shared between us and other project the way cairo and libjpg is.
>
> And hopefully that will be your library, hint hint nudge nudge ;)
The library is generic. However, it was written for synchronous tree
mutations and assumes a no-fail allocator. It currently assumes that the
environment provides implementations for the following methods:
nsIContent* createElement(PRInt32 aNamespace, nsIAtom* aName,
nsHtml5HtmlAttributes* aAttributes);
nsIContent* createHtmlElementSetAsRoot(nsHtml5HtmlAttributes*
aAttributes);
void detachFromParent(nsIContent* aElement);
PRBool hasChildren(nsIContent* aElement);
nsIContent* shallowClone(nsIContent* aElement);
void detachFromParentAndAppendToNewParent(nsIContent* aChild,
nsIContent* aNewParent);
void appendChildrenToNewParent(nsIContent* aOldParent, nsIContent*
aNewParent);
nsIContent* parentElementFor(nsIContent* eElement);
void insertBefore(nsIContent* aNewChild, nsIContent* aReferenceSibling,
nsIContent* aParent);
// This is only used for foster parenting junk out of tables and isn't
// currently properly coalescing.
void insertCharactersBefore(PRUnichar* aBuffer, PRInt32 aStart, PRInt32
aLength, nsIContent* aReferenceSibling, nsIContent* aParent);
// This can be pre-coalesced by the tree builder.
void appendCharacters(nsIContent* aParent, PRUnichar* aBuffer, PRInt32
aStart, PRInt32 aLength);
void appendComment(nsIContent* aParent, PRUnichar* aBuffer, PRInt32
aStart, PRInt32 aLength);
void appendCommentToDocument(PRUnichar* aBuffer, PRInt32 aStart, PRInt32
aLength);
void addAttributesToElement(nsIContent* aElement, nsHtml5HtmlAttributes*
aAttributes);
(As far as the generic parser core is concerned, nsIContent* is just
some type that can be assigned to a variable and be passed as argument
to host methods that can retain/release it. The create and clone methods
are assumed to return pre-retained objects. Normal element appends use
detachFromParentAndAppendToNewParent(). That is, the detach part is a
no-op for newly-created unparented nodes.)
Are these operations a suitable interface for the kind separation of
parsing you mean?
In article
<mailman.174.12239068...@lists.mozilla.org>,
"L. David Baron" <dba...@dbaron.org> wrote:
> The timers we have gating this behavior are a bit of a mess (and
> compete with each other). Hopefully we can come up with something
> better (based on a particular refresh rate goal) once we have
> Compositor. I'm not sure to what extent doing that is part of roc's
> plans for compositor or is something that can happen as followup or
> even independently.
From the tree builder point of view, would the main impact be sharing
the last flush time and an "is it time to flush?" check with other code?
Boris Zbarsky
> * Maintain a numFlushed integer on each stack node the way existing
> sinks do.
> * Have a flushing method that traverses the stack towards root and
> notifies appends for each node whose child count is greater than
> numFlushed.
> * On normal append, don't notify by default. Check clock if it is time
> to call the flushing method.
All good so far.
> * When a node comes off the stack, flush its children.
There's no obvious need to do that if the node itself hasn't been
flushed yet.
> * For all other mutations, call the flushing method, perform the
> mutation and fire the relevant notification immediately.
With the caveat above, that's basically what the current sinks do.
> I'm not sure if setting attributes on a node before appending it to the
> tree requires notifications for the attribute mutations. Does it?
It doesn't.
> How do current sinks deal with numFlushed getting out of sync if the
> tree is mutated for a timeout set by script?
The sink flushes out all notifications on BeginUpdate (so as soon as the
mutation starts).
> In the context of HTML5 parsing, this seems harder than deferring
> notifications.
The thing is, in practice deferring notifications has lead to various
bugs, many of them security-related, due to the state of the DOM not
matching what various observers _think_ it should be. Jonas' approach
may well end up being simpler in the sink (in terms of the logic
involved) and safer overall.
> Deferring notifications adds flushing counts to the stack nodes. What
> kind of data structure would be suitable for keeping track of
> uncommitted insertions? Would the deferred insertions be committed
> whenever the next tree mutation is not a simple append to the current
> node? How would things work if a script used a timeout to change the
> tree during parse?
Letting Jonas field this.
> The create and clone methods are assumed to return pre-retained objects.
We probably want to annotate that somehow on the interface... We can
worry about this part later once we finalize the API.
-Boris
Henri Sivonen
Boris Zbarsky <bzba...@mit.edu> wrote:
> Henri Sivonen wrote:
> > * When a node comes off the stack, flush its children.
>
> There's no obvious need to do that if the node itself hasn't been
> flushed yet.
But if the node is coming off the stack, the tree builder no longer has
a pointer to it and can't flush it later.
Do you mean the children of an element don't need to be flushed *at all*
if the children are completed before the element itself get flushed?
> The sink flushes out all notifications on BeginUpdate (so as soon as the
> mutation starts).
Ah. That explains it.
> The thing is, in practice deferring notifications has lead to various
> bugs, many of them security-related, due to the state of the DOM not
> matching what various observers _think_ it should be. Jonas' approach
> may well end up being simpler in the sink (in terms of the logic
> involved) and safer overall.
It seems to me that the problem isn't that the tree builder sees the
number of children inserted and the number of children flushed. The
problem seems to be that other code sees number of children inserted
instead of seeing number of children flushed.
Could this be addressed by making the nodes hold the number of children
flushed as their child array length towards all code except the tree
builder? The real child array length would then be maintained on the
tree builder stack.
That is, the numbers on the tree builder stack and the on the nodes
would be swapped compared to how it works currently.
Henri Sivonen
Henri Sivonen <hsiv...@iki.fi> wrote:
> Could this be addressed by making the nodes hold the number of children
> flushed as their child array length towards all code except the tree
> builder? The real child array length would then be maintained on the
> tree builder stack.
>
> That is, the numbers on the tree builder stack and the on the nodes
> would be swapped compared to how it works currently.
Alternatively, instead of putting the uncommitted appends into the child
list on the nodes themselves, the tree builder stack nodes could hold
the uncommitted tail of the child lists, if appends are the only kind of
mutations that need need to be deferred.
Either way, the tree builder nodes would be deferring-aware instead of
tree insertion and parser being separate boxes.
Boris Zbarsky
> Do you mean the children of an element don't need to be flushed *at all*
> if the children are completed before the element itself get flushed?
That's correct. Just like we don't notify directly on kids of a node
that is inserted into the DOM via insertBefore().
> It seems to me that the problem isn't that the tree builder sees the
> number of children inserted and the number of children flushed. The
> problem seems to be that other code sees number of children inserted
> instead of seeing number of children flushed.
Right.
> Could this be addressed by making the nodes hold the number of children
> flushed as their child array length towards all code except the tree
> builder?
This might work, yes... It'd require a bunch of changes to the content
code, though.
-Boris
Boris Zbarsky
> Alternatively, instead of putting the uncommitted appends into the child
> list on the nodes themselves, the tree builder stack nodes could hold
> the uncommitted tail of the child lists, if appends are the only kind of
> mutations that need need to be deferred.
They're the only things that need to defer, yes. And I think this is
basically what Jonas is proposing.
-Boris
Henri Sivonen
Boris Zbarsky <bzba...@mit.edu> wrote:
This approach would be easily implementable without requiring changes to
the portable part of the HTML5 parser.
Instead of nsIContent*, the parser core would just need to see a proxy
object which would hold an nsCOMPtr<nsIContent> and a pending append
list (nsTArray< nsCOMPtr<nsINode> >?).
Should I go ahead with this approach?
Jonas Sicking
>> batching and replace it with insertion batching. So in other words we'll
>> hold on to small subtrees as we're parsing. And when we decide it's time
>> to update what's rendered (probably mostly based on timer) we'll spend
>> cycles on inserting these subtrees and rendering them.
>>
>> Things like this is why I think we should keep parsing separated from
>> the creation and insertion of the nodes into the DOM.
>
> In the context of HTML5 parsing, this seems harder than deferring
> notifications. The spec assumes synchronous node creation and insertion
> to the tree and only requires the parser to hold pointers to element
> nodes from the stack nodes. The tree builder code I have follows the
> assumptions of the spec very closely here.
Deferring notifications currently has many problems in the tree. A few
algorithms that should be O(N) end up being O(N^2) because we walk nodes
multiple times due to walking nodes that have been inserted but not yet
notified on, and then walking them again when they are inserted.
Additionally we're having to sprinkle notification flushing all over the
code to ensure that the DOM and the notifications are in sync when we
have code that uses both. These flushes are easy to forget (as it is
non-trivial to see that they are required) resulting in bugs. The times
when we flush also gets very complex which makes it hard to grasp when
flushing in reality occurs and what the performance costs due to this are.
So while it saves complexity in the parsing code. It adds a lot of
complexity elsewhere, and adds unknown performance costs, potentially
very big ones. Additionally, it has been very hard to keep the
notification batching bug free. It is so critical that notifications and
the DOM are in sync in a few places, such as when doing layout. There
are very complex reentry problems which still to this day results in
duplication of layout frames leading to crashes. So ultimately in the
current code I expect insert notification both to be a win in simplicity
inside the parser, as well as outside it.
> Deferring notifications adds flushing counts to the stack nodes. What
> kind of data structure would be suitable for keeping track of
> uncommitted insertions? Would the deferred insertions be committed
> whenever the next tree mutation is not a simple append to the current
> node? How would things work if a script used a timeout to change the
> tree during parse?
The deferred insertions are kept as a list of pending insertions. Each
insertion has a parent to insert it, an index where to insert (in the
vast majority of cases the index is -1 meaning 'append'), and a DOM to
insert. As long as we are parsing into a DOM that is not yet inserted
we'll just right away into that DOM, with no additional pending
insertions being generated.
/ Jonas
Boris Zbarsky
> Instead of nsIContent*, the parser core would just need to see a proxy
> object which would hold an nsCOMPtr<nsIContent> and a pending append
> list (nsTArray< nsCOMPtr<nsINode> >?).
>
> Should I go ahead with this approach?
Seems ok to me, but really Jonas is the one to coordinate this with.
-Boris
Henri Sivonen
> > In the context of HTML5 parsing, this seems harder than deferring
> > notifications.
I was mistaken. Deferring insertions isn't harder as long as the tree
builder gets an opportunity to flush before anyone else modifies the
tree.
In article <5MudnRNUxKT9lWjV...@mozilla.org>,
Jonas Sicking <jo...@sicking.cc> wrote:
> The deferred insertions are kept as a list of pending insertions. Each
> insertion has a parent to insert it, an index where to insert (in the
> vast majority of cases the index is -1 meaning 'append'), and a DOM to
> insert.
A pending list of insertion works. However, insertBefore changes the
insertion index for subsequent insertBefores, so holding a reference
node instead an index would be simpler. (Repeated reference node
searches could be optimized in the flushing method not searching twice
if consecutive insertBefores have the same reference node.)
Is there already code that I should use for this?
Jonas Sicking
> I said:
>
>>> In the context of HTML5 parsing, this seems harder than deferring
>>> notifications.
>
> I was mistaken. Deferring insertions isn't harder as long as the tree
> builder gets an opportunity to flush before anyone else modifies the
> tree.
That is hard though. If scripts run when we are in the state of having
pending inserts, then the script can modify the DOM. I think it would be
very confusing to the script if inserting a node somewhere in the tree
causes a bunch of other nodes to be inserted elsewhere.
> In article <5MudnRNUxKT9lWjV...@mozilla.org>,
> Jonas Sicking <jo...@sicking.cc> wrote:
>
>> The deferred insertions are kept as a list of pending insertions. Each
>> insertion has a parent to insert it, an index where to insert (in the
>> vast majority of cases the index is -1 meaning 'append'), and a DOM to
>> insert.
>
> A pending list of insertion works. However, insertBefore changes the
> insertion index for subsequent insertBefores, so holding a reference
> node instead an index would be simpler. (Repeated reference node
> searches could be optimized in the flushing method not searching twice
> if consecutive insertBefores have the same reference node.)
Either you can hold on to the node, or you can adjust the insertion
index as needed. We have internal notifications that are really fast
that you can use to get notified about any DOM mutations.
> Is there already code that I should use for this?
Nothing finalized at this point no.
/ Jonas
Henri Sivonen
Jonas Sicking <jo...@sicking.cc> wrote:
> Henri Sivonen wrote:
> > I said:
> >
> >>> In the context of HTML5 parsing, this seems harder than deferring
> >>> notifications.
> >
> > I was mistaken. Deferring insertions isn't harder as long as the tree
> > builder gets an opportunity to flush before anyone else modifies the
> > tree.
>
> That is hard though. If scripts run when we are in the state of having
> pending inserts, then the script can modify the DOM. I think it would be
> very confusing to the script if inserting a node somewhere in the tree
> causes a bunch of other nodes to be inserted elsewhere.
Right. Giving the tree builder an opportunity to flush just before a
script mutates the tree is too late. The tree builder should get an
opportunity to flush just before a script tries to access the DOM in any
way--even for reading.
Are there cases where scripts access the document without causing
FlushPendingNotifications() to be called on the document first?
Boris Zbarsky
> Are there cases where scripts access the document without causing
> FlushPendingNotifications() to be called on the document first?
Yes. For example, traversing the DOM using .firstChild and .nextSibling
will never flush as things stand.
We do flush in some places (getElementById,
getElementsByTagName(...).length), but that has to do with those methods
relying on notifications to update internal state that the answer is
based on.
If we start lazily adding to the DOM, we'd probably have to do so before
entering JS at all or something, unless we can figure out a smarter
approach.
-Boris
Henri Sivonen
Boris Zbarsky <bzba...@mit.edu> wrote:
> If we start lazily adding to the DOM, we'd probably have to do so before
> entering JS at all or something, unless we can figure out a smarter
> approach.
So it seems. Where should I look if I try to add that myself?
Another thing:
There are now "monolithic containers" that aren't (or in the past
weren't) fully robust if they get notified before their children are
complete.
PRBool
nsXMLContentSink::IsMonolithicContainer(nsINodeInfo* aNodeInfo)
{
return ((aNodeInfo->NamespaceID() == kNameSpaceID_XHTML &&
(aNodeInfo->NameAtom() == nsGkAtoms::tr ||
aNodeInfo->NameAtom() == nsGkAtoms::select ||
aNodeInfo->NameAtom() == nsGkAtoms::object ||
aNodeInfo->NameAtom() == nsGkAtoms::applet))
#ifdef MOZ_MATHML
|| (aNodeInfo->NamespaceID() == kNameSpaceID_MathML &&
(aNodeInfo->NameAtom() == nsGkAtoms::math))
#endif
);
}
If one of these hasn't had all their children inserted yet and a script
runs (possibly from timeout) causing a flush, it's now within the
parser's power to protect higher layers from layout breakage.
Any suggestions on how to deal with this except by filing bugs against
layout? How do these elements deal with scripted appends?
Boris Zbarsky
> Any suggestions on how to deal with this except by filing bugs against
> layout? How do these elements deal with scripted appends?
<tr> deals ok, just slowly. Probably the same for <select>, though
there is weirdness in terms of which options are selected. <object> and
<applet> don't deal. Don't know about <math>.
-Boris