-3

List<T>.Enumerator “snapshots” list version upon creation by _version = list._version;. This allows enumerator to halt enumeration when List<T> changed during it.

This behavior likely originates from need to move what is hidden under foreach statement into forefront while in obedience to contract (for each).

foreach(var i in numbers)
{
  if (i > 3)
    numbers.Remove(i);
}

After removal item order is shifted to left. If there is no versioning, then enumeration can continue on the 2nd next item. By this chance versioning seems fine.

In contrast

var enumerator = numbers.GetEnumerator();
while (enumerator.MoveNext())
{
  var i = enumerator.Current;
  if (i > 3)
    numbers.Remove(i);
}

does not have for each contract. Now it is just decision of List<T>.Enumerator to be exhaustive making sure it is.

Let consult Sort method

public void Sort() => Sort(0, Count, null);
public void Sort(int index, int count, IComparer<T>? comparer)
{
   … // Some code omitted. Code bellow differently formatted.   

  if (count > 1)
    Array.Sort<T>(_items, index, count, comparer);

  _version++;
}

I think, I wonder who would ever do

foreach(var i in numbers)
{
  if (some condition)
    numbers.Sort();
}

Similar applies to Reverse.

public void Reverse() => Reverse(0, Count);
public void Reverse(int index, int count)
{
    … // Some code omitted. Code bellow differently formatted.

  if (count > 1)  
    Array.Reverse(_items, index, count);
            
  _version++;
}

On other hand

foreach(var i in numbers)
{
  if (i % 3)
    numbers.Reverse();
}

I expect could produce nice series but I am not mathematician.

This count there are some points from which List<T>.Enumerator can be viewed:

  1. It is exhaustive as feature and negative impact on List<T> and enumerator performance should be consumed as levy.
  2. It is exhaustive as safeguard. Versioning in this case substitutes analyzer function that helps developers to avoid items miss or repeating them during enumeration due items shift. For this point penalties are debatable.
  3. List<T> exhibits wastrel implementation.
  • Versioning addresses truly only cases that causes left/right items shift copy – removal, insertion.
  • Version is also handled for Reverse, Sort but what scenario allows for accidental such change during enumeration? I guess none.
  • Version is handled in methods: T this [int index] set – there it can make sense but I doubt anyone would ever expect previous value when it is deliberately replaced at exact index; Add – adds to end and enumerator perfectly can work with this (relying on size), no need for version; Clear – affects enumeration but in safe way, check against size is sufficient; EnsureCapacity – I do not get how this can threat enumeration; Insert – avoids items repetition; InsertRange – avoids items miss and repetition, RemoveAll, RemoveAt, RemoveRange – avoids items miss
  • If so then, in total, this most likely means that some methods could be freed from versioning by virtue of common sense and/or low probability of misuse while for shifting ones this counts still debatable.

Worth noting that _version is not protected against overflow. That it turn draws back to point 2. If versioning should serve run-time, should it be overflow protected? Likely.

It seems so List<T> versioning was designed in order to serve development (time) and there could be provided analyzers, checking shifting methods inside loops. Exception cannot go unnoticed, that is for sure. Also shift can occur outside the loop (method call).

7
  • 2
    I'm not sure I understand your code. are you changing the list so many times that version overflows and goes to -1?
    – Ewan
    Feb 20 at 22:37
  • 2
    I cant find anything about this check making enumeration slow. do you have links?
    – Ewan
    Feb 20 at 22:42
  • @Ewan There’s plenty of resources about SZArrayEnumerator vs List<T>.Enumerator performance. One plain enough stackoverflow.com/questions/454916/…. And yes, _version in sample come back to its initial value, 0.
    – Yarl
    Feb 21 at 17:15
  • that link doesnt mention version and neither does the jon skeet link in the comment.
    – Ewan
    Feb 22 at 14:37
  • @Ewan, if you compare SZGenericArrayEnumerator<T> with List<T>.Enumerator you get that they differ only in versioning logic. There’s difference also in Current but these could go same.
    – Yarl
    Feb 22 at 20:47

3 Answers 3

6

So if there is change to List, there is in fact no threat to enumeration.

Yes there is. You might repeat an element, or skip it. Just because the index refers to an element doesn't mean the enumerator is valid.

What you've shown is that if you carefully craft a situation, you can trick one of the safety checks. You are staggeringly unlikely to come across this situation accidentally. It remains a beneficial check for the vast majority of uses.

List is not written to be immune to carefully crafted malice, but to be robust to ordinary situations.

