3 February

.NET Core vs Framework. Производительность коллекций

.NETC#

image


Релиз .NET Core 3.1 — хороший повод мигрировать свой проект с Framework на Core. Во-первых, это отполированная версия с долгосрочной поддержкой (LTS), т.е. её можно смело использовать в продакшене. Во-вторых, в третьей версии добавили поддержку WPF и WinForms, так что теперь появилась возможность мигрировать и десктопные приложения.


Мне стало интересно, какой прирост производительности можно ожидать от Core в самых базовых классах, которые максимально часто используются в коде. Например, коллекции List, Array и Dictionary.


Если вам тоже интересно, как и почему изменилась производительность основных коллекций в Core 3 — прошу под кат!


Бенчмарки


Для сравнительных тестов я взял три актуальных рантайма: .NET Framework 4.8, .NET Core 3.1 и .NET Core 2.1. Все замеры производились на следующей конфигурации:


BenchmarkDotNet=v0.12.0, OS=Windows 10.0.18363
Intel Core i7-7700K CPU 4.20GHz (Kaby Lake), 1 CPU, 8 logical and 4 physical cores
.NET Core SDK=3.1.101
[Host] : .NET Core 3.1.1 (CoreCLR 4.700.19.60701, CoreFX 4.700.19.60801), X64 RyuJIT
Job-1  : .NET Framework 4.8 (4.8.4075.0), X64 RyuJIT
Job-2  : .NET Core 2.1.15 (CoreCLR 4.6.28325.01, CoreFX 4.6.28327.02), X64 RyuJIT
Job-3  : .NET Core 3.1.1 (CoreCLR 4.700.19.60701, CoreFX 4.700.19.60801), X64 RyuJIT

Также я прогонял все тесты на двух дополнительных машинах (на Haswell и Sky Lake), чтобы убедиться, что результаты тестов стабильны и воспроизводятся на другом железе.


Класс ValuesGenerator (да и основу для самих бенчмарков) я позаимствовал из репозитория перфоманс-тестов. Эти тесты используются мейнтейнерами .NET Core для тестирования предлагаемых оптимизаций.


List


Цикл for


Код List_IterateFor
[GenericTypeArguments(typeof(int))]
[GenericTypeArguments(typeof(string))]
public class ListIterationFor<T>
{
    [Params(100, 1_000, 10_000)]
    public int Size;

    private List<T> _list;

    [GlobalSetup]
    public void Setup() => _list = new List<T>(ValuesGenerator.ArrayOfUniqueValues<T>(Size));

    [Benchmark]
    public T List_IterateFor()
    {
        T result = default;
        List<T> collection = _list;

        for (int i = 0; i < collection.Count; i++)
            result = collection[i];

        return result;
    }
}

Method Runtime Size Mean Error StdDev Ratio
IterateFor_Int .NET 4.8 1000 565.09 ns 0.191 ns 0.127 ns 1.00
IterateFor_Int .NET Core 2.1 1000 451.14 ns 0.236 ns 0.156 ns 0.80
IterateFor_Int .NET Core 3.1 1000 451.08 ns 0.143 ns 0.085 ns 0.80
IterateFor_String .NET 4.8 1000 574.80 ns 6.795 ns 4.494 ns 1.00
IterateFor_String .NET Core 2.1 1000 460.86 ns 3.771 ns 2.494 ns 0.80
IterateFor_String .NET Core 3.1 1000 460.35 ns 0.681 ns 0.405 ns 0.80

В Core JIT генерирует более эффективный код, чтение элементов из List в цикле for стало быстрее на ~20%.


Цикл foreach


Код List_IterateForEach
[GenericTypeArguments(typeof(int))]
[GenericTypeArguments(typeof(string))]
public class ListIterationForEach<T>
{
    [Params(100, 1_000, 10_000)]
    public int Size;

    private List<T> _list;

    [GlobalSetup]
    public void Setup() => _list = new List<T>(ValuesGenerator.ArrayOfUniqueValues<T>(Size));

    [Benchmark]
    public T List_IterateForEach()
    {
        T result = default;
        List<T> collection = _list;

        foreach (var item in collection)
            result = item;

        return result;
    }
}

