Bug 130384 – Micro-optimize element descendant iterator.

• Status: RESOLVED
• Resolution: FIXED
• Component: DOM

[Andreas Kling]

Patch forthcoming.

[Andreas Kling]

Created attachment 227013 [details]
Patch

[Build Bot]

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]

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 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]

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 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]

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]

Created attachment 227023 [details]
Patch

[Antti Koivisto]

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]

Created attachment 227026 [details]
Better patch

[Andreas Kling]

Created attachment 227028 [details]
Even better patch

[Antti Koivisto]

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]

Committed r165822: <http://trac.webkit.org/changeset/165822>

[Alexey Proskuryakov]

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 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]

(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]

ap had just cc'd me so i didn't realise it was an archaic patch :D

[Andreas Kling]

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.