[API Proposal]: ConditionalWeakTable<TKey,TValue>.GetOrAdd

[Sergio0694]

Background and motivation

Currently, there doesn't seem to be a way to implement a lock-free caching algorithm using a ConditionalWeakTable<TKey, TValue> without having to allocate a delegate + closure to insert a value into the table. That is, consider this:

// Try to get an existing value for the key
if (table.TryGetValue(key, out Foo? result))
{
    return result;
}

// Value does not exist, create it (this is potentially expensive)
result = CreateValueForKey(key, configuration);

// Add the value into the table in a way that makes it so that if we're racing against
// another thread, we're guaranteeing that all threads will still only see and retrieve
// the same instance from the table.
table.GetValue(key, _ => result);

That last step would ideally be some table.GetOrAdd(key, result) call, with no delegate needed.
I know you can also do TryAdd and GetValue again if false, but that does one extra unnecessary lookup.

Also consider this similar example:

table.GetValue(key, key => CreateValueForKey(key, configuration));

This works, but it captures configuration and allocates a display and non-cached delegate unnecessarily.

Looking at ConditionalWeakTable<TKey, TValue>, it seems easy enough to add these new APIs:

// Gets the current value, or adds the new one and returns it
public TValue GetOrAdd(TKey key, TValue value);

// Overload of 'GetValue' also taking additional state
public TValue GetValue<TState>(TKey key,  CreateValueCallback<TState> createValueCallback, TState state);

These two convenience methods can be used where appropriate. For instance, it might be simpler in some cases to use the new GetValue overload, whereas in other cases where you might want more control, you might manually try the first lookup, then do some additional work if that fails, and finally call GetOrAdd with the new value you produced.

API Proposal

namespace System.Runtime.CompilerServices;

public sealed class ConditionalWeakTable<TKey, TValue>
{
    public bool TryGetValue(TKey key, [MaybeNullWhen(false)] out TValue value);
    public void Add(TKey key, TValue value);
    public bool TryAdd(TKey key, TValue value);
    public void AddOrUpdate(TKey key, TValue value);
+   public TValue GetOrAdd(TKey key, TValue value);
    public bool Remove(TKey key);
    public void Clear();

    public TValue GetValue(TKey key, CreateValueCallback createValueCallback);
+   public TValue GetValue<TState>(TKey key, CreateValueCallback<TState> createValueCallback, TState state);
+       where TState : allows ref struct
    public TValue GetOrCreateValue(TKey key);

    public delegate TValue CreateValueCallback(TKey key);
+   public delegate TValue CreateValueCallback<TState>(TKey key, TState state)
+       where TState : allows ref struct
}

API Usage

Updating the example above to use the new API:

if (table.TryGetValue(key, out Foo? result))
{
    return result;
}

result = CreateValueForKey(key, state);

return table.GetOrAdd(key, result);

AND

table.GetValue(key, CreateValueForKey, state);

Alternative Designs

