Array.Count() much slower than List.Count()

Question

When using the extension method of IEnumerable<T> Count(), an array is at least two times slower than a list.

Function                      Count()
List<int>                     2,299
int[]                         6,903

From where did the difference comes?

I understand that both are calling the Count property of ICollection:

If the type of source implements ICollection, that implementation is used to obtain the count of elements. Otherwise, this method determines the count.

For the list it returns List<T>.Count, and for array, Array.Length. Moreover, Array.Length is supposed to be faster than List<T>.Count.

Benchmark:

class Program
{
    public const long Iterations = (long)1e8;

    static void Main()
    {
        var list = new List<int>(){1};
        var array = new int[1];
        array[0] = 1;

        var results = new Dictionary<string, TimeSpan>();
        results.Add("List<int>", Benchmark(list, Iterations));
        results.Add("int[]", Benchmark(array, Iterations));

        Console.WriteLine("Function".PadRight(30) + "Count()");
        foreach (var result in results)
        {
            Console.WriteLine("{0}{1}", result.Key.PadRight(30), Math.Round(result.Value.TotalSeconds, 3));
        }
        Console.ReadLine();
    }

    public static TimeSpan Benchmark(IEnumerable<int> source, long iterations)
    {
        var countWatch = new Stopwatch();
        countWatch.Start();
        for (long i = 0; i < iterations; i++) source.Count();
        countWatch.Stop();

        return countWatch.Elapsed;
    }
}

Edit:

leppie and Knaģis answers are pretty amazing, but I want to add a remark.
As Jon Skeet said:

There are effectively two equivalent blocks, just testing for different collection interface types, and using whichever one it finds first (if any). I don't know whether the .NET implementation tests for ICollection or ICollection< T > first - I could test it by implementing both interfaces but returning different counts from each, of course, but that's probably overkill. It doesn't really matter for well-behaved collections other than the slight performance difference - we want to test the "most likely" interface first, which I believe is the generic one.

The generic one could be the most likely to happens, but if you invert the two, ie call the non generic cast before the generic one, Array.Count() becomes a little faster than List.Count(). On the other hand, non generic version is slower for List.

Good to know if anyone want to call Count() in an 1e8 iterations loop!

Function       ICollection<T> Cast     ICollection Cast
List                1,268                   1,738         
Array               5,925                   1,683

+1 Interesting. Also, with your numbers it seems you are running 64-bit. In 32-bit, the difference is a lot more! — leppie, Apr 25 '13 at 07:44
Maybe this helps http://stackoverflow.com/questions/981254/is-the-linq-count-faster-or-slower-than-list-count-or-array-length — V4Vendetta, Apr 25 '13 at 07:49
It's actually *four times* slower for my tests! Most interesting. — Matthew Watson, Apr 25 '13 at 07:50

Knaģis · Accepted Answer · 2013-04-25T08:36:12.380

9

The reason is that Enumerable.Count<T>() performs a cast to ICollection<T> to retrieve the count both from the list and the array.

Using this sample code:

public static int Count<TSource>(IEnumerable<TSource> source)
{
    ICollection<TSource> collection = source as ICollection<TSource>;
    if (collection != null)
    {
        return 1; // collection.Count;
    }
}

you can determine that the cast takes much longer for the array, in fact most of the time taken for counting is from this cast:

Function                      Count()
List<int>                     1,575
int[]                         5,069

The key might be this statement from the documentation (emphasis mine):

In the .NET Framework version 2.0, the Array class implements the System.Collections.Generic.IList, System.Collections.Generic.ICollection, and System.Collections.Generic.IEnumerable generic interfaces. The implementations are provided to arrays at run time, and therefore are not visible to the documentation build tools. As a result, the generic interfaces do not appear in the declaration syntax for the Array class, and there are no reference topics for interface members that are accessible only by casting an array to the generic interface type (explicit interface implementations).

edited Apr 25 '13 at 08:36

answered Apr 25 '13 at 08:05

Knaģis

20,827
7
66
80

3

Sorry, but this isn't true. `int[]` definitely *DOES* implement `ICollection` I have single-stepped through the implementation of `Enumerable.Count()` and verified that it isn't doing two casts. – Matthew Watson Apr 25 '13 at 08:14
1

