Работа с векторами с шарп

Вашему вниманию предлагается небольшой обзор возможностей векторизации алгоритмов в .NET Framework и .NETCORE. Цель статьи познакомить с этими приёмами тех, кто их вообще не знал и показать, что .NET не сильно отстаёт от «настоящих, компилируемых» языков для нативной
разработки.

Я только начинаю изучать приёмы векторизации, так что если кто из сообщества укажет мне на явные косяк, или предложит улучшенные версии описанных ниже алгоритмов, то буду дико рад.

Видео:Программирование на С++. Урок 70. ВекторСкачать

Немного истории

В .NET SIMD впервые появился в 2015 году с выходом .NET Framework 4.6. Тогда были добавлены типы Matrix3x2, Matrix4x4, Plane, Quaternion, Vector2, Vector3 и Vector4, которые позволили прозводить векторизированные вычисления. Позже был добавлен тип Vector , который предоставил больше возможностей для векторизации алгоритмов. Но многие программисты всё равно были недовольны, т.к. вышеописанные типы ограничивали поток мыслей программиста и не давали возможности использовать полную мощь SIMD-инструкций современных процессоров. Уже в наше время, в .NET Core 3.0 Preview появилось пространство имён System.Runtime.Intrinsics, которое предоставляет гораздо большую свободу в выборе инструкций. Чтобы получить наилучшие результаты в скорости надо использовать RyuJit и нужно либо собирать под x64, либо отключить Prefer 32-bit и собирать под AnyCPU. Все бенчмарки я запускал на компьютере с процессором Intel Core i7-6700 CPU 3.40GHz (Skylake).

Видео:vector | Библиотека стандартных шаблонов (stl) | Уроки | C++ | #1Скачать

Суммируем элементы массива

Я решил начать с классической задачи, которую часто пишут первой, когда речь заходит про векторизацию. Это задача нахождения суммы элементов массива. Напишем четыре реализации этой задачи, будем суммировать элементы массива Array:

С использованием LINQ

С использованием векторов из System.Numerics:

С использованием кода из пространства System.Runtime.Intrinsics:

Я запустил бенчмарк на эти 4 метода у себя на компьютере и получил такой результат:

Видно, что решения с Vectors и Intrinsics очень сильно выигрывают в скорости по сравнению с очевидным решением и с LINQ. Теперь надо разобраться что происходит в этих двух методах.

Рассмотрим подробнее метод Vectors:

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

То можно увидеть, что он очень похож на Vectors за некоторым исключением:

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

Видео:Векторы и Манипуляции с ними, Vector3 - Unity урокиСкачать

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

Надо сравнить два массива байт. Собственно это та задача, из-за которой я начал изучать SIMD в .NET. Напишем опять несколько методов для бенчмарка, будем сравнивать два массива: ArrayA и ArrayB:

Самое очевидное решение:

Решение через LINQ:

Решение через функцию MemCmp:

С использованием векторов из System.Numerics:

С использованием Intrinsics:

Результат бэнчмарка на моём компьютере:

Весь код этих методов, думаю, понятен, за исключением двух строк в Intrinsics:

В первой два вектора сравниваются на равенство и результат сохраняется в вектор 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 = , а vb = ;
• Тогда areEqual будет равен ;
• Метод MoveMask вернёт 10011100b, который нужно будет сравнивать с маской 11111111b, т.к. эти маски неравны, то выходит, что и векторы va и vb неравны.

Видео:векторы С++Скачать

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

Иногда требуется посчитать сколько раз конкретный элемент встречается в коллекции, например, интов, этот алгоритм тоже можно ускорить. Напишем несколько методов для сравнения, будем искать в массиве Array элемент Item.

с использованием LINQ:

с использованием векторов из System.Numerics.Vectors:

С использованием Intrinsics:

Результат бенчмарка на моём компьютере:

Методы Vectors и Intrinsics полностью совпадают в логике, отличия только в реализации конкретных операций. Идея в целом такая:

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

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

Видео:ОПЕРАТОРЫ. АРИФМЕТИЧЕСКИЕ ОПЕРАЦИИ С ЧИСЛАМИ В C# | C# ОТ НОВИЧКА К ПРОФЕССИОНАЛУ | Урок # 8Скачать

Заключение

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

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

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

Видео:artcam работа с векторамиСкачать

Как создать вектор в С#

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

Вероятно, вы хотите использовать общий List класс, как в List .

Скажем, у вас есть имена ваших серверов в строке значений, разделенных запятыми. Затем вы можете использовать метод расширения Split и ToList() (в IEnumerable), чтобы преобразовать его в список с динамическим размером.

Или, если вы проверяете их по одному с помощью другого метода.

Видео:Самопересекающиеся вектора в ArtCam. Как их победить?Скачать

