Comments 66
Вы в тексте постоянно путаете массивы и списки (которые вообще ни разу не одно и то же). В иммутабельных языках, например, копирование списка — O(1), а массива — O(N)).
Когда прочитал "если вы ищете хорошего джуна - напишите мне в тг", почему-то сразу подумал, что автор себя и предлагает :( А такую статью, наверное, может и ИИ написать :(
https://en.wikipedia.org/wiki/Analysis_of_algorithms может пригодится это
у пермута есть симд, простите, поэтому ссылка выше неизбежно нужна будет
разбиение множества тоже вроде можно в те регистры кинуть
есть пример с деревом фенвика и ускорением в интернете, 1е8 елементов с avx вставляет за 2.4(на моей тачке+латенси например устный счет около 3 секунд с амортизацией и дискретностью 2.4) секунды у автора в той статье написано 9 секунд алгоритм О(логН), а может и O1 вставка же у него в статье о интринсиках (тут я ошибся скорее всего там потомучто вставка в массивы)
тоесть придётся потом еще раз учиться уже с ускорением всем этим алгоритмам, и понять как замерять
В дерево Фенвика не вставляют элементы. Элементов там всегда ровно N. В этом дереве можно элементы менять и оно позволяет считать сумму на отрезках (ну или некоторые другие операции).
Вы ничего не путаете? Как там применять векторные операции я не представляю вообще, ибо там надо взять log(n) определенных ячеек в массиве. Можете найти ссылку?
не путаю есть пример, и там можно применить векторизацию, а вообще там про возведение в степерь итаративно, скорее всего путаю и я выше написал что там массивы
но следом ниже идёт пример с деревом фенвика, так что просто надо понять нужно ли дерево фенвика и попробовать наверно
sse, автор доказал что по дереву фенвика можно пройти комбинаторно, и цикла в ускорении не будет из-за нюанса, как я понял, в любом случае придётся изучать sse, ниже вот пример пришлось понимать, потомучто тема реверса интересна - это пускай и не ассемблер, но всё же
Ну дайте ссылку тогда, пожалуйста.
прикрепил ссылку выше, там пример с автовекторизацией(и небольшой дайджест о инструкциях), и по ссылке информация по дереву, там в статье есть ссылка, конкретно по дереву, а с ссе/avx мы либо автоматической векторизацией пользуемся либо накидываем некоторые места конкретно вставками, проверяя как я понял перед этим поддержку процессором инструкций
А, ну это неинтересно, там куча запросов "параллельно" выполняются. Это-то понятно как векторизовать. Программисту для этого, правда, пришлось поменять два вложенных цикла местами.
так вы определили и я перепроверил определение дерева, это сумма, а дерево это бин индексы соотв задача сужается до разбиения дерева по кеш линии как я понял, соотв у вас кеш будет суммироваться за сколько почти за 1 операцию как я понимаю если напрямую управлять, вообще интересно, конечно
ходить по размеру 256 где 256 это часть дерева наверно так первое о чем подумал, управляя (H,L) наверно
а само дерево в памяти, и по участку просто брать в симд
получится поидее каждый прыжок с новым участком в инструкциях поидее
Вы как-то постоянно на своей волне. Как будто вы вообще не понимаете чужих слов, и ваши слова очень сложно понять. По всем темам ваши комментарии меня очень озадачивают.
я перепроверил определение дерева, это сумма,
Нет, дерево - не сумма. Дерево фенвика - это структура данных, позволяющая быстро считать сумму значений на отрезке и изменять значения. Обычно реализуется в виде массива, где в каждой ячейке хранится сумма определенного множества элементов, которые так хитро подобраны, что для суммы элеменов любого отрезка индексов вида [0, l] вам надо сложить log n ячеек. А при изменении любого элемента - изменить log n ячеек. И эти ячейки можно находить простыми битовыми манипуляциями.
задача сужается до разбиения дерева по кеш линии как я понял
Нет, тут вообще ни при чем кеш.
Дерево в приведенном примере никак не разбивается и никак не меняется.
Там даже комментарий по вашей сслыке есть:
// те же самые циклы фенвика, только вдоль запросов;
В простой реализации вы берете запрос q[i] и для него суммируете log n ячеек внутри функции sum. Но ячейки там по массиву разбросаны и их сумму не векторизовать. В векторизированной версии делается Logn итераций, где для каждого запроса суммируется очередная ячейка. Просто поменяли порядок вычисления, вместо суммы logn значений первого запроса, потом log n второго запроса, делаются все первые слагаемые всех запросов, потом все вторые слогаемые всех запросов.
Разница в том, что тут вычисляемые индексы зависят не от предыдущей итерации, а от итерации log n шагов назад. Поэтому соседние итерации можно считать параллельно.
Работает только в очень странном случае, где у вас очень много заранее известных запросов и нет изменений. В этом случае использовать дерево Фенвика - глупость, лучше подсчитать массив префиксных сумм.
ходить по размеру 256 где 256
Вообще никак ни к чему выше сказанному в комментариях или по вашей ссылке ваш текст не относится. Это какой-то поток мыслей, который я разобрать не могу.
тогда не читайте мои комментарии и не обсуждайте со мной какие-либо темы, вот у вас так и у вас нет, а у меня так как я сказал и я понимаю что я написал, и вы понимаете что вы пишите
я не буду обьяснять что такое кеш и 256 в этих случаях и где и почему прыжки, я вот проверил свою гипотезу покрытия в кеше 1 операцией и у меня сошлось, возьмите тогда 512 там побыстрее будет, вы вольны пользоваться этими регистрами как вздумается или как вам нужно
напомню библиотека даёт ручное управление регистрами, перевороты, и шифты, кеш это L2 или L3 если вы возьмете из памяти невыорвняный участок в симд в той статье тоже сказано, то у вас будет не выровненый участок соответственно будет последствие, соотв надо чтото делать, касательно 1 операции, я не буду настаивать если вы это не видите окэй как говориться
512 [256x2] = [0 .. 32]
тогда не читайте мои комментарии и не обсуждайте со мной какие-либо темы
Если вы не будете получать конструктивных отзывов на ваши комментарии, то так и будете повышать энтропию и полдить мало осмысленные комментарии.
я вам конструктивно и пишу что в фенвике вы будете несмотря на кадр делать 1 операцию, там же есть пример и там 1 операция
это всё укладывается в те регистры
Какой кадр? Какую операцию? Вы про vectorized_fenwick() из статьи?
фрейм счета относительно счетчика - прохода счетчика
с каждым обновлением счетчика будет меняться память
вы извините там всё выходит, я именно эту функцию не буду кидать в симд-исполнении как пример, вы проверьте, там всё получается
тема ускорений косвено связана на контексте ассемблера, то что там в автовекторизации получается это хорошо, но в таких узких местах важнее подход с инстрисинками
Вроде каждое слово имеет смысл, а все вместе в вашем комментарии - вообще не дало мне никакой информации.
Можно начать немного подальше и поподробнее? Что такое фрейм счета? Какой счетчик? Память меняется - потому что в нее что-то пишется, или вы имеете ввиду что адреса меняются?
ну вы минусите очевидное я выше писал [0 .. 31] для 512, [0..15] 256 вот вы подумайте как сделать так чтобы не по байтово(не по 1 числу ходить а по кадру симда выбранного вами) перемножать а сразу строками выровненными и поймёте о чем реч
насчет кадра счетчика и фрейма понаблюдайте за ассемблером и памятью
нет интереса в симд кидать всю память правильно? у нас суть лента(лента конечна но последовательность лент процессору не известны), соотв дальше вот постарайтесь догадаться сами
у меня всё красиво легло в симд покадрово и у вас должно получится
я называю кадром потомучто мы оперируем не 1 числом а лентой чисел
Что значат эти числа? 512 - это, видимо разрядность векторных операций, а [0..31]? Как они относятся к фенвику?
кадра счетчика и фрейма
Кадр - это перевод на русский английского frame. То, что вы два этих термина используете как что-то разное означает, что у вас такая каша в голове.
Фрейм в ассемблере... это вы стэк фрейм имеете ввиду?
Как наблюдая за ассемблером я должен понять, что вы называете "фреймом счета" и какой счетчик вы имеете ввиду? За каким именно ассемблером я должен наблюдать? Ассемблерный код vectorized_fenwick()? Или вы предлагаете почитать мануал по x86-64 архитектуре?
Я вам на каждый ваш комметарий прошу вас объяснить что такое вот такой вот термин в вашем понимании, а вы вываливаете какой-то только вам известно как связанный с этим текст вместо хотя бы ссылки на википедию или какой-то мануал, или простое человеческого "XXX - это сепулька вот в этом вот месте, делающая вот такое вот супельчение"
512 это размер, [0 .. 31 ] количество флоатов, вот такой вот поворот мы пришли к флоатам вобщем, я врятли обьясню, я понял что вы не заметили там ни 1 ленты
vectorized_fenwick() - реч про эту функцию
а вы хотите по 1 числу фенвика обходить?
кадр или фрейм локальный в контексте симда и 1 функции это размер выбранного Симда чтобы не оперировать 1 числом а воспользоваться всей лентой, тоесть всем регистром в расчете
для 1 числа идут операции, а мы можем уложить числа в ленту и оперировать регистровой операцией которая сделает за 1 операцию паралельно 16, например не 1 раз произвести сложение а сразу 16 сложений (размер и действия 16 ти кратные будут локальны в этой функции они будут как бы из мира ассемблера )
я ассемблер смотрю на своей тачке в файле .s или в годболте (gcc/clang)
да предлагается внимательно посмотреть на 2ой цикл
вот такой вот поворот мы пришли к флоатам вобщем, я врятли обьясню, я понял что вы не заметили там ни 1 ленты
Ленты? А вообще, проверьтесь на ADHD, вы скачете с темы на тему и не можете удержать в голове контекст обсуждения.
покажите как вы пользуетесь суммой в регистрах, сразу будет нагляднее, я сразу скажу вам что и как, 1 примера будет достаточно он всё прояснит и вы наверно всё поймёте
упрощу вопрос вы хотите прыгать по 1 числу и считать 1 текущее число, или вы хотите регистрами решать?
Я ничего не хочу. Я вижу код vectorized_fenwick() из вашей ссылки, я отлично понимаю, как он работает, что там векторизуется и почему. Но при этом я вижу, что этот код выполняет сразу много запросов к дереву (массив q там) при этом не выполняя никаких запросов на изменение чисел в дереве между ними.
Поэтому я считаю, что этот пример очень натянутый и неинтересный, ибо вся суть этой структуры данных "дерево фенвика" - уметь выполнять запросы быстро, когда данные часто меняются между запросами. Тут же есть много запросов, но числа, которые вы суммируете, при этом не меняются вообще. В этом случае есть гораздо более быстрые и заточенные под этот случай сутруктуры данных (массив префиксных сумм, например).
повторю вопрос, покажите пожалуйста как вы производите сумму в регистрах, раз вы развернули такую дискуссию, то давайте конструктивнее? извините вы покажете как вы производите сумму в регистрах? в данных подходах решение прыгать по 1 числу или по регистрам имеет ключевой нюанс помимо прочих нюансов
Скрытый текст
#include <stdio.h>
#include <stdlib.h>
#include <immintrin.h>
typedef __attribute__(( aligned(32))) float af32;
__attribute__(( aligned(32))) float a[16]={
2,3,4,5,
6,7,8,9,
0,1,2,3,
4,5,6,7
};
__attribute__(( aligned(32))) float b[16]={
0,1,2,3,
4,5,6,7,
0,1,2,3,
4,5,6,7
};
__attribute__(( aligned(32))) float c[16]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
void testadd4() {
__m256 x = _mm256_load_ps( (a+(0<<2)) );
__m256 y = _mm256_load_ps( (b+(0<<2)) );
__m256 x1 = _mm256_load_ps( (a+(2<<2)) );
__m256 y1 = _mm256_load_ps( (b+(2<<2)) );
__mmask8 mask ={0x0};
__m256 z = _mm256_add_ps(x, y);
__m128 xh=_mm256_extractf128_ps(z,0);
__m128 xl=_mm256_extractf128_ps(z,1);
__m256 x4=_mm256_set_m128(xh,xl);
__m256 z1 = _mm256_add_ps(x1, y1);
__m128 xh1=_mm256_extractf128_ps(z1,0);
__m128 xl1=_mm256_extractf128_ps(z1,1);
__m256 x41=_mm256_set_m128(xh1,xl1);
_mm256_storeu2_m128(&c[0],&c[4],x4);//
_mm256_storeu2_m128(&c[8],&c[12],x41);//
}
это не очевидно? если для вас это не очевидно, то смысл продолжать этот разговор, простите
, раз вы развернули такую дискуссию, то давайте конструктивнее?
Где я развернул такую дискуссию? Приведите цитату, пожалуйста! Я спросил как векторизовался fenwick, вы привели статью, я сказал, что там векторизовано кривое применение fenwick'а - очень искусственный и ненужный случай.
извините вы покажете как вы производите сумму в регистрах?
Я где-то говорил, что я произвожу сумму в регистрах?
код
Вижу вы зачем-то привели тривиальный пример суммирования через интринсики AVX-256. Какое он имеет отношение к обсуждению векторизации дерева фенвика я не понимаю. Ну, кроме того, что дерево фенивика тоже считает какие-то суммы. Только в дереве считаются суммы внутри одного массива и на произвольном куске, а тут вы два массива фиксированной длины складываете. Это же совсем разные случаи.
А еще у вас там небольшой косяк. Вместо использования _mm256_extract_f128_ps и _mm256_set_m128 вам надо лишь поменять местами аргументы у _mm256_storeu2_m128 - там же сначала идет hi addr, а потом lo addr.
это не очевидно?
Код очевиден, да. Непонятно, что вы хотели этим кодом продемонстрировать.
сделайте это и прикрепите вывод и код пожалуйста, чтобы можно было проверить
Сделать что?
либо сумму, как вы считаете либо, то как вы увидели, теории не нужны от вас теперь раз вы так продолжаете дискуссию прикрепляйте примеры с выводом пожалуйста чтобы можно было видеть и проверять, иначе нету обьекта дискуссии и не понятно что и как вы поняли и увидели, если вы будете теоретически продолжать дискуссию о счете, разговор предлагаю закончить, по крайней мере в теоретической составляющей я участвовать не буду если не будет примеров и вывода
покажите что вы правы
Какую сумму?! Увидел что?!
Исправленный ваш код для тривиального суммирования 16 float?
Вот он, аж 2 версии, первая без лишнего перетасовывания битов, вторая еще и без повторения кода:
Скрытый текст
void testadd4_fixed() {
__m256 x = _mm256_load_ps( (a+(0<<2)) );
__m256 y = _mm256_load_ps( (b+(0<<2)) );
__m256 x1 = _mm256_load_ps( (a+(2<<2)) );
__m256 y1 = _mm256_load_ps( (b+(2<<2)) );
__m256 z = _mm256_add_ps(x, y);
__m256 z1 = _mm256_add_ps(x1, y1);
_mm256_storeu2_m128(&c[4],&c[0],z);//
_mm256_storeu2_m128(&c[12],&c[8],z);//
}
void testadd4_one(float *a, float *b, float *c) {
__m256 x = _mm256_load_ps(a);
__m256 y = _mm256_load_ps(b);
__m256 z = _mm256_add_ps(x, y);
_mm256_storeu2_m128(&c[4],&c[0],z);//
}
void testadd4_better() {
testadd4_one(a, b, c);
testadd4_one(a+8, b+8, c+8);
}Все 3 функции trestadd4 (ваша), testadd4_fixed, testadd4_better считают одно и тоже: 2 4 6 8 10 12 14 16 0 2 4 6 8 10 12 14
Ассемблерный выход примерно одинаковый в моих вариантах, только чуть другой порядок операций. Компилятор, кстати, достаточно умный, чтобы в вашей функции выкинуть ненужные инструкции самостоятельно, но зачем засорять код лишними операциями?
а зачем вы фиксите то чем не пользуетесь? пошли нюансы, вы показали свой вариант или вы исправили? насчет вашего первого вопроса тогда не понятны ваши вопросы более ранние
Так, если вы не хотели ваш исправленый код, то что вы хотите от меня?
я выше написал вам что не понятен предмет ваших обсуждений, касательно всей этой ветки после того что я заметил что вам чтото не понравилось в суждении, которое вам не нужно о дереве фенвика, тоесть какое вам дело кто как решает, если вы не показали своего решения даже о том что до этого спрашивали, а готовы только что-то исправлять, тоесть вы же раннее задавали вопросы, и как бы тогда вопрос зачем вы задаёте эти вопросы всё исправляете, но своё видение вы не показываете, большой вопрос
Когда вы сказали про векторизацию дерева фенвика я как раз сказал, что это сделать очень сложно и я слабо в это верю и попросил ссылку, потому что это очень интересно и было бы реально круто, если бы можно было его распараллелить. Но по ссылке вместо векторизации собственно операции вы дереве, происходит лишь параллельное выполнение нескольких операций, что, в общем-то довольно просто и бесполезно на практике. Я выскзал свое огорчение этим фактом.
Есть сложная и интересная задача, выше высказывание намекнуло на ее решение, но приведенная статья решает не эту интересную и сложную задачу, о чем я и написал.
так вы потом стали задавать вопросы что это, что то, чтобы исправить чужой пример, вопрос стоит так, если вы огорчились, зачем спрашивать дальше то что знаете, если вы исправляете, и вопрос стоит так если вы заведомо знаете как лучше, в чем интерес ваших вопросов не показывая своего видения? а тем более вы как пишите увидели что это сделать очень сложно, хотя после этого были вопросы о самих симдах, а на деле вы готовы получается только чужие примеры рассматривать и обсуждать теорию, на уровне возможно или нет
предмета нет в обоих случаях предмет это то что вы исправляете, но вы не пользуетесь этими примерами вот в чем беда
так вы потом стали задавать вопросы что это, что то, чтобы исправить чужой пример,
Я лишь пытался понять, что вы вообще имели ввиду! Если бы вы сразу написали что-то вроде "а вы разве знаете какой-то более хороший метод векторизации дерева фенвика", дискуссии бы не состаялось. Вместо этого вы стали писать лишь вам понятно как связнные с этим утверждения.
нет, спасибо я останусь при своём мнении, вы точно так же спрашивали про транспонирование только в вопросе, а примера с транспонированием нету. а моё решение без транспонирования
обьясню почему я так делаю, я хочу склеить 2 буффера в 1 и шифтовать значения, меняя высший и нижний регистр от 16 до 0 тогда будет эмуляция
Скрытый текст
void testadd4()
{
{//1
__m256 x41=_mm256_set_m128(xh1,xl1);
x41=_mm256_alignr_epi8(_mm256_permute2x128_si256(x41, x41, 0x03), x41,16);
}
{//2
__m256 x41=_mm256_set_m128(xl1,xh1);
x41=_mm256_alignr_epi8(_mm256_permute2x128_si256(x41, x41, 0x03), x41,16);
}
}это 2 разных случая если эмулировать до 16
когда сверха достигается до 0 надо прокинуть местами высший и нижний и установить счетчик в 16 и пошел далее вниз до второго нуля и тогда будет 16 чисел, останется только промахи занулять командой и или еще какой по положению бита высоты в двух регистрах
тоесть мне стал принципиально интересен случай с 16 числами. это средний спил к производительности(тоесть блок прохода по 16 будет, в цикле даст буст), но ухудшает понимание и на стаковерфлоу много вопросов о склеивании
есть prefix/ тут посмотрите, самый максимум у 512 пишут
В алгоритмике крутейшая страница про деревья отрезков и дерево Фенвика с векторизцией и укладыванием в кэш. И это лучший мануал по ним, который я вообще видел в сети (для полноты картины добавлю основную ссылку со страницы)
А вот это реально круто, спасибо. Действительно, если использовать не бинарные деревья, то там постоянно надо обрабатывать сразу всех детей вершины и это можно векторизовать.
только по 8 без связки лоу и хай вы не сможете крутить 1ой командой без смены верхнего нижнего, иначе не был бы этот вопрос так актуален, тоесть просто обращаясь в 0 в 256 прокрутив у вас поменяются местами в определенный момент лоу и хай, slli с нуля продемонстрирует тоже самое и начнет свой ход c заполнения нулями отделив верхний от нижнего, если мы по 0 работаем допустим, я предпологаю просто показывается общая концепция на алгоритмике, но не полное решение
Скрытый текст
x41=_mm256_slli_si256(x41,4);
0.000000
9.000000
11.000000
13.000000
0.000000
17.000000
19.000000
21.000000
x41=_mm256_alignr_epi8(_mm256_slli_epi32(x41,4), x41, 4);
11.000000
13.000000
15.000000
0.000000
19.000000
21.000000
23.000000
0.000000эмуляцией может служит связка верха с низом, под permute() и отслеживанием двух разрядов по 16 каждый 0 16 это значит сдвиг на том где 16 и он будет в тот момент верхним, такие приколы были замечены
у меня так
Скрытый текст
//__m128 xh2=_mm256_extractf128_ps(z1,1);
__m128 xh1=_mm256_extractf128_ps(z1,0);
__m128 xl1=_mm256_extractf128_ps(z1,1);
__m256 x41=_mm256_set_m128(xh1,xl1);//16V 16
x41=_mm256_alignr_epi8(_mm256_permute2f128_si256(x41, x41, 0x03), x41, 16);
x41=_mm256_alignr_epi8(_mm256_permute2f128_si256(x41, x41, 0x03), x41, 12);
x41=_mm256_alignr_epi8(_mm256_permute2f128_si256(x41, x41, 0x03), x41, 8);
x41=_mm256_alignr_epi8(_mm256_permute2f128_si256(x41, x41, 0x03), x41, 4);
//x41=_mm256_alignr_epi8(_mm256_permute2f128_si256(x41, x41, 0x03), x41, 0);
x41=_mm256_set_m128(xl1,xh1);//16 16V
x41=_mm256_alignr_epi8(_mm256_permute2f128_si256(x41, x41, 0x03), x41, 16);
x41=_mm256_alignr_epi8(_mm256_permute2f128_si256(x41, x41, 0x03), x41, 12);
x41=_mm256_alignr_epi8(_mm256_permute2f128_si256(x41, x41, 0x03), x41, 8);
x41=_mm256_alignr_epi8(_mm256_permute2f128_si256(x41, x41, 0x03), x41, 4);
//x41=_mm256_alignr_epi8(_mm256_permute2f128_si256(x41, x41, 0x03), x41, 0);
_mm256_storeu2_m128(&c[0],&c[4],x4);//
_mm256_storeu2_m128(&c[12],&c[8],x41);//а на алгоритмике по другому и там не числа с плавающей точкой у меня будут числа с плавающей точкой и наверняка тут еще куча нюансов
ну и соединить 2 куска x4 и x41 пока не имею представления без 512 как наверно и не возможно
я не прав, это интересно покопаться пофиксил у себя 8 сложений делает как в гайде на плавающих точках )
Присоединяюсь к комментатору выше. Ваши сегодняшние сообщения вообще не понятны. Кажется, вы что-то заметили в алгоритмике, что-то свое на основе этого придумали, и делитесь своими идеями с общественностью, но вы не указали к чему конкретно ваши комментарии относятся. Я же не вижу, что именно вы там прочитали. Потом, ваш код, вываленный вот так, без объяснения хотя бы какую задачу он решает - не несет никакого смысла.
Вам стоит перед отправкой ваших комментариев остановиться и задуматься, а весь ли контекст есть в треде, в который вы отвечаете. И если нет - включить его в ваш комментарий.
проблема в том что вы не огласили эти нюансы исправляя, которые я выше продемонстрировал
потомучто инт вектор и флоат вектор могут быть нюансы, мы же хотябы про префиксы правильно?
или вы предлагаете хранить индексы отдельно?
на стеке храним индексы правильно?
нюансов очень много если это пример выходящий за границы 8 елементного массива на стеке
mm256permute2f128_si256(int256, int)
и вот нюансов таких много, а нужно например онли float
а сли разбивает вектор
или как в алгоритмике но,
mm256slli_si256 (int256, int)
тогда то что я показал очевидно
Вы вообще о чем? Какие индексы? Какой стек? При чем тут флоат и инты? Исправления? Вы про ту маленькую заметку о выкидывании перетасовки 128-бит местами в примере суммирования?
в целом про префиксы и инты, потомучто дерево фенвика включает в себя префиксы
а что такое префиксы и дерево фенвика?, давайте про другую структуру например просто дерево(или просто префиксы бесконечные в массиве например они флоаты все ), в обоих статьях предлагается хранить всё на стеке, и примеры с интами, вы вот где собрались инты применять?
в 3д на интах так прикинуть класс получается
как вы будете применять эти знания если там будут флоаты чаще в расчетах
а гцц например кидает ошибку на обе эти функции он ждёт инты
))) ну сами посмотрите есть пример ок, но применять знания чаще надо в флоатах
Вы упоминули префиксы. Вы не знаете что это такое, или проверяете что я термин знаю? Это часть массива, если отбросить сколько-то последних элементов. Дерево фенвика позволяет быстро считать сумму элементов любого префикса, а так же изменять любой элемент.
например просто дерево
Что значит "просто дерево"? Дерево - это граф без циклов, само по себе оно для структур данных бесполезно почти всегда. Надо на него еще какие-то свойства навесить (как в дереве фенвика, каждая вершина хранит сумму какого-то подмножества элементов массива. Или в балансированных деревьях поиска значения в вершинах упорядочены и высота дерева ограничена).
в обоих статьях предлагается хранить всё на стеке
Нет, не предлагается. Там везде структура данных в куче. Но это вообще не важно. Даже с точки зрения векторизации. Стек/куча - все та же оперативная память. Только на стеке дешевле ее выделять.
примеры с интами, вы вот где собрались инты применять
Структуры эти используются не только в 3d, а где угодно, и чаще всего работают с интами. Вообще, про 3d - это у вас в голове контекст, никто тут и в статьях его не упоминал. Но если вы хотите примеров: индексы в базах данных, сжатие данных, а так же изображений и видео в частности. Все цвета пикселей - целые числа обычно. Обработка сигналов - аудио данные все обычно в виде интов. В том же геймдеве, если расширить кругозор от 3д графики: почти вся логика работает с int-ами (здоровье, координаты, урон, характеристики предметов и их количество...). Пока не могу придумать, где там использовать дерево фенвика, но сбалансированные деревья поиска будут использоваться повсеместно.
ну вы убрали частный случай не сказав о нюансах а потом заминусили то что вы убрали, потомучто он является по правилам самого симда нюансом и входит в решение на симде, это тоже странно, нет там они на стеке а не в куче, хотя вам виднее, оба примера про стек а не кучу(в тех двух статьях), дерево тоже структура данных
только там примеры с интами! важный нюанс
Скрытый текст
как вы собираетесь хотябы в 3д применить ускоренную структуру которая с интами, я потому и спросил вы предпологаете хранить отдельно индексы?
так данные выгоднее хранить во флоатах, ладно я всё понял
С интами надо использовать sse а не avx. Используйте другие интринсики и все скомпилируется.
убрали частный случай не сказав о нюансах а потом заминусили то что вы убрали, потомучто он является по правилам самого симда нюансом
Вы про исправление вашего примера? Это не ньюанс симда, а ваша ошибка. Я вам даже ссылку на ассемблерный выход компилятора выдал, и он ваши перетасовки регистров убрал сам, потому что они не нужны. Вы считаете, что в компиляторе тоже ошибка, а его создатели, в отличии от вас, не понимают ньюансов AVX?
как вы собираетесь хотябы в 3д
Я не собираюсь! 3d - это ваши тараканы в вашей голове. А вне 3д оно отлично применяется и с интами. Я вам кучу примеров привел выше.
я потому и спросил вы предпологаете хранить отдельно индексы
Что за индексы? Вы опять на своей волне, это у вас в 3d из интов только какие-то индексы? Нет, интами могут быть цвета пикселей, количество золота у персонажей или что угодно еще.
За сим я заявляю, что отныне буду вас игнорировать и молча минусить, ибо с вами невозможно разговаривать. Вы вообще не читаете, что вам пишут, и пишите каждый раз что-то вообще никак логически не связанное с чем либо, на что вы отвечаете, или даже вашими предыдущими словами.
нет вообще про суть префиксов
https://godbolt.org/z/fqGaEczWY
вот сами посмотрите, у вас поделятся 2 секции и как в алгоритмике уже не фурычит, вот буквально я вставил другой пример(префиксов) и отделился хай от лоу, а вы о чем вообще?
я код прикрепил на удаленной машине такое же поведение
вот общий пример prefix-sum-array-implementation-applications-competitive-programming/
пример у алгоритмика отработал только от 1 до 8 вставляешь другой всё, ну и где ошибка )
вот просто работает то что я говорил, https://godbolt.org/z/csjWb7d3q, с кучей нюансов, а код из алгоритмики еще запустить надо!, прошу обратить внимание на ассемблер, даже учитывая нюансы, это лютый ансейф использовать не рекомендуется
всё ради такого спуска правда операций чуть по-больше, зато считается наглядно
x = _mm256_add_ps(x,aplusb_aligned(v,c,a,b,2));
x = _mm256_add_ps(x,aplusb_aligned(v,c,a,b,3));
x = _mm256_add_ps(x,aplusb_aligned(v,c,a,b,4));
x = _mm256_add_ps(x,aplusb_aligned(v,c,a,b,5));
x = _mm256_add_ps(x,aplusb_aligned(v,c,a,b,6));
x = _mm256_add_ps(x,aplusb_aligned(v,c,a,b,7));
x = _mm256_add_ps(x,aplusb_aligned(v,c,a,b,8));я просто считаю вы неглядя исправили вы наверно ожидаете инты но нужны флоаты и флоат более ефективен чем инта, на интах наверно будет работать, но нужна плавающая точка и с плавающей точкой там ничего не убирается, потомучто надо держать два регистра по 16 и крутить их управляя
Это вы меня комментировали? Не понял про что вы, как и, если честно, каждое Ваше сообщение в этом треде.
Позвольте дать совет, о котором Вы не просили: судя по всему у Вас плохо получается общаться с людьми и доносить свои мысли до других. Это нормально и часто встречается у технических специалистов, но вот когда даже опытные коллеги по цеху говорят вам, что ничего не понятно -- стоит что-то менять в себе.
а с какими структурами вы работали и где?, тогда вероятность есть что вы ничего не поймёте если будете исключать возможность плавающей точки и особенностей
тоесть с интами заработает как в алгоритмике, а с флоатами есть особенности, вы можете конечно гнать инту в флоат но будут нюансы скажется на структуре, отрезки это же флоаты, это индексы целые числа
вот обратите внимание на структуру BVH -accelerated structure
почему она accelerated? она ускоренная не только потомучто разбивает по иерархии а потомучто создаёт сетку, и это в первом приближении в идеале она должна леч в SIMD
Bounding-Volume-Hierarchy тут анимация есть что происходит
нет ну есть вариант индексы отдельно хранить как инты, и над индексами делать ситуации в симд, тут интересно наверно тоже есть нюансы
префиксы искать это оказалось не сложно, проблема хотябы чанки делать в вокселях в симд попадая в сетку
(хотя бы, лучше конечно и чанкование в симд и иметь bvh-simd я сейчас так думаю) а префиксы это так первый подход на самом деле я считаю
у меня при такой конфигурации
const int n = (80), m = 80; последнее число 80ое число =68, может это и ошибка, но то что там разложить на SSE/AVX можно очевидно
а вы понимая, не дали ответ.
тоесть вы вопросы задали проверили, а сами ответ не дали
Скрытый текст
//-Ofast -ffast-math -mavx2
#include <stdio.h>
#include <immintrin.h>
float a[8]={0,1,2,3,4,5,6,7};
float b[8]={0,1,2,3,4,5,6,7};
float c[8]={0,0,0,0,0,0,0,0};
void rrr(float *a, int result);
void aplusb_aligned() {
__m256 x = _mm256_load_ps( (a+(0<<2)));
__m256 y = _mm256_load_ps( (b+(0<<2)));
__mmask8 mask ={0x0};
__m256 z = _mm256_add_ps(x, y);
__m256 perm=_mm256_permute_ps( z,0b11011 );
_mm256_storeu2_m128(&c[0],&c[4],perm);//
}
void permuteALL()
{
}
int main()
{
rrr(a,1);
return 0;
}
void rrr(float *a, int result)
{
aplusb_aligned();
for(int i=0;i<8;i++)
printf("%f\n",c[i]);
}crazy shaffle ))))
Простите за глупый вопрос. Я только с очень специфическими алгоритмами сталкивался, а от списков, графов и пр. крайне далек. Да и язык для меня непонятный (я его читаю, как псевдокод). Но:
> Пример: Найти цикл в связном списке
разве приведенный код не дойдет до конца вот такого списка:
1(4), 2(3), 3(2), 4(none)
Тут есть цикл 2-3, но последовательное применение (next) ведет к none. Так же ведь нельзя найти никакой цикл, недостижимый от head-а?
Или слово "связный" в условии означает что в списке нет недостижимых от head-а элементов?
В статье про Qsort автор не прав про сложность O(N log N), так как выбирая пивотом средний элемент на определенных тестах может быть достигнута сложность O(N^2), т.к. уровней рекурсии может быть вплоть до N
Да, вы правы. В худшем случае сложность O(N^2). Я даже написал это в таблице, но потом посмотрел и выглядело перегрузом информации не много и удалил. Как я написал в начале статьи, все что тут рассматривается нужно дополнительно изучать в других источниках/книгах и т.д. Статью стоит воспринимать как роадмап, чем она и является.
> Пример 3: Поиск максимального элемента в массиве
Простите великодушно, но этот пример я тоже не понял. В чем выигрыш от разбиения массива на части -то? Я вижу только накладные расходы.
Или такой код лучше распараллеливается в некоторых языках? Но тогда хотя бы намекните, в каких. В фортране например, так писать совершенно точно не надо.
.
UPD: И, соответственно, я не могу врубиться в рекомендацию:
> Метод "разделяй и властвуй" используется для задач (...) нахождение минимального/максимального элемента в массиве.
Можете пояснить, что имеется в виду?
Или это рекомендация для языков, где массивы реализованы каким-то экзотическим способом? Но такие языки, вероятно, изначально не преследуют цели быть эффективными при работе с такой структурой. И, соответственно, для решения таких задач лучше взять язык попроще, где самый тупой подход гарантирует О(n), и для этого не надо изобретать какие-то ухищрения...
Я бы упомянул в статье алгоритм решения любой задачи:
Внимательно читать условие и входящие / исходящие данные
Набросать тест кейсы, в том числе граничные
Подумать над подходом/алгоритмом, постараться быстро его оценить, к чему он может привести
Реализовать подход/алгоритм
Прогнать тесты, пофиксить
Вообще выбор подхода алгоритма самая сложная часть, но она может сократить время на все остальное.
Например задача полиндром целого числа (121 > 121) [9. Palindrome Number]. Это easy на литкоде. На этапе №3 можно рассуждать так: перевернуть число, сравнить число. А что значит перевернуть число? На том же самом литкоде есть задача [7. Reverse Integer] - и она уже medium. То есть решая easy задачу не следует использовать алгоритм уровня medium.
Современные интервьюеры слишком заигрываются в алгоритмы. ИМХО.
Как пройти алгоритмическое собеседование: полный гид по алгоритмам, сложностям и стратегиям