Summary: | Improve performance of commonInclusiveAncestor for deeply nested nodes | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Product: | WebKit | Reporter: | Darin Adler <darin> | ||||||||
Component: | DOM | Assignee: | Darin Adler <darin> | ||||||||
Status: | RESOLVED FIXED | ||||||||||
Severity: | Normal | CC: | cdumez, esprehn+autocc, ews-watchlist, kangil.han, koivisto, webkit-bug-importer | ||||||||
Priority: | P2 | Keywords: | InRadar | ||||||||
Version: | WebKit Nightly Build | ||||||||||
Hardware: | All | ||||||||||
OS: | All | ||||||||||
Attachments: |
|
Description
Darin Adler
2020-04-27 08:22:32 PDT
Created attachment 397684 [details]
Patch
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. Created attachment 397685 [details]
Patch
Created attachment 397686 [details]
Patch
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. If a==b is common it might be worth optimizing for it. (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? Yeah, it is such a cheap test. Tempting to also add a special case for when a and b both have the same parent. But for now I will not. Committed r260762: <https://trac.webkit.org/changeset/260762> |