C#•2w ago

List<> struct Enumerator vs array enumerator

why List<> struct Enumerator holds current value instead of just index to that value like in array enumerator?

73 Replies

https://source.dot.net/#System.Private.CoreLib/src/libraries/System.Private.CoreLib/src/System/Collections/Generic/List.cs,9c3d580a8b7a8fe8,references List<> struct Enumerator also hold index

DanchykOP•2w ago

but why then it holds index and current value instead of just index?

ティナ•2w ago

idk, probably it is newer? most of the IEnumerator implementation now caches Current because it may not be O(1) get from its data structure

DanchykOP•2w ago

but accessing item by index in array is constant time, why cache Current ?

ティナ•2w ago

mb, the words are not good, time complexity is unrelated here i mean keep returning Current by _list[_index] maybe slightly slower than caching it at the first (in MoveNext) and keep returning the same _current for subsequent access

DanchykOP•2w ago

make sense when same Current accessed multiple times, but are there any other cases when it makes sense?

Kuurama•2w ago

From IEnumerator<T>: // Returns the current element of the enumeration. The returned value is // undefined before the first call to MoveNext and following a // call to MoveNext that returned false. Multiple calls to // GetCurrent with no intervening calls to MoveNext // will return the same object. new T Current { get; } Maybe because they don't want a different behavior on calling Current depending on the underlying data structure? If index is 0 by default and it's just a property forwarding to the inner list. It has a different meaning than the IEnumerator<T>.Current is supposed to mean. If it's -1, it's gonna throw. And they might want not to have to deal with a if case on the Current property. So caching is better than 1 comparison every access

ティナ•2w ago

ArrayEnumerator index started from -1, there should be no difference as long as calling Current causes undefined behaviour before MoveNext

Kuurama•2w ago

Calling Current with index -1 is gonna crash no? on everything else, it's unititialized memory no? Better optimising not to have to check for -1 i guess

MODiX•2w ago

ティナ

REPL Result: Failure

int[] arr = new int[10];
            IEnumerator e = arr.GetEnumerator();
            e.Current

int[] arr = new int[10];
            IEnumerator e = arr.GetEnumerator();
            e.Current

Exception: InvalidOperationException

- Enumeration has not started. Call MoveNext.

- Enumeration has not started. Call MoveNext.

Compile: 283.531ms | Execution: 21.220ms | React with ❌ to remove this embed.

Kuurama•2w ago

hum, beside multiple access, no clue then. :_SuwonShrug: Didn't know that was gonna throw lol Thanks

ティナ•2w ago

public object? Current
        {
            get
            {
                nint index = _index;
                Array array = _array;
 
                if ((nuint)index >= array.NativeLength)
                {
                    if (index < 0)
                    {
                        ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumNotStarted();
                    }
                    else
                    {
                        ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumEnded();
                    }
                }
 
                return array.InternalGetValue(index);
            }
        }

public object? Current
        {
            get
            {
                nint index = _index;
                Array array = _array;
 
                if ((nuint)index >= array.NativeLength)
                {
                    if (index < 0)
                    {
                        ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumNotStarted();
                    }
                    else
                    {
                        ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumEnded();
                    }
                }
 
                return array.InternalGetValue(index);
            }
        }

welp it checks the index

Kuurama•2w ago

but not for List?

DanchykOP•2w ago

but not for list

ティナ•2w ago

they just assign default to list iirc

Kuurama•2w ago

:aussmie: hold on, could you try the same code with list does it throw too?

ティナ•2w ago

private T? _current;

private T? _current;

oh nullable

           object? IEnumerator.Current
            {
                get
                {
                    if (_index <= 0)
                    {
                        ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen();
                    }
 
                    return _current;
                }
            }

           object? IEnumerator.Current
            {
                get
                {
                    if (_index <= 0)
                    {
                        ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen();
                    }
 
                    return _current;
                }
            }

throw btw its _index start from 0

MODiX•2w ago

ティナ

REPL Result: Failure

List<int> a=new();
            IEnumerator e=a.GetEnumerator();
            e.Current

List<int> a=new();
            IEnumerator e=a.GetEnumerator();
            e.Current

Exception: InvalidOperationException

- Enumeration has either not started or has already finished.

- Enumeration has either not started or has already finished.

Compile: 355.219ms | Execution: 22.120ms | React with ❌ to remove this embed.

Kuurama•2w ago

what about the public T Current ? I'm lost rn X)

DanchykOP•2w ago

generic Current should'n throw exception

Kuurama•2w ago

How do you access it differently?

DanchykOP•2w ago

IEnumerator<int> e=a.GetEnumerator();

ティナ•2w ago

the generic one doesnt throw i guess

public T Current => _current!;

public T Current => _current!;

MODiX•2w ago

ティナ

REPL Result: Success

List<int> a = new();
            IEnumerator<int> e = a.GetEnumerator();
            e.Current

List<int> a = new();
            IEnumerator<int> e = a.GetEnumerator();
            e.Current

Result: int

Compile: 294.050ms | Execution: 21.493ms | React with ❌ to remove this embed.

Kuurama•2w ago

Interresting

DanchykOP•2w ago

:email:

Kuurama•2w ago

Same with array i guess

ティナ•2w ago

Array class doesnt implement the generice version, it just implements IList

MODiX•2w ago

ティナ

REPL Result: Failure

int[] a = new int[10];
IEnumerator<int> e = a.GetEnumerator();

int[] a = new int[10];
IEnumerator<int> e = a.GetEnumerator();

Exception: CompilationErrorException

