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

[Michael Strauß]

On Wed, 5 Jul 2023 22:14:38 GMT, John Hendrikx <jhendrikx at openjdk.org> wrote:

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

I see. If the cached sets are not passed into the cache again, it doesn't seem to be all that useful to precompute the hash.

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

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