Re: MT Design Question

Discussion in 'C++' started by Anthony Williams, Aug 29, 2010.

  1. Scott Meyers <> writes:

    > Suppose I have a graph that I want to search for a node that has some
    > characteristic (e.g., holds a value within some range). Suppose further that of
    > the many ways to search the graph (e.g., depth-first, breadth-first, random
    > walk, etc.), I can't predict which will be best, so I want to run them all
    > concurrently, stopping when either one of them finds a suitable node or they all
    > fail. That is, given something like this
    >
    > Node* dfsSearch(Graph g, Predicate p); // do dfs search of g for
    > // a node satisfying p
    > Node* bfsSearch(Graph g, Predicate p); // do bfs search of g
    > Node* rwSearch(Graph g, Predicate p); // do random walk search of g
    >
    > I want to do this:
    >
    > concurrently invoke dfsSearch, bfsSearch, and rwSearch;
    > wait until one returns success or they all return lack of success;
    > if one returned success, tell the others to stop searching;


    Spawn a thread for each search using std::async to catch the
    result/exception in a future, passing in a "done" flag:

    std::atomic<bool> done(false);
    std::vector<std::future<Node*>> results;
    results.push_back(std::async(std::launch::async,
    do_dfs_search,graph,predicate,&done));
    results.push_back(std::async(std::launch::async,
    do_bfs_search,graph,predicate,&done));
    results.push_back(std::async(std::launch::async,
    do_rw_search,graph,predicate,&done));

    where the do_xxx_search functions poll the done flag periodically, and
    exit with "not found" if done is already set. They set "done" if they
    exit successfully, but not if they exit with an exception.

    In the main thread, then wait on each future in turn. You need to ensure
    that all threads exit before you continue anyway, since leaving threads
    running in the background is a bad idea as you don't know what they'll
    access. You thus don't lose anything by waiting in whatever order if
    you're going to just return the value:

    std::exception_ptr e;
    for(unsigned i=0;i<results.size();++i)
    {
    try{
    if(Node* res=results.get()) return res;
    }
    catch(...)
    {
    e=std::current_exception();
    }
    }
    // no answer found, so throw an exception, if any
    if(e!=std::exception_ptr())
    std::rethrow_exception(e);
    // else return "not found"
    return nullptr;

    You can change the logic around the exceptions fairly easily, e.g. to
    always propagate the first found, to only propagate if all threads
    throw, to propagate a composite exception containing all the thrown
    exceptions, or whatever.

    If you're going to do further processing right there and then in the
    waiting function, you don't want to have to wait for the other threads
    to finish. Therefore you need another mechanism.

    You could just use a mutex and condition variable which is passed in to
    every thread function. The cond var is notified when each thread exits
    (with notify_all_at_thread_exit) and the waiting thread then blocks on
    the cond var rather than on any of the futures. When it wakes from the
    cond-var wait it can poll the futures to see which (if any) thread is
    done, and process the result as appropriate.

    std::mutex m;
    std::condition_variable c;

    // pass &m and &c into threads.

    std::unique_lock<std::mutex> lk(m);
    for(;;)
    {
    for(unsigned i=0;i<results.size();++i)
    {
    if(!results.valid() ||
    (result.wait_for(std::chrono::seconds(0))!=
    std::future_status::ready))
    break;
    try{
    if(Node* res=results.get()) return res;
    }
    catch(...)
    {
    e=std::current_exception();
    }
    }
    }

    The thread function then does:

    std::unique_lock<std::mutex> lk(m);
    std::notify_all_at_thread_exit(c,std::move(lk));

    when it's done. This is essentially what boost::wait_for_any does under
    the covers.

    Alternatively, you could use a single promise/future pair to store the
    result and have the main thread wait for that. In this case you need to
    ensure that it is set if all threads throw, otherwise the main thread
    will wait forever. This can be achieved by using an atomic count of
    searching threads which is decremented when each thread exits (whether
    normally or with an exception). The last thread out must set the promise
    however it exits.

    std::promise<Node*> p;
    std::atomic<int> count(3);
    std::future<Node*> result=p.get_future();
    std::vector<std::future<void>> async_handles;
    async_handles.push_back(std::async(std::launch::async,
    do_dfs_search,graph,predicate,&done,&p,&count));
    async_handles.push_back(std::async(std::launch::async,
    do_bfs_search,graph,predicate,&done,&p,&count));
    async_handles.push_back(std::async(std::launch::async,
    do_rw_search,graph,predicate,&done,&p,&count));

    do_something_with(result.get());

    Each thread then does something like:

    try{
    if(Node* res=real_search())
    {
    try{
    p.set_value(res);
    }
    catch(std::future_error) // in case promise already set
    {}
    }
    if(!--count)
    {
    try{
    p.set_value(nullptr);
    }
    catch(std::future_error) // in case promise already set
    {}
    }
    }
    catch(...)
    {
    if(!--count)
    {
    try{
    p.set_exception(std::current_exception());
    }
    catch(std::future_error) // in case promise already set
    {}
    }
    }

    Anthony
    --
    Author of C++ Concurrency in Action http://www.stdthread.co.uk/book/
    just::thread C++0x thread library http://www.stdthread.co.uk
    Just Software Solutions Ltd http://www.justsoftwaresolutions.co.uk
    15 Carrallack Mews, St Just, Cornwall, TR19 7UL, UK. Company No. 5478976
    Anthony Williams, Aug 29, 2010
    #1
    1. Advertising

  2. Anthony Williams

    Scott Meyers Guest

    On 8/29/2010 3:38 PM, Anthony Williams wrote:
    > If you're going to do further processing right there and then in the
    > waiting function, you don't want to have to wait for the other threads
    > to finish. Therefore you need another mechanism.
    >
    > You could just use a mutex and condition variable which is passed in to
    > every thread function. The cond var is notified when each thread exits
    > (with notify_all_at_thread_exit) and the waiting thread then blocks on
    > the cond var rather than on any of the futures.


    In theory, arbitrary computation make take place between the time a promise is
    set and the thread setting that promise exits (e.g., due to the destruction of
    locals and TLS objects), correct? That being the case, would it not generally
    be better practice to either notify the condvar immediately after setting the
    promise or to have the calling thread wait on the future? My intuition is that
    it's a bad idea to assume that thread exit is more or less simultaneous with
    setting a promise, but my intuition is suspect. What's your view?

    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 30, 2010
    #2
    1. Advertising

  3. Scott Meyers <> writes:

    > On 8/29/2010 3:38 PM, Anthony Williams wrote:
    >> If you're going to do further processing right there and then in the
    >> waiting function, you don't want to have to wait for the other threads
    >> to finish. Therefore you need another mechanism.
    >>
    >> You could just use a mutex and condition variable which is passed in to
    >> every thread function. The cond var is notified when each thread exits
    >> (with notify_all_at_thread_exit) and the waiting thread then blocks on
    >> the cond var rather than on any of the futures.

    >
    > In theory, arbitrary computation make take place between the time a
    > promise is set and the thread setting that promise exits (e.g., due to
    > the destruction of locals and TLS objects), correct?


    That depends on the mechanism you use for setting the future. If you use
    std::async then the future is not ready until the async thread exits
    (the wording says that future::get joins with the async thread). Since
    that is how this was set up, you don't want to notify the cond var until
    then, otherwise the waiting thread will wake before the future is ready.

    If you use a promise explicitly then it is made ready at the point you
    call set_value or set_exception. Of course, if you use
    set_value_at_thread_exit then it is not ready until then.

    Anthony
    --
    Author of C++ Concurrency in Action http://www.stdthread.co.uk/book/
    just::thread C++0x thread library http://www.stdthread.co.uk
    Just Software Solutions Ltd http://www.justsoftwaresolutions.co.uk
    15 Carrallack Mews, St Just, Cornwall, TR19 7UL, UK. Company No. 5478976
    Anthony Williams, Aug 30, 2010
    #3
  4. Anthony Williams

    Scott Meyers Guest

    On 8/29/2010 3:38 PM, Anthony Williams wrote:
    > In the main thread, then wait on each future in turn. You need to ensure
    > that all threads exit before you continue anyway, since leaving threads
    > running in the background is a bad idea as you don't know what they'll
    > access. You thus don't lose anything by waiting in whatever order if
    > you're going to just return the value:

    [...]
    > If you're going to do further processing right there and then in the
    > waiting function, you don't want to have to wait for the other threads
    > to finish.


    If I'm understanding this correctly, it's bad practice to return from a function
    while threads spawned by that function are still running, because "you don't
    know what they'll access," but it's okay to do work in that function in parallel
    with those spawned threads, because, um, you do know what they'll access?

    Would it be more accurate to say that returning while spawned threads are
    running is bad, because you don't know what the calling function will do and
    hence whether that will interfere with what the spawned threads are doing? (The
    calling function also, in general, has no way of knowing when the spawned
    threads finish, whereas the function that spawned them generally does.)

    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 30, 2010
    #4
  5. Scott Meyers <> writes:

    > On 8/29/2010 3:38 PM, Anthony Williams wrote:
    >> In the main thread, then wait on each future in turn. You need to ensure
    >> that all threads exit before you continue anyway, since leaving threads
    >> running in the background is a bad idea as you don't know what they'll
    >> access. You thus don't lose anything by waiting in whatever order if
    >> you're going to just return the value:

    > [...]
    >> If you're going to do further processing right there and then in the
    >> waiting function, you don't want to have to wait for the other threads
    >> to finish.

    >
    > If I'm understanding this correctly, it's bad practice to return from
    > a function while threads spawned by that function are still running,
    > because "you don't know what they'll access," but it's okay to do work
    > in that function in parallel with those spawned threads, because, um,
    > you do know what they'll access?
    >
    > Would it be more accurate to say that returning while spawned threads
    > are running is bad, because you don't know what the calling function
    > will do and hence whether that will interfere with what the spawned
    > threads are doing? (The calling function also, in general, has no way
    > of knowing when the spawned threads finish, whereas the function that
    > spawned them generally does.)


    Yes, that's what I meant: if A calls B and B spawns threads then A
    doesn't know about the threads, and doesn't know what they'll access, so
    if they are still running after B exits then they may do something
    incompatible with what A then does (e.g. access an object which A has
    now destroyed)

    Anthony
    --
    Author of C++ Concurrency in Action http://www.stdthread.co.uk/book/
    just::thread C++0x thread library http://www.stdthread.co.uk
    Just Software Solutions Ltd http://www.justsoftwaresolutions.co.uk
    15 Carrallack Mews, St Just, Cornwall, TR19 7UL, UK. Company No. 5478976
    Anthony Williams, Aug 30, 2010
    #5
    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,797
    Just an Illusion
    Jul 9, 2004
  2. SpamProof
    Replies:
    3
    Views:
    644
    SpamProof
    Dec 1, 2003
  3. dave
    Replies:
    5
    Views:
    591
    William Brogden
    Jul 17, 2004
  4. Tim Smith
    Replies:
    2
    Views:
    854
    Tim Smith
    Dec 15, 2004
  5. Bartholomew Simpson

    class design/ design pattern question

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

Share This Page