Computing sum of elements with mutlithreads

Question

I'm reading about multithreads with C++. My code is to compute the sum of elements using multithread approach. The code is

#include <iostream>
#include <thread>
#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);

    // create vector of threads
    std::vector<std::thread> threads;

    // 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);
    //create 1,000 threads
    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;
        threads.push_back(std::thread{ func, std::ref(sum), temp });
    }
    for(auto& t : threads){
        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.

Answer 1

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.