IE Maze Solver testcase hits hotspot in nsFloatManager::GetFlowArea

NEW
Unassigned

Status

()

Core
Layout: Block and Inline
7 years ago
2 years ago

People

(Reporter: bz, Unassigned)

Tracking

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

Trunk
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(Not tracked)

Details

(Whiteboard: ietestdrive [qa+], URL)

Attachments

(1 attachment)

(Reporter)

Description

7 years ago
On my mac, 50% of the total time is reflow (the rest is painting).

Almost half of reflow is in nsFloatManager::GetFlowArea, called from nsBlockFrame::AddFloat, called from nsLineLayout::ReflowFrame.

Presumably this is actually the GetFloatAvailableSpace calls AddFloat makes being inlined (including both overloads of GetFloatAvailableSpace and the GetFloatAvailableSpaceWithState call).

I'm guessing we're ending up with an O(N^2) algorithm here, right?
(Reporter)

Updated

7 years ago
Keywords: perf
(Reporter)

Comment 1

7 years ago
One other note.  The reason we do float reflow at all is that each cell of the maze is a float.  Each cell also has an empty div kid.  When marking a cell for the first time, the script changes the style of the cell's div kid.

That said, it's only changing the visibility and background styles; why the heck is this triggering reflow?
(Reporter)

Comment 2

7 years ago
Oh, this is semi-ridiculous.

1)  There is nothing in-flow inside that maze: just floated borders and abs pos
    markers.
2)  They handle positioning the (absolutely positioned, natch) markers by setting
    their transform from no transform to a translate transform.  For us that
    means reframing, of course.  And they do this one marker at a time, when they
    change the marker's color.

So we end up reframing the marker, and hence reflowing the whole maze.

Also, changing transform-origin would force reflow of the marker no matter what.

Of course since the marker is abs pos reframing it, or reflowing it, absolutely can't change the position of _anything_ else on the page.  So it seems like the right optimization here would be for that case...  Can we manage that?
(In reply to comment #2)
> Of course since the marker is abs pos reframing it, or reflowing it, absolutely
> can't change the position of _anything_ else on the page.  So it seems like the
> right optimization here would be for that case...  Can we manage that?

Except abs pos elements can change scrollable overflow area, and we currently only change overflow areas during reflow.  We need a mechanism for recomputing overflow areas outside of reflow; it blocks a whole bunch of things we need to do.  (I thought we had a bug on it, but can't find one.)
(Reporter)

Comment 4

7 years ago
Fwiw, I think that we should still fix this bug as filed: we shouldn't need an O(N^2) algorithm on the floats here.  I just don't think that'll get us close to "fast" on the maze, given all the other reflow/reframe overhead here.

Comment 5

6 years ago
O(N^2)?
A candidate for blocking Bug 86952.

Comment 6

6 years ago
opera pass this test amazingly
Please add Windows platform also. I can confirm that Maze solver runs very slow on Windows comared to other browsers
OS: Mac OS X → All
Hardware: x86 → All

Comment 8

6 years ago
Looks to be better in nightly FF8. But Firefox just gets killed in this test. Anything we can do better on this? 

On 64bit Win7 
Processor:Intel﴾R﴿ Core﴾TM﴿ i7 CPU       Q 820  @ 1.73GHz   1.73 GHz
Installed memory ﴾RAM﴿:	8.00 GB
System type:	64‐bit Operating System

Build identifier: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:5.0) Gecko/20100101 Firefox/5.0
Time: 233 seconds

Build identifier: Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:8.0a1) Gecko/20110707 Firefox/8.0a1
Time: 115 seconds

Google Chrome	12.0.742.112 (Official Build 90304)
Time: 1.5 seconds

IE 9 9.0.8080
Time: 6.0 seconds
(Reporter)

Comment 9

6 years ago
> Anything we can do better on this? 

This bug and bug 641341 are the obvious things we can do better.  That's why they're filed.

Well, that and making the painting faster somehow; see comment 0.
(Reporter)

Updated

6 years ago
See Also: → bug 641341
In this comparison (http://www.tomshardware.com/reviews/web-browser-performance-standard-html5,3013-16.html) this test was one of the few areas where Firefox was rated as weak.
If reflowing the entire maze is causing us to invalidate the entire maze, then the repaint time should go down as amount of maze reflowed is reduced.  But of course the paint time might be worth looking at in case anything sticks out.
Created attachment 563041 [details]
jprof at 2ms

This takes 85 seconds on my ultra-fast Xeon desktop, and 4.5 seconds on Chrome on the same machine.  Really.

This bug's contribution is around 17%.
(Reporter)

Comment 13

6 years ago
Bug 670311 will hopefully make this all better.
Depends on: 670311
FYI, TomsHardware indicates FF7 got 10 seconds *worse* than FF6 on this test - so we went in the wrong direction.
(Reporter)

Comment 15

6 years ago
Regression range welcome.  Possibly in an actual metabug tracking the test that all the specific bugs block?
I'd love to - but there's no way I have time. :-(  Perhaps QA could verify the regression and bisect.
Juan or Anthony can we get someone assigned to verify the regression?
Keywords: qawanted
Whiteboard: ietestdrive → ietestdrive [qa+]
(Reporter)

Comment 18

6 years ago
Please file a separate bug for the regression.  Do NOT hijack this bug.

Updated

6 years ago
Depends on: 691414
Filed bug 691414 on the regression
(Reporter)

Comment 20

6 years ago
I don't see an obvious way to make this faster, actually... And even with bug 670311 fixed we'd still need to reflow the placeholders to get the right y position for them.  David, any ideas?

One other note: a lot of the reflow seems to happen off paint events, so moving painting to the refresh driver might help here.
(Reporter)

Updated

6 years ago
See Also: → bug 691645
Would being able to reframe all children of a frame (rather than the frame itself) help here at all?  (We could do that on transform to no transform changes, since the reason to reframe is for fixed-pos descendants.)  Or we could even replace that with code that searches the descendants for a fixed-pos frame and just reframes those -- may well be worth doing.  Would that get rid of the need to reflow at all?
(Reporter)

Comment 22

6 years ago
If we didn't need to reframe the transformed element itself on transform changes then we would not need to reflow at all on this testcase, yes.  All the remaining cost would be painting.
... with bug 524925, of course.
(Reporter)

Comment 24

6 years ago
Note that we would also need to deal with transformed ib splits a bit too; right now they get the positioned wrapper blocks.  But we could just reframe an ib split on transform changes; that situation is cheap to detect and I bet rare.
Depends on: 691651
I filed bug 691651 for doing that.
(Reporter)

Comment 26

6 years ago
Oh, hmm.  I wonder why I was seeing no time spent in reflow when I hacked the transform stuff here, given bug 524925...

Updated

5 years ago
Blocks: 776190
Blocks: 918620

Comment 27

4 years ago
Removing qawanted since the regression has already been filed (fyi: it doesn't reproduce on current versions).
Keywords: qawanted
I can't seem to find IE Maze Solver anywhere on the web anymore.
Did anyone save a copy to disk by any chance?
http://web.archive.org/web/20140325062456/http://ie.microsoft.com/testdrive/Performance/MazeSolver/Default.html

works for me.
Thanks!  It looks like they've put it on github actually:
https://github.com/MicrosoftEdge/Demos/tree/master/mazesolver
You need to log in before you can comment on or make changes to this bug.