838642 - nsContainerFrame::StealFrame is O(n)

Status: RESOLVED FIXED

(Core :: Layout, defect)

Description

[Mats Palmgren (inactive)]

nsContainerFrame::StealFrame is O(n) because it iterates over the frame
lists to find out which list the child is on.  We don't need to do that -
if the frame isn't the first/last sibling then we can simply unhook it
from its siblings without updating its nsFrameList, and if it is the first
or last sibling we only need to compare it to the First/LastChild() of the
potential frame lists it could be on.  This makes StealFrame O(1).

Comment 1

[Mats Palmgren (inactive)]

Attachment: Make nsContainerFrame::StealFrame O(1)

Boris, you've reviewed some of my nsFrameList patches in the past iirc,
can you review this?  Give it to roc otherwise, thanks.

Comment 2

[Mats Palmgren (inactive)]

Attachment: Remove nsContainerFrame::RemovePropTableFrame which is now unused

Comment 3

[Mats Palmgren (inactive)]

Try run for bug 838642, bug 838671, bug 838679, bug 838688, bug 838706:
https://tbpl.mozilla.org/?tree=Try&rev=1aa9c6c26a55

Comment 4

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 710756 [details] [diff] [review]
Make nsContainerFrame::StealFrame O(1)

So in nsContainerFrame::StealFrame, we depend on the nsFrameList::StartRemoveFrame calls never leaving a list empty unless the StartRemoveFrame call actually happened on that list, right?

That's worth commenting somewhere...

This patch gives me the creeps.  Can we at least assert somehow that the frame is in one of the lists involved, please?

With that, r=me

Comment 5

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 710758 [details] [diff] [review]
Remove nsContainerFrame::RemovePropTableFrame which is now unused

r=me

Comment 6

[Mats Palmgren (inactive)]

> we depend on the nsFrameList::StartRemoveFrame calls never leaving a list empty...

Yes, that is the documented behavior of StartRemoveFrame.  Let me know if you
find that sufficient or if you want further documentation.

With some added assertions:
https://hg.mozilla.org/integration/mozilla-inbound/rev/e8ca3fa39660
https://hg.mozilla.org/integration/mozilla-inbound/rev/0a77b9b02ba5

Comment 7

[Boris Zbarsky [:bzbarsky]]

Ah, indeed.  That's probably good enough, yes.

Comment 8

[Gregory Szorc [:gps]]

https://hg.mozilla.org/mozilla-central/rev/e8ca3fa39660
https://hg.mozilla.org/mozilla-central/rev/0a77b9b02ba5