Как увеличилась производительность 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?.