Boris Zbarsky [:bzbarsky] Reporter
	Description • 18 years ago

STEPS TO REPRODUCE:

1)  Load the testcases in bug 352367.
2)  Profile it.
3)  Look at the profile.

EXPECTED RESULTS:  Content lists don't take too much time

ACTUAL RESULTS:

Total hit count: 1281040
135645 nsContentList::PopulateWith  (more than 10% of total time).

The problem is an O(N^2) algorithm.  This is what happens:

1)  We parse a form control.  It tries to recover state.  This involves calling
    IndexOf() on the form control list _without_ flushing (for perf reasons).
2)  The list walks forward into parts of the DOM tree that haven't been
    notified on yet, looking for the form control.  Which is what we want it to 
    do in this case.
3)  When those parts of the tree get notified on via ContentAppended(), the
    content list marks itself dirty, since it thinks an insertion happened and
    dealing with those is hard.

As a result, we end up recreating the list over and over and over again a bunch of times...

I'll try to think of some way to deal with this.

	Boris Zbarsky [:bzbarsky] Reporter
	Comment 1 • 18 years ago

So I see two possible ways forward:

1)  Figure out a way to handle this in nsContentList.cpp
2)  Change the state-generation code to not use content lists (and just use
    IndexOf() on the parent node instead, like we do in non-HTML documents
    anyway).

Thoughts?

	Boris Zbarsky [:bzbarsky] Reporter
	Comment 2 • 18 years ago

So I've been failing to think of a way to handle this in nsContentList.  The more I think about it, the more I like changing state restoration...

	Jonas Sicking (:sicking) No longer reading bugmail consistently
	Comment 3 • 18 years ago

So is the problem here that we're finding nodes that hasn't been notified on yet? And so when those nodes are notified for we've already found nodes past it and thus we consider it an insertion?

Would this simply be fixed by when we get notified for a node check if it's already in the list and if so do nothing?

	Boris Zbarsky [:bzbarsky] Reporter
	Comment 4 • 18 years ago

> So is the problem here that we're finding nodes that hasn't been notified on
> yet? And so when those nodes are notified for we've already found nodes past it
> and thus we consider it an insertion?

Yes, precisely.  Or rather, when we're notified on whatever random ancestor of the node the sink notifies on, we note that it comes before the last item in the list and call it an insertion.

> Would this simply be fixed by when we get notified for a node check if it's
> already in the list and if so do nothing?

The problem, again, is that we're being notified on some ancestor, in general.  We could walk through its kids and see which ones are already in the list, true.  But that would make the whole deal O(N^2) in length of the list anyway, no?

	Jonas Sicking (:sicking) No longer reading bugmail consistently
	Comment 5 • 18 years ago

Ah, yes, i didn't think about the case where we notify on an ancestor.

I really dislike all this lazy notification stuff. The world would be so much easier if we always notified when inserting a node in the tree...

	Boris Zbarsky [:bzbarsky] Reporter
	Comment 6 • 18 years ago

And put the laziness in the frame constructor?  Sure.

	Johnny Stenback (:jst)
	Comment 7 • 18 years ago

Not something that's seen in a lot of webpages, so not a blocker.

	Firefox Bug Husbandry Bot
	Comment 8 • 6 years ago

https://bugzilla.mozilla.org/show_bug.cgi?id=1472046

Move all DOM bugs that haven't been updated in more than 3 years and has no one currently assigned to P5.

If you have questions, please contact :mdaly.