Как увеличилась производительность LINQ в .NET 7?

В новой версии .NET улучшилась производительность методов Min, Max, Average и Sum для массивов и списков. Как вы думаете, во сколько раз увеличилась скорость их выполнения? В 2 раза, в 5? Нет, они стали гораздо быстрее. Посмотрим, как этого удалось достичь.

Как же улучшился LINQ?

LINQ (Language-Integrated Query) представляет простой и удобный язык запросов. Он позволяет в простой форме выражать сложные операции. LINQ использует практически каждый разработчик .NET. Однако за удобство использования приходится платить скоростью выполнения и лишней выделенной памятью. В большинстве ситуаций эти затраты не оказывают существенного влияния. Однако в местах, где производительность является критичной, эти недостатки могут неприятно проявиться.

Итак, методы, которые получили улучшения производительности: Enumerable.Max, Enumerable.Min, Enumerable.Average, Enumerable.Sum.

С помощью небольшого бенчмарка проверим, как увеличилась их производительность.

using BenchmarkDotNet.Attributes; using BenchmarkDotNet.Running; using System.Collections.Generic; using System.Linq;   [MemoryDiagnoser(displayGenColumns: false)] public partial class Program {   static void Main(string[] args) =>     BenchmarkSwitcher.FromAssembly(typeof(Program).Assembly).Run(args);    [Params (10, 10000)]   public int Size { get; set; }   private IEnumerable<int> items;    [GlobalSetup]   public void Setup()   {     items = Enumerable.Range(1, Size).ToArray();   }      [Benchmark]   public int Min() => items.Min();    [Benchmark]   public int Max() => items.Max();    [Benchmark]   public double Average() => items.Average();    [Benchmark]   public int Sum() => items.Sum(); } 

Результаты бенчмарка:

Из результатов видно, что для небольших массивов время выполнения поиска минимума уменьшилось в 10 раз, а для массива в 10 000 элементов — в 20 раз. Аналогичная ситуация и для остальных методов, кроме нахождения суммы — разница в размере коллекций не так значительно повлияла на результат.

Также стоит заметить, что в .NET 7 при вызове методов не выделяется дополнительная память.

Проверим, как эти методы будут работать со списками List<T>.

В .NET 6 операции над массивами быстрее, чем над списками. Это справедливо и в .NET 7 для небольших коллекций. C ростом числа элементов списки сравниваются с массивами по производительности.

По результатам тестов производительность для списков увеличилась в 31 раз.

За счёт чего достигается такое преимущество?

Заглянем в реализацию метода Min и посмотрим, как он устроен.

Так выглядит реализация метода Min в .NET 6:

public static int Min(this IEnumerable<int> source) {   if (source == null)   {     ThrowHelper.ThrowArgumentNullException(ExceptionArgument.source);   }    int value;   using (IEnumerator<int> e = source.GetEnumerator())   {     if (!e.MoveNext())     {       ThrowHelper.ThrowNoElementsException();     }      value = e.Current;     while (e.MoveNext())     {       int x = e.Current;       if (x < value)       {         value = x;       }     }   }   return value; } 

Метод довольно простой. Получаем коллекцию IEnumerable<int>, берём элемент коллекции и с помощью метода MoveNext получаем следующий элемент. Сравниваем их, сохраняем тот, что меньше, повторяем до конца коллекции.

Новая версия метода Min выглядит иначе:

public static int Min(this IEnumerable<int> source) => MinInteger(source); 

Для коллекций целых чисел применяется метод MinInteger. Рассмотрим, что в нём происходит.

