Is the Linq Count() faster or slower than List.Count or Array.Length?

Question

Is the Linq Count() method any faster or slower than List<>.Count or Array.Length?

Answer 1

In general Slower. LINQ's Count in general is an O(N) operation while List.Count and Array.Length are both guaranteed to be O(1).

However it some cases LINQ will special case the IEnumerable<T> parameter by casting to certain interface types such as IList<T> or ICollection<T>. It will then use that Count method to do an actual Count() operation. So it will go back down to O(1). But you still pay the minor overhead of the cast and interface call.

Answer 2

I believe that if you call Linq.Count() on either an ICollection or IList (like an ArrayList or List) then it will just return the Count property's value. So the performance will be about the same on plain collections.

Answer 3

The Enumerable.Count() method checks for ICollection<T>, using .Count - so in the case of arrays and lists, it is not much more inefficient (just an extra level of indirection).

Answer 4

I would say it depends on the List. If it is an IQueryable that is a table in a db somewhere then Count() will be much faster because it doesn't have to load all of the objects. But if the list is in-memory i would guess that the Count property would be faster if not about the same.

Answer 5

Marc has the right answer but the devil is in the detail.

On my machine:

• For arrays .Length is about 100 times faster than .Count()
• For Lists .Count is about 10 times faster than .Count() - Note: I would expect similar performance from all Collections that implement IList<T>

Arrays start off slower since .Length involves only a single operation, .Count on arrays involves a layer of indirection. So .Count on arrays starts off 10x slower (on my machine), which could be one of those reasons the interface is implemented explicitly. Imagine if you had an object with two public properties, .Count and .Length. Both do the exact same thing but .Count is 10X slower.

Of course non of this really makes much of a difference since you would have to be counting your arrays and lists millions of times a second to feel a performance hit.

Code:

    static void TimeAction(string description, int times, Action func) {
        var watch = new Stopwatch();
        watch.Start();
        for (int i = 0; i < times; i++) {
            func();
        }
        watch.Stop();
        Console.Write(description);
        Console.WriteLine(" Time Elapsed {0} ms", watch.ElapsedMilliseconds);
    } 

    static void Main(string[] args) {
        var array = Enumerable.Range(0, 10000000).ToArray();
        var list = Enumerable.Range(0, 10000000).ToArray().ToList();

        // jit
        TimeAction("Ignore and jit", 1 ,() =>
        {
            var junk = array.Length;
            var junk2 = list.Count;
            array.Count();
            list.Count();
        });


        TimeAction("Array Length", 1000000, () => {
            var tmp1 = array.Length;
        });

        TimeAction("Array Count()", 1000000, () =>
        {
            var tmp2 = array.Count();
        });

        TimeAction("Array Length through cast", 1000000, () =>
        {
            var tmp3 = (array as ICollection<int>).Count;
        });


        TimeAction("List Count", 1000000, () =>
        {
            var tmp1 = list.Count;
        });

        TimeAction("List Count()", 1000000, () =>
        {
            var tmp2 = list.Count();
        });

        Console.ReadKey();
    }

Results:

Array Length Time Elapsed 3 ms
Array Count() Time Elapsed 264 ms
Array Length through cast Time Elapsed 16 ms
List Count Time Elapsed 3 ms
List Count() Time Elapsed 18 ms

Answer 6

Some additional info - LINQ Count - the difference between using it and not can be huge - and this doesn't have to be over 'large' collections either. I have a collection formed from linq to objects with about 6500 items (big.. but not huge by any means) . Count() in my case takes several seconds. Converting to a list (or array, whatver) the count is then virtually immediate. Having this count in an inner loop means the impact could be huge. Count enumerates through everything. An array and a list are both 'self aware' of their lengths and do not need to enumerate them. Any debug statements (log4net for ex) that reference this count() will also then slow everything down considerably more. Do yourself a favor and if you need to reference this often save the count size and only call it once on a LINQ collection unless you convert it to a list and then can reference away without a performance hit.

Here is a quick test of what I was talking about above. Note every time we call Count() our collection size changes.. hence evaluation happens, which is more than an expected 'count' operation. Just something to be aware of : )

    
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;

    namespace LinqTest
    {
        class TestClass
        {
            public TestClass()
            {
                CreateDate = DateTime.Now;
            }
            public DateTime CreateDate;
        }

        class Program
        {

            static void Main(string[] args)
            {
                //Populate the test class
                List list = new List(1000);
                for (int i=0; i<1000; i++)
                {
                    System.Threading.Thread.Sleep(20);
                    list.Add(new TestClass());
                    if(i%100==0)
                    { 
                        Console.WriteLine(i.ToString() +  " items added");
                    }
                }

                //now query for items 
                var newList = list.Where(o=> o.CreateDate.AddSeconds(5)> DateTime.Now);
                while (newList.Count() > 0)
                {
                    //Note - are actual count keeps decreasing.. showing our 'execute' is running every time we call count.
                    Console.WriteLine(newList.Count());
                    System.Threading.Thread.Sleep(500);
                }
            }
        }
    }