c++ - Parallel search of distinct values? -

c++ - Parallel search of distinct values? -

consider next code :

// preprocessor #include <iostream> #include <chrono> #include <thread> #include <algorithm> #include <mutex> #include <random> // main function int main() { // random vector of size 100 10 different random values std::vector<unsigned int> vector = make_random_vector(100, 10); // @ end, result should 10 different random values std::vector<unsigned int> result; // mutex deals concurrency std::mutex mutex; // parallel search parallel_for_each(vector.begin(), vector.end(), [=, &result, &mutex](const unsigned int& i){ /* critical section: begin */ // if current element not yet in resulting vector, inserts if (!std::binary_search(result.begin(), result.end(), i)) { mutex.lock(); result.insert(std::lower_bound(result.begin(), result.end(), i), i); mutex.unlock(); } /* critical section: end */ }); // unique values result.erase(std::unique(result.begin(), result.end()), result.end()); // display result std::for_each(result.begin(), result.end(), [](const unsigned int& i){ std::cout<<i<<std::endl; }); // finalization homecoming 0; }

the goal find n distinct values in vector in parallel.

my question : preceding code ok (no problem of concurrency), , if not, how right ?

note: code has calls 2 functions :

parallel_for_each executes provided function on provided number of threads :

// parallel execution returning execution time in seconds template <class iterator, class function> double parallel_for_each(const iterator& first, const iterator& last, function&& function, const int nthreads = std::thread::hardware_concurrency()) { const std::chrono::high_resolution_clock::time_point tbegin = std::chrono::high_resolution_clock::now(); const long long int ntasks = std::max(static_cast<int>(1), nthreads); const long long int grouping = std::max(static_cast<long long int>(first < last), static_cast<long long int>((last-first)/ntasks)); std::vector<std::thread> threads; iterator = first; threads.reserve(ntasks); (it = first; < last-group; += group) { threads.push_back(std::thread([=, &last, &group, &function](){std::for_each(it, std::min(it+group, last), function);})); } std::for_each(it, last, function); std::for_each(threads.begin(), threads.end(), [](std::thread& current){current.join();}); homecoming std::chrono::duration_cast<std::chrono::duration<double> >(std::chrono::high_resolution_clock::now()-tbegin).count(); }

make_random_vector produces random vector of nelements nvalues different random values

// produces random vector of nelements nvalues different random values std::vector<unsigned int> make_random_vector(const unsigned int nelements, const unsigned int nvalues) { std::vector<unsigned int> vector(nelements); std::vector<unsigned int> values(nvalues); std::random_device device; std::mt19937 engine(device()); std::uniform_int_distribution<unsigned int> distribution1; std::uniform_int_distribution<unsigned int> distribution2(0, nvalues-1); std::for_each(values.begin(), values.end(), [=, &distribution1, &engine](unsigned int& i){i = distribution1(engine);}); std::for_each(vector.begin(), vector.end(), [=, &distribution2, &engine, &values](unsigned int& i){i = values[distribution2(engine)];}); homecoming vector; }

your code has problem, protect concurrent write access not read access of result.

a solution move mutex locking outside of if follow:

[=, &result, &mutex](const unsigned int& i){ std::lock_guard<std::mutex> lck (mutex); // if current element not yet in resulting vector, inserts if (!std::binary_search(result.begin(), result.end(), i)) { result.insert(std::lower_bound(result.begin(), result.end(), i), i); } }

but break purpose of parallel :/

an other solution work on different result set, , bring together result @ end of loop.

an other solution may variant of double-checked locking requires re-create result @ each insertion.

c++ c++11 concurrency parallel-processing mutex