RFR: 8315454: Add an immutable BitSet

[John Rose]

On 1 Sep 2023, at 2:38, Maurizio Cimadamore wrote:

> On Fri, 1 Sep 2023 09:07:34 GMT, Per Minborg <pminborg at openjdk.org> wrote:
>
>>> Maybe it would make sense to start with a JDK-internal variant before exploring potential public API?
>>
>> This is certainly one alternative.
>
> When looking at this I thought about that too. It seems like the particular case where this optimization is applicable is very specific, and I'm on the fence as to whether this deserves a public API. At the same time, there might be near-misses that could be difficult to address once the API is set in stone. I'd suggest to let it bake (inside the JDK) for some time, and later on decide whether it should be exposed as a public API.
>
> All that said, the idea of exposing a fast predicate over an immutable snapshot is very cute and clever :-)

There is a related API I call Classifier which takes a List<T> l and returns an immutable IntFunction<T>, where the function works like x->l.indexOf(x).  The reason it might deserve (someday) to be its own API is that the factory for a classifier might be allowed to do significant work to create an optimized instruction sequence for classifying its inputs.  The literature of perfect hash functions would apply in many cases, and the classifier spun up for some particular list might operate in O(1) time.  The reason I started thinking about such things was considering the optimization of switches (say, over strings or other values) and the optimization of RE character classes.  Perfect hashing applies in both cases, but the heuristic algorithms should be hidden behind an API, and Classifier is what came up for me as the centerpiece.  (That plus classifier factories on various kinds of lists and arrays and other sequences or sets.)

— John