Russian Qt Forum

Добрый день

Тормозит здесь

C++ (Qt)
std::vector<Vec3> CPolySDS::CalcVerNormals( const std::vector<Vec3> & pos ) const
{
	std::vector<Vec3> dst(pos.size());
 
	for (size_t i = 0; i < mNorIndex.size(); i += mNumVerPerFace) {
		Vec3 faceN = GetFaceNormal(&mNorIndex[i], mNumVerPerFace, pos);
		for (size_t j = 0; j < mNumVerPerFace; ++j)
			dst[mNorIndex[i + j]] += faceN;
	}
 
// ну и далее вектор посылается на видеокарту
 

Отладчик показывает что 58% съедается на цикле. Скорость 1 fps, т.е. мышей можно елозить с большим трудом. Если отключаю цикл - скорость 6 fps, тоже не блеск, но лучше. Число итераций цикла > 2 лимонов.

Ну разумеется стандартное решение (OpenMP) здесь ничего не ускоряет, а Qt-шный "конкурент" даже замедляет. Это даже без локера что нужен для вложенного цикла. Оно и понятно - слишком мала "нагрузка" (или "кластер"), в GetFaceNormal по сути только вычитание векторов + векторное произведение.

Конечно первая мысль - увеличить кластер. Типа: да, GetFaceNormal слишком мал, но итераций-то прилично, за 2 мульена. Вот давайте "объединим" и 4 ядрам дадим 4 задачи по 500К итераций каждая - и будет счастье  :) Проверял много раз (и в данном случае), хотя знал что OpenMP делает это  по умолчанию. Ну конечно никакого счастья не получил, скорость та же.

Др варианты. Самое крутое - перенести на GPU, но это такой головняк из-за жалких 5 строчек кода  :'(  Искать еще какую-то "систему" (давеча видел какой-то "open"), ну это долго а рез-т не гарантируется.

Как же все-таки бороться с этим маленьким говнецом?

Спасибо

Я так подозреваю, что такая задержка в функции

C++ (Qt)
GetFaceNormal(&mNorIndex[i], mNumVerPerFace, pos)
 

А что будет с fps, если цикл оставить, а на эту функцию заглушку поставить?

Ну типа

C++ (Qt)
Vec3 GetFaceNormal(...)
{
return Vec3();
}
 

GPU без "головняка":
https://thrust.github.io/

Не понял задумку, нагрузка мала, а мы делаем ее еще меньше. Ну ладно, проверить нетрудно. Получил 2 fps (вместо 1), что впрочем не значит "вдвое" (там просто округление до целого). Что естественно - расчетов стало меньше. Но никакого намека на ускорение на 4 ядрах. Совсем. Что будет на большем числе ядер - хз (нередко возникает обратный эффект)

Да, и вот момент: для вложенного цикла  нужен локер, оператор += разумеется not thread-safe. Как его реализовать? Ясно нужен unfair но боюсь что и его здесь не хватит.

Что делает этот код: вычисляет нормали к вертексам как сумму нормалей всех фейсов (полигонов) ссылающихся на данный вертекс. Конфликты (data race) здесь редки, но увы, они есть

Ну сначала надо установить и "осмотреть" не такой уж маленький софт. Образующуяся "еще одна зависимость" также не радует. Конечно это нормально, но не сказал бы что "так уж просто"  :) Бегло глянув примеры, я понял следующее: если я имею (массивные) вектора на CPU - мне надо передать их на GPU. Боюсь что уже эта операция займет куда больше времени чем простецкий расчет в главной нитке. Поэтому вряд ли удастся "ускорить это (конкретное) место". Вот если бы изначально все данные планировались на thrust - тогда .. может быть..

Буду рад продолжить обсуждение деталей GPU реализации, хотя знаю здесь очень мало.  Но уверен ответа не последует, "тыцалки" (или "тыцуны"?) почему-то никогда не хотят говорить о "тыцаемом"  :)

При таком отношении к местному населениию, вы точно ответа не получите. Даже, если кто-то и умеет читать мысли.

Нормальное отношение, если нет желания (или познаний) просто обсудить предмет - то зачем предлагать его другим?

Если я хочу "что-то получить" - я гуглю, а на форуме я хочу поговорить с умными  людьми  :)

А о чём тут можно говорить вообще? Вы выдали некоторый кусок кода, который на первый взгляд вполне нормальный. Ускорить его можно разве что "разворачиванием" цикла. Насколько хорош остальной код, можно только догадываться.
Возможно, что вы просто сделали/выбрали плохую архитектуру проекта. Соответственно, никто ничего особо сказать и не может. Ни "тыцуны", ни обычные программисты.
Если бы у меня возникла такая проблема, я бы просто сделал минимальный проект с проблемным кодом и выложил бы его. И, вот тут, уже можно было бы о чём то рассуждать.

