Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

8322964: Optimize performance of CSS selector matching #1316

Closed

Conversation

hjohn
Copy link
Collaborator

@hjohn hjohn commented Jan 4, 2024

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

  • Change must not contain extraneous whitespace
  • 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

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
Copy link

bridgekeeper bot commented Jan 4, 2024

👋 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.

@hjohn hjohn changed the title Feature/selector performance improvement JDK-8322964 Optimize performance of CSS selector matching Jan 4, 2024
@hjohn hjohn marked this pull request as ready for review January 4, 2024 12:27
@openjdk openjdk bot added the rfr Ready for review label Jan 4, 2024
@mlbridge
Copy link

mlbridge bot commented Jan 4, 2024

Copy link
Collaborator

@nlisker nlisker left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I just scrolled quickly through the changes and left some comments,

If deprecation for removal is part of the PR the consequences will need to be discussed. Are the for-removal classes and methods not widely used?

@kevinrushforth
Copy link
Member

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
Copy link

openjdk bot commented Jan 4, 2024

@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 openjdk bot added the csr Need approved CSR to integrate pull request label Jan 4, 2024
@openjdk
Copy link

openjdk bot commented Jan 4, 2024

@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.

Copy link
Member

@kevinrushforth kevinrushforth left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Left a couple inline comments.

@hjohn
Copy link
Collaborator Author

hjohn commented Jan 5, 2024

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
Copy link

mlbridge bot commented Jan 5, 2024

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
Copy link

mlbridge bot commented Jan 6, 2024

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

@kevinrushforth kevinrushforth self-requested a review January 6, 2024 20:19
@bridgekeeper
Copy link

bridgekeeper bot commented Feb 12, 2024

@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
Copy link
Collaborator Author

hjohn commented May 24, 2024

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
Copy link
Member

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
Copy link
Collaborator Author

hjohn commented May 24, 2024

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
Copy link
Collaborator

nlisker commented May 24, 2024

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

@tsayao
Copy link
Collaborator

tsayao commented May 24, 2024

I built it and tested on a retail self-checkout app that uses a lot of css. All good.

@kevinrushforth
Copy link
Member

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.

If someone wants you to wait for them, they should make it clear by adding a comment. Also if someone has given substantive feedback, but hasn't (re)approved, it's good to give them a change to review.

@arapte can add a comment if he wants to review, otherwise go ahead and integrate on Monday.

@openjdk openjdk bot removed the ready Ready to be integrated label May 28, 2024
@hjohn
Copy link
Collaborator Author

hjohn commented May 28, 2024

@kevinrushforth @andy-goryachev-oracle @Maran23 @mstr2

I couldn't leave this without a proper test, so I created a test for FixedCapacitySet.

I didn't discover any issues, but did discover there was a line of code I couldn't cover in the OpenAddressed variant (not even with a specially crafted test case). I checked the code, and realized the situation can never occur, so I've removed those lines and added a comment and assert instead.

@openjdk openjdk bot added the ready Ready to be integrated label May 28, 2024
Copy link
Contributor

@andy-goryachev-oracle andy-goryachev-oracle left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

please add copyright header

@openjdk openjdk bot removed the ready Ready to be integrated label May 28, 2024
Copy link
Contributor

@andy-goryachev-oracle andy-goryachev-oracle left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

thank you! sorry, I missed that earlier.

@openjdk openjdk bot added the ready Ready to be integrated label May 29, 2024
@hjohn
Copy link
Collaborator Author

hjohn commented May 31, 2024

/integrate

@openjdk
Copy link

openjdk bot commented May 31, 2024

Going to push as commit b08d7bb.
Since your change was applied there have been 2 commits pushed to the master branch:

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

Your commit was automatically rebased without conflicts.

@openjdk openjdk bot added the integrated Pull request has been integrated label May 31, 2024
@openjdk openjdk bot closed this May 31, 2024
@openjdk openjdk bot removed ready Ready to be integrated rfr Ready for review labels May 31, 2024
@openjdk
Copy link

openjdk bot commented May 31, 2024

@hjohn Pushed as commit b08d7bb.

💡 You may see a message that your pull request was closed with unmerged commits. This can be safely ignored.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
integrated Pull request has been integrated
7 participants