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

[fabioromano1]

On Wed, 18 Jan 2023 14:15:17 GMT, Uwe Schindler <uschindler at openjdk.org> wrote:

> As one dealing with bitsets very often: In my opinion, adding this to bitset adds too much overhead on the hot methods like set/clear methods. Especially loops that populate a BitSet with values, I am not sure if the whole loop can be vectorized by Hotspot after this patch.
> 
> From my experience with Apache Lucene it has been shown, that you use bitsets often to track existence/not existence in very hot loops. Calling cardinality() is done only after you have build the bitset and before you use it in a read-only way.
> 
> I know there are other usages patterns, but also code using BitSet as a compact `Set<Integer>` does not need cardinality information.
> 
> I also have a comment about the code: There is an assert-only method called `checkInvariants()` that is executed after all bulk operations. This one should also check the cardinality fits the current words. This is especially important after those crazy methods that intersect bitsets and have special handling of first/last word.

I have already added a condition that asserts 0 <= cardinality <= length().

In my personal experience, I used BitSet for implementing a set of candidates for a sudoku solver, and the call to cardinality is needed often, and obviously is not read-only, since some candidates can be removed after the call.

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

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