Это "не тот случай". Код совсем не "проблемный", он корректно работает, вот только "недостаточно быстр"

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

Дежурная прибаутка про "корявую архитектуру". Если мы хотим рисовать объекты, нормали к вертексам иметь/считать обязаны. Это момент чисто технический, к "архитектуре" отношения не имеет.

О многом. Напр я ожидал чего-то типа "надо смотреть в сторону GPU" (как обычно изрекают знатоки). Но как туда смотреть? OpenGL? Ну на скромном core 3.3 (требования) - это вряд ли. Значит что-то типа OpenCL, CUDA (кстати тыцнутый thrust в нее входит) и.т.п. Никогда этим не занимался и энтузиазма лезть в это огромное болота никакого. Но "жизнь заставит", данный случай в принципе типовой. Почему бы и не "попробывать"?

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

Обязательно ли посылать полный вектор dst на видеокарту?
Может разделить по ядрам и каждое ядро сформирует и отправит свой кусок вектора?
Ещё неплохо было бы подумать насчёт оптимизации количества итераций?
По опыту, могу сказать, что программная оптимизация не даёт вау-эффекта, а оптимизация на уровне бизнес логики может в десятки тысяч раз ускорить.

Кстати для этого надо расшарить контекст для каждой нитки (недавно за это получил). Что будет - не знаю, проверить не просто. В любом случае "передача данных на GPU" - всего лишь одна из проблем. Если делать на GLSL - придется изрядно попыхтеть уже с чтением эл-тов массива. С записью - намного больше. А с локом - вообще не знаю как, наверно придется сделать 2 прохода чтобы от него избавиться. Конечно написать пару-тройку шейдеров, аккуратно все зарядить, и.т.п., в общем - кал ужасный.

Конечно эта рекомендация справедлива, но увы - не всегда возможна/применима.  А главное - почти всегда "дорогостоящая". Из-за буквально 5 строк мы начинаем "большую войну" или "глубокий анализ" (который может ни к чему и не привести). Такой путь явно "не технологичен".

Смотрим на исходный код: простые расчеты, большая кратность - явно работа для той скотины с огромными мощностями но мозгами курчонка. Да, "brute force" - это нехорошо, но все очень довольны когда она есть  :)

Я имел ввиду не шарить один вектор на 4 потока/ядра, а каждый поток делает свой локальный вектор, и его посылает на GPU, или куда там еще.

Шарить надо контекст, просто так посылать из др нитки (не главной где контекст создан) = отлуп/ошибка. Ну и шансов на ускорение немного, ведь N ниток льют "в одну дырочку". Вообще мне кажется неверным пытаться в данном случае что-то делать "руками", здесь явно нужна "современная технология" (о которых так любят говорить :) )

Затык, я так понимаю в расчетах, а не в "дырочке".

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

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

Да, а что же со ссылочкой выше? Ну как всегда - тыцнуло и смылoсь :'(

Я и предлагаю этот цикл распаралеллить на все 4 ядра. Каждое посчитает свою 1/4 итераций. При 4-х ядрах не в 4 конечно, но раза в 2 как минимум должен быть прирост.
И после окончания потоков слить полученные 4 результата в один вектор, который и запулить на ГПУ.

Нужно убрать цикл из цикла, а затем уже параллелить

C++ (Qt)
std::vector<Vec3> CPolySDS::CalcVerNormals( const std::vector<Vec3> & pos ) const
{
	std::vector<Vec3> dst(pos.size());
	std::vector<Vec3> faces( mNorIndex.size() / mNumVerPerFace );
 
        // эффективно распараллеливаем здесь
	for (size_t i = 0; i < mNorIndex.size(); i += mNumVerPerFace) {
		faces[ i / mNumVerPerFace ] = GetFaceNormal(&mNorIndex[i], mNumVerPerFace, pos);
	}
 
        // не очень эффективно распараллеливаем здесь
	for (size_t i = 0; i < mNorIndex.size(); i += mNumVerPerFace) {
		for (size_t j = 0; j < mNumVerPerFace; ++j)
			dst[mNorIndex[i + j]] += faces[ i / mNumVerPerFace ];
	}
 
// ну и далее вектор посылается на видеокарту
 

Как вариант не очень эффективное распараллеливание попробовать реализовать без блокировок диапазонами таким способом

Номера индексов mNorIndex поделить на диапазоны. Первым потоком выполнять операции только для [0...N1), вторым - [N1...N2) и т.д. [Nx...mNorIndex.size()).
Диапазоны нужно выбирать так, чтобы кеши CPU заведомо не пересеклись.

Правильно так:
Значения индексов mNorIndex поделить на диапазоны. Первым потоком выполнять операции только для [0...N1), вторым - [N1...N2) и т.д. [Nx...max_index)).
Где max_index, максимальное значение из mNorIndex.

