Pull to refresh

Небольшой обзор SIMD в .NET/C#

Reading time 11 min
Views 24K

Вашему вниманию предлагается небольшой обзор возможностей векторизации алгоритмов в .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:


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;
}

  • int vectorSize = Vector<int>.Count; — это сколько 4х байтовых чисел мы можем поместить в вектор. Если используется аппаратное ускорение, то эта величина показывает сколько 4х-байтовых чисел можно поместить в один SIMD регистр. По сути она показывает над сколькими элементами данного типа можно проводить операции параллельно;
  • accVector — вектор, в котором будет накапливаться результат функции;
    var v = new Vector<int>(array, i); — загружаются данные в новый вектор v, из array, начиная с индекса i. Загрузится ровно vectorSize данных.
  • accVector = Vector.Add(accVector, v); — складываются два вектора.
    Например в Array хранится 8 чисел: {0, 1, 2, 3, 4, 5, 6, 7} и vectorSize == 4, тогда:
    В первой итерации цикла accVector = {0, 0, 0, 0}, v = {0, 1, 2, 3}, после сложения в accVector будет: {0, 0, 0, 0} + {0, 1, 2, 3} = {0, 1, 2, 3}.
    Во второй итерации v = {4, 5, 6, 7} и после сложения accVector = {0, 1, 2, 3} + {4, 5, 6, 7} = {4, 6, 8, 10}.
  • Остаётся только как-то получить сумму всех элементов вектора, для этого можно применить скалярное умножение на вектор, заполненный единицами: int result = Vector.Dot(accVector, Vector<int>.One);
    Тогда получится: {4, 6, 8, 10} {1, 1, 1, 1} = 4 1 + 6 1 + 8 1 + 10 * 1 = 28.
  • В конце, если требуется, то досуммируются числа, которые не помещаются в последний вектор.

Если взглянуть в код метода Intrinsics:


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 за некоторым исключением:


  • vectorSize задан константой. Так происходит потому что в этом методе явно используются Avx2 инструкции, которые оперируют с 256 битными регистрами. В реальном приложении должна быть проверка на то поддерживает ли текущий процессор Avx2 инструкции и если не поддерживает, вызывать другой код. Выглядит это примерно так:
    if (Avx2.IsSupported) {
    DoThingsForAvx2();
    }
    else if (Avx.IsSupported) {
    DoThingsForAvx();
    }
    ...
    else if (Sse2.IsSupported) {
    DoThingsForSse2();
    }
    ...
  • var accVector = Vector256<int>.Zero; accVector объявлен как 256 битный вектор, заполненный нулями.
  • fixed (int* ptr = Array) — в ptr заносится указатель на array.
  • Дальше такие же операции как и в Vectors: загрузка данных в вектор и сложение двух векторов.
  • Для суммирования элементов вектора был применён такой способ:
    • создаётся массив на стэке: var temp = stackalloc int[vectorSize];
    • загружается вектор в этот массив: Avx2.Store(temp, accVector);
    • в цикле суммируются элементы массива.
  • потом досуммируются элементы массива, которые не помещаются в последний вектор

Сравниваем два массива


Надо сравнить два массива байт. Собственно это та задача, из-за которой я начал изучать 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 можно посмотреть псевдокод этой операции:
Метод MoveMask из вектора делает 32-х битное число. Значениями битов являются старшие биты каждого из 32 однобайтовых элементов вектора. Псевдокод можно посмотреть здесь.


Таким образом, если какие-то байты в va и vb не совпадают, то в areEqual соответствующие байты будут равны 0, следовательно старшие биты этих байт тоже будут равны 0, а значит и соответствующие биты в ответе Avx2.MoveMask тоже будут равны 0 и сравнение с equalsMask не пройдёт.


Разберём небольшой пример, приняв что длина вектора 8 байт (чтобы писать было меньше):


  • Пускай va = {100, 10, 20, 30, 100, 40, 50, 100}, а vb = {100, 20, 10, 30, 100, 40, 80, 90};
  • Тогда areEqual будет равен {255, 0, 0, 255, 255, 255, 0, 0};
  • Метод MoveMask вернёт 10011100b, который нужно будет сравнивать с маской 11111111b, т.к. эти маски неравны, то выходит, что и векторы va и vb неравны.