Векторы в C++: для начинающих

Всем привет! До этого дня мы использовали чистые массивы. Чистые — это значит простые массивы, не имеющие у себя в багаже различных функций. В этом уроке мы пройдем нечистые массивы — векторы.

Быстрый переход по статье:

Видео:C# ФУНКЦИИ И МЕТОДЫ | МЕТОД C# ЧТО ЭТО | ФУНКЦИИ C# ПРИМЕР | C# ОТ НОВИЧКА К ПРОФЕССИОНАЛУ | # 35Скачать

Что такое вектор (vector)

Вектор — это структура данных, которая уже является моделью динамического массива.

Давайте вспомним о том, что для создания динамического массива (вручную) нам нужно пользоваться конструктором new и вдобавок указателями. Но в случае с векторами всего этого делать не нужно.
Вообще, по стандарту пользоваться динамическим массивом через конструктор new — не есть правильно. Так как в компьютере могут происходить различные утечки памяти.

Видео:C# 2023 С НУЛЯ ДО ПРОФИ | СЛИВ ЛУЧШЕГО КУРСАСкачать

Как создать вектор (vector) в C++

Сначала для создания вектора нам понадобится подключить библиотеку — , в ней хранится шаблон вектора.

Кстати, сейчас и в будущем мы будем использовать именно шаблон вектора. Например, очередь или стек, не созданные с помощью массива или вектора, тоже являются шаблонными.

Далее, чтобы объявить вектор, нужно пользоваться конструкцией ниже:

• Вначале пишем слово vector .
• Далее в угольных скобках указываем тип, которым будем заполнять ячейки.
• И в самом конце указываем имя вектора.

В примере выше мы создали вектор строк.

Кстати, заполнить вектор можно еще при инициализации (другие способы мы пройдем позже — в методах вектора). Делается это также просто, как и в массивах. Вот так:

После имени вектора ставим знак равенства и скобки, в которых через пробел указываем значение элементов.

Такой способ инициализации можно использовать только в C++!

Так, чтобы заполнить вектор строками, нам нужно использовать кавычки — «строка» .

Второй способ обратиться к ячейке

Мы знаем, что в векторе для обращения к ячейке используются индексы. Обычно мы их используем совместно с квадратными скобками [] .

Но в C++ есть еще один способ это сделать благодаря функции — at(). В скобках мы должны указать индекс той ячейки, к которой нужно обратиться.

Вот как она работает на практике:

Давайте запустим эту программу:

Как указать количество ячеек для вектора

Указывать размер вектора можно по-разному. Можно это сделать еще при его инициализации, а можно хоть в самом конце программы. Вот, например, способ указать длину вектора на старте:

Так в круглых скобках () после имени вектора указываем первоначальную длину. А вот второй способ:

Первая строчка нам уже знакома. А вот во второй присутствует незнакомое слово — reserve , это функция, с помощью которой мы говорим компилятору, какое количество ячеек нам нужно использовать.

Вы можете задать логичный вопрос:»А в чем разница?». Давайте создадим два вектора и по-разному укажем их количество ячеек.

Как видим, в первом случае мы вывели три нуля, а во втором: 17, 0, 0.

Все потому, что при использовании первого способа все ячейки автоматически заполнились нулями.

При объявлении чего-либо (массива, вектора, переменной и т.д) мы выделяем определенное количество ячеек памяти, в которых уже хранится ненужный для ПК мусор. В нашем случае этим мусором являются числа.

Поэтому, когда мы вывели второй вектор, в нем уже находились какие-то рандомные числа — 17, 0, 0. Обычно они намного больше. Можете кстати попробовать создать переменную и вывести ее значение.

Нужно помнить! При использовании второго способа есть некоторый плюс — по времени. Так как для первого способа компилятор тратит время, чтобы заполнить все ячейки нулями.

Видео:Работа с массивами. Вектор столбцы и вектор строки 1. Урок 7Скачать

Как сравнить два вектора

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

Вектор снова на шаг впереди! Чтобы нам сравнить два вектора, потребуется применить всего лишь оператор ветвления if.

🔥 Видео

Программирование на С++. Урок 71. Пример работы с вектором. Двумерный вектор.Скачать

#11. Произведение матриц и векторов, элементы линейной алгебры | NumPy урокиСкачать

АртКам| работа с векторамиСкачать

C# - Массивы. Уроки для маленьких и тупых #7.Скачать

#7. Реализация динамического массива на С++ с помощью std::vector | Структуры данныхСкачать

Массив объектов класса. Динамический. Статический. Создание Особенности. ООП C++ Для начинающих #96Скачать

C# .NET Windows Form | СОЗДАЁМ PAINT НА C#Скачать