Keep using GetValue and waste the delegate + closure allocation (also it's much clunkier).

Risks

None that I can see, it's just two small new APIs with no additional changes needed.
The functionality is the same as already available today, just more effcient.

[ghost]

Tagging subscribers to this area: @dotnet/area-system-runtime-compilerservices
See info in area-owners.md if you want to be subscribed.

Issue Details

---

Background and motivation

Currently, there doesn't seem to be a way to implement a lock-free caching algorithm using a ConditionalWeakTable<TKey, TValue> without having to allocate a delegate + closure to insert a value into the table. That is, consider this:

// Try to get an existing value for the key
if (table.TryGetValue(key, out Foo? result))
{
    return result;
}

// Value does not exist, create it (this is potentially expensive)
result = CreateValueForKey(key);

// Add the value into the table in a way that makes it so that if we're racing against
// another thread, we're guaranteeing that all threads will still only see and retrieve
// the same instance from the table.
table.GetValue(key, _ => result);

That last step would ideally be some table.GetOrAdd(key, result) call, with no delegate needed.
I know you can also do TryAdd and GetValue again if false, but that does one extra unnecessary lookup.

Looking at ConditionalWeakTable<TKey, TValue>, it would seem to be relatively easy to add the new API:

public void GetOrAdd(TKey key, TValue value)
{
    if (key is null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
    }

    lock (_lock)
    {
        int entryIndex = _container.FindEntry(key, out object? existingValue);

        if (entryIndex != -1)
        {
            return Unsafe.As<TValue>(existingValue);
        }

        CreateEntry(key, value);
    }
}

Essentially just a small variation compared to the existing AddOrUpdate method.

API Proposal

namespace System.Runtime.CompilerServices;

public sealed class ConditionalWeakTable<TKey, TValue>
{
+   public void GetOrAdd(TKey key, TValue value);
}

API Usage

Updating the example above to use the new API:

if (table.TryGetValue(key, out Foo? result))
{
    return result;
}

result = CreateValueForKey(key);

return table.GetOrAdd(key, result);

Alternative Designs

Keep using GetValue and waste the delegate + closure allocation (also it's much clunkier).

Risks

None that I can see, it's just a small new API with no additional changes needed.
The functionality is the same as already available today, just more effcient.

Author:	Sergio0694
Assignees:	-
Labels:	api-suggestion, area-System.Runtime.CompilerServices, untriaged, needs-area-label
Milestone:	-

[AustinWise]

Another approach for allowing closure-less use of GetValue:

namespace System.Runtime.CompilerServices;

public sealed class ConditionalWeakTable<TKey, TValue>
{
+   public delegate TValue CreateValueWithStateCallback<TState>(TKey key, TState state);
+   public TValue GetValue<TState>(TKey key,  CreateValueWithStateCallback<TState> createValueCallback, TState state);
}

It's very similar to the existing GetValue function, but it allows passing a state value to the delegate. It's similar to String.Create and other functions in the BCL.

I think this would work for your use case and others. For example, in NativeAOT ComWrappers the GetOrCreateComInterfaceForObject function calls TryGetValue to try to avoid a delegate allocation before calling GetValue. This call to TryGetValue would become unnecessary if GetValue supported passing the CreateComInterfaceFlags as the state parameter.

[Sergio0694]

Honestly, both methods seem useful to me, in different scenarios. For instance:

• The one with a callback would be useful in GetOrCreateComInterfaceForObject
• The one I proposed would be useful in Exit the lock before we call into user code and handle losing the race for the RCW table #110828

Updated proposal:

namespace System.Runtime.CompilerServices;

public sealed class ConditionalWeakTable<TKey, TValue>
{
+   public TValue GetOrAdd(TKey key, TValue value);
+   public TValue GetValue<TState>(TKey key,  CreateValueCallback<TState> createValueCallback, TState state);

+   public delegate TValue CreateValueCallback<TState>(TKey key, TState state)
+       where TState : allows ref struct
}

@tannergooding @eiriktsarpalis are there any other concerns with the proposed shape? If not, could you help mark this as ready to review, so we can move this forward? I'd be happy to contribute these two if they get approved. We can use them to improve ComWrappers on Native AOT in several places as well. Thank you! 🙂

[eiriktsarpalis]

without having to allocate a delegate + closure to insert a value into the table.

In the original example the only thing that your closure is capturing is the key, which could have been passed parametrically. Would it be possible to update the proposal in the OP, and show an example that better conveys what the new GetValue<TState> overload is solving?

Apart from that the proposal looks good to me, although I'm not sure if the original method should be called GetOrAdd or just GetValue. Technically the existing GetValue is similar to the GetOrAdd in ConcurrentDictionary so I'm somewhat concerned that introducing it here would add to the confusion. Anyway, I'm sure this will be debated to death in API review :-)

[Sergio0694]

I've updated the OP to include the two proposed APIs and use examples of both 🙂

"Apart from that the proposal looks good to me, although I'm not sure if the original method should be called GetOrAdd or just GetValue. Technically the existing GetValue is similar to the GetOrAdd in ConcurrentDictionary so I'm somewhat concerned that introducing it here would add to the confusion. Anyway, I'm sure this will be debated to death in API review :-)"

The main reason why I named it GetOrAdd is to distinguish it from GetValue, because all GetValue overloads on ConditionalWeakTable<,> create a new value on their own (either via Activator, or with a supplied callback), whereas this one explicitly takes an existing value provided by the user. The fact it was also consistent with the naming on ConcurrentDictionary<,> was also nice 😄

[eiriktsarpalis]

I've updated the OP to include the two proposed APIs and use examples of both 🙂

I guess I was trying to say that the example could be written like so:

table.GetValue(key, key => CreateValueForKey(key, configuration));

I initially misinterpreted this as it being an issue of the delegate not accepting the key, but this should make it more clear that the actual problem is the delegate needing to capture configuration. Using the new API this would be rewritten as

table.GetValue(key, static (key, configuration) => CreateValueForKey(key, configuration), configuration);

[Sergio0694]

I've updated the OP to also include that example and mention that it'd waste a display class + delegate allocation 👍

To clarify, the proposal is intentionally including both APIs, to give users more flexibility depending on the scenario.

[bartonjs]

Video

• Rather than creating a new delegate type with different arity, we should just use Func.
• When deciding between making the (TKey, TValue) method GetOrAdd or GetValue, we decided to hide the existing members and move everything to the GetOrAdd name, for better alignment with other types with the same semantics.
• We're not obsoleting the old members at this time, just hiding them.

namespace System.Runtime.CompilerServices;

public sealed partial class ConditionalWeakTable<TKey, TValue>
{
+   public TValue GetOrAdd(TKey key, TValue value);
+   public TValue GetOrAdd(TKey key, Func<TKey, TValue> valueFactory);
+   public TValue GetOrAdd<TArg>(TKey key, Func<TKey, TArg, TValue> valueFactory, TArg factoryArgument)
+       where TArg : allows ref struct;
    
+   [EditorBrowsable(EditorBrowsableState.Never)]
    public TValue GetValue(TKey key, CreateValueCallback createValueCallback);
  
+   [EditorBrowsable(EditorBrowsableState.Never)]
    public TValue GetOrCreateValue(TKey key);

+   [EditorBrowsable(EditorBrowsableState.Never)]
    public delegate TValue CreateValueCallback(TKey key);
}

[eiriktsarpalis]

@Sergio0694 would you be interested in contributing the implementation?

[Sergio0694]

Yesss, happy to take this one! 😄

[Sergio0694]

@jkotas I have a follow up question on GetOrCreateValue (didn't ask it yesterday as we were already running way overtime 😅). I'm wondering if especially now that the whole API is hidden, there's some trick we can do to drop the [DynamicallyAccessedMember] annotation on the type. It feels like a waste to have to keep that, only for an API that we're now explicitly trying people to not even use. For instance, would [DynamicallyDependency] potentially do the trick? As in:

public sealed partial class ConditionalWeakTable<TKey, TValue>
{
    [DynamicDependency(DynamicallyAccessedMemberTypes.PublicParameterlessConstructor, typeof(TValue))]
    [EditorBrowsable(EditorBrowsableState.Never)]
    public TValue GetOrCreateValue(TKey key);
}

Would this be sufficient and allow us to drop [DynamicallyAccessedMember] on TValue on the whole type?
If not, is there anything else we could do to avoid paying that size overhead for everyone and make this API pay-for-play?

cc. @MichalStrehovsky

[jkotas]

Would this be sufficient and allow us to drop [DynamicallyAccessedMember] on TValue on the whole type?

I do not understand nuances of the reflection annotations well enough to tell whether this would be sufficient. If you try to do this, do you see any build breaks or complains from the analyzers?

[Sergio0694]

Trying this out, I realized that you can't currently use a type parameter for a type argument in an attribute. I'm out of ideas on how to fix this then 🥲

[Sergio0694]

Would adding [RequiresUnreferencedCode] on GetOrCreateValue be completely out of the picture, or is that something that could potentially be considered?

[jkotas]

It would have to be tracked as a breaking change. I am not sure whether we have a prior art for breaking changes of this nature.

[MichalStrehovsky]

It would be very difficult to add support for "keep members on the T, but only if a specific instance method is called" (and especially so if TValue is a class due to generic sharing; the compiler considers the instance method called on any canonically equivalent T). I don't think there's anything that can be done.

[Sergio0694]

@MichalStrehovsky what do you think about the breaking change if removing the annotation and marking the method as trim unsafe? Is that something you think we could try to do? People calling it would still get the proper warning, which they can easily fix by either using dynamic dependency, or better yet, just calling the new APIs, which are also faster anyway.

[MichalStrehovsky]

Are we purely discussing improved size or are there other considerations? If it's size only, it would have to be really significant to even consider. "We broke your code but look it can be 0.8% smaller" is a much harder sell than "We broke your code but look it can be 8% smaller".

Also note the existing annotation is to keep the public parameterless constructor only - if there is no public parameterless constructor on the T, the size impact should be zero even with the annotation.