- Cannot implicitly convert type 'System.Collections.IEnumerator' to 'System.Collections.Generic.IEnumerator<int>'. An explicit conversion exists (are you missing a cast?)

- Cannot implicitly convert type 'System.Collections.IEnumerator' to 'System.Collections.Generic.IEnumerator<int>'. An explicit conversion exists (are you missing a cast?)

Compile: 352.310ms | Execution: 0.000ms | React with ❌ to remove this embed.

ティナ•2w ago

thats pretty old

Kuurama•2w ago

any reason why?

DanchykOP•2w ago

array doesn't have generic enumerator

DanchykOP•2w ago

reason why i interested in implementation of Enumerator, i'm writing own PooledArray and need to make decision how to implement enumerator

DanchykOP•2w ago

caching current value leads to bigger heap allocations in case then Enumerator boxes to interface, especially for large structs

Kuurama•2w ago

Part of why you asked why the list enumerator caches it I Believe

DanchykOP•2w ago

exactly

Kuurama•2w ago

No way to know who wrote the List version? :KEK:

DanchykOP•2w ago

one sec

ティナ•2w ago

list has a method returning the struct directly iirc

Kuurama•2w ago

Because maybe there is some good reasons. Maybe not :kappa: It's funny to see that some things are implemented only on half the things lol

DanchykOP•2w ago

Kuurama•2w ago

Still better to have them around even little by little though

ティナ•2w ago

https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.list-1.getenumerator?view=net-8.0

List<T>.GetEnumerator Method (System.Collections.Generic)

Returns an enumerator that iterates through the List<T>.

Kuurama•2w ago

Stephen?

ティナ•2w ago

the one that return the struct directly

DanchykOP•2w ago

looks like i should watch all videos about IEnumerable with Stephen Toub

Kuurama•2w ago

https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.ienumerator-1?view=net-9.0 Even this example shows caching the value

IEnumerator<T> Interface (System.Collections.Generic)

Supports a simple iteration over a generic collection.

Kuurama•2w ago

If you get the Reasons behind it. It would be cool to let us know here!

DanchykOP•2w ago

i plan to watch videos with Stephen about IEnumerable, i'll let you know if i find anything interesting

ティナ•2w ago

struct ReadOnlyListIt<T>:IEnumerator<T> {
    private readonly IReadOnlyList<T> _list;
    private T _current;
    private int _index;

    public T Current => _current;

    object IEnumerator.Current => Current;

    public void Dispose() {
        throw new NotImplementedException();
    }

    public bool MoveNext() {
        if(_index >= _list.Count) { return false; }
        _current = _list[_index++];
        return true;
    }

    public void Reset() {
        throw new NotImplementedException();
    }
}

struct ReadOnlyListIt<T>:IEnumerator<T> {
    private readonly IReadOnlyList<T> _list;
    private T _current;
    private int _index;

    public T Current => _current;

    object IEnumerator.Current => Current;

    public void Dispose() {
        throw new NotImplementedException();
    }

    public bool MoveNext() {
        if(_index >= _list.Count) { return false; }
        _current = _list[_index++];
        return true;
    }

    public void Reset() {
        throw new NotImplementedException();
    }
}

you can have a simple IEnumerator for all IReadOnlyList (but it cannot detect modification), make sense to cache current cuz you dont know if the indexer is O(1)

DanchykOP•2w ago

it's make sense if you don't know about indexer implementation

Kuurama•2w ago

But what if you do it when you know it's O(1)? Maybe it's about having the same size for all IEnumerator<T> for some compiler trick somewhere?

DanchykOP•2w ago

i don't think

Kuurama•2w ago

or reinterpret cast or whatever? Oh well that wouldn't make sence given value types

DanchykOP•2w ago

i see another reason to cache current if you cache Current you ensure what it cannot be changed ( If value type, or cannot be assigned other reference for ref type ) List Enumerator have also version check

Kuurama•2w ago

ooh

DanchykOP•2w ago

Kuurama•2w ago

No deep immutability hits

ティナ•2w ago

they tends to throw if the version not match

Kuurama•2w ago

Mystery solved then

ティナ•2w ago

but i think that wouldnt happen in concurrent collection

Kuurama•2w ago

don't they freeze the Stuff in a new array? Saw that for concurrent bag last time I checked. I was kinda disappointed Maybe it's not the case. or not anymore. But I'm fairly sure it copies the content as a Snapshot for current values when doing the enumerator. It just locks while doing the copy.

ste•2w ago

If it wasn't cached (in Current), it would have to check the version every time the Current property is called, since the underlying array could have been changed (due to List expansion) Sorry if you have already figured this out, was too lazy to read all the conversation

DanchykOP•2w ago

probably it's cached to prevent version check on every Current access, but i'm not sure interesting, when you use indexer on List<> to set value it increments version but if you use CollectionsMarshal.AsSpan(list) and sets value by indexer versions doesn't change

ティナ•2w ago

the setter of list is skipped

DanchykOP•2w ago

doesn't throw

DanchykOP•2w ago

throws

DanchykOP•2w ago

confused behavior

ティナ•2w ago

AsSpan get the internal array of list so you can directly set the element to the array without using the indexer of list

ste•2w ago

Yeah, you're kind of «on your own» when working with the underlying array. Just like when the span keeps referring to the same old array even if the List expands and resizes itself

Kuurama•2w ago

collection marshal X) not SafeMarchal

DanchykOP•2w ago

look at ArraySegment<T> Enumerator, it doesn't cache Current

Kuurama•2w ago

So it's increasing memory use so less instructions are made Oh, I forgot about that

Gaming

Programming

List<> struct Enumerator vs array enumerator

Did you find this page helpful?