626927 - Significant perf regression painting lots of table cells

Status: RESOLVED DUPLICATE of bug 1409047

(Core :: Graphics, defect)

Description

[Michael Sinz]

Attachment: Zip file containing the HTML, CSS, and JS that shows the perf problem

I am noticing a significant reduction in performance in the performance of DOM manipulation relative to Firefox 3.6 and significantly worse performance then Chrome or Safari.

This may be related to DOM layout events.  The example, which can be seen at http://sinz.org/Maze/ (and in the attached ZIP file - no server required), spends a lot of time changing element background color from black to white.  In other places it changes some black to blue.  In all cases it is just background color changes.

Note that Firefox used to be close to Safari and Chrome, albeit lately Chrome has gotten faster.  The Firefox 4 betas run at 1/4 the speed of Firefox 3.6 and around 1/9th the speed of Chrome and Safari.

Example numbers taken on my machine:
Firefox 3.6.13:     448 tiles/second
Firefox 4.0 b9:     121 tiles/second
Chrome 9.0.597.45: 1184 tiles/second
Safari 5.0.3:       635 tiles/second

Note that IE8 is so slow that it is not worth mentioning.

Use the Table form of the layout to see these perf behaviors.  Other forms have slightly different characteristics, more so on FF than the Chrome or Safari.

Once the maze is rendered you can see the other color flipping perf regressions by typing "O" to clear the information DIV and then "H" to hint at the maze solution.  Press "U" to undo the hint.  These operations can be done in "real time" and produce an interesting visual effect and also clearly shows the perf differences (in addition to the initial maze generation)

Larger window sizes have greater perf issues in all browsers - best to use large or full screen window to get the most perf/profiling information when testing.

Comment 1

[Boris Zbarsky [:bzbarsky]]

Michael, thanks for the bug report!

The regression range is http://hg.mozilla.org/mozilla-central/pushloghtml?fromchange=5fda39cd703c&tochange=96de199027d7 (at least on Mac) when running the "table.html" test.

A profile shows that 97% of the time is spent painting.  About 19% is building the display list, about 22% under ComputeVisibilityForRoot, 19% is WillEndTransaction (enumerating over the hashtable calling UpdateDislayItemDataForFrame), 28% under BuildContainerLayerFor.

So presumably a regression from bug 564991.