Method Runtime Size Mean Error StdDev Ratio
IterateForEach_Int .NET 4.8 1000 1,574.5 ns 2.73 ns 1.81 ns 1.00
IterateForEach_Int .NET Core 2.1 1000 1,575.8 ns 3.82 ns 2.27 ns 1.00
IterateForEach_Int .NET Core 3.1 1000 1,568.1 ns 0.61 ns 0.40 ns 1.00
IterateForEach_String .NET 4.8 1000 8,046.3 ns 36.51 ns 24.15 ns 1.00
IterateForEach_String .NET Core 2.1 1000 6,465.0 ns 15.26 ns 10.09 ns 0.80
IterateForEach_String .NET Core 3.1 1000 5,886.3 ns 14.65 ns 9.69 ns 0.73

Итерирование List с ссылочными типами через foreach стало быстрее на 27%, но для значимых типов ничего не поменялось. Здесь можно оценить, насколько foreach медленнее, чем for. Разница в их эффективности на Core составляет 3.5x (value types) и 12x (reference types), примерно также как и в полном фреймворке.


Add


Чтобы протестировать метод без ресайза внутреннего массива в тесте используется конструктор List с заданной ёмкостью (capacity).


Код List_Add
[GenericTypeArguments(typeof(int))]
[GenericTypeArguments(typeof(string))]
public class ListAdd<T>
{
    private T[] _uniqueValues;

    [Params(100, 1_000, 10_000)]
    public int Size;

    [GlobalSetup]
    public void Setup() => _uniqueValues = ValuesGenerator.ArrayOfUniqueValues<T>(Size);

    [Benchmark]
    public List<T> List_Add()
    {
        List<T> collection = new List<T>(Size);
        T[] uniqueValues = _uniqueValues;

        for (int i = 0; i < uniqueValues.Length; i++)
            collection.Add(uniqueValues[i]);

        return collection;
    }
}

Method Runtime Size Mean Error StdDev Ratio
Add_Int .NET 4.8 1000 2,006.5 ns 11.65 ns 6.93 ns 1.00
Add_Int .NET Core 2.1 1000 1,249.0 ns 1.00 ns 0.60 ns 0.62
Add_Int .NET Core 3.1 1000 1,260.9 ns 5.88 ns 3.89 ns 0.63
Add_String .NET 4.8 1000 3,250.8 ns 53.13 ns 35.14 ns 1.00
Add_String .NET Core 2.1 1000 2,816.8 ns 37.26 ns 22.18 ns 0.87
Add_String .NET Core 3.1 1000 2,538.2 ns 30.55 ns 20.21 ns 0.78

На Core 3 добавление работает быстрее на 22% (reference types) и 37% (value types). Что изменилось в коде метода? Добавление без ресайза, т.е. самый частый вариант выделен в отдельный метод с атрибутом [AggressiveInlining], т.е. он теперь инлайнится. Из мелких оптимизаций: убраны две лишние проверки выхода за границы и значение поля size теперь кешируется в локальную переменную.


Contains


Давайте возьмём негативный сценарий для метода Contains: будем искать элементы, которых нет в коллекции.


Код List_Contains
[GenericTypeArguments(typeof(int))]
[GenericTypeArguments(typeof(string))]
public class ListContains<T> where T : IEquatable<T>
{
    [Params(100, 1_000, 10_000)]
    public int Size;

    private List<T> _list;
    private T[] _lookupValues;

    [GlobalSetup]
    public void Setup()
    {
        var uniqueValues = ValuesGenerator.ArrayOfUniqueValues<T>(Size * 2);
        _list = uniqueValues.Take(Size).ToList();
        _lookupValues = uniqueValues.Skip(Size).ToArray();
    }

    [Benchmark]
    public int List_Contains()
    {
        int count = 0;
        List<T> collection = _list;
        T[] array = _lookupValues;

        for (int i = 0; i < array.Length; i++)
        {
            if (collection.Contains(array[i]))
                count++;
        }

        return count;
    }
}

Method Runtime Size Mean Error StdDev Ratio
Contains_Int .NET 4.8 1000 1,128.975 us 5.4951 us 3.6347 us 1.00
Contains_Int .NET Core 2.1 1000 456.040 us 0.1437 us 0.0950 us 0.40
Contains_Int .NET Core 3.1 1000 188.002 us 0.1619 us 0.0964 us 0.17
Contains_String .NET 4.8 1000 4,027.20 us 9.479 us 5.641 us 1.00
Contains_String .NET Core 2.1 1000 3,332.93 us 2.156 us 1.128 us 0.83
Contains_String .NET Core 3.1 1000 2,723.48 us 2.460 us 1.464 us 0.68

