.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 (да и основу для самих бенчмарков) я позаимствовал из репозитория перфоманс-тестов ^[1]. Эти тесты используются мейнтейнерами .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" (подробнее ^[20]). Естественно, этот алгоритм медленнее, чем нерандомизированный. Чтобы производительность 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 ^[31].

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

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

Стивен Тауб про оптимизации в .NET Core: Core 2.0 ^[33], Core 2.1 ^[34], Core 3.0 ^[35]
Блоги: Андрей Акиньшин ^[36], Егор Богатов ^[37], Adam Sitnik ^[38], Matt Warren ^[39]
Материалы по .NET Performance ^[40]
Тесты веб-фреймворков от TechEmpower ^[41]
Репозиторий с перфоманс тестами ^[1]
Репозиторий рантайма Core ^[42]
Браузер исходного кода .NET Framework ^[43] и .NET Core ^[44]

Автор: fixer_m

Источник ^[45]