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

[fabioromano1]

On Thu, 19 Jan 2023 23:14:12 GMT, John R Rose <jrose at openjdk.org> wrote:

> I'll pile on: This optimization doesn't buy much in today's world, where most machines execute `bitCount` in one cycle. It saves a trivial loop. Over very large bitsets that saves something, but most bitsets are likely to be medium to small (across all use cases). And for large bitsets, if there is a problem with cardinality testing, the user should provide for it separately. Perhaps as a class which contains a bitset, plus the extra cached information. You might also cache the index of the first and last words containing a set bit. There's no end to what one might cache: It's data, and you can derive information from it. That's a job for users, not for the library.
> 
> Also, as folks have noted, adding a speedup in one place pushes slowdowns in other places. Worst of all, there are new race conditions in the "improved" data structure.
> 
> I don't recommend this change. If the data structure were immutable, I might think otherwise (as String caches its hashcode), but the race conditions really spoil it for me.

As @cl4es noted, race conditions are not a problem, since BitSet is not a thread-safe class. Anyway, I decided to do instead a subclass that implements this enhancement, in order to avoid creating the problems shown here.

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

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