RFR: JDK-8322964 Optimize performance of CSS selector matching [v5]

[Andy Goryachev]

On Sun, 25 Feb 2024 22:28:12 GMT, John Hendrikx <jhendrikx at openjdk.org> wrote:

>> 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).
>
> John Hendrikx has updated the pull request incrementally with one additional commit since the last revision:
> 
>   Optimize performance of OpenAddressed Set just in case it is ever used

modules/javafx.graphics/src/main/java/com/sun/javafx/css/FixedCapacitySet.java line 96:

> 94:              : maximumCapacity == 2 ? new Duo<>()
> 95:              : maximumCapacity < 10 ? new Hashless<>(maximumCapacity)  // will reject negative values
> 96:                                     : new OpenAddressed<>(maximumCapacity);

I wonder if standard HashSet should be used instead of OpenAddressed one, or should there be another threshold which results in a HashSet, to support large sets? 

Or we can reasonably guarantee that these sets are always small?

modules/javafx.graphics/src/main/java/com/sun/javafx/css/FixedCapacitySet.java line 135:

> 133:     protected final void ensureNotFrozen() {
> 134:         if (frozen) {
> 135:             throw new UnsupportedOperationException();

should we explain why?  "the set is frozen" or something like that.

modules/javafx.graphics/src/main/java/com/sun/javafx/css/FixedCapacitySet.java line 207:

> 205: 
> 206:             for (T element : c) {
> 207:                 modified |= add(element);

is there a reason we are overriding the superclass with essentially the same implementation (and this implementation executes OR on every element, while the superclass one is more efficient).
not that it's important in the case of Single...

modules/javafx.graphics/src/main/java/com/sun/javafx/css/FixedCapacitySet.java line 215:

> 213:         @Override
> 214:         public int hashCode() {
> 215:             return element == null ? 0 : element.hashCode();

very minor: should we mix in the class hashCode?  ex:
`return Objects.hashCode(Single.class, element);`

modules/javafx.graphics/src/main/java/com/sun/javafx/css/FixedCapacitySet.java line 290:

> 288: 
> 289:         @Override
> 290:         public boolean addAll(Collection<? extends T> c) {

same concern about overriding the superclass method

modules/javafx.graphics/src/main/java/com/sun/javafx/css/FixedCapacitySet.java line 391:

> 389: 
> 390:         @Override
> 391:         public boolean addAll(Collection<? extends T> c) {

and here

modules/javafx.graphics/src/main/java/com/sun/javafx/css/FixedCapacitySet.java line 570:

> 568:                 T element = elements[i];
> 569: 
> 570:                 h += element == null ? 0 : element.hashCode();

- is there a reason not to use the standard hashCode pattern of `result = 31 * result + (element == null ? 0 : element.hashCode());`?
- should we also mix in the class hash code?

modules/javafx.graphics/src/test/java/test/com/sun/javafx/css/BitSetTest.java line 160:

> 158: //
> 159: //        assertNotEquals(set1, set2);
> 160: //    }

should we remove the dead code?

-------------

PR Review Comment: https://git.openjdk.org/jfx/pull/1316#discussion_r1518416160
PR Review Comment: https://git.openjdk.org/jfx/pull/1316#discussion_r1518402302
PR Review Comment: https://git.openjdk.org/jfx/pull/1316#discussion_r1518407964
PR Review Comment: https://git.openjdk.org/jfx/pull/1316#discussion_r1518403624
PR Review Comment: https://git.openjdk.org/jfx/pull/1316#discussion_r1518412187
PR Review Comment: https://git.openjdk.org/jfx/pull/1316#discussion_r1518412908
PR Review Comment: https://git.openjdk.org/jfx/pull/1316#discussion_r1518414743
PR Review Comment: https://git.openjdk.org/jfx/pull/1316#discussion_r1518422248