Bug 211078 – Improve performance of commonInclusiveAncestor for deeply nested nodes

• Component: DOM
• Status: RESOLVED FIXED

[Darin Adler]

Improve performance of commonInclusiveAncestor for deeply nested nodes

[Darin Adler]

Created attachment 397684 [details]
Patch

[Darin Adler]

Comment on attachment 397684 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=397684&action=review

> Source/WebCore/dom/Node.cpp:2631
> +    for (std::size_t i = 0; i < difference; ++i)

I should omit the std:: here.

[Darin Adler]

Created attachment 397685 [details]
Patch

[Darin Adler]

Created attachment 397686 [details]
Patch

[Antti Koivisto]

Comment on attachment 397686 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=397686&action=review

findNearestCommonComposedAncestor has another implementation using a HashSet. Yours is probably better since it avoids allocation and hashing even if it requires more traversal.

> Source/WebCore/dom/Node.cpp:2627
> +    auto [depthA, depthB] = std::make_tuple(depth(a), depth(b));
> +    auto [x, y, difference] = depthA > depthB

Interesting use of temporary tuples.

[Antti Koivisto]

If a==b is common it might be worth optimizing for it.

[Darin Adler]

(In reply to Antti Koivisto from comment #6)
> If a==b is common it might be worth optimizing for it.

Maybe I should speculatively include that without even measuring?

[Antti Koivisto]

Yeah, it is such a cheap test.

[Darin Adler]

Tempting to also add a special case for when a and b both have the same parent. But for now I will not.

[Darin Adler]

Committed r260762: <https://trac.webkit.org/changeset/260762>

[Radar WebKit Bug Importer]

<rdar://problem/62456207>