Simple threaded summation, review please.

**manasij7479** · 06-06-2012

Here is my attempt to perform the sum of elements between two iterators, with n threads , using C++11 std::thread `s.

It appears to work correctly, with odd, even or zero length of input.

Code:

namespace mm
{
    template<typename Iterator, typename T>
    T sum(Iterator begin, Iterator end, T& t)  // It could do without the reference..added for easy thread operations below
    {
        while(begin!=end)
        {
            t+=*begin++;
        }
        return t;
    }

    template<typename Iterator, typename T >
    T threaded_sum(Iterator begin, Iterator end,T& t,short int n = std::thread::hardware_concurrency())
    {
        if(n<1)n=2;//n == no. of threads
        
        int span = (end-begin)/n; //Length of the array handled by all but the nth thread
        

        std::vector<std::pair<Iterator,Iterator>> work;//Begin,end iterators for each thread
        
        Iterator temp;//for retaining the begin iterator for the last thread
        for(int i=0; i< n-1 ; ++i)
        {
            static Iterator x(begin),y;
            y = x+span;
            work.push_back({x,y});
            x = y;
            temp = y;
        }
        work.push_back({temp,end}); //Done out of the loop to include remainders 

        std::vector<T> results(n);
        std::vector<std::thread> threads;

        for(int i=0;i<n;++i)
        {
            threads.push_back
            (
                std::thread
                (
                    sum<Iterator,T>,
                    work[i].first,
                    work[i].second,
                    std::ref(results[i])
                )
            );
        }
        for(auto& x:threads)x.join();

        sum(results.begin(),results.end(),t);
        return t;
    }

}

Usage:

Code:

int main()
{
    std::vector<int> foo = {1,2,3,4,5,6,7,8,9,10};
    int x(0);
    std::cout<<mm::threaded_sum(foo.begin(),foo.end(),x);
    return 0;
}

[Edit]Don't forget the C++11 and pthread flags if any of you want to compile the code.[/Edit]

I'm seriously starting to learn about concurrent programming from scratch after some half-hearted attempts for the past months and realizing that it is a whole new paradigm for me and not just another API.
(Some library/Language independent book recommendations would be great !)

**phantomotap** · 06-06-2012

O_o

That's, overall, a nice use of C++11.

A few things you can improve (for funsies or experience):

With just a little more cleverness you can make this generic enough that the underlying type doesn't need a default constructor.

With a little more abstract design you can make the operations arbitrarily complex instead of just assignment under the condition that the operations is without shared state or knows to protect itself.

If you are going to be working a lot with C++11 thread facilities you may as well make join on a collection an abstract operation.

A few picky things:

No. It should not be done without the reference. The reference gives you a little because you are using unknown types.

Using a `short int' in an interface because the range isn't going to be larger than that is silly. The valid range precondition check must be noted, and possibly performed, regardless of the types range. It also happens that just `int' works better in a lot ways that I'm not going to talk about.

Why have you made a couple of the iterators static? There is no reason not to redesign so that the loop is a natural expression of the algorithm without that forced awkwardness. You need to use `std::swap' (use `using std::swap') to implement this in the chance that the iterators are expensive.

Your iterators in the interface are generic types so you must not use raw adjustments directly without confirming the iterator traits. A better approach would be to use `std::advance'.

Some library/Language independent book recommendations would be great !

The books I learned from are major textbooks far to expensive to recommend.

However, searching for "concurrency patterns" or similar will give you good results to start.

Soma

**manasij7479** · 06-06-2012

So, this

Code:

      Iterator temp;//for retaining the begin iterator for the last thread
        for(int i=0; i< n-1 ; ++i)
        {
            static Iterator x(begin),y;
            y = x+span;
            work.push_back({x,y});
            x = y;
            temp = y;
        }
        work.push_back({temp,end}); //Done out of the loop to include remainders

should better be

Code:

      Iterator x(begin),y;
        for(int i=0; i < n-1 ; ++i)
        {
            y = x;
            std::advance(y,span);
            work.push_back({x,y});
            std::swap(x,y);
        }
        work.push_back({x,end}); //Done out of the loop to include remainders

?
Though, I find the first version easier to follow mentally... for some reason (probably lack of sleep now..!).

**phantomotap** · 06-06-2012

easier to follow

^_^

You want easy to follow don't get involved with concurrency and generic programming.

Soma

**manasij7479** · 06-06-2012

Originally Posted by phantomotap

With a little more abstract design you can make the operations arbitrarily complex instead of just assignment under the condition that the operations is without shared state or knows to protect itself.

That point went tangentially above my head.

If you are going to be working a lot with C++11 thread facilities you may as well make join on a collection an abstract operation.

What exactly do you mean by an "abstract operation" ?
Using for_each or making a generic function that takes any container of std::threads to join all of them ?

**phantomotap** · 06-06-2012

That point went tangentially above my head.

Consider an overload of your function that takes an unknown type (by value or optionally constant reference if you want to put in the work) which may be used as a a binary function with a generic but unspecified signature returning an unspecified but convertible type.

I'll wait here until you think about it for a moment.

Okay. If you still don't get the suggestion look at `std::accumulate'.

Using for_each or making a generic function that takes any container of std::threads to join all of them ?

I was suggesting something more along the lines of the later; it will eventually serve as part of a "thread pool" mechanic that you will eventually make.

Soma

**manasij7479** · 06-06-2012

That would be easy to implement....with an extra template argument...and no change needed in the body of the threaded function.
The only change will be in the normal function "t+=*begin++;" to "t = foo(t,*begin++);".
Or, am I missing something ?

**phantomotap** · 06-06-2012

I didn't say it would be a difficult task.

That's more or less the basic idea for mathematics operations.

Soma

**antred** · 06-06-2012

Originally Posted by phantomotap

Using a `short int' in an interface because the range isn't going to be larger than that is silly. The valid range precondition check must be noted, and possibly performed, regardless of the types range. It also happens that just `int' works better in a lot ways that I'm not going to talk about.

Why not unsigned int? That's what std::thread::hardware_concurrency() returns and it makes sense. I mean you can't really have a negative number of concurrent threads, can you?

**Codeplug** · 06-07-2012

>> It also happens that just `int' works better in a lot ways that I'm not going to talk about.
You can read more about that in the link below:
unsigned int usage

gg

Thread: Simple threaded summation, review please.

Thread Tools

Search Thread

Display

Simple threaded summation, review please.

Similar Threads

simple summation question

Review my simple Lexer please..

Going from single-threaded to multi-threaded

Simple calculator -- code review

Help With Simple Summation...