How to achieve remove_if functionality in .NET ConcurrentDictionary

Question

I have a scenario where I have to keep reference counted object for given key in the ConcurrentDictionary, if reference count reaches 0, I want to delete the key. This has to be thread safe hence I am planning to use the ConcurrentDictionary.

Sample program as follows. In the concurrent dictionary, I have key and value , the value is KeyValuePair which holds my custom object and reference count.

ConcurrentDictionary<string, KeyValuePair<object, int>> ccd = 
    new ConcurrentDictionary<string, KeyValuePair<object, int>>();

// following code adds the key, if not exists with reference 
// count   for  my custom object to 1
// if the key already exists it increments the reference count

var addOrUpdateValue = ccd.AddOrUpdate("mykey",
    new KeyValuePair<object, int>(new object(), 1),
    (k, pair) => new KeyValuePair<object, int>(pair.Key, pair.Value + 1));

Now I want a way to remove the key when the reference count reaches to 0. I was thinking , remove method on ConcurrentDictionary which takes key and predicate , removes the key if the predicate return 'true'. Example.

ConcurrentDictionary.remove(TKey, Predicate<TValue> ). 

There is no such method on ConcurrentDictionary, question is how to do the same in thread safe way ?.

Answer 1

.NET doesn't expose a RemoveIf directly, but it does expose the building blocks necessary to make it work without doing your own locking.

ConcurrentDictionary implements ICollection<T>, which has a Remove that takes and tests for a full KeyValuePair instead of just a key. Despite being hidden, this Remove is still thread-safe and we'll use it to implement this. One caveat for this to work is that Remove uses EqualityComparer<T>.Default to test the value, so it must be equality comparable. Your current one is not, so we'll re-implement that as such:

struct ObjectCount : IEquatable<ObjectCount>
{
    public object Object { get; }
    public int Count { get; }

    public ObjectCount(object o, int c)
    {
        Object = o;
        Count = c;
    }

    public bool Equals(ObjectCount o) =>
       object.Equals(Object, o.Object) && Count == o.Count;

    public override bool Equals(object o) =>
       (o as ObjectCount?)?.Equals(this) == true;

    // this hash combining will work but you can do better.
    // it is not actually used by any of this code.
    public override int GetHashCode() =>
       (Object?.GetHashCode() ?? 0) ^ Count.GetHashCode();
}

And finally, we'll define a method to increment/decrement counts from your dictionary:

void UpdateCounts(ConcurrentDictionary<string, ObjectCount> dict, string key, int toAdd)
{
    var addOrUpdateValue = dict.AddOrUpdate(key,
        new ObjectCount(new object(), 1),
        (k, pair) => new ObjectCount(pair.Key, pair.Value + toAdd));

    if(addOrUpdateValue.Count == 0)
    {
        ((ICollection<KeyValuePair<string, ObjectCount>>)dict).Remove(
            new KeyValuePair<string, ObjectCount>(key, addOrUpdateValue));
    }
}

The value for that key might be changed between the calls of AddOrUpdate and Remove, but that doesn't matter to us: because Remove tests the full KeyValuePair, it will only remove it if the value hasn't changed since the update.

This is the common lock-free pattern of setting up a change and then using a final thread-safe op to safely "commit" the change only if our data structure hasn't been updated in the meantime.

Answer 2

You can't use a ConcurrentDictionary because it does not expose its internal locking. Your increment must occur under the same lock that controls the add (a simple interlocked add is not enough as a concurrent thread may remove the object before you increment the count). Similarly, the decrement must acquire the lock to be able to safely remove it if it reaches 0 count. What this spell is that you must use a dictionary for which you control the locking explicitly.

Answer 3

I had a similar issue - having multi-threaded piece of code, I needed to count the number of times I've accessed certain type of resource. In other words - I need to find distribution of access to different resource types.

The way I've solved it:

Create store for your counts:

ConcurrentDictionary<string, StrongBox<int>> _counts = new ConcurrentDictionary<string, StrongBox<int>>();

When the resource is accessed, increment access count:

Interlocked.Increment(ref _counts.GetOrAdd(_resourceType, new StrongBox<int>(0)).Value);

In your case you'll have to take care of decrement as well.

I know it's not a full solution to the problem you've presented, and it's not a direct answer to it, but I hope it can be useful to someone.

Answer 4

Currently (.NET 6) the ConcurrentDictionary<K,V> class has no API available that allows to update or remove a key, based on a user-supplied delegate. This functionality can be achieved laboriously by using the methods TryGetValue, TryUpdate and TryRemove in a loop:

string key = "mykey";
while (true)
{
    if (!ccd.TryGetValue(key, out KeyValuePair<object, int> existingValue))
        break; // The key was not found

    // Create new value based on the existing value
    KeyValuePair<object, int> newValue = KeyValuePair
        .Create(existingValue.Key, existingValue.Value - 1);

    if (newValue.Value > 0)
    {
        if (ccd.TryUpdate(key, newValue, existingValue))
            break; // The key was updated successfully
    }
    else
    {
        if (ccd.TryRemove(KeyValuePair.Create(key, existingValue)))
            break; // The key was removed successfully
    }

    // We lost the race to either TryUpdate or TryRemove. Try again.
}

In case there is no contention, the loop will exit after a single iteration.

I have made a proposal on GitHub, for an API TryUpdateOrRemove that would fill this void. In case this proposal is accepted, the above code could be reduced to this:

ccd.TryUpdateOrRemove(key, (_, existingValue) =>
{
    KeyValuePair<object, int> newValue = KeyValuePair
        .Create(existingValue.Key, existingValue.Value - 1);
    if (newValue.Value > 0) return (UpdateRemoveResult.Update, newValue);
    return (UpdateRemoveResult.Remove, default);
});

In case you like this proposal, make sure to give it an upvote on GitHub. Not only it's less code, but it should be also more efficient because the key would be hashed only once.

Answer 5

This will give you a dictionary that tracks the count of an item if it is not zero and has no item when it is 0. The increment and decrement are fairly straightforward. The Remove empty node looks odd, but preserves accurate count even if adds and removes come in out of order. The decrement initial value of -1, again is to handle when calls come in out of order.

Concurrent programming is weird sometimes.

   private void Increment(string key)
    {
       var result =  ccd.AddOrUpdate(key,new KeyValuePair<object, int>(new object(), 1),(k, pair) => new KeyValuePair<object, int>(pair.Key, pair.Value + 1));
       RemoveEmptyNode(key, result);

    }

    private void Decrement(string key)
    {
        var result = ccd.AddOrUpdate(key, new KeyValuePair<object, int>(new object(), -1), (k, pair) => new KeyValuePair<object, int>(pair.Key, pair.Value - 1));
        RemoveEmptyNode(key, result);
    }

    private void RemoveEmptyNode(string key, KeyValuePair<object, int> result)
    {
        if (result.Value == 0)
        {
            KeyValuePair<object, int> removedKeyValuePair;
            if (ccd.TryRemove(key, out removedKeyValuePair))
            {
                if (removedKeyValuePair.Value != 0)
                {
                    ccd.AddOrUpdate(key, removedKeyValuePair,
                        (k, pair) => new KeyValuePair<object, int>(key, pair.Value + removedKeyValuePair.Value));
                }
            }
        }
    }
}