OpenMP / __gnu_parallel для неупорядоченной_карты
В какой-то момент в моем коде я должен выполнить операции со всеми элементами в unordered_map. Чтобы ускорить этот процесс, я хочу использовать openMP, но наивный подход не работает:
std::unordered_map<size_t, double> hastTable;
#pragma omp for
for(auto it = hastTable.begin();
it != hastTable.end();
it ++){
//do something
}
Причина этого в том, что итератор unordered_map не является итератором с произвольным доступом.
В качестве альтернативы я попробовал директивы __gnu_parallel, работающие над for_each. Но следующий код
#include <parallel/algorithm>
#include <omp.h>
__gnu_parallel::for_each (hashTable.begin(), hashTable.end(),[](std::pair<const size_t, double> & item)
{
//do something with item.secon
});
составлено с помощью (gcc 4.8.2)
g++ -fopenmp -march=native -std=c++11
не работает параллельно. Переключение unordered_map с вектором и использование той же директивы __gnu_parallel выполняется параллельно.
Почему он не работает параллельно в случае неупорядоченной карты? Есть ли обходные пути?
Далее я дам вам простой код, который воспроизводит мою проблему.
#include <unordered_map>
#include <parallel/algorithm>
#include <omp.h>
int main(){
//unordered_map
std::unordered_map<size_t, double> hashTable;
double val = 1.;
for(size_t i = 0; i<100000000; i++){
hashTable.emplace(i, val);
val += 1.;
}
__gnu_parallel::for_each (hashTable.begin(), hashTable.end(),[](std::pair<const size_t, double> & item)
{
item.second *= 2.;
});
//vector
std::vector<double> simpleVector;
val = 1.;
for(size_t i = 0; i<100000000; i++){
simpleVector.push_back(val);
val += 1.;
}
__gnu_parallel::for_each (simpleVector.begin(), simpleVector.end(),[](double & item)
{
item *= 2.;
});
}
Я с нетерпением жду ваших ответов.
Решение
Вы можете разделить цикл на диапазоны индексов сегментов, а затем создать внутрикадровый итератор для обработки элементов. unordered_map имеет .bucket_count() и специфичная для сегмента итератор begin(bucket_number), end(bucket_number) которые позволяют это. Предполагая, что вы не изменили значение по умолчанию max_load_factor() от 1.0 и иметь разумную хэш-функцию, вы будете средний 1 элемент на ведро и не должен тратить слишком много времени на пустые ведра.
Другие решения
Канонический подход с контейнерами, которые не поддерживают случайные итераторы, заключается в использовании явных задач OpenMP:
std::unordered_map<size_t, double> hastTable;
#pragma omp parallel
{
#pragma omp single
{
for(auto it = hastTable.begin(); it != hastTable.end(); it++) {
#pragma omp task
{
//do something
}
}
}
}
Это создает отдельную задачу для каждой итерации, которая приносит некоторые издержки и поэтому имеет смысл только тогда, когда //do something на самом деле означает //do quite a bit of work,