На Core 3 поиск Int в List стал примерно в 6 раз быстрее, а поиск строк — в 1.4 раза. В Core JIT научился в некоторых ситуациях девирутализировать виртуальные методы, т.е. они вызываются напрямую. Более того, такие методы могут быть заинлайнены. В данном случае девиртуализируется метод EqualityComparer.Default.Equals, который используется для сравнения элементов. В случае с Int всё сводится к вызову Int32.Equals, который к тому же инлайнится. В итоге получившийся код по эффективности близок к прямому сравнению двух Int.


Кстати, раньше я всегда думал, что метод Contains внутри вызывает IndexOf, но оказалось, что это верно только для Core. В полном фреймворке это разные методы, и работают они с разной скоростью.


List Methods Summary


Сводная таблица относительной производительности (ratio) основных методов List при N = 1000.


List Method Type .NET 4.8 Core 2.1 Core 3.1 Details
Ctor Int 1.00 0.82 0.47 Report
Ctor String 1.00 0.90 0.92 Report
IterateFor Int 1.00 0.80 0.80 Report
IterateFor String 1.00 0.80 0.80 Report
IterateForEach Int 1.00 1.00 1.00 Report
IterateForEach String 1.00 0.80 0.73 Report
Add Int 1.00 0.62 0.63 Report
Add String 1.00 0.87 0.78 Report
Contains Int 1.00 0.40 0.17 Report
Contains String 1.00 0.83 0.68 Report
IndexOf Int 1.00 0.99 0.43 Report
IndexOf String 1.00 0.95 0.95 Report

Array Methods Summary


Подробно останавливаться на методах массива я не буду, поскольку List — это обертка над массивом.
Так что здесь я приведу таблицу относительной производительности Array при N = 1000.


Array Method Type .NET 4.8 Core 2.1 Core 3.1 Details
Ctor Int 1.00 0.73 0.88 Report
Ctor String 1.00 0.75 0.84 Report
IterateFor Int 1.00 0.86 1.00 Report
IterateFor String 1.00 1.00 1.00 Report
IterateForEach Int 1.00 0.84 1.00 Report
IterateForEach String 1.00 1.00 1.00 Report

Здесь можно отметить, что как и прежде, цикл foreach для массива преобразуется в обычный for. Т.е. с точки зрения производительности для итерации массива нет разницы какой из циклов использовать.


Dictionary


Randomized Hash


В .NET Core для расчета хешей строк теперь используется рандомизированный алгоритм (Marvin). Т.е. при каждом запуске приложения хеш одной и той же строки будет разным. Это защита от хеш-атак, в частности "hash flooding" (подробнее). Естественно, этот алгоритм медленнее, чем нерандомизированный. Чтобы производительность Dictionary со строковым ключом не просела, внутри него рандомизированный хеш включается только при достижении определённого количества коллизий (сейчас HashCollisionThreshold = 100).


Add


Код Dictionary_Add
[GenericTypeArguments(typeof(int))]
[GenericTypeArguments(typeof(string))]
public class DictionaryAdd<T>
{
    private T[] _uniqueValues;

    [Params(100, 1_000, 10_000)]
    public int Size;

    [GlobalSetup]
    public void Setup() => _uniqueValues = ValuesGenerator.ArrayOfUniqueValues<T>(Size);

    [Benchmark]
    public Dictionary<T, T> Dictionary_Add()
    {
        var collection = new Dictionary<T, T>(Size);
        var uniqueValues = _uniqueValues;

        for (int i = 0; i < uniqueValues.Length; i++)
            collection.Add(uniqueValues[i], uniqueValues[i]);

        return collection;
    }
}

Method Runtime Size Mean Error StdDev Ratio
Add_IntKey .NET 4.8 1000 10.449 us 0.0690 us 0.0456 us 1.00
Add_IntKey .NET Core 2.1 1000 12.270 us 0.0492 us 0.0325 us 1.17
Add_IntKey .NET Core 3.1 1000 11.355 us 0.0723 us 0.0478 us 1.09
Add_StringKey .NET 4.8 1000 33.229 us 0.0331 us 0.0219 us 1.00
Add_StringKey .NET Core 2.1 1000 35.303 us 0.1821 us 0.1084 us 1.06
Add_StringKey .NET Core 3.1 1000 26.976 us 0.1248 us 0.0825 us 0.81

