Open Bug 641340 Opened 10 years ago Updated 10 months ago

IE Maze Solver testcase hits hotspot in nsFloatManager::GetFlowArea


(Core :: Layout: Block and Inline, defect)

Not set




(Reporter: bzbarsky, Unassigned)


(Depends on 1 open bug, Blocks 2 open bugs, )


(Keywords: perf, Whiteboard: ietestdrive [qa+])


(1 file)

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?
Keywords: perf
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?
Oh, this is semi-ridiculous.

1)  There is nothing in-flow inside that maze: just floated borders and abs pos
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.)
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.
A candidate for blocking Bug 86952.
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
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
> 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.
See Also: → 641341
In this comparison (,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.
Attached file 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%.
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.
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+]
Please file a separate bug for the regression.  Do NOT hijack this bug.
Filed bug 691414 on the regression
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.
See Also: → 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?
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.
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.
Oh, hmm.  I wonder why I was seeing no time spent in reflow when I hacked the transform stuff here, given bug 524925...
Blocks: 776190
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?
You need to log in before you can comment on or make changes to this bug.