RFR: JDK-8199216: Quadratic layout time with nested nodes and pseudo-class in style sheet [v8]

[Michael Strauß]

On Fri, 9 Jun 2023 12:45:02 GMT, John Hendrikx <jhendrikx at openjdk.org> wrote:

>> This fix introduces immutable sets of `PseudoClass` almost everywhere, as they are rarely modified.  These are re-used by caching them in a new class `ImmutablePseudoClassSetsCache`.
>> 
>> In order to make this work, `BitSet` had to be cleaned up.  It made assumptions about the collections it is given (which may no longer always be another `BitSet`).  I also added the appropriate null checks to ensure there weren't any other bugs lurking.
>> 
>> Then there was a severe bug in `toArray` in both the subclasses that implement `BitSet`.
>> 
>> The bug in `toArray` was incorrect use of the variable `index` which was used for both advancing the pointer in the array to be generated, as well as for the index to the correct `long` in the `BitSet`.  This must have resulted in other hard to reproduce problems when dealing with `Set<PseudoClass>` or `Set<StyleClass>` if directly or indirectly calling `toArray` (which is for example used by `List.of` and `Set.of`) -- I fixed this bug because I need to call `Set.copyOf` which uses `toArray` -- as the same bug was also present in `StyleClassSet`, I fixed it there as well.
>> 
>> The net result of this change is that there are far fewer `PseudoClassState` objects created; the majority of these are never modified, and the few that are left are where you'd expect to see them modified.
>> 
>> A test with 160 nested HBoxes which were given the hover state shows a 99.99% reduction in `PseudoClassState` instances and a 70% reduction in heap use (220 MB -> 68 MB), see the linked ticket for more details.
>> 
>> Although the test case above was extreme, this change should have positive effects for most applications.
>
> John Hendrikx has updated the pull request with a new target base due to a merge or a rebase. The pull request now contains 16 commits:
> 
>  - Merge branch 'master' of https://git.openjdk.org/jfx into
>    feature/immutable-pseudoclassstate
>  - Merge remote-tracking branch 'upstream/master' into feature/immutable-pseudoclassstate
>  - Avoid using Lambda in ImmutablePseudoClassSetsCache.of()
>  - Merge branch 'master' of https://git.openjdk.org/jfx into
>    feature/immutable-pseudoclassstate
>  - Fix another edge case in BitSet equals
>    
>    When arrays are not the same size, but there are no set bits in the ones
>    the other set doesn't have, two bit sets can still be considered equal
>  - Take element type into account for BitSet.equals()
>  - Base BitSet on AbstractSet to inherit correct equals/hashCode/toArray
>    
>    - Removed faulty toArray implementations in PseudoClassState and
>    StyleClassSet
>    - Added test that verifies equals/hashCode for PseudoClassState respect
>    Set contract now
>    - Made getBits package private so it can't be inherited
>  - Remove unused code
>  - Ensure Match doesn't allow modification
>  - Simplify ImmutablePseudoClassSetsCache and avoid an unnecessary copy
>  - ... and 6 more: https://git.openjdk.org/jfx/compare/9ad0e908...7975ae99

modules/javafx.graphics/src/main/java/com/sun/javafx/css/ImmutablePseudoClassSetsCache.java line 50:

> 48:      * @throws NullPointerException when {@code pseudoClasses} is {@code null} or contains {@code null}s
> 49:      */
> 50:     public static Set<PseudoClass> of(Set<PseudoClass> pseudoClasses) {

Usually, a static `of` method returns an instance of the declaring class. Maybe a name like `immutableSetOf` would be better.

modules/javafx.graphics/src/main/java/com/sun/javafx/css/ImmutablePseudoClassSetsCache.java line 57:

> 55:         }
> 56: 
> 57:         Set<PseudoClass> copy = Set.copyOf(pseudoClasses);

The set that is returned from this method will probably be passed into the method over and over again. Every time, `CACHE.get(...)` will call `pseudoClasses.hashCode()`, which in turn iterates over all elements to compute the hash code. Have you considered precomputing the hash code of the set, so that this repeated recalculation is not required? While this might seem like a micro-optimization, we are potentially dealing with a method that is called very often.

Here is an alternative implementation for an immutable set that precomputes and stores its hash code:

final class ImmutableSet<T> extends AbstractSet<T> {
    private final T[] elements;
    private final int hashCode;

    @SuppressWarnings("unchecked")
    ImmutableSet(Set<T> elements) {
        this.elements = (T[])elements.toArray();
        this.hashCode = elements.hashCode();
    }

    @Override
    public Object[] toArray() {
        return elements.clone();
    }

    @Override
    public Iterator<T> iterator() {
        return new Iterator<>() {
            int index;

            @Override
            public boolean hasNext() {
                return index < elements.length;
            }

            @Override
            public T next() {
                try {
                    return elements[index++];
                } catch (ArrayIndexOutOfBoundsException ignored) {
                    throw new NoSuchElementException();
                }
            }
        };
    }

    @Override
    public int size() {
        return elements.length;
    }

    @Override
    public int hashCode() {
        return hashCode;
    }
}

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

PR Review Comment: https://git.openjdk.org/jfx/pull/1076#discussion_r1253628919
PR Review Comment: https://git.openjdk.org/jfx/pull/1076#discussion_r1253634604