Runtime: API Proposal: Dictionary<K,V>.Update to replace a value without double-lookup

[Joe4evr]

Background and Motivation

I have a class that implements copy-on-write semantics:

public partial class ValueWrapper
{
    // Returns a new instance with
    // the provided value appended
    public ValueWrapper Add(string value);
}

This class is used as a Dictionary value, but currently it requires a double lookup in order perform an update operation:

var wrapper = _entries[key];
_entries[key] = wrapper.Add(value);

It certainly feels like something could be done to avoid the second indexing operation there.

Proposed API

26848, who had pretty much the same problem, suggested copying the signature of ConcurrentDictionary<K,V>.AddOrUpdate. This seems a bit excessive, so I propose a simpler version:

public partial class Dictionary<TKey, TValue>
{
+    public void Update(TKey key, Func<TKey, TValue, TValue> updateValueFactory);
}

This would throw KeyNotFoundException if the provided key doesn't exist.

Usage Examples

_entries.Update(key, (_, wrapper) => wrapper.Add(value));

Alternative Designs

I have tried DictionarySlim from Microsoft.Experimental.Collections, and while its GetOrAddValueRef(TKey) method would work for me for the updating scenario, that type lacks some other things that I'm depending on from the normal Dictionary, namely:

• No copy constructor to pre-fill a new instance with all the keys/values of another instance

* It doesn't expose its collection of Keys which I happen to use as well

A functional alternative (though not as safe) would be a ref access method, as proposed at #27062. It wouldn't be an elegant one-liner, but it would obviate the need for delegate allocation(s).

ref var wrapper = ref CollectionMarshal.ValueRef(_entries, key); // Current proposed method
wrapper = wrapper.Add(value));

Risks

This is a purely additive change, so it should have no risks on existing code.

[msftbot[bot]]

Tagging subscribers to this area: @eiriktsarpalis
Notify danmosemsft if you want to be subscribed.

[YairHalberstadt]

Personally, I would appreciate all the ConcurrentDictionary methods on Dictionary:

AddOrUpdate
GetOrAdd
TryRemove
TryUpdate
TryAdd

However, I think it might make more sense to add them as extension methods/DIMs on IDictionary.

[jnm2]

@YairHalberstadt If they were added as extension methods, I don't think they'd be able to avoid the double lookup.

[YairHalberstadt]

@jnm2 I care less about the double lookup and more about convenience

[eiriktsarpalis]

This seems a bit excessive, so I propose a simpler version

Why do you think it is excessive? The Update method doesn't seem to solve the double lookup issue in the general case, since you'd need to check that the key is populated.

[jnm2]

@eiriktsarpalis The Update method would first look up the internal slot and throw KeyNotFoundException if none exists, then it would invoke the callback to obtain a value and assign it to the slot without a second lookup.

[eiriktsarpalis]

Duplicate of #15059

[Joe4evr]

@eiriktsarpalis I disagree. None of what's proposed in #15059 would allow writing a new value based on an existing value without the double-lookup problem. An update in my scenario requires an existing value (and bubble up the KeyNotFoundException if there is no value at the provided key). GetOrAdd can't buy me that as far as I can see.

[eiriktsarpalis]

Fair point, however there is significant overlap between the two requests and as such it's best that we consolidate into one conversation. @layomia is already working on prototyping an implementation of #15059 so it might make sense to evaluate an update variant at the same time.

FWIW my opinion is we should be considering an AddOrUpdate variant instead of this. It has fewer failure modes and is consistent with what ConcurrentDictionary is offering.