12.01.2019 16:30
T-D-K 43 6800 Источник

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

Комментарии (43)


  1. Kiel
    12.01.2019 20:13
    #19606686

    В c# можно без агрегатора посчитать сумму через linq

    var arr = new []{ 5, 8, 9 };
    var sum = arr.Sum();


    А вообще c# это не производительность.


    1. T-D-K
      12.01.2019 20:59
      #19606784

      T IEnumerable.Sum() возвращает тот же тип, что и в коллекции. Aggregate позволяет этого избежать, чтобы не получить переполнения.


      1. Kiel
        12.01.2019 21:22
        #19606848

        Хорошее замечание, правда в таком случае мы кастим весь массив, что еще сильнее бьет по производительности


      1. AgentFire
        12.01.2019 21:52
        #19606902

        но ведь есть arr.Cast<long>().Sum().


        1. Anarh
          12.01.2019 23:07
          #19607054
          +1

          Ваш код выбросит исключение, потому что внутри перед кастом элементы сначала приводятся к object. В данном случае можно заменить на arr.Select(i => (long)i).Sum();


          1. T-D-K
            12.01.2019 23:08
            #19607058

            Поддерживаю. Эта классика есть в Clr via C#. Частая проблема боксинга.

            int intNumber = 10;
object o = intNumber;
long longNumber = (long) o;

            В последней строчке будет ошибка.


          1. AgentFire
            13.01.2019 12:48
            #19607988

            Это где это "внутри перед кастом" они приводятся к object?


            var arr = new []{ 5, 8, 9 };
