Контейнеры C++ и параллель omp ⇐ C++

[Anonymous]

Итак, у меня есть алгоритм, который получает набор объектов и вычисляет следующий набор объектов. Код ниже представляет собой игрушечную версию реального кода для краткости. Следующий фрагмент иллюстрирует тему программы и не компилируется. Полный рабочий код смотрите в конце этого поста.
struct Ints
{
// is just for the toy example. The real code has proper objects.
std::set vals;

Ints (const std::set &vals) : vals(vals) {}

bool operator < (const Ints &that) const
{
return vals < that.vals;
}

// Build Ints objects from this and add them to `set'.
void add_variants (std::set &set) const
{
for (int i : vals)
{
Ints y (*this);
y.vals.insert (i + 2);
set.emplace (std::move (y));

Ints z (*this);
z.vals.insert (i - 1);
set.emplace (std::move (z));
}
}
};

// For a set of Ints, get a set of all morphed Ints.
// Approach 0: All sequential, non-parallel.
std::set next_set (const std::set &set)
{
std::set set2;
for (const auto &y : set)
y.add_variants (set2);
return set2;
}

int main ()
{
int n_loops = 16;

std::set set { Ints (std::set { 10 }) };

for (int i = 1; i add_variants_mutex (list, mux);

std::set set2;
for ( ; ! list.empty (); list.pop_front ())
set2.emplace (std::move (list.front ()));
return set2;
}

Это работает, но перемещение элементов Ints из списка в set2 является последовательным.
Я хочу, чтобы N-1 потоков добавлялись в список, а 1 поток передавался из списка в set2. Что-то вроде
WHILE (other-threads-are-running OR list-is-nonempty)
WHILE (list-is-nonempty)
consume-first-element-of-list

который работает параллельно с потоками N-1, которые добавляются в конец списка.
Приведенный ниже игрушечный код имеет больше вариантов распараллеливания, я уверен, что их также можно улучшить. Тайминги, полученные с помощью этих подходов, следующие:



Время
Последовательное
Приблизительно 1
Приблизительно 2
Приблизительно 3




реальный
0м3,817с
0м4,065с
0м2,276с
0м6,341с


пользователь
0m3.780s
0m7.665s
0m4.147s
0m6.525s



Подход мьютекса 3 на самом деле худший, но с реальным кодом, который может измениться.

C++11 + OpenMP Toy Code
Я использую GCC v13.2 с -O3 -fopenmp
#include
#include
#include
#include // std::move
#include
#include
#include
#include

struct Ints
{
// is just for the toy example. The real code has proper objects.
std::set vals;

Ints (const std::set &vals) : vals(vals) {}

bool operator < (const Ints &that) const
{
return vals < that.vals;
}

// Build Ints objects from this and add them to `set'.
void add_variants (std::set &set) const
{
for (int i : vals)
{
Ints y (*this);
y.vals.insert (i + 2);
set.emplace (std::move (y));

Ints z (*this);
z.vals.insert (i - 1);
set.emplace (std::move (z));
}
}
// Approach 1: Same, but try parallel for to speed up.
void add_variants_omp (std::set &set) const
{
// Build a vector with addresses so we can omp parallel for
// over it. Use a vector of const int* (and not of int)
// since that resembles the non-toy algorithm where we have
// a collection of objects.
std::vector v;
v.resize (vals.size ());
int j = 0;
for (const auto &i : vals)
v[j++] = &i;

#pragma omp parallel for
for (size_t j = 0; j < v.size (); ++j)
{
Ints y (*this);
y.vals.insert (*(v[j]) + 2);
#pragma omp critical
set.emplace (std::move (y));

Ints z (*this);
z.vals.insert (*(v[j]) - 1);
#pragma omp critical
set.emplace (std::move (z));
}
}
// Approach 2: Same, but instead of adding to a set, return a set of all
// morphed Ints.
std::set get_variants () const
{
std::set set;
for (int i : vals)
{
Ints y (*this);
y.vals.insert (i + 2);
set.emplace (std::move (y));

Ints z (*this);
z.vals.insert (i - 1);
set.emplace (std::move (z));
}
return set;
}
// Approach 3: Same, but append to a common list.
void add_variants_mutex (std::list &list, std::mutex &mut) const
{
for (int i : vals)
{
Ints y (*this);
y.vals.insert (i + 2);

Ints z (*this);
z.vals.insert (i - 1);
mut.lock ();
list.emplace_back (std::move (y));
list.emplace_back (std::move (z));
mut.unlock ();
}
}
};

std::ostream& operator

Подробнее здесь: https://stackoverflow.com/questions/798 ... p-parallel