Add RemoveIfValue to ConcurrentDictionary

[CornedBee]

EDIT by: @scalablecory

@CornedBee I'd like to get this suggestion to a point where it can be reviewed as a proposal. What do you think of this?

@safern what do you think?

Rationale and Usage

ConcurrentDictionary has an implementation of "remove if" hidden away inside of the private ICollection<T>.Remove. Usage of this looks like:

void DecrementCount(ConcurrentDictionary<string, int> dict, string key)
{
    while(true)
    {
        int current = dict[key];

        if(current != 1)
        {
            if(dict.TryUpdate(key, current - 1, current))
            {
                return;
            }
        }
        else
        {
	    ICollection<KeyValuePair<string, int>> col = dict;
            if(col.Remove(new KeyValuePair<string, int>(key, current)))
            {
                return;
            }	
        }
    }
}

This proposal is to expose this existing feature in a more friendly and discoverable API. New usage:

void DecrementCount(ConcurrentDictionary<string, int> dict, string key)
{
    while(true)
    {
        int current = dict[key];

        if(current != 1)
        {
            if(dict.TryUpdate(key, current - 1, current))
            {
                return;
            }
        }
        else
        {
            if(dict.TryRemoveIf(key, current))
            {
                return;
            }	
        }
    }
}

The discoverability issue:

• https://stackoverflow.com/q/8723585
• https://stackoverflow.com/q/27297326
• https://stackoverflow.com/q/39516516
• https://stackoverflow.com/q/39679779
• @stephentoub's https://devblogs.microsoft.com/pfxteam/little-known-gems-atomic-conditional-removals-from-concurrentdictionary/

Proposed API

class ConcurrentDictionary<>
{
    public bool TryRemoveIf(TKey key, TValue comparisonValue);
}

Approved API

class ConcurrentDictionary<>
{
    public bool TryRemove(KeyValuePair<TKey key, TValue> keyValuePair);
}

Details

• This brings parity with TryUpdate.
• Unfortunately we have a wart: the existing TryRemove does not compare a value, but TryUpdate does. TryRemoveIf will therefor have naming inconsistent with one of them.

Open Questions

• Should we make the existing method public? Not sure if reasonable API signature.
• It could be useful to return a type other than bool that indicates one of: removed, key not found, or value not found.
• It could also be useful to return the original value in an out param.
  • This would avoid rehashing in a spin loop. Existing implementation inside of ConcurrentDictionary has spin loops that do this, so the feature already exists and it's clearly a useful optimization, but avoiding rehashing in general is a larger discussion.
  • It would also allow some cleanup if the value removed is "equal" but not the same instance, though I'm not sure how common this is.
• This API, along with the existing TryUpdate, has a non-obvious complication in that it only uses the default comparer for a type: the example above would not work as the user intended if MyState is a class that hasn't overridden Equals. It may be worth trying to make this easier to use.
  • There's worry that TryRemoveIf's use case has greater exposure to misuse, and it may be worth keeping it hidden to avoid that.
• Do we want to support custom comparers for values? I can't see a big use case for this, and if we need more flexibility here I would prefer a general TryRemoveIf(TKey key, Func<TKey, TValue, object, bool> comparer, object state).

[ianhays]

This seems like a reasonable proposal. I wonder if it might be better just to make the ICollection remove public instead of adding a new API though.

[yizhang82]

I just ran into the exact same problem and my workaround is the same - just cache ICollection and use ICollection.Remove.

One problem with the current ICollection.Remove implementation is that it always uses the default comparer, which isn't always what one would want.

 bool valuesMatch = EqualityComparer<TValue>.Default.Equals(oldValue, curr._value);

So adding an TryRemoveIf API with a new overload and also allowing passing a value comparer in constructor would be helpful.

[scalablecory]

This would bring feature parity with ConcurrentDictionary.TryUpdate, and would be useful.

[scalablecory]

[ moved to top comment ]

[safern]

I agree with @ianhays old comment, I think to make it less confusing, wouldn't make sense to just make ICollection.Remove(KeyValuePair<TKey, TValue> public?

