849263 - MovingBoxes test spends lots of time updating overflow areas

Status: RESOLVED FIXED

(Core :: Layout, defect)

Description

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

https://raw.github.com/tumult/PerformanceBenchmarks/master/MovingBoxes.html (needs to be downloaded, can't be run from that URL) is very slow.  This has regressed sometime since Firefox 4.  I haven't figured out a regression range, but my guess is that it's either bug 524925 or bug 815666 since it's spending a massive amount of time inside OverflowChangedTracker::Flush (poor-man's profiling, i.e., breaking in gdb, showed only that and painting/compositing stuff).  (I would expect bug 524925 to have put an O(N^2) performance problem in this testcase and bug 815666 to have fixed it, actually.  Though I don't quite understand what bug 815666 is doing, and it doesn't actually seem quite right to me.)

Comment 1

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Also, this came from:
http://blog.tumult.com/2013/02/28/transform-translate-vs-top-left/

Comment 2

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: Make OverflowChangedTracker actually sort by depth in the tree where it intended to.

Comment 3

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

I still have some questions about the stuff OverflowChangedTracker::Flush is doing, but those can wait... at least until I eat breakfast, and perhaps longer.

Comment 4

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

"blocks" bug 815666 at least in that it fixes a mistake in bug 815666 that prevented that bug from making the performance optimization that it intended to.  Probably regressed by bug 524925, though, but I haven't checked.

Comment 5

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

(In reply to David Baron [:dbaron] (don't cc:, use needinfo? instead) from comment #1)
> Also, this came from:
> http://blog.tumult.com/2013/02/28/transform-translate-vs-top-left/

The only contact info I've found on that would be replying on twitter to:
https://twitter.com/hypeapp/status/307272488138711041
which I'll probably try doing after this lands.

Comment 6

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: testcase

I'll attach the testcase for posterity in case that github repo changes or disappears.

Comment 7

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Oh, and the actual regression range for the perf regression in the first phase of the test is:
https://hg.mozilla.org/mozilla-central/pushloghtml?fromchange=6338a8988917&tochange=7e4c2abb9fc9
i.e., bug 157681, which converted top/left changes to use the codepath from bug 524925.  But the transform phase of the test probably regressed earlier.

(That said, there's probably also work to do to make this faster after this patch.)

Comment 8

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

Comment on attachment 722835 [details] [diff] [review]
Make OverflowChangedTracker actually sort by depth in the tree where it intended to.

Review of attachment 722835 [details] [diff] [review]:
-----------------------------------------------------------------

Ugh.

Comment 9

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

https://hg.mozilla.org/integration/mozilla-inbound/rev/9a9689e414e4

Comment 10

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/9a9689e414e4