Re: MT Design Question
"Scott Meyers" <NeverRead@aristeia.com>
This is a threading-related design question assuming that C++0x is the
implementation language.
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.
I don't get this part. The problem suggests that all runners do the same
search. So if any of them exhausted the input and reports 'fail' you can
accept that as the verdict. Why wait the others to alse report the same?
Though that is just a minor detail to signal the stop condition.
If all runners have their separate location to store the result, I'd start
with a single atomic<bool> that is the finish sign. Each thread polls it
regularly and if finds set, cancels its work, exiting. And whoever
finishes naturally sets it.
This only leaves the problem of joining. A simple way looks like every
thread knows the 'next' one and joins that on exit. The "main" thread
considered the first. So soon after anyone sets the bool you're back to a
single thread, and can proceed to find the result from the candidates.
Having no locks at all it seem efficient for a single-core environment. On
multicore there will be a ton of reads around a shared byte, but unless
atomic<> has some weird penalty it shall not be a problem either, at least I
don't see how other sync stuff would be better.
I didn't check fow future<> stuff works in C++0x, my approach only builds
what I get from the memory model and thread basics.