Like Tree1Likes
  • 1 Post By phantomotap

Simple threaded summation, review please.

This is a discussion on Simple threaded summation, review please. within the C++ Programming forums, part of the General Programming Boards category; Here is my attempt to perform the sum of elements between two iterators, with n threads , using C++11 std::thread ...

  1. #1
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498

    Simple threaded summation, review please.

    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 !)
    Last edited by manasij7479; 06-06-2012 at 12:48 PM.
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  2. #2
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,172
    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

  3. #3
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    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..!).
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  4. #4
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,172
    easier to follow
    ^_^

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

    Soma
    Elkvis likes this.

  5. #5
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    Quote Originally Posted by phantomotap View Post
    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 ?
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  6. #6
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,172
    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

  7. #7
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    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 ?
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  8. #8
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,172
    I didn't say it would be a difficult task.

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

    Soma

  9. #9
    Registered User antred's Avatar
    Join Date
    Apr 2012
    Location
    Germany
    Posts
    227
    Quote Originally Posted by phantomotap View Post
    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?

  10. #10
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,649
    >> 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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. simple summation question
    By uural4792 in forum C Programming
    Replies: 16
    Last Post: 10-13-2011, 01:04 AM
  2. Review my simple Lexer please..
    By manasij7479 in forum C++ Programming
    Replies: 4
    Last Post: 08-19-2011, 10:56 AM
  3. Going from single-threaded to multi-threaded
    By Dino in forum C Programming
    Replies: 11
    Last Post: 03-23-2008, 01:14 PM
  4. Simple calculator -- code review
    By jafet in forum C++ Programming
    Replies: 7
    Last Post: 09-22-2006, 11:49 PM
  5. Help With Simple Summation...
    By TOPFLOR in forum C Programming
    Replies: 19
    Last Post: 08-09-2006, 10:50 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21