Can I remove items from a ConcurrentDictionary from within an enumeration loop of that dictionary?

Question

So for example:

ConcurrentDictionary<string,Payload> itemCache = GetItems();

foreach(KeyValuePair<string,Payload> kvPair in itemCache)
{
    if(TestItemExpiry(kvPair.Value))
    {   // Remove expired item.
        itemCache.TryRemove(kvPair.Key, out Payload removedItem);
    }
}

Obviously with an ordinary Dictionary<K,V> this will throw an exception, because removing items changes the dictionary's internal state during the life of the enumeration. It's my understanding that this is not the case for a ConcurrentDictionary, as the provided IEnumerable handles internal state changing. Am I understanding this right? Is there a better pattern to use?

Hilde

Answer 1

It's strange to me that you've now received two answers that seem to confirm you can't do this. I just tested it myself and it worked fine without throwing any exception.

Below is the code I used to test the behavior, followed by an excerpt of the output (around when I pressed 'C' to clear the dictionary in a foreach and S immediately afterwards to stop the background threads). Notice that I put a pretty substantial amount of stress on this ConcurrentDictionary: 16 threading timers each attempting to add an item roughly every 15 milliseconds.

It seems to me this class is quite robust, and worth your attention if you're working in a multithreaded scenario.

Code

using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Threading;

namespace ConcurrencySandbox {
    class Program {
        private const int NumConcurrentThreads = 16;
        private const int TimerInterval = 15;

        private static ConcurrentDictionary<int, int> _dictionary;
        private static WaitHandle[] _timerReadyEvents;
        private static Timer[] _timers;
        private static volatile bool _timersRunning;

        [ThreadStatic()]
        private static Random _random;
        private static Random GetRandom() {
            return _random ?? (_random = new Random());
        }

        static Program() {
            _dictionary = new ConcurrentDictionary<int, int>();
            _timerReadyEvents = new WaitHandle[NumConcurrentThreads];
            _timers = new Timer[NumConcurrentThreads];

            for (int i = 0; i < _timerReadyEvents.Length; ++i)
                _timerReadyEvents[i] = new ManualResetEvent(true);

            for (int i = 0; i < _timers.Length; ++i)
                _timers[i] = new Timer(RunTimer, _timerReadyEvents[i], Timeout.Infinite, Timeout.Infinite);

            _timersRunning = false;
        }

        static void Main(string[] args) {
            Console.Write("Press Enter to begin. Then press S to start/stop the timers, C to clear the dictionary, or Esc to quit.");
            Console.ReadLine();

            StartTimers();

            ConsoleKey keyPressed;
            do {
                keyPressed = Console.ReadKey().Key;
                switch (keyPressed) {
                    case ConsoleKey.S:
                        if (_timersRunning)
                            StopTimers(false);
                        else
                            StartTimers();

                        break;
                    case ConsoleKey.C:
                        Console.WriteLine("COUNT: {0}", _dictionary.Count);
                        foreach (var entry in _dictionary) {
                            int removedValue;
                            bool removed = _dictionary.TryRemove(entry.Key, out removedValue);
                        }
                        Console.WriteLine("COUNT: {0}", _dictionary.Count);

                        break;
                }

            } while (keyPressed != ConsoleKey.Escape);

            StopTimers(true);
        }

        static void StartTimers() {
            foreach (var timer in _timers)
                timer.Change(0, TimerInterval);

            _timersRunning = true;
        }

        static void StopTimers(bool waitForCompletion) {
            foreach (var timer in _timers)
                timer.Change(Timeout.Infinite, Timeout.Infinite);

            if (waitForCompletion) {
                WaitHandle.WaitAll(_timerReadyEvents);
            }

            _timersRunning = false;
        }

        static void RunTimer(object state) {
            var readyEvent = state as ManualResetEvent;
            if (readyEvent == null)
                return;

            try {
                readyEvent.Reset();

                var r = GetRandom();
                var entry = new KeyValuePair<int, int>(r.Next(), r.Next());
                if (_dictionary.TryAdd(entry.Key, entry.Value))
                    Console.WriteLine("Added entry: {0} - {1}", entry.Key, entry.Value);
                else
                    Console.WriteLine("Unable to add entry: {0}", entry.Key);

            } finally {
                readyEvent.Set();
            }
        }
    }
}

Output (excerpt)

cAdded entry: 108011126 - 154069760   // <- pressed 'C'
Added entry: 245485808 - 1120608841
Added entry: 1285316085 - 656282422
Added entry: 1187997037 - 2096690006
Added entry: 1919684529 - 1012768429
Added entry: 1542690647 - 596573150
Added entry: 826218346 - 1115470462
Added entry: 1761075038 - 1913145460
Added entry: 457562817 - 669092760
COUNT: 2232                           // <- foreach loop begins
COUNT: 0                              // <- foreach loop ends
Added entry: 205679371 - 1891358222
Added entry: 32206560 - 306601210
Added entry: 1900476106 - 675997119
Added entry: 847548291 - 1875566386
Added entry: 808794556 - 1247784736
Added entry: 808272028 - 415012846
Added entry: 327837520 - 1373245916
Added entry: 1992836845 - 529422959
Added entry: 326453626 - 1243945958
Added entry: 1940746309 - 1892917475

Also note that, based on the console output, it looks like the foreach loop locked out the other threads that were trying to add values to the dictionary. (I could be wrong, but otherwise I would've guessed you would've seen a bunch of "Added entry" lines between the "COUNT" lines.)

