Closed Bug 522930 Opened 15 years ago Closed 11 years ago

Insert Fragment Performance / DOM Refresh [Test Case #2] - 100x slower than Chrome

Categories

(Core :: CSS Parsing and Computation, defect, P2)

Product:
Core
Component:
CSS Parsing and Computation
Platform:
x86
Windows Vista
Type:
defect

Tracking

()

Status:
RESOLVED WORKSFORME

People

(Reporter: bugzilla, Assigned: bzbarsky)

References

(
URL
)

Details

(Keywords: testcase)

Attachments

(2 files)

The testcase
73.08 KB, text/html
Details
Modified testcase with flush
73.22 KB, text/html
Details 
User-Agent:       Mozilla/5.0 (Windows; U; Windows NT 6.0; en-US; rv:1.9.1.3) Gecko/20090824 Firefox/3.5.3 (.NET CLR 3.5.30729) FirePHP/0.3
Build Identifier: Mozilla/5.0 (Windows; U; Windows NT 6.0; en-US; rv:1.9.1.3) Gecko/20090824 Firefox/3.5.3 (.NET CLR 3.5.30729) FirePHP/0.3

This is a corollary to bug <a href="https://bugzilla.mozilla.org/show_bug.cgi?id=522748">bug 522748</a>.  This is a second test case, identical to the performance issue I'm experiencing in production.  The first test turned out to be a Kaspersky related issue.

This has been tested in FF 3.5.3 Normal and Safe-Mode.

Taking out 1000 rows and re-inserting via Range.insertNode() with a DocumentFragment takes about 8000ms in FF, 60ms in chrome under specific circumstances.

The TestCase outlines the exact conditions to make this occur.

Reproducible: Always

Steps to Reproduce:
1. Go to http://www.clintpriest.com/JS_TestCase_DOMSpeed2.php
2. Click 'Run Test'
3.
Mozilla/5.0 (Windows; U; Windows NT 6.0; en-US; rv:1.9.3a1pre) Gecko/20091017 Minefield/3.7a1pre

Google Chrome is 93ms here. Opera 90ms (first try). Latest Minefield 12147ms.
Attached file The testcase — 
Ah, this is cute.  The issue is that changing the classname posts a restyle event for the row and all its later siblings, due to this selector:

  TABLE#DataTable TR.Control + TR td:first-child

So we end up doing a number of restyles that is O(N^2) in number of rows.
I'm not actually sure that keeping track of restyles via the node tree would help with this situation, unless we cleared the restyle hint on removal from the tree.  We can do that anyway (remove from the pending restyle hashtable on removal from the DOM), and probably should, but a trivial change to the testcase defeats that: just comment out all the lines mentioning Range and Fragment, so that all the restyling is just happening without removing any nodes from the DOM.

Clint, you can work around this in the meantime by doing the Fragment.appendChild _before_ you change the class, if the testcase accurately represents what your code is doing.
Status: UNCONFIRMED → NEW
Ever confirmed: true
I just changed the testcase to do a Range.deleteContents() before the for loop, and Fragment.appendChild() prior to changing the className.  I got '3 x 1000 = 4632ms' on the performance test now.

I can definitely come up with a workaround for this, not a problem, its a pretty specific issue.  I'm sure a different CSS state would be an easy solution.

I've got a 3rd test case I'm going to post in a few minutes, hope I'm not being a pain. :)
I just submitted one last test case for document.evaluate(), bug 522967
So we can probably make that case (changing class to/from something non-matching) better by doing HasAttributeDependentStyle in both AttributeWillChange and AttributeChanged and requiring a match on the attr.  I think we probably want to consider doing that too.  But setting all the rows' className to "Control" would still trigger the O(N^2) behavior.

On the other hand, I just looked at the relevant webkit code, and they do this fast by just doing it wrong.  Relevant comment in WebCore/dom/Element.cpp:

    // FIXME: This check is good enough for :hover + foo, but it is not good enough for :hover + foo + bar.
    // For now we will just worry about the common case, since it's a lot trickier to get the second case right
    // without doing way too much re-resolution.

and indeed they screw up this testcase:

  <style>
    div { color: red; }
    .foo + div + div { color: green; }
  </style>
  <body onload="document.getElementsByTagName('div')[0].className = 'foo'">
    <div></div>
    <div></div>
    <div>Text</div>

That said, Opera does get that testcase right, and doesn't have the O(N^2) issue on the attached test page, even when the class is being set to 'Control'.  So clearly we _could_ have a better system for tracking changes here...  I wonder how much it would cost on DOM manipulation.
Component: General → Style System (CSS)
Product: Firefox → Core
QA Contact: general → style-system
> I got '3 x 1000 = 4632ms' on the performance test now.

Hmm.  I'd expect times closer to 200ms if you do the appendChild before changing the className...  Is that 4600ms number with Kaspersky installed again, by any chance?
The TestCase has been changed to do the appendChild before the className unless I got your suggestion wrong.  Does the code on that page do what you suggested?
Right.  I'm looking at the testcase, and the numbers I see are 77ms for Chrome (so comparable to what you see), 189ms for Fx 3.5 (so 20x faster than what you see) for the 3x1000 test.  Just trying to undertand that discrepancy....
Odd, I didn't get that performance right after I changed it but I am getting the better performance now.  Do you want me to change the test case back so it can be used with the poor performance profile?

Thanks for all your help with these performance test cases.  I'd been planning to write a fairly sophisticated data analysis tool and had been leaning towards using an RIA tool such as Silverlight for performance reasons but with all this work on performance lately I'm pretty confident that JS/HTML can handle the load.
> Do you want me to change the test case back

No need; the old version is attached to this bug report.
Oh, I _do_ have an idea for how to nix the O(N^2) thing using a webkit-like style hint on the content node itself.  Just need a hint value for "we'll restyle this node and have marked all following nodes the same way", then mark all following siblings with that value until we hit one that has the value already; we can stop there.
Depends on: 523294
OK, I didn't file a bug for now on removing nodes from mPendingRestyles on removal from the DOM, since that doesn't really handle the case of the node's parent being removed...

Filed bug 523294 on making HasAttributeDependentStyle more conservative.
The patch in bug 523294 gets rid of the O(N^2) behavior on this particular testcase, as expected; the issue comment 6 points out remains.
(In reply to comment #3)
> I'm not actually sure that keeping track of restyles via the node tree would
> help with this situation, unless we cleared the restyle hint on removal from
> the tree.  We can do that anyway (remove from the pending restyle hashtable on
> removal from the DOM), and probably should, but a trivial change to the
> testcase defeats that: just comment out all the lines mentioning Range and
> Fragment, so that all the restyling is just happening without removing any
> nodes from the DOM.

Why would removing from the pending restyle hashtable be better than what we currently do, which is just not process the restyle if the content node is not in the document (at the start of ProcessOneRestyle)?
(In reply to comment #15)
> Why would removing from the pending restyle hashtable be better than what we
> currently do, which is just not process the restyle if the content node is not
> in the document (at the start of ProcessOneRestyle)?

Oh, I guess if we put the node back in the document before processing the pending restyles?
> Oh, I guess if we put the node back in the document

Right.  That's what this testcase does.
Depends on: 479655
As expected the fix for bug 479655 made even the version of this testcase modified per comment 6 fast.

We're still about 1.5x slower than chrome if I actually time including the layout flush; looking into that.
Assignee: nobody → bzbarsky

    
  
Priority: -- → P1

    
  
Priority: P1 → P2

    
    

    
  
Quick test of attachment #452341 [details] shows that Firefox 25b9 is equally fast or marginally faster than Chrome 30. However, both Aurora 26.0a2 (2013-10-17) and Nightly 27.0a1 (2013-10-18) are 20-30% slower than 25b9. 

So, we have an unfortunate regression.

    
    

    
  
I don't see a 20% slowdown from 25b9 to nightly on that testcase...  I see maybe 5%.  And note that nightlies are --enable-profiling builds, which can be marginally slower than release builds.

How do 25 nighlies compare to current ones?  If there's a regression, are you willing to bisect it?
Flags: needinfo?(fb+mozdev)

    
    

    
  
I will have a look at it, though likely not before next week. If somebody is willing to take this before me, please go ahead. 

(Keeping ni? for now.)

    
    

    
  
I can no longer see a difference (minus minimal noise) between Beta 26 through Nightly 28. Firefox is also slightly (and consistently) faster than Chrome 31. 

Firefox 25 Release however seems slightly faster (61-63ms vs. 66-67ms in Beta 26) but I have trouble reproducing this for the Nightly, and the results are too noisy to allow a sensible bisection. This is what I got, though it's possible that there's nothing to find here, and/or the issue was fixed in later commits: 

Last good nightly: 2013-08-14
First bad nightly: 2013-08-15

Pushlog:
http://hg.mozilla.org/mozilla-central/pushloghtml?fromchange=3c61cc01a3b1&tochange=a8daa428ccbc


As per above, I don't think it's worth to investigate this further, unless there's something that stands out to you in the pushlog.
Flags: needinfo?(fb+mozdev) → needinfo?(bzbarsky)

    
    

    
  
Yeah, nothing in there jumps out at me.  Worskforme, I guess.  Thank you for double-checking that!
Status: NEW → RESOLVED
Closed: 11 years ago
Flags: needinfo?(bzbarsky)
Resolution: --- → WORKSFORME

          You need to log in
          before you can comment on or make changes to this bug.
        






  

    
  







  

    

      
Attachment

      

      
      
      
      
    

    

      

        

          

            
General

            

              Creator: 



            

            
Created: 

            
Updated: 

            
Size: