Proposal: Dictionary<TKey, TValue>.TryAdd(TKey, TValue)

[stephentoub]

It's very common to see code that does this:

Dictionary<TKey, TValue> data = ...;
...
if (!data.ContainsKey(key))
    data.Add(key, value);

This forces the dictionary to lookup the key twice when the key isn't yet in the dictionary.

It'd be great if we had an additional method on the type:

public bool TryAdd(TKey key, TValue value);

Functionally it would behave exactly as if it were implemented like:

public bool TryAdd(TKey key, TValue value)
{
    if (ContainsKey(key)) return false;
    Add(key, value);
    return true;
}

but the implementation internally would be done more efficiently, essentially implemented by calling a variant of Insert but that returns false instead of throwing when a duplicate key is found.

[svick]

I wonder whether other functions from ConcurrentDictionary could make sense on Dictionary as convenience functions/performance improvements.

For example if you need something like MultiValueDictionary, you would normally write:

List<T> values;
if (!dict.TryGetValue(key, out values))
{
    values = new List<T>();
    dict.Add(key, values);
}

// use values here

Or you could simplify this and also potentially make it more efficient into:

var values = dict.GetOrAdd(key, _ => new List<T>());

I'm focusing on this being simpler code, because it's not clear to me whether it would actually be more efficient

Though this specific example might become moot if MultiValueDictionary ever leaves alpha.

---

Regarding TryAdd(): what about a delegate overload, for the cases where value is freshly created and expensive to create? Or does "expensive to create" imply "the overhead of the additional lookup is insignificant, so the ContainsKey()/Add() combo is sufficient"?

[richlander]

@stephentoub I suspect a lot of people would appreciate this feature. It's conceptually more intuitive.

Do you have a sense of the performance benefit? How many times would you need execute this pattern for it to matter?

[whoisj]

This is better. The entire test and set model most developers use with Dictionary<K,V> is flawed from a thread safety point of view anyways. This allows a (in theory) thread-safe way to test and set new values into the dictionary; in addition to saving on typing. 👍

What about methods like .AddOrUpdate and .TryRemove or even .TryUpdate.

I'd be willing to help code on weekends

[svick]

@whoisj It still wouldn't be thread-safe. The whole Dictionary (and pretty much any other class that wasn't designed for thread-safety) is "flawed from a thread safety point of view".

I think that you're assuming that since it's a single method call, it has to be atomic. But it doesn't have to be.

If you want thread-safe dictionary, just use ConcurrentDictionary.

[whoisj]

@svick touche. Yes "atomic" not "safe".

[VSadov]

I have definitely seen and written a lot of code doing TryAdd.
Any kind of caching or accumulating pattern where underlying storage is a Dictionary will likely do the probe-and-add.

[stephentoub]

For reference, this is what I was imagining in terms of the change:
stephentoub/coreclr@b3b0ba4

Do you have a sense of the performance benefit?

It depends on the type of the key being used, as the primary costs involved in a lookup are the computation of the hash code and the comparison of the added key against all of the key entries in the same target bucket. For a very simple key, e.g. an Int32, the improvement seems to be around 15%. For a complex key, the improvement approaches 50%, which is the theoretical maximum you'd expect from removing one of the two lookup operations.

[whoisj]

So benefits and no tradeoffs? Why is there even a discussion?

[stephentoub]

There's always a cost to new APIs. Ongoing maintenance, testing, documentation, extra code means larger binaries, more surface area means more choice which can lead to customer confusion, etc. etc.

[jbevain]

@stephentoub +1 for this change.

As a separate comment, reading the line of your diff stephentoub/coreclr@b3b0ba4#diff-333b4ea3107f8853ce3c9c3d99182a7bR196

Reminds me why I like to specify the argument's name when passing bool literals: we don't know what true means by just reading the line. I haven't seen a DO/DON'T guideline for this, it's not mentioned in the coding style document either. Is there an informal guideline for named args?

[sharwell]

This is better. The entire test and set model most developers use with Dictionary<K,V> is flawed from a thread safety point of view anyways. This allows a (in theory) thread-safe way to test and set new values into the dictionary; in addition to saving on typing.

This is very concerning, because the rationale is completely wrong. Like all operations capable of altering a Dictionary<TKey, TValue>, the new operation would require external synchronization for all reader/writer scenarios. It is not thread-safe, and it is not atomic. The sole benefit of this change is a simplification of, and slight performance improvement to¹, the following construct:

if (!dictionary.Contains(key))
  dictionary[key] = value;

¹ The performance benefit comes from only needing to look up the hash bucket once in the case an addition is required.

