Подтвердить что ты не робот

Array.Count() намного медленнее, чем List.Count()

При использовании метода расширения IEnumerable<T> Count() массив по меньшей мере в два раза медленнее, чем список.

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

Откуда произошла разница?

Я понимаю, что оба вызова свойства Count ICollection:

Если тип источника реализует ICollection, эта реализация используется для получения количества элементов. В противном случае этот метод определяет счетчик.

Для списка он возвращает List<T>.Count и для массива Array.Length. Более того, Array.Length предполагается быстрее, чем 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 и ответы Knaģis довольно удивительны, но я хочу добавить замечание.
Как сказал Джон Скит:

Существует фактически два эквивалентных блока, просто тестирование для различные типы интерфейсов сбора данных и использование того, что находит сначала (если есть). Я не знаю, проверяются ли тесты .NET для ICollection или ICollection <T> сначала - я мог бы проверить это путем внедрения оба интерфейса, но, разумеется, но это, вероятно, излишнее. Это не имеет большого значения для хорошие коллекции, отличные от небольшой разницы в производительности - Сначала мы хотим протестировать "наиболее вероятный" интерфейс, который, я считаю, является общим.

Возможно, наиболее вероятно, что общий вариант может произойти, но если вы инвертируете два, то есть вызовите не общий набор перед родовым, Array.Count() станет немного быстрее, чем List.Count(). С другой стороны, для версии List нестандартная версия медленнее.

Полезно знать, хочет ли кто-нибудь позвонить Count() в цикл итераций 1e8!

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

ОТВЕТЫ

Ответ 1

Причина в том, что Enumerable.Count<T>() выполняет приведение к ICollection<T> для извлечения счетчика как из списка, так и из массива.

Используя этот пример кода:

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

вы можете определить, что литье занимает намного больше времени для массива, на самом деле большая часть времени, затраченного на подсчет, принадлежит этому приведению:

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

Ключом может быть это утверждение из документации (выделено мной):

В .NET Framework версии 2.0 класс Array реализует System.Collections.Generic.IList, System.Collections.Generic.ICollection и System.Collections.Generic.IEnumerable общие интерфейсы. The реализации реализуются массивами во время выполнения, и поэтому они не видны инструментам сборки документации. В результате общий интерфейсы не отображаются в синтаксисе объявления для массива класса, и нет никаких эталонных тем для членов интерфейса, которые доступны только путем заливки массива в общий тип интерфейса (явные реализации интерфейса).

Ответ 2

32-разрядный анализ профилирования (все в мс, только интересные биты, вставка JIT отключена):

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() кажется, вызывает System.Runtime.CompilerServices.JitHelpers::UnsafeCast для случая массива.

Для списка List<int>.Count просто возвращает размер.

Inc time - это стоимость, включая детские звонки. Ex time - только стоимость тела метода.

Когда вложение отключено, Array.Count() в два раза медленнее.

Это может быть связано с тем, что упоминался теперь удаленный ответ. Похоже, что применяемые атрибуты (ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success) и SecuritySafeCritical) препятствуют тому, чтобы среда выполнения включала вызов, следовательно, большая разница (в 38 раз медленнее в моем случае в 32-битном режиме).

Профилировать это самостоятельно:

Получить https://github.com/leppie/IronScheme/raw/master/IronScheme/tools/IronScheme.Profiler.x86.dll Запустите приложение (только для сборки x86):

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

Когда приложение выходит, создается файл report.tab, который затем можно использовать в Excel.

Ответ 3

Я отправляю это, а не как ответ, но чтобы обеспечить более проверяемую среду.

Я взял копию фактической реализации Enumerable<T>.Count() и изменил исходную тестовую программу, чтобы использовать ее, чтобы люди могли сделать одноэтапное ее в отладчике.

Если вы запустите версию версии ниже, вы получите аналогичные тайминги для OP.

Для обоих List<T> и int[] первый приказ, назначенный is2, будет не нулевым, поэтому будет вызываться is2.Count.

Таким образом, казалось бы, разница исходит от внутренней реализации .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;
        }
    }
}

Учитывая эту информацию, мы можем упростить тест, чтобы просто сосредоточиться на различиях синхронизации между List.Count и 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);
        }
    }
}

Приведенный выше код дает следующие результаты для запуска сборки релиза вне отладчика:

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

На этом этапе я подумал: "Конечно, мы можем оптимизировать Count() для распознавания T[] и вернуть .Length напрямую. Поэтому я изменил реализацию Count() следующим образом:

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

Примечательно, что даже после внесения этого изменения массивы были еще медленнее в моей системе, несмотря на то, что не-массивы вынуждены делать дополнительный прилив!

Результаты (выпуск) для меня были:

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

У меня полная потеря, чтобы объяснить этот последний результат...

Ответ 4

Это потому, что int[] требует кастинга, а List<int> - нет. Если вы будете использовать свойство Length, результат будет совсем другим - прим. 10 раз быстрее, чем List<int>.Count().