Подсчитываем сколько раз элемент встречается в коллекции


Иногда требуется посчитать сколько раз конкретный элемент встречается в коллекции, например, интов, этот алгоритм тоже можно ускорить. Напишем несколько методов для сравнения, будем искать в массиве 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 полностью совпадают в логике, отличия только в реализации конкретных операций. Идея в целом такая:


  • создаётся вектор mask, в котором в каждом элементе храниться искомое число;
  • Загружается в вектор v часть массива и сравнивается с маской, тогда в равных элементах в areEqual будут выставлены все биты, т.к. areEqual — вектор из интов, то, если выставить все биты одного элемента, получим -1 в этом элементе ((int)(1111_1111_1111_1111_1111_1111_1111_1111b) == -1);
  • вычитается из accVector вектор areEqual и тогда в accVector будет сумма того, сколько раз элемент item встретился во всех векторах v для каждой позиции (минус на минут дают плюс).

Весь код из статьи можно найти на GitHub


Заключение


Я рассмотрел лишь очень малую часть возможностей, которые предоставляет .NET для векторизации вычислений. За полным и актуальным список доступных интринсиков в .NETCORE под x86 можно обратиться к исходному коду. Удобно, что там в C# файлах в summary каждого интринсика есть его же название из мира C, что упрощает и понимание назначения этого интринсика, и перевод уже существующих С++/С алгоритмов на .NET. Документация по System.Numerics.Vector доступна на msdn.


На мой вгляд, у .NET есть большое преимущество перед C++, т.к. JIT компиляция происходит уже на клиентской машине, то компилятор может оптимизировать код под конкретный клиентский процессор, предоставляя максимальную производительность. При этом программист для написания быстрого кода может оставаться в рамках одного языка и технологий.


UPD (15.09.2019):


В бенчмарках был косяк

В бенчмарках я использовал IterationSetup, которые, как выяснилось, может сильно влиять на показатели бенчмарков, которые отрабатывают меньше чем за 100мс. Если переделать на GlobalSetup, то результаты будут вот такие.


Сумма элементов массива:


Method ItemsCount Mean Error StdDev Ratio
Naive 10 3.531 ns 0.0336 ns 0.0314 ns 1.00
LINQ 10 76.925 ns 0.4166 ns 0.3897 ns 21.79
Vectors 10 2.750 ns 0.0210 ns 0.0196 ns 0.78
Intrinsics 10 6.513 ns 0.0623 ns 0.0582 ns 1.84
Naive 100 47.982 ns 0.3975 ns 0.3524 ns 1.00
LINQ 100 590.414 ns 3.8808 ns 3.4402 ns 12.31
Vectors 100 10.122 ns 0.0747 ns 0.0699 ns 0.21
Intrinsics 100 14.277 ns 0.0566 ns 0.0529 ns 0.30
Naive 1000 569.910 ns 2.8297 ns 2.6469 ns 1.00
LINQ 1000 5,658.570 ns 31.7465 ns 29.6957 ns 9.93
Vectors 1000 79.598 ns 0.3498 ns 0.3272 ns 0.14
Intrinsics 1000 66.970 ns 0.3937 ns 0.3682 ns 0.12
Naive 10000 5,637.571 ns 37.5050 ns 29.2814 ns 1.00
LINQ 10000 56,498.987 ns 294.8776 ns 275.8287 ns 10.02
Vectors 10000 772.900 ns 2.6802 ns 2.5070 ns 0.14
Intrinsics 10000 579.152 ns 2.8371 ns 2.6538 ns 0.10
Naive 100000 56,352.865 ns 230.7916 ns 215.8826 ns 1.00
LINQ 100000 562,610.571 ns 3,775.7631 ns 3,152.9332 ns 9.98
Vectors 100000 8,389.647 ns 165.9590 ns 227.1666 ns 0.15
Intrinsics 100000 7,261.334 ns 89.6468 ns 69.9903 ns 0.13