var sum = arr.Sum();


            1. T-D-K
              13.01.2019 12:53
              #19607998

              Вот код Cast:

              public static IEnumerable<TResult> Cast<TResult>(this IEnumerable source)
{
    IEnumerable<TResult> typedSource = source as IEnumerable<TResult>;
    if (typedSource != null)
    {
        return typedSource;
    }
    
    if (source == null)
    {
        throw Error.ArgumentNull(nameof(source));
    }
    
    return CastIterator<TResult>(source);
}
private static IEnumerable<TResult> CastIterator<TResult>(IEnumerable source)
{
    foreach (object obj in source)
    {
        yield return (TResult)obj;
    }
}


              Вот в этой строчке: yield return (TResult)obj; и будет падение.


              1. AgentFire
                13.01.2019 14:01
                #19608136

                вот жеж тупость :S


    1. firedragon
      13.01.2019 10:15
      #19607626

      C# это энтерпрайз. С кучей легаси кода и очень широкими возможностями.
      Попытка спустится на низкий уровень в той же яве, это просто боль.

      Кроме этого ни что не мешает вынести критичный код в библиотеку (с + asm) и вызывать уже оттуда.


      1. dotnetdonik
        13.01.2019 13:23
        #19608046
        +2

        Кроме этого ни что не мешает вынести критичный код в библиотеку (с + asm) и вызывать уже оттуда.


        А вот люди, что полагаются на возможности SIMD из статьи ниже думают совсем иначе :)
        Integrating native code libraries into .NET code for the sake of performance is not guaranteed to yield the benefits of native code optimization unless the custom code itself is also optimized. With the high-level programming models in .NET for SIMD, concurrency I/O, database access, network programming, and many other kinds of operations, developers could choose to develop all their HPC code in .NET and avoid incurring the cost and effort of integrating low-level native code into their applications.



      1. alexr64
        13.01.2019 15:13
        #19608252

        Кроме этого ни что, кроме зависимости от конкретной ос и битности, а также наличия в команде нативного программиста под каждую ос, не мешает вынести критичный код в библиотеку (с + asm) и вызывать уже оттуда.

        Fixed.


  1. Siemargl
    12.01.2019 20:29
    #19606722

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

    дНет будет иметь «большое преимущество перед C++», когда его хоть как то догонит =)
    См и тут выше пример с memcmp, который даже с маршаллингом и без инлайна выигрывает вдвое-втрое.

    В качестве пруфа предоставлю возможность транслировать код из статьи на С++ и проверить самостоятельно.


    1. T-D-K
      12.01.2019 21:02
      #19606792
      +1

      Я считаю, что основной фактор в большой разнице в скорости memcmp и моего кода на C# в том, что memcmp писали умные люди с кучей опыта, а код на C# писал я.


      1. 0x1000000
        12.01.2019 21:40
        #19606880

        Может memcmp тоже SIMD внутри использует. Что-то уж больно быстр он.


        1. T-D-K
          12.01.2019 22:26
          #19606974

          Вот декмпилированный код memcmp, который используется в моих тестах: pastebin.com/bbPqQD1N
          Там только проверка на передаваемый размер, в общем случае сравнение идёт по 8 байт, объединённых в 4 группы.
          Вот ассемблерный код, который генерит JIT для Intrinsics: pastebin.com/u77KXa5r
          Он страшный, но я хз как его улучшить.
          Тесты все ходят, в них я уверен, так что memcmp просто написан лучше, работает напрямую с памятью и мой код скорее всего где-то промахивается в кэше.


          1. ignorance
            13.01.2019 14:35
            #19608192
            +1

            Посмотрел код pastebin.com/u77KXa5r
            Очень странно.
            vmovdqu ymm0,ymmword ptr [rax] — загружаем 256 байт массива ArrayA в регистр ymm0
            vmovupd ymmword ptr [rbp-0B0h],ymm0 — выгружаем его обратно в память
            …
            vmovdqu ymm0,ymmword ptr [rax] — загружаем 256 байт массива ArrayB в регистр ymm0
            vmovupd ymmword ptr [rbp-70h],ymm0 — выгружаем его обратно в память
            vmovupd ymm0,ymmword ptr [rbp-0B0h] — загружаем ранее выгруженный ArrayA в регистр ymm0
            vpcmpeqb ymm0,ymm0,ymmword ptr [rbp-70h] — сравниваем ArrayA (ymm0) и ArrayB (который в памяти), результат заносим в ymm0

            Это не Debug, часом? Не вижу других причин для использования единственного регистра ymm0


            1. T-D-K
              13.01.2019 14:40
              #19608200

              Это не Debug точно, т.к. этот asm код я получал через BenchmarkDotNet, а он отказывается работать в Debug. Данные гоняются туда-сюда из регистров в стэк и обратно как мне кажется из-за локальных переменных.
              Мне тоже этот момент вчера не понравился и я переписал сравнение без локальных переменных:

              byte* ptrA1 = ptrA + i;
