Closed Bug 838642 Opened 9 years ago Closed 9 years ago

nsContainerFrame::StealFrame is O(n)

Categories

(Core :: Layout, defect)

defect
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla22

People

(Reporter: mats, Assigned: mats)

References

(Blocks 1 open bug)

Details

(Keywords: perf)

Attachments

(2 files)

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).
Boris, you've reviewed some of my nsFrameList patches in the past iirc,
can you review this?  Give it to roc otherwise, thanks.
Attachment #710756 - Flags: review?(bzbarsky)
Blocks: 838671
Blocks: 838688
Blocks: 838706
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
Attachment #710756 - Flags: review?(bzbarsky) → review+
Comment on attachment 710758 [details] [diff] [review]
Remove nsContainerFrame::RemovePropTableFrame which is now unused

r=me
Attachment #710758 - Flags: review?(bzbarsky) → review+
> 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
Ah, indeed.  That's probably good enough, yes.
https://hg.mozilla.org/mozilla-central/rev/e8ca3fa39660
https://hg.mozilla.org/mozilla-central/rev/0a77b9b02ba5
Status: NEW → RESOLVED
Closed: 9 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla22
You need to log in before you can comment on or make changes to this bug.