[sharwell]

I think the TryAdd is not the best choice for a new method on this collection type, because I believe it has limited applicability compared to an alternative:

TValue Dictionary<TKey, TValue>.GetOrAdd(TKey, TValue)

Unlike TryAdd which returns a bool, the GetOrAdd method would return the actual instance associated with a specified key in the dictionary. In addition to providing the majority of benefits offered by TryAdd, it is also applicable to cases where a dictionary is being used as a cache.

TValue existing;
if (!dictionary.TryGetValue(key, out existing))
{
  dictionary[key] = value;
  existing = value;
}

Note that while GetOrAdd is applicable to more scenarios than TryAdd, the TryAdd method would continue to provide benefits for the following case:

if (!dictionary.ContainsKey(key))
{
  dictionary[key] = value;
  // Some operation here which should not execute if the dictionary was unchanged
}

[stephentoub]

I think the TryAddValue is not the best choice

What is TryAddValue?

the TryAdd method would continue to provide benefits for the following case

That's exactly the scenario for which I was proposing it. If you look around the corefx codebase, for example, that pattern shows up a lot, and rarely in such cases does the code need the current value from the collection.

GetOrAdd method would return the actual instance associated with a specified key in the dictionary

I have no problem with a GetOrAdd method being added to Dictionary<TKey, TValue>, and I agree it's useful, which is why we added it to ConcurrentDictionary<TKey, TValue> when we introduced that type. It, however, doesn't diminish my desire for TryAdd.

[justinvp]

👍 for TryAdd.

[sharwell]

What is TryAddValue?

I meant TryAdd.

Would you be opposed to expanding this proposal to include the other conditional update methods? I've positioned them in what I see as their overall level of versatility. I don't have anything against TryAdd, it's just that I've never encountered a case where I needed to use it (as opposed to one of the methods above it), but I have encountered many cases where one of the other methods was needed and TryAdd was not a helpful replacement.

• AddOrUpdate
• GetOrAdd
• TryUpdate
• TryAdd

[stephentoub]

Would you be opposed to expanding this proposal to include the other conditional update methods?

I don't have a problem with it, but each API should be considered individually, not en mass.

The key for me is that TryAdd is a primitive operation (add this value, failing if it already exists); it's exactly like the existing Add, except with a Boolean used for the failure mode instead of an exception, such that Add can easily be built on top of TryAdd (as it is in my example implementation). You can approximate TryAdd as a compound operation using other primitive operations (find + add to avoid the exception), but that's just a workaround.

The other operations are all truly compound operations built in terms of the primitives, with most of their names highlighting their compound nature, e.g. pseudo-code:

AddOrUpdate:

public TValue AddOrUpdate<TArg>(TKey key, Func<TKey, TArg, TValue> addFactory, Func<TKey, TValue, TArg, TValue> updateFactory, TArg factoryArg)
{
    TValue value;
    return (this[key] = TryGetValue(key, out value) ?
        updateFactory(key, value, factoryArg) :
        addFactory(key, factoryArg));
}

GetOrAdd:

public TValue GetOrAdd<TArg>(TKey key, Func<TKey, TArg, TValue> factory, TArg factoryArg)
{
    TValue value;
    if (!TryGetValue(key, out value))
    {
        value = factory(key, factoryArg);
        Debug.Assert(TryAdd(key, value));
    }
    return value;
}

TryUpdate:

public bool TryUpdate(TKey key, TValue newValue, TValue oldValue)
{
    TValue existingValue;
    if (!TryGetValue(key, out existingValue) || !EquaityComparer<TValue>.Default.Equals(existingValue, oldValue))
        return false;
    this[key] = newValue;
    return true;
}

Are these useful? Of course, they implement commonly used patterns. And they should be implementable more efficiently internal to the dictionary rather than on top of it, due to being able to avoid multiple lookups. They're also more complex, take delegates that can easily lead to misuse causing perf problems in the consuming code, etc. I was quick to add TryAdd and TryUpdate to ConcurrentDictionary because for ConcurrentDictionary they're both primitive operations, where the dictionary can ensure they're implemented atomically with regards to other operations on the collection in a way that consuming code can't. And we added GetOrAdd and AddOrUpdate because they are common patterns and the code required to implement them in a concurrency-friendly way is more than what's shown above for Dictionary.

My point is simply that I'd be happy to have these helpers as members of Dictionary, but not instead of TryAdd; TryAdd is a fundamental operation for the dictionary.

I have encountered many cases where one of the other methods was needed and TryAdd was not a helpful replacement

