845526 - FrameLayerBuilder::RemoveFrameFromLayerManager can cause O(N^2) behavior

Status: RESOLVED FIXED

(Core :: Layout, defect)

Description

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

Every time we tear down a frame we add to thebesData->mRegionToInvalidate. This can get arbitrarily complex, so N calls to RemoveFrameFromLayerManager take O(N^2) time.

To reproduce:
1) Load http://www.gutenberg.org/cache/epub/42205/pg42205.txt
2) in Web Console, do
var s=document.documentElement.style;s.transformOrigin="top left";s.transform="scale(2)"
3) Reload page --- hangs.

I think we may be prerendering the root element --- that may be another bug.

Comment 1

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

Attachment: fix

Comment 2

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

https://hg.mozilla.org/integration/mozilla-inbound/rev/05c35dc73323

Comment 3

[Ed Morley [:emorley]]

Push backed out for failing to compile on Windows (so far):
https://tbpl.mozilla.org/?tree=Mozilla-Inbound&onlyunstarred=1&rev=dba7a059ed22

https://hg.mozilla.org/integration/mozilla-inbound/pushloghtml?changeset=0a91da5f5eab

Comment 4

[Jared Wein [:jaws] (please needinfo? me)]

This patch shouldn't have caused the build failures on that inbound push. Can we try this again?

The build failures appear to be related to the patches for bug 829557.

Comment 5

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/b0857123e281

Comment 6

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/b0857123e281

Comment 7

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/04856b09ea1e

Comment 8

[Philip Chee]

This patchset looks remarkably empty...
> https://hg.mozilla.org/mozilla-central/rev/04856b09ea1e

Comment 9

[Jared Wein [:jaws] (please needinfo? me)]

(In reply to Philip Chee from comment #8)
> This patchset looks remarkably empty...
> > https://hg.mozilla.org/mozilla-central/rev/04856b09ea1e

That's because this patch ended up getting pushed to central twice.

Comment 10

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

Yes, my fault, sorry.