Open Bug 776190 Opened 8 years ago Updated 6 years ago

Make maze solver fast

Categories

(Core :: Layout, defect)

defect
Not set

Tracking

()

People

(Reporter: bzbarsky, Unassigned)

References

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

Details

(Keywords: meta, Whiteboard: ietestdrive)

Attachments

(1 file)

We just need a tracking bug for this.

The outstanding issues, on a high level, are:

1)  Bug 691651: we need to stop reframing and reflowing so much here.
2)  Bug 691645: we need to stop overinvalidating.

Once we get those two done, we should reprofile.

#1 should be about a 3x speedup on its own, for what it's worth.  Mats, do you know whether you have time to look into it?
Depends on: 776193
Whiteboard: ietestdrive
Depends on: 641340
OS: Mac OS X → All
Hardware: x86 → All
Keywords: meta
On my local machine, latest Nightly is already faster than Chrome dev build or Internet Explorer 9

For 30x30
Nightly : 7.8 s
Chrome dev : 9.1 s
Internet Explorer : 13 s

For 40x40
Nightly : 24 s (though the browser kept hanging after the test was complete)
Chrome dev : 8.8 s
Internet Explorer : 27 s

Its amusing that chrome 30x30 is slower than 40x40.
Note that the mazes are different at different sizes, and how much of the maze is explored before it finds a solution - and you can generate random mazes, but there's no clear way to set the random seed to get a reproducible random maze.  (The Sinz maze creator has a seed option for this reason.)  One could modify the JS for the IE maze solver to let it take a seed I'm sure
Ok, something is very, very odd here.

