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

    Вашему вниманию предлагается небольшой обзор возможностей векторизации алгоритмов в .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
    Share post
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 50

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

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


      А вообще c# это не производительность.
        0
        T IEnumerable.Sum() возвращает тот же тип, что и в коллекции. Aggregate позволяет этого избежать, чтобы не получить переполнения.
          –1
          Хорошее замечание, правда в таком случае мы кастим весь массив, что еще сильнее бьет по производительности
            0

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

              +1
              Ваш код выбросит исключение, потому что внутри перед кастом элементы сначала приводятся к object. В данном случае можно заменить на arr.Select(i => (long)i).Sum();
                0
                Поддерживаю. Эта классика есть в Clr via C#. Частая проблема боксинга.
                int intNumber = 10;
                object o = intNumber;
                long longNumber = (long) o;
                

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

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


                  var arr = new []{ 5, 8, 9 };
                  var sum = arr.Sum();
                    0
                    Вот код 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; и будет падение.
                      0

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

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

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

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

                  Fixed.
                    0
                    Теперь разберем по пунктам. По факту сейчас в продакшене существует примерно следующая система:
                    64bit
                    Windows, RH, Debian, Ubuntu
                    Intel Xeon
                    GPU Nvidia

                    Следующее утверждение. SIMD как правило используются в библиотеках, которые отлаживают годами, зачастую они и компилируются специальным компилятором.
                    Пытаться их переписать на C# это безумная утопия. А вот написать враппер или даже вызвать через exec. Вполне себе нормальное решение.

                    В итоге получаем:
                    1. Чистый красивый код на C#
                    2. «Вылизанный» низкоуровневый код на 2 платформы (amd64 Linux static, amd64 Windows static)

                    Кстати встречный вопрос а какой класс задач вы предлагаете решать на C# с помощью SIMD?

                    Только просьба без фанатизма, вспоминайте что ML, CV и прочее значительно легче решить на GPU
                      +3
                      Кстати встречный вопрос а какой класс задач вы предлагаете решать на C# с помощью SIMD?

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

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

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

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

                      0
                      Вот декмпилированный код memcmp, который используется в моих тестах: pastebin.com/bbPqQD1N
                      Там только проверка на передаваемый размер, в общем случае сравнение идёт по 8 байт, объединённых в 4 группы.
                      Вот ассемблерный код, который генерит JIT для Intrinsics: pastebin.com/u77KXa5r
                      Он страшный, но я хз как его улучшить.
                      Тесты все ходят, в них я уверен, так что memcmp просто написан лучше, работает напрямую с памятью и мой код скорее всего где-то промахивается в кэше.
                        +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
                          Это не 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
                          вроде смотрится лучше, но больше прироста скорости бенчмарк не показал
                            0
                            Да, загрузка ArrayB вроде уже одной инструкцией. А загрузку ArrayA не покажете?
                            Потому что судя по операции сравнения
                            vpcmpeqb ymm0,ymm0,ymmword ptr [rax]
                            мы опять используем единственный регистр, а ArrayA выгружается в память обратно.
                            Видимо, компилятор не может (пока?) оптимизировать операцию с регистрами.
                            Забавно, что выгрузка в память в исходном ассемблерном коде идет через операцию vmovupd, предназначенную для работы с double.
                              0
                              Вот полный 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 ещё.
                                0
                                Да, здесь я неправ.
                                Отстается неясным, почему это не помогло по скорости.
                                  0
                                  После среды у меня будет время свободное вечером и я полностью разберу сравню код memcmp и, которые генерирует JIT, и попытаюсь понять в чём тормоза. Если кто-нибудь не сделает это раньше.
                                    0
                                    Посмотрел код memcmp. Основные затраты там в ветке if ( Size >> 5 ). Unrolled цикл, в котором обрабатывается 32 байта четыремя сравнениями int64.
                                    В коде JIT, предположу, мешает обвязка.
                                      +2
                                      С опозданием, но всё-таки опишу результаты попыток ускорить:
                                      pastebin.com/JB4PvusV — код метода сравнения
                                      pastebin.com/rJHH0GQn — лог BenchmarkDotNet
                                      pastebin.com/LwDrtnmD — asm код.
                                      Использовал NetCore 3.0 Preview 2.0
                                      Тело цикла уменьшилось на 4 инструкции: выпилились вызовы функций + я по вашему совету закэшировал ArrayA.Length — vectorSize.
                                      На неопределённое время точно прекращаю дальнейшие попытки, т.к. свободного времени почти нет.
                                        +1
                                        Наконец-то посмотрел, спасибо.
                                        Вроде с точки зрения векторизации все правильно.
                                        Но последовательность инструкций
                                        mov dword ptr [rbp-14h],eax
                                        mov eax,dword ptr [rbp-14h]
                                        удивляет все равно (в главном цикле переменная i загружается в регистр аж 4 раза). Такое впечатление, что IL транслируется в машинный код один к одному, без оптимизации.
                                        Возможно, проще сделать цикл отдельно на long вместо разворачивания. По производительности там особо разницы не будет (сравниваются не более 24 байт), а код в asm сократится и ветвлений будет меньше.

                                        С точки зрения измерений, думаю, 10000 дает слишком малое суммарное время — порядка сотен наносекунд, чтобы сравнивать Intrinsic и MemCmp. На 100000 MemCmp неожиданно обгоняет, а на 1000000 получаем слишком большой разброс результатов (StdDev сопоставимо с Mean), чтобы судить однозначно.
                                        0
                                        Я пробовал ещё ксорить векторы и потом через _mm256_testz_si256 сравнивать с вектором, заполенным единицами. Существенного прироста в скорости не было.
                                    +1
                                    Возможно, имеет смысл кэшировать ArrayA.Length — vectorSize в локальную переменную. Там в цикле есть обращение
                                    call 00007ff9`175eb570 get_ArrayA
                                    Подозреваю, для вычисления длины массива на каждой итерации.

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

                        дНет будет иметь «большое преимущество перед 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

                        Если сопоставить с трудозатратами и временем на разработку такого и кода и использованием высокроуневого АПИ на С# — последний очевидно будет более предпочтительным.
                          –5
                          Я не против того, что дНет дает сопоставимые результаты по сравнению с нативным кодом, что то типа О(1).

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

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

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

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

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

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

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

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

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

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

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

                                        +1

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

                                          0
                                          Проблема именно в том что архитектуры очень разные, и оптимизировать под каждую конкретно очень дорого и сложно. Поэтому оптимизированные библиотеки предоставляет производитель железа который эти инструкции туда добавил. И как правило он их туда добавляет не просто так, а для улучшения производительности именно этих библиотек.
                                          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 это только вершина айсберга.
                                    +2
                                    Код с Veсtors, помимо того, что более читаем и понятен, как мне кажется, лучше соответствует духу .NET. CLR мог бы как раз в зависимости от возможностей целевой машины транслировать его в SSE2/SSE4/AVX/AVX2/AVX-512.
                                      +1
                                      Про SIMD хорошо в своё время рассказал на DotNext-е Sasha Goldshtein: www.youtube.com/watch?v=WeJ8b3WRSmM
                                      В этом году был Егор Богатов (см. dotnext-moscow.ru ) с докладом про перфоманс-оптимизации, но видео ещё не выложено в публичный доступ.
                                        0

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

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

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

                                            Незначительно, но лучше перебдеть, чем оставить мусор в регистрах ;-)

                                            0

                                            Плата за универсальность

                                        Only users with full accounts can post comments. Log in, please.