yes, `int[]` does implement `ICollection` but it is the cast that is slow in itself... will modify the answer... – Knaģis Apr 25 '13 at 08:22
@MatthewWatson: I think we are all coming to the conclusion that casting to `ICollection` is handled special in the case of an array. – leppie Apr 25 '13 at 08:31
2

We can conclude that ICollection is retrieve at run time by doing crazy stuff taking more time than just a simple interface-instance cast. – Cyril Gandon Apr 25 '13 at 08:59
@leppie My comment was addressed to the original form of this answer; it doesn't really apply to the latest revisions. – Matthew Watson Apr 25 '13 at 09:06
@Scorpi0 AFAIK the cast itself is always an identity transform. The problem is the test that checks if the cast is valid. This test seems to be more complicated for arrays. – CodesInChaos Apr 25 '13 at 10:29

score 5 · Answer 2 · answered Apr 25 '13 at 08:20

32-bit profiling analysis (all in ms, only interesting bits, JIT inlining disabled):

Name    Count   'Inc Time'  'Ex Time'   'Avg Inc Time'  'Avg Ex Time'
System.Linq.Enumerable::Count(<UNKNOWN>):int32 <System.Int32>   
        20000000    13338.38    7830.49 0.0007  0.0004
System.SZArrayHelper::get_Count():int32 <System.Int32>  
        10000000    4063.9      2651.44 0.0004  0.0003
System.Collections.Generic.List<System.Int32>::get_Count():int32    
        10000000    1443.99     1443.99 0.0001  0.0001
System.Runtime.CompilerServices.JitHelpers::UnsafeCast(Object):System.__Canon <System.__Canon>  
        10000004    1412.46     1412.46 0.0001  0.0001

System.SZArrayHelper::get_Count() seems to call System.Runtime.CompilerServices.JitHelpers::UnsafeCast for the array case.

For the list, List<int>.Count simply returns the size.

Inc time is cost including child calls. Ex time is cost of method body only.

When inlining is disabled, the Array.Count() is twice as slow.

It could be due to the fact mentioned the now deleted answer. It would appear the attributes applied (ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success) and SecuritySafeCritical) prevents the runtime from inlining the call, hence the big difference (38 times slower in my case in 32-bit mode).

To profile this yourself:

Get https://github.com/leppie/IronScheme/raw/master/IronScheme/tools/IronScheme.Profiler.x86.dll Run the app (x86 build only) as:

regsvr32 IronScheme.Profiler.x86.dll
set COR_PROFILER={9E2B38F2-7355-4C61-A54F-434B7AC266C0}
set COR_ENABLE_PROFILING=1
ConsoleApp1.exe

When app exits, a report.tab file is created which can then be used in Excel.

Made a test, `var genericCollection = source as ICollection;` is five times slower with array than list. Funny thing is that a cast to ICollection is much more faster! — Cyril Gandon, Apr 25 '13 at 08:23
@Scorpi0: Interesting :) That probably causes the `JitHelpers::UnsafeCast` call. — leppie, Apr 25 '13 at 08:27
the attributes didn't seem to be the reason because when calling `List.Count` and `Array.Length` directly (without the Enumerable in the middle) their performance was exactly the same... — Knaģis, Apr 25 '13 at 08:27
@Knaģis: Without the profiler, it makes a huge difference. With profiler (JIT inlining disabled), the difference is only 2 times. — leppie, Apr 25 '13 at 08:28
@leppie Any clue on why this cast take this path, or do I have to post another question? — Cyril Gandon, Apr 25 '13 at 08:46
@Scorpi0 I'd guess it's related to array being a special type. It's generic-like but not really generic, it supports co-variance in an unusual way. So it's not too surprising that casting arrays to `ICollection` needs some special casing. — CodesInChaos, Apr 25 '13 at 08:48
@Scorpi0: The info at the bottom of Knaģis's answer might be the reason. — leppie, Apr 25 '13 at 08:50

score 3 · Answer 3 · edited Apr 25 '13 at 10:21

I'm posting this, not as an answer, but to provide a more testable environment.

I have taken a copy of the actual implementation of Enumerable<T>.Count() and changed the original test program to use it, so people can single-step it in the debugger.

If you run a release version of the code below, you will get similar timings to the OP.

For both List<T> and int[] the first cast assigned to is2 will be non-null so is2.Count will be called.

So it would appear the difference is coming from the internal implementation of .Count.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;

