Runtime: Proposal: Add an atomic ToArray + Clear method to ConcurrentDictionary<TKey, TValue>

[smourier]

Rationale and usage

ConcurrentDictionary<TKey, TValue> is heavily used in thread-safe scenarios (memory cache, temp storage, etc.). There are times when you wish to clear instances of a thread-safe dictionary and get the values, at the same time, in a single atomic operation.

Here is an example in a disposable class that contains an internal dictionary.

public class MyClass : IDisposable
{
    private ConcurentDictionary<k,v> _dic ...;

    public void Dispose()
    {
        var objs = _dic.ToArray();
        // race condition can happen here
        _dic.Clear();
        foreach (var obj in objs)
        {
            obj.Dispose();
        }
    }
}

Here is another example with a class that uses the dictionary as an event queue:

public class EventQueues
{
    private ConcurentDictionary<k,v> _dic ...;

    public void AddEvent(MyEvent evt)
    {
        ...
        _dic[evt.key] = evt;
        ...
    }

    public void SendEvents()
    {
        var events = _dic.ToArray();
        // race condition can happen here
        _dic.Clear();

        // send events
        Task.Run(() =>
        {
          foreach (var evt in events)
          {
              evt.Send(...);
          }
        });
    }
}

Of course it's possible for the user to implement an atomic ToArray + Clear operation using a lock, however it means there will at least be 3 locks:

• for the ToArray+Clear methods wrap
• for the ToArray method call (internal to ConcurrentDictionary)
• for the Clear method call (internal to ConcurrentDictionary).

Another way to do this is to swap the _dicmember with the new one, like this:

    public void Dispose()
    {
        var dic = _dic;
        _dic = new ConcurentDictionary<k,v>(...);

        var objs = dic.ToArray();
        dic.Clear();
        foreach (var obj in objs)
        {
            obj.Dispose();
        }
    }

But it looks awkward (maybe it's a personal opinion?), plus it prevents the user to mark _dicas a readonlymember. And, is it really atomic?

Proposed API

public class ConcurrentDictionary<TKey, TValue>
{
+    public void KeyValuePair<TKey, TValue>[] RemoveAll();
}

I've used the same name ("Remove" as with the TryRemove existing method. I'm wondering if a signature like TryRemoveAll(out KeyValuePair<TKey, TValue>[] value) would make any sense?

But, it could also be

public class ConcurrentDictionary<TKey, TValue>
{
+    public void Clear(out KeyValuePair<TKey, TValue>[] values);
}

This one could cause (rare) regressions if people do reflection on the "Clear" name.

Reference implementation

An implementation could be this:

    public KeyValuePair<TKey, TValue>[] RemoveAll()
    {
        int locksAcquired = 0;
        try
        {
            AcquireAllLocks(ref locksAcquired);

            // this is copied from ToArray() code
            // we could make a private inlinable lock-free function common to ToArray() and this one
            int count = 0;
            checked
            {
                for (int i = 0; i < _tables._locks.Length; i++)
                {
                    count += _tables._countPerLock[i];
                }
            }

            if (count == 0)
            {
                return Array.Empty<KeyValuePair<TKey, TValue>>();
            }

            KeyValuePair<TKey, TValue>[] array = new KeyValuePair<TKey, TValue>[count];
            CopyToPairs(array, 0);

            // this is copied from Clear() code
            // we could make a private inlinable lock-free function common to Clear() and this one
            Tables newTables = new Tables(new Node[DefaultCapacity], _tables._locks, new int[_tables._countPerLock.Length]);
            _tables = newTables;
            _budget = Math.Max(1, newTables._buckets.Length / newTables._locks.Length);

            return array;
        }
        finally
        {
            ReleaseLocks(0, locksAcquired);
        }
    }    

[MarcoRossignoli]

If you aren't in a hot path, could you simply set old dic in a tmp and re-create _dic = new ConcurrentDictionary<K,V>() and after iterate on tmp to call dispose , right?
However code looks strange to me, I mean if you are in a Dispose and you want to cleanup objects you have to be sure no new item inside it, so you could null reference and do some null check and handle with ObjectDisposedException on add/get.

[smourier]

This code was just an example. I'm not looking for solutions, as there are many, but for something builtin.

[MarcoRossignoli]

This code was just an example

Ah ok sorry!

[Wraith2]

Dispose method aside doesn't the general premise or Marco's post still work? if you want to ensure that the view of the dictionary you have is the latest version you need to prevent other callers from modifying it which requires some form of lock or block.

Whether that lock or block is internal or external to the dictionary only changes who maintains the code, in which case why is the bcl containing the lock better than the user doing so when both can achieve the same goal?

[smourier]

Using a temp does not always work because most of the time my dictionaries are also marked as readonly.

Using ConcurrentDictionary is cool because I don't have to use any lock in my code. And that's the whole point of it. Adding a Monitor/lock just for that is sad IMHO while I often need it, and it seems a natural function of such a dictionary. For example, TryRemovegives out back the object if it was removed, so we could also have similar semantics for the clear (which removes everything):

public bool TryClear(out KeyValuePair<TKey, TValue>[] array);

I would be happy with such a method too.

It could even be an async function. Anyway, I don't presume how BCL would implement that, but I'm hoping it can be better than just an external and additional lock.

[Clockwork-Muse]

Hrm. I'd probably go with:

public KeyValuePair<TKey, TValue>[] RemoveAll();

It always succeeds, after all (as does Clear()) - if there's no values in the dictionary it just returns an empty array.

However, as others have pointed out, this doesn't absolve you of "external" race conditions.

[smourier]

I don't see any RemoveAll method on ConcurrentDictionary.

[Clockwork-Muse]

Uh, no, I meant for an API proposal.

[svick]

Do you have a realistic use case where this would be useful?

[smourier]

The use case is get all the items and clear in an atomic way, quite the same use case as TryRemove but for the whole collection. Calling it in Dispose is indeed one use case, but every time I need a thread-safe accumulator, like a log which is dumped periodically, a mailbox, a list of "tasks" to execute, something that's emptied periodically, etc., I add some extra lock or interlocked exchange (like marco's suggestion) code.

