Sunday, March 29, 2009

An Interesting Side-Effect of Concurrency: Removing Items from a Collection While Enumerating

Copyright 2008-2009, Paul Jackson, all rights reserved

During my presentation on Parallel Programming in .Net 4.0 at the Orlando Code Camp yesterday, I was asked a question that I didn’t know the answer to and didn’t have time in the session to try out.  The question had to do with the new concurrent collections (System.Collections.Concurrent) available in .Net 4.0 and whether their concurrency also enabled us to change the collection while it was being enumerated.

We all know that this is something we can’t do:

   1: var dictionary = new Dictionary<int, DateTime>();
   2:  
   3: for (int i = 0; i < 10; i++)
   4: {
   5:     dictionary.Add(i, DateTime.Now);
   6: }
   7:  
   8: foreach (var item in dictionary)
   9: {
  10:     Console.WriteLine("Key: {0}", item.Key);
  11:     dictionary.Remove(item.Key);
  12: }
  13:  
  14: Console.WriteLine("Items remaining: {0}", dictionary.Count);
  15: Console.ReadLine();

At line 11, trying to remove an item from the collection we’re enumerating over results in an InvalidOperationException -- Collection was modified; enumeration operation may not execute.

But an interesting side-effect of the concurrent collections in .Net 4.0 appears to be that this is now possible – obviously because one thread needs to be able to enumerate a concurrent collection while others are adding-to/removing-from.  So changing the code to use ConcurrentDictionary:

   1: var dictionary = new ConcurrentDictionary<int, DateTime>();
   2:  
   3: for (int i = 0; i < 10; i++)
   4: {
   5:     dictionary.TryAdd(i, DateTime.Now);
   6: }
   7:  
   8: foreach (var item in dictionary)
   9: {
  10:     Console.WriteLine("Key: {0}", item.Key);
  11:     var temp = item.Value;
  12:     dictionary.TryRemove(item.Key, out temp);
  13: }
  14:  
  15: Console.WriteLine("Items remaining: {0}", dictionary.Count);
  16: Console.ReadLine();

Results in our being able to enumerate the dictionary and remove each item as we process it. 

image

But what if we want to remove one of the items that hasn’t been processed yet?  What if some value in the current item being processed results in our needing to remove a future item?

   1: var dictionary = new ConcurrentDictionary<int, DateTime>();
   2:  
   3: for (int i = 0; i < 10; i++)
   4: {
   5:     dictionary.TryAdd(i, DateTime.Now);
   6: }
   7:  
   8: foreach (var item in dictionary)
   9: {
  10:     Console.WriteLine("Key: {0}", item.Key);
  11:     if (item.Key == 4)
  12:     {
  13:         DateTime temp = DateTime.Now;
  14:         dictionary.TryRemove(8, out temp);
  15:     }
  16: }
  17:  
  18: Console.WriteLine("Items remaining: {0}", dictionary.Count);
  19: Console.ReadLine();

In this example, when we process the item with a key of 4, we want to remove key 8 from the collection – which also works:

image

And corollary of this is also true, that if we try to add to the collection while enumerating:

   1: foreach (var item in dictionary)
   2: {
   3:     Console.WriteLine("Key: {0}", item.Key);
   4:  
   5:     if (dictionary.Count < 20)
   6:     {
   7:         dictionary.TryAdd(dictionary.Count + 1, DateTime.Now);
   8:     }
   9: }

It works as well:

image

So a special “thank you” to the gentleman in my session yesterday who asked the question.  It looks like the answer’s “yes”.

kick it on DotNetKicks.com Shout it

No comments: