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

[John Hendrikx]

On Mon, 4 Sep 2023 09:40:14 GMT, Johan Vos <jvos 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/BitSet.java line 543:
> 
>> 541:         int b = other.bits != null ? other.bits.length : 0;
>> 542: 
>> 543:         if (a != b) return false;
> 
> I understand the following loop will return false in case a != b as well, but for performance reasons, wouldn't it be best to keep this test (as it immediately fails in case a != b)?

The problem is that `BitSet` isn't diligent enough about how it manages its arrays.  If all bits get cleared in the highest `long`, it would need to shrink the array (potentially by more than one `long` if the next highest `long` is also `0`), but of course it doesn't.  The only thing it does is to reset to an empty array when **all** bits were cleared.

So `a != b` does not guarantee they're not equal.  If `a` has length 1 and `b` has length 2 but its `bits[1]` is `0`, they're still equal (assuming `bits[0]` is equal for both).

The whole class is poorly engineered unfortunately -- note that almost all comments about this change are pointing out problems in `BitSet`, not about the actual caching.

I think it would best to remove `BitSet`.  The need for it is minimal once the caching goes in; saving space when you have a million copies of these is useful, but no longer relevant when they're now a million references to the same (immutable) copy.

> Are we guaranteed that it is an invariant of this Class that there will never be an entry in bits that is 0?

Unfortunately not, the `remove` code does not shrink the array (it only shrinks when all bits were cleared, not when only the bits were cleared in higher `long` locations).

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

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