Last Comment Bug 641340 - IE Maze Solver testcase hits hotspot in nsFloatManager::GetFlowArea
: IE Maze Solver testcase hits hotspot in nsFloatManager::GetFlowArea
Status: NEW
ietestdrive [qa+]
: perf
Product: Core
Classification: Components
Component: Layout: Block and Inline (show other bugs)
: Trunk
: All All
: -- normal with 21 votes (vote)
: ---
Assigned To: Nobody; OK to take it and work on it
:
Mentors:
http://web.archive.org/web/2014032506...
Depends on: 670311 691414 691651
Blocks: 776190 ietestdrive
  Show dependency treegraph
 
Reported: 2011-03-13 10:31 PDT by Boris Zbarsky [:bz]
Modified: 2015-09-30 13:43 PDT (History)
36 users (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
jprof at 2ms (1.72 MB, text/html)
2011-09-28 05:51 PDT, Randell Jesup [:jesup]
no flags Details

Description Boris Zbarsky [:bz] 2011-03-13 10:31:07 PDT
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?
Comment 1 Boris Zbarsky [:bz] 2011-03-13 12:18:53 PDT
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?
Comment 2 Boris Zbarsky [:bz] 2011-03-13 12:47:58 PDT
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?
Comment 3 David Baron :dbaron: ⌚️UTC-7 (review requests must explain patch) 2011-03-13 13:02:03 PDT
(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.)
Comment 4 Boris Zbarsky [:bz] 2011-03-13 13:19:09 PDT
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 [Baboo] 2011-03-30 13:14:19 PDT
O(N^2)?
A candidate for blocking Bug 86952.
Comment 6 Ahmed Aly 2011-06-01 08:01:29 PDT
opera pass this test amazingly
Comment 7 Girish Sharma [:Optimizer] 2011-06-26 09:32:36 PDT
Please add Windows platform also. I can confirm that Maze solver runs very slow on Windows comared to other browsers
Comment 8 Matt Evans [:mevans] 2011-07-08 00:19:30 PDT
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
Comment 9 Boris Zbarsky [:bz] 2011-07-08 12:57:10 PDT
> 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.
Comment 10 Jeff Muizelaar [:jrmuizel] 2011-08-29 06:55:47 PDT
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.
Comment 11 Chris Jones [:cjones] inactive; ni?/f?/r? if you need me 2011-08-30 23:32:31 PDT
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.
Comment 12 Randell Jesup [:jesup] 2011-09-28 05:51:33 PDT
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%.
Comment 13 Boris Zbarsky [:bz] 2011-09-30 00:35:10 PDT
Bug 670311 will hopefully make this all better.
Comment 14 Randell Jesup [:jesup] 2011-10-03 08:27:35 PDT
FYI, TomsHardware indicates FF7 got 10 seconds *worse* than FF6 on this test - so we went in the wrong direction.
Comment 15 Boris Zbarsky [:bz] 2011-10-03 08:30:26 PDT
Regression range welcome.  Possibly in an actual metabug tracking the test that all the specific bugs block?
Comment 16 Randell Jesup [:jesup] 2011-10-03 09:28:07 PDT
I'd love to - but there's no way I have time. :-(  Perhaps QA could verify the regression and bisect.
Comment 17 Matt Evans [:mevans] 2011-10-03 09:43:54 PDT
Juan or Anthony can we get someone assigned to verify the regression?
Comment 18 Boris Zbarsky [:bz] 2011-10-03 10:10:49 PDT
Please file a separate bug for the regression.  Do NOT hijack this bug.
Comment 19 Randell Jesup [:jesup] 2011-10-03 10:55:28 PDT
Filed bug 691414 on the regression
Comment 20 Boris Zbarsky [:bz] 2011-10-03 19:49:13 PDT
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.
Comment 21 David Baron :dbaron: ⌚️UTC-7 (review requests must explain patch) 2011-10-03 20:13:34 PDT
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?
Comment 22 Boris Zbarsky [:bz] 2011-10-03 20:15:57 PDT
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.
Comment 23 David Baron :dbaron: ⌚️UTC-7 (review requests must explain patch) 2011-10-03 20:16:31 PDT
... with bug 524925, of course.
Comment 24 Boris Zbarsky [:bz] 2011-10-03 20:19:44 PDT
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.
Comment 25 David Baron :dbaron: ⌚️UTC-7 (review requests must explain patch) 2011-10-03 20:22:12 PDT
I filed bug 691651 for doing that.
Comment 26 Boris Zbarsky [:bz] 2011-10-03 20:22:22 PDT
Oh, hmm.  I wonder why I was seeing no time spent in reflow when I hacked the transform stuff here, given bug 524925...
Comment 27 Ioana (away) 2013-09-23 07:04:19 PDT
Removing qawanted since the regression has already been filed (fyi: it doesn't reproduce on current versions).
Comment 28 Mats Palmgren (:mats) 2015-09-30 13:29:39 PDT
I can't seem to find IE Maze Solver anywhere on the web anymore.
Did anyone save a copy to disk by any chance?
Comment 30 Mats Palmgren (:mats) 2015-09-30 13:43:53 PDT
Thanks!  It looks like they've put it on github actually:
https://github.com/MicrosoftEdge/Demos/tree/master/mazesolver

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