73737 2011-12-02 23:32:11 -0800 HIERARCHY_REQUEST_ERR check in checkAcceptChild should be optimized for newChild without children 2011-12-16 23:50:25 -0800 1 1 1 Unclassified WebKit DOM 528+ (Nightly build) Unspecified Unspecified RESOLVED FIXED P2 Normal --- 73802 73853 1 rniwa rniwa arv darin eae ggaren mjs ojan sam webkit.review.bot oldest_to_newest 514445 0 rniwa 2011-12-02 23:32:11 -0800 Per statistics posted in http://lists.whatwg.org/pipermail/whatwg-whatwg.org/2011-December/034038.html, it's pretty clear that the check for HIERARCHY_REQUEST_ERR in checkAcceptChild should be optimized for the case where newChild doesn't have any children or less than 10 children. 514447 1 rniwa 2011-12-02 23:32:37 -0800 Diff I used to collect statistics for completeness: Index: Source/WebCore/dom/Node.cpp =================================================================== --- Source/WebCore/dom/Node.cpp (revision 101848) +++ Source/WebCore/dom/Node.cpp (working copy) @@ -1309,6 +1309,15 @@ // HIERARCHY_REQUEST_ERR: Raised if this node is of a type that does not allow children of the type of the // newChild node, or if the node to append is one of this node's ancestors. + { + unsigned i = 0; + for (Node* node = newChild; node && i < 100; node = node->traverseNextNode(newChild)) + i++; + if (i < 100) + fprintf(stderr, "inserting child with %d nodes\n", i); + else + fprintf(stderr, "inserting child with 100+ nodes\n"); + } if (newChild == newParent || newParent->isDescendantOf(newChild)) { ec = HIERARCHY_REQUEST_ERR; 514460 2 117749 rniwa 2011-12-03 01:15:27 -0800 Created attachment 117749 perf test 514467 3 rniwa 2011-12-03 01:28:59 -0800 I took 11 samples on Apple's mac port applied on r101862. Without patch: shallow tree: 2ms deep tree: 4.09ms (std:0.3) deeper tree: 11.45ms (std:0.5) With patch: shallow tree: 2ms deep tree: 3ms deeper tree: 6.91ms (std 0.3) 40% improvement! The number, however, indicates that we have at least one more linear algorithm hidden somewhere. 514468 4 117751 rniwa 2011-12-03 01:35:21 -0800 Created attachment 117751 Patch 514565 5 arv 2011-12-03 12:28:41 -0800 Thanks for bringing this up. I forgot we talked about this a while ago. I thought of another simple optimization we could do here. If we are comparing two trees that have different inDocument state, then we know that one cannot be a descendant of the other: if (inDocument() != other->inDocument()) return false; I'm curious how many of the cases you saw where a node is appended that has no children falls into the above category? My gut feeling is that the building of the disconnected tree falls into the no child case and that the attachment to the document would fall into the above case. 514584 6 rniwa 2011-12-03 15:09:59 -0800 (In reply to comment #5) > Thanks for bringing this up. I forgot we talked about this a while ago. > > I thought of another simple optimization we could do here. If we are comparing two trees that have different inDocument state, then we know that one cannot be a descendant of the other: > > if (inDocument() != other->inDocument()) > return false; > > I'm curious how many of the cases you saw where a node is appended that has no children falls into the above category? My gut feeling is that the building of the disconnected tree falls into the no child case and that the attachment to the document would fall into the above case. That's an excellent obervation obervstion. I'm going to collect a stat on this as well as the number of ancesors newParent has. 514605 7 darin 2011-12-03 19:27:18 -0800 That code counts the total number of descendants, not the number of children. 514625 8 rniwa 2011-12-03 21:00:34 -0800 (In reply to comment #7) > That code counts the total number of descendants, not the number of children. Oh, right. That's what I meant. New stat coming per Erik's comment. Will wait landing this patch until that. 514645 9 rniwa 2011-12-03 23:19:09 -0800 (In reply to comment #5) > I'm curious how many of the cases you saw where a node is appended that has no children falls into the above category? My gut feeling is that the building of the disconnected tree falls into the no child case and that the attachment to the document would fall into the above case. 59%. Sample size: 42,000 - 1 n = Number of inserted nodes 1 2 7 6 100+ 3 10+ 5 4 20+ 0.679 0.089 0.038 0.029 0.028 0.024 0.021 0.018 0.013 0.011 d = Number of ancestors of new parent 1 20+ 10+ 3 2 4 5 9 8 6 0.544 0.160 0.114 0.077 0.061 0.011 0.010 0.008 0.006 0.006 P(either but not both in document) = 0.625610133575 P(d=1 | n=1) ≈ 0.50007 P(parent not in document | n=1) ≈ 0.585 P(child not in document | n=1) ≈ 0.00681 P(either but not both in document | n=1) ≈ 0.589 P(either but not both in document) ≈ 0.626 P(n = 1, either but not both in document) ≈ 0.400 P(n = 1 | either but not both in document) ≈ 0.639 514647 10 rniwa 2011-12-03 23:55:21 -0800 My data suggests that we should do both optimizations. 514648 11 117784 rniwa 2011-12-04 00:03:54 -0800 Created attachment 117784 Also implement arv's optimization 514650 12 rniwa 2011-12-04 00:48:16 -0800 Resubmitting the patch for review since I've implemented Erik's optimization as well. Most significantly, P(n = 1 or either but not both in document) ≈ 0.904. So this patch will make 90% of cases really fast. 514656 13 117785 rniwa 2011-12-04 01:14:12 -0800 Created attachment 117785 new perf test Given that parent having more than 30 ancestors is very rare, I've updated my perf test to reflect this. 514724 14 arv 2011-12-04 11:12:03 -0800 (In reply to comment #12) > Most significantly, P(n = 1 or either but not both in document) ≈ 0.904. So this patch will make 90% of cases really fast. 90%! Wow that is huge. I expect this to have big impact on Gmail. We should ask them for numbers to see how much this brings down their latency. 514734 15 117784 rniwa 2011-12-04 12:30:04 -0800 Comment on attachment 117784 Also implement arv's optimization Thanks for the reviews, Darin! 514736 16 rniwa 2011-12-04 12:32:20 -0800 (In reply to comment #14) > (In reply to comment #12) > > Most significantly, P(n = 1 or either but not both in document) ≈ 0.904. So this patch will make 90% of cases really fast. > > 90%! Wow that is huge. I expect this to have big impact on Gmail. We should ask them for numbers to see how much this brings down their latency. Hm... we still have a linear performance, and there are so many other APIs that are much slower so I'll be surprised this had any meaningful impact on Gmail but it'll great if this patch improved their latency :) 514755 17 117784 webkit.review.bot 2011-12-04 13:53:13 -0800 Comment on attachment 117784 Also implement arv's optimization Clearing flags on attachment: 117784 Committed r101967: <http://trac.webkit.org/changeset/101967> 514756 18 webkit.review.bot 2011-12-04 13:53:18 -0800 All reviewed patches have been landed. Closing bug. 117749 2011-12-03 01:15:27 -0800 2011-12-04 01:14:12 -0800 perf test insert-node-perf.html text/html 1121 rniwa PCFET0NUWVBFIGh0bWw+CjxodG1sPgo8Ym9keT4KPHVsPgo8bGk+U2hhbGxvdyB0cmVlOiA8c3Bh biBpZD0ic2hhbGxvdyI+PC9zcGFuPiBtczwvbGk+CjxsaT5EZWVwIHRyZWUgKDIwMCspOiA8c3Bh biBpZD0iZGVlcCI+PC9zcGFuPiBtczwvbGk+CjxsaT5EZWVwZXIgdHJlZSAoNTAwKyk6IDxzcGFu IGlkPSJkZWVwZXIiPjwvc3Bhbj4gbXM8L2xpPgo8L3VsPgo8ZGl2IGlkPSJjb250YWluZXIiPjwv ZGl2Pgo8c2NyaXB0PgoKZnVuY3Rpb24gc2V0dXBEZWVwVHJlZShtYWduaXR1ZGUpCnsKICAgIHZh ciBub2RlID0gZG9jdW1lbnQuZ2V0RWxlbWVudEJ5SWQoJ2NvbnRhaW5lcicpOwogICAgbm9kZS5p bm5lckhUTUwgPSAnJzsKICAgIGZvciAodmFyIGkgPSAwOyBpIDwgbWFnbml0dWRlOyBpKyspIHsK ICAgICAgICB2YXIgY2hpbGQgPSBkb2N1bWVudC5jcmVhdGVFbGVtZW50KCdkaXYnKTsKICAgICAg ICBub2RlLmFwcGVuZENoaWxkKGNoaWxkKTsKICAgICAgICBub2RlID0gY2hpbGQ7CiAgICB9CiAg ICByZXR1cm4gbm9kZTsKfQoKZnVuY3Rpb24gdGVzdChjb250YWluZXIpCnsKICAgIHZhciBzdGFy dFRpbWUgPSBEYXRlLm5vdygpOwogICAgdmFyIHNwYW4gPSBudWxsOwogICAgZm9yICh2YXIgaSA9 IDA7IGkgPCAxMDAwOyBpKyspIHsKICAgICAgICBzcGFuID0gZG9jdW1lbnQuY3JlYXRlRWxlbWVu dCgnc3BhbicpOwogICAgICAgIGNvbnRhaW5lci5hcHBlbmRDaGlsZChzcGFuKTsKICAgIH0KICAg IGZvciAodmFyIGkgPSAwOyBpIDwgMTAwMDsgaSsrKQogICAgICAgIGNvbnRhaW5lci5pbnNlcnRC ZWZvcmUoZG9jdW1lbnQuY3JlYXRlRWxlbWVudCgnc3BhbicpLCBzcGFuKTsKICAgIHJldHVybiBE YXRlLm5vdygpIC0gc3RhcnRUaW1lOwp9Cgpkb2N1bWVudC5nZXRFbGVtZW50QnlJZCgnc2hhbGxv dycpLmlubmVySFRNTCA9IHRlc3Qoc2V0dXBEZWVwVHJlZSgwKSk7CmRvY3VtZW50LmdldEVsZW1l bnRCeUlkKCdkZWVwJykuaW5uZXJIVE1MID0gdGVzdChzZXR1cERlZXBUcmVlKDIwMCkpOwpkb2N1 bWVudC5nZXRFbGVtZW50QnlJZCgnZGVlcGVyJykuaW5uZXJIVE1MID0gdGVzdChzZXR1cERlZXBU cmVlKDUwMCkpOwoKPC9zY3JpcHQ+CjwvYm9keT4KPC9odG1sPgo= 117751 2011-12-03 01:35:21 -0800 2011-12-04 00:03:51 -0800 Patch bug-73737-20111203013520.patch text/plain 2004 rniwa SW5kZXg6IFNvdXJjZS9XZWJDb3JlL0NoYW5nZUxvZwo9PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09Ci0tLSBTb3VyY2UvV2Vi Q29yZS9DaGFuZ2VMb2cJKHJldmlzaW9uIDEwMTkxNykKKysrIFNvdXJjZS9XZWJDb3JlL0NoYW5n ZUxvZwkod29ya2luZyBjb3B5KQpAQCAtMSwzICsxLDIwIEBACisyMDExLTEyLTAzICBSeW9zdWtl IE5pd2EgIDxybml3YUB3ZWJraXQub3JnPgorCisgICAgICAgIEhJRVJBUkNIWV9SRVFVRVNUX0VS UiBjaGVjayBpbiBjaGVja0FjY2VwdENoaWxkIHNob3VsZCBiZSBvcHRpbWl6ZWQgZm9yIG5ld0No aWxkIHdpdGhvdXQgY2hpbGRyZW4KKyAgICAgICAgaHR0cHM6Ly9idWdzLndlYmtpdC5vcmcvc2hv d19idWcuY2dpP2lkPTczNzM3CisKKyAgICAgICAgUmV2aWV3ZWQgYnkgTk9CT0RZIChPT1BTISku CisKKyAgICAgICAgSXQgdHVybmVkIG91dCB0aGF0IG1vc3Qgb2Ygbm9kZXMgaW5zZXJ0ZWQgYnkg RE9NIEFQSXMgc3VjaCBhcyBpbnNlcnRCZWZvcmUgYW5kIGFwcGVuZENoaWxkCisgICAgICAgIGRv bid0IGhhdmUgYW55IGNoaWxkcmVuLiBPcHRpbWl6ZSBpc0Rlc2NlbmRhbnRPZiB3aGljaCBpcyB1 c2VkIGJ5IGNoZWNrQWNjZXB0Q2hpbGQgZm9yIHRoaXMgY2FzZS4KKyAgICAgICAgT24gYSB0ZXN0 IGNhc2UgYXR0YWNoZWQgb24gdGhlIGJ1Zywgd2Ugc2VlIGEgNDAlIGltcHJvdmVtZW50LgorCisg ICAgICAgIFVuZm9ydHVuYXRlbHkgbm8gdGVzdHMgYmVjYXVzZSB3ZSBzdGlsbCBoYXZlIGEgTyhu KSBhbGdvcml0aG0gc29tZXdoZXJlLgorCisgICAgICAgICogZG9tL05vZGUuY3BwOgorICAgICAg ICAoV2ViQ29yZTo6Tm9kZTo6aXNEZXNjZW5kYW50T2YpOgorICAgICAgICAoV2ViQ29yZTo6Tm9k ZTo6Y29udGFpbnMpOgorCiAyMDExLTEyLTAzICBEYW4gV2luc2hpcCAgPGRhbndAZ25vbWUub3Jn PgogCiAgICAgICAgIFtHVEtdIFJlbW92ZSBsb3RzIG9mIGNvZGUgdGhhdCBpcyBub3cgdW5uZWNl c3NhcnkgYWZ0ZXIKSW5kZXg6IFNvdXJjZS9XZWJDb3JlL2RvbS9Ob2RlLmNwcAo9PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 Ci0tLSBTb3VyY2UvV2ViQ29yZS9kb20vTm9kZS5jcHAJKHJldmlzaW9uIDEwMTg2MikKKysrIFNv dXJjZS9XZWJDb3JlL2RvbS9Ob2RlLmNwcAkod29ya2luZyBjb3B5KQpAQCAtMTM0OCw4ICsxMzQ4 LDEwIEBAIHZvaWQgTm9kZTo6Y2hlY2tBZGRDaGlsZChOb2RlICpuZXdDaGlsZCwKIGJvb2wgTm9k ZTo6aXNEZXNjZW5kYW50T2YoY29uc3QgTm9kZSAqb3RoZXIpIGNvbnN0CiB7CiAgICAgLy8gUmV0 dXJuIHRydWUgaWYgb3RoZXIgaXMgYW4gYW5jZXN0b3Igb2YgdGhpcywgb3RoZXJ3aXNlIGZhbHNl Ci0gICAgaWYgKCFvdGhlcikKKyAgICBpZiAoIW90aGVyIHx8ICFvdGhlci0+Zmlyc3RDaGlsZCgp KQogICAgICAgICByZXR1cm4gZmFsc2U7CisgICAgaWYgKG90aGVyID09IG90aGVyLT5kb2N1bWVu dCgpKQorICAgICAgICByZXR1cm4gZG9jdW1lbnQoKSA9PSBvdGhlciAmJiB0aGlzICE9IGRvY3Vt ZW50KCkgJiYgaW5Eb2N1bWVudCgpOwogICAgIGZvciAoY29uc3QgQ29udGFpbmVyTm9kZSogbiA9 IHBhcmVudE5vZGUoKTsgbjsgbiA9IG4tPnBhcmVudE5vZGUoKSkgewogICAgICAgICBpZiAobiA9 PSBvdGhlcikKICAgICAgICAgICAgIHJldHVybiB0cnVlOwpAQCAtMTM2MSw4ICsxMzYzLDYgQEAg Ym9vbCBOb2RlOjpjb250YWlucyhjb25zdCBOb2RlKiBub2RlKSBjbwogewogICAgIGlmICghbm9k ZSkKICAgICAgICAgcmV0dXJuIGZhbHNlOwotICAgIGlmIChkb2N1bWVudCgpID09IHRoaXMpCi0g ICAgICAgIHJldHVybiBub2RlLT5kb2N1bWVudCgpID09IHRoaXMgJiYgbm9kZS0+aW5Eb2N1bWVu dCgpOwogICAgIHJldHVybiB0aGlzID09IG5vZGUgfHwgbm9kZS0+aXNEZXNjZW5kYW50T2YodGhp cyk7CiB9CiAK 117784 2011-12-04 00:03:54 -0800 2011-12-04 13:53:13 -0800 Also implement arv's optimization bug-73737-20111204000353.patch text/plain 2364 rniwa SW5kZXg6IFNvdXJjZS9XZWJDb3JlL0NoYW5nZUxvZwo9PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09Ci0tLSBTb3VyY2UvV2Vi Q29yZS9DaGFuZ2VMb2cJKHJldmlzaW9uIDEwMTkxNykKKysrIFNvdXJjZS9XZWJDb3JlL0NoYW5n ZUxvZwkod29ya2luZyBjb3B5KQpAQCAtMSwzICsxLDI0IEBACisyMDExLTEyLTAzICBSeW9zdWtl IE5pd2EgIDxybml3YUB3ZWJraXQub3JnPgorCisgICAgICAgIEhJRVJBUkNIWV9SRVFVRVNUX0VS UiBjaGVjayBpbiBjaGVja0FjY2VwdENoaWxkIHNob3VsZCBiZSBvcHRpbWl6ZWQgZm9yIG5ld0No aWxkIHdpdGhvdXQgY2hpbGRyZW4KKyAgICAgICAgaHR0cHM6Ly9idWdzLndlYmtpdC5vcmcvc2hv d19idWcuY2dpP2lkPTczNzM3CisKKyAgICAgICAgUmV2aWV3ZWQgYnkgTk9CT0RZIChPT1BTISku CisKKyAgICAgICAgSXQgdHVybmVkIG91dCB0aGF0IDUwLTcwJSBvZiBub2RlcyBpbnNlcnRlZCBi eSBET00gQVBJcyBzdWNoIGFzIGluc2VydEJlZm9yZSBhbmQgYXBwZW5kQ2hpbGQKKyAgICAgICAg ZG9uJ3QgaGF2ZSBhbnkgZGVzY2VuZGVudCBub2Rlcy4gT3B0aW1pemUgaXNEZXNjZW5kYW50T2Yg d2hpY2ggaXMgdXNlZCBieSBjaGVja0FjY2VwdENoaWxkIGZvciB0aGlzIGNhc2UuCisgICAgICAg IE9uIGEgdGVzdCBjYXNlIGF0dGFjaGVkIG9uIHRoZSBidWcsIHdlIHNlZSBhIDQwJSBpbXByb3Zl bWVudC4KKworICAgICAgICBBbHNvIG9wdGltaXplIGZvciBjYXNlcyB3aGVyZSBlaXRoZXIgbmV3 IGNoaWxkIG9yIG5ldyBwYXJlbnQgYnV0IG5vdCBib3RoIGFyZSBpbiBkb2N1bWVudCBhcyBzdWdn ZXN0ZWQKKyAgICAgICAgYnkgRXJpayBBcnZpZHNzb24uIFRoaXMgYXBwZWFycyB0byBoYXBwZW4g YWJvdXQgNDAtNzAlIG9mIHRoZSB0aW1lLCBhbmQgdGhlIHN5bW1ldHJpYyBkaWZmZXJlbmNlIGJl dHdlZW4KKyAgICAgICAgdGhlIHR3byBjYXNlcyBpcyBhYm91dCA1MCUgc28gaXQncyB3b3J0aCBp bXBsZW1lbnRpbmcgYm90aCBvcHRpbWl6YXRpb25zLgorCisgICAgICAgIFVuZm9ydHVuYXRlbHkg bm8gdGVzdHMgYmVjYXVzZSB3ZSBzdGlsbCBoYXZlIGEgTyhuKSBhbGdvcml0aG0gc29tZXdoZXJl LgorCisgICAgICAgICogZG9tL05vZGUuY3BwOgorICAgICAgICAoV2ViQ29yZTo6Tm9kZTo6aXNE ZXNjZW5kYW50T2YpOgorICAgICAgICAoV2ViQ29yZTo6Tm9kZTo6Y29udGFpbnMpOgorCiAyMDEx LTEyLTAzICBEYW4gV2luc2hpcCAgPGRhbndAZ25vbWUub3JnPgogCiAgICAgICAgIFtHVEtdIFJl bW92ZSBsb3RzIG9mIGNvZGUgdGhhdCBpcyBub3cgdW5uZWNlc3NhcnkgYWZ0ZXIKSW5kZXg6IFNv dXJjZS9XZWJDb3JlL2RvbS9Ob2RlLmNwcAo9PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09Ci0tLSBTb3VyY2UvV2ViQ29yZS9k b20vTm9kZS5jcHAJKHJldmlzaW9uIDEwMTg2MikKKysrIFNvdXJjZS9XZWJDb3JlL2RvbS9Ob2Rl LmNwcAkod29ya2luZyBjb3B5KQpAQCAtMTM0OCw4ICsxMzQ4LDEwIEBAIHZvaWQgTm9kZTo6Y2hl Y2tBZGRDaGlsZChOb2RlICpuZXdDaGlsZCwKIGJvb2wgTm9kZTo6aXNEZXNjZW5kYW50T2YoY29u c3QgTm9kZSAqb3RoZXIpIGNvbnN0CiB7CiAgICAgLy8gUmV0dXJuIHRydWUgaWYgb3RoZXIgaXMg YW4gYW5jZXN0b3Igb2YgdGhpcywgb3RoZXJ3aXNlIGZhbHNlCi0gICAgaWYgKCFvdGhlcikKKyAg ICBpZiAoIW90aGVyIHx8ICFvdGhlci0+Zmlyc3RDaGlsZCgpIHx8IGluRG9jdW1lbnQoKSAhPSBv dGhlci0+aW5Eb2N1bWVudCgpKQogICAgICAgICByZXR1cm4gZmFsc2U7CisgICAgaWYgKG90aGVy ID09IG90aGVyLT5kb2N1bWVudCgpKQorICAgICAgICByZXR1cm4gZG9jdW1lbnQoKSA9PSBvdGhl ciAmJiB0aGlzICE9IGRvY3VtZW50KCkgJiYgaW5Eb2N1bWVudCgpOwogICAgIGZvciAoY29uc3Qg Q29udGFpbmVyTm9kZSogbiA9IHBhcmVudE5vZGUoKTsgbjsgbiA9IG4tPnBhcmVudE5vZGUoKSkg ewogICAgICAgICBpZiAobiA9PSBvdGhlcikKICAgICAgICAgICAgIHJldHVybiB0cnVlOwpAQCAt MTM2MSw4ICsxMzYzLDYgQEAgYm9vbCBOb2RlOjpjb250YWlucyhjb25zdCBOb2RlKiBub2RlKSBj bwogewogICAgIGlmICghbm9kZSkKICAgICAgICAgcmV0dXJuIGZhbHNlOwotICAgIGlmIChkb2N1 bWVudCgpID09IHRoaXMpCi0gICAgICAgIHJldHVybiBub2RlLT5kb2N1bWVudCgpID09IHRoaXMg JiYgbm9kZS0+aW5Eb2N1bWVudCgpOwogICAgIHJldHVybiB0aGlzID09IG5vZGUgfHwgbm9kZS0+ aXNEZXNjZW5kYW50T2YodGhpcyk7CiB9CiAK 117785 2011-12-04 01:14:12 -0800 2011-12-04 01:14:12 -0800 new perf test insert-node-perf.html text/html 1239 rniwa PCFET0NUWVBFIGh0bWw+CjxodG1sPgo8Ym9keT4KPHVsPgo8bGk+U2hhbGxvdyB0cmVlOiA8c3Bh biBpZD0ic2hhbGxvdyI+PC9zcGFuPiBtczwvbGk+CjxsaT5EZWVwIHRyZWUgKDIwKyk6IDxzcGFu IGlkPSJkZWVwIj48L3NwYW4+IG1zPC9saT4KPGxpPkRlZXBlciB0cmVlICg1MCspOiA8c3BhbiBp ZD0iZGVlcGVyIj48L3NwYW4+IG1zPC9saT4KPC91bD4KPGRpdiBpZD0iY29udGFpbmVyIj48L2Rp dj4KPHNjcmlwdD4KCmZ1bmN0aW9uIHNldHVwRGVlcFRyZWUobWFnbml0dWRlKQp7CiAgICB2YXIg bm9kZSA9IGRvY3VtZW50LmdldEVsZW1lbnRCeUlkKCdjb250YWluZXInKTsKICAgIG5vZGUuaW5u ZXJIVE1MID0gJyc7CiAgICBmb3IgKHZhciBpID0gMDsgaSA8IG1hZ25pdHVkZTsgaSsrKSB7CiAg ICAgICAgdmFyIGNoaWxkID0gZG9jdW1lbnQuY3JlYXRlRWxlbWVudCgnZGl2Jyk7CiAgICAgICAg bm9kZS5hcHBlbmRDaGlsZChjaGlsZCk7CiAgICAgICAgbm9kZSA9IGNoaWxkOwogICAgfQogICAg cmV0dXJuIG5vZGU7Cn0KCmZ1bmN0aW9uIHRlc3QoY29udGFpbmVyKQp7CiAgICB2YXIgc3RhcnRU aW1lID0gRGF0ZS5ub3coKTsKICAgIHZhciBzcGFuID0gbnVsbDsKICAgIGZvciAodmFyIGkgPSAw OyBpIDwgNTAwMDsgaSsrKSB7CiAgICAgICAgc3BhbiA9IGRvY3VtZW50LmNyZWF0ZUVsZW1lbnQo J3NwYW4nKTsKICAgICAgICBjb250YWluZXIuYXBwZW5kQ2hpbGQoc3Bhbik7CiAgICB9CiAgICBm b3IgKHZhciBpID0gMDsgaSA8IDUwMDA7IGkrKykKICAgICAgICBjb250YWluZXIuaW5zZXJ0QmVm b3JlKGRvY3VtZW50LmNyZWF0ZUVsZW1lbnQoJ3NwYW4nKSwgc3Bhbik7CiAgICByZXR1cm4gRGF0 ZS5ub3coKSAtIHN0YXJ0VGltZTsKfQoKZnVuY3Rpb24gcmVwZWF0VGVzdChtYWduaXR1ZGUpIHsK ICAgIHZhciBzdW0gPSAwOwogICAgZm9yICh2YXIgaSA9IDA7IGkgPCAxMDsgaSsrKQogICAgICAg IHN1bSArPSB0ZXN0KHNldHVwRGVlcFRyZWUobWFnbml0dWRlKSk7CiAgICByZXR1cm4gc3VtOwp9 Cgpkb2N1bWVudC5nZXRFbGVtZW50QnlJZCgnc2hhbGxvdycpLmlubmVySFRNTCA9IHJlcGVhdFRl c3QoMCk7CmRvY3VtZW50LmdldEVsZW1lbnRCeUlkKCdkZWVwJykuaW5uZXJIVE1MID0gcmVwZWF0 VGVzdCgyMCk7CmRvY3VtZW50LmdldEVsZW1lbnRCeUlkKCdkZWVwZXInKS5pbm5lckhUTUwgPSBy ZXBlYXRUZXN0KDUwKTsKCjwvc2NyaXB0Pgo8L2JvZHk+CjwvaHRtbD4K