Reconsider version checks in collections?

[stephentoub]

Many of our mutable collection types maintain version numbers. These version numbers are incremented for many (not necessarily all) of the mutating operations performed on the type, e.g.

runtime/src/libraries/System.Private.CoreLib/src/System/Collections/Generic/List.cs

Lines 196 to 198 in 2ba2396

	public void Add(T item)
	{
	_version++;

The version number is then snapshot as part of calling GetEnumerator, and every MoveNext on the resulting enumerator compares the version number that was snapshot against the current version number.

runtime/src/libraries/System.Private.CoreLib/src/System/Collections/Generic/List.cs

Lines 1166 to 1170 in 2ba2396

	public bool MoveNext()
	{
	List<T> localList = _list;
	if (_version == localList._version && ((uint)_index < (uint)localList._size))

This serves as a way to flag some misuse, where mutation is performed during enumeration.

The motivation here is good: help developers find misuse. There are a few problems, though:

1. It adds a little overhead. It's minimal, and this alone is not worth a change for, but it requires an extra Int32 field on the type as well as on the enumerator, it requires an increment operation as part of each mutation, and it requires an extra branch as part of each MoveNext.
2. It doesn't cover all forms of enumeration. If, for example, you enumerate a List<T> via foreach (var item in list) Use(item);, then it applies, but if you change to iterating via for (int i = 0; i < list.Count; i++) Use(list[i]);, then it doesn't.
3. We're considering proposals for enabling the compiler to lower foreach usage down to such for-based iteration, and at that point we'd need to either forego the compiler optimization or give up on many places where this versioning would apply.
4. The inconsistency of if/where it kicks in is visible in higher-level APIs. For example, LINQ's Select operator special-cases IList<T> implementations to use indexing in some situations... using list.Select(Transform).ToArray() will not use the version checks even though the Transform could mutate the list. We also end up avoiding optimizing in this way in other places because it'd be visible.

I'm opening this issue to gauge folks' appetite for removing these versions. Do they still provide good enough value that they're worth keeping? Have they outlived their usefulness?

[ghost]

Tagging subscribers to this area: @dotnet/area-system-collections
See info in area-owners.md if you want to be subscribed.

Issue Details

---

Many of our mutable collection types maintain version numbers. These version numbers are incremented for many (not necessarily all) of the mutating operations performed on the type, e.g.

runtime/src/libraries/System.Private.CoreLib/src/System/Collections/Generic/List.cs

Lines 196 to 198 in 2ba2396

	public void Add(T item)
	{
	_version++;

The version number is then snapshot as part of calling GetEnumerator, and every MoveNext on the resulting enumerator compares the version number that was snapshot against the current version number.

runtime/src/libraries/System.Private.CoreLib/src/System/Collections/Generic/List.cs

Lines 1166 to 1170 in 2ba2396

	public bool MoveNext()
	{
	List<T> localList = _list;
	if (_version == localList._version && ((uint)_index < (uint)localList._size))

This serves as a way to flag some misuse, where mutation is performed during enumeration.

The motivation here is good: help developers find misuse. There are a few problems, though:

1. It adds a little overhead. It's minimal, and this alone is not worth a change for, but it requires an extra Int32 field on the type as well as on the enumerator, it requires an increment operation as part of each mutation, and it requires an extra branch as part of each MoveNext.
2. It doesn't cover all forms of enumeration. If, for example, you enumerate a List<T> via foreach (var item in list) Use(item);, then it applies, but if you change to iterating via for (int i = 0; i < list.Count; i++) Use(list[i]);, then it doesn't.
3. We're considering proposals for enabling the compiler to lower foreach usage down to such for-based iteration, and at that point we'd need to either forego the compiler optimization or give up on many places where this versioning would apply.
4. The inconsistency of if/where it kicks in is visible in higher-level APIs. For example, LINQ's Select operator special-cases IList<T> implementations to use indexing in some situations... using list.Select(Transform).ToArray() will not use the version checks even though the Transform could mutate the list. We also end up avoiding optimizing in this way in other places because it'd be visible.

I'm opening this issue to gauge folks' appetite for removing these versions. Do they still provide good enough value that they're worth keeping? Have they outlived their usefulness?

Author:	stephentoub
Assignees:	-
Labels:	area-System.Collections
Milestone:	Future

[tannergooding]

The main examples of what it protects against are multithreaded access (which is often dangerous for these types anyways, without explicit synchronization) and various cases of sharing where some method in the enumerator ends up mutating the collection itself, right?

I'd guess handling these via analyzers is fairly complex and not feasible, so it wouldn't be "trivial" to replace the functionality for devs that still want it.

We could have some compat or config switch, but in general I've not personally found it useful to have and have often been annoyed at the inconsistency around its tracking/enforcement (within a singular type and also across different collection types) and so would be personally happy to see it go. -- IIRC, LINQ is another example where our ICollection<T> checks can bypass the normal enumerator and end up not failing for modifications

[tannergooding]

IIRC, LINQ is another example where our ICollection checks can bypass the normal enumerator and end up not failing for modifications

A concrete example is the places, like Enumerable.Max, where we use TryGetSpan and then iterate using for. This includes for List<T>

[rickbrew]

In an older version of Paint.NET, I actually relied on this behavior for a background cleanup thread that scanned through a List of weak references. If it got the InvalidOperationException then it would abort the enumeration and schedule another cleanup. It was an interesting design! It avoided locking as well as the overhead of using concurrent collections. I've since switched to a more robust design using concurrent collections.

That said, I think the version checks are an outdated relic of an overly-cautious design era (it's not bad design, mind you, it just hasn't proven its value IMO). It's an easy thing to forget about when implementing your own collection classes, leading to inconsistency between framework-provided and custom collection classes. It's also kind of hard to implement in some cases, and can add a false assurance of safety when it is implemented. And, as you mention, it prevents certain optimizations -- like replacing foreach with for and eliminating the allocation. (fun fact: When I worked at FB on Android stuff, we had annotation processor that would rewrite our Java code in exactly this way. So it has merit and precedent.)

I think I can count on one hand the number of times I've hit an InvalidOperationException due to modification while enumerating ... over the last 20 years.

Ultimately I think the version checks add too much burden on new collection class implementations. It adds a good amount of risk to the implementation cost of new collection classes. I would much prefer collection classes that support immutability (which we have), freezing (which we'll have in 8, and which you also see in WPF), and snapshotting (which I have my own implementations of), all of which provide better and more visible safety guarantees in this area.

That said, I'm a low-level coder at heart and while I'm happy to gain some performance by removing the version checks, I do not have data -- scientific nor anecdotal -- about how helpful (or not) this is for all the other .NET developers out there. So for me, yes please remove them. But I'm not willing to gain some cycles for my app in exchange for a large ecosystem wide reduction in safety. I can always fork a collection class and remove the version checks if I really need those few extra cycles. (Paint.NET has many custom collection classes for all sorts of scenarios)

[rickbrew]

Also, wouldn't that lowering optimization make it basically pointless (in a good way) to implement custom struct enumerators on collections that implement I[ReadOnly]List<T>? If the compiler will lower foreach to for anyway, and if it knows the concrete type, then all we'd need to reach par performance vs. a custom struct Enumerator is an unchecked T this[int i] indexer 🤔

[hamarb123]

Not sure if this is possible, but it could be good to enable the checks on debug mode only, that way you'd get the benefit of it when debugging, but also no performance harm in release mode. I suspect this may not be possible though as I certainly don't know how to do this :)

2. It doesn't cover all forms of enumeration. If, for example, you enumerate a List<T> via foreach (var item in list) Use(item);, then it applies, but if you change to iterating via for (int i = 0; i < list.Count; i++) Use(list[i]);, then it doesn't.

I'm sure you already know this, but I would like to add that if someone is doing it by index, then they definitely should be able to mutate it, it's been useful to me a number of times, they just have to make sure they keep the index up-to-date. In foreach, you can't keep the 'index' up-to-date based on your mutations, so it makes enough sense to block mutations there.

I don't really care if they're removed, I've not seen the exceptions that many times (it was mostly when I was learning basic programming, they were quite useful to see then though as it let me know what the issue was, and if it had looked like it worked, it likely would have been incorrect behaviour), and when I did it was usually because I wanted to mutate it anyway. But if they wanted to lower to the index lookup form, then I think you might as well remove the versioning, since they'd rarely be called, but you certainly shouldn't add the version check in explicitly during lowering imo.

[fowl2]

I've often seen beginners (and sometimes even myself) be "saved" by the current behavior.

Note that it's not just unprotected multi-threading but also eg. the "obvious"

// THIS IS WRONG
foreach (var item in list)
    if (item.ShouldBeDeletedForSomeReason)
        list.Remove(item);

or

// THIS IS WRONG
foreach (var item in list)
    list.Add(item);

Which could manifest in far harder to track down problems. As List is by far the most used collection it's likely to found first. Of course that also makes the potential performance gain more worthwhile as well.

---

• We're considering proposals for enabling the compiler to lower foreach usage down to such for-based iteration, and at that point we'd need to either forego the compiler optimization or give up on many places where this versioning would apply.

If lowering, I imagine the compiler could detect any references to the collection in the body and pessimise in that case. If it's really showing up in profiles as performance sensitive, converting to a for loop could be done manually.

---

Not sure if this is possible, but it could be good to enable the checks on debug mode only, that way you'd get the benefit of it when debugging, but also no performance harm in release mode. I suspect this may not be possible though as I certainly don't know how to do this :)

Changing class layout during debugger attach sounds hairy. I don't think there's any precedent in the BCL for adding extra checks in DEBUG / eliding them !DEBUG (of the entrypoint?). There may be enough other runtime checks that could be optionally added or skipped that might make it worth it to introduce such a mechanism. A bit of design work there to balance complexity of many options vs. no one ever using it if it's too slow vs people leaving it on in prod by mistake, etc.

[Nuklon]

// THIS IS WRONG
foreach (var item in list)
    if (item.ShouldBeDeletedForSomeReason)
        list.Remove(item);

This is a good case of why versioning should be removed. It works fine when you use for loop:

for (int i = 0; i < list.Count; i++)
{
    if (list[i].ShouldBeDeletedForSomeReason)
        list.RemoveAt(i--);
}

This versioning restriction only makes such cases more complicated then it needs to be. If I remove such an item while iterating, it should just continue with the other items.

[theodorzoulias]

@Nuklon if you Remove the list[i], then the list[i] will not stay empty. All items after the i will be moved down by one click, so the list[i] will be replaced with the item that was previously the list[i + 1]. This item is going to be skipped, because in the next iteration of the foreach loop the i will be incremented. This is the problem.

[eiriktsarpalis]

For example, LINQ's Select operator special-cases IList<T> implementations to use indexing in some situations... using list.Select(Transform).ToArray() will not use the version checks even though the Transform could mutate the list.

Being slightly pedantic here, but Transform could only mutate the elements of the collection (provided that they are references) but not the structure of the collection itself. This kind of mutation is out of scope for version checks, as it can be made on List<SomeMutableClass> directly and even to immutable collections like ImmutableArray<SomeMutableClass>.

To your broader point, it seems it can be split into two potentially independent proposals:

1. Removing runtime version checks for collection enumerators.
2. Pursuing more language optimizations that bypass collection enumerators for lists.

It seems to me that 1) offers limited performance benefits and risks regressing the small number of components that do depend on the current behavior in production (as reported above in #81523 (comment)) whereas 2) seems like something users can opt into at compile time.

[tannergooding]

could only mutate the elements of the collection (provided that they are references) but not the structure of the collection itself

This depends on whether Transform can captuire or other reference list. Consider a scenario such as:

public float[] GetFirstElement(List<Vector3> list)
{
    return list.Select(Transform).ToArray();

    float Transform(Vector3 value, int index)
    {
        if (value == Vector3.Zero)
        {
            _ = list.RemoveAt(index);
        }
        return value.X;
    }
}

The same could be true for an instance function Transform where list is a field of the class or any other number of scenarios where the operation doing the selection can get an alias to the collection being enumerated.

[tannergooding]

Such scenarios are not super likely, but they certainly are possible to encounter. LINQ being inconsistent with whether or not it surfaces version changes means that users get an inconsistent experience.

Likewise, we don't strictly update _version in the right places. Consider List<T>.Remove where updating _version is the last thing and therefore an enumeration on another thread can still view what is effectively "torn state"

If we were to keep _version, I believe we'd need to audit our usages of _version and ensure it is always the first thing mutated, before any other fields are mutated.

I think the overall state, inconsistency around its usage/handling/visibility to users, and more all point towards it just being more painful and less useful than it was designed/intended and it'd likely be better (both for perf and general consistency/usability) to remove it.

[tannergooding]

It's also worth pointing out that I don't believe the performance benefits are limited.

The difference between foreach vs for for a collection is significant. We'd likely see extremely non-trivial performance improvements to LINQ if we were able to use for everywhere it was available.

We've already seen such improvements when utilizing the internal TryGetSpan method and even just when generally utilizing for around IList<T> when we have both a count and indexer.

[eiriktsarpalis]

It's also worth pointing out that I don't believe the performance benefits are limited.

The difference between foreach vs for for a collection is significant. We'd likely see extremely non-trivial performance improvements to LINQ if we were able to use for everywhere it was available.

Definitely, but we could pursue these without stripping version checks from the enumerator implementations themselves (which LINQ is already doing in most of its optimized methods). The obvious downside is that the less the enumerator is being used by other components or the compilers, the less likely it is for concurrency bugs to be discovered by the version checker, so perhaps that is reason enough for us to consider removing it altogether.

[danmoseley]

Note that Dictionary<K,V> would still have some important protection against invalid concurrent access -- the guard against loops in the chain. Hypothesis -- all patterns of invalid concurrent access on dictionary will eventually cause a chain and trigger the guard.

[danmoseley]

I don't think I can remember ever discovering a bug through the version check, and as you point out it's incomplete and adds size, so I'm supportive

[benaadams]

Note that Dictionary<K,V> would still have some important protection against invalid concurrent access -- the guard against loops in the chain. Hypothesis -- all patterns of invalid concurrent access on dictionary will eventually cause a chain and trigger the guard.

That's a good example, Dictionary has had enumerator version checks forever; however the the number of concurrent corruptions revealed from the loop guard was high and the enumerator check wasn't serving a purpose to detect those.

In addition with regards to inconsistencies; the pattern above when applied to Dictionary rather than List

foreach (var kv in dict)
    if (kv.Value.ShouldBeDeletedForSomeReason)
        dict.Remove(kv.Key);

Intentionally doesn't increase the version, so that you can use this pattern for performance and allocations; as otherwise you need to collate to a second structure (e.g. List) then do a second loop for the removals.

I'd prefer the version to be removed; with a stretch goal of a analyser to pick up the foreach+modify for list (which is better anyway as is compile time prevention rather than runtime failure)

For unsynchronised concurrent mutations you are already in trouble, and not sure the version adds any value 😅

[danmoseley]

conversely, here's an example of the version check helping spot a bug.
dotnet/msbuild#8458

@ladipro would it have been found if the list was merely corrupted/overwritten/inconsistent?

[danmoseley]

Intentionally doesn't increase the version, so that you can use this pattern for performance and allocations; as otherwise you need to collate to a second structure (e.g. List) then do a second loop for the removals.

Indeed, that is safe (and thus doesn't have a version check, in fact I believe we removed it) -- if we remove version checks, I guess we need to document which patterns are safe and which are not for each type.

[stephentoub]

if we remove version checks, I guess we need to document which patterns are safe and which are not for each type.

We need that, regardless :-)

[danmoseley]

Indeed, but I meant in the code, whereas (in theory!) that's implicitly documented with the version check.

[tannergooding]

One issue is that the version check doesn't necessarily catch all mutations.

There is a bit of a race condition in that since its often the last updated field (rather than the first) an enumerator on another thread can see and potentially miss that a mutation happened.

I'm sure they help in some cases, but overall the inconsistency in handling and other aspects just seems like overhead that could potentially be handled via analyzers or other considerations.

[stephentoub]

whereas (in theory!) that's implicitly documented with the version check.

Yes and no. If I enumerate a list using the enumerator:

foreach (var item in list)
{
    ...
}

sure, synchronous mutations can be caught and flagged. But if I perform the exact same iteration except using the indexer (which is more efficient):

for (int i = 0; i < list.Count; i++)
{
    var item = list[i];
    ...
}

then there's no version check, and it's not "implicitly documented".

The benefits are incredibly inconsistent.

[danmoseley]

Thinking about it another way -- if we didn't have these checks already I'm confident we wouldn't add them today. It would be nice to have another small size win just like when we removed the SyncRoot objects, etc.

[stephentoub]

@jkotas, do you have an opinion here, whether these versions are providing enough value to keep them around?

[benaadams]

conversely, here's an example of the version check helping spot a bug. dotnet/msbuild#8458

@ladipro would it have been found if the list was merely corrupted/overwritten/inconsistent?

That's a race condition between multiple threads; bigger issues at play than this check will discover? And the data structures are called out as not being threadsafe 90% of the data structures aren't threadsafe and have no protections. (Dictionary is special case with the recent addition, however that's to prevent infinite looping, still isn't threadsafe)

[jkotas]

@jkotas, do you have an opinion here, whether these versions are providing enough value to keep them around?

These version checks prevent common source of bugs. As a data point, we should consider what the other programming environments do in similar situations.

I just tried the following in C++:

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> v;

    for (int i = 1; i <= 5; i++)
        v.push_back(i);

    for (auto it = v.begin(); it != v.end(); ++it)
    {
        cout << *it;
        v.push_back(10);
    }
}

I got _ITERATOR_DEBUG_LEVEL assert (in debug builds) telling me that I have done something wrong. (The assert was rather cryptic, but that's a different problem.) Do we want to have worse diagnosability than C++ STL in these situations?

---

A different line of thought: If we were to remove these version checks, the exception should be replaced by easy to explain, intuitive, well-defined behavior. We would not want to leave the behavior undefined. Undefined behaviors are bad, they always take you by surprise and cause dissatisfaction. What would that well-defined behavior be (ie what would the documentation for collection enumerators say)? Ideally, this well-defined behavior would be same across collections.

[tannergooding]

Do we want to have worse diagnosability than C++ STL in these situations?

I think the fact that they are debug only (or opt-in for other builds) is an interesting point. For a typical production app they normally do not exist and have no impact on the size or code execution of the app in total.

We don't quite have the same capability of exposing such things in .NET. We could have the checks compiled in/out based on a static readonly field (which is populated from an AppContext switch), but the backing fields could not be removed and the general higher level checks have some impact on inlining and other factors. -- I've done this to enable opt-in release mode "assert" support for a couple of my lowlevel libraries, like TerraFX.Interop.Mimalloc which is a port of mimalloc to C#, and it works pretty well overall.

I think it's also worth noting that the simple cases like the above are the kind of thing that could be handled by an analyzer. I think the complex cases are more interesting from that perspective, but we ultimately still end up with missing things in for loops, in all manner of LINQ operations, and have a general behavior that is already a bit hit or miss based on the underlying implementation of _version per collection type and per method that updates it.

In the case of LINQ, we've seen some pretty significant perf wins where the underlying implementation uses functionality like TryGetSpan to bypass the iterator, some level of version handling could still be added back in those cases, but it'd require being able to get that information externally to the list.

[benaadams]

Aside an aside; the error message is a warning about a risk:

"Collection was modified; enumeration operation may not execute."

But since it throws an exception; well, it definitely won't execute 😅

[hamarb123]

This (paragraph) is so unrelated, but,
"May not" effectively means "can't" here as opposed to mightn't (like if a teacher were to say to a student: you may not go to the toilet) (gotta love English).

I personally think we should at least remove the version increment from set_Item, and instead just read the item from the list when .Value is called (I know this isn't called directly by users just using a foreach loop, but it can be in other contexts); would this actually be slower?

I think having the local variable not necessarily be the same as what's in the list is not an error, and actually quite useful (e.g. if you want to replace an item in the list, and then do some cleanup on the one you replaced, or read some values from it afterwards, etc), and I think that someone who understands that you have a copy of a reference (or value for value types) on the stack when enumerating probably wouldn't make this particular mistake unless it's very non-obvious that the list has an item set elsewhere (which is probably a documentation error imo if it's not obvious).

[filipnavara]

FWIW I went through some of the crash reports I referred to in #81523 (comment). For a significant number of the cases I think we would get similar diagnostic if Count was saved before starting the enumeration and then checked on every step. I realize it would cover only a subset of the problems that are exposed today but it may be big enough subset, and it's easier to make it into debug-only check (or a runtime config switch even, if we want to continue to use it in Release builds).

[mikernet]

Note that count checks instead of version checks would also result in a loss of an exception when Reverse() or Sort() is called on a list mid-enumeration.

[stephentoub]

Note that count checks instead of version checks would result in a loss of an exception when Reverse() or Sort() is called on a list mid-enumeration.

It also would have limited benefit, at least on List<T>. You'd still need the check as part of MoveNext, so you'd still have that branch, and more importantly you still couldn't lower a foreach to a for loop automatically. It also doesn't reduce the size on 64-bit, where if _version were removed you'd just end up with 4 bytes of wasted padding, and the Enumerator doesn't get any smaller, either. In the common case for List<T>, then, it'd really only save a single inc as part of Add.

[mikernet]

you still couldn't lower a foreach to a for loop automatically

Maybe you can, just only in release builds? Based on this discussion my opinion leans towards keeping the full version checks and lower to for in release builds to effectively elide them. at least during enumeration.

[stephentoub]

Maybe you can, just only in release builds?

I was talking about replacing a version check with a count check. If you still need the check in a build, then you can't change how it's lowered. If you don't need the check in some build, then it doesn't matter whether other builds check version or count.

[danmoseley]

We don't quite have the same capability of exposing such things in .NET. We could have the checks compiled in/out based on a static readonly field (which is populated from an AppContext switch), but the backing fields could not be removed and the general higher level checks have some impact on inlining and other factors. -- I've done this to enable opt-in release mode "assert" support for a couple of my lowlevel libraries, like TerraFX.Interop.Mimalloc which is a port of mimalloc to C#, and it works pretty well overall.

@jkotas is there prior thinking on the idea of having an "opt in, minimal overhead debug mode for release assemblies". something like an appcontext or similar that would enable checks that otherwise get elided. Maybe the field gets left behind, or some ghastly trick with a shared dictionary or something (given it's diagnostic only). I could imagine that facility being handy in other cases. I appreciate though it wouldn't help in @leculver case as it would mean it switched off for customers in general.

[tannergooding]

We effectively do this for some “power scenarios” like hardware intrinsics today.

API review opted to have LoadAligned only require alignment validation in unoptimized code over introducing a new api.

This allowed the single api to be used which does the optimal thing for the hot case while still providing the necessary validation for the cold and startup case (which also covers most unit tests/etc)

[jkotas]

is there prior thinking on the idea of having an "opt in, minimal overhead debug mode for release assemblies".

In .NET Framework, we used to have managed debugging assistants that were basically a way to enable additional debug-only checks in release runtime and CoreLib. It just made things complicated - we struggled with deciding which one of these should be enabled by default and when. The learning was that the on-by-default diagnosics has to be very cheap. Otherwise, it will start impacting F5 performance and people complain. We had to scale back on which one of these debugging assistants are on by default in .NET Framework for this reason.

I am happy that we did not bring them over to .NET Core. If there is cheap high-value diagnostic, we just make it on-by-default to keep things simple.

[jkotas]

We effectively do this for some “power scenarios” like hardware intrinsics today.
API review opted to have LoadAligned only require alignment validation in unoptimized code over introducing a new api..

This sort of undefined behavior is not specific to LoadAligned intrinsic. Optimizations can remove memory accesses in unsafe low-level code, and in turn eliminate exceptions that can be caused by invalid memory addresses.

[mikernet]

or some ghastly trick with a shared dictionary or something

I've used a static ConditionalWeakTable for tacking on diagnostic fields to an object if it's a reference type, and a static readonly bool (treated as a JIT constant) to enable the diagnostic behavior with an appsettings value read on startup, but that is high-overhead to leave enabled.

The more I think about it, I'm not sure that defaulting to lowering foreach to for in release builds to elide these checks is a great idea either. The VS example is a rather compelling argument that they can be quite valuable in production release code. I would prefer to keep them in our DB engine, for example - the safeguards against silently corrupted state being persisted and easier diagnostics are more valuable than a bit of extra perf IMO.

[danmoseley]

@jkotas point taken, but I'm hypothesizing off by default diagnostics.

[jkotas]

Managed debugging assistants were off by default. The debugger enabled them selectively, and you can also enable them using environment variables outside debugger.

We have established patterns to control diagnostic features, for example DebuggerSupport or EventSourceSupport. There is a way to turn these on/off dynamically, there is a way to trim the code when it is not going to be used by the app, and the SDK includes (overridable) defaults for when these are tuned on, off or trimmed. If we were to introduce collections version checks as a configurable feature, I expect that it would follow the established patterns.

[mikernet]

@tannergooding

If we were to keep the checks, I'd think we'd really want to make sure they are consistent and deterministic (e.g. _version is always written before any other changes, helping to ensure they don't see other mutations first)

Are you referring to concurrency scenarios here? I don't see what the difference is in single-threaded access, and for multithreaded access wouldn't that just change when the concurrency problem is detected in equally unpredictable ways?

For example, Thread1 calls a method that modifies a list, _version is incremented, Thread2 calls GetEnumerator() and records the current version, then Thread1 begins making changes to the underlying data as Thread2 is oblivious to the fact that the values it is enumerating are being changed as it does so.

Or is there some other situation where incrementing version before changing the underlying data is more reliable?

[tannergooding]

@mikernet, the general issue is that _version is often the last field mutated today.

This means there are lots of scenarios where changing it last means that concurrency can otherwise "miss" the change or cause other issues.

Ensuring it is consistent/deterministic would imply that _version needs to be the first mutation, before anything else mutates, to help avoid these types of issues (even if it wouldn't completely mitigate them).

[tannergooding]

There's also a lot of inconsistency in "what" counts as a version change

Including between list, array, dictionaries, sets, etc.

[hez2010]

How about making version checks a Debug-only things. In the Release config those checks will be eliminated.

[danmoseley]

How about making version checks a Debug-only things

I think this was discussed above - bear in mind that almost no developers will have debug versions of List, etc. They're not distributed. So it would need some mechanism to have code in the release build of List etc that the jit can choose to emit or not based on some kind of flag. And wiring that flag to the app's build configuration. That would be a rather useful thing to have in general.

[danmoseley]

For many of these types we can probably eliminate the size of version field while still retaining a reasonably sensitive check.

Our de-facto principal is we want to avoid enumerating garbage (by being stuck on an old copy of the backing data) or getting in a loop (by following next pointers in the hashing types). We're OK with seeing a torn collection, apparently, because IIRC that was our reasoning for removing the version++ from Remove() on Dictionaries: we determined it would not lead to those bad effects.

So if that is our principles, it seems to me we can get fairly close without the version field.

For HashSet<T> something like this -- using a mix of _count and _freeCount as the version, you're sensitive to unbalanced adds and removes and (I think in most cases), to trimming and growth. If you mix in _freeList, you're more sensitive still (I think). entries.Length is also available.

Dictionary would likely be much the same, unlike Hashset you can replace in place, but that doesn't affect the backing store or the next pointers.

For List<T>, using _count and _size will catch unbalanced adds and removes, and unbalanced trims and growth. If you want to catch balanced trim/growth you can use the hashcode of the backing array, at a little more expense. What you definitely lose is sensitivity to modification of an entry - but that doesn't matter for the stated goal above. The enumeration will be "correct" in a reasonable sense.

And so forth.

These changes would shrink the objects 4 bytes and remove the (tiny) cost of the version increment from the hot remove/set/update paths, at the expense of a (equally tiny) cost to the enumeration and a (slightly) weaker guarantee. If the faulty access is from another thread, rather than from modification during enumeration on the same thread, the increased indeterminism could further increase your chance of finding any bug during testing/production.

You still lose any checks on the lowering to for's, which was the primary reason this issue was created. However the benefit of shrinking the objects at no incremental cost would still be interesting, IMO, as there's scenarios (like MSBuild) where there can be huge numbers of collections and the 4 bytes adds up. Also, it would benefit any cases where the foreach's were not lowered, such as perhaps an older compiler or cases the compiler can't lower.

Does this reasoning seem reasonable?

[jnm2]

If the cost of enumeration is overall increasing, how do you evaluate whether the decrease in modification cost (and memory space) offsets the cost enough? I would expect enumeration to be at least slightly more frequent (hot?) than modification operations, if not significantly more.

[danmoseley]

I would expect enumeration to be at least slightly more frequent (hot?) than modification operations, if not significantly more.

You're probably right. Still, it's hard to imagine the cost is visible either way. The only reason to do this would be to eliminate the field

[Neme12]

This is a good case of why versioning should be removed. It works fine when you use for loop:

Not that I have any strong opinion one way or the other, but this in particular is not a good reason. It would still only keep working when you use a for loop because there is no index in a foreach loop that you can decrement.

[Neme12]

If the version checks were removed, why does the compiler still have to optimize List<T> enumeration to a for loop to be more efficient? Why couldn't the JIT then emit equivalent code in these cases?