6
  • I agree on rearranging before enumeration ends can produce awkward sequences. Nevertheless, SZGenericArrayEnumerator<T> (.NET Core) nor SZArrayEnumerator (.NET Framewokr) do any checks. So enumerate half array, then Array.Reverse, then rest is considered valid result? I would say rather than robustness hack mayhap redundancy. Why List<T>.Reverse means new _version while Array.Reverse not? There is little sense in List<T> versioning. I cannot imagine any scenario where this happens from time-to-time while in most cases there is no change before enumerator reaches end.
    – Yarl
    Feb 21 at 20:26
  • 1
    @Yarl regarding list vs array, I think of arrays as basically primitives, and as such they don't follow the usual rules of API design: regardless of performance considerations, they are not designed to provide any fun guarantees: they may be handed off to unmanaged code etc. so they cannot be versioned. Lists and other data-structures built with arrays, however, make certain guarantees, but may require you to use them synchronously. (that is to say, the array enumerator can't know and doesn't care what you do, which is fine by the contract of IEnumerator) Feb 22 at 11:05
  • @VisualMelon, yes I guess you’re not wrong. I was wondering if this enumerator is some typified enumerator, e.g. state consistent enumerator. Nonetheless technically there is no need to end enumeration just because collection changed, so what would be wrong if this is analyzer rule?
    – Yarl
    Feb 22 at 12:38
  • 2
    @Yarl it could certainly be a useful analyser, but it wouldn't suffice to cover more dynamic cases: if the list isn't entirely local, then any virtual call could lead to its modification which would be impossible to detect by analyser without an ownership system like Rust has (i.e. if you don't know all the code that could modify the list, there is nothing you can do, and because C# lets you copy references freely this cannot be implemented in C# without an awful lot of annotations and analysers on top). Feb 22 at 12:45
  • 1
    (note also that in some cases the JIT will effectively disable the version checks if it detects that it is impossible for the list to be modified on the same thread: the check is there, but it doesn't update the value of the version, so it reduces to a branch-prediction-friendly test (because it never fails), but there is more to the overhead of enumerating a list than the version checks) Feb 22 at 12:50
0

OK so, my understanding of your code is that you alter the list 2 times max int number of times. Each change increments the int _version so that it loops over max int and goes to negative max int, then all the way back up to -1.

This breaks the internal check that _version should be equal to the expected _version when you change it one more time as its now equal when you have changed the list.

Congrats you found a bug!

But. Consider how you might eliminate this bug. If you just change it to long then you still have the same bug, just a higher number of changes. Its not a trivial problem to solve as you essentially have n possible versions of a list, with no real limit.

Should you prevent changes to a list which has reached your max? Should you invalidate linked enumerations when the underlying list changes?

We can only guess on the reasons why this way was chosen, you can see that all options have downsides. However! Given that _version is int and not uint, I have feeling this is just an oversight and it should be possible to implement a fix without major downsides.

7
  • Given that _version is int and not uint, I have feeling this is just an oversight I don't follow: why would uint be significant? Feb 22 at 16:12
  • _version is only ever incremented and starts at 0. Although it makes no difference to a comparison, a human thinking about it would naturally choose a uint and then consider overflow and then ulong. If it was ulong or uint, or even byte I would assume a conscious choice where sign and max had been taken into consideration. But int? its just the default.
    – Ewan
    Feb 22 at 16:30
  • uint isn't CLS, which may be factor (shouldn't matter though)? Anyhow, your last sentence reads as though changing to uint would be a fix, which I'm guessing wasn't the intention :P Feb 22 at 16:38
  • no, im just trying to guess at intentions
    – Ewan
    Feb 22 at 17:10
  • Problem is not bug or performance in core but sense saturation. If versioning should prevent unintentional changes during foreach what scenario can be about to Reverse, Sort, RemoveAll during foreach enumeration? Still these make new version. When enumerating (while(enumerator.MoveNext()) it’s really on ease that anyone does stopping it intentionally to make changes not otherwise but this is not possible. So, versioning proofs to not be any conceptual enumerator implementation, rather serves development time. Proper code never causes version violation during production run.
    – Yarl
    Feb 22 at 20:33
-1

As I see the case, there was no best one options for authors than to exploit control flow constructs in List<T> methods in order to preserve common contract of foreaching.

I mean mostly that not everyone needs help in ensuring something is valid/complete and that nobody ever said that enumeration has to be definitely exhaustive.

When this versioning caught sight of world should be that time accompanied with at least fast enumerator that does not check against version that could be consumed manually.

Or even better whole List<T> should have been provided with fast counterpart that does not version. (System.Collection.Performance)

It would be copy-paste-edit epsilon-zero-like implementation.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.