Bug 45507 – Improve the local{SharedStyle,CousinList} algorithm

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

[Julien Chaffraix]

Currently the algorithm in the CSSStyleSelector to look for cousins iterates twice to avoid a bad runtime complexity. This is arbitrary and will miss some cousin.

The idea is to change this algorithm to one that guarantees a number of visited nodes while limiting the exponential complexity (locateCousin is called in a for loop and calls itself recursively).

[Julien Chaffraix]

Created attachment 67142 [details]
Proposed fix: Use a budgeted algorithm that simplifies the code and is a slightly better trade-off

[WebKit Review Bot]

Attachment 67142 [details] did not pass style-queue:

Failed to run "['WebKitTools/Scripts/check-webkit-style']" exit_code: 1
WebCore/css/CSSStyleSelector.cpp:965:  Extra space before ) in if  [whitespace/parens] [5]
WebCore/css/CSSStyleSelector.cpp:966:  This { should be at the end of the previous line  [whitespace/braces] [4]
WebCore/css/CSSStyleSelector.cpp:975:  Extra space before last semicolon. If this should be an empty statement, use { } instead.  [whitespace/semicolon] [5]
Total errors found: 3 in 3 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Julien Chaffraix]

Created attachment 67282 [details]
Proposed fix: Use a budgeted algorithm that simplifies the code and is a slightly better trade-off (without the style issues)

[Dave Hyatt]

Comment on attachment 67282 [details]
Proposed fix: Use a budgeted algorithm that simplifies the code and is a slightly better trade-off (without the style issues)

I like it!

[Darin Adler]

Comment on attachment 67282 [details]
Proposed fix: Use a budgeted algorithm that simplifies the code and is a slightly better trade-off (without the style issues)

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

> WebCore/css/CSSStyleSelector.cpp:949
> +Node* CSSStyleSelector::locateCousinList(Element* parent, unsigned &visitedNodesCount)

The "&" goes next to the type rather than next to the variable name.

> WebCore/css/CSSStyleSelector.cpp:951
> +    if (visitedNodesCount >= (cStyleSearchThreshold * cStyleSearchLevelThreshold))

The parentheses here are not helpful. Please remove them.

> WebCore/css/CSSStyleSelector.cpp:1076
> +    unsigned visitedNodesCount = 0;

The phrase “visited nodes count” is not good grammar, but “visited node count” would be.

> WebCore/css/CSSStyleSelector.cpp:1079
> +    // FIXME: We should use the ElementTraversal API instead of this for-loop but we need to test the performance implication of this change.

I’m glad that you would test performance before making the change, but I don’t agree with the FIXME. Just because element traversal is a public DOM API doesn’t mean it’s a good idea to use it inside the engine. With both previousSibling and isElementNode implemented as efficient inline functions, it’s almost certainly better to call code that can do this inline. If you’d like to come back here and deploy some kind of fast implementation of element traversal, that’s OK, but I do not think it deserves a FIXME comment.

> WebCore/css/CSSStyleSelector.h:113
> +        Node* locateCousinList(Element* parent, unsigned &visitedNodes);

Please move the & next to the type.

The name visitedNodes is not good. This variable does not hold nodes, so it should not be named “visited nodes”. I think visitedNodeCount is an acceptable name.

[Eric Seidel (no email)]

What's the next step here, Julien?  Are you going to post an updated patch?

[Julien Chaffraix]

Created attachment 82888 [details]
Rebased patch - Also addressed Darin's comments

Finally got around to update this patch. Re-applied the logic on top of ToT.

[Antti Koivisto]

Looks good. Did you measure performance? I would be interested in hearing the sharing percentage on some major web sites with this vs. the old code. It should be easy to find out with some debugging code thrown in.

[Julien Chaffraix]

(In reply to comment #8)
> Looks good. Did you measure performance? I would be interested in hearing the sharing percentage on some major web sites with this vs. the old code. It should be easy to find out with some debugging code thrown in.

We did some sharing measurements on major websites. Most websites were showing small benefits (less than 5%) but on at least 2 (amazon & rakuten.co.jp) we found out that much sharing was missed by the current algorithm. In those 2 cases, the new algorithm would improve the sharing by resp. 33% (amazon) and 16% (rakuten).

[Antti Koivisto]

Comment on attachment 82888 [details]
Rebased patch - Also addressed Darin's comments

Nice. r=me assuming layout tests pass.

[WebKit Commit Bot]

Comment on attachment 82888 [details]
Rebased patch - Also addressed Darin's comments

Clearing flags on attachment: 82888

Committed r79293: <http://trac.webkit.org/changeset/79293>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.