438001 - DOM performance downgrade in FF3.x

Status: NEW

(Core :: DOM: Core & HTML, defect, P5)

Description

[Kamil Burzynski]

User-Agent:       Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9) Gecko/2008052906 Firefox/3.0
Build Identifier: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9) Gecko/2008052906 Firefox/3.0

Insertion of tons of div elements to the document works 2-3 times slower on ff3.x builds when compared to ff1.5 or ff2.x builds.

Reproducible: Always

Steps to Reproduce:
1. Load the code from http://www.nopik.whsites.net/graphics.html on FF2.x. After loading alert will say how much seconds a main loop was executing.
2. Load the same code on FF3.x on the same machine. It will be done 2-3 times slower.
3. Repeat steps 1 and 2 2-3 times to get average (usually it seems, that 2nd and 3rd runs do run at different speed than 1st).
Actual Results:  
FF3.0 worked slower than FF2.x

Expected Results:  
FF3.0 being faster, or at least not slower than FF2.0

There was similar bug: https://bugzilla.mozilla.org/show_bug.cgi?id=374037 with SVG nodes, though it do not seem as duplicate (my issue is about DOM, not SVG, and I really see performance downgrade on the same JS code between ff versions).

Btw. the funny thing is that it seems, that we have O(N^2) algorithm here. At the end of source there is for-loop with about 60 iterations. If I change it to 100, the performance will be about 3 times worse on my machine, with 200 iterations it is at least 10 times slower. Maybe this is the problem?

Comment 1

[Ria Klaassen (not reading all bugmail)]

Regression range is http://bonsai.mozilla.org/cvsquery.cgi?module=PhoenixTinderbox&date=explicit&mindate=2006-06-01+15%3A00&maxdate=2006-06-01+21%3A00
Caused by Bug 90983 or Bug 338653 ? (Sorry if I'm blocking the wrong one.)

Comment 2

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

The one think that bug 90983 could have made slower was insertion of DocumentFragments into the DOM. This happens when setting .innerHTML. We used to be better about notifying less for such insertions, but the code got simplified which resulted in more notifications happening.

Would be great to get a smaller testcase that showed the slowdown to see if that is the issue.

Comment 3

[Boris Zbarsky [:bzbarsky]]

This testcase uses createContextualFragment, and then inserts the resulting DocumentFragment.  So it's precisely being hit by the change from bug 90983.

And yes, there's an O(N^2) algorithm here: appending frames (as we end up doing here for each newly-constructed frame) is O(N) in the framelist length (since they're in a linked list).  Or rather, we find the prev frame pretty quickly based on the content model, but then inserting the placeholder into the line box is O(N) in number of elements in the line box and inserting the abs pos frame is O(N) in number of frames in the abs pos list.

Since each insertion is O(N), all the inserts together are O(N^2).

Note that if we do a single notification, there is only _one_ insertion operation on the frame tree, so inserting the DocumentFragment is then O(N) in the number of kids, not O(N^2).

innerHTML would have the same issues if we were to test with reasonably long flat (not deeply nested) innerHTML content...

Comment 4

[Boris Zbarsky [:bzbarsky]]

Note that we have existing bugs on the fact that getting last frames is O(N).

Comment 5

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

I'm not at all exited about bringing back the special code we used to have for inserting fragments. It appears to be very rare to insert long flat fragments.

What we could do is change when we fire mutation events when inserting fragments. That would allow us to insert all nodes in the fragment in one go without worrying about scripts executing, and then notify and fire mutation events.

Comment 6

[Boris Zbarsky [:bzbarsky]]

> It appears to be very rare to insert long flat fragments.

That's possible, but most of the algorithmic slowness issues we have are "very rare" on the scale of the web, because most web pages are pretty small.

If we can somehow do only one notification here, that would be very good.

Comment 7

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

This is a rare edgecase so not blocking. Would be nice to fix though so taking.

Comment 8

[Boris Zbarsky [:bzbarsky]]

I should make that clearer.  This won't happen often, but when it does it's really nasty...

Comment 9

[Kamil Burzynski]

It is not so rare. For example many mouse gestures extensions (used by many
users everyday) does insert a lot of small (1-2px) elements (usually divs, but
not always).. actually this is why long mouse trail in such extension is so
slow.. Also, as browsers are becoming used more and more beyond just plain
HTML, dozens of advanced libraries are created - and they are slowly shifting
to area where this bug will be blocking (for example take a canvas emulation
library from the attached example) and FF3.0 will look bad compared to the
Opera ;)
And such libraries when large amount of elements are generated in a
programmatic way do generate flat list of elements, not a balanced tree..

Comment 10

[Firefox Bug Husbandry Bot]

Bulk priority change, per :mdaly

Comment 11

[BugBot [:suhaib / :marco/ :calixte]]

The bug assignee is inactive on Bugzilla, so the assignee is being reset.