Does calling Count on IEnumerable iterate the whole collection?

Question

Consider the following code:

static IEnumerable<int> GetItems()
{
    return Enumerable.Range(1, 10000000).ToArray();  // or: .ToList();
}

static void Main()
{
    int count = GetItems().Count();
}

Will it iterate over all the 10 billion integers and count them one-by-one, or will it use the array's Length / list's Count properties?

No, `Length` (in case of array) or `Count` (in case of `IList`) will be used — Dmitry Bychenko, Sep 30 '15 at 10:26
See http://stackoverflow.com/questions/2521592/difference-between-ienumerable-count-and-length — Amittai Shapira, Sep 30 '15 at 10:28
You can find the implementation yourself :) http://referencesource.microsoft.com/#System.Core/System/Linq/Enumerable.cs,41ef9e39e54d0d0b — Sriram Sakthivel, Sep 30 '15 at 10:28
I will also recommand to use LongCount if you expect the result to be bigger than Int32 — Guillaume Beauvois, Sep 30 '15 at 10:30
Hope you're alright with the duplicate closure. It's not a 100% duplicate but the question is answered there (and more). — usr, Sep 30 '15 at 10:30
It is quite hard to create an array that has more than `int.MaxValue` items @GuillaumeBeauvois — Patrick Hofman, Sep 30 '15 at 10:30

score 4 · Accepted Answer · edited Sep 30 '15 at 10:52

4

If the IEnumerable is an ICollection, it will return the Count property.

Here's the source code:

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;
}

An array implements ICollection<T>, so it doesn't need to be enumerated.

edited Sep 30 '15 at 10:52

Patrick Hofman

153,850
22
249
325

answered Sep 30 '15 at 10:29

Jakub Lortz

14,616
3
25
39

So, does the code given return an `ICollection` or not? – Patrick Hofman Sep 30 '15 at 10:33
@PatrickHofman *Which* code? – Peter - Reinstate Monica Sep 30 '15 at 10:33
`return Enumerable.Range(1, 10000000).ToArray(); // or: .ToList();`, as in the question. – Patrick Hofman Sep 30 '15 at 10:34
As discussed here (http://stackoverflow.com/a/4482567/3150802), arrays implement `IList` which in turn is an `ICollection`. These implementations are added at run time giving arrays a special status, but they are there, so yes, calling `.Count()` on a an array should be a O(1) operation, no matter what type the reference has. – Peter - Reinstate Monica Sep 30 '15 at 10:40
That would make the answer actually answer the question @Peter. – Patrick Hofman Sep 30 '15 at 10:42
@PatrickHofman Right, I edited the answer. – Jakub Lortz Sep 30 '15 at 10:51
I see, I updated it a little to be precise. – Patrick Hofman Sep 30 '15 at 10:53

score 0 · Answer 2 · edited May 23 '17 at 12:16

0

The code will first put all the integers into array (due to your .ToArray() call), and then return the length of the array (since all arrays implement ICollection), which the actual code calls. It will not count all items in the array one by one.

edited May 23 '17 at 12:16

Community

1
1

answered Sep 30 '15 at 10:28

martijn

1,417
1
16
26

I cannot detect an array in the source code presented by @Jakub, and I don't see a reason why one should create one. – Peter - Reinstate Monica Sep 30 '15 at 10:34
2

@PeterSchneider There is in the code from OP, just read: `return Enumerable.Range(1, 10000000).ToArray(); ` The code clearly calls `ToArray`. – Patrick Hofman Sep 30 '15 at 10:35
Oh. I misunderstood. Well. I guess the answer to the OP is "you just did something insane but the compiler will not add insanity on top". I assume that C# compilers are allowed to apply the as-if rule, so the compiler is allowed to do nothing at all (since the program has no observable effect). If you print the count, the compiler is free to just print 10000000, no arrays or anything. – Peter - Reinstate Monica Sep 30 '15 at 10:43
No, since it doesn't know there aren't side effects. It will create the array, no matter how useless it is. – Patrick Hofman Sep 30 '15 at 10:49
@PatrickHofman You can see there are no side effects; I can see it. The compiler can see it. It's all there, in plain view. The complete source code is even in a single translation unit. Or am I missing something? – Peter - Reinstate Monica Sep 30 '15 at 10:55
Yes, compilers are dumb @Peter. – Patrick Hofman Sep 30 '15 at 10:57

Does calling Count on IEnumerable iterate the whole collection?

2 Answers2