Proposal: Make it easier to iterate through an ArraySegment

[jamesqo]

Approved API shape

public struct ArraySegment<T>
{
    public Enumerator GetEnumerator();

    // Change existing internal class ArraySegmentEnumerator to:
    public struct Enumerator : IEnumerator<T>
    {
        public bool MoveNext();
        public T Current { get; }
        public void Dispose();
        // NOT public:
        //void IEnumerator.Reset();
    }
}

• Change existing internal class ArraySegment<T>.ArraySegmentEnumerator to struct (see above).

Value: Saves 1 boxing per enumerator:

foreach (T item in ArraySegmentReturningMethod()) { }

Note: I know that Span is supposed to supplant ArraySegment, this was added way back in 2.0, etc. However, the indexer seems so trivial to add and could help increase readability of existing code.

[karelz]

What is the motivation for Enumerator and GetEnumerator? The foreach cycle already works today, because struct ArraySegment<T> implements IEnumerable<T> and IEnumerable.

[benaadams]

That's really weird it does already have an Enumerator (class ArraySegmentEnumerator); wonder why it doesn't expose it as a struct enumerator? Would get the boxed IEnumerator version for free(ish) - apart from the boxing bit.

Maybe to keep it private?

[jamesqo]

@karelz As @benaadams just mentioned it allocates since it is a class and is passed around as an IEnumerator. Even if we made it a struct it would box currently.

[mellinoe]

Since the current nested enumerator type isn't exposed, can we just replace it with a struct enumerator (implementing IEnumerable) and expose that directly?

[justinvp]

Both IEnumerable<T> and IEnumerable are implemented explicitly, so we're free and clear to add a public GetEnumerator() method that returns a struct enumerator that would avoid any boxing. If we do make the enumerator a struct and make it public, it'd be nice to name it Enumerator instead of ArraySegmentEnumerator, which matches the naming used for List<T> and Dictionary<TKey, TValue>'s nested struct enumerators.

[jamesqo]

@mellinoe

Since the current nested enumerator type isn't exposed, can we just replace it with a struct enumerator (implementing IEnumerable) and expose that directly?

I think we may want to create a new type, actually. For reference, here is how the enumerator is currently implemented: ArraySegmentEnumerator

        private sealed class ArraySegmentEnumerator : IEnumerator<T>
        {
            private T[] _array;
            private int _start;
            private int _end;
            private int _current;

            internal ArraySegmentEnumerator(ArraySegment<T> arraySegment)
            {
                Contract.Requires(arraySegment.Array != null);
                Contract.Requires(arraySegment.Offset >= 0);
                Contract.Requires(arraySegment.Count >= 0);
                Contract.Requires(arraySegment.Offset + arraySegment.Count <= arraySegment.Array.Length);

                _array = arraySegment._array;
                _start = arraySegment._offset;
                _end = _start + arraySegment._count;
                _current = _start - 1;
            }

            public bool MoveNext()
            {
                if (_current < _end)
                {
                    _current++;
                    return (_current < _end);
                }
                return false;
            }

            public T Current
            {
                get
                {
                    if (_current < _start) ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumNotStarted();
                    if (_current >= _end) ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumEnded();
                    return _array[_current];
                }
            }

            object IEnumerator.Current
            {
                get
                {
                    return Current;
                }
            }

            void IEnumerator.Reset()
            {
                _current = _start - 1;
            }

            public void Dispose()
            {
            }
        }

We can make it faster by removing some redundant checks/fields (eliminating _start, unconditionally incrementing _current, not checking during Current, etc.):

public struct Enumerator
{
    private readonly T[] _array;
    private readonly int _count;
    private int _current;

    internal Enumerator(ArraySegment<T> segment)
    {
        _array = segment.Array;
        _count = segment.Count;
        _current = _segment.Offset - 1;
    }

    public bool MoveNext() => _current++ < end;

    public T Current => _array[_current];
}

But this would break existing behavior.

[justinvp]

But this would break existing behavior.

We should just remove the checks. IEnumerator<T>.Current is documented as "undefined" in these cases so there is no requirement to throw (non-generic Current is documented as throwing in one of those cases). It's a behavior change, but highly unlikely that someone would depend on it throwing.

