Re: MT Design Question

Discussion in 'C++' started by Scott Meyers, Aug 24, 2010.

  1. Scott Meyers

    Scott Meyers Guest

    Paavo Helde wrote:
    > But there is a shared state, namely the results. When the worker thread
    > has found some result, it has to write it somewhere where the main thread
    > can find it.


    This is what a future is for. As I noted, my plan is for each search function
    to have its own future. In C++0x, callees write their result to a promise, and
    callers retrieve the result through a future. The state shared by a promise and
    future is internally synchronized, so there is no need for clients to use a
    mutex with it.

    > This location is shared and needs some MT protection, e.g. a
    > mutex. You might also want to maintain a counter of finished worker
    > threads to decide when they have all failed, this counter would be shared
    > as well.


    When all workers have finished, all their futures will be ready, so there is no
    need for a counter to determine that (although it could be convenient).

    Scott

    --
    * C++ and Beyond: Meyers, Sutter, & Alexandrescu, Oct. 24-27 near Seattle
    (http://cppandbeyond.com/)
    * License my training materials for commercial (http://tinyurl.com/yfzvkp9) or
    personal use (http://tinyurl.com/yl5ka5p).
     
    Scott Meyers, Aug 24, 2010
    #1
    1. Advertising

  2. Scott Meyers

    Scott Meyers Guest

    Paavo Helde wrote:
    > I see. I overlooked the usage of C++0x future<> in the OP. I am not
    > familiar with this feature, but it appears to be a higher level construct
    > having internal synchronisation.


    It also has the advantage that it can hold either a return value or an exception.

    Scott

    --
    * C++ and Beyond: Meyers, Sutter, & Alexandrescu, Oct. 24-27 near Seattle
    (http://cppandbeyond.com/)
    * License my training materials for commercial (http://tinyurl.com/yfzvkp9) or
    personal use (http://tinyurl.com/yl5ka5p).
     
    Scott Meyers, Aug 25, 2010
    #2
    1. Advertising

  3. Scott Meyers

    James Kanze Guest

    On Aug 25, 12:24 am, Paavo Helde <> wrote:
    > Scott Meyers <> wrote
    > innews:i51fus$hft$:


    > > Paavo Helde wrote:
    > >> But there is a shared state, namely the results. When the
    > >> worker thread has found some result, it has to write it
    > >> somewhere where the main thread can find it.


    > > This is what a future is for. As I noted, my plan is for
    > > each search function to have its own future. In C++0x,
    > > callees write their result to a promise, and callers
    > > retrieve the result through a future. The state shared by
    > > a promise and future is internally synchronized, so there is
    > > no need for clients to use a mutex with it.


    > I see. I overlooked the usage of C++0x future<> in the OP.
    > I am not familiar with this feature, but it appears to be
    > a higher level construct having internal synchronisation.


    Yes. The intent, if I understand it correctly, is to
    encapsulate the creation of the thread and its join. The
    results data are set in the thread, and only read after the join
    in the creating thread.

    And again, IIUC, Scott's problem can be summarized as "you can
    only wait for one future at a time". You can poll them, in
    a loop, but Scott, very understandably, doesn't want to do that.

    I'm not as familiar as I'd like to be with the proposed
    threading in the standard, but I have handled a similar problem
    with Posix threads: I made the threads detached (so no join was
    available), and used a (single) condition to communicate, with
    a table of results, one per thread.

    --
    James Kanze
     
    James Kanze, Aug 25, 2010
    #3
  4. Scott Meyers

    Scott Meyers Guest

    James Kanze wrote:
    > Yes. The intent, if I understand it correctly, is to
    > encapsulate the creation of the thread and its join. The
    > results data are set in the thread, and only read after the join
    > in the creating thread.


    This isn't quite true. The calling thread can read the future as soon as it's
    set by the callee (via the corresponding promise). The callee thread may then
    run for a while longer, e.g., to invoke destructors of local objects and
    thread-local objects. If the thread runs detached, there may never be a join,
    although that complicates matters at program shutdown.

    > I'm not as familiar as I'd like to be with the proposed
    > threading in the standard, but I have handled a similar problem
    > with Posix threads: I made the threads detached (so no join was
    > available), and used a (single) condition to communicate, with
    > a table of results, one per thread.


    This sounds like your design had the master thread wait until all worker threads
    were done, i.e., until the table was completely filled in. Is that correct? My
    problem is more along the lines of wanting to wake the master when any entry in
    the table is filled in with a non-exception result. But that just pushes the
    notification problem into the table object: how is it to know when a thread has
    posted a non-exception result if it doesn't use polling?

    Scott

    --
    * C++ and Beyond: Meyers, Sutter, & Alexandrescu, Oct. 24-27 near Seattle
    (http://cppandbeyond.com/)
    * License my training materials for commercial (http://tinyurl.com/yfzvkp9) or
    personal use (http://tinyurl.com/yl5ka5p).
     
    Scott Meyers, Aug 25, 2010
    #4
  5. Francesco S. Carta, Aug 25, 2010
    #5
  6. Scott Meyers

    Scott Meyers Guest

    Paavo Helde wrote:
    > Which makes it more high-level in some sense. And this exception throwing
    > is not useful anyway in this case as far as I can see. One does not want
    > to trigger an exception if another thread can still produce a result


    In the scenario I'm discussing, if one thread throws, it has no effect on other
    threads. The exception for that thread will just be stored in the thread's
    future. The other threads will continue to run.

    > if all fail, one wants to throw a new exception instead (possibly
    > combining information from all of the worker thread exceptions).


    And the caller can do that if it wants to. It can just do a get() on each
    future, catch any exception that may be present, then use whatever logic it
    wants to to decide what, if anything, should be thrown from there.

    > In other words, in my experience an ordinary mutex and condition would
    > work nicely here, with a protected result location an and a thread
    > counter.


    So you'd run all searches concurrently, passing them all a common result
    location to write to. What would you do if all ended by throwing an exception?
    How would you distinguish "none of the searches found anything" from "all the
    searches ended by throwing an exception"?

    Scott

    --
    * C++ and Beyond: Meyers, Sutter, & Alexandrescu, Oct. 24-27 near Seattle
    (http://cppandbeyond.com/)
    * License my training materials for commercial (http://tinyurl.com/yfzvkp9) or
    personal use (http://tinyurl.com/yl5ka5p).
     
    Scott Meyers, Aug 25, 2010
    #6
  7. Scott Meyers

    Balog Pal Guest

    >> In other words, in my experience an ordinary mutex and condition would
    >> work nicely here, with a protected result location an and a thread
    >> counter.

    >
    > So you'd run all searches concurrently, passing them all a common result
    > location to write to.


    MT design is mostly about avoiding sharing as much as possible. It will
    involve extra sync primitives, extra lock operations, task switches.

    > What would you do if all ended by throwing an exception?


    And also extra complexity in cases like that. Race for time and space. With
    extra chances to overlook some interaction.

    I would not start considering it before having multiple (per-thread)
    locations is proved as an issue. What is hard to imagine even wth a system
    without dynamic allocation.
     
    Balog Pal, Aug 25, 2010
    #7
  8. "Paavo Helde" <> wrote in message
    news:Xns9DDFEF607DD9Cmyfirstnameosapriee@216.196.109.131...
    [...]
    >
    > If there is a way to wait for multiple future<> results, all this could
    > be done by the master thread instead, which can then sort out all this
    > ternary logic by itself. This might be a bit cleaner, especially in
    > regard of dealing with orphaned threads (those not yet finished when the
    > master thread returns the found result).


    This pseudo-code will only work when a future is obtained from a promise:
    ________________________________________________________
    struct complete
    {
    std::condition_variable m_cond;
    std::mutex m_mutex;
    };




    template<typename T>
    struct promise_ex
    {
    std::promise<T> m_promise;
    complete& m_complete;


    void set_value(T v)
    {
    m_complete.m_mutex.lock();
    m_promise.set_value(v);
    m_complete.m_mutex.unlock();
    m_complete.m_cond.notify_one();
    }
    };




    template<typename T>
    struct multi_wait
    {
    complete m_complete;
    linked_list<std::future<T>*> m_list;


    void push_future(std::future<T>* f)
    {
    m_list.push(f);
    }


    std::future<T>* wait()
    {
    std::future<T>* result = NULL;

    m_complete.m_mutex.lock();

    while (! m_list.is_empty())
    {
    for each std::future<T>* in m_list as f
    {
    if (f->is_ready())
    {
    result = f;
    m_list.pop(f);
    goto bailout;
    }
    }

    m_complete.m_cond.wait(m_complete.m_mutex);
    }

    bailout:
    m_complete.m_mutex.unlock();

    return result;
    }
    };
    ________________________________________________________




    That should allow a thread to wait on the result of multiple futures without
    spin-polling.
     
    Chris M. Thomasson, Aug 25, 2010
    #8
  9. Scott Meyers

    Scott Meyers Guest

    Chris M. Thomasson wrote:
    > ________________________________________________________
    > struct complete
    > {
    > std::condition_variable m_cond;
    > std::mutex m_mutex;
    > };
    >
    >
    >
    >
    > template<typename T>
    > struct promise_ex
    > {
    > std::promise<T> m_promise;
    > complete& m_complete;
    >
    >
    > void set_value(T v)
    > {
    > m_complete.m_mutex.lock();
    > m_promise.set_value(v);
    > m_complete.m_mutex.unlock();
    > m_complete.m_cond.notify_one();
    > }
    > };
    >
    >
    >
    >
    > template<typename T>
    > struct multi_wait
    > {
    > complete m_complete;
    > linked_list<std::future<T>*> m_list;
    >
    >
    > void push_future(std::future<T>* f)
    > {
    > m_list.push(f);
    > }
    >
    >
    > std::future<T>* wait()
    > {
    > std::future<T>* result = NULL;
    >
    > m_complete.m_mutex.lock();
    >
    > while (! m_list.is_empty())
    > {
    > for each std::future<T>* in m_list as f
    > {
    > if (f->is_ready())
    > {
    > result = f;
    > m_list.pop(f);
    > goto bailout;
    > }
    > }
    >
    > m_complete.m_cond.wait(m_complete.m_mutex);
    > }
    >
    > bailout:
    > m_complete.m_mutex.unlock();
    >
    > return result;
    > }
    > };


    As I noted at the outset, I'm no MT expert, so my judgment is suspect, but this
    looks like it would work. I like that I can wait for the first result to come
    back, and if I don't like it (e.g., because it's an exception), I can easily
    continue waiting on the rest of the worker threads. Once I have a result I
    like, there a handy list of futures that tells me which workers need to be told
    to stop working. (There's no API for that in C++0x, but Chris's solution
    augments the promise API, so it's not surprising that we'd have to augment
    (i.e., build on) the standard future API, too.)

    Scott

    --
    * C++ and Beyond: Meyers, Sutter, & Alexandrescu, Oct. 24-27 near Seattle
    (http://cppandbeyond.com/)
    * License my training materials for commercial (http://tinyurl.com/yfzvkp9) or
    personal use (http://tinyurl.com/yl5ka5p).
     
    Scott Meyers, Aug 26, 2010
    #9
  10. "Scott Meyers" <> wrote in message
    news:i54bdb$n5s$...
    > Chris M. Thomasson wrote:
    > > ________________________________________________________

    [...]
    >
    > As I noted at the outset, I'm no MT expert, so my judgment is suspect, but
    > this looks like it would work. I like that I can wait for the first
    > result to come back, and if I don't like it (e.g., because it's an
    > exception), I can easily continue waiting on the rest of the worker
    > threads. Once I have a result I like, there a handy list of futures that
    > tells me which workers need to be told to stop working. (There's no API
    > for that in C++0x, but Chris's solution augments the promise API, so it's
    > not surprising that we'd have to augment (i.e., build on) the standard
    > future API, too.)


    Well, the technique should work fine. EXCEPT for the fact that I cannot seem
    to find a function that is able to poll a future for "readiness". It appears
    that the `future<>::is_ready()' function is nowhere to be found within the
    following draft:

    http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3092.pdf

    I see `future<>::valid()' function, but I don't quite know what that is
    supposed to do.

    DAMN! It appears that one has to call a timed wait with a timeout of zero in
    order to perform a poll operation wrt the readiness of a future. Why is
    `future<>::is_ready()' missing in this draft!?

    ;^(...



    SH#@I#@$I#@$I!!!!
     
    Chris M. Thomasson, Aug 26, 2010
    #10
  11. "Chris M. Thomasson" <> wrote in message
    news:Gcndo.83474$...
    [...]
    > DAMN! It appears that one has to call a timed wait with a timeout of zero
    > in order to perform a poll operation wrt the readiness of a future. Why is
    > `future<>::is_ready()' missing in this draft!?


    Humm... Perhaps I speak too fast here Scott. I think I can totally get
    around the fact that `future<>::is_ready()' does not seem to be included in
    the current C++0x draft. It should be simple. Let me think for a moment, and
    I will try to post a solution...
     
    Chris M. Thomasson, Aug 26, 2010
    #11
  12. Scott Meyers

    James Kanze Guest

    On Aug 25, 7:57 pm, Scott Meyers <> wrote:
    > James Kanze wrote:
    > > Yes. The intent, if I understand it correctly, is to
    > > encapsulate the creation of the thread and its join. The
    > > results data are set in the thread, and only read after the
    > > join in the creating thread.


    > This isn't quite true. The calling thread can read the future
    > as soon as it's set by the callee (via the corresponding
    > promise). The callee thread may then run for a while longer,
    > e.g., to invoke destructors of local objects and thread-local
    > objects. If the thread runs detached, there may never be
    > a join, although that complicates matters at program shutdown.


    In other words, it uses a condition in its implementation. (I'm
    not sure how this works with exceptions, though.)

    > > I'm not as familiar as I'd like to be with the proposed
    > > threading in the standard, but I have handled a similar problem
    > > with Posix threads: I made the threads detached (so no join was
    > > available), and used a (single) condition to communicate, with
    > > a table of results, one per thread.


    > This sounds like your design had the master thread wait until
    > all worker threads were done, i.e., until the table was
    > completely filled in. Is that correct?


    In my case, yes. In practice, the master thread was woken up
    each time a worker thread updated the table. It then checked
    whether it had all the information it needed, and went back to
    sleep if not.

    > My problem is more along the lines of wanting to wake the
    > master when any entry in the table is filled in with
    > a non-exception result. But that just pushes the notification
    > problem into the table object: how is it to know when
    > a thread has posted a non-exception result if it doesn't use
    > polling?


    When the worker thread updates the table, it locks the mutex,
    makes the modifications, then called pthread_cond_signal on the
    condition and freed the mutex. The master thread then woke up,
    and checked the conditions.

    --
    James Kanze
     
    James Kanze, Aug 26, 2010
    #12
  13. "Chris M. Thomasson" <> wrote in message
    news:Jfndo.83475$...
    > "Chris M. Thomasson" <> wrote in message
    > news:Gcndo.83474$...
    > [...]
    >> DAMN! It appears that one has to call a timed wait with a timeout of zero
    >> in order to perform a poll operation wrt the readiness of a future. Why
    >> is `future<>::is_ready()' missing in this draft!?

    >
    > Humm... Perhaps I speak too fast here Scott. I think I can totally get
    > around the fact that `future<>::is_ready()' does not seem to be included
    > in the current C++0x draft. It should be simple. Let me think for a
    > moment, and I will try to post a solution...


    Something like this should be able to "work around the problem":
    _______________________________________________________
    struct complete
    {
    std::condition_variable m_cond;
    std::mutex m_mutex;
    };




    // new data-structure...
    template<typename T>
    struct future_ex
    {
    std::future<T> m_future;
    bool m_ready; // == false;


    bool is_ready() const
    {
    return m_ready;
    }
    };




    template<typename T>
    struct promise_ex
    {
    std::promise<T> m_promise;
    complete& m_complete;

    /* new -> */ std::future_ex<T>& m_future_ex;


    void set_value(T v)
    {
    m_complete.m_mutex.lock();
    m_promise.set_value(v);

    /* new -> */ m_future_ex.m_ready = true;

    m_complete.m_mutex.unlock();
    m_complete.m_cond.notify_one();
    }
    };




    // new ... Changed all `std::future<T>' to `future_ex<T>'
    template<typename T>
    struct multi_wait
    {
    complete m_complete;
    linked_list<future_ex<T>*> m_list;


    void push_future(future_ex<T>* f)
    {
    m_list.push(f);
    }


    future_ex<T>* wait()
    {
    future_ex<T>* result = NULL;

    m_complete.m_mutex.lock();

    while (! m_list.is_empty())
    {
    for each future_ex<T>* in m_list as f
    {
    if (f->is_ready())
    {
    result = f;
    m_list.pop(f);
    goto bailout;
    }
    }

    m_complete.m_cond.wait(m_complete.m_mutex);
    }

    bailout:
    m_complete.m_mutex.unlock();

    return result;
    }
    };
    _______________________________________________________




    Humm... I now have to explicitly extend futures and promises in order for
    this `multi_wait<>' scheme to work out. Scott, is there truly no way to poll
    a `std::future<>' for completion such that a subsequent call to
    `std::future<>::get' will be 100% guaranteed to contain either a result or
    an exception? What is that `std::future<>::valid' call all about!?


    Confused again!

    ;^(...
     
    Chris M. Thomasson, Aug 27, 2010
    #13
  14. Scott Meyers

    Scott Meyers Guest

    On 8/25/2010 10:46 PM, Chris M. Thomasson wrote:
    > DAMN! It appears that one has to call a timed wait with a timeout of zero in
    > order to perform a poll operation wrt the readiness of a future. Why is
    > `future<>::is_ready()' missing in this draft!?


    I don't know that, but what's wrong with doing the wait with a zero timeout?
    AFAIK, that's the accepted way to poll.

    Scott

    --
    * C++ and Beyond: Meyers, Sutter, & Alexandrescu, Oct. 24-27 near Seattle
    (http://cppandbeyond.com/)
    * License my training materials for commercial (http://tinyurl.com/yfzvkp9) or
    personal use (http://tinyurl.com/yl5ka5p).
     
    Scott Meyers, Aug 27, 2010
    #14
  15. "Scott Meyers" <> wrote in message
    news:i57ham$h7j$...
    > On 8/25/2010 10:46 PM, Chris M. Thomasson wrote:
    >> DAMN! It appears that one has to call a timed wait with a timeout of zero
    >> in
    >> order to perform a poll operation wrt the readiness of a future. Why is
    >> `future<>::is_ready()' missing in this draft!?

    >
    > I don't know that, but what's wrong with doing the wait with a zero
    > timeout?


    A personal bias... :^(

    Perhaps the wait function... Ahhhh, I almost tried to optimize a very slow
    path...

    :^o

    > AFAIK, that's the accepted way to poll.


    It works.
     
    Chris M. Thomasson, Aug 27, 2010
    #15
  16. * Chris M. Thomasson, on 27.08.2010 09:49:
    > "Scott Meyers"<> wrote in message
    > news:i57ham$h7j$...
    >> On 8/25/2010 10:46 PM, Chris M. Thomasson wrote:
    >>> DAMN! It appears that one has to call a timed wait with a timeout of zero
    >>> in
    >>> order to perform a poll operation wrt the readiness of a future. Why is
    >>> `future<>::is_ready()' missing in this draft!?

    >>
    >> I don't know that, but what's wrong with doing the wait with a zero
    >> timeout?

    >
    > A personal bias... :^(
    >
    > Perhaps the wait function... Ahhhh, I almost tried to optimize a very slow
    > path...
    >
    > :^o
    >
    >> AFAIK, that's the accepted way to poll.

    >
    > It works.


    Which compilers are you folks using to test this?

    With MinGW g++ 4.4.1 and Visual C++ 10.0 I find no <future> header...


    Cheers,

    - Alf

    --
    blog at <url: http://alfps.wordpress.com>
     
    Alf P. Steinbach /Usenet, Aug 27, 2010
    #16
  17. Scott Meyers

    Scott Meyers Guest

    On 8/27/2010 12:51 AM, Alf P. Steinbach /Usenet wrote:
    > Which compilers are you folks using to test this?


    I use VC10 and the thread library from just::software
    (http://www.stdthread.co.uk/). From the library's web site:

    # Compatible with Microsoft Visual Studio 2008, Microsoft Visual C++ Express
    2008, Microsoft Visual Studio 2010 and Microsoft Visual C++ Express 2010 for
    both 32-bit and 64-bit Windows targets.

    # Compatible with g++ 4.3 and g++ 4.4 for 32-bit and 64-bit Ubuntu linux
    targets, making full use of the C++0x support from g++ including rvalue
    references and variadic templates.

    Scott

    --
    * C++ and Beyond: Meyers, Sutter, & Alexandrescu, Oct. 24-27 near Seattle
    (http://cppandbeyond.com/)
    * License my training materials for commercial (http://tinyurl.com/yfzvkp9) or
    personal use (http://tinyurl.com/yl5ka5p).
     
    Scott Meyers, Aug 27, 2010
    #17
  18. Scott Meyers

    lucdanton Guest

    On Aug 27, 9:51 am, "Alf P. Steinbach /Usenet" <alf.p.steinbach
    > wrote:
    > Which compilers are you folks using to test this?
    >
    > With MinGW g++ 4.4.1 and Visual C++ 10.0 I find no <future> header...


    g++ 4.5 on Linux ships with <future> (and std::future, std::promise,
    std::packaged_task std::shared_future, std::async are in there). Can't
    remember for 4.4, and last time I checked nobody was working on making
    <future> work for MinGW.
     
    lucdanton, Aug 27, 2010
    #18
  19. Scott Meyers

    Scott Meyers Guest

    On 8/27/2010 12:49 AM, Chris M. Thomasson wrote:
    > "Scott Meyers"<> wrote in message
    >> I don't know that, but what's wrong with doing the wait with a zero
    >> timeout?

    [...]
    >> AFAIK, that's the accepted way to poll.

    >
    > It works.


    Usually :) If the future you got is from std::async and you didn't specify the
    launch policy, the invocation of the "asynchronous" function may be deferred
    until you call wait or get, in which case your "zero time" wait will have to
    wait until the "asynchronous" function (which, in this case, is being invoked
    synchronously) returns.

    To avoid this possibility, specify a launch policy of std::launch::async when
    you call std::async.

    (BTW, I don't specify this stuff, I just try to figure out how to explain it.)

    Scott

    --
    * C++ and Beyond: Meyers, Sutter, & Alexandrescu, Oct. 24-27 near Seattle
    (http://cppandbeyond.com/)
    * License my training materials for commercial (http://tinyurl.com/yfzvkp9) or
    personal use (http://tinyurl.com/yl5ka5p).
     
    Scott Meyers, Aug 29, 2010
    #19
  20. "Scott Meyers" <> wrote in message
    news:i5cpmc$tmh$...
    > On 8/27/2010 12:49 AM, Chris M. Thomasson wrote:
    >> "Scott Meyers"<> wrote in message
    >>> I don't know that, but what's wrong with doing the wait with a zero
    >>> timeout?

    > [...]
    >>> AFAIK, that's the accepted way to poll.

    >>
    >> It works.

    >
    > Usually :) If the future you got is from std::async and you didn't
    > specify the launch policy, the invocation of the "asynchronous" function
    > may be deferred until you call wait or get, in which case your "zero time"
    > wait will have to wait until the "asynchronous" function (which, in this
    > case, is being invoked synchronously) returns.


    Humm... That's interesting. I was completely ignorant of that fact! Thanks
    for taking the time to mention it Scott.

    :^)


    > To avoid this possibility, specify a launch policy of std::launch::async
    > when you call std::async.


    That's definitely good to know!


    > (BTW, I don't specify this stuff, I just try to figure out how to explain
    > it.)


    =^)
     
    Chris M. Thomasson, Aug 30, 2010
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. ZackS
    Replies:
    5
    Views:
    6,868
    Just an Illusion
    Jul 9, 2004
  2. SpamProof
    Replies:
    3
    Views:
    669
    SpamProof
    Dec 1, 2003
  3. dave
    Replies:
    5
    Views:
    616
    William Brogden
    Jul 17, 2004
  4. Tim Smith
    Replies:
    2
    Views:
    883
    Tim Smith
    Dec 15, 2004
  5. Bartholomew Simpson

    class design/ design pattern question

    Bartholomew Simpson, Jun 12, 2007, in forum: C++
    Replies:
    2
    Views:
    462
    Daniel T.
    Jun 12, 2007
Loading...

Share This Page