byte* ptrB1 = ptrB + i;
if (Avx2.MoveMask(Avx2.CompareEqual(Avx2.LoadVector256(ptrA1), Avx2.LoadVector256(ptrB1))) != equalsMask) {
    return false;
}

              И получилось уже такое:
              00007ff9`17612cfa 4863c0 movsxd rax,eax
              00007ff9`17612cfd 480345d0 add rax,qword ptr [rbp-30h]
              00007ff9`17612d01 c4e17e6f00 vmovdqu ymm0,ymmword ptr [rax]
              00007ff9`17612d06 488b45b0 mov rax,qword ptr [rbp-50h]
              00007ff9`17612d0a c4e17d7400 vpcmpeqb ymm0,ymm0,ymmword ptr [rax]
              00007ff9`17612d0f c4e17dd7c0 vpmovmskb eax,ymm0
              00007ff9`17612d14 83f8ff cmp eax,0FFFFFFFFh
              вроде смотрится лучше, но больше прироста скорости бенчмарк не показал


              1. ignorance
                13.01.2019 16:33
                #19608420

                Да, загрузка ArrayB вроде уже одной инструкцией. А загрузку ArrayA не покажете?
                Потому что судя по операции сравнения
                vpcmpeqb ymm0,ymm0,ymmword ptr [rax]
                мы опять используем единственный регистр, а ArrayA выгружается в память обратно.
                Видимо, компилятор не может (пока?) оптимизировать операцию с регистрами.
                Забавно, что выгрузка в память в исходном ассемблерном коде идет через операцию vmovupd, предназначенную для работы с double.


                1. T-D-K
                  13.01.2019 16:56
                  #19608482

                  Вот полный asm: pastebin.com/MCDQ7mfr

                  Да, загрузка ArrayB вроде уже одной инструкцией. А загрузку ArrayA не покажете?… ArrayA выгружается в память обратно.


                  вот я тут вас не понял
                  00007ff9`17612cfa 4863c0 movsxd rax,eax
                  00007ff9`17612cfd 480345d0 add rax,qword ptr [rbp-30h]
                  00007ff9`17612d01 c4e17e6f00 vmovdqu ymm0,ymmword ptr [rax]
                  00007ff9`17612d06 488b45b0 mov rax,qword ptr [rbp-50h]
                  00007ff9`17612d0a c4e17d7400 vpcmpeqb ymm0,ymm0,ymmword ptr [rax]
                  00007ff9`17612d0f c4e17dd7c0 vpmovmskb eax,ymm0
                  00007ff9`17612d14 83f8ff cmp eax,0FFFFFFFFh

                  Разве не так получается:
                  • в 17612d01 грузим в ymm0 256 бит из [rax] — часть из arrayA
                  • в 17612d0a используем как второй аргумент часть arrayB из памяти. Не грузим её в отдельный регистр, но это сильно бьёт по скорости? По-моему так лучше.
                  • в 17612d0f грузим маску в eax, потом сравниваем


                  Я надеюсь что компилятор «пока» не может оптимизировать это, т.к. .netcore 3 в preview ещё.


                  1. ignorance
                    13.01.2019 17:15
                    #19608508

                    Да, здесь я неправ.
                    Отстается неясным, почему это не помогло по скорости.


                    1. T-D-K
                      13.01.2019 17:28
                      #19608526

                      После среды у меня будет время свободное вечером и я полностью разберу сравню код memcmp и, которые генерирует JIT, и попытаюсь понять в чём тормоза. Если кто-нибудь не сделает это раньше.


                      1. ignorance
                        13.01.2019 18:09
                        #19608588

                        Посмотрел код memcmp. Основные затраты там в ветке if ( Size >> 5 ). Unrolled цикл, в котором обрабатывается 32 байта четыремя сравнениями int64.
                        В коде JIT, предположу, мешает обвязка.


                  1. ignorance
                    13.01.2019 17:29
                    #19608530
                    +1

                    Возможно, имеет смысл кэшировать ArrayA.Length — vectorSize в локальную переменную. Там в цикле есть обращение
                    call 00007ff9`175eb570 get_ArrayA
                    Подозреваю, для вычисления длины массива на каждой итерации.

                    Отдельно можно попробовать инкремент указателей вместо прибавления счетчика.


    1. dotnetdonik
      12.01.2019 23:51
      #19607156
      +4

      И этот бред кочует из статьи в статью, в.т.ч по Яве, не имея никаких доказательств реального, а не возможного теоретически.

      дНет будет иметь «большое преимущество перед C++», когда его хоть как то догонит =)


      .net векторизация с оптимизациями недавними рантайма уже вполне сопоставим работает с unmanaged кодом, просто в статье этой нет сравнения с C/C++ — вот почитайте как эти же векторы для мандельброта в managed коде сравнивают с различными комбинациях c unmanaged код на C++. В целом он будет работать быстрее чем невекторизированный код на C/C++. Векторизированный нативный код хоть и быстрее, на с# для SIMD задач скейлится отлично и в режиме многопоточности работает быстрее чем однопоточный векторизированный нативный код.

      www.codeproject.com/Articles/1223361/%2FArticles%2F1223361%2FBenchmarking-NET-Core-SIMD-performance-vs-Intel-IS

      Если сопоставить с трудозатратами и временем на разработку такого и кода и использованием высокроуневого АПИ на С# — последний очевидно будет более предпочтительным.


      1. Siemargl
        13.01.2019 09:52
        #19607592

        Я не против того, что дНет дает сопоставимые результаты по сравнению с нативным кодом, что то типа О(1).

        Я против заведомо ложных утверждений, одно из которых я и вынес в цитату.
        Вообще, это один из приемов софистики.


      1. ignorance
        13.01.2019 16:44
        #19608454
        +1

        Соглашусь, что векторизованный .net будет лучше невекторизованного С++ на больших объемах данных. Однако, вот смотрите, чем мы занимаемся в ветке комментариев выше — смотрим результат компиляции в asm. Т.е. чтобы писать эффективный код, все равно придется спускаться по абстракциям. И то, что нам приходится прибегать к unsafe — не так уж сильно отличается от С++ по безопасности и усилиям на отладку.
        В этой связи не проще ли выносить узкие части на С++? Компилятор (MS) достаточно умен, чтобы разрулить регистры, и можно достичь неплохой производительности, даже не прибегая к чтению руководств от Intel и анализа показателей latency для инструкций.


    1. Nagg
      13.01.2019 00:39
      #19607242
      +1

      С++ может компилироваться на клиенте через llvm jit и как дотнет/ява оптимизироваться под конкретное железо но в целом к плюсам нужные ровные руки (чуть изменил и хоп — автовекторизация отвалилась) и много терпения для ожидания компиляции -_-


      1. dotnetdonik
        13.01.2019 00:55
        #19607264
        +1

        В случае .net jit это только малая часть от данных результатов. Понятное дело, что если векторные оптимизации сами по себе бы не дали таких результатов в managed языке. В целом все развивается вокруг идеи low alloc типов и апи, что не аллоцируют. И высокоуровневое апи для работы с ними, что не требуют писать unmanaged код. Поэтому кроме нормальной поддержки SIMD у них еще большинство апи работают через memory pooling с буферами, что не создают GC pressure со стеком(работать с которым теперь, к слову, так же можно не прибегая к unmanaged коду) или native memory — опять же это все скрыто внутри удобных высокоуровневых Апи не требующих писать тон boilerplate кода как в С/C++ — скорее всего они будут иметь какой-то perf penalty но в целом будут работать соизмеримо и выглядеть куда предпочтительней.


        1. Nagg
          13.01.2019 01:07
          #19607286

          Спасибо за разъяснения :D


  1. KvanTTT
    12.01.2019 22:52
    #19607022
    +1

    Ох уж эти запятые! Сначала показалось что LINQ во много раз быстрее наивной реализации. На мой взгляд лучше использовать пробелы в качестве разделителей, либо вообще их не использовать.


    1. T-D-K
      12.01.2019 22:56
      #19607036

      Согласен. С пробелами стало более выразительно.


  1. Nagg
    13.01.2019 00:34
    #19607236
    +2

    Единственная проблема с System.Runtime.Intrinsics — для максимальной эффективности вам придется сильно усложнить код, к примеру прежде чем бегать векторами по циклу надо выравнить данные, вот вам пример "простой" функции на C# для сложения массива чисел https://github.com/dotnet/machinelearning/blob/287bc3e9b84f640e9b75e7b288c2663a536a9863/src/Microsoft.ML.CpuMath/AvxIntrinsics.cs#L988-L1095 ;-)


  1. kovserg
    13.01.2019 11:19
    #19607732

    .NET есть большое преимущество перед C++, т.к. JIT компиляция происходит… При этом программист для написания быстрого кода может оставаться в рамках одного языка и технологий
    Чем python не устраивает и SIMD и CUDA и всё в рамках «одного языка и технологий» и не привязано гвоздями к .NET.
    Как правило перед программистом стоит задача написать быстро, а не «быстрого кода». И для ускорения используются уже готовые оптимизированные библиотеки.

    Тут основная проблема не в наличии векторных инструкций, а в отсутствии возможности упрощения кода, разделения алгоритма, организации представления данных, графа исполнения и оптимизаций. Что приводит к резкому усложнению кода. Попытки справиться с этим можно посмотреть в языке halide-lang.org


    1. Nagg
      13.01.2019 18:49
      #19608692
      +1

      Вы говорите о разных вещах, ни один компилятор ни одного языка (в том числе "быстрый" питон) не сможет автоматически векторизировать сложный код и ВСЕГДА придется скатываться до использования интринсиков прямо в коде


      1. kovserg
        13.01.2019 22:20
        #19609202
        +1

        Вы не поняли. Для написания быстрого кода программисту не надо лезть в дебри разных архитектур. Он просто использует декомпозицию матриц, умножает вектора, решает диф.уравнения, вызывает нейронные сети на фермах видиокарт. Ему нафиг не упало лезть и программировать плисы или копаться в AVX512. Если у вас супер компьютер с 2,397,824 ядрами вы не будете колупаться на C# с такой ерундой.


        1. Nagg
          13.01.2019 22:25
          #19609220
          +1

          Умножение матриц и декомпозицию матриц (что это?) за вас написали на интрисиках. Эти самые интринсики и обозревал автор статьи — они для тех, кто хочет писать инструменты повверх которых такие как вы не будут задумываться о перфомансе. Нет универсального языка, который любую вашу формулу максимально оптимизирует сам


          1. Nagg
            13.01.2019 22:29
            #19609236
            +1

            К примеру, вы можете взять базовые System.Numerics.Matrix4x4 в дотнете и перемножить их просто mat3 = mat1 * mat2; — дотнет сам за вас их векторизует ;-)


          1. kovserg
            14.01.2019 08:18
            #19609992

            Проблема именно в том что архитектуры очень разные, и оптимизировать под каждую конкретно очень дорого и сложно. Поэтому оптимизированные библиотеки предоставляет производитель железа который эти инструкции туда добавил. И как правило он их туда добавляет не просто так, а для улучшения производительности именно этих библиотек.
            software.intel.com/ru-ru/performance-libraries
            developer.nvidia.com/gpu-accelerated-libraries
            developer.amd.com/amd-cpu-libraries
            projectne10.github.io/Ne10
            www.ti.com/processors/digital-signal-processors/libraries/libraries.html
            www.intel.com/content/www/us/en/software/programmable/sdk-for-opencl/overview.html
            github.com/aws/aws-fpga
            www.imgtec.com/developers/neural-network-sdk
            …
            И что бы не писать горы кода на C/C++ перед получением результата их оборачивают в библиотеки для языков типа python, что бы удобно было пользоваться тем кому нужно «ехать, а не шашечки».
            И потом написание оптимизированных алгоритмов вручную это очень сложный и дорогостоящий процесс, требующий анализа огромного количества ограничений.
            Попробуй-те оптимизировать реальную задачу, а не сложение векторов и вы поймёте что наличия доступа к SIMD это только вершина айсберга.


  1. ignorance
    13.01.2019 17:46
    #19608564
    +2

    Код с Veсtors, помимо того, что более читаем и понятен, как мне кажется, лучше соответствует духу .NET. CLR мог бы как раз в зависимости от возможностей целевой машины транслировать его в SSE2/SSE4/AVX/AVX2/AVX-512.


  1. a-tk
    13.01.2019 18:43
    #19608670
    +1

    Про SIMD хорошо в своё время рассказал на DotNext-е Sasha Goldshtein: www.youtube.com/watch?v=WeJ8b3WRSmM
    В этом году был Егор Богатов (см. dotnext-moscow.ru ) с докладом про перфоманс-оптимизации, но видео ещё не выложено в публичный доступ.


    1. dmitry_dvm
      13.01.2019 20:56
      #19608960

      Видео Егора есть на сайте дотнекста в трансляции первого дня.
      По теме: почему прямая реализация быстрее linq? Что они там наворотили, что стало медленнее реализации "в лоб"?


      1. ignorance
        13.01.2019 23:42
        #19609418

        Спасибо, познавательно.

        Кстати, он озвучил одну из проблем intrinsics avx в .net — jit вставляет sse-инструкции vzeroupper, а смешение AVX и SSE кода, насколько я помню, может ухудшить производительность.