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

Релиз .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

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

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

Цикл foreach

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

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

Add

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

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

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

Contains

Давайте возьмём негативный сценарий для метода 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;
    }
}

На 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.

Array Methods Summary

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

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

Dictionary

Randomized Hash

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

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

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

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

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

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

Dictionary Methods Summary

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

Результаты

Как и ожидалось, почти все рассмотренные методы на 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