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

Status: RESOLVED FIXED

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

Description

[Boris Zbarsky [:bzbarsky]]

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 [:bzbarsky]]

Attachment: Testcase based on the one linked from bug 1191389

Comment 2

[Boris Zbarsky [:bzbarsky]]

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 [:bzbarsky]]

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