Sure, TryAdd would not be a substitute when one of these more complicated operations is needed. Just as these more complex operations are not a good substitute when just TryAdd is needed for the (common) pattern called out earlier in this thread. The closest would be GetOrAdd, but it does unnecessary additional work, and if you need to make a decision based on whether the value was added or not, you can't easily do so with a signature like that shown... you'd need to complicate the GetOrAdd API to also return information about which path was taken, at an added expense.

[whoisj]

This is very concerning, because the rationale is completely wrong. Like all operations capable of altering a Dictionary<TKey, TValue>, the new operation would require external synchronization for all reader/writer scenarios. It is not thread-safe, and it is not atomic.

I did correct my mis-statement, it is not thread-safe but it is, however, atomic. If the implementation of TryAdd were not atomic, how could it possibly have any use? I'll agree it's not a "primitive" operation, but it is "atomic".

That said, this seems like a no brainier for addition to the library. I agree with @svick that there are likely other complex-atomic entry points in to the set that would bring value as well. I also agree with @stephentoub that this pull request should remained focused on delivering TryAdd and we should create issues for any additional methods.

[sharwell]

@whoisj atomic is used to refer to the behavior of an operation with respect to other threads. Dictionary<TKey, TValue> is not safe for concurrent use by multiple threads. If you were to ignore this fact and attempt to use Dictionary<TKey, TValue> in a concurrent environment, not only would TryAdd not be atomic, but all of the post-conditions for the methods can be broken as well. I've seen dictionaries go into a state where they are completely unusable from this.

[mburbea]

TryGetValue in the current implementation can throw an exception right now in it's current implementation when used in a multithreaded environment and that is "atomic".

As for the primitives, I feel it's unfortunate that Dictionary.Add returns void instead of a bool to indicate success or failure. TryAdd is a welcome inclusion. As for the primitives, I would greatly want a GetOrAdd, I often do the standard caching pattern.

TValue value;
if (cache.TryGetValue(key, out value))
{
     cache.Add(key, GetNewValue(key));
}

And while I could use the concurrent for the primitive, for a single threaded job it's overkill to use that collection.

[dotnetchris]

GetOrAdd should definitely be added to IDictionary and implemented across the collections. I find GetOrAdd to be so valuable I'll use the ConcurrentDictionary just to have it.

[JonHanna]

The concurrent dictionary operations that take a Func are only atomic as observed by threads operating on the dictionary, not from within the Func.
As for the suggestion wrt dictionary, if nothing else it sounds like fun to write ;)

[rickbrew]

Dictionary<TKey, TValue> isn't sealed, but the core methods aren't virtual (unlike, for instance, Collection<T>.InsertItem). Therefore this idea seems safe, and I would definitely make use of it.

[JonHanna]

@dotnetchris

GetOrAdd should definitely be added to IDictionary

That though would be a breaking change in terms of every single implementation of the interface outside of corefx.

On a related note, since Dictionary is in mscorlib and used there a lot, should this be under coreclr?

[JonHanna]

@stephentoub

I don't have a problem with it, but each API should be considered individually, not en mass.

In cognitive terms, there could be a bigger change to add some of the methods that ConcurrentDictionary has that Dictionary currently does not, than to add them all. It's easy to get "Dictionary now has all the methods ConcurrentDictionary has".

In terms of implementation, https://github.com/hackcraft/coreclr/commit/1a982053ae39ee0e418d370fdee3497ecefd0e5a takes a stab at that.

[jamesqo]

A little late, but +1 for TryAdd. I found a lot of calls that looked like if (!dict.ContainsKey(...)) dict.Add(...) recently, so adding this will help a lot of code run a little faster.

[terrajobst]

We did a quick review on this. The only open question is whether that's the only type of API that is essentially borrowed from ConcurrenctDicationary<K,V> that would make sense here. After taking a quick look, I don't think there are any more APIs besides the one proposed by @sharwell, which is GetOrAdd.

However, we should probably add similar APIs to SortedList<T>.

Otherwise, no concerns from my side.

[joshfree]

@terrajobst does this mean you can tag this as "feature approved"?

[jamesqo]

Is there a formal specification of what is being proposed? I might grab this if I have time but it seems unclear from the discussion exactly which out of TryAdd, GetOrAdd, AddOrUpdate, and TryUpdate were approved and what parameters they should take.

[danmoseley]

@safern can you please talk to @terrajobst to get explicit what the API board actually approved.

[safern]

@danmosemsft yes, I'll talk to @terrajobst and will post the API approved so that @jamesqo can grab this!

[danmoseley]

