Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Closed
Sergio0694 opened this issue Feb 27, 2025 · 7 comments
Labels
api-suggestion Early API idea and discussion, it is NOT ready for implementation area-System.Collections partner-impact This issue impacts a partner who needs to be kept updated

Comments

@Sergio0694
Copy link
Contributor

Sergio0694 commented Feb 27, 2025

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.

@Sergio0694 Sergio0694 added api-suggestion Early API idea and discussion, it is NOT ready for implementation area-System.Collections partner-impact This issue impacts a partner who needs to be kept updated labels Feb 27, 2025
@dotnet-policy-service dotnet-policy-service bot added the untriaged New issue has not been triaged by the area owner label Feb 27, 2025
Copy link
Contributor

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

@Sergio0694 Sergio0694 changed the title [API Proposal]: 'ConcurrentDictionary<TKey, TValue.AlternateLookup<TAlternateKey>.GetOrAdd' overloads [API Proposal]: 'ConcurrentDictionary<TKey, TValue>.AlternateLookup<TAlternateKey>.GetOrAdd' overloads Feb 27, 2025
@stephentoub
Copy link
Member

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
Copy link
Contributor Author

"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
Copy link
Member

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
Copy link
Contributor Author

"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
Copy link
Member

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
Copy link
Contributor Author

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

@Sergio0694 Sergio0694 closed this as not planned Won't fix, can't repro, duplicate, stale Feb 27, 2025
@dotnet-policy-service dotnet-policy-service bot removed the untriaged New issue has not been triaged by the area owner label Feb 27, 2025
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
api-suggestion Early API idea and discussion, it is NOT ready for implementation area-System.Collections partner-impact This issue impacts a partner who needs to be kept updated
Projects
None yet
Development

No branches or pull requests

2 participants