День 1535. #ЗаметкиНаПолях
LINQ на Стероидах с SIMD
В этом посте рассмотрим использование SIMD-инструкций для ускорения запросов LINQ и посмотрим, как это работает совместно с «обобщённой математикой» в C# 10.
Допустим, у нас есть список чисел, и мы хотим найти сумму. Самый быстрый способ — использовать SIMD-инструкции (Single Instruction Multiple Data), которые позволяют выполнять одну и ту же операцию с несколькими значениями данных одновременно. Внимание: есть две ловушки, связанные с этим:
- Это гораздо сложнее, чем простой цикл или использование LINQ.
- Не рекомендуется для небольших наборов данных и когда производительность не критична.
Точкой входа в SIMD-операции является тип Vector<T>. T может быть любого числового типа. Тип Vector<T> имеет свойство Count, которое сообщает, сколько элементов он может содержать. Это важно, потому что, если мы, например, складываем два вектора друг с другом, мы делаем это за "одну" операцию. Результатом будет вектор с тем же количеством элементов, что и входные векторы. Чем больше элементов мы можем хранить, тем быстрее будет работать код. Это зависит от вашей архитектуры. В вашем процессоре есть SSE: «Streaming SIMD Extensions» - набор инструкций, позволяющих выполнять SIMD-операции. Размер векторов зависит от версии SSE, которую поддерживает ЦП: SSE2 – 2 элемента, SSE4.1 – 4 и так далее.
С появлением C# 10 и «обобщённой математики», мы можем использовать операции SIMD для любого числового типа, не создавая функцию для каждого типа в отдельности.
Идея состоит в том, что мы разбиваем нашу проблему на более мелкие подзадачи, которые будут решаться за одну операцию. Например, функция Min: разбиваем весь массив на мелкие фрагменты и ищем в каждом наименьшее значение.
public static T Min<T>(this Span<T> span)
where T : unmanaged, IMinMaxValue<T>, INumber<T>
Для простоты мы используем Span<T>. Нам нужна непрерывная память, так как блоки памяти передаются в процессор SIMD, который не может обрабатывать произвольные адреса памяти.
- INumber<T> — означает, что тип является числом.
- IMinMaxValue<T> — тип имеет минимальное и максимальное значение.
- unmanaged - тип является типом значения и не содержит ссылочных типов внутри себя. Таким мы можем использовать stackalloc, и запрещать сценарии, в которых структура со ссылочным типом внутри даёт неожиданные результаты.
Сначала создаём вектор с максимальным значением типа и приводим Span непосредственно к вектору:
var spanAsVectors =
MemoryMarshal.Cast<T, Vector<T>>(span);
Span<T> vector =
stackalloc T[Vector<T>.Count];
vector.Fill(T.MaxValue);
var min = new Vector<T>(vector);
Далее сравниваем каждую запись вектора с каждым другим вектором, чтобы получить минимум:
foreach (var v in spanAsVectors)
min = Vector.Min(v, min);
В итоге получим вектор с n элементами, один из которых является минимальным. НО! MemoryMarshal.Cast<T, Vector<T>>(span) имеет большой недостаток: если у нас Vector<T>.Count = 4, а всего элементов 9, функция вернёт только 2 вектора. Поэтому мы должны выделить и сравнить «остаток»:
var remain = span.Length % Vector<T>.Count;
if (remain > 0)
{
Span<T> last =
stackalloc T[Vector<T>.Count];
last.Fill(T.MaxValue);
span[^remain..].CopyTo(last);
min = Vector.Min(min, new Vector<T>(last));
}
Теперь получим минимальное значение из вектора:
var minVal = T.MaxValue;
for (var i = 0; i < Vector<T>.Count; i++)
minVal = T.Min(minVal, min[i]);
return minVal;
Результаты бенчмарка для 100000 случайных чисел float впечатляют:
Method Mean Ratio
Linq 67.41us 1.00
For 55.58us 0.82
LinqSIMD 10.78us 0.16
С появлением обобщённой математики мы теперь можем выполнять SIMD-операции для пользовательских типов и для более широкого диапазона типов без использования дополнительного кода. Это огромный шаг вперёд для экосистемы .NET.
Код этого примера, а также других Linq функций можно найти в библиотеке LinqSIMDExtensions, которая также доступна в виде пакета nuget.
Источник: https://steven-giesel.com/blogPost/faf06188-bae9-484d-804d-a42d58d18cad