Fast Linux XEON desktop
Linux64 pull from head, Debug build but optimized (I'll do a non-debug build to cross-check):
20x20: 1.3 seconds(!) (Chrome: 0.8)
30x30: 50 seconds(!!!) (Chrome 22 dev channel: 6.7)
40x40: 65 sec (!) (Chrome: ~6.5 - note it spends a lot less time backtracking)
For me on Windows 7 with Intel T4300:
        Nightly     IE 9     Chrome 22
20x20:     1.3        2.3        1.3
30x30:    67         38         11
40x40:   177         62         13
On MacOSX:
      Nightly(20121001)  Chrome(24.0.1283.0)
30x30:  6.4                5.2
40x40:  25                 5.4

In a local --enable-shark build I get similar results as Nightly.
The time profile is dominated by building display lists.

There's one entry that looks odd: about 7% is spent in isalloc_validate, which
seems excessive. (AFAICT, this function is only used by default on OSX though)
http://hg.mozilla.org/mozilla-central/annotate/85df971e0db1/memory/mozjemalloc/jemalloc.c#l4418
Ok, without debug turned on it's much faster - ~6.5s for 30x30, 25-30 for 40x40, similar to yours

jprof says 90% of both is PresShell::PaintFrame.  Of that, ~55% is nsDisplayList::PaintForFrame, ~25% is nsIFrame::BuildDIsplayListForStackingContext().
For me, nightly is not compare to chrome yet. 
Windows XP pro, 32 bit.
CPU: AMD Athlon 64 X2 6000+, ram: 4gb , video: AMD HD6450 

        nightly(20121001030603)  chrome (23.0.1271.10 dev-m)
20x20     2.6                    0.7
30x30     43                     6.6
40x40     ---                     11

(If i start firefox after windows sleeping mode - it shows 7.2 for 20x20 and 75 for 30x30).

How can i do jprof for you?
I don't think we need any more profiling here right now. We know what the problems are.
MazeSolver is now officially fast on Nightly!
i filed a bug which is maze solver related :

https://bugzilla.mozilla.org/show_bug.cgi?id=786585
to Dennis Jakobsen: 
It is not. Today's nightly still takes 42s for 30x30. How could it be "officially fast"? It still has a lot of depending bugs to be solved.
I'm seeing:
20x20   0.7s
30x30   5.7s
40x40   5.7s

That IS fast, but if it can go even faster, great!
(In reply to Dennis Jakobsen from comment #13)
> I'm seeing:
> 20x20   0.7s
> 30x30   5.7s
> 40x40   5.7s
> 
> That IS fast, but if it can go even faster, great!

You are seeing these small numbers because luckily you got the solution that was straight forward. Try again and again and you might get a decept path size solution in which Chrome will win by a huge difference.
(In reply to Dennis Jakobsen from comment #13)
> I'm seeing:
> 20x20   0.7s
> 30x30   5.7s
> 40x40   5.7s
> 
> That IS fast, but if it can go even faster, great!

You seeing these small numbers, because i bet you have OS other than mine windows XP. But there is a difference in rendering speed between XP and 7, linux and mac, etc. Please describe your configuration like others.
(In reply to mr.troll from comment #15)
> You seeing these small numbers, because i bet you have OS other than mine
> windows XP. But there is a difference in rendering speed between XP and 7,
> linux and mac, etc. Please describe your configuration like others.

That also might be the case, but I am also on Windows 7, and sometimes, rarely, I also see numbers this low for 40x40, as the path taken by the solver is almost straight towards the exit.
Using the link above, the 20x20, 30x30, and 40x40 mazes are identical, both the first time they're selected and if you re-select with the dropdown after running a test, and so are the solution paths.  The path to solve the maze if you restart without switching sizes is NOT the same as the path on the initial solution, though it appears to stay the same after that.

They may NOT be the same on initial load (of 30x30) across different browsers (Chrome vs FF), but if you switch to 20x20 and back to 30x30 the maze is the same.  HOWEVER, the path take to solve the exact same maze in FF and Chrome is DIFFERENT, so cross-browser comparison using this test is NOT possible at a fine-grained level (though on a gross level you can certainly see differences).  

Part of it I'm sure is that Chrome's RNG and ours return different sequences, even with the same seed.  The maze would need to be refactored to use an internal JS RNG (or internal really bad RNG like "take the next entry from this hard-coded list of "random" numbers).

There may be variability in the time taken to solve it due to timers, GFX drivers, etc, and they may have changed the page at some point to give a consistent seed.  But they're consistent now (just had three running on three screens in front of me: Fast Linux64 Xeon, Win7 core-i7 laptop (~2.8GHz?) and WinXP Athlon X4 965 3.4 Ghz).

I consistently get 0.8, 6.5 and 8.7-8.8 on the Oct 8th local opt m-c build on Xeon - which is a major improvement from Oct 1st for 40x40.
Here are my results :

My main profile with HA enabled : 2.9, 26 and 213 seconds
Clean profile : 0.9, 14 and 40 seconds
This is on my laptop running windows 8 with intel core i5-2410M dual-core @2.30 GHz, nvidia geforce 525M driver version 306.97 and 4GB ram.

Are the slow results caused by hardware acceleration? Are there any bugs about that?
Just asking seeing the amazing results you guys are achieving, i would love to have something similar on my regular profile. Other than that i still have to give you guys props you did an amazing job improving the performance. Far better than what it used to be.
Please try turning off HA, and also try restarting with all extensions disabled...  I'll bet one of them will be closer to the clean profile, and that might be useful to know.  (though if it's an extension, .... consider nuking it)
Thanks for the quick reply, after some quick diagnostic i found the culprit.
The add-ons don't seem to have any significant impact instead a preference was at fault : 

"layout.frame_rate.precise", true
"layout.frame_rate", 240

which was suggested somewhere for a smoother scrolling experience if i recall correctly. It causes more frequent repainting which is obviously the cause, after resetting to default i got the following results 0.9, 9.9 and 29 seconds. A pretty dramatic improvement. So thanks again.
> "layout.frame_rate", 240

Uh...  Whoever suggested that is nuts.  The default there is 60, which is the rate at which your monitor paints!  So what you had going on was painting 4 times as often as you can actually get pixels on screen.

I wonder whether we should disable that pref, or rename it, or something.  :(
You are right, this is more proof that it is not wise to tinker with the settings too much. At the time i didn't know that it affected the browser as a whole. I thought that it was an equivalent to using the SmoothWheel add-on due to Bug 206438 being fixed. Guess i should have deducted that from the name of the pref.
There seems to be a regression in this.
In the 20x20 and the 40x40 maze (but *not* 30x30), Nightly quickly starts repainting progressively larger rectangles.
Please file a new bug about that.  Thanks.
Results in 40x40:
Using the latest Yandex Browser (Not sure what version of Chromium): 5.4 - 6
Using the latest Nightly 24: 19-21

Very disappointed in these results, and this is the latest Nightly under Central as of 2013-05-29. (Typing on the 30th at 2 AM, so no new version yet)

Then again, I have been seeing this result from the Fox since last year, I test the latest Nightlies with this test every 1-2 since who knows, but it has been the majority of last year as well.

Reproduced on 2 computers:
1. i3-540, GTX 650. 5400RPM HDD, 8 GB RAM
2. Fx-4100. GTX 660, 7200RPM HDD. 8 GB RAM
Megarid, first please describe which OS you are using on both PC, was the profile clean or not. 
Second, nobody officially said that firefox is as fast as chrome in this test. The bug is not closed and it depends on many bugs. In fact Firefox is faster than year before. I strongly believe that speed depends of OS, in linux firefox is much faster in this test than in windows XP. 

P.S. The latest Yandex Browser is the same as Chrome/25, but results are the same as in Chrome 28 or Opera Next (based on chrome 28). So speed doesn't depends on version (until they'll rewrite DOM implementation in Blink).
I tested the latest, must be 29 of Chromium and it got to the end in 10 - 17 seconds, must be a problem with the Blink.

And I am not merely saying that it has to be as fast as Chromium-based browsers, but 19 seconds vs 5.4 is a huge gap and it should be noted.

The i3-540 has Windows 7 Ultimate 64-bit.
The FX-4100 has Windows 7 Home Premium.

19 seconds came from the Safe Mode in the Nightly version, 20 - 21 came from regular mode in Nightly.
Also, I always test with a clean profile, before testing I make sure that nothing exists from Firefox to regress it.

Firefox is optimized for Linux variants, or so said from the developer in PaleMoon, so Linux naturally has the advantage.
Seriously, no updates?
Anything we can tweak from our end?
This is driving me insane. How is it possible for Chrome to surpass Firefox and Firefox just stays constant on this test?
Developers from Mozilla should have great know-how of how this thing works, even if it has bugs, since bugs didn't stop Chrome from doing a better job.

1 and a half years of my time to see if Firefox improves on this and nothing, disappointing.
This thing should have been fast (5 seconds) by now.

Side rant:
Same goes for browser start-up time, even if I had 50 add-ons. Chromium browsers load-up the browser fast even for 17 extensions, but Firefox takes seconds more with 12, this is absurd. This should have been fixed years ago, if you guys were able to fix the memory leaks that should be fixed from the add-on developers you guys can fix the start-up time no matter how many add-ons we have, especially on fast machines, so this is more disappointment.

Windows 7 Home Premium 64-bit
FX-4100 (3.6GHz w/Turbo Core 3.8GHz)
Nvidia GeForce GTX 660
8Gb DDR3-1333MHz
7,200 RPM HDD (6Gpbs)
Depends on: 998232
You need to log in before you can comment on or make changes to this bug.