Bug 234842 - [:has() pseudo-class] Avoid O(n^2) in style invalidation with repeated DOM mutations
Summary: [:has() pseudo-class] Avoid O(n^2) in style invalidation with repeated DOM mu...
Alias: None
Product: WebKit
Classification: Unclassified
Component: CSS (show other bugs)
Version: WebKit Nightly Build
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Antti Koivisto
Keywords: InRadar
Depends on:
Blocks: 227702
  Show dependency treegraph
Reported: 2022-01-04 07:27 PST by Antti Koivisto
Modified: 2022-01-14 09:33 PST (History)
15 users (show)

See Also:

Patch (14.27 KB, patch)
2022-01-04 07:57 PST, Antti Koivisto
no flags Details | Formatted Diff | Diff
Patch (14.31 KB, patch)
2022-01-13 06:07 PST, Antti Koivisto
no flags Details | Formatted Diff | Diff
Patch for landing (16.36 KB, patch)
2022-01-14 02:05 PST, Antti Koivisto
no flags Details | Formatted Diff | Diff
Patch (15.49 KB, patch)
2022-01-14 02:18 PST, Antti Koivisto
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Antti Koivisto 2022-01-04 07:27:50 PST
Even without :has() it is possible to have cases where the cost of doing accurate style invalidation exceeds the benefits. With :has() these cases become easier to hit. Add a backdown mechanism where we detect this and switch to eager invalidation.
Comment 1 Antti Koivisto 2022-01-04 07:57:33 PST
Created attachment 448298 [details]
Comment 2 Antti Koivisto 2022-01-04 07:57:53 PST
Submitted web-platform-tests pull request: https://github.com/web-platform-tests/wpt/pull/32240
Comment 3 EWS Watchlist 2022-01-04 07:58:32 PST
This patch modifies the imported WPT tests. Please ensure that any changes on the tests (not coming from a WPT import) are exported to WPT. Please see https://trac.webkit.org/wiki/WPTExportProcess
Comment 4 Darin Adler 2022-01-04 23:19:27 PST
It seems both clever to do this, but also makes me wish we had some other definition of "too expensive" other than using ApproximateTime. Will this be OK from an automated testing point of view?

Seems like we could have different test results on different speed computers, and other such things, whereas some other definition of complexity (counting something, perhaps) would give us more reproducible results, that could have the same effect.
Comment 5 Darin Adler 2022-01-04 23:22:07 PST
Another way to think about it is that if we stick with the ApproximateTime strategy, as computers get faster and faster, WebKit becomes more and more willing to waste up to 64ms doing even more accurate style invalidation that it did on the previous generation, but it still doesn’t have enough benefit to be worth it.

Maybe not a practical problem?
Comment 6 Antti Koivisto 2022-01-05 03:34:49 PST
I like the use of time measurement since it actually gives a highly relevant definition for "expensive". The style system is complex enough that "count number of times something happens" approaches are difficult to make capture all scenarios.

This is really meant to protect against pathological cases, the current 64ms limit is difficult to hit unless you are specifically trying. This probably won't affect any tests normal tests.

I think we need a counter in addition to the timer though. The current patch would make debugging annoying since setting a breakpoint inside the timed section would affects subsequent execution even in trivial cases.

Also I'm still considering other options.
Comment 7 Tim Nguyen (:ntim) 2022-01-05 05:31:15 PST
Comment on attachment 448298 [details]

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

> LayoutTests/imported/w3c/web-platform-tests/css/selectors/invalidation/has-complexity.html:39
> +const start = performance.now();

nit: You're not using this. I assume you want to remove this? Logging (end - start) would cause flakiness in the test results.
Comment 8 Radar WebKit Bug Importer 2022-01-11 07:28:14 PST
Comment 9 Antti Koivisto 2022-01-13 06:07:51 PST
Created attachment 449053 [details]
Comment 10 Dean Jackson 2022-01-13 09:23:18 PST
Comment on attachment 449053 [details]

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

> Source/WebCore/style/ChildChangeInvalidation.cpp:72
> +                // FIXME: We should cache this state accross invalidations instead of just testing a single sibling.

Typo: across

> LayoutTests/imported/w3c/web-platform-tests/css/selectors/invalidation/has-complexity.html:29
> +const yellow = 'rgb(128, 0, 128)';

This is actually purple.

> LayoutTests/imported/w3c/web-platform-tests/css/selectors/invalidation/has-complexity.html:48
> +for (let i = 0; i < count - 1; ++i) {

Why -1 here?

> LayoutTests/imported/w3c/web-platform-tests/css/selectors/invalidation/has-complexity.html:65
> +testColor(`After appending div with ${count} elements. This should not time out.`, yellow);

You should probably rename yellow to purple since that's what you use in the CSS.
Comment 11 Antti Koivisto 2022-01-14 00:02:48 PST
> This is actually purple.

> > LayoutTests/imported/w3c/web-platform-tests/css/selectors/invalidation/has-complexity.html:48
> > +for (let i = 0; i < count - 1; ++i) {
> Why -1 here?

we add the last element separately so that gives exactly count elements.
Comment 12 Antti Koivisto 2022-01-14 02:05:26 PST
Created attachment 449149 [details]
Patch for landing
Comment 13 Antti Koivisto 2022-01-14 02:18:24 PST
Created attachment 449150 [details]
Comment 14 EWS 2022-01-14 03:58:01 PST
Committed r288012 (246038@main): <https://commits.webkit.org/246038@main>

All reviewed patches have been landed. Closing bug and clearing flags on attachment 449150 [details].
Comment 15 Darin Adler 2022-01-14 09:33:23 PST
Comment on attachment 449150 [details]

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

> Source/WebCore/style/ChildChangeInvalidation.h:31
> +#include <wtf/HashSet.h>

Pretty sure this can be done with Forward.h instead, and might be worth it. Can define a type and declare a function involving it without the HashSet.h header. The hash table headers are super commonly used but also huge, so I’m never sure how important it is to keep them out of other headers.