Bug 135255 – Merge CheckingContexts from SelectorCompiler and SelectorChecker

• Status: RESOLVED
• Resolution: FIXED
• Component: CSS

[Alex Christensen]

Eventually SelectorCompiler::CheckingContext and SelectorChecker::SelectorCheckingContext should be made the same class.  

m_mode should be moved from SelectorChecker to SelectorChecker::SelectorCheckingContext because the compiled selectors need it, too.  
m_element should probably be moved from SelectorChecker::SelectorCheckingContext to SelectorChecker because the compiled selectors probably don't need it.
There might be some other things that need to move around as we compile all selectors.

[Yusuke Suzuki]

This looks really nice!
I think we can remove SelectorChecker::CheckingContext third parameter, visitedMatchType. Only when the mode is QueryingRules, we pass VisitedMatchDisabled value to this constructor.
When mode is moved to this CheckingContext, we can determine this value by `mode == QueryingRules ? VisitedMatchDisabled : VisitedMatchEnabled`!

[Yusuke Suzuki]

Created attachment 237413 [details]
Patch

[Yusuke Suzuki]

Created attachment 237414 [details]
Patch

[Yusuke Suzuki]

Created attachment 237415 [details]
Patch

[Yusuke Suzuki]

Created attachment 237416 [details]
Patch

[Yusuke Suzuki]

Comment on attachment 237416 [details]
Patch

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

Added comments.

> Source/WebCore/css/ElementRuleCollector.cpp:312
> +    context.scrollbarPart = m_pseudoStyleRequest.scrollbarPart;

Merged. So we simply use SelectorChecker::CheckingContext for slow path and CSS JIT.

> Source/WebCore/css/SelectorChecker.cpp:63
> +};

Moved into SelectorChecker.cpp!

> Source/WebCore/css/SelectorChecker.cpp:85
> +};

Defined SelectorChecker::CheckingContextWithStatus. It is extended CheckingContext with SelectorChecker specific fields.

> Source/WebCore/css/SelectorChecker.cpp:163
> +bool SelectorChecker::match(const CSSSelector* selector, Element* element, const CheckingContext& providedContext) const

Take selector and element. It is similar to CSS JIT checker interface.

> Source/WebCore/css/SelectorChecker.cpp:165
> +    CheckingContextWithStatus context(providedContext, selector, element);

Then update provided SelectorChecker::CheckingContext to SelectorChecker::CheckingContextWithStatus.

> Source/WebCore/css/SelectorChecker.h:-49
> -    enum VisitedMatchType { VisitedMatchDisabled, VisitedMatchEnabled };

Hidden!

