[API Proposal]: Dictionary.GetOrAdd

[verdie-g]

Background and motivation

One pattern that I feel I write everyday, especially when replacing GroupBy for perf reason, is this

Dictionary<int, List<Blog>> blogsByUserId = [];

// ...

if (!blogsByUserId.TryGet(userId, out List<Blog> blogs))
{
    blogs = [];
}

blogs.Add(blog);

It's verbose and requires two dictionary accesses. It could be rewritten with CollectionsMarshal.GetValueRefOrAddDefault but it's an uncommon API so it requires more effort to understand for the reader

ref List<Blog>? blogs = ref CollectionsMarshal.GetValueRefOrAddDefault(blogsByUserId, userId, out bool exists);
if (!exists)
{
    blogs = [];
}

blogs.Add(blog);

A GetOrAdd method would greatly simplified that code. I understand that we want to avoid adding helpers for every possible use-cases but I believe it's such a common pattern that it deserves to be built-in.

API Proposal

The implementation would reside right next to the helper Dictionary.GetValueOrDefault.

namespace System.Collections.Generic;

public static class CollectionExtensions
{
    public static TValue GetOrAdd<TKey, TValue>(
        this Dictionary<TKey, TValue> dictionary,
        TKey key,
        Func<TKey, TValue> valueFactory)
        where TKey : notnull;

    public static TValue GetOrAdd<TKey, TValue, TArg>(
        this Dictionary<TKey, TValue> dictionary,
        TKey key,
        Func<TKey, TState, TValue> valueFactory,
        TArg factoryArgument)
        where TKey : notnull;
}

Inspired by ConcurrentDictionary<TKey,TValue>.GetOrAdd.

The implementation would leverage CollectionsMarshal.GetValueRefOrAddDefault.

API Usage

The original snippet could be rewritten with

blogsByUserId.GetOrAdd(userId, static _ => []).Add(blog);

Alternative Designs

IDictionary extension

CollectionsMarshal.GetValueRefOrAddDefault only work on Dictionary. Still, we could do a

public static TValue GetOrAdd<TKey, TValue>(
    this IDictionary<TKey, TValue> dictionary,
    TKey key,
    Func<TKey, TValue> valueFactory)
{
    if (dictionary is Dictionary<TKey, TValue> d)
    {
        ref TValue? value = ref CollectionsMarshal.GetValueRefOrAddDefault(d, key, out bool exists);
        if (!exists)
        {
            value = valueFactory(key);
        }
    }
    else
    {
        // ...
    }
}

That would have an impact of the performance.

Dictionary instance method

Sounds like a good practice to use an extension method rather than an instance one when possible.

Risks

Break existing GetOrAdd extensions

I would expect many existing implementations of GetOrAdd, see this sourcegraph query for example. This proposal would introduce a potential source breaking change.

[dotnet-policy-service]

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

[eiriktsarpalis]

Duplicate of #15059. We ended up with CollectionsMarshal.GetValueRefOrAddDefault as more efficient way for achieving the same result.

[verdie-g]

@eiriktsarpalis the proposal is an extra helper over CollectionsMarshal.GetValueRefOrAddDefault

[verdie-g]

@eiriktsarpalis could you have a look at this again 🙏 The proposal has several advantages over CollectionsMarshal.GetValueRefOrAddDefault:

• Could work with IDictionary
• Hides complexity of CollectionsMarshal.GetValueRefOrAddDefault. Most .NET developers around me would not be comfortable to use such advanced method.
• Less error-prone. A developer could try to compare the return value with null instead of using the out parameter exists

ref List<Blog>? blogs = ref CollectionsMarshal.GetValueRefOrAddDefault(blogsByUserId, userId, out bool exists);
if (blogs == null) // Wrong
{
}

• Less verbose
• Allows chaining

ref List<Blog>? blogs = ref CollectionsMarshal.GetValueRefOrAddDefault(blogsByUserId, userId, out bool exists);
if (!exists)
{
    blogs = [];
}

blogs.Add(blog);

VS

blogsByUserId.GetOrAdd(userId, static _ => []).Add(blog);

[eiriktsarpalis]

Could work with IDictionary

How could it work with IDictionary without forcing duplicate lookups? Given that this is intended as a performance sensitive method, I don't see how including runtime type tests or a creation delegate helps. ConcurrentDictionary is different in that regard since insertions are fundamentally more expensive. This is also the conclusion reached in #15059 which is what led to the introduction of GetValueRefOrAddDefault.

[tannergooding]

I don't think it could work efficiently with IDictionary, but sometimes people don't strictly need the most efficient thing. They just want the convenient thing instead.

More practically, I think for Dictionary<TKey, TValue> itself the premise is that people want the ability to simply GetOrAdd without having to go use a hidden away API that requires special considerations and nuance to handle safely/effectively.

That being said, no one is blocked from adding such extensions to the existing APIs and for Dictionary<TK,TV> it can be implemented as efficiently as possible already (due to the CollectionsMarshal API). They can do it for any signature, whether it involves an existing value or dynamically creating a value only as needed due to cost.

[verdie-g]

Hmm I'm not able to measure correctly the impact of the is Dictionary.

---

That first benchmark gives weird results, probably because the observed iteration time is too small.

Method	Mean	Error	StdDev	Median
DictionaryGetOrAdd_KeyExists	98.99 ns	11.47 ns	31.39 ns	83.00 ns
DictionaryGetOrAdd_KeyDoesNotExists	58.56 ns	12.29 ns	32.38 ns	62.50 ns
IDictionaryGetOrAdd_KeyExists	111.77 ns	14.57 ns	39.64 ns	84.00 ns
IDictionaryGetOrAdd_KeyDoesNotExists	414.35 ns	141.92 ns	376.36 ns	333.00 ns

