Skip to main content
Removed the calls to wait because they're unnecessary
Source Link
Yuushi
  • 11.1k
  • 2
  • 31
  • 66
template <typename Iterator> typename std::iterator_traits<Iterator>::value_type parallel_sum(Iterator begin, Iterator end) { using T = typename std::iterator_traits<Iterator>::value_type; auto midpoint = begin + std::distance(begin, end) / 2; std::future<T> f1 = std::async(std::launch::async, adder<Iterator>, begin, midpoint); std::future<T> f2 = std::async(std::launch::async, adder<Iterator>, midpoint, end);    f1.wait(); f2.wait();  return f1.get() + f2.get(); } 
template <typename Iterator> typename std::iterator_traits<Iterator>::value_type parallel_sum(Iterator begin, Iterator end) { using T = typename std::iterator_traits<Iterator>::value_type; auto midpoint = begin + std::distance(begin, end) / 2; std::future<T> f1 = std::async(std::launch::async, adder<Iterator>, begin, midpoint); std::future<T> f2 = std::async(std::launch::async, adder<Iterator>, midpoint, end);    f1.wait(); f2.wait();  return f1.get() + f2.get(); } 
template <typename Iterator> typename std::iterator_traits<Iterator>::value_type parallel_sum(Iterator begin, Iterator end) { using T = typename std::iterator_traits<Iterator>::value_type; auto midpoint = begin + std::distance(begin, end) / 2; std::future<T> f1 = std::async(std::launch::async, adder<Iterator>, begin, midpoint); std::future<T> f2 = std::async(std::launch::async, adder<Iterator>, midpoint, end); return f1.get() + f2.get(); } 
std::future<T> f2 = std::async(std::launch::async, adder<Iterator>, midpoint+1, end); to std::future<T> f2 = std::async(std::launch::async, adder<Iterator>, midpoint, end); and std::launch_async to std::launch::async
Source Link
template <typename Iterator> typename std::iterator_traits<Iterator>::value_type parallel_sum(Iterator begin, Iterator end) { using T = typename std::iterator_traits<Iterator>::value_type; auto midpoint = begin + std::distance(begin, end) / 2; std::future<T> f1 = std::async(std::launch_asynclaunch::async, adder<Iterator>, begin, midpoint); std::future<T> f2 = std::async(std::launch_asynclaunch::async, adder<Iterator>, midpoint + 1, end); f1.wait(); f2.wait(); return f1.get() + f2.get(); } 
template <typename Iterator> typename std::iterator_traits<Iterator>::value_type parallel_sum(Iterator begin, Iterator end) { using T = typename std::iterator_traits<Iterator>::value_type; auto midpoint = begin + std::distance(begin, end) / 2; std::future<T> f1 = std::async(std::launch_async, adder<Iterator>, begin, midpoint); std::future<T> f2 = std::async(std::launch_async, adder<Iterator>, midpoint + 1, end); f1.wait(); f2.wait(); return f1.get() + f2.get(); } 
template <typename Iterator> typename std::iterator_traits<Iterator>::value_type parallel_sum(Iterator begin, Iterator end) { using T = typename std::iterator_traits<Iterator>::value_type; auto midpoint = begin + std::distance(begin, end) / 2; std::future<T> f1 = std::async(std::launch::async, adder<Iterator>, begin, midpoint); std::future<T> f2 = std::async(std::launch::async, adder<Iterator>, midpoint, end); f1.wait(); f2.wait(); return f1.get() + f2.get(); } 
Source Link
Yuushi
  • 11.1k
  • 2
  • 31
  • 66

Firstly, it's a good first attempt at writing some threaded code. The major sticking point is that you're passing in an int & and returning void. Of course, std::thread will just run some code and won't return you a result. However, within the C++11 threading library, there are a number of things you can use that will allow you to return results, instead of having to use std::ref and reference parameters.

Before tackling that, let's look at the adder function itself. I'm going to go through a sequence of improvements that can be made to it. Firstly, you should try and use the correct type to index into a std::vector:

using size_type = std::vector<int>::size_type; int adder( const std::vector<int> & v, size_type begin, size_type end) { for( ; begin < end; ++begin ) { result = result + v.at( begin ); } } 

This is ok, but it could be a lot more generic: What if the values aren't stored in a std::vector? Instead, template this so that it can use anything that supports an iterator concept:

template <typename Iterator> int adder(Iterator begin, Iterator end) { int result = 0; for(auto it = begin; it != end; ++it) { result += *it; } return result; } 

Ok, getting there, but we can still improve this quite a bit: what if we want to sum any kind of numeric type? (Note this will require an #include <iterator>):

template <typename Iterator> std::iterator_traits<Iterator>::value_type adder(Iterator begin, Iterator end) { std::iterator_traits<Iterator>::value_type result; for(auto it = begin; it != end; ++it) { result += *it; } return result; } 

Ok, so we're not locked into a vector or an int type anymore. However, this pattern of summing up a bunch of values is really common, and there is library functionality that takes care of it for us: std::accumulate (note that this needs an #include <algorithm>):

template <typename Iterator> typename std::iterator_traits<Iterator>::value_type adder(Iterator begin, Iterator end) { using T = typename std::iterator_traits<Iterator>::value_type; return std::accumulate(begin, end, T()); } 

Now for the threading part.

The C++11 threading library has a really handy function called std::async. This allows you to run some piece of code in a thread, and retrieve a result from it. It will give you back what is known as a std::future (note that this needs an #include <future>):

template <typename Iterator> typename std::iterator_traits<Iterator>::value_type parallel_sum(Iterator begin, Iterator end) { using T = typename std::iterator_traits<Iterator>::value_type; auto midpoint = begin + std::distance(begin, end) / 2; std::future<T> f1 = std::async(std::launch_async, adder<Iterator>, begin, midpoint); std::future<T> f2 = std::async(std::launch_async, adder<Iterator>, midpoint + 1, end); f1.wait(); f2.wait(); return f1.get() + f2.get(); } 

We then use this as follows:

int main() { std::vector<int> v; for(int i = 0; i < 100000; ++i) { v.push_back(i); } int total = parallel_sum(v.begin(), v.end()); std::cout << total << "\n"; } 

There's probably too much to absorb here in one go, but I'll break down the main points:

  • Try and make your functions work with the facilities provided by the standard library. Iterators permeate the container/algorithm side of it - if you can, try and work with iterators instead of directly with containers.
  • Look for functionality in the standard library that can help you with common tasks, such as std::accumulate.
  • With threading, if you want to get results back, prefer to use std::async instead of passing parameters by reference to store results.