RFR: 8300487: Store cardinality as a field in BitSet

[Claes Redestad]

On Wed, 11 Jan 2023 13:23:44 GMT, fabioromano1 <duke at openjdk.org> wrote:

>> src/java.base/share/classes/java/util/BitSet.java line 421:
>> 
>>> 419:         final long bitMask = 1L << bitIndex;
>>> 420:         words[wordIndex] ^= bitMask;
>>> 421:         cardinality += (words[wordIndex] & bitMask) != 0 ? 1 : -1;
>> 
>> Isn't there a race condition here? 
>> 
>> I'm wondering if it would not be better to cache the last cardinality and invalidate (negative cardinality) when the bit set is changed. Less intrusive and potentially quicker.
>
> I agree with the fact that is less intrusive, but certainly not potentially quicker, since the complete recalculation of cardinality requires linear time in the value of wordsInUse

A perhaps slightly less racy way would be to only read and write from `words` once:

final long newValue = words[wordIndex] ^ bitMask;
cardinality += (newValue & bitMask) != 0 ? 1 : -1;
words[wordIndex] = newValue;

.. but the fact remains that `BitSet` is not thread-safe, so I think we shouldn't complicate things to avoid or eliminate potential races. (Using a local might help the compiler to avoid the back-to-back array read, but probably doesn't matter)

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

PR: https://git.openjdk.org/jdk/pull/11837