Суммируются. Циклом, в 4096 сложений, даже без разворачивания цикла. Никакой векторизации.
матрицы тоже не паралелятся прям
Матрицы как раз параллелятся элементарно. У вас n^2 выходных значений, каждое из которых считается независимо от всех остальных. Поэтому их можно считать параллельно. И вместо N^3 сложений у вас получается N^3/4 четверок сложений - вот и ускорение в 4 раза.
sse вот еще ссылка тип операции в разделе Трудности автовекторизации a[i]=b[i]+c[i]
Нет, проблема с пересекающимеся данными тут не применима, ибо я взял ваш пример с двумя глобальными массивами. Даже с допиской #pragma GCC ivdep ничего не меняется.
пример значит в симд можно придти к такому же результату,
Да, симд-ом можно всегда получить такой же ответ. Но иногда, как в примере с префиксными суммами он получается недоутилизорован. Кажая операция по факту вместо четырех значений работает только с одним. Никакого прироста скорости это не дает.
Вы понимаете, что Simd ускоряет вычисления не потому, что вот эти xmm регистры такие волшебные, а потому что там происходит по 4 операции сразу?
Ну блин, вы почитайте ваш ассемблерный выход-то. Там нет никакой векторизации вычислений, ровно как я и говорил. Посчитайте, сколько у вас там операций vaddss. 15. Сколько операций сложения в исходном коде? 15. Сколько их выполнено параллельно через Single Instruction Multiple Data? Ровно 0.
Хmm регистры используются при сложении, просто потому что это float. Ну, удобнее компилятору использовать эти регистры вместо вещественного "сопроцессора" (он не сопроцессор уже давно, но концепция стека там осталась). Ну не завезли в X86 вещественных скалярных регистров.
Чуть проще понять, что там происходит, если сделать массив из 4 элементов: godbolt.
Смотрите,там 4 операции загрузки данных в регистры. Каждый из 4-рех исходных элементов попадает в свой отдельный регистр (movss). Потом там 3 операции сложения (addss). Ровно столько, сколько в исходном коде. Только запись в память оптимизирована одной выгрузкой, это да.
Поменяйте float на int, компилятор будет для счета использовать скалярные регистры, ибо никакой векторизации тут нет. Запись последовательных вычисленных значений одной операцией будет, это да, но вычисления не векторизованы - все те же 3 операции сложения.
Так что можете не пытаться сложения векторизовывать.
Примеры чего? Ускорения? Так я говорю, что оно не возможно. И вы сами говорите, что у вас замедление.
префиксные суммы такого же вида почт
Только тем, что и там и там есть сложение. В перфиксных суммах результат каждого сложения зависит от предыдущего результата. В статье же - нет (кроме случая пересекающихся массивов. Там тоже есть зависимость и поэтому компилятор отказывается это векторизовывать. О чем и статья, собственно).
Вы что, пытаетесь через simd ускорить подсчет префиксных сумм? Не получится. Потому что каждое следующее значение зависит от предыдущего. Вы не можете их вычислить быстрее чем за n разных операций. Навешивая тут сверху симд, вы все только замедляете. У вас все те же n операций, но теперь тяжелее. симд ускаряет за счет того, что вы далете в 4-8-16 раз меньше операций, когда их можно выполнять параллельно. Если у вас зависимость по данным, то операции нельзя распараллелить.
Не обращайте внимания. Этот комментатор недавно открыл для себя SIMD, написал какой-то пример с матрицами, так обрадовался, что теперь везде пытается свести тему на это, как студент из анекдота, выучивший только билет про блох (вот если бы у рыб была шерсть, то там бы были блохи, а блохи...). При этом у человека огромные проблемы с выражением своих мыслей. В каждой теме только об этом и пишет, при чем почти всегда вообще не в тему.
Как вам выше уже сказали - это называется Bucket sort.
На практике тут получить хорошее ускорение далеко не всегда можно, ибо вам надо подобрать хорошую функцию ранжирования объектов. Для строк это особенно сложно.
Конкретно ваши сгенерированные строки примерно равномерно распределены по возможноым коротким префиксам - нескольким первым символам. Так что тут ваш прием срабатывает хорошо. В этом случае можно еще отлично работает radix sort, что тоже будет O(N).
С интами надо использовать sse а не avx. Используйте другие интринсики и все скомпилируется.
убрали частный случай не сказав о нюансах а потом заминусили то что вы убрали, потомучто он является по правилам самого симда нюансом
Вы про исправление вашего примера? Это не ньюанс симда, а ваша ошибка. Я вам даже ссылку на ассемблерный выход компилятора выдал, и он ваши перетасовки регистров убрал сам, потому что они не нужны. Вы считаете, что в компиляторе тоже ошибка, а его создатели, в отличии от вас, не понимают ньюансов AVX?
как вы собираетесь хотябы в 3д
Я не собираюсь! 3d - это ваши тараканы в вашей голове. А вне 3д оно отлично применяется и с интами. Я вам кучу примеров привел выше.
я потому и спросил вы предпологаете хранить отдельно индексы
Что за индексы? Вы опять на своей волне, это у вас в 3d из интов только какие-то индексы? Нет, интами могут быть цвета пикселей, количество золота у персонажей или что угодно еще.
За сим я заявляю, что отныне буду вас игнорировать и молча минусить, ибо с вами невозможно разговаривать. Вы вообще не читаете, что вам пишут, и пишите каждый раз что-то вообще никак логически не связанное с чем либо, на что вы отвечаете, или даже вашими предыдущими словами.
Вы упоминули префиксы. Вы не знаете что это такое, или проверяете что я термин знаю? Это часть массива, если отбросить сколько-то последних элементов. Дерево фенвика позволяет быстро считать сумму элементов любого префикса, а так же изменять любой элемент.
например просто дерево
Что значит "просто дерево"? Дерево - это граф без циклов, само по себе оно для структур данных бесполезно почти всегда. Надо на него еще какие-то свойства навесить (как в дереве фенвика, каждая вершина хранит сумму какого-то подмножества элементов массива. Или в балансированных деревьях поиска значения в вершинах упорядочены и высота дерева ограничена).
в обоих статьях предлагается хранить всё на стеке
Нет, не предлагается. Там везде структура данных в куче. Но это вообще не важно. Даже с точки зрения векторизации. Стек/куча - все та же оперативная память. Только на стеке дешевле ее выделять.
примеры с интами, вы вот где собрались инты применять
Структуры эти используются не только в 3d, а где угодно, и чаще всего работают с интами. Вообще, про 3d - это у вас в голове контекст, никто тут и в статьях его не упоминал. Но если вы хотите примеров: индексы в базах данных, сжатие данных, а так же изображений и видео в частности. Все цвета пикселей - целые числа обычно. Обработка сигналов - аудио данные все обычно в виде интов. В том же геймдеве, если расширить кругозор от 3д графики: почти вся логика работает с int-ами (здоровье, координаты, урон, характеристики предметов и их количество...). Пока не могу придумать, где там использовать дерево фенвика, но сбалансированные деревья поиска будут использоваться повсеместно.
Вы вообще о чем? Какие индексы? Какой стек? При чем тут флоат и инты? Исправления? Вы про ту маленькую заметку о выкидывании перетасовки 128-бит местами в примере суммирования?
Присоединяюсь к комментатору выше. Ваши сегодняшние сообщения вообще не понятны. Кажется, вы что-то заметили в алгоритмике, что-то свое на основе этого придумали, и делитесь своими идеями с общественностью, но вы не указали к чему конкретно ваши комментарии относятся. Я же не вижу, что именно вы там прочитали. Потом, ваш код, вываленный вот так, без объяснения хотя бы какую задачу он решает - не несет никакого смысла.
Вам стоит перед отправкой ваших комментариев остановиться и задуматься, а весь ли контекст есть в треде, в который вы отвечаете. И если нет - включить его в ваш комментарий.
А вот это реально круто, спасибо. Действительно, если использовать не бинарные деревья, то там постоянно надо обрабатывать сразу всех детей вершины и это можно векторизовать.
Но только если вы не начальник. С этими поговорить, выслушать вон тех, пообедать вон с теми бизнес-партнерами, встретится с политиками, просмотреть презентацию и сказать свое веское слово, сесть на бизнес джет и поелететь на конференцию. Этим можно легко с утра до ночи заниматься без потери производительности.
Плюс, если учесть что вам платят за час работы десятки тысяч долларов, то можно и постараться.
Наводящий вопрос: как расшифровывается абревиатура SIMD, знаете?
Понятия не имею о чем вы (в прочем, это частое явление с вашими комментариями, и не только у меня).
Я не про эту эту статью, я про код этого комментатора.
На каком скрине?
Суммируются. Циклом, в 4096 сложений, даже без разворачивания цикла. Никакой векторизации.
Матрицы как раз параллелятся элементарно. У вас n^2 выходных значений, каждое из которых считается независимо от всех остальных. Поэтому их можно считать параллельно. И вместо N^3 сложений у вас получается N^3/4 четверок сложений - вот и ускорение в 4 раза.
Нет, проблема с пересекающимеся данными тут не применима, ибо я взял ваш пример с двумя глобальными массивами. Даже с допиской
#pragma GCC ivdepничего не меняется.Да, симд-ом можно всегда получить такой же ответ. Но иногда, как в примере с префиксными суммами он получается недоутилизорован. Кажая операция по факту вместо четырех значений работает только с одним. Никакого прироста скорости это не дает.
Вы понимаете, что Simd ускоряет вычисления не потому, что вот эти xmm регистры такие волшебные, а потому что там происходит по 4 операции сразу?
Ну блин, вы почитайте ваш ассемблерный выход-то. Там нет никакой векторизации вычислений, ровно как я и говорил. Посчитайте, сколько у вас там операций vaddss. 15. Сколько операций сложения в исходном коде? 15. Сколько их выполнено параллельно через Single Instruction Multiple Data? Ровно 0.
Хmm регистры используются при сложении, просто потому что это float. Ну, удобнее компилятору использовать эти регистры вместо вещественного "сопроцессора" (он не сопроцессор уже давно, но концепция стека там осталась). Ну не завезли в X86 вещественных скалярных регистров.
Чуть проще понять, что там происходит, если сделать массив из 4 элементов: godbolt.
Смотрите,там 4 операции загрузки данных в регистры. Каждый из 4-рех исходных элементов попадает в свой отдельный регистр (movss). Потом там 3 операции сложения (addss). Ровно столько, сколько в исходном коде. Только запись в память оптимизирована одной выгрузкой, это да.
Поменяйте float на int, компилятор будет для счета использовать скалярные регистры, ибо никакой векторизации тут нет. Запись последовательных вычисленных значений одной операцией будет, это да, но вычисления не векторизованы - все те же 3 операции сложения.
Так что можете не пытаться сложения векторизовывать.
Дайте ссылочку на godbolt с исходным кодом и я принесу публичные извинения.
Примеры чего? Ускорения? Так я говорю, что оно не возможно. И вы сами говорите, что у вас замедление.
Только тем, что и там и там есть сложение. В перфиксных суммах результат каждого сложения зависит от предыдущего результата. В статье же - нет (кроме случая пересекающихся массивов. Там тоже есть зависимость и поэтому компилятор отказывается это векторизовывать. О чем и статья, собственно).
Вы что, пытаетесь через simd ускорить подсчет префиксных сумм? Не получится. Потому что каждое следующее значение зависит от предыдущего. Вы не можете их вычислить быстрее чем за n разных операций. Навешивая тут сверху симд, вы все только замедляете. У вас все те же n операций, но теперь тяжелее. симд ускаряет за счет того, что вы далете в 4-8-16 раз меньше операций, когда их можно выполнять параллельно. Если у вас зависимость по данным, то операции нельзя распараллелить.
P.s. Как префиксные суммы связанны со статьей?
Не обращайте внимания. Этот комментатор недавно открыл для себя SIMD, написал какой-то пример с матрицами, так обрадовался, что теперь везде пытается свести тему на это, как студент из анекдота, выучивший только билет про блох (вот если бы у рыб была шерсть, то там бы были блохи, а блохи...). При этом у человека огромные проблемы с выражением своих мыслей. В каждой теме только об этом и пишет, при чем почти всегда вообще не в тему.
Да, отличная идея: без инженеров все косяки быстро наладятся, баги в драйверах не появятся и репутация с долей рынка восстановятся!
Вообще, надо всех увлолить а еще производство до 0 сократить - вот затрат вообще нет.
Так классы - это и есть словарь с функциями (virtual table). Просто удобно реализовано на уровне языка.
Как вам выше уже сказали - это называется Bucket sort.
На практике тут получить хорошее ускорение далеко не всегда можно, ибо вам надо подобрать хорошую функцию ранжирования объектов. Для строк это особенно сложно.
Конкретно ваши сгенерированные строки примерно равномерно распределены по возможноым коротким префиксам - нескольким первым символам. Так что тут ваш прием срабатывает хорошо. В этом случае можно еще отлично работает radix sort, что тоже будет O(N).
С интами надо использовать sse а не avx. Используйте другие интринсики и все скомпилируется.
Вы про исправление вашего примера? Это не ньюанс симда, а ваша ошибка. Я вам даже ссылку на ассемблерный выход компилятора выдал, и он ваши перетасовки регистров убрал сам, потому что они не нужны. Вы считаете, что в компиляторе тоже ошибка, а его создатели, в отличии от вас, не понимают ньюансов AVX?
Я не собираюсь! 3d - это ваши тараканы в вашей голове. А вне 3д оно отлично применяется и с интами. Я вам кучу примеров привел выше.
Что за индексы? Вы опять на своей волне, это у вас в 3d из интов только какие-то индексы? Нет, интами могут быть цвета пикселей, количество золота у персонажей или что угодно еще.
За сим я заявляю, что отныне буду вас игнорировать и молча минусить, ибо с вами невозможно разговаривать. Вы вообще не читаете, что вам пишут, и пишите каждый раз что-то вообще никак логически не связанное с чем либо, на что вы отвечаете, или даже вашими предыдущими словами.
Вы упоминули префиксы. Вы не знаете что это такое, или проверяете что я термин знаю? Это часть массива, если отбросить сколько-то последних элементов. Дерево фенвика позволяет быстро считать сумму элементов любого префикса, а так же изменять любой элемент.
Что значит "просто дерево"? Дерево - это граф без циклов, само по себе оно для структур данных бесполезно почти всегда. Надо на него еще какие-то свойства навесить (как в дереве фенвика, каждая вершина хранит сумму какого-то подмножества элементов массива. Или в балансированных деревьях поиска значения в вершинах упорядочены и высота дерева ограничена).
Нет, не предлагается. Там везде структура данных в куче. Но это вообще не важно. Даже с точки зрения векторизации. Стек/куча - все та же оперативная память. Только на стеке дешевле ее выделять.
Структуры эти используются не только в 3d, а где угодно, и чаще всего работают с интами. Вообще, про 3d - это у вас в голове контекст, никто тут и в статьях его не упоминал. Но если вы хотите примеров: индексы в базах данных, сжатие данных, а так же изображений и видео в частности. Все цвета пикселей - целые числа обычно. Обработка сигналов - аудио данные все обычно в виде интов. В том же геймдеве, если расширить кругозор от 3д графики: почти вся логика работает с int-ами (здоровье, координаты, урон, характеристики предметов и их количество...). Пока не могу придумать, где там использовать дерево фенвика, но сбалансированные деревья поиска будут использоваться повсеместно.
Вы вообще о чем? Какие индексы? Какой стек? При чем тут флоат и инты? Исправления? Вы про ту маленькую заметку о выкидывании перетасовки 128-бит местами в примере суммирования?
Присоединяюсь к комментатору выше. Ваши сегодняшние сообщения вообще не понятны. Кажется, вы что-то заметили в алгоритмике, что-то свое на основе этого придумали, и делитесь своими идеями с общественностью, но вы не указали к чему конкретно ваши комментарии относятся. Я же не вижу, что именно вы там прочитали. Потом, ваш код, вываленный вот так, без объяснения хотя бы какую задачу он решает - не несет никакого смысла.
Вам стоит перед отправкой ваших комментариев остановиться и задуматься, а весь ли контекст есть в треде, в который вы отвечаете. И если нет - включить его в ваш комментарий.
А вот это реально круто, спасибо. Действительно, если использовать не бинарные деревья, то там постоянно надо обрабатывать сразу всех детей вершины и это можно векторизовать.
Признаю свою неправоту, функциональные языки невероятно сильны.
Но только если вы не начальник. С этими поговорить, выслушать вон тех, пообедать вон с теми бизнес-партнерами, встретится с политиками, просмотреть презентацию и сказать свое веское слово, сесть на бизнес джет и поелететь на конференцию. Этим можно легко с утра до ночи заниматься без потери производительности.
Плюс, если учесть что вам платят за час работы десятки тысяч долларов, то можно и постараться.