103017 2012-11-21 21:44:12 -0800 [Shadow] Attaching children of a shadow host takes O(N^2) where N is the number of host children 2012-11-26 01:08:10 -0800 1 1 1 Unclassified WebKit DOM 528+ (Nightly build) Unspecified Unspecified RESOLVED FIXED P2 Normal --- 103016 1 shinyak shinyak dglazkov ojan webcomponents-bugzilla webkit.review.bot oldest_to_newest 773551 0 shinyak 2012-11-21 21:44:12 -0800 We would like make this O(N). According to my micro benchmark: #host children -> distribution time 100 -> 67 [us] 200 -> 203 [us] 300 -> 497 [us] 400 -> 1331 [us] 500 -> 2084 [us] 773553 1 shinyak 2012-11-21 21:44:51 -0800 I would like to upload benchmarks later. 773590 2 shinyak 2012-11-21 22:46:43 -0800 InsertionPoint::nextTo() takes O(N). and it's called in NodeRenderingContext::nextRenderer(), which is called O(N) times. So Element::attach() will be O(N^2). 773595 3 shinyak 2012-11-21 22:54:32 -0800 > #host children -> distribution time > 100 -> 67 [us] > 200 -> 203 [us] > 300 -> 497 [us] > 400 -> 1331 [us] > 500 -> 2084 [us] Sorry, this is not correct. distribution is O(N). 773691 4 175610 shinyak 2012-11-22 00:40:41 -0800 Created attachment 175610 Patch 773913 5 175610 webkit.review.bot 2012-11-22 06:40:27 -0800 Comment on attachment 175610 Patch Attachment 175610 did not pass chromium-ews (chromium-xvfb): Output: http://queues.webkit.org/results/14966355 New failing tests: platform/chromium-linux/fast/text/international/complex-joining-using-gpos.html 775083 6 shinyak 2012-11-25 18:26:20 -0800 It seems just a flake. Let me add cq+ again. 775228 7 175610 webkit.review.bot 2012-11-26 01:08:05 -0800 Comment on attachment 175610 Patch Clearing flags on attachment: 175610 Committed r135689: <http://trac.webkit.org/changeset/135689> 775230 8 webkit.review.bot 2012-11-26 01:08:10 -0800 All reviewed patches have been landed. Closing bug. 175610 2012-11-22 00:40:41 -0800 2012-11-26 01:08:05 -0800 Patch bug-103017-20121122173827.patch text/plain 4657 shinyak U3VidmVyc2lvbiBSZXZpc2lvbjogMTM1NDYwCmRpZmYgLS1naXQgYS9Tb3VyY2UvV2ViQ29yZS9D aGFuZ2VMb2cgYi9Tb3VyY2UvV2ViQ29yZS9DaGFuZ2VMb2cKaW5kZXggMTBjN2I2MmI5MDE4YTNh ZTNkMjEzYjJkNDZlMWZjNTM3Mjc5MTg0MS4uNTI3OTZhYjRkODA2ZjA4M2Y1MTBlYzU1OTViOTI5 ZTNmNDIyNGJmNCAxMDA2NDQKLS0tIGEvU291cmNlL1dlYkNvcmUvQ2hhbmdlTG9nCisrKyBiL1Nv dXJjZS9XZWJDb3JlL0NoYW5nZUxvZwpAQCAtMSwzICsxLDM1IEBACisyMDEyLTExLTIyICBTaGlu eWEgS2F3YW5ha2EgIDxzaGlueWFrQGNocm9taXVtLm9yZz4KKworICAgICAgICBbU2hhZG93XSBB dHRhY2hpbmcgY2hpbGRyZW4gb2YgYSBzaGFkb3cgaG9zdCB0YWtlcyBPKE5eMikgd2hlcmUgTiBp cyB0aGUgbnVtYmVyIG9mIGhvc3QgY2hpbGRyZW4KKyAgICAgICAgaHR0cHM6Ly9idWdzLndlYmtp dC5vcmcvc2hvd19idWcuY2dpP2lkPTEwMzAxNworCisgICAgICAgIFJldmlld2VkIGJ5IE5PQk9E WSAoT09QUyEpLgorCisgICAgICAgIFNpbmNlIENvbnRlbnREaXN0cmlidXRpb24gd2FzIGp1c3Qg YSBWZWN0b3IsIENvbnRlbnREaXN0cmlidXRpb246OmZpbmQoKSB0b29rIE8oTikuIEVhY2ggY2hp bGQgb2Ygc2hhZG93IGhvc3QgY2FsbHMgaXQuCisgICAgICAgIEFzIGEgcmVzdWx0LCBhdHRhY2hp bmcgY2hpbGRyZW4gb2Ygc2hhZG93IGhvc3QgdGFrZXMgTyhOXjIpIGF0IGFsbC4KKworICAgICAg ICBJbiB0aGlzIHBhdGNoLCB3ZSBtYWtlIENvbnRlbnREaXN0cmlidXRpb246OmZpbmQoKSBPKDEp IGFtb3J0aXplZGx5LiBXZSBpbnRyb2R1Y2UgSGFzaE1hcCBmcm9tIGEgTm9kZSB0byBWZWN0b3Ig aW5kZXgsCisgICAgICAgIGFuZCB1c2UgaXQgZm9yIENvbnRlbnREaXN0cmlidXRpb246OmZpbmQo KS4KKworICAgICAgICBObyBuZXcgdGVzdHMsIGNvdmVyZWQgYnkgZXhpc3RpbmcgdGVzdHMuCisK KyAgICAgICAgKiBodG1sL3NoYWRvdy9Db250ZW50RGlzdHJpYnV0b3IuY3BwOgorICAgICAgICAo V2ViQ29yZTo6Q29udGVudERpc3RyaWJ1dGlvbjo6c3dhcCk6CisgICAgICAgIChXZWJDb3JlKToK KyAgICAgICAgKFdlYkNvcmU6OkNvbnRlbnREaXN0cmlidXRpb246OmFwcGVuZCk6CisgICAgICAg IChXZWJDb3JlOjpDb250ZW50RGlzdHJpYnV0aW9uOjpmaW5kKToKKyAgICAgICAgKFdlYkNvcmU6 OkNvbnRlbnREaXN0cmlidXRvcjo6ZGlzdHJpYnV0ZVNlbGVjdGlvbnNUbyk6CisgICAgICAgICog aHRtbC9zaGFkb3cvQ29udGVudERpc3RyaWJ1dG9yLmg6CisgICAgICAgIChDb250ZW50RGlzdHJp YnV0aW9uKTogQ29udGVudERpc3RyaWJ1dGlvbiBub3cgY29udGFpbnMgVmVjdG9yIGFuZCBhIHJl dmVyc2UgbWFwLgorICAgICAgICAoV2ViQ29yZTo6Q29udGVudERpc3RyaWJ1dGlvbjo6Zmlyc3Qp OgorICAgICAgICAoV2ViQ29yZTo6Q29udGVudERpc3RyaWJ1dGlvbjo6bGFzdCk6CisgICAgICAg IChXZWJDb3JlOjpDb250ZW50RGlzdHJpYnV0aW9uOjphdCk6CisgICAgICAgIChXZWJDb3JlOjpD b250ZW50RGlzdHJpYnV0aW9uOjpzaXplKToKKyAgICAgICAgKFdlYkNvcmU6OkNvbnRlbnREaXN0 cmlidXRpb246OmlzRW1wdHkpOgorICAgICAgICAoV2ViQ29yZTo6Q29udGVudERpc3RyaWJ1dGlv bjo6Y2xlYXIpOgorICAgICAgICAoV2ViQ29yZTo6Q29udGVudERpc3RyaWJ1dGlvbjo6Y29udGFp bnMpOgorICAgICAgICAoV2ViQ29yZTo6Q29udGVudERpc3RyaWJ1dGlvbjo6bm9kZXMpOgorCiAy MDEyLTExLTIwICBKYW1lcyBTaW1vbnNlbiAgPHNpbW9uamFtQGNocm9taXVtLm9yZz4KIAogICAg ICAgICBbUmVzb3VyY2UgVGltaW5nXSBQb3B1bGF0ZSBQZXJmb3JtYW5jZVJlc291cmNlVGltaW5n IHN0cnVjdHMgd2l0aCB0aW1pbmcgZGF0YQpkaWZmIC0tZ2l0IGEvU291cmNlL1dlYkNvcmUvaHRt bC9zaGFkb3cvQ29udGVudERpc3RyaWJ1dG9yLmNwcCBiL1NvdXJjZS9XZWJDb3JlL2h0bWwvc2hh ZG93L0NvbnRlbnREaXN0cmlidXRvci5jcHAKaW5kZXggOTU0ZGRjZjkwODQ3MTk5YWYwOWQ0Njc4 MTA5ZjNjODlmOGNjZTNjMy4uZTMyMTY4MzlmZGY3YTdmODIyM2UzYTUwMmZmNDVmYzE4MTAwNmY1 MCAxMDA2NDQKLS0tIGEvU291cmNlL1dlYkNvcmUvaHRtbC9zaGFkb3cvQ29udGVudERpc3RyaWJ1 dG9yLmNwcAorKysgYi9Tb3VyY2UvV2ViQ29yZS9odG1sL3NoYWRvdy9Db250ZW50RGlzdHJpYnV0 b3IuY3BwCkBAIC0zNiw2ICszNiwyOCBAQAogCiBuYW1lc3BhY2UgV2ViQ29yZSB7CiAKK3ZvaWQg Q29udGVudERpc3RyaWJ1dGlvbjo6c3dhcChDb250ZW50RGlzdHJpYnV0aW9uJiBvdGhlcikKK3sK KyAgICBtX25vZGVzLnN3YXAob3RoZXIubV9ub2Rlcyk7CisgICAgbV9pbmRpY2VzLnN3YXAob3Ro ZXIubV9pbmRpY2VzKTsKK30KKwordm9pZCBDb250ZW50RGlzdHJpYnV0aW9uOjphcHBlbmQoUGFz c1JlZlB0cjxOb2RlPiBub2RlKQoreworICAgIHNpemVfdCBzaXplID0gbV9ub2Rlcy5zaXplKCk7 CisgICAgbV9pbmRpY2VzLnNldChub2RlLmdldCgpLCBzaXplKTsKKyAgICBtX25vZGVzLmFwcGVu ZChub2RlKTsKK30KKworc2l6ZV90IENvbnRlbnREaXN0cmlidXRpb246OmZpbmQoY29uc3QgTm9k ZSogbm9kZSkgY29uc3QKK3sKKyAgICBIYXNoTWFwPGNvbnN0IE5vZGUqLCBzaXplX3Q+Ojpjb25z dF9pdGVyYXRvciBpdCA9IG1faW5kaWNlcy5maW5kKG5vZGUpOworICAgIGlmIChpdCA9PSBtX2lu ZGljZXMuZW5kKCkpCisgICAgICAgIHJldHVybiBub3RGb3VuZDsKKworICAgIHJldHVybiBpdC5n ZXQoKS0+dmFsdWU7Cit9CisKIENvbnRlbnREaXN0cmlidXRvcjo6Q29udGVudERpc3RyaWJ1dG9y KCkKICAgICA6IG1fdmFsaWRpdHkoVW5kZXRlcm1pbmVkKQogewpAQCAtMTU2LDEwICsxNzgsMTAg QEAgdm9pZCBDb250ZW50RGlzdHJpYnV0b3I6OmRpc3RyaWJ1dGVTZWxlY3Rpb25zVG8oSW5zZXJ0 aW9uUG9pbnQqIGluc2VydGlvblBvaW50LAogICAgICAgICBpZiAoZGlzdHJpYnV0ZWRbaV0pCiAg ICAgICAgICAgICBjb250aW51ZTsKIAotICAgICAgICBpZiAoIXF1ZXJ5Lm1hdGNoZXMocG9vbCwg aSkpCisgICAgICAgIGlmICghcXVlcnkubWF0Y2hlcyhwb29sLm5vZGVzKCksIGkpKQogICAgICAg ICAgICAgY29udGludWU7CiAKLSAgICAgICAgTm9kZSogY2hpbGQgPSBwb29sW2ldLmdldCgpOwor ICAgICAgICBOb2RlKiBjaGlsZCA9IHBvb2wuYXQoaSkuZ2V0KCk7CiAgICAgICAgIGRpc3RyaWJ1 dGlvbi5hcHBlbmQoY2hpbGQpOwogICAgICAgICBtX25vZGVUb0luc2VydGlvblBvaW50LmFkZChj aGlsZCwgaW5zZXJ0aW9uUG9pbnQpOwogICAgICAgICBkaXN0cmlidXRlZFtpXSA9IHRydWU7CmRp ZmYgLS1naXQgYS9Tb3VyY2UvV2ViQ29yZS9odG1sL3NoYWRvdy9Db250ZW50RGlzdHJpYnV0b3Iu aCBiL1NvdXJjZS9XZWJDb3JlL2h0bWwvc2hhZG93L0NvbnRlbnREaXN0cmlidXRvci5oCmluZGV4 IDBkOGQwMDgyZTZlOTI0MTBlNDNmNjA2MGNlMzZmMTZlNjhlMDQ2YmIuLjk3Y2ZmYmNjNzNlMWM3 OTUxZWM1ODk2ZDNhNWE0OTNmM2I3YzE2ZjkgMTAwNjQ0Ci0tLSBhL1NvdXJjZS9XZWJDb3JlL2h0 bWwvc2hhZG93L0NvbnRlbnREaXN0cmlidXRvci5oCisrKyBiL1NvdXJjZS9XZWJDb3JlL2h0bWwv c2hhZG93L0NvbnRlbnREaXN0cmlidXRvci5oCkBAIC00NCw3ICs0NCwyOSBAQCBjbGFzcyBJbnNl cnRpb25Qb2ludDsKIGNsYXNzIE5vZGU7CiBjbGFzcyBTaGFkb3dSb290OwogCi10eXBlZGVmIFZl Y3RvcjxSZWZQdHI8Tm9kZT4gPiBDb250ZW50RGlzdHJpYnV0aW9uOworY2xhc3MgQ29udGVudERp c3RyaWJ1dGlvbiB7CitwdWJsaWM6CisgICAgUGFzc1JlZlB0cjxOb2RlPiBmaXJzdCgpIGNvbnN0 IHsgcmV0dXJuIG1fbm9kZXMuZmlyc3QoKTsgfQorICAgIFBhc3NSZWZQdHI8Tm9kZT4gbGFzdCgp IGNvbnN0IHsgcmV0dXJuIG1fbm9kZXMubGFzdCgpOyB9CisgICAgUGFzc1JlZlB0cjxOb2RlPiBh dChzaXplX3QgaW5kZXgpIGNvbnN0IHsgcmV0dXJuIG1fbm9kZXMuYXQoaW5kZXgpOyB9CisKKyAg ICBzaXplX3Qgc2l6ZSgpIGNvbnN0IHsgcmV0dXJuIG1fbm9kZXMuc2l6ZSgpOyB9CisgICAgYm9v bCBpc0VtcHR5KCkgY29uc3QgeyByZXR1cm4gbV9ub2Rlcy5pc0VtcHR5KCk7IH0KKworICAgIHZv aWQgYXBwZW5kKFBhc3NSZWZQdHI8Tm9kZT4pOworICAgIHZvaWQgY2xlYXIoKSB7IG1fbm9kZXMu Y2xlYXIoKTsgbV9pbmRpY2VzLmNsZWFyKCk7IH0KKworICAgIGJvb2wgY29udGFpbnMoY29uc3Qg Tm9kZSogbm9kZSkgY29uc3QgeyByZXR1cm4gbV9pbmRpY2VzLmNvbnRhaW5zKG5vZGUpOyB9Cisg ICAgc2l6ZV90IGZpbmQoY29uc3QgTm9kZSopIGNvbnN0OworCisgICAgdm9pZCBzd2FwKENvbnRl bnREaXN0cmlidXRpb24mIG90aGVyKTsKKworICAgIGNvbnN0IFZlY3RvcjxSZWZQdHI8Tm9kZT4g PiYgbm9kZXMoKSBjb25zdCB7IHJldHVybiBtX25vZGVzOyB9CisKK3ByaXZhdGU6CisgICAgVmVj dG9yPFJlZlB0cjxOb2RlPiA+IG1fbm9kZXM7CisgICAgSGFzaE1hcDxjb25zdCBOb2RlKiwgc2l6 ZV90PiBtX2luZGljZXM7Cit9OwogCiBjbGFzcyBDb250ZW50RGlzdHJpYnV0b3IgewogICAgIFdU Rl9NQUtFX05PTkNPUFlBQkxFKENvbnRlbnREaXN0cmlidXRvcik7Cg==