namespace ConsoleApplication1
{
    class Program
    {
        public const long Iterations = (long)1e8;

        static void Main()
        {
            var list = new List<int>() { 1 };
            var array = new int[1];
            array[0] = 1;

            var results = new Dictionary<string, TimeSpan>();
            results.Add("int[]", Benchmark(array, Iterations));
            results.Add("List<int>", Benchmark(list, Iterations));

            Console.WriteLine("Function".PadRight(30) + "Count()");
            foreach (var result in results)
            {
                Console.WriteLine("{0}{1}", result.Key.PadRight(30), Math.Round(result.Value.TotalSeconds, 3));
            }
            Console.ReadLine();
        }

        public static TimeSpan Benchmark(IEnumerable<int> source, long iterations)
        {
            var countWatch = new Stopwatch();
            countWatch.Start();
            for (long i = 0; i < iterations; i++) Count(source);
            countWatch.Stop();

            return countWatch.Elapsed;
        }

        public static int Count<TSource>(IEnumerable<TSource> source)
        {
            ICollection<TSource> is2 = source as ICollection<TSource>;

            if (is2 != null)
                return is2.Count;  // This is executed for int[] AND List<int>.

            ICollection is3 = source as ICollection;

            if (is3 != null)
                return is3.Count;

            int num = 0;

            using (IEnumerator<TSource> enumerator = source.GetEnumerator())
            {
                while (enumerator.MoveNext())
                    num++;
            }

            return num;
        }
    }
}

Given this information, we can simplify the test to just concentrate on the timing differences between List.Count and Array.Count:

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main()
        {
            int dummy = 0;
            int count = 1000000000;

            var array = new int[1] as ICollection<int>;
            var list = new List<int> {0};

            var sw = Stopwatch.StartNew();

            for (int i = 0; i < count; ++i)
                dummy += array.Count;

            Console.WriteLine("Array elapsed = " + sw.Elapsed);

            dummy = 0;
            sw.Restart();

            for (int i = 0; i < count; ++i)
                dummy += list.Count;

            Console.WriteLine("List elapsed = " + sw.Elapsed);

            Console.ReadKey(true);
        }
    }
}

The above code gives the following results for a release build run outside the debugger:

Array elapsed = 00:00:02.9586515
List elapsed = 00:00:00.6098578

At this point, I thought to myself "surely we can optimise the Count() to recognise T[] and return .Length directly. So I changed the implementation of Count() as follows:

public static int Count<TSource>(IEnumerable<TSource> source)
{
    var array = source as TSource[];

    if (array != null)        // Optimised for arrays.
        return array.Length;  // This is executed for int[] 

    ICollection<TSource> is2 = source as ICollection<TSource>;

    if (is2 != null)
        return is2.Count;  // This is executed for List<int>.

    ICollection is3 = source as ICollection;

    if (is3 != null)
        return is3.Count;

    int num = 0;

    using (IEnumerator<TSource> enumerator = source.GetEnumerator())
    {
        while (enumerator.MoveNext())
            num++;
    }

    return num;
}

Remarkably, even after making this change, the arrays were still slower on my system, despite the non-arrays having to make the extra cast!

Results (release build) for me were:

Function                      Count()
List<int>                     1.753
int[]                         2.304

I'm at a total loss to explain this last result...

What is unexpected is that `arr as int[]` is slower than `arr as ICollection`! — Cyril Gandon, Apr 25 '13 at 08:55
@Scorpi0 Indeed, and I wondered if I must have made some kind of mistake, but I can't see if it there is one... — Matthew Watson, Apr 25 '13 at 09:04
Actually the special casing is part of the slowdown for arrays. Normally a type check is extremely cheap. But unfortunately, the CLR supports array covariance, so first it checks that its an array (cheap), and then it does a typecheck to see if the array cast would be safe (expensive). Even though it should be a noop it isn't. — Michael B, May 23 '14 at 04:25

score 1 · Answer 4 · edited Apr 25 '13 at 08:49

1

That is because int[] requires casting, while List<int> does not. If you were to use Length property then result will be quite different - approx. 10x faster than List<int>.Count().

edited Apr 25 '13 at 08:49

CodesInChaos

106,488
23
218
262

answered Apr 25 '13 at 08:02

Array.Count() much slower than List.Count()

4 Answers4

Linked