305898 - Poor DOM L1 interaction performance

Status: RESOLVED FIXED

(Core :: Layout, defect)

Description

[liam Carton]

User-Agent:       Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.0; Avi 1.0; Maxthon)
Build Identifier: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:1.8b3) Gecko/20050712 Firefox/1.0+

Originialy posted under bug 40988

Issue with FF 1.06 DOM L1 interaction.

Filtering rows, based on style.display='none' on approx 1,200 rows terribly 
slow (1 - 2 sec IE, 3 mins FF)

As advised downloaded latest Deer Park Alpha build, and re-tested.

Filter function now far better (IE 1 - 2 Sec FF 3 - 4 sec).

However, sort function, which uses .insertBefore, now having real problems, 
when table is filtered (its slower than before on unfiltered, but only by 
perhaps 50%).

When the table is filtered the sort is so slow that the script times out.  Once 
this has happened once then the sort function no longer functions, and weird 
errors start apperaing on the JS console.  This may just be an alpha issue, 
however the performance of the sort under the filter conditions probably isn't.

What I can conclude is that either:
Moving a DOM node that has display:none is very slow
or
Accessing the data in such an element is very slow.

Reproducible: Always

Steps to Reproduce:
1.Sort on Address column click on header but not resize area or filter icon
2.Time is OK
3.Sort on Name
4.Click on Filter icon for Name
5.Enter the character a and press enter (column is filtered on 'a%')
6.Sort on Address
7.Wait for script timeout error

Actual Results:  
Script time out error
Followed by spurious errors in JS console during any further attempts to sort

Expected Results:  
Sort should complete in less than 3 sec.

The key functions for the sort and filter are:

Sort:
function swapRows(tb,td)

Filter:
function filterBlur(ev)

The table is a "fake" table, made up of a set of span and div tags, with their 
default display properties overidden to produce the correct effect. 

The script contains other functions for other components which can be ignored.

The data in the table is test data, but the live application has between 400 
and 2,000 rows, and between 13 and 40 columns. So the size of the test data is, 
if anything smaller than would be the case in the real world.

Comment 1

[liam Carton]

Attachment: Demonstration web page

Comment 2

[Bob Clary [:bc] (inactive)]

very fast with deerpark/winxp from today. slow as molasses on 1.0.6, wfm?

Comment 3

[liam Carton]

This may not be important, but I reversed the order of the filter (Working top 
to bottom, rather than bottom to top).

This improved speed on IE by +/- 20%
FF +/- 1,000s (now down to a few secs).
DP +/- 30%

This would indicate that FF was choking on re-rendering all the elements for 
each display=none. 

However, DP has this fixed already.

One other point, I don't know if its important, in FF after filtering the 
height of the containg DIV is correctly set, but in DP it remains the same as 
before the filtering, which is not correct. (Is this / Should this be a 
seperate bug?)
If someone would like I can upload the newere version, or the changed line is:

Line in function filterBlur(ev)
Old: for(var i=0;i<spnl;i++)
New: for(var i=spnl-1;i>=0;i--)

DP sort performance (only when filtered) is unchanged by this. 

Comment 4

[Boris Zbarsky [:bzbarsky]]

So the problem here is that if a node is inserted into the DOM and is preceded
by a bunch of display:none content, we'll do a linear search for the frame for
each of them while looking for the right pref sibling in
nsCSSFrameConstructor::ContentInserted (since nsFrameManager::GetPrimaryFrameFor
doesn't check the undisplayed content map).  This means the insertion will be
O(N*M) where N is the total number of preceding siblings and M is the number of
immediate siblings that is display:none.  In this case N and M both get pretty
big, and in fact end up on the order of the total number of rows, so sorting
while filtered ends up O(N^3) in the number of rows....

Comment 5

[Boris Zbarsky [:bzbarsky]]

Just doing a GetUndisplayedContent check in nsFrameManager::GetPrimaryFrameFor
makes this a good bit happier, actually...  Though at that point the fact that
GetUndiplayedContent also does a linear search starts to bite.

I'm going to do a bit of thinking about how to make the whole GetPrimaryFrameFor
setup a little faster, I think.

Comment 6

[liam Carton]

Hi,

I was asked by Wayne Mery to re-test the problem under the current release.  (Last tested in Deer Park).

FF2 has made significant progress on this, and independent filter and sort times are now OK.

However, sorting when a filter is applied still takes way to long.

When the "Name" column is filtered on "a" and the "Tel" is then sorted (by clicking on the header) the sort takes 37 seconds on my machine vs 0.5 seconds in IE6.

A second click on the header then takes about 3 seconds to reverse the sort.  Better, but still an order of magnitude slower than IE6.

I don't have a figure for IE7, but if someone thinks that could help let me know and I will set up a test box for that.

Wayne then asked me to install FF3 beta and re-try.

Apart form silently taking over as default browser (BAD! very Bad!) the performance only changed slightly, dropping from 37 to 32 seconds.

If anyone is interested I have another test that also shows ~10x slower function in FF2 than IE6 (Under FF1 it was x600 slower than IE).

At present I now have no FF installed as the only way I could fix my system after installing FF3 was to completely remove it. 

If anyone wants further test done using FF3 they will need to provide me with a way to install it such that it does not become the default browser.  I simply wont install it under any circumstances as the default. Sorry.

Hope this new info helps.

Congrats on the speed up, but please re-consider this daft idea about silent installs and defaults.  You are just going to irritate people.  I should be left to choose which browser I want as default.

Liam Carton

Comment 7

[Wayne Mery (:wsmwk)]

thanks for the info.

regarding getting back to your original environment it SHOULD be easy. Doesn't control panel>internet settings>programs give you the controls you need?  If you don't the information you need here, ask in a newsgroup or mozillazine forum and someone should be able to help you news.mozilla.org/mozilla.support.firefox  

several bugs talk about default browser setting here are 3 of many:
bug 420270
bug 408944
bug 396267 (not likely related)

Comment 8

[Bob Clary [:bc] (inactive)]

(In reply to comment #6)

> 
> Apart form silently taking over as default browser (BAD! very Bad!) the
> performance only changed slightly, dropping from 37 to 32 seconds.

Did you leave the checkbox checked to set Firefox as your default browser in the panel where you chose a standard vs. custom installation?

Comment 9

[Boris Zbarsky [:bzbarsky]]

Wayne, Comment 4 really summarizes what the issue is here.  None of that has changed in Fx2 or Fx3.  The issue is that the rendering object tree and the content tree are non-isomorphic, so finding the right part of the former to mutate when the latter mutates can take too long.  Until that issue is fixed, and testing on the testcase in this bug verifies the fix, there is no need to bother reporters about retesting.

I really wish comment 7 and comment 8 had been in private mail instead of cluttering up the bug.  :(  I certainly hope any further discussion about the installation stuff doesn't end up here...

In any case, this is still on my list of things to look at sometime this summer or fall as I try to rejigger the frame constructor.  It feels to me like we should at least be able to do some sort of locality-of-reference approach here or something.  Maybe.

Comment 10

[Boris Zbarsky [:bzbarsky]]

Two things that will help here:

1)  Knowing primary frames in O(1) time for all elements: bug 500882
2)  Lazy frame construction: bug 502937.

Comment 11

[Boris Zbarsky [:bzbarsky]]

It looks like the fix for bug 500882 pretty much made this fast, in fact.