# Computing sum of elements with mutlithreads

#include <iostream>
#include <vector>
#include <atomic>

void func(std::atomic<long long>& sum, const std::vector<long long>& vec)
{
long long result(0);
for(int i(0); i < vec.size(); ++i){
result += vec[i];
}
sum += result;
}

int main()
{
// create a variable to hold the result.
std::atomic<long long> sum(0);

// generate numbers
std::vector<long long> num;
for(long long i(1); i<=10000000; ++i)
num.push_back(i);

// each thread should compute the sum of some numbers
long long k(0);
for(int i(0); i<1000; ++i){
// extract elements from the big elements vector (i.e. in this example, each thread handles 10,000)
std::vector<long long> temp(&num[k],&num[k+10000]);
k+=10000;
}
t.join();
}
std::cout << "Sum = " << sum << std::endl;

return 0;
}


I would like to know if my code can be enhanced more. The comments should be enough to explain the code. Thank you.

• This probably gonna perform worse than st approach. Try rolling version, e.g. threads perform sum on range on local number, then master thread sums them again – Incomputable Jul 19 '17 at 3:26
• @Incomputable I don't understand your comment. What is st approach? What is rolling version? – CroCo Jul 19 '17 at 3:41
• st stands for single thread. Will post an answer soon then – Incomputable Jul 19 '17 at 3:43
• You are missing the point. The whole point is to use multithreads. – CroCo Jul 19 '17 at 3:45
• yeah, I'll use multiple threads. Can you use more recent version of C++? Like 14, or even better 17. – Incomputable Jul 19 '17 at 3:46

## Better algorithm

So the main practical improvement would be to use a roll. Atomics are very slow if multiple threads take turns in accessing it in clockwise/anticlockwise manner, e.g. like a carousel. Let's define the algorithm:

1. Retrieve number of physical threads, e.g. cores. Sometimes it is not available, so setting it to 4 would be a pretty good guess these days. Number of threads visible to OS would be important if algorithm would have diverse workload, but this is not the case here.

2. While not reached the end of the vector:

2.1 Allocate all physical threads to sum 1000 numbers in the range. The number might need to be fine tuned, but I believe this already should outweigh the cost of the thread creation.

2.2. Sum the results of each number into result.

The process is actually much harder than it looks like. One has to create a vector of std::promises and get std::futures of them, then create small function that would set the future from outside, then join threads ... Well I guess you got the point. This question should help out with that.

## Compute in place

Since the algorithm does read-only access on the container, it could be just passed by reference. The master function could schedule the work and then collect the result.

## Iterators

I believe that if the properties of std::vector are not exploited, it doesn't make much sense to hardcode it. Iterators provide powerful abstraction, though they take time to get used to them. Also, they could be used to delegate to std::accumulate, e.g. in the small function it would just call accumulate on range.

## More power

I believe the function could be extended without much effort and still retain compatibility and easy of use of original one. Something like this:

template <typename RandomAcessIt,
typename T = std::iterator_traits<RandomAcessIt>::value_type,
typename BinaryOp = std::plus<>>
T accumulate(parallel_compute_tag, RandomAcessIt first, RandomAcessIt last, T initvalue = {}, BinaryOp op = {})


So default would still be +, but it could be changed to whatever heart likes. And then instead of using + one could just op(lhs, rhs).

## Rolling

Here is a terrible picture (I made my best at it)

As you can see, the scheduled threads "roll into" master thread to provide the result. That is why I said rolling approach. I don't really know the term for this though.