In which cases are IEnumerable<T>.Count optimized?

c#, count, ienumerable, optimization

Solution

It doesn't really matter that the result of `Select` is lazily evaluated. The `Count` is always equivalent to the count of the original collection so it could have certainly been retrieved directly by returning a specific object from `Select` that could be used to short-circuit evaluation of the `Count` method.

The reason it's not possible to optimize out evaluation of the `Count()` method on the return value of a `Select` call from something with determined count (like a `List<T>`) is that it could change the meaning of the program.

The `selector` function passed to `Select` method is allowed to have side effects and its side effects are required to happen deterministically, in a predetermined order.

Assume:

new[]{1,2,3}.Select(i => { Console.WriteLine(i); return 0; }).Count();

The documentation requires this code to print

1 2 3

Even though the count is really known from the start and could be optimized, optimization would change the behavior of the program. That's why you can't avoid enumeration of the collection anyway. That's exactly one of the reasons why compiler optimizations are much easier in pure functional languages.

UPDATE: Apparently, it's not clear that it's perfectly possible to implement `Select` and `Count` so that `Select`s on `ICollection<T>` will still be lazily evaluated but the `Count()` will be evaluated in O(1) without enumerating the collection. I'm going to do that without changing the interface of any methods. A similar thing is already done for `ICollection<T>`:

private interface IDirectlyCountable {
    int Count {get;}
}
private class SelectICollectionIterator<TSource,TResult> : IEnumerable<T>, IDirectlyCountable {
     ICollection<TSource> sequence;
     Func<TSource,TResult> selector;
     public SelectICollectionIterator(ICollection<TSource> source, Func<TSource,TResult> selector) {
         this.sequence = source;
         this.selector = selector;
     }
     public int Count { get { return sequence.Count; } }
     // ... GetEnumerator ... 
}
public static IEnumerable<TResult> Select<TSource,TResult>(this IEnumerable<TSource> source, Func<TSource,TResult> selector) {
    // ... error handling omitted for brevity ...
    if (source is ICollection<TSource>)
       return new SelectICollectionIterator<TSource,TResult>((ICollection<TSource>)source, selector);
    // ... rest of the method ...
}
public static int Count<T>(this IEnumerable<T> source) {
    // ...
    ICollection<T> collection = source as ICollection<T>;
    if (collection != null) return collection.Count;
    IDirectlyCountable countableSequence = source as IDirectlyCountable;
    if (countableSequence != null) return countableSequence.Count;
    // ... enumerate and count the sequence ...
}

This will still evaluate the `Count` lazily. If you change the underlying collection, the count will get changed and the sequence is not cached. The only difference will be not doing the side effects in the `selector` delegate.

Problem

Using reflector I have noticed that `System.Linq.Enumerable.Count` method has a condition in it to optimize it for the case when the `IEnumerable<T>` passed is in fact an `ICollection<T>`. If the cast succeeds the Count method does not need to iterate over every element, but can call the Count method of ICollection. Based on this I was starting to think that `IEnumerable<T>` can be used like a readonly view of a collection, without having the performance loss that I originally expected based on the API of `IEnumerable<T>` I was interested whether the optimization of the `Count` still holds when the `IEnumerable<T>` is a result of a `Select` statement over an `ICollection`, but based on reflected code this case is not optimized, and requires an iteration through all elements. Do you draw the same conclusions from reflector? What could be the reason behind the lack of this optimization? I seems like there is a lot of time wasted in this common operation. Does the spec require that the each element is evaluated even if the Count can be determined without doing that?

Original source