37

In .NET<5 and .NET Core 3.1 the following code

var d = new Dictionary<string, int> { { "a", 0 }, { "b", 0 }, { "c", 0 } };
foreach (var k in d.Keys) 
{
   d[k]+=1;
}

throws

System.InvalidOperationException: Collection was modified; enumeration operation may not execute.

When targeting .NET 5 the snippet no longer throws.

What has changed?

I failed to find the answer in Breaking changes in .NET 5 and Performance Improvements in .NET 5.

Is it something to do with ref readonly T?

Dmitry Bychenko
  • 180,369
  • 20
  • 160
  • 215
tymtam
  • 31,798
  • 8
  • 86
  • 126
  • I think we should be able to find the answer in the source code to `Dictionary<, >`, starting reading from the `set` accessor of the indexer `public TValue this[TKey key] { /* ... */ }`. There should exist a private field that keeps track on whether the collection was modified or not. If I assign with the setter `d[k] = tmp;` and `k` was previously in the `Dictionary<,>`, does that count as a modification? They must have changed that. – Jeppe Stig Nielsen Apr 04 '21 at 09:56
  • In the old version, they do `entries[i].value = value; version++; return;` in the branch where we have an update. The `version++` ensures the enumerator will blow up with an exception on the next `MoveNext()` on the enumerator. – Jeppe Stig Nielsen Apr 04 '21 at 10:02
  • (They also allow it with the value collection, for example `foreach (var v in d.Values) { Console.WriteLine("Top " + v + " " + d["c"]); d["c"] += 1; Console.WriteLine("Bottom " + v + " " + d["c"]); }`. So I guess there is still only one `version` field for both keys and values. Where do I see the new C# source of `public class Dictionary`?) – Jeppe Stig Nielsen Apr 04 '21 at 10:23

1 Answers1

48

There was a change to the source code of Dictionary<TKey, TValue> to allow updates of existing keys during enumeration. It was commited on April 9, 2020 by Stephen Toub. That commit can be found here along with corresponding PR #34667.

The PR is titled "Allow Dictionary overwrites during enumeration" and notes that it fixes issue #34606 "Consider removing _version++ from overwrites in Dictionary<TKey, TValue>". The text of that issue, opened by Mr. Toub is as follows:

We previously removed the  _version++  when Remove'ing from a dictionary. We should consider doing so as well when just overwriting a value for an existing key in the dictionary. This would enable update loops that tweak a value in the dictionary without needing to resort to convoluted and more expensive measures.

A comment on that issue asks:

What is the benefit of doing this?

To which Stephen Toub replied:

As called out in the original post, fine patterns that are currently throwing today will start working correctly, e.g.

foreach (KeyValuePair<string, int> pair in dict) dict[pair.Key] = pair.Value + 1;

If you look at the Dictionary<, > source code, you can see that the _version field (which is used to detect modifications) is now only updated under certain conditions and not when an existing key is modified.

The area of particular interest is the TryInsert method (which is called by the indexer, see below) and its third parameter of type InsertionBehavior. When this value is InsertionBehavior.OverwriteExisting the versioning field is not updated for an existing key.

For example, see this section of code from the updated TryInsert:

if (behavior == InsertionBehavior.OverwriteExisting)
{ 
    entries[i].value = value;
    return true;
}

Prior to the change that section looked like this (code comment mine):

if (behavior == InsertionBehavior.OverwriteExisting)
{ 
    entries[i].value = value;
    _version++; // <-----
    return true;
}

Note that the increment of the _version field has been removed, thus allowing modifications during enumeration.

For completeness, the setter of the indexer looks like this. It was not modified by this change, but note the third parameter which influences the above behavior:

set 
{
    bool modified = TryInsert(key, value, InsertionBehavior.OverwriteExisting);
    Debug.Assert(modified);
}

Remove'ing from the dictionary no longer impacts enumeration either. That, however, has been around since netcore 3.0 and is appropriately called out in the documentation of Remove:

.NET Core 3.0+ only: this mutating method may be safely called without invalidating active enumerators on the Dictionary<TKey,TValue> instance. This does not imply thread safety.

Despite one developer's insistence in the linked issue that the documentation be updated (and what appears to be an assurance that it would be), the docs for the indexer have not yet (2021-04-04) been updated to reflect the current behavior.

pinkfloydx33
  • 11,863
  • 3
  • 46
  • 63
  • Good find! The change in the `Dictionary.cs` file (the commit link in your answer) is in fact exactly like I expected. I wonder if it would make sense to make a change to `List<>` as well? Namely when you do `list[index] = newvalue;` (i.e. the indexer `set` accessor), this does only overwrite the value in a "slot" that exists already. So this becomes related to [my answer in another thread](https://stackoverflow.com/a/41246500) where this aspect of a `List<>` is explained. – Jeppe Stig Nielsen Apr 04 '21 at 11:24
  • @JeppeStigNielsen thanks. A lot of digging through the git blame before I realized I could just look at the file history lol – pinkfloydx33 Apr 04 '21 at 11:25
  • As of today, to implement the change in `List<>` I am talking about, all it takes is to remove [line 162 in List.cs file](https://github.com/dotnet/runtime/blob/main/src/libraries/System.Private.CoreLib/src/System/Collections/Generic/List.cs#L162). So anyone seeing this can make a pull request and ruin my answer from the other thread (previous comment by me). – Jeppe Stig Nielsen Apr 04 '21 at 11:38