Пожалуйста, прочтите стартовый пост.

Если имеется ввиду "сделать 2 цикла и параллелить каждый" - то так теряем время на запись/чтение (вектор faces) + (еще хуже) ждем на барьере после первого цикла.

Такое "деление на диапазоны" (иногда называют "stencil") совсем не бесплатно/безобидно. И предрассчитать его получается далеко не всегда.

Я бы делал просто "мешком локеров", напр для Qt

C++ (Qt)
std::vector<int> lock(pos.size());

И перед каждым += с наглой мордой привести к QAtomicInt и лочить testAndSetAcquire

Но до этого дело даже не доходит - оно не масштабит и без всякого лока. Мне кажется очевидным надо прорываться к GPU, это его тема

Найти (или предположить) диапазон значений индексов - откуда здесь могут быть большие затраты?


Любые локеры сделают только хуже. Здесь может только помочь распараллеливание безо всяких локеров. Все потоки пробегаются по всему циклу, только производят вычисления каждый в своем диапазоне. В своих задачах я формирую массивы типа faces заранее (увеличиваю только при необходимости), чтобы не иметь потерь на new|delete.
Использование заранее инициированного пула потоков и ожидание на барьере после первого цикла и далее после второго ничтожно по сравнению с затратами на вычисления.
И да, расчеты нормалей, как правило делают на GPU.

Из первого поста не сильно понятно как было сделано распараллеливание.
Хотя бы псевдокод посмотреть, с теми локами и конкурентным доступом к общим объектам.
PS: OMP параллелит далеко не всегда адекватно.

Очень приятно блять.

thrust использовали на реальном проекте, работает норм, могу рекомендовать. Что быстрее - считать на цпу или передать данные (или создать) на гпу - решай сам, замерь, какие проблемы.

Для "приличных", нормальных задач - да. А вот для таких мелких - нет. Что вполне естественно. Напр для каждого вертекса нужно собрать индексы фейсов куда он входит. Конечно вычислений никаких, но читаются/пишутся немалые вектора, а это уже соразмеримо с временем вычисления нормалей.

Разумеется гуглил (правда без особого фанатизма) но ничего не нашел. Очевидно нужно задействовать какой-то "инструментарий", но вот какой? Требования к видео: OpenGL 3.3, т.е. рассчитывать на большее я не могу. Какие варианты?

CUDA - ну это вроде NVidia SDК, вика показывает перечень поддерживаемых карт. Т.е. выходит нужно поддерживать текущий (медленный) "software вариант" ? Это заботы/груз

OpenCL - какой-то непонятный зверь. "Собирал" неск приложений где он задействован. Одно вообще висит, хотя device инициализиpуется успешно, пришлось OpenCL отключать. В др приложении вроде работает (радостно сообщает что "откомпилило" какой-то местный шейдер) но каков эффект - хз.

Просто перед циклом вставляем
Также проверялся QtConcurrent - ну там вообще мрачно. Также проверялось "ручное" разбиение (типа того что Вы предлагали). Локер не реализован вообще (пока не до него). Во всех случаях на 4 нитках тот же самый 1 fps. Профайлер показывает что да, все нитки задействованы, но в основном стоят на барьере.

Интересно, можно больше подробностей?

Хотя в данном случае CPU не вызывает энтузиазма. Ну "вдвое" - это же очень мало, будет сцена/объект/итераций побольше, опять встанет тот же вопрос.

Смысл разбиения - убрать барьер, т.е общие данные, каждый поток крутит исключительно свои данные.
Крутил несколько млн итераций на ОМП на 8 ядрах, первые несколько секунд все 8 работают, потом по одному отключаются (на каждом ядре по очереди заканчивается данные) и последнее ядро свой кусок очень долго крутит. Может я что то не правильно делал, но это поведение мне не понравилось.

Ну это фишка известная, здесь наоборот, кластер слишком велик, в рез-те все "ждут отстающего".  Бороться так

C++ (Qt)
#pragma omp parallel for schedule(dynamic, 1)  // возможно др значение вместо 1

И задач "нарезать" не по числу ниток, а хотя бы вдвое больше

Ну если задача не поддаётся такому явному распараллеливанию, то может имеет смысл пересмотреть стратегию..?
Как я понял, у вас каждый кадр ожидает функцию

C++ (Qt)
CalcVerNormals
 

Может тогда имеет смысл распараллелить не то, что у неё под капотом находится, а просто сэт кадров?  

