Russian Qt Forum
Март 28, 2024, 17:58 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
 
  Начало   Форум  WIKI (Вики)FAQ Помощь Поиск Войти Регистрация  

Страниц: [1]   Вниз
  Печать  
Автор Тема: Ускорить цикл  (Прочитано 7330 раз)
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« : Октябрь 08, 2020, 11:11 »

Добрый день

Профайлер показывает что драгоценное время съедается здесь
Код
C++ (Qt)
std::map<Extent, std::vector<Matrix>> theMap;
for (const auto & it : data)
 theMap[it.m_extent].push_back(it.m_matrix);
 
Структуры простые
Код
C++ (Qt)
struct Matrix {
double m[16];
};
struct Extent {
int m_type;
Vec3f m_points[8];
};
 
Число итераций цикла 100K и больше.

Возможно ли это ускорить? Если да то как?
 
Спасибо
« Последнее редактирование: Октябрь 08, 2020, 12:11 от Igors » Записан
Авварон
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 3257


Просмотр профиля
« Ответ #1 : Октябрь 08, 2020, 11:49 »

вероятно, имелось ввиду
Код:
struct Data { Extent m_extent; Matrix m_matrix };
std::vector<Data> data;
std::map<Extent, std::vector<Matrix>> theMap;
for (const auto & it : data)
  theMap[it.m_extent].push_back(it.m_matrix);
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #2 : Октябрь 08, 2020, 12:13 »

вероятно, имелось ввиду
Да, спасибо, маленько описАлся, исправил
Записан
Авварон
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 3257


Просмотр профиля
« Ответ #3 : Октябрь 08, 2020, 12:21 »

А что конкретно тормозит? Чтобы понятно с чем бороться.
Если много аллокаций, то можно отсортировать исходный массив и делать reserve/range insert по одинаковым ренжам ключей.
Работа с ренжем кстати уберет лукапы в мапе на вложенных векторах - место для вставки рэнжа надо найти только 1 раз.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #4 : Октябрь 08, 2020, 13:02 »

А что конкретно тормозит? Чтобы понятно с чем бороться.
Сам оператор [] + копирование ключа и данных (хотя Matrix не имеет конструктора(ов)). Правда это при большом числе повторов (затрат на поиск практически нет). Поэтому и хеш (вместо мапы) не проверялся

Если много аллокаций, то можно отсортировать исходный массив и делать reserve/range insert по одинаковым ренжам ключей.
Работа с ренжем кстати уберет лукапы в мапе на вложенных векторах - место для вставки рэнжа надо найти только 1 раз.
Нвсколько я понял, задумка = избежать переаллокаций вектора. Возможно, но не вдохновляет - возни много, а толку чуть. При большом числе повторов сортировка (пусть указателей) обычно проигрывает ассоциативному контейнеру.

Но конечно главный интерес - использовать богатырскую силу всех ядер. Правда сделать это здесь совсем непросто. Ну ясно race прет, но не только
Записан
RedDog
Частый гость
***
Offline Offline

Сообщений: 221


Просмотр профиля
« Ответ #5 : Октябрь 08, 2020, 16:51 »

Код:
std::unordered_map<Extent, std::vector<Matrix>> theMap;
должно ускорить, если ключей много.
вектору можно сделать emplace

да, еще можно в OpenMP цикл засунуть, но правда доступ к контейнерам надо будет локерами обкладывать и может выигрыша не дать
« Последнее редактирование: Октябрь 08, 2020, 17:13 от RedDog » Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #6 : Октябрь 10, 2020, 09:26 »

Я, правду сказать, не пытался  это "разпоточить" (оформил ключ указателем и все, лапки кверху). Не видно как побеждать race, остается дать каждой нитке свою мапу - но тогда придется "сливать" в главной, и хорошо еще если "то на то и выйдет". Но это еще цветочки. Главное:  давно известно что вот такое "маленькое говнецо" не масштабится. Ну можно еще (авторитетно) добавить "точка" Улыбающийся Даже на хорошей кратности. Слишком мал "кластер". И все тулзы уходят в минус (некоторые в катастрофический). Т.е. время больше чем на 1 нитке, причем тем больше чем больше рабочих ниток.

Досадно что эта сборка матриц жрет в 4-5 раз больше чем рисование для которого она собирает
Цитировать
Абыдно слюший
Ну ладно утешаюсь тем что мой код - очень короткий и простой Улыбающийся
Записан
Racheengel
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2679


Я работал с дискетам 5.25 :(


Просмотр профиля
« Ответ #7 : Октябрь 13, 2020, 16:06 »

100000 векторов ПО ЗНАЧЕНИЮ в мапу??
  "ну вы, батенька, даете" Улыбающийся

Тут надо пул матриц делать, а не мапу с векторами, ИМХО.
Записан

What is the 11 in the C++11? It’s the number of feet they glued to C++ trying to obtain a better octopus.

COVID не волк, в лес не уйдёт
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #8 : Октябрь 14, 2020, 09:56 »

100000 векторов ПО ЗНАЧЕНИЮ в мапу??
  "ну вы, батенька, даете" Улыбающийся

Тут надо пул матриц делать, а не мапу с векторами, ИМХО.
Не понял. Убедимся что мы говорим об одном и том же
Код
C++ (Qt)
std::map<Extent, std::vector<Matrix>> theMap;
 
Здесь Extent - это "что" приложение рисует (объект). Цель нарисовать 100K объектов. А матрицы определяют где каждый объект стоит и как повернут. Если сами объекты одинаковы (разница лишь в матрицах), то можно отрисовать одной командой (glDrawElementsInstanced), подав ей массив матриц, это на порядок быстрее чем тюкать по одному. Ну вот я и "собираю" одинаковые объекты в мапу. Да, если все объекты уникальны - буду иметь 100K векторов,, каждый аж с одним эл-том. C'est la vie

"Контейнер на контейнер" часто не есть хорошо, но иногда неизбежно
Записан
Racheengel
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2679


Я работал с дискетам 5.25 :(


Просмотр профиля
« Ответ #9 : Октябрь 16, 2020, 09:28 »

Один элемент на вектор в принципе должен соптимизироваться в просто "один элемент".
Но меня беспокоит именно мапа векторов как конструкция.
По идее при каждом изменении любого вектора нет гарантии, что не будет переаллоцирована вся мапа (а значит, и остальные 99999 векторов).
Вот если бы была мапа указателей на вектора, может было б шустрее.
Но это тестировать надо, конечно. ИМХО.
Записан

What is the 11 in the C++11? It’s the number of feet they glued to C++ trying to obtain a better octopus.

COVID не волк, в лес не уйдёт
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #10 : Октябрь 16, 2020, 10:19 »

Один элемент на вектор в принципе должен соптимизироваться в просто "один элемент".
Но меня беспокоит именно мапа векторов как конструкция.
По идее при каждом изменении любого вектора нет гарантии, что не будет переаллоцирована вся мапа (а значит, и остальные 99999 векторов).
Вот если бы была мапа указателей на вектора, может было б шустрее.
Но это тестировать надо, конечно. ИМХО.
Не, для мапы четко - итератор остается валидным при вставке/удалении др эл-тов. Хранить адресв значений мапы можно. Ну и вставка/удаление в вектор (значение) никак не влияют на "внешний" контейнер (sizeof значения один и тот же с любым числом эл-тов)
Записан
Страниц: [1]   Вверх
  Печать  
 
Перейти в:  


Страница сгенерирована за 0.121 секунд. Запросов: 22.