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?

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 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.)

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.

O(N^2)? 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

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.

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.

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.

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?

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.

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.

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...

Removing qawanted since the regression has already been filed (fyi: it doesn't reproduce on current versions).

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