[safern]

@smourier could you please submit a formal API proposal so that we can run it through API Review and then decide whether if it makes sense or not? This are the guidelines to do so: https://github.com/dotnet/corefx/blob/master/Documentation/project-docs/api-review-process.md

Here is an example: https://github.com/dotnet/corefx/issues/35938

[smourier]

Done: dotnet/corefx#37924

[safern]

Thanks, @smourier I've moved the description of the new issue to this one and updated the title to preserve history. Also I've added markdown format to make it look better. Also, marking as api ready for review.

[scalablecory]

As an alternate to this, we can add an API that does a "clone and clear", constructing a new ConcurrentDictionary using the innards of the original one. This would avoid the expensive operation of copying to an array when you don't need an array.

[smourier]

@scalablecory - It seemed more complicated to me, plus "clone and clear" doesn't sound like something familiar, I mean, less then ToArray() :-), but that would be even better, yes.

[GSPP]

If you aren't in a hot path, could you simply set old dic in a tmp and re-create _dic = new ConcurrentDictionary() and after iterate on tmp to call dispose , right?

That would not be atomic. After the dictionary is swapped out, other threads might still attempt to write to the old dictionary.

This clear+copy must be implemented by ConcurrentDictionary itself.

[terrajobst]

Video

Maybe we don't understand the scenario but as stated it doesn't make sense to us:

1. In order to be safe, dispose needs to stop any party that adds to the dictionary
2. Once that's done, you can just drain the dictionary

@stephentoub, any other thoughts?

[smourier]

The proposal is not related exclusively to dispose scenarios, it's just to be able to get the items and clear the dictionary in an atomic way. Like TryRemove, but for all the collection.

[scalablecory]

I'm not opposed to this API but would like to see a prototype showing that this can be implemented without a course-grained lock. If we need to do "stop the world" serialization, then there's little reason to add it as a user can already do their own to that effect today.

Given the current implementation, I think this will be challenging without impacting perf elsewhere.

[stephentoub]

Dispose

The dispose example may be a red herring; just because the dictionary is cleared doesn't mean an element that was retrieved from it before the clear isn't still being used. Additional synchronization would likely be necessary to enforce that, depending on the scenario.

uses the dictionary as an event queue

This is a very expensive way to implement an event "queue", with every operation to send the events allocating a potentially massive array that then becomes garbage after all the events have been processed. Presumably for such a scenario you wouldn't actually want ToArrayAndClear but rather CopyAndClear such that the array could be pooled and reused, or some other way of avoiding creating a new array each time.

prototype showing that this can be implemented without a course-grained lock

ConcurrentDictionary's ToArray already has to take all the locks, and Clear does as well. How are you thinking that the combining of the two wouldn't also require all the locks?

[smourier]

These are just examples to explain the need (again, it's just like an hypothetical TryRemoveAll). A method like CopyAndClear would be fine too.

Of course anyone can code all that already, and its obvious that such a method would have to take a big lock (or many locks, I don't know the inner details) but at least it would be taken just once, and I had the impression that it would be implemented in a better way if it was done by framework code than be me or anyone else, that's all.

[scalablecory]

ConcurrentDictionary's ToArray already has to take all the locks, and Clear does as well. How are you thinking that the combining of the two wouldn't also require all the locks?

Yes, exactly ;)