Summing values in a vector using threads

Question

This is my very first program that using threads. I use C++11 standard threads and I run it on Linux.

The program creates two threads that sums all the elements in a vector together. The first created thread sums the left half of the vector and the other thread sums the right part of the vector.

The main thread runs until both are done, adds the two sums together and then print the sum.

#include <iostream>
#include <vector>
#include <thread>
void
adder( const std::vector<int> & v, int begin, int end, int & result)
{
 for( ; begin < end; ++begin )
 {
 result = result + v.at( begin );
 }
}
int
main()
{
 int sum_left = 0;
 int sum_right = 0;
 std::vector<int> v( 100000000,1); //100 millions
 int v_size = v.size();
 std::thread t1( adder, v, 0,v_size/2 , std::ref(sum_left) );
 std::thread t2( adder, v, v_size/2, v_size, std::ref(sum_right) );
 t1.join();
 t2.join();
 int sum_total = sum_left + sum_right;
 std::cout << sum_total << '\n';
 return 0;
}

Answer 1

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, end);
 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.

• Morwenn: I love this review, it is comprehensive and easy to read :)
• Morwenn: However, if I'm not mistaken, you can drop the calls to std::future<>::wait since the method get should already call wait.
• Yuushi: @Morwenn Yep, you're right. Fixed.
• foobar: Very nice review. There is so much to learn in this. thanks.
• mayankk2308: This was an excellent primer on C++ threading optimization. Thank you!