Сравнение двух массивов:


Method ItemsCount Mean Error StdDev Ratio
Naive 10000 7,033.8 ns 50.636 ns 47.365 ns 1.00
LINQ 10000 64,841.4 ns 289.157 ns 270.478 ns 9.22
Vectors 10000 504.0 ns 2.406 ns 2.251 ns 0.07
MemCmp 10000 368.1 ns 2.637 ns 2.466 ns 0.05
Intrinsics 10000 283.6 ns 1.135 ns 1.061 ns 0.04
Naive 100000 85,214.4 ns 903.868 ns 845.478 ns 1.00
LINQ 100000 702,279.4 ns 2,846.609 ns 2,662.720 ns 8.24
Vectors 100000 5,179.2 ns 45.337 ns 42.409 ns 0.06
MemCmp 100000 4,510.5 ns 24.292 ns 22.723 ns 0.05
Intrinsics 100000 2,957.0 ns 11.452 ns 10.712 ns 0.03
Naive 1000000 844,006.1 ns 3,552.478 ns 3,322.990 ns 1.00
LINQ 1000000 6,483,079.3 ns 42,641.040 ns 39,886.455 ns 7.68
Vectors 1000000 54,180.1 ns 357.258 ns 334.180 ns 0.06
MemCmp 1000000 49,480.1 ns 515.675 ns 457.133 ns 0.06
Intrinsics 1000000 36,633.9 ns 680.525 ns 636.564 ns 0.04

Количество вхождений элемента в массив:


Method ItemsCount Mean Error StdDev Ratio
Naive 10 8.844 ns 0.0772 ns 0.0603 ns 1.00
LINQ 10 87.456 ns 0.9496 ns 0.8883 ns 9.89
Vectors 10 3.140 ns 0.0406 ns 0.0380 ns 0.36
Intrinsics 10 13.813 ns 0.0825 ns 0.0772 ns 1.56
Naive 100 107.310 ns 0.6975 ns 0.6183 ns 1.00
LINQ 100 626.285 ns 5.7677 ns 5.3951 ns 5.83
Vectors 100 11.844 ns 0.2113 ns 0.1873 ns 0.11
Intrinsics 100 19.616 ns 0.1018 ns 0.0903 ns 0.18
Naive 1000 1,032.466 ns 6.3799 ns 5.6556 ns 1.00
LINQ 1000 6,266.605 ns 42.6585 ns 39.9028 ns 6.07
Vectors 1000 83.417 ns 0.5393 ns 0.4780 ns 0.08
Intrinsics 1000 88.358 ns 0.4921 ns 0.4603 ns 0.09
Naive 10000 9,942.503 ns 47.9732 ns 40.0598 ns 1.00
LINQ 10000 62,305.598 ns 643.8775 ns 502.6972 ns 6.27
Vectors 10000 914.967 ns 7.2959 ns 6.8246 ns 0.09
Intrinsics 10000 931.698 ns 6.3444 ns 5.9346 ns 0.09
Naive 100000 94,834.804 ns 793.8585 ns 703.7349 ns 1.00
LINQ 100000 626,620.968 ns 4,696.9221 ns 4,393.5038 ns 6.61
Vectors 100000 9,000.827 ns 179.5351 ns 192.1005 ns 0.09
Intrinsics 100000 8,690.771 ns 101.7078 ns 95.1376 ns 0.09
Naive 1000000 959,302.249 ns 4,268.2488 ns 3,783.6914 ns 1.00
LINQ 1000000 6,218,681.888 ns 31,321.9277 ns 29,298.5506 ns 6.48
Vectors 1000000 99,778.488 ns 1,975.6001 ns 4,252.6877 ns 0.10
Intrinsics 1000000 96,449.350 ns 1,171.8067 ns 978.5116 ns 0.10
Tags:
Hubs:
+32
Comments 50
Comments Comments 50

Articles