private static T MinInteger<T>(this IEnumerable<T> source)   where T : struct, IBinaryInteger<T> {   T value;    if (source.TryGetSpan(out ReadOnlySpan<T> span))   {     if (Vector.IsHardwareAccelerated &&          span.Length >= Vector<T>.Count * 2)     {       .... // Оптимизированная реализация       return ....;     }   }   .... //Реализация как в .NET 6 } 

Прежде всего пытаемся получить из предоставленной коллекции объект типа ReadOnlySpan<T>. Если не удалось получить ReadOnlySpan представление коллекции, то выполняется ветвь кода, соответствующая реализации метода Min в .NET 6. В нашем случае мы можем получить ReadOnlySpan, так как используем массивы и списки.

Что представляет собой ReadOnlySpan? Типы Span и ReadOnlySpan обеспечивают безопасное представление непрерывной области управляемой и неуправляемой памяти. Структура Span определена как ref struct. Это означает, что она может размещаться только на стеке, что позволяет избежать выделения дополнительной памяти и повышает производительность работы с данными.

В новой версии C# Span тоже немного изменился. С появлением в С# 11 возможности создавать в ref struct поля, хранящиеся по ссылкам, немного изменилось внутреннее представление Span<T>. Раньше для хранения ссылки на начало области памяти применялся специальный внутренний тип ByReference<T>, однако в нём не было проверки безопасности. Сейчас для этого используется ref fields. Это изменение обеспечивает более безопасную работу с памятью. О других нововведениях C# 11 можете прочитать в статье.

Вернёмся к рассмотрению метода Min. Получив ReadOnlySpan, метод пытается по возможности векторизовать поиск, используя тип Vector<T>. Для этого должно выполняться условие:

if (Vector.IsHardwareAccelerated && span.Length >= Vector<T>.Count * 2) 

Первая часть условия проверяет, возвращает ли свойство Vector.IsHardwareAccelerated true. Заглянем в реализацию этого свойства.

public static bool IsHardwareAccelerated {   [Intrinsic]   get => false; } 

К геттеру применяется атрибут [Intrinsic]. Он указывает на то, что значение, возвращаемое IsHardwareAccelerated, может быть заменено JIT. Свойство вернёт true, если к операциям над векторами можно применить аппаратное ускорение посредством встроенной поддержки JIT, в противном случае вернётся false. Для включения аппаратного ускорения необходимо запустить сборку для x64 платформы с Release конфигурацией либо собирать под AnyCPU с отключённым Prefer 32-bit.

Для выполнения второй части условия нужно, чтобы размер Span был как минимум в 2 раза больше размера вектора.

Как будет вычисляться размер этого вектора?

В новой реализации метода *Min *для создания вектора используется тип данных Vector<T>. Этот тип представляет собой обёртку над тремя другими: Vector64<T>, Vector128<T> и Vector256<T>. Они содержат векторизованные данные соответствующей длины. Vector128<T> может хранить 16 8-битных, 8 16-битных, 4 32-битных или 2 64-битных значения. Какой тип использовать, выбирается в зависимости от того, поддерживается он процессором или нет.

Таким образом если при исполнении метода используется тип Vector128<T>, то полученный из массива или списка *Span *должен содержать 8 или больше элементов типа int.

Если все условия соблюдены, метод использует преимущества ReadOnlySpan и Vector для оптимизации поиска минимума:

private static T MinInteger<T>(this IEnumerable<T> source) where T : struct, IBinaryInteger<T> {   ....    if (Vector.IsHardwareAccelerated && span.Length >= Vector<T>.Count * 2)   {     var mins = new Vector<T>(span);     index = Vector<T>.Count;     do     {       mins = Vector.Min(mins, new Vector<T>(span.Slice(index)));       index += Vector<T>.Count;     }     while (index + Vector<T>.Count <= span.Length);      value = mins[0];     for (int i = 1; i < Vector<T>.Count; i++)     {         if (mins[i] < value)       {         value = mins[i];       }     }   .... } 

Рассмотрим, как работает векторизованная реализация поиска минимума. Из первых N элементов *Span (N зависит от типа вектора; для Vector128<int> *это 4 элемента) создаётся вектор, который в методе Vector.Min сравнивается с вектором из следующих N элементов. Конечный вектор будет содержать минимальное значение каждой пары элементов двух данных векторов. Далее берётся следующая часть Span, и такой поиск продолжается. Остаётся только найти минимальное из значений, хранящихся в конечном векторе. Плюс использования вектора заключается в том, что все операции над его элементами происходят одновременно.

Выше продемонстрирован пример использования Span и векторизации для оптимизации метода Min. Что с остальными методами? Подобные возможности используются и в методах Max, Average, Sum. Оптимизированные версии этих методов доступны для массивов и списков типов int, long, float, double и decimal.

Заключение

Путём использования Span и аппаратного ускорения для работы с векторами разработчикам из Microsoft и сообщества .NET удалось достичь заметных улучшений производительности LINQ. Теперь появляется возможность использовать прокаченные методы в ситуациях, где критичны скорость выполнения кода и выделенная память.

Вообще .NET 7 получил немало других улучшений производительности. Вы можете прочитать о них в блоге .NET.

Если хотите поделиться этой статьей с англоязычной аудиторией, то прошу использовать ссылку на перевод: Mikhail Evtihevich. How has LINQ performance enhanced in .NET 7?.