WebKit Bugzilla
New
Browse
Log In
×
Sign in with GitHub
or
Remember my login
Create Account
·
Forgot Password
Forgotten password account recovery
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-
Details
Formatted Diff
Diff
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
Details
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
Details
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
Details
Patch
(16.27 KB, patch)
2014-03-18 03:34 PDT
,
Andreas Kling
koivisto
: review-
Details
Formatted Diff
Diff
Better patch
(17.81 KB, patch)
2014-03-18 04:06 PDT
,
Andreas Kling
no flags
Details
Formatted Diff
Diff
Even better patch
(17.18 KB, patch)
2014-03-18 04:07 PDT
,
Andreas Kling
oliver
: review-
Details
Formatted Diff
Diff
Show Obsolete
(6)
View All
Add attachment
proposed patch, testcase, etc.
Andreas Kling
Comment 1
2014-03-17 22:41:21 PDT
Created
attachment 227013
[details]
Patch
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
Created
attachment 227023
[details]
Patch
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
Committed
r165822
: <
http://trac.webkit.org/changeset/165822
>
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.
Top of Page
Format For Printing
XML
Clone This Bug