c# - Performance of Skip (and similar functions, like Take)

Question

I just had a look at the source code of the Skip/Take extension methods of the .NET Framework (on the IEnumerable<T> type) and found that the internal implementation is working with the GetEnumerator method:

// .NET framework
    public static IEnumerable<TSource> Skip<TSource>(this IEnumerable<TSource> source, int count)  
    {
        if (source == null) throw Error.ArgumentNull("source"); 
        return SkipIterator<TSource>(source, count); 
    }

    static IEnumerable<TSource> SkipIterator<TSource>(IEnumerable<TSource> source, int count) 
    {
        using (IEnumerator<TSource> e = source.GetEnumerator()) 
        {
            while (count > 0 && e.MoveNext()) count--;
            if (count <= 0) 
            { 
                while (e.MoveNext()) yield return e.Current;
            } 
        } 
    }

Suppose that I have an IEnumerable<T> with 1000 elements (underlying type is List<T>). What happens if I'm doing list.Skip(990).Take(10) ? Will it iterate througt the 990 first elements before taking the last ten? (this is how I understand it). If yes, then I don't understand why Microsoft didn't implement the Skip method like this:

    // Not tested... just to show the idea
    public static IEnumerable<T> Skip<T>(this IEnumerable<T> source, int count)
    {
        if (source is IList<T>)
        {
            IList<T> list = (IList<T>)source;
            for (int i = count; i < list.Count; i++)
            {
                yield return list[i];
            }
        }
        else if (source is IList)
        {
            IList list = (IList)source;
            for (int i = count; i < list.Count; i++)
            {
                yield return (T)list[i];
            }
        }
        else
        {
            // .NET framework
            using (IEnumerator<T> e = source.GetEnumerator())
            {
                while (count > 0 && e.MoveNext()) count--;
                if (count <= 0)
                {
                    while (e.MoveNext()) yield return e.Current;
                }
            }
        }
    }

In fact, they did that for the Count method for example...

    // .NET Framework...
    public static int Count<TSource>(this IEnumerable<TSource> source) 
    {
        if (source == null) throw Error.ArgumentNull("source");

        ICollection<TSource> collectionoft = source as ICollection<TSource>; 
        if (collectionoft != null) return collectionoft.Count;

        ICollection collection = source as ICollection; 
        if (collection != null) return collection.Count; 

        int count = 0;
        using (IEnumerator<TSource> e = source.GetEnumerator())
        { 
            checked 
            {
                while (e.MoveNext()) count++;
            }
        } 
        return count;
    } 

So what's the reason?

Answer 1

In Jon Skeet's excellent tutorial re-implementing Linq, he discusses (briefly) that very question:

Although most of these operations can't be sensibly optimized, it would make sense to optimize Skip when the source implements IList. We can skip the skipping, so to speak, and go straight to the appropriate index. This wouldn't spot the case where the source was modified between iterations, which may be one reason it's not implemented in the framework as far as I'm aware.

That seems like a reasonable reason to hold off on that optimization, but I agree that for specific cases, it may be worthwhile to make that optimization if you can guarantee your source can't/won't be modified.