Разумно, примерно таким способом я часто выкручиваюсь (делать/скармливать задачи уровнем выше). К сожалению, это не всегда применимо. Напр в данном случае есть мужик (аттач) который машет руками и.т.п. Я могу его просчитать только для данного кадра (текущего времени), для следующего - все с нуля. Др словами "слишком велико чтобы выделить в задачу"

Ну тогда извиняйте... Другого пути уже не найти.

Что функция рассчетов то делает?
Может она весь кэш процессора вышибает? Есть тулзы (по памяти не скажу) которые профилируют промахи кэша.
Может размер итерации не подогнан под размер кэшей?
Ещё подумать в сторону векторных операций, раза в 4 могут ускорить

Написал пример С++17. Ускорение есть какое-то в пару раз, но для поставленных амбициозных целей явно не подходит).
Возможно и ошибся где-то. А так-то, сразу тестовая программка сильно помогла бы вникнуть в вопрос.

А можно поподробнее в сторону векторных операций? (сам просто сейчас занимаюсь вычислениями собственных значений и собственных векторов)   

У меня

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

:)

В любом случае спасибо за пример современного кода.

CalcFaceNormal вычисляет нормаль к полигону как векторное произведение 3 вертексов (точек, позиций). Если полигон имеет 4 вертекса (как в данном случае) то вычисляются 2 нормали и осредняются (поэтому оформлено методом).

В Bullet есть базовые векторные операции с использованием SIMD и.т.п. Насколько помню только для float (не double). Пробовал вкл/выкл, какого-то ощутимого эффекта не наблюдал. Вообще последние неск лет (если не больше) Bullet озабочен поддержкой OpenCL. Ну когда в последний раз обновлялся было "только для крутых карт"

Я Armadillo  http://arma.sourceforge.net/ (http://arma.sourceforge.net/) использую.. Она под капотом тоже ядрами шуршит.. Правда проблема в том, что нужно каждый раз убеждаться/гарантировать, что матрица эрмитова.. И во-вторых встречаются тройные циклы.. а это сразу ставит крест на распараллеливании..

Ну я не настоящий сварщик, но кажется что вот этот кусок

можно делать векторно сразу чанками. другое дело что там как я понимаю даблы, а в регистр влезает только 2 дабла, так что с 4кратным ускорением я погорячился, кол-во операций только вдвое сократиться

Боюсь, так просто не получится.. Там же ещё оператор += лочить нужно..

Ну SIMD (sse, avx и.т.п.) это типа "мульти-команды", все в рамках одного ядра.

Ну программировать на уровне этих команд - это верный путь в дурдом  :) Там много всяких фокусов что надо знать (наблюдал в исходниках Embree). Чисто из общих соображений думаю на ощутимый "выйгрышь" рассчитывать не приходится. Ну да, += сделаем одной командой, там кстати 4-байтовые флоты. Так ведь на каждой итерации надо обратиться по (другому) индексу. Вот если бы весь вектор впарить одной командой - то была бы моща. Но так обычно удается лишь при совсем уж тупой работе с пыкселями. Да и локер та еще PITA.

На всякий случай расскажу алгоритм/данные. Банальное (или самое простое) "data per vertex". Вектор pos содержит тройки флотов (x, y, z координаты). Вектор индексов, пример

((0, 1, 3, 2), (4, 5, 1, 0) ...)
Хранятся (сплошняком) индексы в массиве pos. Первый фейс ссылается на первую четверку индексов, второй на вторую и.т.д. Индексы могут повторяться, напр выше первые 2 фейса шарят ребро 0,1. Считаем нормаль к фейсу и тут же добавляем ее ко всем выходным вертексным нормалям этого фейса.

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

Ну ладно, так как же все-таки задействовать GPU? Глянем в дусте: есть boost::compute. Бегло глянул, прочел статейку (https://habr.com/ru/post/515308/) на хабре :) Насколько понял, обертка над OpenCL. Смысл тот же что и в тыцнутом thrust. Есть достаточно удобные ф-ции для обмена векторами между GPU <-> CPU. Конечно они не бесплатны по скорости, а если данных мало - может ничего и не ускорим, а наоборот. Ну ладно, считаем что это нормальная, неизбежная проблема.

А вот что собсно с самими расчетами? Тут мрачно. В примерах показывается вызов стандартных built-in ф-ций. Остается вызов кастомной ф-ции (что-то типа шейдера в OpenGL). В бусте такое есть, упомянутая статья приводит охренительный пример
И по сути все, управился. Вот же гад :'( А по индексу как? В OpenGL это возможно, нужно загнать данные в текстуру, а потом texelFetch (точно не помню). Стало быть, и здесь должно быть. Но пока не нашел. Возможно лучше юзать просто OpenCL

Да, а почему же никто не горит желанием овладевать "новыми технологиями"?  :) Может все ими давно уже владеют, только старый ретроград все не сообразит что и как  :)