Concurrency in Modern C++ - Cumulative sum of a vector using two threads

tutorial1

Modern C++ Concurrency - Cumulative sum of a vector - Part 1

In this tutorial we will write a c++ code that will take as input a large list of numbers and it will return the cumulative sum of them.
In order to speed up the process we will write this code so it uses two threads. In the process we will learn how to use a callable object with the operator() redefined to create and run a thread.

Exercice description

So we want to write a multithread program that with help of two threads will sum up a of numbers. For the sake of simplicity the vector is generated s.t. is contains numbers 1,2...n using the following two lines

vector<int> numbers(size);
iota (begin(numbers), end(numbers), 1);

Then two tasks are created of type sum_task. Note that sum_task has the operator() defined. This is the function that thread will execute once we will create it using a sum_task object.
Alsdo note that sum_task need two iterators to be creator because each thread will be responsible for the sum of a specific portion of the list of numbers. The first thread will sum of the first half while the second thread will sum up the remaining ones.
The following code will create two sum_task object each of them iniziatialized so to sum the right portion of the list

    sum_task<It> task1(
        numbers.begin(), 
        numbers.begin()+numbers.size()/2
    );
    sum_task<It> task2(
        numbers.begin()+numbers.size()/2,
        numbers.end()
    );

As you can see task1 start from the begin of the list and stops right in the middle and task2 starts from the middle of the list and will sum all the numers till the end.

Subsequentelly the main creates two threads are created using task1 and task2 and performs the sum of the whole array sequentially so we can check if te result from the threads is correct. Finally it waits for the two threads to finish. It is important to note that after t1 and t2 are created the main continues with the next instructions. We have effectively three threads running, doing work.

//create the two threads
thread t1(ref(task1)); 
thread t2(ref(task2)); 
//calculate the sum of the vector serially 
unsigned long long sum = 0;
for(const auto v : numbers){
    sum+=v;
}
//main has no more work to do 
//it wait for completition of the child threads
t1.join(); 
t2.join(); 

Last thing it shoud be noted is the way we pass the sum_task object to the thread constructor. We use ref so all modification on the object performed by the thread will be reflected in the main thread. The following code will create two threads using copies of task1 and task2!

//create the two threads
thread t1(task1); 
thread t2(task2); 

Te following is the full listing for this tutorial.

#include <iostream>
#include <thread> 
#include <vector>

using namespace std;

template <typename It>
struct sum_task {
 private:
  const It start, finish;
  unsigned long long result;

 public:
  sum_task(const It& s, const It& f) 
  : start(s), finish(f), result(0)
  {};

  void operator()() {
    auto it = start;
    while (it != finish) {
      result += *it++;
    }
  }

  unsigned long long get_result(){
    return result;
  }

};

int main(int argc, char* argv[]) {
    const unsigned long size = stoul(argv[1]);

    vector<int> numbers(size);
    iota (begin(ans), ans, 1);

    using It = decltype(numbers.begin());
    sum_task<It> task1( numbers.begin(), 
                        numbers.begin()+numbers.size()/2
                      );
    sum_task<It> task2( numbers.begin()+numbers.size()/2,
                        numbers.end()
                      );
    //create the two threads
    thread t1(ref(task1)); 
    thread t2(ref(task2)); 

    //threads are up and running at this point
    //running concurrently with the main thread


    //calculate the sum of the vector serially 
    unsigned long long sum = 0;
    for(const auto v : numbers){
        sum+=v;
    }
    //main as no more work to do 
    //it wait for completition of the child threads
    t1.join(); 
    t2.join(); 

    //threads completed
    //let's check the result
    unsigned long long thread_res = 
        task1.get_result() + task2.get_result();

    cout<<"Thread    : "<<thread_res<<endl;
    cout<<"Reference : "<<sum<<endl;
    if(sum==thread_res){
        cout<<"Yes! Result is correct"<<endl;
    }
    else{
        cout<<"Oops :( .... Result is wrong"<<endl;
    }

  return 0;
}

Compilation and running

As usual we can compile this code using the following:

clang++ -O2 -std=c++14 -g -fsanitize=address -Wall  -Wextra -pthreads -o tutorial1 hello.cpp

(19:46:19)[knotman@archazzo]
→ ./tutorial1  1234567
Thread    : 762078456028
Reference : 762078456028
Yes! Result is correct

The sum of the numbers 1,2,3....n can be calculated with the following formula: (n*(n+1))/2.
(1234567*(1234567+1))/2 = 762078456028
Our program seems to be working perfectly! Well done.

References

References

cppreference.com, iota

Be the first to leave a comment. Don’t be shy.

Join the Discussion

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>