Dictionary<TKey,TValue> is one of the most heavily used collection classes after List<T>. One of the lesser known things is how it behaves when you accidentally modify it concurrently.
What is the output of this simple program under .NET 3.1, .NET 5.0 and .NET 4.8?
using System; using System.Collections.Generic; using System.Threading.Tasks; namespace ConcurrentDictionary { class Program { static Dictionary<string, int> _dict = new(); static void Modify() { _dict.Clear(); for (int i = 0; i < 10; i++) { string key = $"Key {i}"; _dict.ContainsKey(key); _dict[key] = 1; } } static void Main(string[] args) { for(int k=0; k < 1_000_000; k++) { if (k % 100 == 0) { Console.WriteLine($"Modify Run {k}"); } Parallel.Invoke(Modify, Modify, Modify); } } } }
Under .NET Core 3.1, .NET 5.0 it will produce
D:\>ConcurrentDictionary.exe Modify Run 0 Modify Run 0 Modify Run 100 Unhandled exception. ---> System.InvalidOperationException: Operations that change non-concurrent collections must have exclusive access. A concurrent update was performed on this collection and corrupted its state. The collection's state is no longer correct. at System.Collections.Generic.Dictionary`2.FindValue(TKey key) at ConcurrentDictionary.Program.<>c__DisplayClass0_0.<Main>g__Modify|0() in D:\Source\vc19\ConcurrentDictionary\Program.cs:line 26 at System.Threading.Tasks.Task.InnerInvoke() at System.Threading.Tasks.Task.<>c.<.cctor>b__277_0(Object obj) at System.Threading.ExecutionContext.RunInternal(ExecutionContext executionContext,
This is similar what you get when you modify a list
Unhandled exception. ---> System.InvalidOperationException: Collection was modified; enumeration operation may not execute. at System.Collections.Generic.List`1.Enumerator.MoveNextRare() at System.Collections.Generic.List`1.Enumerator.MoveNext() at ConcurrentDictionary.Program.ModifyList() in D:\Source\vc19\ConcurrentDictionary\Program.cs:line 31
When you modify a Dictionary or you enumerate a list while it is modified you get an exception back. That is good and expected.
Lets try the Dictionary sample with .NET 4.8 (or an earlier version)
D:>ConcurrentDictionary.exe Modify Run 0 Modify Run 100
This time it will stop working and just hang around. Whats the problem with .NET 4.x? When in doubt take a memory dump with procdump
C:\temp>procdump -ma 2216 ProcDump v10.0 - Sysinternals process dump utility Copyright (C) 2009-2020 Mark Russinovich and Andrew Richards Sysinternals - www.sysinternals.com [22:32:25] Dump 1 initiated: C:\temp\ConcurrentDictionary.exe_210810_223225.dmp [22:32:25] Dump 1 writing: Estimated dump file size is 68 MB. [22:32:25] Dump 1 complete: 68 MB written in 0.3 seconds [22:32:25] Dump count reached.
Then open the Dump with Windbg
c:\Debuggers\windbg.exe -z C:\temp\ConcurrentDictionary.exe_210810_223225.dmp
Load sos dll and then dump all managed thread stacks
Microsoft (R) Windows Debugger Version 10.0.17763.132 AMD64
Copyright (c) Microsoft Corporation. All rights reserved.
Loading Dump File [C:\temp\ConcurrentDictionary.exe_210810_223225.dmp]
User Mini Dump File with Full Memory: Only application data is available
Comment: '
*** procdump -ma 2216
*** Manual dump'
Symbol search path is: srv*
Executable search path is:
Windows 10 Version 19043 MP (8 procs) Free x64
Product: WinNt, suite: SingleUserTS
19041.1.amd64fre.vb_release.191206-1406
Machine Name:
Debug session time: Tue Aug 10 22:32:25.000 2021 (UTC + 2:00)
System Uptime: 0 days 0:22:07.133
Process Uptime: 0 days 0:00:45.000
.............................
0:000> .loadby sos clr
0:000> ~*e!ClrStack
OS Thread Id: 0x2370 (0)
Call Site
System.Collections.Generic.Dictionary`2[[System.__Canon, mscorlib],[System.Int32, mscorlib]].Insert(System.__Canon, Int32, Boolean)
ConcurrentDictionary.Program.Modify() [D:\Source\vc19\ConcurrentDictionary\Program.cs @ 18]
System.Threading.Tasks.Task.Execute()
System.Threading.ExecutionContext.RunInternal(System.Threading.ExecutionContext, System.Threading.ContextCallback, System.Object, Boolean)
System.Threading.ExecutionContext.Run(System.Threading.ExecutionContext, System.Threading.ContextCallback, System.Object, Boolean)
System.Threading.Tasks.Task.ExecuteWithThreadLocal(System.Threading.Tasks.Task ByRef)
System.Threading.Tasks.Task.ExecuteEntry(Boolean)
System.Threading.Tasks.ThreadPoolTaskScheduler.TryExecuteTaskInline(System.Threading.Tasks.Task, Boolean)
System.Threading.Tasks.TaskScheduler.TryRunInline(System.Threading.Tasks.Task, Boolean)
System.Threading.Tasks.Task.InternalRunSynchronously(System.Threading.Tasks.TaskScheduler, Boolean)
System.Threading.Tasks.Parallel.Invoke(System.Threading.Tasks.ParallelOptions, System.Action[])
ConcurrentDictionary.Program.Main(System.String[]) [D:\Source\vc19\ConcurrentDictionary\Program.cs @ 44]
OS Thread Id: 0x1e68 (6)
Call Site
System.Collections.Generic.Dictionary`2[[System.__Canon, mscorlib],[System.Int32, mscorlib]].FindEntry(System.__Canon)
System.Collections.Generic.Dictionary`2[[System.__Canon, mscorlib],[System.Int32, mscorlib]].ContainsKey(System.__Canon)
ConcurrentDictionary.Program.Modify() [D:\Source\vc19\ConcurrentDictionary\Program.cs @ 17]
System.Threading.Tasks.Task.Execute()
System.Threading.ExecutionContext.RunInternal(System.Threading.ExecutionContext, System.Threading.ContextCallback, System.Object, Boolean)
System.Threading.ExecutionContext.Run(System.Threading.ExecutionContext, System.Threading.ContextCallback, System.Object, Boolean)
System.Threading.Tasks.Task.ExecuteWithThreadLocal(System.Threading.Tasks.Task ByRef)
System.Threading.Tasks.Task.ExecuteEntry(Boolean)
System.Threading.ThreadPoolWorkQueue.Dispatch()
0:000> !runaway
User Mode Time
Thread Time
0:2370 0 days 0:00:44.843
6:1e68 0 days 0:00:44.796
2:928 0 days 0:00:00.015
5:233c 0 days 0:00:00.000
4:3560 0 days 0:00:00.000
3:92c 0 days 0:00:00.000
1:1fb8 0 days 0:00:00.000
0:000> .time
Debug session time: Tue Aug 10 22:32:25.000 2021 (UTC + 2:00)
System Uptime: 0 days 0:22:07.133
Process Uptime: 0 days 0:00:45.000
Kernel time: 0 days 0:00:00.000
User time: 0 days 0:01:29.000
We find that we consume a lot of CPU on thread 0 and 6 (44s until the dump was taken). These methods call into Dictionary.FindEntry and Dictionary.Insert which is strange. Why should it take now much more CPU to insert things into a Dictionary?
In the meantime Visual Studio has become pretty good at loading memory dumps as well. The by far best view is still the Parallel Stacks Window
But for now we turn back to Windbg because it offers information which threads consume how much CPU with !runaway on a per thread basis and .time for the complete process. This helps a lot to look at the right threads which are consuming most CPU.
To drill deeper into the innards of the Dictionary we switch to the best Windbg Extension for managed code which is netext. Unzip the latest release for your Windbg into the Windbg\winext folder or you need to fully qualify the path to the x86/x64 version of netext.
0:000> .load netext
netext version 2.1.64.5000 Jun 2 2021
License and usage can be seen here: !whelp license
Check Latest version: !wupdate
For help, type !whelp (or in WinDBG run: '.browse !whelp')
Questions and Feedback: https://github.com/rodneyviana/netext/issues
Copyright (c) 2014-2015 Rodney Viana (http://blogs.msdn.com/b/rodneyviana)
Type: !windex -tree or ~*e!wstack to get started
0:006> ~6s
0:006> !wstack
Listing objects from: 0000007a30afe000 to 0000007a30b00000 from thread: 6 [1e68]
Address Method Table Heap Gen Size Type
@r8=000001eb5a279ef8 00007ffa81d38538 0 0 92 System.Int32[]
@rcx=000001eb5a27ffe8 00007ffa81d4d880 0 0 432 System.Collections.Generic.Dictionary_Entry[]
@rdi=000001eb5a2d69e0 00007ffa81d359c0 0 0 36 System.String Key 1
@rdx=000001eb5a27ffe8 00007ffa81d4d880 0 0 432 System.Collections.Generic.Dictionary_Entry[]
@rsi=000001eb5a272d88 00007ffa81d46db0 0 0 80 System.Collections.Generic.Dictionary
000001eb5a2d69a8 00007ffa81d385a0 0 0 24 System.Int32 0n1
000001eb5a274d48 00007ffa81d3a440 0 0 216 System.Globalization.NumberFormatInfo
000001eb5a2d69c0 00007ffa81d359c0 0 0 28 System.String 1
000001eb5a28e350 00007ffa81d39e00 0 0 48 System.Text.StringBuilder
000001eb5a279a50 00007ffa81d359c0 0 0 40 System.String Key {0}
19 unique object(s) found in 1,716 bytes
0:006> !wdo 000001eb5a27ffe8
Address: 000001eb5a27ffe8
Method Table/Token: 00007ffa81d4d880/200000004
Class Name:
System.Collections.Generic.Dictionary_Entry<System.String,System.Int32>[]
Size : 432
Components: 17
[0]: -mt 00007FFA81D4D820 000001EB5A27FFF8
[1]: -mt 00007FFA81D4D820 000001EB5A280010
[2]: -mt 00007FFA81D4D820 000001EB5A280028
[3]: -mt 00007FFA81D4D820 000001EB5A280040
[4]: -mt 00007FFA81D4D820 000001EB5A280058
...
0:006> !wdo -mt 00007ffa81d4d820 000001eb5a280010
System.Collections.Generic.Dictionary_Entry<System.String,System.Int32>
00007ffa81d3a238 System.__Canon+0000 key 000001eb5a2d6980 Key 0
00007ffa81d385a0 System.Int32 +0008 hashCode 6278e7e7
00007ffa81d385a0 System.Int32 +000c next 1 (0n1)
00007ffa81d385a0 System.Int32 +0010 value 1 (0n1)
The .NET Dictionary stores the data in buckets which is a linked list. The nodes are referenced via an index with the next field. In the dysfunctional case we find at array location 1 as next node index 1 which will cause the node walk to never end.
The decompiled code shows this
The for loop calls i = this.entries[i].next in the incremeent condition. This never incrementing loop will not end and explains the high CPU on two threads.
How do these things usually crop up? When more and more code is made multithreaded and async await is added to the mix you can find in a slow or stuck process often high CPU in FindEntry or Insert. Now you know this indicates not a huge Dictionary which has just become inefficient.
Actually you have found a Dictionary multithreading bug if you are running on .NET 4.x!
You can create a stack tag for these methods and flag them as potential concurrent Dictionary modification if these consume one core or more constantly like this to directly show up in WPA:
The stacktag file for this is
<?xml version="1.0" encoding="utf-8"?>
<Tag Name="">
<Tag Name=".NET">
<Tag Name="Dictionary FindEntry\If one or more Core is consumed this indicates a concurrent dictionary modification which results in endless loops!">
<Entrypoint Module="mscorlib.ni.dll" Method="System.Collections.Generic.Dictionary*.FindEntry*"/>
<Entrypoint Module="mscorlib.dll" Method="System.Collections.Generic.Dictionary*::FindEntry*"/>
<Entrypoint Module="System.Private.CoreLib.dll" Method="System.Collections.Generic.Dictionary*.FindEntry*"/>
</Tag>
<Tag Name="Dictionary Insert\If one or more Core is consumed this indicates a concurrent dictionary modification which results in endless loops!">
<Entrypoint Module="mscorlib.ni.dll" Method="System.Collections.Generic.Dictionary*.Insert*"/>
<Entrypoint Module="mscorlib.dll" Method="System.Collections.Generic.Dictionary*::Insert*"/>
<Entrypoint Module="System.Private.CoreLib.dll" Method="System.Collections.Generic.Dictionary*.Insert*"/>
</Tag>
</Tag>
</Tag>
This is enough debugging Voodoo for today. Drop me a note if you have been biten by this issue and how you found it.
Alois Kraus 
[…] Concurrent Dictionary Modification Pitfalls – Alois Kraus […]
LikeLike
Wait a second, you’re about Dictionary, not ConcurrentDictionary. Indeed, there would be a concurrency issue, as described by MSDN: https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.dictionary-2
[quote]
A Dictionary can support multiple readers concurrently, as long as the collection is not modified. Even so, enumerating through a collection is intrinsically not a thread-safe procedure. In the rare case where an enumeration contends with write accesses, the collection must be locked during the entire enumeration. To allow the collection to be accessed by multiple threads for reading and writing, you must implement your own synchronization.
For thread-safe alternatives, see the ConcurrentDictionary class or ImmutableDictionary class.
[/quote]
LikeLike
ConcurrentDictionary is not in all cases better. If you are mostly reading from it then use a lock around a every Dictionary access and be done with it. ConcurrentDictionay allocates memory which is proportional to the number of cores to become nearly lock free at the expense of a much higher memory consumption. If you have 40 Cores and your working horse data structure is switched from a Dictionary to a ConcurrentDictionary you easily can waste GBs of memory. ConcurrentDictionary is also slower on reading data due to its more complex lookup with the sparsely populated arrays. The only workload where ConcurrentDictionary pays off is when you have many threads mutate the dictionary while you are also reading from it. Then it will be a clear winner. As usual you need to measure if this or that data structure is better for your specific workload. Just changing things based on personal preference without measuring can get you into trouble.
LikeLike
[…] Concurrent Dictionary Modification Pitfalls (Alois Kraus) […]
LikeLike
[…] a .NET Lambda Expression and .NET Source Generators: Finding Class Declarations (Khalid Abuhakmeh) Concurrent Dictionary Modification Pitfalls (Alois Kraus) Stringly Typed vs Strongly Typed (Scott Hanselman) Fine-Tuning Live Debugging with […]
LikeLike