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

[John Hendrikx]

On Wed, 5 Jul 2023 20:56:51 GMT, Marius Hanl <mhanl at openjdk.org> wrote:

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

These sets are still created on demand, just as often as before, the main change is that there will no longer be thousands of exact duplicate sets in memory that can't be shared because they are modifiable.  The passed in sets will in 99% of the cases be newly allocated sets outside of our control, allocated just nanoseconds before.  The hash code therefore will still need to be computed in almost all cases.  These are then compared with the keys in the map, which already have a pre-computed hash code (courtesy of `HashMap`).

It would be exceedingly rare (and probably a mistake) to pass in a set that you got from the cache.  If you use the cache, you know you have an immutable version, and so can share it freely.  Methods that expose these again should be documented that the set is already immutable (see `Match#getPseudoClasses` for example).  Aside from loading new style sheets, the code that will be doing the most calls to `ImmutablePseudoClassSetsCache#of` is in the `CssStyleHelper`:

                PseudoClassState pseudoClassState = new PseudoClassState();

                pseudoClassState.addAll(parent.pseudoClassStates);
                pseudoClassState.retainAll(parent.styleHelper.triggerStates);

                retainedStates[count++] = ImmutablePseudoClassSetsCache.of(pseudoClassState);

As you can see, it constructs a new mutable set, and converts it to an immutable one.  We can't avoid its hash code calculation. 

Also, the returned immutable set is currently a highly optimized implementation from `ImmutableCollections` (although they don't cache the hash code). They for example have memory storage requirements similar to an array, but still offer `O(1)` contains checks thanks to an open addressing hashing scheme that uses probing.  Even that barely matters though as most of these sets will contain only a couple of elements (most of them 1, some of them 2, and extremely rarely 3 or more).  Still, we'd be trading one optimization for another and a new maintenance burden.

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

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