That would also make it consistent with other collections and APIs in the framework where the way to remove is through a Remove API which returns a bool.

@scalablecory thoughts on that?

[scalablecory]

@safern Dictionaries have avoided operating on KeyValuePair, and ConcurrentDictionary has a Try theme going on. I assume these are the reasons Remove is currently explicitly implemented -- it would not be consistent.

[safern]

I agree it has avoided to operate onKeyValuePair but in Dictionary we don’t have a TryRemove, we have a Remove(TKey)

https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.dictionary-2.remove?view=netframework-4.8

I agree the TryRemove in ConcurrentCollection broke this consistency, but TryRemoveIf was confusing at first sight, because there is no condition, basically the if is referring to, if the TKey contains a TValue, which at the end Remove(KeyValuePair<TKey, TValue>) speaks for itself. That is why IMHO the latter is the one that fits best for this scenario.

Also Dictionary exposes a bool Remove(TKey, TValue) which would be my top choice since it doesn’t operate on KeyValuePair.

https://apisof.net/catalog/System.Collections.Generic.Dictionary%3CTKey,TValue%3E.Remove(TKey,TValue)

Since ConcurrentDictionary has already introduced the Try pattern, we could just add an extra override of TryRemove without the if that accepts both the TKey and TValue

@stephentoub who has experience with ConcurrentCollections might have insights as well.

[safern]

Marking as ready for review, and let's discuss the naming and parameters that it will take in API Review.

[stephentoub]

Dictionaries have avoided operating on KeyValuePair

Really? It's part of the IDictionary<> interface.

TryRemoveIf was confusing at first sight

I agree... the If is confusing. Why can't it just be an overload of the existing TryRemove?

Since ConcurrentDictionary has already introduced the Try pattern, we could just add an extra override of TryRemove without the if that accepts both the TKey and TValue

That would be my preference.

if(dict.TryGetValue("foo", out MyState state) && state.Count == 0) dict.TryRemoveIf("foo", state);

All that said, this example used to motivate this API has a race condition: state.Count could change away from 0 after the check and before the TryRemove call. No?

[bartonjs]

Why can't it just be an overload of the existing TryRemove?

TryRemove(key, value) vs TryRemove(key, out value) have very different meanings (one is double-input conditional, one is single-input conditional). Do we have a similar place where we have an overload differing by ref-ness with a similar complexity change? It sort of makes sense when it's "more" complicated instead of "differently" complicated: TryRemove(TKey key, TValue matchValue, out TValue existingValue).

Based on the sample usage with the double-dip, it seems like it really wants a predicate overload:

bool TryRemove(TKey key, Predicate<TValue> predicate, out TValue existingValue);

...

if (dict.TryRemove("foo", s => s.Count == 0, out MyState state))
{
    // Yep
}
else if (state != null)
{
    // Predicate didn't match
}
else
{
    // Key didn't match (or key stored null)
}

[stephentoub]

it seems like it really wants a predicate overload

That predicate would need to be invoked while holding one of the dictionary's locks. We've stayed away from that as it can easily lead to deadlock.

[bartonjs]

Wouldn't AddOrUpdate, when invoking updateValueFactory, be in the same state? (Perhaps it's "yes, and it leads to deadlock all the time")

[stephentoub]

Wouldn't AddOrUpdate, when invoking updateValueFactory, be in the same state? (Perhaps it's "yes, and it leads to deadlock all the time")

AddOrUpdate just uses TryGetValue/TryAdd/TryUpdate in a loop, explicitly avoiding invoking the delegates while holding the dictionary's locks.

[scalablecory]

Really? It's part of the IDictionary<> interface.

Outside of explicitly implemented members, we have no methods that mutate a dictionary taking a KeyValuePair.

Doesn't mean it can't be done, but it would not be look right.

[scalablecory]

this example used to motivate this API has a race condition: state.Count could change away from 0 after the check and before the TryRemove call. No?

It depends on the type of state. I call this out in open questions. Note, TryUpdate and ICollection.Remove have the same issue -- this isn't immediately obvious to users.