c# - tips - Array.Count() mucho más lento que List.Count()

linq performance

Question

Cuando se utiliza el método de extensión de IEnumerable<T> Count() , una matriz es al menos dos veces más lenta que una lista.

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

¿De dónde viene la diferencia?

Entiendo que ambos están llamando a la propiedad Count de ICollection :

Si el tipo de fuente implementa ICollection, esa implementación se utiliza para obtener el recuento de elementos. De lo contrario, este método determina el conteo.

Para la lista, devuelve List<T>.Count , y para array, Array.Length . Además, se supone que Array.Length es más rápido que List<T>.Count .

Punto de referencia:

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

Editar:

Knaģis respuestas de leppie y Knaģis son bastante sorprendentes, pero quiero agregar un comentario.
Como dijo Jon Skeet:

Existen efectivamente dos bloques equivalentes, solo se prueban diferentes tipos de interfaz de colección y se usa el que se encuentra primero (si corresponde). No sé si la implementación de .NET prueba primero para ICollection o ICollection <T>. Podría probarla implementando ambas interfaces pero devolviendo diferentes conteos de cada una, por supuesto, pero eso probablemente sea excesivo. En realidad, no importa si las colecciones se comportan bien, aparte de la leve diferencia de rendimiento: primero queremos probar la interfaz "más probable", que creo que es la genérica.

El genérico podría ser el más probable de suceder, pero si invierte los dos, es decir, llama a la conversión no genérica antes del genérico, Array.Count () se vuelve un poco más rápido que List.Count (). Por otro lado, la versión no genérica es más lenta para List.

Es bueno saber si alguien quiere llamar a Count() en un bucle de iteraciones 1e8.

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

Answer 1

Análisis de perfiles de 32 bits (todo en ms, solo bits interesantes, alineación JIT desactivada):

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() parece llamar a System.Runtime.CompilerServices.JitHelpers::UnsafeCast para el caso de matriz.

Para la lista, List<int>.Count simplemente devuelve el tamaño.

Inc time es costo incluyendo llamadas de niños. Ex time es costo del cuerpo del método solamente.

Cuando se inhabilita el Array.Count() , el Array.Count() es dos veces más lento.

Podría deberse al hecho mencionado la respuesta ahora eliminada. Al parecer, los atributos aplicados ( ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success) y SecuritySafeCritical ) impiden que el tiempo de ejecución incorpore la llamada, de ahí la gran diferencia (38 veces más lenta en mi caso en el modo de 32 bits).

Para perfilar esto usted mismo:

Obtenga https://github.com/leppie/IronScheme/raw/master/IronScheme/tools/IronScheme.Profiler.x86.dll Ejecute la aplicación (solo compilación x86) como:

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

Cuando la aplicación sale, se crea un archivo report.tab que luego se puede usar en Excel.

Answer 2

Esto se debe a que int[] requiere la conversión, mientras que List<int> no lo hace. Si tuviera que utilizar la propiedad Length, el resultado será bastante diferente: aprox. 10 veces más rápido que List<int>.Count() .

Answer 3

Estoy publicando esto, no como una respuesta, sino para proporcionar un entorno más comprobable.

Tomé una copia de la implementación real de Enumerable<T>.Count() y cambié el programa de prueba original para usarlo, de modo que la gente pueda realizar un solo paso en el depurador.

Si ejecuta una versión de lanzamiento del código a continuación, obtendrá tiempos similares al OP.

Tanto para la List<T> como para la int[] la primera is2 asignada a is2 no será nula, por lo que se is2.Count a is2.Count .

Por lo tanto, parece que la diferencia proviene de la implementación interna de .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;
        }
    }
}

Dada esta información, podemos simplificar la prueba para concentrarnos en las diferencias de tiempo entre List.Count y 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);
        }
    }
}

El código anterior proporciona los siguientes resultados para una ejecución de compilación de versión fuera del depurador:

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

En este punto, pensé para mí mismo "seguramente podemos optimizar Count() para reconocer T[] y devolver .Length directamente. Así que cambié la implementación de Count() siguiente manera:

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

Sorprendentemente, incluso después de hacer este cambio, los arreglos seguían siendo más lentos en mi sistema, ¡a pesar de que los arreglos no tenían que hacer el lanzamiento adicional!

Los resultados (release build) para mi fueron:

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

Estoy en una pérdida total para explicar este último resultado ...

Answer 4

La razón es que Enumerable.Count<T>() realiza una ICollection<T> a ICollection<T> para recuperar el recuento de la lista y la matriz.

Usando este código de muestra:

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

puede determinar que la conversión lleva mucho más tiempo para la matriz, de hecho, la mayor parte del tiempo que se tarda en contar es de esta conversión:

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

La clave podría ser esta declaración de la documentation (énfasis mío):

En el .NET Framework versión 2.0, la clase Array implementa las interfaces genéricas System.Collections.Generic.IList, System.Collections.Generic.ICollection y System.Collections.Generic.IEnumerable. Las implementaciones se proporcionan a los arreglos en tiempo de ejecución y, por lo tanto, no son visibles para las herramientas de compilación de la documentación. Como resultado, las interfaces genéricas no aparecen en la sintaxis de declaración para la clase Array, y no hay temas de referencia para los miembros de la interfaz a los que solo se puede acceder mediante la conversión de una matriz al tipo de interfaz genérica (implementaciones de interfaz explícita).