Bug 107111

Summary: CSS: Make tag sub-selectors standalone CSSSelectors.
Product: WebKit Reporter: Andreas Kling <kling>
Component: CSSAssignee: Andreas Kling <kling>
Status: RESOLVED FIXED    
Severity: Normal CC: allan.jensen, buildbot, cmarcelo, dglazkov, koivisto, macpherson, menard, ojan.autocc, rniwa, webcomponents-bugzilla, webkit-bug-importer, webkit-ews, webkit.review.bot
Priority: P2 Keywords: InRadar, Performance
Version: 528+ (Nightly build)   
Hardware: Unspecified   
OS: Unspecified   
Attachments:
Description Flags
WIP patch (Unrated Director's Cut)
webkit-ews: commit-queue-
ews pls
buildbot: commit-queue-
Half-decent WIP
buildbot: commit-queue-
Will it blend?
webkit.review.bot: commit-queue-
A man can dream...
eflews.bot: commit-queue-
With most optimizations intact now..
eflews.bot: commit-queue-
Proposed patch
koivisto: review+, eflews.bot: commit-queue-
Patch for landing none

Description Andreas Kling 2013-01-17 03:45:32 PST
We currently store a QualifiedName in every CSSSelector, a very wasteful practice (~12MB worth of CSSSelectors on Membuster3.)

It should really only be needed when the selector has a tag name or we're in a non-default CSS namespace.
Furthermore, only the first CSSSelector in a subselector chain needs to have the QualifiedName, so we could unionize it with value/raredata.

Awesome memory savings potential here.
Comment 1 Andreas Kling 2013-01-17 03:54:12 PST
Created attachment 183158 [details]
WIP patch (Unrated Director's Cut)
Comment 2 WebKit Review Bot 2013-01-17 03:56:57 PST
Attachment 183158 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/WebCore/css/CSSGrammar.y.in', u'Sou..." exit_code: 1
Source/WebCore/css/CSSParser.cpp:10958:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
Source/WebCore/css/CSSSelector.cpp:557:  Boolean expressions that span multiple lines should have their operators on the left side of the line instead of the right side.  [whitespace/operators] [4]
Total errors found: 2 in 14 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 3 Early Warning System Bot 2013-01-17 03:59:03 PST
Comment on attachment 183158 [details]
WIP patch (Unrated Director's Cut)

Attachment 183158 [details] did not pass qt-ews (qt):
Output: http://queues.webkit.org/results/15940025
Comment 4 Early Warning System Bot 2013-01-17 04:00:14 PST
Comment on attachment 183158 [details]
WIP patch (Unrated Director's Cut)

Attachment 183158 [details] did not pass qt-wk2-ews (qt):
Output: http://queues.webkit.org/results/15907778
Comment 5 EFL EWS Bot 2013-01-17 04:02:31 PST
Comment on attachment 183158 [details]
WIP patch (Unrated Director's Cut)

Attachment 183158 [details] did not pass efl-ews (efl):
Output: http://queues.webkit.org/results/15907780
Comment 6 WebKit Review Bot 2013-01-17 04:02:48 PST
Comment on attachment 183158 [details]
WIP patch (Unrated Director's Cut)

Attachment 183158 [details] did not pass chromium-ews (chromium-xvfb):
Output: http://queues.webkit.org/results/15937058
Comment 7 Andreas Kling 2013-01-17 04:07:13 PST
Created attachment 183159 [details]
ews pls
Comment 8 WebKit Review Bot 2013-01-17 04:11:40 PST
Attachment 183159 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/WebCore/css/CSSGrammar.y.in', u'Sou..." exit_code: 1
Source/WebCore/css/CSSSelector.cpp:558:  Boolean expressions that span multiple lines should have their operators on the left side of the line instead of the right side.  [whitespace/operators] [4]
Total errors found: 1 in 14 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 9 Build Bot 2013-01-17 04:37:28 PST
Comment on attachment 183159 [details]
ews pls

Attachment 183159 [details] did not pass win-ews (win):
Output: http://queues.webkit.org/results/15903962
Comment 10 WebKit Review Bot 2013-01-17 05:39:30 PST
Comment on attachment 183159 [details]
ews pls

Attachment 183159 [details] did not pass chromium-ews (chromium-xvfb):
Output: http://queues.webkit.org/results/15914822

New failing tests:
compositing/iframes/overlapped-nested-iframes.html
css3/selectors3/xml/css3-modsel-24.xml
editing/input/caret-at-the-edge-of-input.html
css3/selectors3/xhtml/css3-modsel-24.xml
http/tests/misc/location-replace-crossdomain.html
editing/execCommand/find-after-replace.html
compositing/iframes/overlapped-iframe-iframe.html
css3/selectors3/html/css3-modsel-24.html
http/tests/loading/simple-subframe.html
compositing/geometry/fixed-position-iframe-composited-page-scale.html
http/tests/local/file-url-sent-as-referer.html
editing/execCommand/paste-1.html
css3/selectors3/xml/css3-modsel-23.xml
editing/selection/3690703-2.html
css3/selectors3/xhtml/css3-modsel-69.xml
compositing/iframes/iframe-copy-on-scroll.html
editing/execCommand/paste-2.html
compositing/iframes/become-composited-nested-iframes.html
css3/selectors3/xml/css3-modsel-69.xml
http/tests/misc/iframe404.html
editing/inserting/before-after-input-element.html
compositing/geometry/fixed-position-iframe-composited-page-scale-down.html
css3/selectors3/html/css3-modsel-23.html
css3/selectors3/xml/css3-modsel-68.xml
css3/selectors3/html/css3-modsel-69.html
compositing/iframes/resizer.html
editing/selection/3690703.html
css3/selectors3/xhtml/css3-modsel-68.xml
css3/selectors3/xhtml/css3-modsel-23.xml
css3/selectors3/html/css3-modsel-68.html
Comment 11 Dimitri Glazkov (Google) 2013-01-17 09:05:52 PST
Comment on attachment 183159 [details]
ews pls

This is neat. Any perf implications?
Comment 12 Build Bot 2013-01-17 10:45:58 PST
Comment on attachment 183159 [details]
ews pls

Attachment 183159 [details] did not pass mac-ews (mac):
Output: http://queues.webkit.org/results/15925661

New failing tests:
fast/frames/flattening/iframe-flattening-out-of-view-and-scroll.html
fast/frames/flattening/iframe-flattening-fixed-width-and-height-no-scrolling.html
editing/execCommand/paste-2.html
fast/dom/gc-10.html
editing/execCommand/find-after-replace.html
fast/frames/frameElement-iframe.html
compositing/iframes/overlapped-iframe-iframe.html
editing/selection/4776665.html
http/tests/loading/simple-subframe.html
fast/dom/Window/open-existing-pop-up-blocking.html
fast/frames/flattening/iframe-flattening-fixed-width.html
compositing/visible-rect/iframe-and-layers.html
editing/pasteboard/drag-image-to-contenteditable-in-iframe.html
fast/dom/attr_dead_doc.html
http/tests/local/file-url-sent-as-referer.html
fast/frames/flattening/iframe-flattening-out-of-view-scroll-and-relayout.html
editing/execCommand/paste-1.html
fast/frames/content-opacity-2.html
editing/pasteboard/subframe-dragndrop-1.html
fast/block/basic/013.html
editing/selection/4975120.html
compositing/iframes/iframe-copy-on-scroll.html
fast/frames/content-opacity-1.html
fast/frames/flattening/iframe-flattening-fixed-width-and-height.html
compositing/iframes/become-composited-nested-iframes.html
fast/block/positioning/window-height-change.html
fast/frames/flattening/iframe-flattening-simple.html
fast/frames/iframe-option-crash.xhtml
editing/selection/4960137.html
compositing/iframes/resizer.html
Comment 13 Andreas Kling 2013-01-17 13:14:52 PST
(In reply to comment #11)
> (From update of attachment 183159 [details])
> This is neat. Any perf implications?

I believe that this will mean less total work in the end, since it allows us to skip tag-related checks for everything but CSSSelector::Tag subselectors. It's also possible that improved locality from shrinking CSSSelector by a pointer will help performance.
Comment 14 Dimitri Glazkov (Google) 2013-01-17 14:22:29 PST
(In reply to comment #13)

> I believe that this will mean less total work in the end, since it allows us to skip tag-related checks for everything but CSSSelector::Tag subselectors. It's also possible that improved locality from shrinking CSSSelector by a pointer will help performance.

Cool!
Comment 15 Andreas Kling 2013-01-17 17:37:22 PST
Created attachment 183328 [details]
Half-decent WIP

Working pretty well now, let's see what EWS thinks.
Comment 16 WebKit Review Bot 2013-01-17 17:41:27 PST
Attachment 183328 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/WebCore/css/CSSGrammar.y.in', u'Sou..." exit_code: 1
Source/WebCore/css/CSSSelector.cpp:558:  Boolean expressions that span multiple lines should have their operators on the left side of the line instead of the right side.  [whitespace/operators] [4]
Total errors found: 1 in 16 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 17 Build Bot 2013-01-17 18:47:56 PST
Comment on attachment 183328 [details]
Half-decent WIP

Attachment 183328 [details] did not pass mac-wk2-ews (mac-wk2):
Output: http://queues.webkit.org/results/15937456

New failing tests:
inspector/styles/force-pseudo-state.html
Comment 18 Andreas Kling 2013-01-17 19:55:19 PST
Before/after Membuster3 results for last WIP:

268696 blocks ( 7%), 13867 KB ( 2%),  0.05 KB/calls -- CSSSelector
210851 blocks ( 6%),  8981 KB ( 1%),  0.04 KB/calls -- CSSSelector

So 4886 KB saved, a ~35% reduction in CSSSelector memory use overall. Non-shabby.
Comment 19 Build Bot 2013-01-17 20:00:37 PST
Comment on attachment 183328 [details]
Half-decent WIP

Attachment 183328 [details] did not pass mac-ews (mac):
Output: http://queues.webkit.org/results/15942315

New failing tests:
inspector/styles/force-pseudo-state.html
Comment 20 Build Bot 2013-01-17 20:56:20 PST
Comment on attachment 183328 [details]
Half-decent WIP

Attachment 183328 [details] did not pass mac-ews (mac):
Output: http://queues.webkit.org/results/15949135

New failing tests:
inspector/styles/force-pseudo-state.html
Comment 21 WebKit Review Bot 2013-01-17 22:46:37 PST
Comment on attachment 183328 [details]
Half-decent WIP

Attachment 183328 [details] did not pass chromium-ews (chromium-xvfb):
Output: http://queues.webkit.org/results/15940503

New failing tests:
fast/dom/shadow/pseudoclass-update-target.html
fast/dom/shadow/pseudoclass-update-indeterminate-progress.html
fast/dom/shadow/reprojection-attribute-modified.html
inspector/styles/force-pseudo-state.html
fast/dom/shadow/distribution-attribute-modified.html
fast/dom/shadow/pseudoclass-update-indeterminate-input.html
fast/dom/shadow/pseudoclass-update-link-area.html
fast/dom/shadow/pseudoclass-update-checked-input.html
fast/dom/shadow/pseudoclass-update-visited-area.html
fast/dom/shadow/pseudoclass-update-checked-option.html
fast/dom/shadow/shadow-contents-select.html
fast/dom/shadow/shadow-select-attribute-featureset.html
Comment 22 Radar WebKit Bug Importer 2013-01-18 13:19:59 PST
<rdar://problem/13044714>
Comment 23 Andreas Kling 2013-01-18 20:24:30 PST
Created attachment 183596 [details]
Will it blend?
Comment 24 WebKit Review Bot 2013-01-18 21:36:08 PST
Comment on attachment 183596 [details]
Will it blend?

Attachment 183596 [details] did not pass chromium-ews (chromium-xvfb):
Output: http://queues.webkit.org/results/15966020

New failing tests:
media/track/track-css-matching.html
Comment 25 EFL EWS Bot 2013-01-18 22:54:26 PST
Comment on attachment 183596 [details]
Will it blend?

Attachment 183596 [details] did not pass efl-ews (efl):
Output: http://queues.webkit.org/results/15975070
Comment 26 Antti Koivisto 2013-01-19 04:37:03 PST
Comment on attachment 183596 [details]
Will it blend?

View in context: https://bugs.webkit.org/attachment.cgi?id=183596&action=review

Looking great.

> Source/WebCore/css/RuleSet.cpp:243
> -    const AtomicString& localName = selector->tag().localName();
> -    if (localName != starAtom) {
> -        addToRuleSet(localName.impl(), m_tagRules, ruleData);
> -        return;
> +    if (selector->m_match == CSSSelector::Tag) {
> +        if (selector->tagQName().localName() != starAtom) {
> +            addToRuleSet(selector->tagQName().localName().impl(), m_tagRules, ruleData);
> +            return;
> +        }
>      }

The main concern is that this will make RuleSet hashes less efficient since we currently look into the first selector part only. Selector div.foo currently goes to the classRules bucket. With this I think it will go to the tagRules bucket and ends up being unnecessarily tested for way more rules.

I think it is ok to land with this likely regression but this should be fixed soonish too. The code here should look into all subselectors to figure out the best bucket (or some other more sophisticated current-element optimization should be implemented).

> Source/WebCore/html/shadow/ContentDistributor.cpp:408
>      if (ScopeContentDistribution::hasContentElement(root)) {
>          for (Element* element = ElementTraversal::firstWithin(root); element; element = ElementTraversal::next(element)) {
> -            if (isHTMLContentElement(element)) {
> -                const CSSSelectorList& list = toHTMLContentElement(element)->selectorList();
> -                for (CSSSelector* selector = list.first(); selector; selector = list.next(selector))
> -                    m_selectFeatures.collectFeaturesFromSelector(selector);
> +            if (!isHTMLContentElement(element))
> +                continue;
> +            const CSSSelectorList& list = toHTMLContentElement(element)->selectorList();
> +            for (CSSSelector* selector = list.first(); selector; selector = CSSSelectorList::next(selector)) {
> +                for (CSSSelector* selectorComponent = selector; selectorComponent; selectorComponent = selectorComponent->tagHistory())
> +                    m_selectFeatures.collectFeaturesFromSelector(selectorComponent);

There shouldn't be code like this outside StyleResolver/SelectorChecker :(
Comment 27 Antti Koivisto 2013-01-19 05:32:55 PST
(In reply to comment #26)
>  With this I think it will go to the tagRules bucket and ends up being unnecessarily tested for way more rules.

I mean "for way more elements".
Comment 28 Andreas Kling 2013-01-20 00:01:54 PST
Created attachment 183659 [details]
A man can dream...
Comment 29 WebKit Review Bot 2013-01-20 00:04:59 PST
Attachment 183659 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/WebCore/ChangeLog', u'Source/WebCor..." exit_code: 1
Source/WebCore/css/CSSParserValues.cpp:229:  One line control clauses should not use braces.  [whitespace/braces] [4]
Total errors found: 1 in 19 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 30 EFL EWS Bot 2013-01-20 00:32:50 PST
Comment on attachment 183659 [details]
A man can dream...

Attachment 183659 [details] did not pass efl-ews (efl):
Output: http://queues.webkit.org/results/15973530
Comment 31 Andreas Kling 2013-01-21 01:49:45 PST
Created attachment 183734 [details]
With most optimizations intact now..
Comment 32 EFL EWS Bot 2013-01-21 02:48:51 PST
Comment on attachment 183734 [details]
With most optimizations intact now..

Attachment 183734 [details] did not pass efl-ews (efl):
Output: http://queues.webkit.org/results/15979966
Comment 33 Andreas Kling 2013-01-21 04:00:03 PST
Created attachment 183757 [details]
Proposed patch

Okay, this should be ready for review. Fingers x'ed.
Comment 34 Antti Koivisto 2013-01-21 04:17:54 PST
Comment on attachment 183757 [details]
Proposed patch

View in context: https://bugs.webkit.org/attachment.cgi?id=183757&action=review

r=me, very nice

> Source/WebCore/css/CSSSelector.h:247
> +        bool m_isNamespacePlaceholder : 1;

It is not really a "placeholder" since it is functionally important. Maybe m_isTagForNamespaceRule or something?

> Source/WebCore/css/RuleSet.cpp:262
> +    if (component->m_match == CSSSelector::Tag) {
> +        if (component->tagQName().localName() != starAtom) {
> +            // If this is part of a subselector chain, recurse ahead to find a narrower set (ID/class.)
> +            if (component->relation() == CSSSelector::SubSelector
> +                && (component->tagHistory()->m_match == CSSSelector::Class || component->tagHistory()->m_match == CSSSelector::Id || SelectorChecker::isCommonPseudoClassSelector(component->tagHistory()))
> +                && findBestRuleSetAndAdd(component->tagHistory(), ruleData))
> +                return true;
> +
> +            addToRuleSet(component->tagQName().localName().impl(), m_tagRules, ruleData);
> +            return true;
> +        }
> +    }

This is enough to avoid regression but we can do better later.
Comment 35 EFL EWS Bot 2013-01-21 06:21:05 PST
Comment on attachment 183757 [details]
Proposed patch

Attachment 183757 [details] did not pass efl-ews (efl):
Output: http://queues.webkit.org/results/16033102
Comment 36 Andreas Kling 2013-01-21 16:18:29 PST
Created attachment 183850 [details]
Patch for landing
Comment 37 WebKit Review Bot 2013-01-21 16:46:43 PST
Comment on attachment 183850 [details]
Patch for landing

Clearing flags on attachment: 183850

Committed r140371: <http://trac.webkit.org/changeset/140371>
Comment 38 WebKit Review Bot 2013-01-21 16:46:49 PST
All reviewed patches have been landed.  Closing bug.