Improve performance of commonInclusiveAncestor for deeply nested nodes
Created attachment 397684 [details]
Comment on attachment 397684 [details]
View in context: https://bugs.webkit.org/attachment.cgi?id=397684&action=review
> + for (std::size_t i = 0; i < difference; ++i)
I should omit the std:: here.
Created attachment 397685 [details]
Created attachment 397686 [details]
Comment on attachment 397686 [details]
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.
> + 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>