`std::find` returns the first matching element, or the range end if none matches. Because it can stop as soon as a match is found, a parallel search should let other workers stop too; otherwise, a serial search may finish sooner. section 8.5.2
Stopping other workers
Searching attic boxes for a photograph illustrates early completion: once one person finds it, the others can stop. In a parallel search, an atomic flag can signal that the answer is known. section 8.5.2
Listing 8.9. An implementation of a parallel find algorithm
template<typename Iterator,typename MatchType>
Iterator parallel_find(Iterator first,Iterator last,MatchType match)
{
struct find_element #1
{
void operator()(Iterator begin,Iterator end,
MatchType match,
std::promise<Iterator>* result,
std::atomic<bool>* done_flag)
{
try
{
for(;(begin!=end) && !done_flag->load();++begin) #2
{
if(*begin==match)
{
result->set_value(begin); #3
done_flag->store(true); #4
return;
}
}
}
catch(...) #5
{
try
{
result->set_exception(std::current_exception()); #6
done_flag->store(true);
}
catch(...) #7
{}
}
}
};
unsigned long const length=std::distance(first,last);
if(!length)
return last;
unsigned long const min_per_thread=25;
unsigned long const max_threads=
(length+min_per_thread-1)/min_per_thread;
unsigned long const hardware_threads=
std::thread::hardware_concurrency();
unsigned long const num_threads=
std::min(hardware_threads!=0?hardware_threads:2,max_threads);
unsigned long const block_size=length/num_threads;
std::promise<Iterator> result; #8
std::atomic<bool> done_flag(false); #9
std::vector<std::thread> threads(num_threads-1);
{ #10
join_threads joiner(threads);
Iterator block_start=first;
for(unsigned long i=0;i<(num_threads-1);++i)
{
Iterator block_end=block_start;
std::advance(block_end,block_size);
threads[i]=std::thread(find_element(), #11
block_start,block_end,match,
&result,&done_flag);
block_start=block_end;
}
find_element()(block_start,last,match,&result,&done_flag); #12
}
if(!done_flag.load()) #13
{
return last;
}
return result.get_future().get(); #14
}
!@%STYLE%@!
{"css":"{\"css\": \"font-weight: bold;\"}","target":"[[{\"line\":3,\"ch\":70},{\"line\":3,\"ch\":72}],[{\"line\":48,\"ch\":70},{\"line\":48,\"ch\":72}],[{\"line\":55,\"ch\":70},{\"line\":55,\"ch\":72}],[{\"line\":60,\"ch\":70},{\"line\":60,\"ch\":72}],[{\"line\":62,\"ch\":70},{\"line\":62,\"ch\":72}],[{\"line\":66,\"ch\":70},{\"line\":66,\"ch\":72}],[{\"line\":12,\"ch\":70},{\"line\":12,\"ch\":72}],[{\"line\":16,\"ch\":70},{\"line\":16,\"ch\":72}],[{\"line\":17,\"ch\":70},{\"line\":17,\"ch\":72}],[{\"line\":22,\"ch\":70},{\"line\":22,\"ch\":72}],[{\"line\":26,\"ch\":70},{\"line\":26,\"ch\":72}],[{\"line\":29,\"ch\":70},{\"line\":29,\"ch\":72}],[{\"line\":45,\"ch\":70},{\"line\":45,\"ch\":72}],[{\"line\":46,\"ch\":70},{\"line\":46,\"ch\":72}],[{\"line\":48,\"ch\":70},{\"line\":48,\"ch\":73}],[{\"line\":55,\"ch\":70},{\"line\":55,\"ch\":73}],[{\"line\":60,\"ch\":70},{\"line\":60,\"ch\":73}],[{\"line\":62,\"ch\":70},{\"line\":62,\"ch\":73}],[{\"line\":66,\"ch\":70},{\"line\":66,\"ch\":73}]]"}
!@%STYLE%@!
See a parallel implementation that shares a result promise and an atomic flag so workers can stop after a match is found. section 8.5.2
