904602 - Optimize various tree traversing in Range

Status: RESOLVED FIXED

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

Description

[Olli Pettay [:smaug][[e-mail]]]

Attachment: artificial test

Currently Range uses GetParentNode to find the subtree root.
nsINode::SubtreeRoot() should work just fine. That one is O(1)

nsRange::ContentRemoved may end up doing nsContentUtils::ContentIsDescendantOf
twice. Reasonably often mStartParent and mEndParent are the same, so we can
optimize out one of those possibly slow calls.

(Unfortunately SubtreeRoot() check inside nsContentUtils::ContentIsDescendantOf
wouldn't be too useful since the parent chain is actually changed *after*
nsIMutationObserver::ContentRemoved call.)

Comment 1

[Olli Pettay [:smaug][[e-mail]]]

Attachment: patch

Gives 40% boost in that artificial test.


Note, I decided to not change
   if (!mEnableGravitationOnElementRemoval) {
     // Do not gravitate.
     return;
in any way, since that is used only in some odd special cases.


https://tbpl.mozilla.org/?tree=Try&rev=d1de420f93c6

Comment 2

[Olli Pettay [:smaug][[e-mail]]]

Patch seems to also save over 9000000 method calls when running 
http://mxr.mozilla.org/mozilla-central/source/dom/imptests/editing/conformancetest/test_runtest.html?force=1

Comment 3

[Mats Palmgren (inactive)]

Comment on attachment 789581 [details] [diff] [review]
patch

>+  } else if (didCheckStartParentDescendant &&
>+             mStartParent == mEndParent) {

Nit: the condition fits on one line

The changes to nsRange::ContentRemoved looks correct.

nsRange::IsValidBoundary also looks correct, but a bit risky since
there's a lot code reaching IsValidBoundary... I see that SubtreeRoot()
has an assertion checking for this though.

I note that nsRange::ContentRemoved calls DoSetRange which calls
IsValidBoundary although only as part of an assertion, but it might
trigger false positives?

nsRange::ParentChainChanged calls IsValidBoundary - is SubtreeRoot()
always valid when ParentChainChanged is called?

I think it would good if you manually check the mochitest full logs
for any "These should always be in sync!" assertions. Perhaps
crashtests too since they may be masked by "asserts(0-999)" and the
like that we have for some tests.

r=mats

Comment 4

[Olli Pettay [:smaug][[e-mail]]]

SubtreeRoot() should return right thing during ParentChainChanged for aContent and its
descendants since UnbindFromTree has been called for those.

Comment 5

[Olli Pettay [:smaug][[e-mail]]]

Attachment: same line

Comment 6

[Olli Pettay [:smaug][[e-mail]]]

Also, note, GetParentNode() during ContentRemoved hasn't been updated either so SubtreeRoot
should return the same value as GetParentNode chain.

Comment 7

[Mats Palmgren (inactive)]

OK, then there's shouldn't be any false positives for ContentRemoved.
Might be worth checking the logs anyway, just in case :-)

Comment 8

[Olli Pettay [:smaug][[e-mail]]]

Yup, will do. Good that I pushed with try: -a so that I get debug builds too :)

Comment 9

[Olli Pettay [:smaug][[e-mail]]]

Couldn't see the assertions in try logs
https://hg.mozilla.org/integration/mozilla-inbound/rev/63635d50157f

Comment 10

[:Ms2ger (he/him; ⌚ UTC+1/+2)]

https://hg.mozilla.org/mozilla-central/rev/63635d50157f