HTML form control state restoration leads to O(N^2) algorithm

NEW
Unassigned

Status

()

Core
DOM: Core & HTML
P5
normal
12 years ago
20 days ago

People

(Reporter: bz, Unassigned)

Tracking

(Depends on: 1 bug, Blocks: 2 bugs, {perf})

Trunk
x86
Linux
Points:
---
Dependency tree / graph
Bug Flags:
blocking1.9 -

Firefox Tracking Flags

(Not tracked)

Details

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.
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?
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...
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?
> 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?
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...
And put the laziness in the frame constructor?  Sure.
Flags: blocking1.9?
Not something that's seen in a lot of webpages, so not a blocker.
Flags: blocking1.9? → blocking1.9-

Updated

10 years ago
Component: DOM: HTML → DOM: Core & HTML
QA Contact: ian → general

Updated

4 years ago
Assignee: general → nobody
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.
Priority: -- → P5
You need to log in before you can comment on or make changes to this bug.