1201692 - ExplicitChildIterator::Seek leads to O(N^2) behavior during frame reconstruction

Status: RESOLVED FIXED

(Core :: DOM: Core & HTML, defect)

Description

[Boris Zbarsky [PTO through Aug 25, :bzbarsky, bz on IRC]]

This is basically a regression from bug 653881.  I should have caught it then in review...

The old seek() call on the ChildIterator in FindInsertionPrevSibling was O(1) in the common case.  But the new Seek() call on ExplicitChildIterator is O(N) in all cases, since it always does a walk along all the kids until it gets to the one we want.

We should be able to fast-path at least the common case here, I'd think: that aChildToFind is a child of mParent.  In that case, can't we just set mChild to aChildToFind and return?

Comment 1

[Boris Zbarsky [PTO through Aug 25, :bzbarsky, bz on IRC]]

Attachment: Testcase based on the one linked from bug 1191389

Comment 2

[Boris Zbarsky [PTO through Aug 25, :bzbarsky, bz on IRC]]

Attachment: Add a fast path to ExplicitChildIterator::Seek for the common case of seeking an actual DOM child of the parent node

This speeds up the testcase by 30% or so

Comment 3

[Boris Zbarsky [PTO through Aug 25, :bzbarsky, bz on IRC]]

Try push at https://treeherder.mozilla.org/#/jobs?repo=try&revision=5eabce5e52ac looks good to me.

Comment 4

[Pulsebot]

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

Comment 5

[Carsten Book [:Tomcat]]

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