211078 2020-04-27 08:22:32 -0700 Improve performance of commonInclusiveAncestor for deeply nested nodes 2020-04-27 09:48:15 -0700 1 1 1 Unclassified WebKit DOM WebKit Nightly Build All All RESOLVED FIXED InRadar P2 Normal --- 1 darin darin cdumez esprehn+autocc ews-watchlist kangil.han koivisto webkit-bug-importer oldest_to_newest 1646009 0 darin 2020-04-27 08:22:32 -0700 Improve performance of commonInclusiveAncestor for deeply nested nodes 1646010 1 397684 darin 2020-04-27 08:24:13 -0700 Created attachment 397684 Patch 1646012 2 397684 darin 2020-04-27 08:26:08 -0700 Comment on attachment 397684 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. 1646014 3 397685 darin 2020-04-27 08:28:23 -0700 Created attachment 397685 Patch 1646016 4 397686 darin 2020-04-27 08:39:19 -0700 Created attachment 397686 Patch 1646027 5 397686 koivisto 2020-04-27 09:06:16 -0700 Comment on attachment 397686 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. 1646029 6 koivisto 2020-04-27 09:08:24 -0700 If a==b is common it might be worth optimizing for it. 1646041 7 darin 2020-04-27 09:18:31 -0700 (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? 1646047 8 koivisto 2020-04-27 09:31:14 -0700 Yeah, it is such a cheap test. 1646055 9 darin 2020-04-27 09:45:39 -0700 Tempting to also add a special case for when a and b both have the same parent. But for now I will not. 1646058 10 darin 2020-04-27 09:47:28 -0700 Committed r260762: <https://trac.webkit.org/changeset/260762> 1646060 11 webkit-bug-importer 2020-04-27 09:48:15 -0700 <rdar://problem/62456207> 397684 2020-04-27 08:24:13 -0700 2020-04-27 08:28:21 -0700 Patch bug-211078-20200427082412.patch text/plain 2196 darin U3VidmVyc2lvbiBSZXZpc2lvbjogMjYwNzUzCmRpZmYgLS1naXQgYS9Tb3VyY2UvV2ViQ29yZS9D aGFuZ2VMb2cgYi9Tb3VyY2UvV2ViQ29yZS9DaGFuZ2VMb2cKaW5kZXggNzU3NDM1NjQ2YzRjMzYz MzY3YjMwOTE1MTI5YWI1YmVjNzdmMjU5Yi4uODdlZWExMGMzMTJkMjQ0ZjA5YmUxNTU5MzhmMWFj NDI4OGNiNTY3NyAxMDA2NDQKLS0tIGEvU291cmNlL1dlYkNvcmUvQ2hhbmdlTG9nCisrKyBiL1Nv dXJjZS9XZWJDb3JlL0NoYW5nZUxvZwpAQCAtMSwzICsxLDE2IEBACisyMDIwLTA0LTI3ICBEYXJp biBBZGxlciAgPGRhcmluQGFwcGxlLmNvbT4KKworICAgICAgICBJbXByb3ZlIHBlcmZvcm1hbmNl IG9mIGNvbW1vbkluY2x1c2l2ZUFuY2VzdG9yIGZvciBkZWVwbHkgbmVzdGVkIG5vZGVzCisgICAg ICAgIGh0dHBzOi8vYnVncy53ZWJraXQub3JnL3Nob3dfYnVnLmNnaT9pZD0yMTEwNzgKKworICAg ICAgICBSZXZpZXdlZCBieSBOT0JPRFkgKE9PUFMhKS4KKworICAgICAgICAqIGRvbS9Ob2RlLmNw cDoKKyAgICAgICAgKFdlYkNvcmU6OmRlcHRoKTogQWRkZWQuCisgICAgICAgIChXZWJDb3JlOjpj b21tb25JbmNsdXNpdmVBbmNlc3Rvcik6IFJlcGxhY2VkIGltcGxlbWVudGF0aW9uIHRoYXQgd2Fs a3MgdGhlCisgICAgICAgIHBhcmVudCBjaGFpbiBvZiB0aGUgc2Vjb25kIG5vZGUgcmVwZWF0ZWRs eSB3aXRoIG9uZSB0aGF0IHdhbGtzIHRoZSBwYXJlbnQKKyAgICAgICAgY2hhaW4gb2YgZWFjaCBu b2RlIHR3aWNlLgorCiAyMDIwLTA0LTI2ICBEYXJpbiBBZGxlciAgPGRhcmluQGFwcGxlLmNvbT4K IAogICAgICAgICBSZXBsYWNlIG1vcmUgdXNlcyBvZiBsaXZlIHJhbmdlcyB3aXRoIFNpbXBsZVJh bmdlCmRpZmYgLS1naXQgYS9Tb3VyY2UvV2ViQ29yZS9kb20vTm9kZS5jcHAgYi9Tb3VyY2UvV2Vi Q29yZS9kb20vTm9kZS5jcHAKaW5kZXggNzhmN2Y1NWJlZjVkMzkxNWI3NzIwNmE5YjEyYWQwMjU1 YjQxNzMzNC4uNDExNzQ4YzgxZWMwMmQ3ZGYwNzM4OTliMjg2YTAxMzJmMDg0NmFhNyAxMDA2NDQK LS0tIGEvU291cmNlL1dlYkNvcmUvZG9tL05vZGUuY3BwCisrKyBiL1NvdXJjZS9XZWJDb3JlL2Rv bS9Ob2RlLmNwcApAQCAtMjYxMiwxNSArMjYxMiwyOSBAQCB2b2lkKiBOb2RlOjpvcGFxdWVSb290 U2xvdygpIGNvbnN0CiAgICAgcmV0dXJuIGNvbnN0X2Nhc3Q8dm9pZCo+KHN0YXRpY19jYXN0PGNv bnN0IHZvaWQqPihub2RlKSk7CiB9CiAKK3N0YXRpYyBzaXplX3QgZGVwdGgoTm9kZSYgbm9kZSkK K3sKKyAgICBzaXplX3QgZGVwdGggPSAwOworICAgIGF1dG8gYW5jZXN0b3IgPSAmbm9kZTsKKyAg ICB3aGlsZSAoKGFuY2VzdG9yID0gYW5jZXN0b3ItPnBhcmVudE5vZGUoKSkpCisgICAgICAgICsr ZGVwdGg7CisgICAgcmV0dXJuIGRlcHRoOworfQorCiBSZWZQdHI8Tm9kZT4gY29tbW9uSW5jbHVz aXZlQW5jZXN0b3IoTm9kZSYgYSwgTm9kZSYgYikKIHsKLSAgICBmb3IgKGF1dG8gYW5jZXN0b3JB ID0gJmE7IGFuY2VzdG9yQTsgYW5jZXN0b3JBID0gYW5jZXN0b3JBLT5wYXJlbnROb2RlKCkpIHsK LSAgICAgICAgZm9yIChhdXRvIGFuY2VzdG9yQiA9ICZiOyBhbmNlc3RvckI7IGFuY2VzdG9yQiA9 IGFuY2VzdG9yQi0+cGFyZW50Tm9kZSgpKSB7Ci0gICAgICAgICAgICBpZiAoYW5jZXN0b3JBID09 IGFuY2VzdG9yQikKLSAgICAgICAgICAgICAgICByZXR1cm4gYW5jZXN0b3JBOwotICAgICAgICB9 Ci0gICAgfQotICAgIHJldHVybiBudWxscHRyOworICAgIGF1dG8gZGVwdGhBID0gZGVwdGgoYSk7 CisgICAgYXV0byBkZXB0aEIgPSBkZXB0aChiKTsKKyAgICBhdXRvIFt4LCB5LCBkaWZmZXJlbmNl XSA9IGRlcHRoQSA+IGRlcHRoQgorICAgICAgICA/IHN0ZDo6bWFrZV90dXBsZSgmYSwgJmIsIGRl cHRoQSAtIGRlcHRoQikKKyAgICAgICAgOiBzdGQ6Om1ha2VfdHVwbGUoJmIsICZhLCBkZXB0aEIg LSBkZXB0aEEpOworICAgIGZvciAoc3RkOjpzaXplX3QgaSA9IDA7IGkgPCBkaWZmZXJlbmNlOyAr K2kpCisgICAgICAgIHggPSB4LT5wYXJlbnROb2RlKCk7CisgICAgd2hpbGUgKHggIT0geSkgewor ICAgICAgICB4ID0geC0+cGFyZW50Tm9kZSgpOworICAgICAgICB5ID0geS0+cGFyZW50Tm9kZSgp OworICAgIH0KKyAgICByZXR1cm4geDsKIH0KIAogVGV4dFN0cmVhbSYgb3BlcmF0b3I8PChUZXh0 U3RyZWFtJiB0cywgY29uc3QgTm9kZSYgbm9kZSkK 397685 2020-04-27 08:28:23 -0700 2020-04-27 08:39:18 -0700 Patch bug-211078-20200427082822.patch text/plain 2205 darin U3VidmVyc2lvbiBSZXZpc2lvbjogMjYwNzUzCmRpZmYgLS1naXQgYS9Tb3VyY2UvV2ViQ29yZS9D aGFuZ2VMb2cgYi9Tb3VyY2UvV2ViQ29yZS9DaGFuZ2VMb2cKaW5kZXggNzU3NDM1NjQ2YzRjMzYz MzY3YjMwOTE1MTI5YWI1YmVjNzdmMjU5Yi4uODdlZWExMGMzMTJkMjQ0ZjA5YmUxNTU5MzhmMWFj NDI4OGNiNTY3NyAxMDA2NDQKLS0tIGEvU291cmNlL1dlYkNvcmUvQ2hhbmdlTG9nCisrKyBiL1Nv dXJjZS9XZWJDb3JlL0NoYW5nZUxvZwpAQCAtMSwzICsxLDE2IEBACisyMDIwLTA0LTI3ICBEYXJp biBBZGxlciAgPGRhcmluQGFwcGxlLmNvbT4KKworICAgICAgICBJbXByb3ZlIHBlcmZvcm1hbmNl IG9mIGNvbW1vbkluY2x1c2l2ZUFuY2VzdG9yIGZvciBkZWVwbHkgbmVzdGVkIG5vZGVzCisgICAg ICAgIGh0dHBzOi8vYnVncy53ZWJraXQub3JnL3Nob3dfYnVnLmNnaT9pZD0yMTEwNzgKKworICAg ICAgICBSZXZpZXdlZCBieSBOT0JPRFkgKE9PUFMhKS4KKworICAgICAgICAqIGRvbS9Ob2RlLmNw cDoKKyAgICAgICAgKFdlYkNvcmU6OmRlcHRoKTogQWRkZWQuCisgICAgICAgIChXZWJDb3JlOjpj b21tb25JbmNsdXNpdmVBbmNlc3Rvcik6IFJlcGxhY2VkIGltcGxlbWVudGF0aW9uIHRoYXQgd2Fs a3MgdGhlCisgICAgICAgIHBhcmVudCBjaGFpbiBvZiB0aGUgc2Vjb25kIG5vZGUgcmVwZWF0ZWRs eSB3aXRoIG9uZSB0aGF0IHdhbGtzIHRoZSBwYXJlbnQKKyAgICAgICAgY2hhaW4gb2YgZWFjaCBu b2RlIHR3aWNlLgorCiAyMDIwLTA0LTI2ICBEYXJpbiBBZGxlciAgPGRhcmluQGFwcGxlLmNvbT4K IAogICAgICAgICBSZXBsYWNlIG1vcmUgdXNlcyBvZiBsaXZlIHJhbmdlcyB3aXRoIFNpbXBsZVJh bmdlCmRpZmYgLS1naXQgYS9Tb3VyY2UvV2ViQ29yZS9kb20vTm9kZS5jcHAgYi9Tb3VyY2UvV2Vi Q29yZS9kb20vTm9kZS5jcHAKaW5kZXggNzhmN2Y1NWJlZjVkMzkxNWI3NzIwNmE5YjEyYWQwMjU1 YjQxNzMzNC4uZDE2NmFmOWNlZWE5YjRkMzc5ZGI3YmM5MGI5ZTZmYzliOWYyODY4OSAxMDA2NDQK LS0tIGEvU291cmNlL1dlYkNvcmUvZG9tL05vZGUuY3BwCisrKyBiL1NvdXJjZS9XZWJDb3JlL2Rv bS9Ob2RlLmNwcApAQCAtMjYxMiwxNSArMjYxMiwyOSBAQCB2b2lkKiBOb2RlOjpvcGFxdWVSb290 U2xvdygpIGNvbnN0CiAgICAgcmV0dXJuIGNvbnN0X2Nhc3Q8dm9pZCo+KHN0YXRpY19jYXN0PGNv bnN0IHZvaWQqPihub2RlKSk7CiB9CiAKK3N0YXRpYyBzaXplX3QgZGVwdGgoTm9kZSYgbm9kZSkK K3sKKyAgICBzaXplX3QgZGVwdGggPSAwOworICAgIGF1dG8gYW5jZXN0b3IgPSAmbm9kZTsKKyAg ICB3aGlsZSAoKGFuY2VzdG9yID0gYW5jZXN0b3ItPnBhcmVudE5vZGUoKSkpCisgICAgICAgICsr ZGVwdGg7CisgICAgcmV0dXJuIGRlcHRoOworfQorCiBSZWZQdHI8Tm9kZT4gY29tbW9uSW5jbHVz aXZlQW5jZXN0b3IoTm9kZSYgYSwgTm9kZSYgYikKIHsKLSAgICBmb3IgKGF1dG8gYW5jZXN0b3JB ID0gJmE7IGFuY2VzdG9yQTsgYW5jZXN0b3JBID0gYW5jZXN0b3JBLT5wYXJlbnROb2RlKCkpIHsK LSAgICAgICAgZm9yIChhdXRvIGFuY2VzdG9yQiA9ICZiOyBhbmNlc3RvckI7IGFuY2VzdG9yQiA9 IGFuY2VzdG9yQi0+cGFyZW50Tm9kZSgpKSB7Ci0gICAgICAgICAgICBpZiAoYW5jZXN0b3JBID09 IGFuY2VzdG9yQikKLSAgICAgICAgICAgICAgICByZXR1cm4gYW5jZXN0b3JBOwotICAgICAgICB9 Ci0gICAgfQotICAgIHJldHVybiBudWxscHRyOworICAgIGF1dG8gZGVwdGhBID0gZGVwdGgoYSk7 CisgICAgYXV0byBkZXB0aEIgPSBkZXB0aChiKTsKKyAgICBhdXRvIFt4LCB5LCBkaWZmZXJlbmNl XSA9IGRlcHRoQSA+IGRlcHRoQgorICAgICAgICA/IHN0ZDo6bWFrZV90dXBsZSgmYSwgJmIsIGRl cHRoQSAtIGRlcHRoQikKKyAgICAgICAgOiBzdGQ6Om1ha2VfdHVwbGUoJmIsICZhLCBkZXB0aEIg LSBkZXB0aEEpOworICAgIGZvciAoZGVjbHR5cGUoZGlmZmVyZW5jZSkgaSA9IDA7IGkgPCBkaWZm ZXJlbmNlOyArK2kpCisgICAgICAgIHggPSB4LT5wYXJlbnROb2RlKCk7CisgICAgd2hpbGUgKHgg IT0geSkgeworICAgICAgICB4ID0geC0+cGFyZW50Tm9kZSgpOworICAgICAgICB5ID0geS0+cGFy ZW50Tm9kZSgpOworICAgIH0KKyAgICByZXR1cm4geDsKIH0KIAogVGV4dFN0cmVhbSYgb3BlcmF0 b3I8PChUZXh0U3RyZWFtJiB0cywgY29uc3QgTm9kZSYgbm9kZSkK 397686 2020-04-27 08:39:19 -0700 2020-04-27 09:06:16 -0700 Patch bug-211078-20200427083918.patch text/plain 2213 darin U3VidmVyc2lvbiBSZXZpc2lvbjogMjYwNzUzCmRpZmYgLS1naXQgYS9Tb3VyY2UvV2ViQ29yZS9D aGFuZ2VMb2cgYi9Tb3VyY2UvV2ViQ29yZS9DaGFuZ2VMb2cKaW5kZXggNzU3NDM1NjQ2YzRjMzYz MzY3YjMwOTE1MTI5YWI1YmVjNzdmMjU5Yi4uODdlZWExMGMzMTJkMjQ0ZjA5YmUxNTU5MzhmMWFj NDI4OGNiNTY3NyAxMDA2NDQKLS0tIGEvU291cmNlL1dlYkNvcmUvQ2hhbmdlTG9nCisrKyBiL1Nv dXJjZS9XZWJDb3JlL0NoYW5nZUxvZwpAQCAtMSwzICsxLDE2IEBACisyMDIwLTA0LTI3ICBEYXJp biBBZGxlciAgPGRhcmluQGFwcGxlLmNvbT4KKworICAgICAgICBJbXByb3ZlIHBlcmZvcm1hbmNl IG9mIGNvbW1vbkluY2x1c2l2ZUFuY2VzdG9yIGZvciBkZWVwbHkgbmVzdGVkIG5vZGVzCisgICAg ICAgIGh0dHBzOi8vYnVncy53ZWJraXQub3JnL3Nob3dfYnVnLmNnaT9pZD0yMTEwNzgKKworICAg ICAgICBSZXZpZXdlZCBieSBOT0JPRFkgKE9PUFMhKS4KKworICAgICAgICAqIGRvbS9Ob2RlLmNw cDoKKyAgICAgICAgKFdlYkNvcmU6OmRlcHRoKTogQWRkZWQuCisgICAgICAgIChXZWJDb3JlOjpj b21tb25JbmNsdXNpdmVBbmNlc3Rvcik6IFJlcGxhY2VkIGltcGxlbWVudGF0aW9uIHRoYXQgd2Fs a3MgdGhlCisgICAgICAgIHBhcmVudCBjaGFpbiBvZiB0aGUgc2Vjb25kIG5vZGUgcmVwZWF0ZWRs eSB3aXRoIG9uZSB0aGF0IHdhbGtzIHRoZSBwYXJlbnQKKyAgICAgICAgY2hhaW4gb2YgZWFjaCBu b2RlIHR3aWNlLgorCiAyMDIwLTA0LTI2ICBEYXJpbiBBZGxlciAgPGRhcmluQGFwcGxlLmNvbT4K IAogICAgICAgICBSZXBsYWNlIG1vcmUgdXNlcyBvZiBsaXZlIHJhbmdlcyB3aXRoIFNpbXBsZVJh bmdlCmRpZmYgLS1naXQgYS9Tb3VyY2UvV2ViQ29yZS9kb20vTm9kZS5jcHAgYi9Tb3VyY2UvV2Vi Q29yZS9kb20vTm9kZS5jcHAKaW5kZXggNzhmN2Y1NWJlZjVkMzkxNWI3NzIwNmE5YjEyYWQwMjU1 YjQxNzMzNC4uYzFiYmYwNjZkZmQ0YzE1NGFkMTI3MWRiMmE0OGE2YzA5MDIyMjcyNiAxMDA2NDQK LS0tIGEvU291cmNlL1dlYkNvcmUvZG9tL05vZGUuY3BwCisrKyBiL1NvdXJjZS9XZWJDb3JlL2Rv bS9Ob2RlLmNwcApAQCAtMjYxMiwxNSArMjYxMiwyOCBAQCB2b2lkKiBOb2RlOjpvcGFxdWVSb290 U2xvdygpIGNvbnN0CiAgICAgcmV0dXJuIGNvbnN0X2Nhc3Q8dm9pZCo+KHN0YXRpY19jYXN0PGNv bnN0IHZvaWQqPihub2RlKSk7CiB9CiAKK3N0YXRpYyBzaXplX3QgZGVwdGgoTm9kZSYgbm9kZSkK K3sKKyAgICBzaXplX3QgZGVwdGggPSAwOworICAgIGF1dG8gYW5jZXN0b3IgPSAmbm9kZTsKKyAg ICB3aGlsZSAoKGFuY2VzdG9yID0gYW5jZXN0b3ItPnBhcmVudE5vZGUoKSkpCisgICAgICAgICsr ZGVwdGg7CisgICAgcmV0dXJuIGRlcHRoOworfQorCiBSZWZQdHI8Tm9kZT4gY29tbW9uSW5jbHVz aXZlQW5jZXN0b3IoTm9kZSYgYSwgTm9kZSYgYikKIHsKLSAgICBmb3IgKGF1dG8gYW5jZXN0b3JB ID0gJmE7IGFuY2VzdG9yQTsgYW5jZXN0b3JBID0gYW5jZXN0b3JBLT5wYXJlbnROb2RlKCkpIHsK LSAgICAgICAgZm9yIChhdXRvIGFuY2VzdG9yQiA9ICZiOyBhbmNlc3RvckI7IGFuY2VzdG9yQiA9 IGFuY2VzdG9yQi0+cGFyZW50Tm9kZSgpKSB7Ci0gICAgICAgICAgICBpZiAoYW5jZXN0b3JBID09 IGFuY2VzdG9yQikKLSAgICAgICAgICAgICAgICByZXR1cm4gYW5jZXN0b3JBOwotICAgICAgICB9 Ci0gICAgfQotICAgIHJldHVybiBudWxscHRyOworICAgIGF1dG8gW2RlcHRoQSwgZGVwdGhCXSA9 IHN0ZDo6bWFrZV90dXBsZShkZXB0aChhKSwgZGVwdGgoYikpOworICAgIGF1dG8gW3gsIHksIGRp ZmZlcmVuY2VdID0gZGVwdGhBID4gZGVwdGhCCisgICAgICAgID8gc3RkOjptYWtlX3R1cGxlKCZh LCAmYiwgZGVwdGhBIC0gZGVwdGhCKQorICAgICAgICA6IHN0ZDo6bWFrZV90dXBsZSgmYiwgJmEs IGRlcHRoQiAtIGRlcHRoQSk7CisgICAgZm9yIChkZWNsdHlwZShkaWZmZXJlbmNlKSBpID0gMDsg aSA8IGRpZmZlcmVuY2U7ICsraSkKKyAgICAgICAgeCA9IHgtPnBhcmVudE5vZGUoKTsKKyAgICB3 aGlsZSAoeCAhPSB5KSB7CisgICAgICAgIHggPSB4LT5wYXJlbnROb2RlKCk7CisgICAgICAgIHkg PSB5LT5wYXJlbnROb2RlKCk7CisgICAgfQorICAgIHJldHVybiB4OwogfQogCiBUZXh0U3RyZWFt JiBvcGVyYXRvcjw8KFRleHRTdHJlYW0mIHRzLCBjb25zdCBOb2RlJiBub2RlKQo=