RFR: 8300487: Store cardinality as a field in BitSet [v5]

[Claes Redestad]

On Wed, 18 Jan 2023 12:43:31 GMT, fabioromano1 <duke at openjdk.org> wrote:

>> The enanchment is useful for applications that make heavy use of BitSet objects as sets of integers, and therefore they need to make a lot of calls to cardinality() method, which actually require linear time in the number of words in use by the bit set.
>> This optimization reduces the cost of calling cardinality() to constant time, as it simply returns the value of the field, and it also try to make as little effort as possible to update the field, when needed.
>> 
>> Moreover, it has been implemented a new method for testing wheter a bit set includes another bit set (i.e., the set of true bits of the parameter is a subset of the true bits of the instance).
>
> fabioromano1 has updated the pull request incrementally with one additional commit since the last revision:
> 
>   Added author and reverse the cicle order in includes(BitSet)

I'll additionally note that there was a recent enhancement to enable vectorization of loops over `Long.bitCount(long)`, which should help `BitSet.cardinality()` calls by a large factor: https://bugs.openjdk.org/browse/JDK-8278868 - this can mean building up and then invoking an unchanged `cardinality()` is likely to be cheaper than the extra book-keeping to maintain a derived `cardinality` value. How does performance of `BitSet.cardinality()` compare before/after JDK 19? If there's a large improvement the need for this approach might have diminished.

Perhaps caching the result of `cardinality()` is a less intrusive alternative, but as @JimLaskey is suggesting perhaps this would be better conceptualized as a subclass.

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

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