8322964: Optimize performance of CSS selector matching

[hjohn]

Improves performance of selector matching in the CSS subsystem. This is done by using custom set implementation which are highly optimized for the most common cases where the number of selectors is small (most commonly 1 or 2). It also should be more memory efficient for medium sized and large applications which have many style names defined in various CSS files.

Due to the optimization, the concept of StyleClass, which was only introduced to assign a fixed bit index for each unique style class name encountered, is no longer needed. This is because style classes are no longer stored in a BitSet which required a fixed index per encountered style class.

The performance improvements are the result of several factors:

• Less memory use when only very few style class names are used in selectors and styles from a large pool of potential styles (a BitSet for potentially 1000 different style names needed 1000 bits (worst case) as it was not sparse).
• Specialized sets for small number of elements (0, 1, 2, 3-9 and 10+)
• Specialized sets are append only (reduces code paths) and can be made read only without requiring a wrapper
• Iterator creation is avoided when doing containsAll check thanks to the inverse function isSuperSetOf
• Avoids making a copy of the list of style class names to compare (to convert them to StyleClass and put them into a Set) -- this copy could not be cached and was always discarded immediately after...

The overall performance was tested using the JFXCentral application which displays about 800 nodes on its start page with about 1000 styles in various style sheets (and which allows to refresh this page easily).

On JavaFX 20, the fastest refresh speed was 121 ms on my machine. With the improvements in this PR, the fastest refresh had become 89 ms. The speed improvement is the result of a 30% faster Scene#doCSSPass, which takes up the bulk of the time to refresh the JFXCentral main page (about 100 ms before vs 70 ms after the change).

---

Progress

• [x] Change must not contain extraneous whitespace
• [x] Commit message must refer to an issue
• [ ] Change must be properly reviewed (3 reviews required, with at least 1 Reviewer, 2 Authors)

Issue

• JDK-8322964: Optimize performance of CSS selector matching (Enhancement - P4)

Reviewers

• Andy Goryachev (@andy-goryachev-oracle - Reviewer)
• Michael Strauß (@mstr2 - Committer)

Reviewing

Using git

Checkout this PR locally:
$ git fetch https://git.openjdk.org/jfx.git pull/1316/head:pull/1316
$ git checkout pull/1316

Update a local copy of the PR:
$ git checkout pull/1316
$ git pull https://git.openjdk.org/jfx.git pull/1316/head

Using Skara CLI tools

Checkout this PR locally:
$ git pr checkout 1316

View PR using the GUI difftool:
$ git pr show -t 1316

Using diff file

Download this PR as a diff file:
https://git.openjdk.org/jfx/pull/1316.diff

Webrev

Link to Webrev Comment

[bridgekeeper[bot]]

:wave: Welcome back jhendrikx! A progress list of the required criteria for merging this PR into master will be added to the body of your pull request. There are additional pull request commands available for use with this pull request.

[mlbridge[bot]]

Webrevs

• 12: Full - Incremental (cda93e50)
• 11: Full (d72aefab)
• 10: Full (0cf8eeb4)
• 09: Full - Incremental (95086e90)
• 08: Full - Incremental (e4e3a7ce)
• 07: Full - Incremental (2392d8db)
• 06: Full - Incremental (16da6eb0)
• 05: Full - Incremental (dc59c4db)
• 04: Full - Incremental (c388f23d)
• 03: Full (a33f797a)
• 02: Full - Incremental (5201cd2d)
• 01: Full - Incremental (6c3271b0)
• 00: Full (8da98928)

[kevinrushforth]

As @nlisker notes, the implications of any deprecation will need to be discussed. In particular, we need to consider what the consequences are for existing applications. If any of them might be used by apps, then simple deprecation (rather than deprecating for removal) might be best.

/reviewers 3 /csr

[openjdk[bot]]

@kevinrushforth The total number of required reviews for this PR (including the jcheck configuration and the last /reviewers command) is now set to 3 (with at least 1 Reviewer, 2 Authors).

[openjdk[bot]]

@kevinrushforth has indicated that a compatibility and specification (CSR) request is needed for this pull request.

@hjohn please create a CSR request for issue JDK-8322964 with the correct fix version. This pull request cannot be integrated until the CSR request is approved.

[hjohn]

As @nlisker notes, the implications of any deprecation will need to be discussed. In particular, we need to consider what the consequences are for existing applications. If any of them might be used by apps, then simple deprecation (rather than deprecating for removal) might be best.

The methods cannot be reached easily even though they are public. It would involve creating a Selector using Selector#createSelector, and then casting it to SimpleSelector to get access to its public methods that are not inherited from Selector. SimpleSelector itself does not have a public constructor, and the type SimpleSelector is not returned anywhere directly (it is always just Selector in the public API).

The only use of one of the deprecated methods is to allow access for the internal class SelectorPartitioning which indeed does an instanceof to reach it. The other method is not used anywhere, and seems to have been an attempt to make the selectors available in the same form as you'd find them on nodes Styleable#getStyleClass (which is a List), but is hard to reach (probably an oversight that it got exposed in the final API).

Google searches turn up no hits in 3rd party code for either of these.

I've posted on the mailing list to discuss it further.

[mlbridge[bot]]

Mailing list message from Dirk Lemmermann on openjfx-dev:

I truly love the fact that you guys are starting to use JFXCentral for benchmarking / testing :-) If anyone encounters things bad for performance unrelated to JavaFX itself but caused by JFXCentral then please let me know.

Dirk

[mlbridge[bot]]

