[API Proposal]: 'ConcurrentDictionary<TKey, TValue>.AlternateLookup<TAlternateKey>.GetOrAdd' overloads

[Sergio0694]

Background and motivation

The alternate lookup for ConcurrentDictionary<TKey, TValue> is missing the GetOrAdd overloads, which makes it necessary to do a wasteful secondary lookup to try to get a value and add it if not present. We need to do this in several startup paths in CsWinRT, meaning that without a GetOrAdd we'd end up hitting the second lookup for basically every single marshalled type requiring dynamic type checks at startup:

public static Type Get(ReadOnlySpan<char> runtimeClassName)
{
    var alternate = TypeNameToMappedTypes.GetAlternateLookup<ReadOnlySpan<char>>();

    if (alternate.TryGetValue(runtimeClassName, out Type? type))
    {
        return type;
    }

    type = typeof(int); // Get the value from somewhere

    if (alternate.TryAdd(runtimeClassName, type))
    {
        return type;
    }

    return alternate[runtimeClassName];
}

The code is also very verbose and clunky, on top of being inefficient.

API Proposal

 namespace System.Collections.Concurrent;

 partial class ConcurrentDictionary<TKey, TValue>
 {
     partial struct AlternateLookup<TAlternateKey>
     {
+       public TValue GetOrAdd(TAlternateKey key, Func<TAlternateKey, TValue> valueFactory);
+       public TValue GetOrAdd<TArg>(TAlternateKey key, Func<TAlternateKey, TArg, TValue> valueFactory, TArg factoryArgument) where TArg : allows ref struct;
+       public TValue GetOrAdd(TAlternateKey key, TValue value);
     }
 }

API Usage

The above snippet can then become just this:

public static Type Get(ReadOnlySpan<char> runtimeClassName)
{
    var alternate = TypeNameToMappedTypes.GetAlternateLookup<ReadOnlySpan<char>>();

    return alternate.GetOrAdd(runtimeClassName, GetTypeFromRuntimeClassName);
}

Way simpler, and with no repeated lookups and unnecessary overhead.

Risks

None, these APIs already exist and are well established on ConcurrentDictionary<TKey, TValue> itself.

[dotnet-policy-service]

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

[stephentoub]

which makes it necessary to do a wasteful secondary lookup to try to get a value and add it if not present

GetOrAdd still does two lookups; the only cost it saves over doing a get followed by an add yourself is one GetHashCode.

we'd end up hitting the second lookup for basically every single marshalled type requiring dynamic type checks at startup:

Have you measured the actual overhead here? I'm surprised it registers.

[Sergio0694]

"GetOrAdd still does two lookups"

This manual version can do up to 3 though, if you also happened to lose the race when trying to add the key after the initial check. So it's still mean you'd go down to just 2 in the worst case, which is a small improvement?

To clarify, I'm not trying to make an argument for GetOrAdd per se. Those APIs already exist, so I'd imagine whatever argument was made when they were added has already been resolved and deemed sufficient. This is strictly just about making the alternate lookup having parity. Performance isn't really the main concern, I'd have opened this proposal even just for convenience alone 😄

[stephentoub]

I'm not trying to make an argument for GetOrAdd per se

You are, though... this proposal is an argument for GetOrAdd being added. :)

This manual version can do up to 3 though, if you also happened to lose the race when trying to add the key after the initial check.

You have high amounts of concurrency on your startup path?

so I'd imagine whatever argument was made when they were added has already been resolved and deemed sufficient

They were added for convenience. I'm not concerned about squaring the circle here for alternate lookup; it doesn't need complete parity with every single method. Note, too, that the GetOrAdd overloads have their own overheads, namely a delegate invocation, plus a closure if one is captured.

[Sergio0694]

"You are, though... this proposal is an argument for GetOrAdd being added. :)"

You are of course right, I just meant to say that to me this would be different if I had been proposing GetOrAdd to be added in the first place on ConcurrentDictionary<,>, in which case I'd have tried to provide more argument in support of it. In this case instead what I'm trying to say is, those APIs already exist, so whatever argument worked for them, the same applies here too.

"You have high amounts of concurrency on your startup path?"

I'd use this in CsWinRT, so I can't really speak for the amount of concurrency in consuming applications. I'd be inclined to say I wouldn't expect too many collisions in this specific scenario, but I was just trying to say that getting the maximum theoretical number of lookups from 3 down to 2 still seemed like general goodness. But yeah the main reason would be convenience.

"I'm not concerned about squaring the circle here for alternate lookup"

Why? It feels a bit weird that if you decide to use the alternate lookup, you fall of a little cliff there and have to go back to manually handling multiple attempts for lookups, and need to trade the convenience away to save the key allocation. To me it'd seem reasonable to say, you can use the lookup if you have a span, but that's orthogonal to the convenience lookup methods you have.

"Note, too, that the GetOrAdd overloads have their own overheads, namely a delegate invocation, plus a closure if one is captured."

I'm not too concerned about the delegate invocation in this specific case, since that'd most likely end up just being noise compared to the actual type map lookup, since Jan mentioned that'd probably involve some UTF8 transcoding as well. As for the closure, of course, we'd want to only ever use this without creating one. I mean not unlike with the existing GetOrAdd on the outer type 😄

[stephentoub]

I'm not concerned about squaring the circle here for alternate lookup"

Why? It feels a bit weird that if you decide to use the alternate lookup, you fall of a little cliff there and have to go back to manually handling multiple attempts for lookups

It's little different from switching to another dictionary (like Dictionary<>) that doesn't have such methods. And because a bunch of the methods are barely used in earnest and probably shouldn't have been added to ConcurrentDictionary in the first place, like the AddOrUpdate methods.

[Sergio0694]

That's fair. Also talked with Eirik offline, will just close this for now then. Thank you! 🙂