Как я могу заполнить std :: unorderd_map одновременно?

Мне нужно заполнить std::unordered_map<int,T> около 100 записей. Это дорого строить, и я хотел бы использовать OpenMP, чтобы сделать это одновременно:Как я могу заполнить std :: unorderd_map одновременно?

unordered_map<int, T> mapWithTs; 

#pragma omp parallel for schedule(dynamic) // dynamic because T constructs in some unpredictable time. 
for(int i=0; i<100; ++i) 
{ 
    mapWithTs.emplace(i, {i}) // calls the constructor T(i) 
}

Я прочитал, что карта будет перефразировать, а затем итераторы больше не будет действительным. Что я должен сделать, чтобы сделать эту работу?

Кроме того, как выглядит решение параллелизма со стандартной библиотекой?

источник

2016-10-09 dani

Дорогие конструкции, но они дешевы для перемещения? Может ли каждый поток создавать свой собственный вектор, а затем один поток перемещает эти векторные объекты в карту? – Galik

Вы создали бы несколько потоков, каждый из которых заполняет собственную карту, а затем объединяет карты (в одном потоке). –

Вам просто нужно синхронизировать (взаимное исключение) доступ к карте. Я не знаю, как сделать эту синхронизацию с OpenMP, но, предположительно, вы это делаете. Если нет, просто обратитесь к документации. –

В случае, если эти дорогостоящие экземпляры для создания являются справочными, то есть с помощью shared_ptr, raw pointer, & c., Я предлагаю разрешить каждому потоку создавать свою собственную стек-локальную карту в шаге, также канонически называемом также «map», , а затем объединить их все в один поток в шаге, канонически называемом «уменьшить».

Это называется алгоритмом «уменьшения карты».

«карта» является обычным именем функции, которая применяет функцию ко всем элементам коллекции

«уменьшить» это обычное имя функции, которая сочетает в себе все элементы коллекции в одно значение по вызов функции с текущим промежуточным результатом и каждый элемент

отсюда название :)

источник

2016-10-09 09:46:32 yeoman

Остерегайтесь использования операции «карта», которая неявно использует память кучи через 'new',' malloc' или подобное. Большинство реализаций предоставляют единую кучу для всех потоков, поэтому использование памяти кучи может привести к конфликту и блокировке, аналогичной явно использующей общую карту с блокировками. –

Вы имеете в виду, когда он бежит низко? Или это кучи JVM, GNU libC++, BSD libC++, на удивление ужасно неэффективные, когда речь идет о параллельных распределениях? – yeoman

* Вы имеете в виду, когда он бежит низко? Или кучи JVM, GNU libC++, BSD libC++ неожиданно ужасно неэффективны, когда речь идет о параллельных распределениях? * Любой из них. Любой из них. Это зависит от реализации кучи и шаблона использования памяти. По моему опыту, многопоточные кучи, как правило, работают очень хорошо - большую часть времени. Но я видел шаблоны использования, которые уменьшают реализацию кучи для эффективного однопоточного приложения. Это то, о чем нужно знать, если вы рассчитываете на то, что 6-процентное ускорение будет работать от 8 потоков и вообще не будет ускорено. –

Как отметил Galik и Yeoman, необходимо, чтобы сделать перемещение ваших объектов дешевая операция. Если это уже (строительство тяжелое, но перемещение дешево), тогда вы в порядке. В противном случае вы должны поместить свои объекты в uniq_ptr. После этого перерывы будут также дешевой операцией (да, rehash принимает линейное время, но это 0 (1) амортизированная сложность). Поэтому вам не нужно беспокоиться о перефразировании.

Следующее - заполнение карты. Вы работаете с ним из нескольких потоков, поэтому вы должны следить за тем, чтобы одновременно с ним работал не более одного потока. Вам нужно что-то вроде #pragma omp critical или std :: mutex. И здесь важная роль: если вы используете emplace, как вы делаете это сейчас, то тяжелый конструктор Т будет выполнен в критическом разделе, который убивает всю идею распараллеливания. Поэтому в этом конкретном случае вы предпочли бы создать объект T заранее, затем входите в критический раздел и перемещаете объект в хэш-карту.

Если конструкция T действительно тяжелая операция (требуется гораздо больше времени, а затем вставка значения в неупорядоченный_мап), то это все. Вы не получите прирост производительности за счет создания списков потоков и вставки их в карту. В противном случае, ответ yoman может дать вам дополнительные преимущества за счет увеличения сложности вашего кода.

источник

2016-10-09 11:53:33

Как я могу заполнить std :: unorderd_map одновременно?

ответ

Смежные вопросы