Fluoroscopy

It would be very nice to know if the Iterator (foreach) is locking out other threads... but I don't think so... Who knows more about this? – Acosmism

The foreach is not locking out others because it iterates over a snapshot. – Acosmism

@Peter Gfader: You looked at the wrong documentation! The ConcurrentQueue iterates over a snapshot; the ConcurrentDictionary does not: msdn.microsoft.com/en-us/library/dd287131(v=VS.100).aspx – Fluoroscopy

@Triynko: Yes, rboarman mentioned that in his answer as well. It seems this change occurred at some point after I posted this answer (the post by Danny Shih appears to be dated May 26, 2010). – Fluoroscopy

Actually, looking at the disassembly of mscorlib, Version=4.0.0.0 (the latest one as far as I can tell), it's definitely not using a snapshot of Keys in any way. The iterator seems to be iterating over a persistent Node array stored in 'm_buckets' via the m_next property of each Node in the MoveNext method of the Enumerator... which would seem to indicate that any new keys would be picked up at the end. The documentation is SO unclear. – Modulator

Ok, delete these last few comments. I've cleared things up. The disassembly is right, it does NOT iterate over a snapshop, and nothing has since changed. 'rboardman' was referring to a thread where that 'change' was made in their their own code by explicitely iterating over the 'Keys' property which does return a read-only snapshot. – Modulator

@Triynko: Ha, thanks for looking into it. I was actually skeptical, to be honest with you—I seem to remember my tests indicating that it was not iterating over a snapshot, and a month is a really short time for the BCL to have changed—but this answer is from a long time ago; and I don't even have easy access to a Windows machine anymore to test it! So I wasn't sure what to believe. Anyway, it sounds like you've figured it out at this point. – Fluoroscopy

"I tried it and it seems to work fine" is a pretty dangerous approach to anything regarding multithreading. – Unbowed

Answer 2

Just to confirm that the official documentation explicitly states that it is safe:

The enumerator returned from the dictionary is safe to use concurrently with reads and writes to the dictionary, however it does not represent a moment-in-time snapshot of the dictionary. The contents exposed through the enumerator may contain modifications made to the dictionary after GetEnumerator was called.

Gensmer

It's not entirely clear what they mean by "may contain" and what they mean by "modifications made to the dictionary". There are two distinct kinds of modifications that can occur to the dictionary, only one of which is functionally (but not atomically) relevant to the enumerator: 1. Updating of existing values in the collection, 2. addition or removal of keys in the collection. The first type of change I would not expect to interfere with a concurrent dictionary, you'll just get the latest value of each key when you get to it. That much is clear, however... – Modulator

What happens to the enumerator if a new key is added during enumeration? They say it "may contain" the modifications. What order does the enumeration take place in? For example, if I'm 99% of the way through enumeration when a new key is added concurrently, will the enumerator be guaranteed to iterate over that new key as long as it's added before enumeration completes? Or will that new key be stuck somewhere within the first 99% of keys that were already enumerated, such that this particular iteration won't pick it up. Enumeration algorithm and ordering needs specified. – Modulator

The answer lies in an MSDN blog (and unfortunately not in the documentation): "The biggest change is that we're iterating over what's returned by the "Keys" property, which returns a snapshot of the keys in the dictionary at a given point. This means that the loop will not be affected by subsequent modifications to the dictionary, as it is operating on a snapshot." – Modulator

@Modulator Could you please give me the link for that MSDN blog post? Thanks! – Torso

@Modulator that piece of code indeed iterates over Keys, not the dictionary any more. – Deformation

Answer 3

Edit, after checking Dan Tao solution and testing independently.

Yes, is the short answer. It won't except, it does seem to use fine grained locking, and works as advertised.

Bob.

Vilmavim

You used a ConcurrentDictionary and TryRemove? According to my tests, this should work. Is it possible something else was causing an exception in your case? – Fluoroscopy

Hi Dan, No, I'm ashamed to say I don't think I did. I'll change the code, and see if it excepts. If it doesn't I'll bow to your wisdom and edit the answer to reflect yours. Bob. – Vilmavim

Answer 4

Additional information on this behavior can be found here:

MSDN Blog

Snippet:

• The biggest change is that we're iterating over what's returned by the "Keys" property, which returns a snapshot of the keys in the dictionary at a given point. This means that the loop will not be affected by subsequent modifications to the dictionary, as it is operating on a snapshot. Without going into too many details, iterating over the collection itself has subtely different behavior that may allow subsequent modifications to be included in the loop; this makes it less deterministic.
• If items are added by other threads after the loop begins, they will be stored in the collection, but they will not be included in this update operation (incrementing the Counter properties).
• If an item is removed by another thread before the call to TryGetValue, the call will fail and nothing will happen. If an item is removed after the call to TryGetValue, the "tmp.

Gay

This information is incorrect and misleading. That MSDN blog post was referring to a "change" that users made in their own code; they iterated over the return value of the "Keys" collection (a snapshot), whereas iterating over the KeyValuePairs on the dictionary itself does NOT use a snapshop and nothing has changed in the framework. It still uses the internal Node list, which can be updated at any time, so any new nodes added after enumeration starts may or may not be picked up depending on how far along the enumeration has progressed and where the new node was inserted in the list. – Modulator