roc, the testcase just has a big table and then goes through and changes a bunch of classes on the cells that affect the background color.  But it sounds like for each paint we end up dealing with all the cells or something?  Memories of that raytracer testcase.  :(

Comment 2

[Robert O'Callahan (:roc) (email my personal email if necessary)]

This is another example of using thousands of HTML elements instead of a graphics API. Much as I'd like to make this fast, we have higher priorities right now. We should revisit this stuff after we've implemented display-list-based-invalidation, because any approach to making this fast would involve incremental updates to the display items associated with a layer, and that's going to be intimately tied up with DLBI.

Comment 3

[Michael Sinz]

While I agree that the canvas API would be nice but the regression here is somewhat amazing.  To put the perf in perspective, my PalmPre cell phone running an ARM processor gets over 145 tiles/second on a screen with even more cells than the test case I ran on my 2.4GHz dual-core Mac.  (The Pre did 145 tiles/second on a 77x113 sized maze.)

And while using thousands of elements may be over the top, it does show some algorithmic problems that may be harder to witness at smaller table sizes like what happens at the NASDAQ site or much less complex sites such as shopping sites, etc.

For me the bigger issue is that this will tend to make point out that HTML pages with any complexity will be ever so slightly (or significantly) slower.  (The account activity page at my bank produces a nice large table of activity details that really do not belong as graphics APIs.)

PS - I had not intended this to be a benchmark until I ran into the problem of it running (or should I say not running) on IE.  To help diagnose things I added some information display to the program and restructured with different display layout mechanisms.  (Due to input from friends that worked on the IE team)

Comment 4

[Boris Zbarsky [:bzbarsky]]

Michael, there is definitely a known algorithmic problem here: painting a table is O(N) in the number of the table's cells visible on screen, even if you only changed some of the cells.  This means that if you change the cells one at a time, with paints in between, the overall operation is O(N^2) in the number of cells.

Except for very large N (which don't happen in the layout table or NASDAQ cases) and high update rate (which also don't happen there) cases where the cells _are_ being updated a few at a time instead of all at once (also rare), it doesn't cause an issue...

The regression here is unfortunate, but the code that caused it is needed to make other, much more common, things paint significantly faster.

We do plan to work on a fix for this; as roc says we don't _want_ to be slow here.  It's just that the timeframe for Firefox 4 is too tight at this point to rearchitect the graphics subsystem around cases like this without breaking other things in the process....

Comment 5

[Michael Sinz]

I do understand - I was just a bit surprised by the scale of the change.

Comment 6

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Your bank's account activity page is unlikely to have thousands of cells visible at once.

Comment 7

[Randell Jesup [:jesup] (needinfo me)]

With dlbi landed (see bug 770011), it's as fast as Chrome (even a little faster!) on my dev system, IF it can complete before some timer goes off (a few seconds).  After the timer goes off, it slows down by 6-12x.  Very encouraging, if we can resolve the timer issue!

Comment 8

[Guilherme Lima]

Maze Complete   (Table)   [Firefox 29]
Maze size: 110 x 48 (5280 tiles)
260 	ms in JavaScript 	0.049 	ms/tile
24587 	ms not in JavaScript 	4.656 	ms/tile
24847 	ms total time 	4.705 	ms/tile
212.5 	tiles per second 	11 	tiles/step
-----

Maze Complete   (Table)   [Chrome 31]
Maze size: 110 x 51 (5610 tiles)
110	ms in JavaScript	0.019	ms/tile
3759	ms not in JavaScript	0.67	ms/tile
3869	ms total time	0.689	ms/tile
1449.98	tiles per second	11      tiles/step
-----

Maze Complete   (Table)   [Mozilla 11] - WHAT? Anyway, it's IE 11
Maze size: 110 x 52 (5720 tiles)  
613     ms in JavaScript        0.107 ms/tile 
17230   ms not in JavaScript    3.012 ms/tile 
17843   ms total time   3.119   ms/tile 
320.57  tiles per second        11      tiles/step

Comment 9

[Michael Sinz]

Update - on my MBP, these are the performance numbers - not looking good for Firefox.


Maze Complete   (Table)   [Firefox 33]
Maze size: 111 x 72 (7992 tiles)
152 	ms in JavaScript 	0.019 	ms/tile
37275 	ms not in JavaScript 	4.664 	ms/tile
37427 	ms total time		4.683 	ms/tile
213.53 	tiles per second 	11 	tiles/step
--------------------------------------------------
Maze Complete   (Table)   [Chrome 40]
Maze size: 111 x 72 (7992 tiles)
114	ms in JavaScript		0.014	ms/tile
6400	ms not in JavaScript	0.8	ms/tile
6514	ms total time		0.815	ms/tile
1226.89	tiles per second		11	tiles/step
--------------------------------------------------
Maze Complete   (Table)   [Safari 8]
Maze size: 111 x 72 (7992 tiles)
86	ms in JavaScript		0.01	ms/tile
5181	ms not in JavaScript	0.648	ms/tile
5267	ms total time		0.659	ms/tile
1517.37	tiles per second		11	tiles/step

Comment 10

[Randell Jesup [:jesup] (needinfo me)]

Linux64 Xeon
Aurora/35 local build (opt, --enable-profiling)
for a 30x30 maze (small), average perf on reloads is 880-1020 tiles/s (note: use Restart for more consistent results than reload).
On Chrome 40, it gets about 2000-2400 (typ. 2200-2300) tiles/s.

As size increases, it gets worse:
Aurora/35 125x77: 205 tiles/s
Chrome/40 110x71: 1319 tile/s

One thing I notice which might account to the slowdown and maybe the overall difference:
Painting on larger mazes in FF is "jumpy" - most of the time you can see it go almost "as it goes", then suddenly a chunk of the maze will drop in all at once.  I suspect the "chunks" are going much faster, and we're simply painting more aggressively as cells change instead of chunking them.

Note: We were as fast as Chrome after DLBI landed IF the maze was small (per my comment above).  Perhaps we were suppressing paint (or chunking more) for N ms after a user interaction or load.  In any case, the small-maze behavior seems to have regressed since then.  Not sure how much bug mazes have regressed.  comment 8 though would indicate it was similarly slow for large mazes last December.

bz's comment about applicability still is true though.  For the Web, this is an edge-case.  Webby cases with large tables of small entries would be updating them all at once, or updating a one or a couple.  *Large* tables like this are generally rare outside of a few edge cases, and most "large" tables tend to be very wide or very long, not both.  Possible exception would be a google docs-like spreadsheet - but they likely don't use naive rendering, and even there likely don't hit corner cases like this.

Amusing Side note: Careful resizing it in Chrome 40.  Resizing it larger (especially for larger sizes) will almost always hang the Chrome content process requiring me to close the tab.  We don't have that problem.

Less amusing side note: while not likely a great JS benchmark, I notice Safari is faster than Chrome or FF in the JS portion, and on Mike's Mac, the difference is around 2x (~10ms vs ~19ms/tile)

Comment 11

[Michael Sinz]

I agree that it is not a major case on the web, especially since the right way to do something like this (if that was even useful) would be via <canvas>.

Things are changing but it is an interesting edge case test for an edge case that may not be interesting anymore.

Comment 12

[Michael Sinz]

Note that the regression has gotten worse and is now over 10x slower than Chrome for the Table version.

Comment 13

[Boris Zbarsky [:bzbarsky]]

Bug 1409047 is tracking comment 12.

Comment 14

[BugBot [:suhaib / :marco/ :calixte]]

In the process of migrating remaining bugs to the new severity system, the severity for this bug cannot be automatically determined. Please retriage this bug using the new severity system.