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

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.

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"?

@stephentoub

@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?

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

@whoisj

@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.

@svick

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

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.

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.

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

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.

@stephentoub

@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?

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.

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
}

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.

👍 for TryAdd.

@ViktorHofer

@ViktorHofer vNext = 2.2 or 3.0?

Not decided yet.

@IanKemp

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

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

        }

@kdg3737

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

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

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?

@kdg3737

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.

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.

@kdg3737

@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.

Navigation Menu

Repository navigation

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

46 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

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

Description

Activity

svick commented on Jun 5, 2015

richlander commented on Jun 5, 2015

whoisj commented on Jun 5, 2015

svick commented on Jun 5, 2015

whoisj commented on Jun 5, 2015

VSadov commented on Jun 5, 2015

stephentoub commented on Jun 7, 2015

whoisj commented on Jun 7, 2015

stephentoub commented on Jun 7, 2015

jbevain commented on Jun 8, 2015

sharwell commented on Jun 8, 2015

sharwell commented on Jun 8, 2015

stephentoub commented on Jun 8, 2015

justinvp commented on Jun 9, 2015

46 remaining items

IanKemp commented on Jul 19, 2018

ViktorHofer commented on Jul 19, 2018

jnm2 commented on Jul 19, 2018

kdg3737 commented on Jun 26, 2019

danmoseley commented on Jul 16, 2019

danmoseley commented on Jul 16, 2019

kdg3737 commented on Jul 17, 2019

danmoseley commented on Jul 17, 2019

kdg3737 commented on Jul 17, 2019

danmoseley commented on Jul 17, 2019

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions