Thread-safety of ConcurrentDictionary vs. Dictionary

README.md

Thread-safety of ConcurrentDictionary

Imagine a case where entries are being added in one thread and selectively removed in another thread. You wonder, what about the new namespace System.Collections.Concurrent?

Research

I could not tell from the MSDN documentation whether the ConcurrentDictionary could be enumerated safely while being modified in another thread. I set out to answer the question "Is any more thread-safe than Dictionary?" The thread-safety disclaimer doesn't indicate to me that it would be safe to enumerate (Spoiler! Answer: not always).

All public and protected members of ConcurrentDictionary<TKey, TValue> are thread-safe and may be used concurrently from multiple threads. However, members accessed through one of the interfaces the ConcurrentDictionary<TKey, TValue> implements, including extension methods, are not guaranteed to be thread safe and may need to be synchronized by the caller.

This guarantee applies to ConcurrentDictionary.ToArray(), so that would seem a safe choice.

From my perspective, System.Collections.Immutable.ImmutableDictionary is much easier to wrap my head around because it is thread-safe, without qualification.

The ConcurrentDictionary seems to be safely enumerable in my test, and looking at the source, it seems they at least thought about it.

The ConcurrentDictionary.ToList() (LINQ extension methed) create's a List, which uses ICollection<T>.CopyTo, which is verifiably not thread-safe.  Contrast that (unsafe optimization of using IList<T>) with FSharp's SeqModule.OfSeq, which enumerates the collection. I haven't been able to make it fail.

ConcurrentDictionary<K,V>.GetEnumerator seems to enumerate it consistently (safely).

Concluding remarks

• ConcurrentDictionary is safe to use in this case and is prettier than the alternatives (in this case rewriting with immutability or using explicit locking).
• ConcurrentDictionary can easily be used incorrectly with idiomatic C# (LINQ). So much for making it easy to fall into the "pit of success"!
• ConcurrentDictionary is not a "silver bullet."  I consider it "advanced" (in a bad way) and I will avoid it if better a better solution presents itself.
• ConcurrentDictionary can be a useful tool.

AProgram.cs

using System;
using System.Collections.Generic;
using System.Collections.Concurrent;
using System.Text.RegularExpressions;
using System.Linq;
using System.Threading;
using static System.Console;
using Microsoft.FSharp.Core;
using Microsoft.FSharp.Collections;

namespace ConcurrentDictTest
{
    using TDictionary = ConcurrentDictionary<string, string>;
    //using TDictionary = Dictionary<string, string>;
    static class Program
    {
        const int count = 1000000;
        static readonly TDictionary dict = new TDictionary();

        static void Main()
        {
            WriteLine("TEST #1 - Enumerate while adding");
            WriteLine("-------------------------------------------------------------------------------");
            WriteLine("Add many entries in one thread, while reading entries with other threads.");
            WriteLine();
            MainAdd();

            dict.Clear();

            WriteLine();
            WriteLine("TEST #2 - Enumerate while removing");
            WriteLine("-------------------------------------------------------------------------------");
            WriteLine("Remove many entries in one thread, while reading entries with other threads.");
            WriteLine();
            MainRemove();
        }

        static void MainAdd()
        {
            var threads = new[] {
                new Thread(AddEntries),
                new Thread(EnumerateWithForeachCount),
                new Thread(EnumerateWithLinqCount),
                new Thread(EnumerateKeysWithLinqCount),
                new Thread(EnumerateWithFsharpCount),
            };
            foreach (var t in threads)
                t.Start();
            foreach (var t in threads)
                t.Join();
        }

        static void MainRemove()
        {
            AddEntries();
            var threads = new[] {
                new Thread(RemoveEntries),
                new Thread(EnumerateWithForeach0),
                new Thread(EnumerateWithLinq0),
                new Thread(EnumerateKeysWithLinq0),
                new Thread(EnumerateWithFsharp0),
            };
            foreach (var t in threads)
                t.Start();
            foreach (var t in threads)
                t.Join();
        }

        static void EnumerateWithForeach0() => EnumerateWithForeach(0);
        static void EnumerateWithForeachCount() => EnumerateWithForeach(count);
        static void EnumerateWithForeach(int expectedCount)
        {
            try
            {
                int ct;
                do
                {
                    ct = 0;
                    foreach(var item in dict)
                    {
                        if(item.Key == null)
                            throw new Exception("Somehow the dictionary returned a null."); // "use" the item.
                        ct++;
                    }
                } while (ct != expectedCount);
                WriteBullet("Foreach       - Successfully enumerated. Count: " + ct);
            }
            catch(Exception e)
            {
                WriteBullet("Foreach       - Failed with:\r\n   " + e);
            }
        }

        static void EnumerateWithLinq0() => EnumerateWithLinq(0);
        static void EnumerateWithLinqCount() => EnumerateWithLinq(count);
        static void EnumerateWithLinq(int expectedCount)
        {
            try
            {
                var items = dict.ToList();
                do
                {
                    items = dict
                        //.Where(x => true)
                        .ToList();
                    foreach(var item in items)
                    {
                        if(item.Key == null)
                            throw new Exception("Somehow the dictionary returned a null."); // "use" the item.
                    }
                } while (items.Count() != expectedCount);
                WriteBullet("Linq          - Successfully enumerated. Count: " + items.Count());
            }
            catch(Exception e)
            {
                WriteBullet("Linq          - Failed with:\r\n   " + e);
            }
        }

        static void EnumerateKeysWithLinq0() => EnumerateKeysWithLinq(0);
        static void EnumerateKeysWithLinqCount() => EnumerateKeysWithLinq(count);
        static void EnumerateKeysWithLinq(int expectedCount)
        {
            try
            {
                WriteBullet($".Keys is {(dict.Keys is System.Collections.ICollection ? "" : "not ")} an ICollection.");
                WriteBullet($".Keys is {(dict.Keys is ICollection<string> ? "" : "not ")} an ICollection<string>.");
                WriteBullet($".Keys is {(dict.Keys is IList<string> ? "" : "not ")} an IList<string>.");
                var items = dict.Keys.ToList();
                do
                {
                    items = dict.Keys
                        //.Where(x => true)
                        .ToList();
                    foreach (var item in items)
                    {
                        if (item == null)
                            throw new Exception("Somehow the dictionary returned a null key."); // "use" the item.
                    }
                } while (items.Count() != expectedCount);
                WriteBullet("Keys.ToList() - Successfully enumerated keys. Count: " + items.Count());
            }
            catch (Exception e)
            {
                WriteBullet("Keys.ToList() - Failed with:\r\n   " + e);
            }
        }

        static void EnumerateWithFsharp0() => EnumerateWithFsharp(0);
        static void EnumerateWithFsharpCount() => EnumerateWithFsharp(count);
        static void EnumerateWithFsharp(int expectedCount)
        {
            Converter<KeyValuePair<int, int>, bool> converter = x => true;
            try
            {
                var items = ListModule.OfSeq(dict);
                do
                {
                    items = ListModule.OfSeq(
                        //SeqModule.Where(
                            //FSharpFunc<KeyValuePair<int, int>, bool>.FromConverter(converter),
                            dict)
                            //)
                            ;
                    foreach(var item in items)
                    {
                        if(item.Key == null)
                            throw new Exception("Somehow the dictionary returned a null."); // "use" the item.
                    }
                } while (items.Count() != expectedCount);
                WriteBullet("F#            - Successfully enumerated. Count: " + items.Count());
            }
            catch (Exception e)
            {
                WriteBullet("F#            - Failed with:\r\n   " + e);
            }
        }

        static void AddEntries()
        {
            for(int i = 0; i < count; i++)
                dict[i.ToString()] = i.ToString();
            WriteBullet("Done adding " + dict.Count);
        }