Also note: ArraySegmentEnumerator is currently marked as [Serializable]. Since .NET Core hasn't shipped with serialization support yet, now's our chance to make it a struct, rename, and reduce the fields.

[benaadams]

Also https://msdn.microsoft.com/en-us/library/system.collections.ienumerator.reset(v=vs.110).aspx

The Reset method is provided for COM interoperability. It does not necessarily need to be implemented; instead, the implementer can simply throw a NotSupportedException.

[JonHanna]

The Reset here is trivial enough that it's not a burden. Since it's not going to gain much to get rid of it, then even if it'll probably never affect anyone ever (did anyone ever even use Reset in COM?) it may as well stay in.

[benaadams]

Need to additionally store _start for Reset

[JonHanna]

Ah yes.
Kill it, so. It's a weird thing to use, and if someone is broken by it, it's won't be hard to upgrade (hold onto a copy of the struct0.

[karelz]

I am not sold on exposing new APIs just because we can, unless there is real data showing it matters (perf wise in this case). Saving 1 boxing is not IMO worth it, unless there is real-world code (not a made up example) where the saving would make a noticeable difference. Or unless we believe it is a pattern we should have everywhere ...

[jamesqo]

@karelz It is kind of a chicken-and-egg problem... ArraySegment<T> is used by high-perf code. High perf code doesn't want boxing, so avoids the foreach and writes it the uglier way.

Saving 1 boxing

*every time the ArraySegment is iterated over.

[karelz]

I don't think it is chicken-and-egg problem. I think it is premature optimization problem - i.e. optimization before we measure.
On top of that if some high-performance code hits this particular boxing on hot path, it can easily avoid it by rewriting the code into for-cycle. And if it happens for a few projects, I expect we will get a report with real-world data/use case. The discussion will be different in such case.

The problem is that we could spend decades optimizing one boxing here and another instruction there and we may or may not make a noticeable difference in all that effort (and if we did, it would be by a chance/accident).
If it is simple (high-confidence) change which has no downside, then sure, let's do it - why not, right? If it is not so simple (e.g. needs to add public API), we should really think twice if it is worth the effort and impact (yet another public method in IntelliSense, potentially restricting further flexibility of the type, etc.).
On top of that if we spend time in micro-optimizations, we may miss the high-level architectural perf problems - like multiple buffer copying (which Span<T> is trying to solve), which pop only in measuring real-world end-to-end scenarios. Span<T> is the high-performance API in the space, so I would not overoptimize ArraySegment now.

If there are other reasons (e.g. it is general pattern to have GetEnumerator() with Enumerator whenever you implement IEnumerator), then I am willing to change my position.

Anyway, I am be wrong as well, so am fine presenting the option at API review.

[stephentoub]

Regarding the enumerator, we should expose the internal enumerator as a struct Enumerator and have a public GetEnumerator return it. It's little work, it fixes a gaping hole in the API, and such boxing does add up. This is part of peanut butter effect across .NET... we've historically not cared about this or that little allocation because on its own it's not consequential, but when you add all of those up across all such APIs, they can be impactful.

As for the indexer, we should add that, too... but it's already there as part of the IList explicit implementation:
https://source.dot.net/#System.Private.CoreLib/src/System/ArraySegment.cs,154
The change is just to make it an implicit implementation.

[karelz]

Regarding the enumerator, we should expose the internal enumerator as a struct Enumerator and have a public GetEnumerator return it.

