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).
Created attachment 67142 [details] Proposed fix: Use a budgeted algorithm that simplifies the code and is a slightly better trade-off
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.
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)
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!
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.
What's the next step here, Julien? Are you going to post an updated patch?
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.
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.
(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).
Comment on attachment 82888 [details] Rebased patch - Also addressed Darin's comments Nice. r=me assuming layout tests pass.
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>
All reviewed patches have been landed. Closing bug.