RFR: 8330465: Stable Values and Collections (Internal)

Tue May 14 14:14:23 UTC 2024

On Wed, 17 Apr 2024 15:17:52 GMT, Per Minborg <pminborg at openjdk.org> wrote:

>> Also, I want to mention a few important differences between `@Stable` and Stable Values:
>> 
>> Patterns:
>> 1. Benign race (does not exist in StableValue API): multiple threads can create an instance and upload, any non-null instance is functionally equivalent so race is ok (seen in most of JDK)
>> 2. compareAndSet (setIfUnset): multiple threads can create instance, only one will succeed in uploading; usually for when the instance computation is cheap but we want single witness.
>> 3. atomic computation (computeIfUnset): only one thread can create instance which will be witnessed by other threads; this pattern ensures correctness and prevents wasteful computation by other threads at the cost of locking and lambda creation.
>> 
>> Allocation in objects: `@Stable` field is local to an object but `StableValue` is another object; thus sharing strategy may differ, as stable fields are copied over but StableValue uses a shared cache (which is even better for avoiding redundant computation)
>> 
>> Question:
>> 1. Will we ever try to expose the stable benign race model to users?
>> 2. Will we ever try to inline the stable values in object layout like a stable field?
>
>> Question:
>> 
>> 1. Will we ever try to expose the stable benign race model to users?
>> 2. Will we ever try to inline the stable values in object layout like a stable field?
> 
> 1. I think there is little or no upside in exposing the benign race. It would also be difficult to assert the invariant, competing objects are functionally equivalent. So, I think no.
> 
> 2. In a static context, the stable value will be inlined (or rather constant-folded). So we are partly already there. For pure instance contexts, I have some ideas about this but it is non-trivial.

@minborg Just curious, why are you adding holder-in-holder benchmark cases?

>> src/java.base/share/classes/java/util/ImmutableCollections.java line 173:
>> 
>>> 171:                             .map(Objects::requireNonNull)
>>> 172:                             .toArray();
>>> 173:                     return keys instanceof EnumSet
>> 
>> We can move this instanceof check before the stream call.
>
> As we need the array in both cases, how would such a solution look like without duplicating code?

I was thinking about changing the StableEnumMap factory to directly take an EnumSet/BitSet indicating the indices without conversions to full objects and arrays.

>> src/java.base/share/classes/java/util/ImmutableCollections.java line 1677:
>> 
>>> 1675:     static final class StableEnumMap<K extends Enum<K>, V>
>>> 1676:             extends AbstractImmutableMap<K, StableValue<V>>
>>> 1677:             implements Map<K, StableValue<V>>, HasComputeIfUnset<K, V> {
>> 
>> Note that this might be a navigable map, as enums are comparable.
>
> While that is true, no other immutable collection implements a navigable map. The way the API is currently wired, it always returns a `Map`. If we go down this route, it would incidentally return a `NaviableMap` if presented with an `EnumMap` or, we could have a separate factory for enums that states it returns a `NavigableMap`. I think creating all the required views would increase complexity significantly and I am not sure it would be used that much. That said, let us keep this open for the future.

Fair enough, `Collections` APIs like `unmodifiableSortedMap` explicitly avoid implementing too many interfaces.

>> src/java.base/share/classes/jdk/internal/lang/StableValue.java line 279:
>> 
>>> 277:     static <V> V computeIfUnset(List<StableValue<V>> list,
>>> 278:                                 int index,
>>> 279:                                 IntFunction<? extends V> mapper) {
>> 
>> Hmm, these APIs seem unintuitive and error-prone to users. Have you studied the use case where for one stable list/map, there are distinct initialization logics for different indices/keys so that they support different mappers for the same list/map? I cannot recall on top of my head. 
>> 
>> If we drop said ability and restrict mappers to the list/map creation, the whole thing will be much cleaner, and it's a better way to avoid capturing lambdas as well. Users can still go to individual stable values and use functional creation if they really, really want that functionality.
>
> I see what you mean with distinct initialization logic. This is not the intended use though. 
> 
> The reason these methods exist is to avoid lambda capturing. Let's say we have a `Function<K, V>` we want to apply to a `Map<K, StableValue<V>>`. Then, retrieving a `stable = StableValue<V>` and applying `stable.computeIfUnset(() -> function.apply(key))` would capture a new `Supplier`. Another alternative would be to write imperative code similar to what is already in these methods.
> 
> What we could do is provide factories for memorized functions (the latter described in the draft JEP at the end (https://openjdk.org/jeps/8312611) ) even though these are easy to write.
> 
> I think what you are proposing is something like this?
> 
> 
> Map<K, StableValue<V>> map = StableValue.ofMap(keys, k -> createV(k));
> 
> 
> or perhaps even:
> 
> 
> Map<K, V> map = StableValue.ofMap(keys, k -> createV(k));

Yes, consider the 3 capture scenarios:
| API | Capture frequency | Capture Impact | Code Convenience | Flexibility |
|-----|-------------------|----------------|------------------|-------------|
| `StableValue.ofMap(map, k -> ...)` | By accident | single capture is reused | OK | One generator for all keys |
| `StableValue.computeIfUnset(map, key, k -> ...)` | By accident | capture happens for all access sites | somewhat ugly | Different generator for different keys |
| `map.get(k).computeIfUnset(() -> ...)` | Always | capture happens for all access sites | OK | Different generator for different keys |

Notice the `ofMap` factory is the most tolerant to faulty captures: even if it captures, the single capturing lambda is reused for all map stables, avoiding capture overheads at access sites. Given Java compiler doesn't tell user anything about captures during compilation, I think `ofMap` is a better factory to avoid accidentally writing capturing lambdas.

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

PR Comment: https://git.openjdk.org/jdk/pull/18794#issuecomment-2075071225
PR Review Comment: https://git.openjdk.org/jdk/pull/18794#discussion_r1598376355
PR Review Comment: https://git.openjdk.org/jdk/pull/18794#discussion_r1568472583
PR Review Comment: https://git.openjdk.org/jdk/pull/18794#discussion_r1568491254