That sounds reasonable. I was afraid we would have to add yet another public inner enumerator class (I didn't realize the existing one is private). Exposing existing one follows general enumerator pattern on perf-sensitive classes.

[jamesqo]

@karelz @stephentoub Please see https://github.com/dotnet/corefx/issues/14170#issuecomment-264604632 and the subsequent comments. If we expose the existing implementation, we will want to change behavior in some corner cases in Current and Reset to reduce struct size. Is that OK?

[karelz]

I don't think we need to change the behavior as you describe above. Your simplified code without checks is moreover incorrect - it will allow misuse of the API (when people forget to call MoveNext first, the Current will either throw IndexOutOfRangeException or return data you should not have access to). That does not sound desirable.

[jamesqo]

@karelz There is similar code in ImmutableArray's enumerator. In the real world 99% of use cases of this API are through foreach, and the compiler will always generate the correct code and put MoveNext first. I think we should put performance first over corner cases here.

(when people forget to call MoveNext first, the 'Currentwill either throwIndexOutOfRangeException` or return data you should not have access to)

ArraySegment already exposes the entirety of the underlying array, so I don't see why this is an issue. s.Array[s.Offset + s.Count] = "hi"

[stephentoub]

If we expose the existing implementation, we will want to change behavior in some corner cases in Current and Reset to reduce struct size. Is that OK?

That is an unrelated request. Even if didn't expose the existing implementation and instead exposed a new one and a new GetEnumerator method, it would still be a breaking change to have different behavior for that newly exposed enumerator, as recompiling code that targeted GetEnumerator which should from targeting the interface method to the instance method, and it would get the new behavior.

[jamesqo]

it would still be a breaking change to have different behavior for that newly exposed enumerator, as recompiling code that targeted GetEnumerator which should from targeting the interface method to the instance method, and it would get the new behavior.

Can you give an example? Since currently GetEnumerator is explicitly implemented, the only way that existing code when recompiled will get the new enumerator is through foreach. And since foreach never calls Reset and always calls MoveNext and Current in the proper order, it seems like those changes wouldn't affect it.

[stephentoub]

Since currently GetEnumerator is explicitly implemented

Hmm, I see, I think you're right.

That said, I'm not convinced anything should change in the implementation, i.e. I'm not convinced it's worthwhile either taking a breaking change for existing usage of ArraySegment as IEnumerable or introducing yet another enumerator. Size-wise, the best you could do would be to get rid of one Int32 field (_start). And the proposed changes not only result in not properly validating and throwing for misuse, but can actually result in MoveNext returning true when it shouldn't, in that usage could end up wrapping around. I agree that it'd be rare to see resulting breaks, but what's the benefit of the change?

The recommended path forward will be to use Span, not ArraySegment, so we're really only doing this to make existing usage better, and while I've not measured, I'd bet that exposing the Enumerator and making it a struct (eliminating the interface calls, making things more easily inlinable, avoiding the allocation when foreach'd, etc.) addresses >= 90% of the possible gain. If someone really cared about throughput, they wouldn't be using the enumerator at all, and instead would just use a for loop, looping over the array directly from offset to offset+count, which is going to be better than anything we can do in the struct enumerator. So we'd be taking a breaking change (or adding additional code) to account for maybe a 10% extra improvement, if that, for a scenario where if someone actually cared about throughput, they wouldn't have written that code anyway.

Again, though, I'm guessing on the actual costs... someone should measure. I'm also not entirely against such a change, I just want to make sure if we make it it's for the right reasons. I doubt such a change would be ported back to desktop, making it yet another difference between desktop and core, something we strive to avoid unless there's a strong reason for it.

[karelz]

API review:
The indexer is already part of #18007 -- we should remove it from this proposal.
Adding GetEnumerator + changing the internal class ArraySegmentEnumerator to public struct Enumerator is approved (we need update of the top proposal).

[karelz]

Updated proposal on the top.

[AlexRadch]

@karelz I am working on this. But I have 2 questions:

1. Should I make Enumerator.Reset() method public? Why it is hidden in proposal on top?
2. Should I make Enumerator.Dispose() method public? Why it is hidden in proposal on top? I think it should be public. For example List<T>.Enumerator.Dispose() is public.

[karelz]

Good questions - @jamesqo @stephentoub @weshaggard can you guys advise here?

[stephentoub]

Dispose should be public. Reset can be an explicit interface implementation.

[karelz]

Thanks @stephentoub. Spec on the top updated.

[AlexRadch]

@stephentoub Thanks. I made Dispose public.

[AlexRadch]

@karelz Issue can do closed see dotnet/coreclr#8559

[jamesqo]

@AlexRadch There have to be tests added for the new API and it has to be exposed in corefx.

[danmoseley]

@AlexRadch do you expect to have time to expose this? Otherwise it can't be used.

[karelz]

No response for 1.5 months, unassigning the issue - it is again up for grabs, available for anyone to pick it up and finish it. Who's up for it?

[jamesqo]

@karelz I'm exposing/adding tests for this along with another ArraySegment API.

[karelz]

Thanks for heads up, assigned to you.