- PVSM.RU - https://www.pvsm.ru -
Вашему вниманию предлагается небольшой обзор возможностей векторизации алгоритмов в .NET Framework и .NETCORE. Цель статьи познакомить с этими приёмами тех, кто их вообще не знал и показать, что .NET не сильно отстаёт от "настоящих, компилируемых" языков для нативной
разработки.
Я только начинаю изучать приёмы векторизации, так что если кто из сообщества укажет мне на явные косяк, или предложит улучшенные версии описанных ниже алгоритмов, то буду дико рад.
В .NET SIMD впервые появился в 2015 году с выходом .NET Framework 4.6. Тогда были добавлены типы Matrix3x2, Matrix4x4, Plane, Quaternion, Vector2, Vector3 и Vector4, которые позволили прозводить векторизированные вычисления. Позже был добавлен тип Vector<T>, который предоставил больше возможностей для векторизации алгоритмов. Но многие программисты всё равно были недовольны, т.к. вышеописанные типы ограничивали поток мыслей программиста и не давали возможности использовать полную мощь SIMD-инструкций современных процессоров. Уже в наше время, в .NET Core 3.0 Preview появилось пространство имён System.Runtime.Intrinsics, которое предоставляет гораздо большую свободу в выборе инструкций. Чтобы получить наилучшие результаты в скорости надо использовать RyuJit и нужно либо собирать под x64, либо отключить Prefer 32-bit и собирать под AnyCPU. Все бенчмарки я запускал на компьютере с процессором Intel Core i7-6700 CPU 3.40GHz (Skylake).
Я решил начать с классической задачи, которую часто пишут первой, когда речь заходит про векторизацию. Это задача нахождения суммы элементов массива. Напишем четыре реализации этой задачи, будем суммировать элементы массива Array:
Самая очевидная
public int Naive() {
int result = 0;
foreach (int i in Array) {
result += i;
}
return result;
}
С использованием LINQ
public long LINQ() => Array.Aggregate<int, long>(0, (current, i) => current + i);
С использованием векторов из System.Numerics:
public int Vectors() {
int vectorSize = Vector<int>.Count;
var accVector = Vector<int>.Zero;
int i;
var array = Array;
for (i = 0; i < array.Length - vectorSize; i += vectorSize) {
var v = new Vector<int>(array, i);
accVector = Vector.Add(accVector, v);
}
int result = Vector.Dot(accVector, Vector<int>.One);
for (; i < array.Length; i++) {
result += array[i];
}
return result;
}
С использованием кода из пространства System.Runtime.Intrinsics:
public unsafe int Intrinsics() {
int vectorSize = 256 / 8 / 4;
var accVector = Vector256<int>.Zero;
int i;
var array = Array;
fixed (int* ptr = array) {
for (i = 0; i < array.Length - vectorSize; i += vectorSize) {
var v = Avx2.LoadVector256(ptr + i);
accVector = Avx2.Add(accVector, v);
}
}
int result = 0;
var temp = stackalloc int[vectorSize];
Avx2.Store(temp, accVector);
for (int j = 0; j < vectorSize; j++) {
result += temp[j];
}
for (; i < array.Length; i++) {
result += array[i];
}
return result;
}
Я запустил бенчмарк на эти 4 метода у себя на компьютере и получил такой результат:
Method | ItemsCount | Median |
---|---|---|
Naive | 10 | 75.12 ns |
LINQ | 10 | 1,186.85 ns |
Vectors | 10 | 60.09 ns |
Intrinsics | 10 | 255.40 ns |
Naive | 100 | 360.56 ns |
LINQ | 100 | 2,719.24 ns |
Vectors | 100 | 60.09 ns |
Intrinsics | 100 | 345.54 ns |
Naive | 1000 | 1,847.88 ns |
LINQ | 1000 | 12,033.78 ns |
Vectors | 1000 | 240.38 ns |
Intrinsics | 1000 | 630.98 ns |
Naive | 10000 | 18,403.72 ns |
LINQ | 10000 | 102,489.96 ns |
Vectors | 10000 | 7,316.42 ns |
Intrinsics | 10000 | 3,365.25 ns |
Naive | 100000 | 176,630.67 ns |
LINQ | 100000 | 975,998.24 ns |
Vectors | 100000 | 78,828.03 ns |
Intrinsics | 100000 | 41,269.41 ns |
Видно, что решения с Vectors и Intrinsics очень сильно выигрывают в скорости по сравнению с очевидным решением и с LINQ. Теперь надо разобраться что происходит в этих двух методах.
Рассмотрим подробнее метод Vectors:
public int Vectors() {
int vectorSize = Vector<int>.Count;
var accVector = Vector<int>.Zero;
int i;
var array = Array;
for (i = 0; i < array.Length - vectorSize; i += vectorSize) {
var v = new Vector<int>(array, i);
accVector = Vector.Add(accVector, v);
}
int result = Vector.Dot(accVector, Vector<int>.One);
for (; i < array.Length; i++) {
result += array[i];
}
return result;
}
Если взглянуть в код метода Intrinsics:
public unsafe int Intrinsics() {
int vectorSize = 256 / 8 / 4;
var accVector = Vector256<int>.Zero;
int i;
var array = Array;
fixed (int* ptr = array) {
for (i = 0; i < array.Length - vectorSize; i += vectorSize) {
var v = Avx2.LoadVector256(ptr + i);
accVector = Avx2.Add(accVector, v);
}
}
int result = 0;
var temp = stackalloc int[vectorSize];
Avx2.Store(temp, accVector);
for (int j = 0; j < vectorSize; j++) {
result += temp[j];
}
for (; i < array.Length; i++) {
result += array[i];
}
return result;
}
То можно увидеть, что он очень похож на Vectors за некоторым исключением:
if (Avx2.IsSupported) {
DoThingsForAvx2();
}
else if (Avx.IsSupported) {
DoThingsForAvx2();
}
...
else if (Sse2.IsSupported) {
DoThingsForSse2();
}
...
Надо сравнить два массива байт. Собственно это та задача, из-за которой я начал изучать SIMD в .NET. Напишем опять несколько методов для бенчмарка, будем сравнивать два массива: ArrayA и ArrayB:
Самое очевидное решение:
public bool Naive() {
for (int i = 0; i < ArrayA.Length; i++) {
if (ArrayA[i] != ArrayB[i]) return false;
}
return true;
}
Решение через LINQ:
public bool LINQ() => ArrayA.SequenceEqual(ArrayB);
Решение через функцию MemCmp:
[DllImport("msvcrt.dll", CallingConvention = CallingConvention.Cdecl)]
static extern int memcmp(byte[] b1, byte[] b2, long count);
public bool MemCmp() => memcmp(ArrayA, ArrayB, ArrayA.Length) == 0;
С использованием векторов из System.Numerics:
public bool Vectors() {
int vectorSize = Vector<byte>.Count;
int i = 0;
for (; i < ArrayA.Length - vectorSize; i += vectorSize) {
var va = new Vector<byte>(ArrayA, i);
var vb = new Vector<byte>(ArrayB, i);
if (!Vector.EqualsAll(va, vb)) {
return false;
}
}
for (; i < ArrayA.Length; i++) {
if (ArrayA[i] != ArrayB[i])
return false;
}
return true;
}
С использованием Intrinsics:
public unsafe bool Intrinsics() {
int vectorSize = 256 / 8;
int i = 0;
const int equalsMask = unchecked((int) (0b1111_1111_1111_1111_1111_1111_1111_1111));
fixed (byte* ptrA = ArrayA)
fixed (byte* ptrB = ArrayB) {
for (; i < ArrayA.Length - vectorSize; i += vectorSize) {
var va = Avx2.LoadVector256(ptrA + i);
var vb = Avx2.LoadVector256(ptrB + i);
var areEqual = Avx2.CompareEqual(va, vb);
if (Avx2.MoveMask(areEqual) != equalsMask) {
return false;
}
}
for (; i < ArrayA.Length; i++) {
if (ArrayA[i] != ArrayB[i])
return false;
}
return true;
}
}
Результат бэнчмарка на моём компьютере:
Method | ItemsCount | Median |
---|---|---|
Naive | 10000 | 66,719.1 ns |
LINQ | 10000 | 71,211.1 ns |
Vectors | 10000 | 3,695.8 ns |
MemCmp | 10000 | 600.9 ns |
Intrinsics | 10000 | 1,607.5 ns |
Naive | 100000 | 588,633.7 ns |
LINQ | 100000 | 651,191.3 ns |
Vectors | 100000 | 34,659.1 ns |
MemCmp | 100000 | 5,513.6 ns |
Intrinsics | 100000 | 12,078.9 ns |
Naive | 1000000 | 5,637,293.1 ns |
LINQ | 1000000 | 6,622,666.0 ns |
Vectors | 1000000 | 777,974.2 ns |
MemCmp | 1000000 | 361,704.5 ns |
Intrinsics | 1000000 | 434,252.7 ns |
Весь код этих методов, думаю, понятен, за исключением двух строк в Intrinsics:
var areEqual = Avx2.CompareEqual(va, vb);
if (Avx2.MoveMask(areEqual) != equalsMask) {
return false;
}
В первой два вектора сравниваются на равенство и результат сохраняется в вектор areEqual, у которого в элемент на конкретной позиции все биты выставляются в 1, если соответствующие элементы в va и vb равны. Получается, что если векторы из байт va и vb полностью равны, то в areEquals все элементы должны равняться 255 (11111111b). Т.к. Avx2.CompareEqual является обёрткой над _mm256_cmpeq_epi8, то на сайте Intel [1] можно посмотреть псевдокод этой операции:
Метод MoveMask из вектора делает 32-х битное число. Значениями битов являются старшие биты каждого из 32 однобайтовых элементов вектора. Псевдокод можно посмотреть здесь [2].
Таким образом, если какие-то байты в va и vb не совпадают, то в areEqual соответствующие байты будут равны 0, следовательно старшие биты этих байт тоже будут равны 0, а значит и соответствующие биты в ответе Avx2.MoveMask тоже будут равны 0 и сравнение с equalsMask не пройдёт.
Разберём небольшой пример, приняв что длина вектора 8 байт (чтобы писать было меньше):
Иногда требуется посчитать сколько раз конкретный элемент встречается в коллекции, например, интов, этот алгоритм тоже можно ускорить. Напишем несколько методов для сравнения, будем искать в массиве Array элемент Item:
Самый очевидный:
public int Naive() {
int result = 0;
foreach (int i in Array) {
if (i == Item) {
result++;
}
}
return result;
}
с использованием LINQ:
public int LINQ() => Array.Count(i => i == Item);
с использованием векторов из System.Numerics.Vectors:
public int Vectors() {
var mask = new Vector<int>(Item);
int vectorSize = Vector<int>.Count;
var accResult = new Vector<int>();
int i;
var array = Array;
for (i = 0; i < array.Length - vectorSize; i += vectorSize) {
var v = new Vector<int>(array, i);
var areEqual = Vector.Equals(v, mask);
accResult = Vector.Subtract(accResult, areEqual);
}
int result = 0;
for (; i < array.Length; i++) {
if (array[i] == Item) {
result++;
}
}
result += Vector.Dot(accResult, Vector<int>.One);
return result;
}
С использованием Intrinsics:
public unsafe int Intrinsics() {
int vectorSize = 256 / 8 / 4;
//var mask = Avx2.SetAllVector256(Item);
//var mask = Avx2.SetVector256(Item, Item, Item, Item, Item, Item, Item, Item);
var temp = stackalloc int[vectorSize];
for (int j = 0; j < vectorSize; j++) {
temp[j] = Item;
}
var mask = Avx2.LoadVector256(temp);
var accVector = Vector256<int>.Zero;
int i;
var array = Array;
fixed (int* ptr = array) {
for (i = 0; i < array.Length - vectorSize; i += vectorSize) {
var v = Avx2.LoadVector256(ptr + i);
var areEqual = Avx2.CompareEqual(v, mask);
accVector = Avx2.Subtract(accVector, areEqual);
}
}
int result = 0;
Avx2.Store(temp, accVector);
for(int j = 0; j < vectorSize; j++) {
result += temp[j];
}
for(; i < array.Length; i++) {
if (array[i] == Item) {
result++;
}
}
return result;
}
Результат бенчмарка на моём компьютере:
Method | ItemsCount | Median |
---|---|---|
Naive | 1000 | 2,824.41 ns |
LINQ | 1000 | 12,138.95 ns |
Vectors | 1000 | 961.50 ns |
Intrinsics | 1000 | 691.08 ns |
Naive | 10000 | 27,072.25 ns |
LINQ | 10000 | 113,967.87 ns |
Vectors | 10000 | 7,571.82 ns |
Intrinsics | 10000 | 4,296.71 ns |
Naive | 100000 | 361,028.46 ns |
LINQ | 100000 | 1,091,994.28 ns |
Vectors | 100000 | 82,839.29 ns |
Intrinsics | 100000 | 40,307.91 ns |
Naive | 1000000 | 1,634,175.46 ns |
LINQ | 1000000 | 6,194,257.38 ns |
Vectors | 1000000 | 583,901.29 ns |
Intrinsics | 1000000 | 413,520.38 ns |
Методы Vectors и Intrinsics полностью совпадают в логике, отличия только в реализации конкретных операций. Идея в целом такая:
Весь код из статьи можно найти на GitHub [3]
Я рассмотрел лишь очень малую часть возможностей, которые предоставляет .NET для векторизации вычислений. За полным и актуальным список доступных интринсиков в .NETCORE под x86 можно обратиться к исходному коду [4]. Удобно, что там в C# файлах в summary каждого интринсика есть его же название из мира C, что упрощает и понимание назначения этого интринсика, и перевод уже существующих С++/С алгоритмов на .NET. Документация по System.Numerics.Vector доступна на msdn [5].
На мой вгляд, у .NET есть большое преимущество перед C++, т.к. JIT компиляция происходит уже на клиентской машине, то компилятор может оптимизировать код под конкретный клиентский процессор, предоставляя максимальную производительность. При этом программист для написания быстрого кода может оставаться в рамках одного языка и технологий.
Автор: Юдаков Дмитрий
Источник [6]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/c-2/305034
Ссылки в тексте:
[1] на сайте Intel: https://software.intel.com/sites/landingpage/IntrinsicsGuide/#expand=406,3832,784&text=_mm256_cmpeq_epi8
[2] здесь: https://software.intel.com/sites/landingpage/IntrinsicsGuide/#expand=406,3832,784,3832&text=_mm256_movemask_epi8
[3] GitHub: https://github.com/tdkkdt/SIMDArticle
[4] исходному коду: https://github.com/dotnet/corefx/tree/master/src/Common/src/CoreLib/System/Runtime/Intrinsics/X86
[5] msdn: https://docs.microsoft.com/en-us/dotnet/api/system.numerics.vector
[6] Источник: https://habr.com/post/435840/?utm_source=habrahabr&utm_medium=rss&utm_campaign=435840
Нажмите здесь для печати.