Mailing list message from John Hendrikx on openjfx-dev:

It's a very nice application, I had never seen it before.? As the original bug was reported against it that caused a performance regression, I started using it to also test a potential performance improvement.? Although I think it does a back-end call every time I "refresh", so I might have been hitting your servers a bit during that period.

I'll let you know if I discover that's off.? Only thing I did was disable a piece of code that was causing a stack trace to be logged each time (a bug in one of the components, fx tray icon, I think).

--John

On 04/01/2024 22:49, Dirk Lemmermann wrote:

I truly love the fact that you guys are starting to use JFXCentral for benchmarking / testing :-) If anyone encounters things bad for performance unrelated to JavaFX itself but caused by JFXCentral then please let me know.

Dirk

[bridgekeeper[bot]]

@hjohn This pull request has been inactive for more than 4 weeks and will be automatically closed if another 4 weeks passes without any activity. To avoid this, simply add a new comment to the pull request. Feel free to ask for assistance if you need help with progressing this pull request towards integration!

[hjohn]

I think we can continue with this one, now that #1340 is done.

[kevinrushforth]

@hjohn Please merge the latest upstream master to pick up the fix for JDK-8324182.

[Maran23]

Tested with a big application, did not found any CSS regressions. Did not dive into the code yet.

[hjohn]

I think this PR now no longer needs a CSR.

[hjohn]

I think its /csroff or something...

[hjohn]

/csroff

[openjdk[bot]]

@hjohn Unknown command csroff - for a list of valid commands use /help.

[hjohn]

/csr unneeded

[openjdk[bot]]

@hjohn only Reviewers can determine that a CSR is not needed.

[kevinrushforth]

I was about to reply, but I see that the Skara bot beat me to it. :)

I'll double-check later (or Andy can), and if there are no public API implications, issue the /csr unneeded command.

[andy-goryachev-oracle]

@hjohn is right - no public API changes remain in this PR.

[andy-goryachev-oracle]

/csr unneeded

[openjdk[bot]]

@andy-goryachev-oracle determined that a CSR request is not needed for this pull request.

[openjdk[bot]]

@hjohn This change now passes all automated pre-integration checks.

ℹ️ This project also has non-automated pre-integration requirements. Please see the file CONTRIBUTING.md for details.

After integration, the commit message for the final commit will be:

8322964: Optimize performance of CSS selector matching

Reviewed-by: angorya, mstrauss, mhanl, kcr

You can use pull request commands such as /summary, /contributor and /issue to adjust it as needed.

At the time when this comment was updated there had been 2 new commits pushed to the master branch:

• 2e1427e8c873c10c0929ffdf385bec305f13f41d: 8087444: CornerRadii with different horizontal and vertical values treated as uniform
• dedcf1d236b5429dcf3c42f5fd1095b28d5da063: 8332539: Update libxml2 to 2.12.7

Please see this link for an up-to-date comparison between the source branch of this pull request and the master branch. As there are no conflicts, your changes will automatically be rebased on top of these commits when integrating. If you prefer to avoid this automatic rebasing, please check the documentation for the /integrate command for further details.

➡️ To integrate this PR with the above commit message to the master branch, type /integrate in a new comment.

[bridgekeeper[bot]]

@hjohn This pull request has been inactive for more than 4 weeks and will be automatically closed if another 4 weeks passes without any activity. To avoid this, simply add a new comment to the pull request. Feel free to ask for assistance if you need help with progressing this pull request towards integration!

[hjohn]

I think this is ready to be integrated. Let me know if there is anything still missing.

[kevinrushforth]

I'm in the process of testing this. I'll do that and report back.

[hjohn]

Code looks good to me. As mentioned above, I tested it already and everything was good, so I'm certain that there is no regression here.

I'm generally not a big fan of 'reimplementing' Collections, but I can see why it is needed here and it also makes sense, especially for something like CSS which needs to be fast. Something I saw as well in Swing (just check the ArrayTable class 😄 ).

I'm not a fan either, especially because custom collection implementations when referred to by their interface may sneak their way through the various classes and eventually be returned to users. Any deviation from the collection contracts then suddenly is a bug users may encounter. I would have done this with plain HashSet (or Set.of) were it not for the fact that a lot of performance gains were possible due to the limited way FX is using these sets.

I wonder if we may want to add some tests for the FixedCapacitySet?

Yeah, now that it is more likely that this will make it into FX, I will add a small set of unit tests for this class.

[kevinrushforth]

I wonder if we may want to add some tests for the FixedCapacitySet?

Yeah, now that it is more likely that this will make it into FX, I will add a small set of unit tests for this class.

Since this PR is ready to integrate, I think it would be fine to file a new test bug for the additional tests if you like. If you prefer to add the new tests now, that's fine, too (we can re-review it).

[hjohn]

I wonder if we may want to add some tests for the FixedCapacitySet?

Yeah, now that it is more likely that this will make it into FX, I will add a small set of unit tests for this class.

Since this PR is ready to integrate, I think it would be fine to file a new test bug for the additional tests if you like. If you prefer to add the new tests now, that's fine, too (we can re-review it).

I'm fine integrating this as-is and adding a test soon after. I will leave this over the weekend to give others time to review.

Also some clarification on the contributing rules: "all Reviewers who have requested the chance to review have done so" -- does the indication at the top right of the PR count towards this or should it be a comment? :) In the first case, @nlisker and @arapte, please indicate if you wish to review this still.

[nlisker]

The code looks good. I didn't test it, but I'm fine with integrating.