| Summary: | Micro-optimize element descendant iterator. | ||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Product: | WebKit | Reporter: | Andreas Kling <kling> | ||||||||||||||||
| Component: | DOM | Assignee: | Andreas Kling <kling> | ||||||||||||||||
| Status: | RESOLVED FIXED | ||||||||||||||||||
| Severity: | Normal | CC: | allan.jensen, ap, buildbot, commit-queue, esprehn+autocc, kangil.han, kling, koivisto, oliver, rniwa, sam | ||||||||||||||||
| Priority: | P2 | ||||||||||||||||||
| Version: | 528+ (Nightly build) | ||||||||||||||||||
| Hardware: | Unspecified | ||||||||||||||||||
| OS: | Unspecified | ||||||||||||||||||
| Attachments: |
|
||||||||||||||||||
|
Description
Andreas Kling
2014-03-17 22:34:57 PDT
Created attachment 227013 [details]
Patch
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 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
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 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
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 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
Created attachment 227023 [details]
Patch
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. Created attachment 227026 [details]
Better patch
Created attachment 227028 [details]
Even better patch
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. Committed r165822: <http://trac.webkit.org/changeset/165822> 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. 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? (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. ap had just cc'd me so i didn't realise it was an archaic patch :D 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. |