Добавление в Dictionary с ключом String стало быстрее на 19%. В случае с Int ключом результат (ratio) зависит от размера: на 100 — 0.95, на 1'000 — 1.09, на 10'000 — 0.93. Отклонения небольшие, возможно, это просто "шум". На других машинах отклонения ещё меньше. Будем считать, что с ключом типа Int добавление элемента происходит примерно с той же скоростью.


GetValue


Код Dictionary_GetValue
[GenericTypeArguments(typeof(int))]
[GenericTypeArguments(typeof(string))]
public class DictionaryGetValue<T>
{
    private Dictionary<T, T> _dictionary;
    private T[] _values;

    [Params(100, 1_000, 10_000)]
    public int Size;

    [GlobalSetup]
    public void Setup()
    {
        _values = ValuesGenerator.ArrayOfUniqueValues<T>(Size);
        _dictionary = _values.ToDictionary(i => i);
    }

    [Benchmark]
    public T Dictionary_GetValue()
    {
        Dictionary<T, T> collection = _dictionary;
        T[] values = _values;

        T result = default;

        for (int i = 0; i < values.Length; i++)
            result = collection[values[i]];

        return result;
    }
}

Method Runtime Size Mean Error StdDev Ratio
GetValue_IntKey .NET 4.8 1000 10.916 us 0.019 us 0.013 us 1.00
GetValue_IntKey .NET Core 2.1 1000 10.985 us 0.135 us 0.089 us 1.01
GetValue_IntKey .NET Core 3.1 1000 9.424 us 0.086 us 0.056 us 0.86
GetValue_StringKey .NET 4.8 1000 31.622 us 0.294 us 0.175 us 1.00
GetValue_StringKey .NET Core 2.1 1000 31.787 us 0.090 us 0.047 us 1.00
GetValue_StringKey .NET Core 3.1 1000 23.572 us 0.098 us 0.058 us 0.75

Получение элемента по строковому ключу стало быстрее на 25%, по Int ключу — на 14%. Однако, здесь есть зависимость от размера Dictionary. Чем меньше размер — тем больше Framework отстает от Core 3 и наоборот. На маленьких размерах Core 3 работает в 1.5 раза быстрей. При достижении размера в 10'000 производительность Core 3 падает до уровня Framework и даже чуть ниже (см. отчеты ниже).


В коде класса Dictionary слишком много изменений, чтобы однозначно сказать, какие из них больше всего повлияли на производительность.


Dictionary Methods Summary


Сводная таблица относительной производительности основных методов Dictionary при N = 1000.


Dictionary Method Type .NET 4.8 Core 2.1 Core 3.1 Details
Ctor Int 1.00 0.95 0.62 Report
Ctor String 1.00 4.06 3.84 Report
Add Int 1.00 1.17 1.09 Report
Add String 1.00 1.06 0.81 Report
GetValue Int 1.00 1.01 0.86 Report
GetValue String 1.00 1.00 0.75 Report
ContainsKey Int 1.00 0.84 0.78 Report
ContainsKey String 1.00 0.99 0.73 Report
ContainsValue Int 1.00 0.54 0.54 Report
ContainsValue String 1.00 0.86 0.90 Report

Результаты


Как и ожидалось, почти все рассмотренные методы на Core 3 работают быстрее. Разница зачастую составляет 20-30%, а то и больше. Для таких базовых коллекций это отличный результат.


Код и детальные результаты всех тестов доступны на GitHub.


На сегодня Core практически догнал Framework по возможностям, а по производительности давно оставил его позади. Что касается ASP.NET Core — к третьей версии он вышел в топ самых производительных веб-фреймворков (топ-5 по последним тестам TechEmpower).


Материалы по теме


Стивен Тауб про оптимизации в .NET Core: Core 2.0, Core 2.1, Core 3.0
Блоги: Андрей Акиньшин, Егор Богатов, Adam Sitnik, Matt Warren
Материалы по .NET Performance
Тесты веб-фреймворков от TechEmpower
Репозиторий с перфоманс тестами
Репозиторий рантайма Core
Браузер исходного кода .NET Framework и .NET Core

Tags:net corenet frameworkC#benchmarkbenchmarkdotnet
Hubs: .NET C#
+41
15.8k 76
Comments 40