Ускорить цикл

[Igors]

Добрый день

Профайлер показывает что драгоценное время съедается здесь

Код

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 и больше.

Возможно ли это ускорить? Если да то как?
 
Спасибо

[Авварон]

вероятно, имелось ввиду

Код:

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]

вероятно, имелось ввиду

Да, спасибо, маленько описАлся, исправил

[Авварон]

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

[Igors]

А что конкретно тормозит? Чтобы понятно с чем бороться.

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

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

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

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

[RedDog]

Код:

std::unordered_map<Extent, std::vector<Matrix>> theMap;

должно ускорить, если ключей много.
вектору можно сделать emplace

да, еще можно в OpenMP цикл засунуть, но правда доступ к контейнерам надо будет локерами обкладывать и может выигрыша не дать

[Igors]

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

Досадно что эта сборка матриц жрет в 4-5 раз больше чем рисование для которого она собирает

Абыдно слюший

Ну ладно утешаюсь тем что мой код - очень короткий и простой

[Racheengel]

100000 векторов ПО ЗНАЧЕНИЮ в мапу??
  "ну вы, батенька, даете"

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

[Igors]

100000 векторов ПО ЗНАЧЕНИЮ в мапу??
  "ну вы, батенька, даете"

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

Не понял. Убедимся что мы говорим об одном и том же

Код

C++ (Qt)
std::map<Extent, std::vector<Matrix>> theMap;
 

Здесь Extent - это "что" приложение рисует (объект). Цель нарисовать 100K объектов. А матрицы определяют где каждый объект стоит и как повернут. Если сами объекты одинаковы (разница лишь в матрицах), то можно отрисовать одной командой (glDrawElementsInstanced), подав ей массив матриц, это на порядок быстрее чем тюкать по одному. Ну вот я и "собираю" одинаковые объекты в мапу. Да, если все объекты уникальны - буду иметь 100K векторов,, каждый аж с одним эл-том. C'est la vie

"Контейнер на контейнер" часто не есть хорошо, но иногда неизбежно

[Racheengel]

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

[Igors]

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

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