Bug 211078 - Improve performance of commonInclusiveAncestor for deeply nested nodes
Summary: Improve performance of commonInclusiveAncestor for deeply nested nodes
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: DOM (show other bugs)
Version: WebKit Nightly Build
Hardware: All All
: P2 Normal
Assignee: Darin Adler
URL:
Keywords: InRadar
Depends on:
Blocks:
 
Reported: 2020-04-27 08:22 PDT by Darin Adler
Modified: 2020-04-27 09:48 PDT (History)
6 users (show)

See Also:


Attachments
Patch (2.14 KB, patch)
2020-04-27 08:24 PDT, Darin Adler
no flags Details | Formatted Diff | Diff
Patch (2.15 KB, patch)
2020-04-27 08:28 PDT, Darin Adler
no flags Details | Formatted Diff | Diff
Patch (2.16 KB, patch)
2020-04-27 08:39 PDT, Darin Adler
koivisto: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Darin Adler 2020-04-27 08:22:32 PDT
Improve performance of commonInclusiveAncestor for deeply nested nodes
Comment 1 Darin Adler 2020-04-27 08:24:13 PDT Comment hidden (obsolete)
Comment 2 Darin Adler 2020-04-27 08:26:08 PDT Comment hidden (obsolete)
Comment 3 Darin Adler 2020-04-27 08:28:23 PDT Comment hidden (obsolete)
Comment 4 Darin Adler 2020-04-27 08:39:19 PDT
Created attachment 397686 [details]
Patch
Comment 5 Antti Koivisto 2020-04-27 09:06:16 PDT
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.
Comment 6 Antti Koivisto 2020-04-27 09:08:24 PDT
If a==b is common it might be worth optimizing for it.
Comment 7 Darin Adler 2020-04-27 09:18:31 PDT
(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?
Comment 8 Antti Koivisto 2020-04-27 09:31:14 PDT
Yeah, it is such a cheap test.
Comment 9 Darin Adler 2020-04-27 09:45:39 PDT
Tempting to also add a special case for when a and b both have the same parent. But for now I will not.
Comment 10 Darin Adler 2020-04-27 09:47:28 PDT
Committed r260762: <https://trac.webkit.org/changeset/260762>
Comment 11 Radar WebKit Bug Importer 2020-04-27 09:48:15 PDT
<rdar://problem/62456207>