Bug 75083 – Indirect adjacency combinator has potential sublinear performance

• Component: CSS
• Status: RESOLVED FIXED

[Allan Sandfeld Jensen]

When evaluating a selector with multiple "indirect adjacency" combinators such as "a ~ b ~ c", the runtime of of the selector-matcher currently has sublinear performance. Two indirect adjacency combinator will for instance result in O(n^2) element checks, where n is the number of siblings. Three indirect adjacency combinators will result in O(n^3) element checks, etc.

The "indirect adjacency" combinator is very rare in the wild, so the chance of seeing two in the same selector is highly unlikely however. 

The problem can be solved similar to the same issue with multiple ancestor combinators. The recursive selector checker just needs to expanded with a result-type of SelectorFailsAllSiblings.

[Allan Sandfeld Jensen]

Created attachment 120315 [details]
Patch

[Darin Adler]

Comment on attachment 120315 [details]
Patch

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

> Source/WebCore/ChangeLog:4
> +        Fix rare superlinear runtime of the indirect adjacency combinator

The code change is fine, but it needs a test. Using the techniques from the LayoutTests/perf directory is should be straightforward to demonstrate the problem and the fix.

[Allan Sandfeld Jensen]

Created attachment 120659 [details]
New patch with performance tests

[WebKit Review Bot]

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

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'LayoutTests/ChangeLog', u'LayoutTests/perf..." exit_code: 1

LayoutTests/ChangeLog:1:  ChangeLog entry has no bug number  [changelog/bugnumber] [5]
Total errors found: 1 in 5 files


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

[Allan Sandfeld Jensen]

Created attachment 120669 [details]
Patch

[Antti Koivisto]

Comment on attachment 120669 [details]
Patch

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

r=me

> Source/WebCore/ChangeLog:7
> +        https://bugs.webkit.org/show_bug.cgi?id=75083
> +        Fix rare superlinear runtime of the indirect adjacency combinator
> +
> +        Reviewed by NOBODY (OOPS!).
> +

You should briefly explain in the ChangeLog what the superlinear case looks like and how this patch fixes it.

[Allan Sandfeld Jensen]

Created attachment 120939 [details]
Patch

Updates changelog with test and improved description

[Antti Koivisto]

Comment on attachment 120939 [details]
Patch

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

> Source/WebCore/ChangeLog:10
> [phone]  Allan Sandfeld Jensen  <[e-mail]>
> +
> +        Fix superlinear runtime of the rare case of multiple indirect adjency combinators,
> +        such as "li ~ li ~ li". The recursive matching algorithm now detects cases
> +        where all siblings have failed a check of a selector.
> +        https://bugs.webkit.org/show_bug.cgi?id=75083
> +
> +        Reviewed by NOBODY (OOPS!).
> +
> +        Test: perf/nested-combined-selectors.html

If you look around in the ChangeLog, you see that the standard format is:

Bug title
<Bugzilla URL>

Reviewed by Foo.

Brief description.

Test: for/foo.html

Please follow that.

[Allan Sandfeld Jensen]

Created attachment 120940 [details]
Patch

[Antti Koivisto]

Comment on attachment 120940 [details]
Patch

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

> LayoutTests/ChangeLog:1
> -2012-01-02  Gavin Barraclough  <[e-mail]>
> + 2011-12-28  Allan Sandfeld Jensen  <[e-mail]>

Extra space.

> LayoutTests/ChangeLog:10
> + 2012-01-02  Gavin Barraclough  <[e-mail]>

Extra space.

[Allan Sandfeld Jensen]

Created attachment 121085 [details]
Patch

One more attempt at perfect Changelog writing.

[WebKit Review Bot]

Comment on attachment 121085 [details]
Patch

Clearing flags on attachment: 121085

Committed r104133: <http://trac.webkit.org/changeset/104133>

[WebKit Review Bot]

All reviewed patches have been landed.  Closing bug.

[Nils Barth]

This bug appears to still be present.
Allan, if you're concerned about this, you might want to take a look at the revised tests.

Per revised LayoutTests/perf in Chromium, the test:
perf/nested-combined-selectors.html
...which was flaky before, is now consistently failing, and inspecting the output, as at:
http://test-results.appspot.com/dashboards/flakiness_dashboard.html#tests=%5Eperf%2Fnested-combined-selectors.html%24
...shows that it has O(n^2) performance once n >= 32 or so.
(You can download resources/magnitude-perf.js and perf/nested-combined-selectors.html from ToT Chromium and run locally to verify.)

I don't know if this is an unrealistically large size; description Allan writes:
    The "indirect adjacency" combinator is very rare in the wild,
    so the chance of seeing two in the same selector is highly unlikely however. 

I've opened a bug at Chromium regarding this:
Issue 232266: perf/nested-combined-selectors.html fails (on Linux): styling multiple combinators is O(n^2), should be O(n)
https://code.google.com/p/chromium/issues/detail?id=232266