Does System.Linq.Enumerable.Reverse copy all elements internally to an array?

.net, .net-4.0, linq

Solution

Obviously it's not possible to optimize all cases. If some object implements only `IEnumerable<T>` and not `IList<T>`, you have to iterate it until the end to find the last element. So the optimization would be only for types that implement `IList<T>` (like `T[]` or `List<T>`).

Now, is it actually optimized in .Net 4.5 DP? Let's fire up Reflector ILSpy:

public static IEnumerable<TSource> Reverse<TSource>(
    this IEnumerable<TSource> source)
{
    if (source == null)
    {
        throw Error.ArgumentNull("source");
    }
    return ReverseIterator<TSource>(source);
}

Okay, how does `ReverseIterator<TSource>()` look?

private static IEnumerable<TSource> ReverseIterator<TSource>(
    IEnumerable<TSource> source)
{
    Buffer<TSource> buffer = new Buffer<TSource>(source);
    for (int i = buffer.count - 1; i >= 0; i--)
    {
        yield return buffer.items[i];
    }
    yield break;
}

What that iterator block does is to create a `Buffer<T>` for the collection and iterate backwards through that. We're almost there, what's `Buffer<T>`?

[StructLayout(LayoutKind.Sequential)]
internal struct Buffer<TElement>
{
    internal TElement[] items;
    internal int count;
    internal Buffer(IEnumerable<TElement> source)
    {
        TElement[] array = null;
        int length = 0;
        ICollection<TElement> is2 = source as ICollection<TElement>;
        if (is2 != null)
        {
            length = is2.Count;
            if (length > 0)
            {
                array = new TElement[length];
                is2.CopyTo(array, 0);
            }
        }
        else
        {
            foreach (TElement local in source)
            {
                if (array == null)
                {
                    array = new TElement[4];
                }
                else if (array.Length == length)
                {
                    TElement[] destinationArray = new TElement[length * 2];
                    Array.Copy(array, 0, destinationArray, 0, length);
                    array = destinationArray;
                }
                array[length] = local;
                length++;
            }
        }
        this.items = array;
        this.count = length;
    }

    // one more member omitted
}

What have we here? We copy the content to an array. In every case. The only optimization is that if we know `Count` (that is, the collection implements `ICollection<T>`), we don't have to reallocate the array.

So, the optimization for `IList<T>` is not in .Net 4.5 DP. It creates a copy of the whole collection in every case.

If I were to guess why it isn't optimized, after reading Jon Skeet's article on this issue, I think it's because that optimization is observable. If you mutate the collection while iterating, you would see the changed data with the optimization, but the old data without it. And optimizations that actually change behavior of something in subtle ways are a bad thing, because of backwards compatibility.

Problem

Original source