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

[Marius Hanl]

On Wed, 5 Jul 2023 20:52:28 GMT, Michael Strauß <mstrauss at openjdk.org> wrote:

>> 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 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;
>     }
> }

we can even consider to calculate it lazily, if we want to take this approach

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

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