Then we should open an issue to use it. The crude regex if +\(!([^.]+)\.ContainsKey\(([^)]+)\)\)[ {]*\n[ {]*\1.Add\(\2, finds 4 uses outside of the tests (I would have expected more -- Find Refs on ContainsKey would find them)

if +\(!([^.]+)\.ContainsKey\(([^)]+)\)\)[ {]*\n[ {]+\1\[ to find the indexing variation does not hit anything.

[jamesqo]

finds 4 uses outside of the tests (I would have expected more -- Find Refs on ContainsKey would find them)

I think I found like 50+ last year when I grepped the repo for ContainsKey, looking for places that had a pattern like if (dict.ContainsKey(key)) { T value = dict[key]; ... } to replace them with TryGetValue. I manually sifted through all of the usages and I remember only ~4 of them could use TryGetValue, all the rest were doing if (!dict.ContainsKey(key)) { dict.Add(key, ...); }.

[safern]

I talked to @terrajobst and the approved API was:

public bool TryAdd(TKey key, TValue value)

If we would like GetOrAdd, AddOrUpdate, and TryUpdate then we should either update this API proposal and go through the review process again, or open a new issue proposing those three APIs.

/cc @jamesqo @danmosemsft

[danmoseley]

Anyone interested in taking this one, so we cna get it in for 2.0? Seems like it shouldn't take too long.

[danmoseley]

@sepidehms as you have a few cycles, do you want to code this up, since IMO it would be nice to squeeze this into 2.0?

[jamesqo]

@danmosemsft I'm taking care of it right now.

[IanKemp]

I'm not seeing TryAdd in either Standard 2.0 or Framework 4.7.2 - any timeline on when we can expect this method in those?

[ViktorHofer]

This will probably be available in .NET Standard vNext.

[IanKemp]

@ViktorHofer vNext = 2.2 or 3.0?

[ViktorHofer]

Not decided yet.

[jnm2]

@IanKemp follow https://github.com/dotnet/standard/issues/833 for updates on that.

[kdg3737]

I recently had a use case for a TryAdd where I needed to update an existing value in the dictionary in case the key already existed. Thought I'd share the solution since the proposals here don't cover this:

        [Test]
        public void ExtendedDictionary_TryAdd() {
            ExtendedDictionary<string, int> dic = new ExtendedDictionary<string, int>();

            dic.Add("bla", 1);
            int val = 2;
            bool addok = false;
            addok = dic.TryAdd("blo", val, (ev, fcb) => {
                val = ev;
                addok = false;
            });
            Assert.AreEqual(2, val);
            Assert.AreEqual(true, addok);
            val = 37;
            addok = dic.TryAdd("bla", val, (ev, fcb) => {
                val = ev;
                fcb(38);
            });
            Assert.AreEqual(1, val);
            Assert.AreEqual(true, addok);
            Assert.AreEqual(38, dic["bla"]);
            addok = dic.TryAdd("bla", val, (ev, fcb) => {
                val = ev;
            });
            Assert.AreEqual(38, val);
            Assert.AreEqual(false, addok);
            Assert.AreEqual(38, dic["bla"]);
        }

The TryAdd method:

        public bool TryAdd(TKey key, TValue value, Action<TValue, Action<TValue>> cb) {
            bool ret = true;
            Insert(key, value, true, (existingval, forcecb) => {
                ret = false;
                cb(existingval, (nv) => {
                    ret = true;
                    forcecb(nv);
                });
            });

            return ret;
        }

The changes to the Insert method (copied from Dictionary.cs, mostly):

        private void Insert(TKey key, TValue value, bool add, Action<TValue, Action<TValue>> alreadyExistsCallback = null) {

            if (key == null) {
                ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
            }

            if (buckets == null) Initialize(0);
            int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
            int targetBucket = hashCode % buckets.Length;

#if FEATURE_RANDOMIZED_STRING_HASHING
            int collisionCount = 0;
#endif

            for (int i = buckets[targetBucket]; i >= 0; i = entries[i].next) {
                if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) {
                    if (add) {
                        
                        if (alreadyExistsCallback != null) {
                            bool shouldreturn= true;
                            alreadyExistsCallback(entries[i].value, (nv) => {
                                value = nv;
                                shouldreturn = false;
                            });
                            if (shouldreturn)
                                return;
                        }
                        else
                            ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);
                    }
                    entries[i].value = value;
                    version++;
                    return;
                }

#if FEATURE_RANDOMIZED_STRING_HASHING
                collisionCount++;
#endif
            }
            int index;
            if (freeCount > 0) {
                index = freeList;
                freeList = entries[index].next;
                freeCount--;
            }
            else {
                if (count == entries.Length) {
                    Resize();
                    targetBucket = hashCode % buckets.Length;
                }
                index = count;
                count++;
            }

            entries[index].hashCode = hashCode;
            entries[index].next = buckets[targetBucket];
            entries[index].key = key;
            entries[index].value = value;
            buckets[targetBucket] = index;
            version++;

#if FEATURE_RANDOMIZED_STRING_HASHING
 
#if FEATURE_CORECLR
            // In case we hit the collision threshold we'll need to switch to the comparer which is using randomized string hashing
            // in this case will be EqualityComparer<string>.Default.
            // Note, randomized string hashing is turned on by default on coreclr so EqualityComparer<string>.Default will 
            // be using randomized string hashing
 
            if (collisionCount > HashHelpers.HashCollisionThreshold && comparer == NonRandomizedStringEqualityComparer.Default) 
            {
                comparer = (IEqualityComparer<TKey>) EqualityComparer<string>.Default;
                Resize(entries.Length, true);
            }
#else
            if(collisionCount > HashHelpers.HashCollisionThreshold && HashHelpers.IsWellKnownEqualityComparer(comparer)) 
            {
                comparer = (IEqualityComparer<TKey>) HashHelpers.GetRandomizedEqualityComparer(comparer);
                Resize(entries.Length, true);
            }
#endif // FEATURE_CORECLR
 
#endif

        }

[danmoseley]

@kdg3737 would SlimDictionary work for you? (code, package)

[danmoseley]

BTW, I recommend that you open a new issue if you want to discuss, typically posts on closed issues are overlooked.

[kdg3737]

That's a nice trick with the ref returns Dan! But it has an issue, how do you distinguish between a missing key and one that is in the DictionarySlim but has a default value? Look at this test:

        [Test]
        public void DictionarySlim() {
            DictionarySlim<string, int> dicv = new DictionarySlim<string, int>();

            bool present = dicv.TryGetValue("bla", out _);
            Assert.AreEqual(false, present); // nope, not there
            ref int x = ref dicv.GetOrAddValueRef("bla");
            Assert.AreEqual(0, x); // the key wasn't found or the value was 0 ???
            x = 0; // assign it
            present = dicv.TryGetValue("bla", out _);
            Assert.AreEqual(true, present); // there it is
            x = ref dicv.GetOrAddValueRef("bla");
            Assert.AreEqual(0, x); // the key wasn't found or the value was 0 ???
        }

Also where are the indexers?

[danmoseley]

how do you distinguish between a missing key and one that is in the DictionarySlim but has a default value

@kdg3737 as you point out, GetOrAddValueRef does not provide a way to know whether it added the value or not (although you can figure it out if the value is not default). If you need to know this, you must use TryGetValue or ContainsKey. Certainly we could have another out parameter for this but it would likely require that the JIT generate less efficient code.

There are no indexers because they are purely convenience members and this is "slim". There is value in keeping a generic type small because its code is generated separately for every differently sized type that it is instantiated over. For Dictionary<K,V> this can be many types, for example.

The type is in corefxlab because the API is not final. If you have feedback on the API, please do open an issue there. You may want to look at the discussion in the original PR first: dotnet/corefxlab#2458

If the type proves to be widely useful, and we are comfortable with the API, it is may be a candidate for moving into the product.

[kdg3737]

That makes sense for your 'slim' Dictionary, but the topic here is about the regular Dictionary which as-still-is requires a double lookup for a contains-add. The smallest devices we run .net/mono on have 4GB ram these days so it's unlikely we'd ever need or want this 'slim' variant, even with hundreds of different jitted Dictionary types. I'm way more interested in saving CPU cycles (and development time, I do use dictionaries pretty much everywhere) than saving a couple of kilobytes volatile memory which I have in abundance anyway and are consuming power no matter if I use them or not. Functionality beats memory-efficiency, no indexers and the issue I mentioned above are a no-go for me and I expect many developers would agree.

Of course it is nice to see MS care about memory usage and to have this DictionarySlim option. This actually reminds me of another Dictionary I once wrote for large string-keys that would be hashed before putting them in the Dictionary to save on memory (losing IEnumerable in the process). Anyways, I feel I've said what I wanted to, thanks for this conversation and good luck with your work on corefxlab.

[danmoseley]

@kdg3737 I see, I was confused because your example was DictionarySlim. I think if this scenario is important to you, I would open a new issue in this repo to trigger further discussion.

Because of the "code bloat" mentioned in my comment above, we're careful about adding more code into Dictionary, but we can talk about it.