Re: Concurrent Data Structures (Was: Concurrent Containers)
On Sep 3, 10:50 pm, Keith H Duggar <dug...@alum.mit.edu> wrote:
On Sep 3, 3:07 =AC=E2=80 pm, "Balog Pal" <p...@lib.hu> wrote:
"Scott Meyers" <NeverR...@aristeia.com>
Since when do you reject a library component because you have to writ=
e
some custom code to work with it? =AC=E2=80 Do you write your ow=
n containers from
scratch because the STL ones don't have exactly the interface you nee=
d for
your applications, or do you write some custom code with the interfac=
e you
want and use STL under the hood to implement that interface?
Let's not go to extreme relativization (or what is it called ;-). =
=AC=E2=80 Writing a
container (or most library stuff) involves many lines of code.
Inserting critical sections where they are needed is just a few lines.
Working with traditional objects in the MT environment is not a big dea=
l, if
your overall design is sound, and you did identify the points of sharin=
g.
Using a magic class that just does to good thing is cool. But replacing=
the
traditional way with some half-halping thing will hurt more than help,
believe me.
And if they don't believe you they need only hop else-thread and
read the twisted Gordian Knot Joshua entangled around himself by
focussing on preemptive thread/lock based solutions rather than
cooperative process/message based paradigms.
Happily the ever increasing focus of the computational community
on general /distributed/ computing is forcing efforts more toward
asynchronous message based computation and away from synchronous
shared data gymnastics.
To paraphrase Ward Cunningham "the Actor Model is a computational
model, multi-threading is a career path". [1]
http://en.wikipedia.org/wiki/Actor_model
KHD
[1] The original quote being "S-expressions are a representation,
XML is a career path." -- Ward Cunningham, 2003
Ok. I'll bite.
For fear that I have been tainted, may I ask how you would solve this
problem? Note that I have a working prototype, but I'm not sure of the
most straightforward way to convert it to use "threadsafe" queues
instead of condition variables.
Basically, it's my make replacement / clone. Let's suppose we have a
DAG of nodes. Each node has an associated job, say a std::function. To
simply without missing any important points, the engine wants to run
all of those jobs as fast as possible with one constraint: all
ancestors of a node X must have their jobs completed (and visible) to
the current thread before the current thread may do job for node X.
Let's call a job ready when all of its ancestors' nodes' jobs are
complete (and visible), no one else is running the job, and the job
has not yet been run.
So, a simple solution would be to keep a single multiple-producer,
multiple-consumer threadsafe queue which holds all ready jobs.
Initially, all nodes without ancestors would be added to the queue.
Then the threadpool would start. The main method of each worker is
something like:
for (;;)
{
block until there is a job, pop a job off the queue
run job
atomically decrement the field "number of outstanding ancestors"
for all direct children
for all children which have "0 == number of outstanding
ancestors", push that child to the queue.
}
However, this isn't very good in practice. It's a scheduling problem.
The problem is the arbitrary order in which the ready jobs are run.
The goal is to keep all of the CPUs busy, so correctly picking which
ready job to run may result in higher throughput rate later by
exposing more ready jobs. I found that a good heuristic for a subset
of my company's codebase is "When there are multiple ready jobs, pick
the job with the longest path to an offspring." In which case, the
worker main method looks something like:
for (;;)
{
Job job;
{
LockGuard lock(make_instance_wide_mutex);
while (priority_queue_of_ready_jobs.size() == 0)
wait(make_instance_wide_condition_variable,
make_instance_wide_mutex);
job = priority_queue_of_ready_jobs.topAndPop();
}
run job
{
LockGuard lock(make_instance_wide_mutex);
atomically decrement the field "number of outstanding ancestors"
for all direct children
for all children which have "0 == number of outstanding
ancestors", push that child to the priority queue.
}
if a child was just pushed, then signal or broadcast
make_instance_wide_condition_variable
}
I have not yet added cancellation, but I was definitely considering
it. As I see it, my simple option is: set the stop flag within
critical section of make_instance_wide_mutex. I would check the stop
flag right before going to sleep in the condition variable while loop.
This should suffice. I would probably give a function like
"cancellation_point" as part of the interface given to the
implementers of the jobs so that they could opt-in and stop quicker.
So Keith H Duggar , I guess my questions are:
1- I assumed that your claim includes only simple FIFO queues. Is a
priority queue acceptable in your models and arguments?
2- If not, what do you see to be the most straightforward way to
implement this logic with threadsafe FIFO queues? Is your problem with
any any sort of inter-thread blocking which isn't on a threadsafe FIFO
queue? Or is your problem with all shared state?
If I have to get rid of all shared state except threadsafe FIFO
queues, I suppose I could make a manager thread which has a local
priority queue of ready jobs. Worker threads would have two one-way
threadsafe FIFO queues with the manager. The workers could request a
ready job, receive it, do the job, and report back when the job is
done. I agree something like this would be required for distributed
computing where shared changeable state is hard / costly, but it seems
like a waste of a thread and over engineering on my single process
example.