> Source/WebCore/css/SelectorChecker.h:55
> +    struct CheckingContext {

Moved from SelectorCompiler::CheckingContext to here.

> Source/WebCore/css/SelectorChecker.h:89
> +    bool checkScrollbarPseudoClass(const CheckingContextWithStatus&, const CSSSelector*) const;

Internally, use CheckingContextWithStatus.

> Source/WebCore/css/SelectorCheckerTestFunctions.h:171
> +

ContextType is now unnecessary since CheckingContexts are merged.

> Source/WebCore/css/SelectorQueryFastPath.h:42
> +    bool matchesRightmostSelector() const;

Now don't take visitedMatchType parameter since visited match type is always disabled under the SelectorQuery context.

> Source/WebCore/css/SelectorQueryFastPath.h:47
> +    bool commonPseudoClassSelectorMatches() const;

matchesRightmostAttributeSelector is dropped since it is no longer used.

[Benjamin Poulain]

Comment on attachment 237416 [details]
Patch

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

Sorry for the delay, I was finishing on some style invalidation bug.

The patch is a good improvement of the code base.

You can remove SelectorQueryFastPath instead of cleaning it up. SelectorQueryFastPath was invented by Antti to solve the performance problems before we had the CSS JIT. Nowadays it is no longer useful, the JIT is a lot faster.

> Source/WebCore/ChangeLog:4
> +        Merge CheckingContexts from SelectorCompiler and SelectorChecker
> +        https://bugs.webkit.org/show_bug.cgi?id=135255

You have 2 changeslog entries.

> Source/WebCore/CMakeLists.txt:1306
> -    css/SelectorCheckerFastPath.cpp
>      css/SelectorFilter.cpp
> +    css/SelectorQueryFastPath.cpp

You don't need to bother with SelectorCheckerFastPath. We should remove it, I just haven't had time to clean up SelectorQuery.

[Yusuke Suzuki]

Comment on attachment 237416 [details]
Patch

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

Thank you for your review! OK, so I'll drop fast path implementation and upload the revised patch :)

>> Source/WebCore/ChangeLog:4
>> +        https://bugs.webkit.org/show_bug.cgi?id=135255
> 
> You have 2 changeslog entries.

Oops! Thank you for pointing it :D

>> Source/WebCore/CMakeLists.txt:1306
>> +    css/SelectorQueryFastPath.cpp
> 
> You don't need to bother with SelectorCheckerFastPath. We should remove it, I just haven't had time to clean up SelectorQuery.

Make sense. So I'll remove it and clean up SelectorQuery implementation.

[Yusuke Suzuki]

Created attachment 237852 [details]
Patch

[Yusuke Suzuki]

Comment on attachment 237852 [details]
Patch

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

Sorry for my further late reply.

> Source/WebCore/dom/SelectorQuery.cpp:-117
> -    if (selectorData.isFastCheckable && !element.isSVGElement()) {

SelectorCheckerFastPath is dropped.

> Source/WebCore/dom/SelectorQuery.cpp:421
>          }

In the old and new implementations, when `RightMostWithIdMatch` is used, basically `selectorMatches` is called and CSS Selector JIT is not used.

In the SelectorQuery implementation, in the some cases, CSS JIT is not used. Such as `RightMostWithIdMatch` case, and multiple selector case (`document.querySelector('a, b')`).
In the `RightMostWithIdMatch` case, the searched node basically becomes one (matched by id). So compiling CSS Selector may affect the performance.
In the multiple selector case, it also incurs larger CSS JIT compiling overhead compared to the typical one.

But, since the fast path is dropped, it sometimes raises the perf regression on `RightMostWithIdMatch`(But since the target node is typically only one, so it may not have any perf regression.).

My questions are,
1. Is the old behavior intended? (not performing CSS JIT in the case of `RightMostWithIdMatch`, multiple selectors and `Element.matches`)
2. Is it acceptable dropping the fast path from selectorMatches? It may raise perf regression on non CSS JIT cases (such as (1))

Do you think about this?

In this patch, I've simply dropped the fast path.

[Benjamin Poulain]

Comment on attachment 237852 [details]
Patch

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

> Source/WebCore/ChangeLog:17
> +        always VisitedMatchDisabled. In this patch, we rename SelectorCheckerFastPath to SelectorQueryFastPath, and
> +        drop VisitedMatchType parameter.

The part regarding SelectorCheckerFastPath needs to be updated.

> Source/WebCore/css/SelectorChecker.cpp:66
> +    // Initial selector constructor

No need for the comment.

[Yusuke Suzuki]

Oops. I've Ctrl-C on `webkit-patch land`. So closing this manually.
http://trac.webkit.org/changeset/173457

[Benjamin Poulain]

It looks like the regression for comma separated selectors is bigger than anticipated: https://perf.webkit.org/#mode=charts&chartList=%5B%5B%22mac-mavericks%22%2C%22Dromaeo%2Fcssquery-jquery%3ARuns%22%5D%5D&days=6&zoom=%5B1410108072682.0085%2C1410415670537.5554%5D

I'll look into it tomorrow.

[Yusuke Suzuki]

(In reply to comment #13)
> It looks like the regression for comma separated selectors is bigger than anticipated: https://perf.webkit.org/#mode=charts&chartList=%5B%5B%22mac-mavericks%22%2C%22Dromaeo%2Fcssquery-jquery%3ARuns%22%5D%5D&days=6&zoom=%5B1410108072682.0085%2C1410415670537.5554%5D
> 
> I'll look into it tomorrow.

Oops! Thank you for your catch!
Do you think about implementing CSS JIT for multiple selectors?
It will be refactored and reused for :matches implementation, and compared to :matches, it seems more stable.
If it's OK, I'll start to implement it.

[Benjamin Poulain]

(In reply to comment #14)
> (In reply to comment #13)
> > It looks like the regression for comma separated selectors is bigger than anticipated: https://perf.webkit.org/#mode=charts&chartList=%5B%5B%22mac-mavericks%22%2C%22Dromaeo%2Fcssquery-jquery%3ARuns%22%5D%5D&days=6&zoom=%5B1410108072682.0085%2C1410415670537.5554%5D
> > 
> > I'll look into it tomorrow.
> 
> Oops! Thank you for your catch!
> Do you think about implementing CSS JIT for multiple selectors?
> It will be refactored and reused for :matches implementation, and compared to :matches, it seems more stable.
> If it's OK, I'll start to implement it.

Long term we should use :matches() but it will take a while before we have it complete. The complete :matches() is pretty tricky: multilevel backtracking, multiple pseudo element matching and :visited/:link. With all the tests this will require, it is gonna be a lot of work.

Short term for this regression we should:
1) Profile this benchmark to confirm the regression is caused by SelectorChecker.
2) If (2) is right, just compile everything that can be compiled and run a loop mixing CSS JIT and slow Selector checker.

For (2), I am thinking something like:
    // ... try to compile every selector.
    if (allSelectorsCompiled) {
        // Traversal checking each compiled selector for every element.
    } else {
        // Slow case like we do today.
    }

Once :matches() is ready and release quality, we'll remove the hack.

What do you think?

[Yusuke Suzuki]

(In reply to comment #15)
> (In reply to comment #14)
> > (In reply to comment #13)
> > > It looks like the regression for comma separated selectors is bigger than anticipated: https://perf.webkit.org/#mode=charts&chartList=%5B%5B%22mac-mavericks%22%2C%22Dromaeo%2Fcssquery-jquery%3ARuns%22%5D%5D&days=6&zoom=%5B1410108072682.0085%2C1410415670537.5554%5D
> > > 
> > > I'll look into it tomorrow.
> > 
> > Oops! Thank you for your catch!
> > Do you think about implementing CSS JIT for multiple selectors?
> > It will be refactored and reused for :matches implementation, and compared to :matches, it seems more stable.
> > If it's OK, I'll start to implement it.
> 
> Long term we should use :matches() but it will take a while before we have it complete. The complete :matches() is pretty tricky: multilevel backtracking, multiple pseudo element matching and :visited/:link. With all the tests this will require, it is gonna be a lot of work.
> 
> Short term for this regression we should:
> 1) Profile this benchmark to confirm the regression is caused by SelectorChecker.
> 2) If (2) is right, just compile everything that can be compiled and run a loop mixing CSS JIT and slow Selector checker.
> 
> For (2), I am thinking something like:
>     // ... try to compile every selector.
>     if (allSelectorsCompiled) {
>         // Traversal checking each compiled selector for every element.
>     } else {
>         // Slow case like we do today.
>     }
> 
> Once :matches() is ready and release quality, we'll remove the hack.
> 
> What do you think?

It sounds reasonable.
I'll take a profile too. Now running `Tools/Scripts/run-perf-tests --release Dromaeo/cssquery-jquery.html`

[Yusuke Suzuki]

Created attachment 238029 [details]
Trunk Perf Results

[Yusuke Suzuki]

Created attachment 238030 [details]
Perf Results with reverting this patch

[Yusuke Suzuki]

I've measured the performance with `Tools/Scripts/run-perf-tests --release Dromaeo/cssquery-jquery.html`, and I've found that actually performance regressions occur in the multiple selectors cases.

Attached perf test results. In this results, 

`div, a, span`: 6999.94/s => 3623.90/s
`div, div, div`: 8511.85/s => 3895.40/s
`div.character, div.dialog`: 11.53k/s => 5343.20/s

results significantly become worse. In the other results, there's no observable performance regression.

[Yusuke Suzuki]

Created attachment 238039 [details]
JIT Compiled version

[Benjamin Poulain]

(In reply to comment #20)
> Created an attachment (id=238039) [details]
> JIT Compiled version

Wow, that's awesome

[Yusuke Suzuki]

Reopening to attach new patch.

[Yusuke Suzuki]

Created attachment 238040 [details]
Patch

[Yusuke Suzuki]

(In reply to comment #21)
> (In reply to comment #20)
> > Created an attachment (id=238039) [details] [details]
> > JIT Compiled version
> 
> Wow, that's awesome

Yeah, I'm surprised at such a great performance gain by applying JIT to multiple selectors!
Benchmarks are very very helpful for optimizing the existing software stacks.
Thank you for your great catch and https://perf.webkit.org/!

I need to monitor https://perf.webkit.org/ :)
And need to run run-perf-tests, it's great!!

[Benjamin Poulain]

Comment on attachment 238040 [details]
Patch

Quick review because I am on the go, but everything looks right.

[Benjamin Poulain]

Created attachment 238060 [details]
Patch

[WebKit Commit Bot]

Comment on attachment 238060 [details]
Patch

Clearing flags on attachment: 238060

Committed r173590: <http://trac.webkit.org/changeset/173590>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.

[Benjamin Poulain]

The problem is over, you got all the performance back...and then some: https://perf.webkit.org/#mode=charts&chartList=%5B%5B%22mac-mavericks%22%2C%22Dromaeo%2Fcssquery-jquery%3ARuns%22%5D%2C%5B%22mac-mavericks%22%2C%22Dromaeo%2Fcssquery-dojo%3ARuns%22%5D%2C%5B%22mac-mavericks%22%2C%22CSS%2FQuerySelector%3ATime%22%5D%5D&days=25

[Yusuke Suzuki]

(In reply to comment #29)
> The problem is over, you got all the performance back...and then some: https://perf.webkit.org/#mode=charts&chartList=%5B%5B%22mac-mavericks%22%2C%22Dromaeo%2Fcssquery-jquery%3ARuns%22%5D%2C%5B%22mac-mavericks%22%2C%22Dromaeo%2Fcssquery-dojo%3ARuns%22%5D%2C%5B%22mac-mavericks%22%2C%22CSS%2FQuerySelector%3ATime%22%5D%5D&days=25

Oh! very nice performance :)