19312 2008-05-29 10:57:43 -0700 SVG hit testing is *way* too slow 2010-05-05 00:31:57 -0700 1 1 1 Unclassified WebKit SVG 528+ (Nightly build) Mac OS X 10.5 RESOLVED FIXED P2 Normal --- 1 eric webkit-unassigned alp krit simon.fraser zimmermann oldest_to_newest 81866 0 eric 2008-05-29 10:57:43 -0700 SVG hit testing is *way* too slow See the attached test case. I think the major problem is that RenderPath::nodeAtPoint() does not to any sort of optimization (like checking against the bbox) before testing against fill contains. Thus for an example like the one in the test case, we end up doing hundreds if not thousands of unnecessary path containment tests (which may involve mallocs, etc). 81868 1 21416 eric 2008-05-29 10:58:59 -0700 Created attachment 21416 test case (sorta a layout test, not quite) See the attached test case. We don't really have a very good way to do perf-based layout tests. The attached test could be modified to be say PASS when it runs under a certain threshold or something. 103863 2 26329 simon.fraser 2008-12-30 22:32:27 -0800 Created attachment 26329 Patch This patch implements your suggestion, and removes much of the hit testing cost. However, repaint is still very expensive. Sharking found bug 23050. 103866 3 simon.fraser 2008-12-30 22:44:47 -0800 Repaint is very expensive because EVERYTHING repaints even if only a small area is dirtied.RenderPath::paint() does no short-circuiting if the relativeBBox() is not in the dirty rect. 104182 4 simon.fraser 2009-01-02 15:30:08 -0800 See also bug 15393. 176029 5 krit 2009-12-30 13:36:02 -0800 *** Bug 15704 has been marked as a duplicate of this bug. *** 176036 6 krit 2009-12-30 13:44:11 -0800 (In reply to comment #3) > Repaint is very expensive because EVERYTHING repaints even if only a small area > is dirtied.RenderPath::paint() does no short-circuiting if the relativeBBox() > is not in the dirty rect. Will the patch on bug 30055 fix this? 220716 7 55039 krit 2010-05-04 12:49:40 -0700 Created attachment 55039 Patch 220717 8 krit 2010-05-04 12:50:58 -0700 (In reply to comment #7) > Created an attachment (id=55039) [details] > Patch This is a huge speed-up of the test attached to this br. 220725 9 55039 zimmermann 2010-05-04 13:06:48 -0700 Comment on attachment 55039 Patch Looks great to me, as discussed before :-) r=me. 220989 10 55039 krit 2010-05-05 00:31:46 -0700 Comment on attachment 55039 Patch Clearing flags on attachment: 55039 Committed r58804: <http://trac.webkit.org/changeset/58804> 220991 11 krit 2010-05-05 00:31:57 -0700 All reviewed patches have been landed. Closing bug. 21416 2008-05-29 10:58:59 -0700 2008-05-29 10:58:59 -0700 test case (sorta a layout test, not quite) t.svg image/svg+xml 2599 eric PD94bWwgdmVyc2lvbj0iMS4wIiBlbmNvZGluZz0iVVRGLTgiPz4KPHN2ZyB4bWxucz0iaHR0cDov L3d3dy53My5vcmcvMjAwMC9zdmciIG9ubG9hZD0ib25Mb2FkKCkiPgogIDxzY3JpcHQ+CiAgICA8 IVtDREFUQVsKICAgICAgdmFyIGN1clggPSAwOwogICAgICB2YXIgY3VyWSA9IDA7CiAgICAgIHZh ciB3aWR0aCA9IDIwOwogICAgICB2YXIgaGVpZ2h0ID0gMjA7CiAgICAgIHZhciBjeCA9IDYwOwog ICAgICB2YXIgY3kgPSA0MDsKICAgICAgdmFyIGJvcmRlclggPSAyMDsKICAgICAgdmFyIGJvcmRl clkgPSA4MDsKICAgICAgCiAgICAgIHZhciBzdGFydCA9IG5ldyBEYXRlKCk7CiAgICAgIGxheW91 dFRlc3RDb250cm9sbGVyLndhaXRVbnRpbERvbmUoKTsKICAgICAgbGF5b3V0VGVzdENvbnRyb2xs ZXIuZHVtcEFzVGV4dCgpOwogICAgICAKICAgICAgZnVuY3Rpb24gb25Mb2FkKCkKICAgICAgewog ICAgICB0cnkgewogICAgICAgIGZvciAodmFyIGR4ID0gMDsgZHggPCBjeDsgZHgrKykgewogICAg ICAgICAgZm9yKHZhciBkeT0wOyBkeSA8IGN5OyBkeSsrKSB7CiAgICAgICAgICAgIC8vIFBpY2sg b25lIG9yIHRoZSBvdGhlcgogICAgICAgICAgICAvKgogICAgICAgICAgICB2YXIgciA9IGRvY3Vt ZW50LmNyZWF0ZUVsZW1lbnROUygiaHR0cDovL3d3dy53My5vcmcvMjAwMC9zdmciLCAicmVjdCIp OwogICAgICAgICAgICByLnguYmFzZVZhbC52YWx1ZSA9IGJvcmRlclggKyB3aWR0aCAqIGR4Owog ICAgICAgICAgICByLnkuYmFzZVZhbC52YWx1ZSA9IGJvcmRlclkgKyBoZWlnaHQqIGR5OwogICAg ICAgICAgICByLndpZHRoLmJhc2VWYWwudmFsdWUgPSB3aWR0aDsKICAgICAgICAgICAgci5oZWln aHQuYmFzZVZhbC52YWx1ZSA9IGhlaWdodDsKICAgICAgICAgICAgKi8KICAgICAgICAgICAgLy8g b3IuLi4KICAgICAgICAgICAgdmFyIHIgPSBkb2N1bWVudC5jcmVhdGVFbGVtZW50TlMoImh0dHA6 Ly93d3cudzMub3JnLzIwMDAvc3ZnIiwgImNpcmNsZSIpOwogICAgICAgICAgICByLmN4LmJhc2VW YWwudmFsdWUgPSBib3JkZXJYICsgd2lkdGggKiBkeCArIHdpZHRoLzI7CiAgICAgICAgICAgIHIu Y3kuYmFzZVZhbC52YWx1ZSA9IGJvcmRlclkgKyBoZWlnaHQgKiBkeSArIGhlaWdodC8yOwogICAg ICAgICAgICByLnIuYmFzZVZhbC52YWx1ZSA9IHdpZHRoLzI7CiAgICAgICAgICAgIAogICAgICAg ICAgICByLnNldEF0dHJpYnV0ZSgiZmlsbCIsICJibHVlIik7CiAgICAgICAgICAgIHIuc2V0QXR0 cmlidXRlKCJzdHJva2UiLCAiYmxhY2siKTsKICAgICAgICAgICAgci5hZGRFdmVudExpc3RlbmVy KCJtb3VzZW92ZXIiLCBvbk1vdXNlT3ZlciwgZmFsc2UpOwogICAgICAgICAgICByLmFkZEV2ZW50 TGlzdGVuZXIoIm1vdXNlb3V0Iiwgb25Nb3VzZU91dCwgZmFsc2UpOwogICAgICAgICAgICBkb2N1 bWVudC5nZXRFbGVtZW50QnlJZCgiY2lyY2xlcyIpLmFwcGVuZENoaWxkKHIpOwogICAgICAgICAg ICAKICAgICAgICAgICAgCiAgICAgICAgICB9CiAgICAgICAgfQogICAgICAKICAgICAgfSBjYXRj aChlKSB7IGFsZXJ0KGUpOyB9CiAgICAgIGV2ZW50U2VuZGVyLm1vdXNlTW92ZVRvKGJvcmRlclgg KyB3aWR0aC8yLCBib3JkZXJZICsgd2lkdGgvMik7CiAgICAgIH0KCiAgICAgIGZ1bmN0aW9uIG9u TW91c2VPdmVyKGV2dCkKICAgICAgewogICAgICAgIGV2dC50YXJnZXQuc2V0QXR0cmlidXRlKCJm aWxsIiwgInJlZCIpOwogICAgICAgIGN1clggKz0gMTsKICAgICAgICBpZiAoY3VyWCA+PSBjeCkK ICAgICAgICB7CiAgICAgICAgICBjdXJYID0gMDsKICAgICAgICAgIGN1clkgKz0gMTsKICAgICAg ICAgIGlmIChjdXJZID49IGN5KQogICAgICAgICAgewogICAgICAgICAgICB2YXIgZW5kID0gbmV3 IERhdGUoKTsKICAgICAgICAgICAgZG9jdW1lbnQuZ2V0RWxlbWVudEJ5SWQoImxhYmVsIikuZmly c3RDaGlsZC5kYXRhID0gIkRvbmUgaW4gIiArIChlbmQtc3RhcnQpLzEwMDAgKyAiIHNlY29uZHMi OwogICAgICAgICAgICBsYXlvdXRUZXN0Q29udHJvbGxlci5ub3RpZnlEb25lKCk7CiAgICAgICAg ICB9CiAgICAgICAgfQogICAgICAgIAogICAgICAgIHNldFRpbWVvdXQoImdvQWdhaW4oKSIsIDEw KTsKICAgICAgfQogICAgICBmdW5jdGlvbiBnb0FnYWluKCkgewogICAgICAgICAgICAgIHhQb3Mg PSBjdXJYICogd2lkdGggKyB3aWR0aC8yICsgYm9yZGVyWDsKICAgICAgICB5UG9zID0gY3VyWSAq IGhlaWdodCArIGhlaWdodC8yICsgYm9yZGVyWTsKICAgICAgICAKICAgICAgICBldmVudFNlbmRl ci5tb3VzZU1vdmVUbyh4UG9zLCB5UG9zKTsKICAgICAgfQogICAgICBmdW5jdGlvbiBvbk1vdXNl T3V0KGV2dCkKICAgICAgewogICAgICBldnQudGFyZ2V0LnNldEF0dHJpYnV0ZSgiZmlsbCIsICJi bHVlIik7Ci8vICAgIGV2dC50YXJnZXQud2lkdGguYmFzZVZhbC52YWx1ZSA9IDIwOwovLyAgICAg IGV2dC50YXJnZXQuaGVpZ2h0LmJhc2VWYWwudmFsdWUgPSAyMDsKICAgICAgfQogICAgXV0+CiAg PC9zY3JpcHQ+CgogIDx0ZXh0IHg9IjUwIiB5PSI1MCIgaWQ9ImxhYmVsIj5SdW5uaW5nIHRlc3Q8 L3RleHQ+CiAgPGcgaWQ9ImNpcmNsZXMiIC8+Cjwvc3ZnPg== 26329 2008-12-30 22:32:27 -0800 2010-05-04 12:49:33 -0700 Patch 19312_partial_patch.txt text/plain 1608 simon.fraser ZGlmZiAtLWdpdCBhL1dlYkNvcmUvcmVuZGVyaW5nL1JlbmRlclBhdGguY3BwIGIvV2ViQ29yZS9y ZW5kZXJpbmcvUmVuZGVyUGF0aC5jcHAKaW5kZXggZTBlNmNjYS4uZjEwNTQ0ZCAxMDA2NDQKLS0t IGEvV2ViQ29yZS9yZW5kZXJpbmcvUmVuZGVyUGF0aC5jcHAKKysrIGIvV2ViQ29yZS9yZW5kZXJp bmcvUmVuZGVyUGF0aC5jcHAKQEAgLTI4NywxMCArMjg3LDIwIEBAIGJvb2wgUmVuZGVyUGF0aDo6 bm9kZUF0UG9pbnQoY29uc3QgSGl0VGVzdFJlcXVlc3QmIHJlcXVlc3QsIEhpdFRlc3RSZXN1bHQm IHJlc3VsCiAgICAgYm9vbCBpc1Zpc2libGUgPSAoc3R5bGUoKS0+dmlzaWJpbGl0eSgpID09IFZJ U0lCTEUpOwogICAgIGlmIChpc1Zpc2libGUgfHwgIWhpdFJ1bGVzLnJlcXVpcmVWaXNpYmxlKSB7 CiAgICAgICAgIEZsb2F0UG9pbnQgaGl0UG9pbnQgPSBtYXBBYnNvbHV0ZVBvaW50VG9Mb2NhbChh YnNvbHV0ZVBvaW50KTsKLSAgICAgICAgaWYgKChoaXRSdWxlcy5jYW5IaXRTdHJva2UgJiYgKHN0 eWxlKCktPnN2Z1N0eWxlKCktPmhhc1N0cm9rZSgpIHx8ICFoaXRSdWxlcy5yZXF1aXJlU3Ryb2tl KSAmJiBzdHJva2VDb250YWlucyhoaXRQb2ludCwgaGl0UnVsZXMucmVxdWlyZVN0cm9rZSkpCi0g ICAgICAgICAgICB8fCAoaGl0UnVsZXMuY2FuSGl0RmlsbCAmJiAoc3R5bGUoKS0+c3ZnU3R5bGUo KS0+aGFzRmlsbCgpIHx8ICFoaXRSdWxlcy5yZXF1aXJlRmlsbCkgJiYgZmlsbENvbnRhaW5zKGhp dFBvaW50LCBoaXRSdWxlcy5yZXF1aXJlRmlsbCkpKSB7Ci0gICAgICAgICAgICB1cGRhdGVIaXRU ZXN0UmVzdWx0KHJlc3VsdCwgYWJzb2x1dGVQb2ludCk7Ci0gICAgICAgICAgICByZXR1cm4gdHJ1 ZTsKKyAgICAgICAgaWYgKGhpdFJ1bGVzLmNhbkhpdFN0cm9rZSAmJiAoc3R5bGUoKS0+c3ZnU3R5 bGUoKS0+aGFzU3Ryb2tlKCkgfHwgIWhpdFJ1bGVzLnJlcXVpcmVTdHJva2UpKSB7CisgICAgICAg ICAgICBGbG9hdFJlY3Qgc3Ryb2tlUmVjdCA9IHJlbGF0aXZlQkJveCgpOworICAgICAgICAgICAg aWYgKHN0cm9rZVJlY3QuY29udGFpbnMoaGl0UG9pbnQpICYmIHN0cm9rZUNvbnRhaW5zKGhpdFBv aW50LCBoaXRSdWxlcy5yZXF1aXJlU3Ryb2tlKSkgeworICAgICAgICAgICAgICAgIHVwZGF0ZUhp dFRlc3RSZXN1bHQocmVzdWx0LCBhYnNvbHV0ZVBvaW50KTsKKyAgICAgICAgICAgICAgICByZXR1 cm4gdHJ1ZTsKKyAgICAgICAgICAgIH0KKyAgICAgICAgfQorCisgICAgICAgIGlmIChoaXRSdWxl cy5jYW5IaXRGaWxsICYmIChzdHlsZSgpLT5zdmdTdHlsZSgpLT5oYXNGaWxsKCkgfHwgIWhpdFJ1 bGVzLnJlcXVpcmVGaWxsKSkgeworICAgICAgICAgICAgRmxvYXRSZWN0IGZpbGxSZWN0ID0gcmVs YXRpdmVCQm94KGZhbHNlKTsKKyAgICAgICAgICAgIGlmIChmaWxsUmVjdC5jb250YWlucyhoaXRQ b2ludCkgJiYgZmlsbENvbnRhaW5zKGhpdFBvaW50LCBoaXRSdWxlcy5yZXF1aXJlRmlsbCkpIHsK KyAgICAgICAgICAgICAgICB1cGRhdGVIaXRUZXN0UmVzdWx0KHJlc3VsdCwgYWJzb2x1dGVQb2lu dCk7CisgICAgICAgICAgICAgICAgcmV0dXJuIHRydWU7CisgICAgICAgICAgICB9CiAgICAgICAg IH0KICAgICB9CiAK 55039 2010-05-04 12:49:40 -0700 2010-05-05 00:31:46 -0700 Patch bug-19312-20100504214938.patch text/plain 1631 krit SW5kZXg6IFdlYkNvcmUvQ2hhbmdlTG9nCj09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0KLS0tIFdlYkNvcmUvQ2hhbmdlTG9n CShyZXZpc2lvbiA1ODc2OCkKKysrIFdlYkNvcmUvQ2hhbmdlTG9nCSh3b3JraW5nIGNvcHkpCkBA IC0xLDMgKzEsMTkgQEAKKzIwMTAtMDUtMDQgIERpcmsgU2NodWx6ZSAgPGtyaXRAd2Via2l0Lm9y Zz4KKworICAgICAgICBSZXZpZXdlZCBieSBOT0JPRFkgKE9PUFMhKS4KKworICAgICAgICBTVkcg aGl0IHRlc3RpbmcgaXMgKndheSogdG9vIHNsb3cKKyAgICAgICAgaHR0cHM6Ly9idWdzLndlYmtp dC5vcmcvc2hvd19idWcuY2dpP2lkPTE5MzEyCisKKyAgICAgICAgVXNlIHRoZSBjYWNoZWQgc3Ry b2tlIGFuZCBmaWxsIGJvdW5kYXJpZXMgaW4gUmVuZGVyUGF0aCBhcyBhIGhldXJpc3RpayB0bwor ICAgICAgICBzcGVlZCB1cCBTVkcncyBoaXQgdGVzdGluZy4KKworICAgICAgICBObyBuZXcgdGVz dHMgYWRkZWQuCisKKyAgICAgICAgKiByZW5kZXJpbmcvUmVuZGVyUGF0aC5jcHA6CisgICAgICAg IChXZWJDb3JlOjpSZW5kZXJQYXRoOjpmaWxsQ29udGFpbnMpOgorICAgICAgICAoV2ViQ29yZTo6 UmVuZGVyUGF0aDo6c3Ryb2tlQ29udGFpbnMpOgorCiAyMDEwLTA1LTA0ICBQYXZlbCBGZWxkbWFu ICA8cGZlbGRtYW5AY2hyb21pdW0ub3JnPgogCiAgICAgICAgIFJldmlld2VkIGJ5IFRpbW90aHkg SGF0Y2hlci4KSW5kZXg6IFdlYkNvcmUvcmVuZGVyaW5nL1JlbmRlclBhdGguY3BwCj09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT0KLS0tIFdlYkNvcmUvcmVuZGVyaW5nL1JlbmRlclBhdGguY3BwCShyZXZpc2lvbiA1ODc0MikK KysrIFdlYkNvcmUvcmVuZGVyaW5nL1JlbmRlclBhdGguY3BwCSh3b3JraW5nIGNvcHkpCkBAIC03 Myw3ICs3Myw3IEBAIFJlbmRlclBhdGg6OlJlbmRlclBhdGgoU1ZHU3R5bGVkVHJhbnNmb3IKIAog Ym9vbCBSZW5kZXJQYXRoOjpmaWxsQ29udGFpbnMoY29uc3QgRmxvYXRQb2ludCYgcG9pbnQsIGJv b2wgcmVxdWlyZXNGaWxsKSBjb25zdAogewotICAgIGlmIChtX3BhdGguaXNFbXB0eSgpKQorICAg IGlmICghbV9maWxsQm91bmRpbmdCb3guY29udGFpbnMocG9pbnQpKQogICAgICAgICByZXR1cm4g ZmFsc2U7CiAKICAgICBpZiAocmVxdWlyZXNGaWxsICYmICFSZW5kZXJTVkdSZXNvdXJjZTo6Zmls bFBhaW50aW5nUmVzb3VyY2UodGhpcywgc3R5bGUoKSkpCkBAIC04NCw3ICs4NCw3IEBAIGJvb2wg UmVuZGVyUGF0aDo6ZmlsbENvbnRhaW5zKGNvbnN0IEZsb2EKIAogYm9vbCBSZW5kZXJQYXRoOjpz dHJva2VDb250YWlucyhjb25zdCBGbG9hdFBvaW50JiBwb2ludCwgYm9vbCByZXF1aXJlc1N0cm9r ZSkgY29uc3QKIHsKLSAgICBpZiAobV9wYXRoLmlzRW1wdHkoKSkKKyAgICBpZiAoIW1fc3Ryb2tl QW5kTWFya2VyQm91bmRpbmdCb3guY29udGFpbnMocG9pbnQpKQogICAgICAgICByZXR1cm4gZmFs c2U7CiAKICAgICBpZiAocmVxdWlyZXNTdHJva2UgJiYgIVJlbmRlclNWR1Jlc291cmNlOjpzdHJv a2VQYWludGluZ1Jlc291cmNlKHRoaXMsIHN0eWxlKCkpKQo=