        static void RemoveEntries()
        {
            RemoveEntriesHashcode();
            WriteBullet("Done removing.  Count:  " + dict.Count);
        }

        static void RemoveEntriesAscending() =>
            RemoveEntries(Enumerable.Range(0, count));

        static void RemoveEntriesDescending() =>
            RemoveEntries(Enumerable.Range(0, count).Reverse());

        static void RemoveEntriesHashcode() =>
            RemoveEntries(Enumerable.Range(0, count).OrderBy(i => i.GetHashCode()));

        static void RemoveEntries(IEnumerable<int> entryKeys)
        {
            string _ignoredValue;
            foreach (int i in entryKeys)
                //dict.Remove(i);
                dict.TryRemove(i.ToString(), out _ignoredValue);
        }

        static void WriteBullet(string s) =>
            WriteLine(
                Regex.Replace(s, @"(?<=^\u0020*)\b", "* ", RegexOptions.Multiline)
                    .Replace("`", "&#x60;")
                    .Replace("[", "&#91;")
                    .Replace("]", "&#93;"));
    }
}

ConcurrentDictTest.csproj

<?xml version="1.0" encoding="utf-8"?>
<Project ToolsVersion="14.0" DefaultTargets="Build" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
  <Import Project="$(MSBuildExtensionsPath)\$(MSBuildToolsVersion)\Microsoft.Common.props" Condition="Exists('$(MSBuildExtensionsPath)\$(MSBuildToolsVersion)\Microsoft.Common.props')" />
  <PropertyGroup>
    <Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration>
    <Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform>
    <ProjectGuid>{AF26CAA5-9032-4D53-A58C-3EE671820F2F}</ProjectGuid>
    <OutputType>Exe</OutputType>
    <AppDesignerFolder>Properties</AppDesignerFolder>
    <RootNamespace>ConcurrentDictTest</RootNamespace>
    <AssemblyName>ConcurrentDictTest</AssemblyName>
    <TargetFrameworkVersion>v4.5.2</TargetFrameworkVersion>
    <FileAlignment>512</FileAlignment>
    <AutoGenerateBindingRedirects>true</AutoGenerateBindingRedirects>
  </PropertyGroup>
  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
    <PlatformTarget>AnyCPU</PlatformTarget>
    <DebugSymbols>true</DebugSymbols>
    <DebugType>full</DebugType>
    <Optimize>false</Optimize>
    <OutputPath>bin\Debug\</OutputPath>
    <DefineConstants>DEBUG;TRACE</DefineConstants>
    <ErrorReport>prompt</ErrorReport>
    <WarningLevel>4</WarningLevel>
  </PropertyGroup>
  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
    <PlatformTarget>AnyCPU</PlatformTarget>
    <DebugType>pdbonly</DebugType>
    <Optimize>true</Optimize>
    <OutputPath>bin\Release\</OutputPath>
    <DefineConstants>TRACE</DefineConstants>
    <ErrorReport>prompt</ErrorReport>
    <WarningLevel>4</WarningLevel>
  </PropertyGroup>
  <ItemGroup>
    <Reference Include="FSharp.Core, Version=4.4.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a, processorArchitecture=MSIL" />
    <Reference Include="System" />
    <Reference Include="System.Core" />
    <Reference Include="System.Xml.Linq" />
    <Reference Include="System.Data.DataSetExtensions" />
    <Reference Include="Microsoft.CSharp" />
    <Reference Include="System.Data" />
    <Reference Include="System.Net.Http" />
    <Reference Include="System.Xml" />
  </ItemGroup>
  <ItemGroup>
    <Compile Include="AProgram.cs" />
  </ItemGroup>
  <ItemGroup>
    <Folder Include="Properties\" />
  </ItemGroup>
  <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />
  <!-- To modify your build process, add your task inside one of the targets below and uncomment it. 
       Other similar extension points exist, see Microsoft.Common.targets.
  <Target Name="BeforeBuild">
  </Target>
  <Target Name="AfterBuild">
  </Target>
  -->
</Project>