Code

public class Bench
{
    public Dictionary<int, int> Dictionary1 { get; set; } = [];
    public Dictionary<int, int> Dictionary2 { get; set; } = [];

    [IterationSetup]
    public void IterationSetup()
    {
        Dictionary1 = new Dictionary<int, int> { [1] = 0 };
        Dictionary2 = new Dictionary<int, int>(capacity: 1);
    }

    [Benchmark]
    public int DictionaryGetOrAdd_KeyExists()
    {
        return ConcreteGetOrAdd(Dictionary1, 1, static _ => 0);
    }

    [Benchmark]
    public int DictionaryGetOrAdd_KeyDoesNotExists()
    {
        return ConcreteGetOrAdd(Dictionary2, 1, static _ => 0);
    }

    [Benchmark]
    public int IDictionaryGetOrAdd_KeyExists()
    {
        return AbstractGetOrAdd(Dictionary1, 1, static _ => 0);
    }

    [Benchmark]
    public int IDictionaryGetOrAdd_KeyDoesNotExists()
    {
        return AbstractGetOrAdd(Dictionary2, 1, static _ => 0);
    }

    public static TValue ConcreteGetOrAdd<TKey, TValue>(
        Dictionary<TKey, TValue> dictionary,
        TKey key,
        Func<TKey, TValue> valueFactory)
        where TKey : notnull
    {
        ArgumentNullException.ThrowIfNull(dictionary);
        ArgumentNullException.ThrowIfNull(valueFactory);

        ref TValue? value = ref CollectionsMarshal.GetValueRefOrAddDefault(dictionary, key, out bool exists);
        if (!exists)
        {
            value = valueFactory(key);
        }

        return value!;
    }

    public static TValue AbstractGetOrAdd<TKey, TValue>(
        IDictionary<TKey, TValue> dictionary,
        TKey key,
        Func<TKey, TValue> valueFactory)
        where TKey : notnull
    {
        ArgumentNullException.ThrowIfNull(dictionary);
        ArgumentNullException.ThrowIfNull(valueFactory);

        if (dictionary is Dictionary<TKey, TValue> d)
        {
            ref TValue? value = ref CollectionsMarshal.GetValueRefOrAddDefault(d, key, out bool exists);
            if (!exists)
            {
                value = valueFactory(key);
            }

            return value!;
        }
        else
        {
            if (!dictionary.TryGetValue(key, out var value))
            {
                value = valueFactory(key);
                dictionary[key] = value;
            }

            return value;
        }
    }
}

---

In the second benchmark, I believe the JIT elides the type check.

Method	Mean	Error	StdDev
DictionaryGetOrAdd	52.63 ns	1.640 ns	4.731 ns
IDictionaryGetOrAdd	50.94 ns	1.517 ns	4.278 ns

Code

public class Bench
{
    private const int Iterations = 1000;

    public Dictionary<int, int> Dictionary { get; set; } = [];

    [IterationSetup]
    public void IterationSetup()
    {
        Dictionary = new Dictionary<int, int>(capacity: 1);
    }

    [Benchmark(OperationsPerInvoke = Iterations)]
    public int DictionaryGetOrAdd()
    {
        int sum = 0;
        for (int i = 0; i < Iterations; i += 1)
        {
            sum += ConcreteGetOrAdd(Dictionary, 1, static _ => 0);
        }

        return sum;
    }

    [Benchmark(OperationsPerInvoke = Iterations)]
    public int IDictionaryGetOrAdd()
    {
        int sum = 0;
        for (int i = 0; i < Iterations; i += 1)
        {
            sum += AbstractGetOrAdd(Dictionary, 1, static _ => 0);
        }

        return sum;
    }

    public static TValue ConcreteGetOrAdd<TKey, TValue>(
        Dictionary<TKey, TValue> dictionary,
        TKey key,
        Func<TKey, TValue> valueFactory)
        where TKey : notnull
    {
        ArgumentNullException.ThrowIfNull(dictionary);
        ArgumentNullException.ThrowIfNull(valueFactory);

        ref TValue? value = ref CollectionsMarshal.GetValueRefOrAddDefault(dictionary, key, out bool exists);
        if (!exists)
        {
            value = valueFactory(key);
        }

        return value!;
    }

    public static TValue AbstractGetOrAdd<TKey, TValue>(
        IDictionary<TKey, TValue> dictionary,
        TKey key,
        Func<TKey, TValue> valueFactory)
        where TKey : notnull
    {
        ArgumentNullException.ThrowIfNull(dictionary);
        ArgumentNullException.ThrowIfNull(valueFactory);

        if (dictionary is Dictionary<TKey, TValue> d)
        {
            ref TValue? value = ref CollectionsMarshal.GetValueRefOrAddDefault(d, key, out bool exists);
            if (!exists)
            {
                value = valueFactory(key);
            }

            return value!;
        }
        else
        {
            if (!dictionary.TryGetValue(key, out var value))
            {
                value = valueFactory(key);
                dictionary[key] = value;
            }

            return value;
        }
    }
}

---

Anyway, don't you think it's worth discussing the value of such extension built in .NET? Nothing prevents a developer to implement them themselves but I feel like it's so common that it could be a great QOL.

[tfenise]

What happens if the valueFactory adds(removes) some other key to(from) the dictionary?