RESOLVED FIXED 130384
Micro-optimize element descendant iterator.
https://bugs.webkit.org/show_bug.cgi?id=130384
Summary Micro-optimize element descendant iterator.
Andreas Kling
Reported 2014-03-17 22:34:57 PDT
Patch forthcoming.
Attachments
Patch (6.20 KB, patch)
2014-03-17 22:41 PDT, Andreas Kling
benjamin: review+
buildbot: commit-queue-
Archive of layout-test-results from webkit-ews-14 for mac-mountainlion-wk2 (756.85 KB, application/zip)
2014-03-17 23:32 PDT, Build Bot
no flags
Archive of layout-test-results from webkit-ews-04 for mac-mountainlion (788.70 KB, application/zip)
2014-03-18 00:04 PDT, Build Bot
no flags
Archive of layout-test-results from webkit-ews-06 for mac-mountainlion (788.14 KB, application/zip)
2014-03-18 01:02 PDT, Build Bot
no flags
Patch (16.27 KB, patch)
2014-03-18 03:34 PDT, Andreas Kling
koivisto: review-
Better patch (17.81 KB, patch)
2014-03-18 04:06 PDT, Andreas Kling
no flags
Even better patch (17.18 KB, patch)
2014-03-18 04:07 PDT, Andreas Kling
oliver: review-
Andreas Kling
Comment 1 2014-03-17 22:41:21 PDT
Build Bot
Comment 2 2014-03-17 23:31:59 PDT
Comment on attachment 227013 [details] Patch Attachment 227013 [details] did not pass mac-wk2-ews (mac-wk2): Output: http://webkit-queues.appspot.com/results/4817975563517952 New failing tests: accessibility/radio-button-title-label.html accessibility/title-ui-element-correctness.html fast/dom/HTMLLabelElement/focus-label.html fast/events/scroll-to-anchor-in-overflow-hidden.html platform/mac/accessibility/internal-link-when-document-has-fragment.html fast/dom/HTMLLabelElement/click-label.html svg/custom/scrolling-embedded-svg-file-image-repaint-problem.html
Build Bot
Comment 3 2014-03-17 23:32:01 PDT
Created attachment 227015 [details] Archive of layout-test-results from webkit-ews-14 for mac-mountainlion-wk2 The attached test failures were seen while running run-webkit-tests on the mac-wk2-ews. Bot: webkit-ews-14 Port: mac-mountainlion-wk2 Platform: Mac OS X 10.8.5
Build Bot
Comment 4 2014-03-18 00:04:26 PDT
Comment on attachment 227013 [details] Patch Attachment 227013 [details] did not pass mac-ews (mac): Output: http://webkit-queues.appspot.com/results/5000623342747648 New failing tests: accessibility/radio-button-title-label.html accessibility/title-ui-element-correctness.html fast/dom/HTMLLabelElement/focus-label.html fast/events/scroll-to-anchor-in-overflow-hidden.html platform/mac/accessibility/internal-link-when-document-has-fragment.html fast/dom/HTMLLabelElement/click-label.html svg/custom/scrolling-embedded-svg-file-image-repaint-problem.html
Build Bot
Comment 5 2014-03-18 00:04:29 PDT
Created attachment 227016 [details] Archive of layout-test-results from webkit-ews-04 for mac-mountainlion The attached test failures were seen while running run-webkit-tests on the mac-ews. Bot: webkit-ews-04 Port: mac-mountainlion Platform: Mac OS X 10.8.5
Build Bot
Comment 6 2014-03-18 01:02:02 PDT
Comment on attachment 227013 [details] Patch Attachment 227013 [details] did not pass mac-ews (mac): Output: http://webkit-queues.appspot.com/results/5679901411639296 New failing tests: accessibility/radio-button-title-label.html accessibility/title-ui-element-correctness.html fast/dom/HTMLLabelElement/focus-label.html fast/events/scroll-to-anchor-in-overflow-hidden.html platform/mac/accessibility/internal-link-when-document-has-fragment.html fast/dom/HTMLLabelElement/click-label.html svg/custom/scrolling-embedded-svg-file-image-repaint-problem.html
Build Bot
Comment 7 2014-03-18 01:02:06 PDT
Created attachment 227017 [details] Archive of layout-test-results from webkit-ews-06 for mac-mountainlion The attached test failures were seen while running run-webkit-tests on the mac-ews. Bot: webkit-ews-06 Port: mac-mountainlion Platform: Mac OS X 10.8.5
Andreas Kling
Comment 8 2014-03-18 03:34:32 PDT
Antti Koivisto
Comment 9 2014-03-18 03:53:13 PDT
Comment on attachment 227023 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=227023&action=review > Source/WebCore/dom/ElementDescendantIterator.h:38 > + ElementDescendantIterator& operator++(); It is not correct to just have custom operator++ as rest of the base class traversal functions will not be stack aware. It is probably better to just get rid of the base class.
Andreas Kling
Comment 10 2014-03-18 04:06:06 PDT
Created attachment 227026 [details] Better patch
Andreas Kling
Comment 11 2014-03-18 04:07:09 PDT
Created attachment 227028 [details] Even better patch
Antti Koivisto
Comment 12 2014-03-18 10:57:14 PDT
Comment on attachment 227028 [details] Even better patch View in context: https://bugs.webkit.org/attachment.cgi?id=227028&action=review > Source/WebCore/dom/ElementDescendantIterator.h:51 > + Vector<Element*, 16, UnsafeVectorOverflow> m_stack; Please call these something more informative like m_ancestorSiblingStack > Source/WebCore/dom/ElementDescendantIterator.h:192 > + Element* firstChild = Traversal<Element>::firstChild(m_current); > + Element* nextSibling = Traversal<Element>::nextSibling(m_current); Please just use ElementTraversal directly. > Source/WebCore/dom/ElementDescendantIterator.h:196 > + if (firstChild) { > + if (nextSibling) > + m_stack.append(nextSibling); Clever! > Source/WebCore/dom/SelectorQuery.cpp:267 > - for (auto& element : descendantsOfType<Element>(const_cast<ContainerNode&>(rootNode))) { > + for (auto& element : elementDescendants(const_cast<ContainerNode&>(rootNode))) { This is bit confusing. It is ok as intermediate step but we should really add all the missing functionality here and start returning ElementDescendantIterator from descendantsOfType<Element>. The typed iterator can then be implemented in terms of ElementDescendantIterator.
Andreas Kling
Comment 13 2014-03-18 11:13:01 PDT
Alexey Proskuryakov
Comment 14 2015-01-10 15:53:00 PST
Comment on attachment 227028 [details] Even better patch View in context: https://bugs.webkit.org/attachment.cgi?id=227028&action=review >> Source/WebCore/dom/ElementDescendantIterator.h:51 >> + Vector<Element*, 16, UnsafeVectorOverflow> m_stack; > > Please call these something more informative like m_ancestorSiblingStack Why was it necessary to use UnsafeVectorOverflow here? DOM iteration the last place where I'd want to disable bounds checking in vectors.
Oliver Hunt
Comment 15 2015-01-10 17:00:09 PST
Comment on attachment 227028 [details] Even better patch View in context: https://bugs.webkit.org/attachment.cgi?id=227028&action=review >>> Source/WebCore/dom/ElementDescendantIterator.h:51 >>> + Vector<Element*, 16, UnsafeVectorOverflow> m_stack; >> >> Please call these something more informative like m_ancestorSiblingStack > > Why was it necessary to use UnsafeVectorOverflow here? DOM iteration the last place where I'd want to disable bounds checking in vectors. I agree with alexey here, do you have performance number that show iteration to actually be a problem?
Andreas Kling
Comment 16 2015-01-11 00:08:13 PST
(In reply to comment #15) > Comment on attachment 227028 [details] > Even better patch > > View in context: > https://bugs.webkit.org/attachment.cgi?id=227028&action=review > > >>> Source/WebCore/dom/ElementDescendantIterator.h:51 > >>> + Vector<Element*, 16, UnsafeVectorOverflow> m_stack; > >> > >> Please call these something more informative like m_ancestorSiblingStack > > > > Why was it necessary to use UnsafeVectorOverflow here? DOM iteration the last place where I'd want to disable bounds checking in vectors. > > I agree with alexey here, do you have performance number that show iteration > to actually be a problem? Not sure what's up with r-'ing this patch, since it landed (and shipped) already. As I recall there was a small improvement on the querySelector torture tests from skipping the bounds checking. I will re-run some A/B tests and dump numbers here.
Oliver Hunt
Comment 17 2015-01-11 10:21:22 PST
ap had just cc'd me so i didn't realise it was an archaic patch :D
Andreas Kling
Comment 18 2015-01-11 19:25:38 PST
I remeasured the performance with bounds checking on/off and it's a wash. Filed bug 140346 with a patch to re-enable the checks.
Note You need to log in before you can comment on or make changes to this bug.