Is this group dying?
Chris Thomasson
locks, which contains the essence of that infamous, pseudo-troll bastard;
'SenderX'! Now that statement alone should quickly spur some fairly lively,
and/or interesting conversations, just to make sure I keep him locked up;
no? Ahh crap, well, you don't actually have to worry for now because I can't
seem find the key's that fit in all the locks on the chest... Please,
somebody tell me not to do such a radical thing! Remember all the wonderful
"pseudo-flame" wars that surprisingly focused on real topics?
http://groups.google.com/group/comp.programming.threads/msg/2b4fd48827d37e28
http://groups.google.com/group/comp.programming.threads/msg/587bd0ff5b90bb71
;^)
Okay, all kidding aside, and on a _MUCH_ more serious note: I was wondering
how the upcoming C++ Standard is going to alter the traffic directed to this
fine newsgroup. Sadly, IMHO, when somebody posts a C++ threading question
over on 'comp.c++.*' they will probably "forget" to include our humble
little group of experts; yikes! Please tell me I am *crazy, which implies I
am oh so dead wrong?
;^(...
*: I have been told I am crazy before because I document all the corrections
I can find, wrt pseudo-code sketches of algorithms I post:
http://groups.google.com/group/microsoft.public.win32.programmer.kernel/msg/95ac7ca21bb12b7c
(somebody used X-No-Archive in that thread..)
Oh well.
--
Chris M. Thomasson
http://appcore.home.comcast.net
llothar
> how the upcoming C++ Standard is going to alter the traffic directed to this
I hope not. Only crazy people are still using C++ for application
development.
Rui Maciel
> Okay, all kidding aside, and on a MUCH more serious note: I was wondering
> how the upcoming C++ Standard is going to alter the traffic directed to
> this fine newsgroup. Sadly, IMHO, when somebody posts a C++ threading
> question over on 'comp.c++.*' they will probably "forget" to include our
> humble little group of experts; yikes! Please tell me I am *crazy, which
> implies I am oh so dead wrong?
I've only recently subscribed to comp.programming.threads. I did it because
I started to develop an interest in learning how to write multi-threaded
applications. The number of people that share that interest will only
increase, due to Intel and AMD's investment in multi-core processors.
I can only see the traffic increasing. This group didn't ceassed to exist in
favour of any C usenet group, even though the pthreads standards describe a
C library. The same applies to unix programming. So why would that happen
with the new C+++ standards?
The thing is, the discussions regarding threaded programming are largely
independent of any programming language. Therefore, I do believe that they
would be largely considered off-topic in newsgroups dedicated to any
programming language and, as we all know, some newsgroups are very strict
at enforcing topicality. Then, having said that, what usenet group is
better suited to host discussions related to multi-threaded programming?
Rui Maciel
Joe Seigh
around a bit to find anything interesting nowadays.
The various programming challenges out there have been insufficiently
challenging.
http://programming.reddit.com/ has been relatively quiet as of late.
--
Joe Seigh
When you get lemons, you make lemonade.
When you get hardware, you make software.
blytkerchan
> Humm... Perhaps I should dig up the buried chest, covered with chains and
> locks, which contains the essence of that infamous, pseudo-troll bastard;
> 'SenderX'! Now that statement alone should quickly spur some fairly lively,
> and/or interesting conversations, just to make sure I keep him locked up;
> no? Ahh crap, well, you don't actually have to worry for now because I can't
> seem find the key's that fit in all the locks on the chest... Please,
> somebody tell me not to do such a radical thing! Remember all the wonderful
> "pseudo-flame" wars that surprisingly focused on real topics?
>
>
> http://groups.google.com/group/comp.programming.threads/msg/587bd0ff5...
>
> ;^)
>
> Okay, all kidding aside, and on a _MUCH_ more serious note: I was wondering
> how the upcoming C++ Standard is going to alter the traffic directed to this
> fine newsgroup. Sadly, IMHO, when somebody posts a C++ threading question
> over on 'comp.c++.*' they will probably "forget" to include our humble
> little group of experts; yikes! Please tell me I am *crazy, which implies I
> am oh so dead wrong?
>
> ;^(...
>
> *: I have been told I am crazy before because I document all the corrections
> I can find, wrt pseudo-code sketches of algorithms I post:
>
> (somebody used X-No-Archive in that thread..)
>
> Oh well.
>
> --
> Chris M. Thomassonhttp://appcore.home.comcast.net
As for being crazy: I think one has to be a *little* deranged to do
multi-threading anyway, as there are simply too many things to take
into account for a sane mind to handle. You must also have seen that
glazed-over look colleagues get in their eyes when you start
explaining some sync problem - don't you?
My team is now big enough (and the people in it indulgent enough) to
have them role-playing in my demonstrations (each holding a pen which
they some-how have to exchange in some thread-safe non-blocking manner
without bumping into each-other and without ending up with more than
one pen at any given time, for example) but still, the mere fact that
I'd interrupt a hard-working colleague to role-play in one of my
explanations might indicate some disorder...
Anyway, I don't think this group will die just because C++ is starting
to think about multi-threading. I remember the arguments being made on
comp.lang.c++ to argue that library changes were not enough to get
threading in there (http://groups.google.ca/groups/search?
hl=en&oe=UTF-8&q=single-threaded+abstract+machine+C%2B%2B&qt_s=Search)
and my last look at the memory model for C++ in thread-aware hosted
environments doesn't quite compile with me yet...
In any case, there's still threading in more general terms, threading
in C++, PThreads, Intel's TBB, etc. etc. and the "how many threads
should I create when I have N cores and M connections?" etc. There's a
lot more to discuss than C++'s semantics for mutexes and shared
memory...
Keep up hope: if you build it, they will come ;-)
rlc
blytkerchan
That proves it then - I am crazy.
rlc
blytkerchan
> This newsgroup has largely been deconstructed. You have to scrounge
> around a bit to find anything interesting nowadays.
>
> The various programming challenges out there have been insufficiently
> challenging.
>
>
> --
> Joe Seigh
>
> When you get lemons, you make lemonade.
> When you get hardware, you make software.
Well, there was that question about a multi-threaded scripting
language recently. If you want a challenge, that sure looked like one
- though admittedly not necessarily a very hard one once the
application domain for the language is defined...
What do you think - want to define the application domain for an
"ideal" threaded scripting language?
;)
rlc
Chris Thomasson
news:1190949183....@r29g2000hsg.googlegroups.com...
> On Sep 27, 8:48 pm, Joe Seigh <jseigh...@xemaps.com> wrote:
>> This newsgroup has largely been deconstructed. You have to scrounge
>> around a bit to find anything interesting nowadays.
>>
>> The various programming challenges out there have been insufficiently
>> challenging.
>
> Well, there was that question about a multi-threaded scripting
> language recently. If you want a challenge, that sure looked like one
> - though admittedly not necessarily a very hard one once the
> application domain for the language is defined...
>
> What do you think - want to define the application domain for an
> "ideal" threaded scripting language?
> ;)
I guess a script object could represent a task, which can be freely
created/joined, and examined for a return value. A task could be driven by a
single thread, or maintain the necessary information (e.g., simple
state-machine) that allows it to reside within the domain of a system
thread-pool/task-scheduler object. I can do the scheduler part using a vZOOM
single-producer/consumer unbounded wait-free queue which uses no
interlocking or expensive #StoreLoad or #LoadStore membars. Distributed
multiplexing on the per-thread queuing scheme. Eventcounts for anything that
needs to wait (e.g., a join on a task).
The main script could create multiple tasks which perform concurrent
operations and subsequently join with them and retrieve their various
results.
The lexer/parser could be per-script object. That way a script can spawn a
new task and continue on parsing/processing; running concurrently with the
newly created tasks parser.
Not sure this needs to be a scripting language... Can't the script be a
small C application that can be accessed with a link on a web-site? I wonder
if something like 'http://www.dinkumware.com/exam' would be interesting... A
highly concurrent C compiler that receives requests generated by the
internet. The C programs could have a limit on their total size; after all
there suppose to be small scripts... Of course this would never work because
somebody could create a virus far to easily...
blytkerchan
> "blytkerchan" <blytkerc...@gmail.com> wrote in message
>
> news:1190949183....@r29g2000hsg.googlegroups.com...
>
>
>
> > On Sep 27, 8:48 pm, Joe Seigh <jseigh...@xemaps.com> wrote:
> >> This newsgroup has largely been deconstructed. You have to scrounge
> >> around a bit to find anything interesting nowadays.
>
> >> The various programming challenges out there have been insufficiently
> >> challenging.
> [...]
>
> > Well, there was that question about a multi-threaded scripting
> > language recently. If you want a challenge, that sure looked like one
> > - though admittedly not necessarily a very hard one once the
> > application domain for the language is defined...
>
> > What do you think - want to define the application domain for an
> > "ideal" threaded scripting language?
> > ;)
>
> I guess a script object could represent a task, which can be freely
> created/joined, and examined for a return value. A task could be driven by a
> single thread, or maintain the necessary information (e.g., simple
> state-machine) that allows it to reside within the domain of a system
> thread-pool/task-scheduler object.
So, you're basically talking about an explicitly multi-threaded (or at
least multi-tasked) scripting language that would have tasks
communicate through message-passing queues.. unless you want to make
the multi-tasking implicit and have those "return values" become
futures.
> I can do the scheduler part using a vZOOM
> single-producer/consumer unbounded wait-free queue which uses no
> interlocking or expensive #StoreLoad or #LoadStore membars. Distributed
> multiplexing on the per-thread queuing scheme. Eventcounts for anything that
> needs to wait (e.g., a join on a task).
OK, how's about this: one single dispatcher thread and any amount of
worker threads. Each worker thread has an "input" queue and an
"output" queue, reads a task from the input queue (or waits on an
event if there's nothing to do) and, when the task is done, spits it
out on the output queue. The dispatcher queue schedules the tasks to
the different worker threads according to expected load from the task
(which could be as simple as looking at the number of nodes in the
parse tree or the size of the bytecode if we compile it that far) and
balances it to the different threads. Tasks can be spawned by other
tasks but would have to pass through the dispatcher queue for that -
same thing for joining.
>From within the scripting language itself, tasks are objects that can
be created (which will have the worker thread add it to its output
queue for dispatching) and joined (which will have the worker thread
pass the current task to the output thread to let the dispatcher join
the two). The task itself can have any payload, which constitutes the
working set of the task, and a single entry point which is either a
script function or a "native" function.
> The main script could create multiple tasks which perform concurrent
> operations and subsequently join with them and retrieve their various
> results.
I'd say the "main script" is just the first task to be launched..
> The lexer/parser could be per-script object. That way a script can spawn a
> new task and continue on parsing/processing; running concurrently with the
> newly created tasks parser.
Actually, I'd have a tendency to go for a two-step execution: lexing/
parsing followed by evaluation. That way, any compile-time errors can
be caught in a nicely clean fashion, an already-parsed state could be
serialized and saved (byte-code, persistent parse-tree or whatever)
and an evaluator can take care of actually evaluating the code
(running it) and keeping track of the context. I've found splitting
the two into two phases (lex/parse followed by evaluation) both cleans
up the implementation and has the advantage of knowing your code is
likely to work without having to run it first.
> Not sure this needs to be a scripting language... Can't the script be a
> small C application that can be accessed with a link on a web-site? I wonder
> if something like 'http://www.dinkumware.com/exam'would be interesting... A
> highly concurrent C compiler that receives requests generated by the
> internet. The C programs could have a limit on their total size; after all
> there suppose to be small scripts... Of course this would never work because
> somebody could create a virus far to easily...
IMO, that's more a question of exposing some built-in types in such a
way that a C or C++ program can also use them, and allowing the
interpreter to be extended with plug-ins written in C, through some
"native interface".
The question remains, though: what is the problem domain? We'll need
to answer that to be able to design the syntax and grammar of the
language.
rlc
Ulrich Eckhardt
> As for being crazy: I think one has to be a *little* deranged to do
> multi-threading anyway, as there are simply too many things to take
> into account for a sane mind to handle.
I'm a loonatick too, then, in addition to my unhealthy addiction to C++
(some would say).
Anyhow, I was recently reading a bit about Erlang with the explicit intent
of stealing ideas. It seems that it is a language that was explicitly
designed to ease design of MT programs, is being used in an industrial
context and that with success.
> You must also have seen that glazed-over look colleagues get in their
> eyes when you start explaining some sync problem - don't you?
Amen, brother!
Uli
Chris Thomasson
>> I guess a script object could represent a task, which can be freely
>> created/joined, and examined for a return value. A task could be driven
>> by a
>> single thread, or maintain the necessary information (e.g., simple
>> state-machine) that allows it to reside within the domain of a system
>> thread-pool/task-scheduler object.
>
> So, you're basically talking about an explicitly multi-threaded (or at
> least multi-tasked) scripting language that would have tasks
> communicate through message-passing queues..
Basically.
> unless you want to make
> the multi-tasking implicit and have those "return values" become
> futures.
Sure. Futures could work in conjunction with explicit threading.
>> I can do the scheduler part using a vZOOM
>> single-producer/consumer unbounded wait-free queue which uses no
>> interlocking or expensive #StoreLoad or #LoadStore membars. Distributed
>> multiplexing on the per-thread queuing scheme. Eventcounts for anything
>> that
>> needs to wait (e.g., a join on a task).
>
> OK, how's about this: one single dispatcher thread and any amount of
> worker threads. Each worker thread has an "input" queue and an
> "output" queue, reads a task from the input queue (or waits on an
> event if there's nothing to do) and, when the task is done, spits it
> out on the output queue. The dispatcher queue schedules the tasks to
> the different worker threads according to expected load from the task
> (which could be as simple as looking at the number of nodes in the
> parse tree or the size of the bytecode if we compile it that far) and
> balances it to the different threads. Tasks can be spawned by other
> tasks but would have to pass through the dispatcher queue for that -
> same thing for joining.
I think that a work stealing scheme would work within the context of a
thread-pool here. That could handle some of the load-balancing.
[...]
>> Not sure this needs to be a scripting language...
[...]
I am now really leaning toward implementing a generic wait-free
factory/observer-pattern with shared memory. The observer stuff can be
handled like:
http://appcore.home.comcast.net/vzoom/msgsys.pdf
(a very simple diagram I created for a consulting job...)
I have it implementing with wait-free queuing and eventcounts, however, its
within the context of a single process. As for the factory pattern, I have
it in threads using hash-tables, linked-lists, mutexs for writers and vzoom
pdr for the readers; no shared-mem. I would like to put all of that in
shared memory abstraction.
> The question remains, though: what is the problem domain?
Wait-Free Generic Shared-Memory Algorithms; Factory, Observer, ect...
> We'll need
> to answer that to be able to design the syntax and grammar of the
> language.
I am thinking that creating a language may end up being a bit to tedious.
What do you think about doing something with shared memory?
Chris Thomasson
>> The question remains, though: what is the problem domain?
Problem/Question:
- How to efficiently solve shared-memory coherency issues in software?
Possible Solution:
- Virtually Zero-Overhead:
> Wait-Free Generic Shared-Memory Algorithms; Factory, Observer, ect...
Any thoughts?
Dmitriy Vyukov
> I think that a work stealing scheme would work within the context of a
> thread-pool here. That could handle some of the load-balancing.
It seems that such scheme becomes a de-facto standard:
http://gee.cs.oswego.edu/dl/papers/fj.pdf
http://msdn.microsoft.com/msdnmag/issues/07/10/Futures/default.aspx?loc=en
http://www.cs.indiana.edu/~welu/socp122-lu.pdf
All are based on ABP work-stealing deque:
http://research.sun.com/scalable/pubs/DynamicWorkstealing.pdf
Work-stealing provides both: automatic load balancing and data
locality with possibility of specifying preferred thread.
Dmitriy V'jukov
Dmitriy Vyukov
> On Sep 30, 1:50 am, "Chris Thomasson" <cris...@comcast.net> wrote:
>
> > I think that a work stealing scheme would work within the context of a
> > thread-pool here. That could handle some of the load-balancing.
>
And of course:
Intel TBB and Cilk
Dmitriy V'jukov
blytkerchan
I like the producer/consumer abstraction a lot, but your vZOOM will
only work in single-producer single-consumer cases if you don't want
to use either locks or interlocked instructions - at least I don't
really see how it could work with multiple producers or multiple
consumers.
For observers, I usually use a generic non-threaded implementation
(non-threaded in that, aside from the container that holds the
pointers to the observers, which needs to be thread-safe, the subject
does not need to know that there is more than one thread anywhere).
Once the notification (task or otherwise) is put in place (in a queue,
for example) the observer is usually "woken up" through a condvar or
an event (on Windows). It sleeps for the rest of the time. As most of
the time, most of my threads are asleep anyway (except those of my
spooler, which do all of the hard work) I'm not all that worried about
using locks in these contexts. Within the Spooler, to hand tasks over
to the worker threads, I have one global queue (multiple producer/
multiple consumer, lock-free but not wait-free) from which the worker
threads take their next task if their local queue is empty. If both
are empty, they sleep on a condvar/event. The per-worker-thread queues
are multi-producer/single-consumer, lock-free and wait-free.
As for a Factory, I don't see why a factory would have to know about
threading unless you want the factory to keep track of whatever it's
created. Other than that, you just need a thread-safe memory manager..
Or perhaps I don't quite see the problem you're seeing.
As for a scripting language: I see scripting languages as a convenient
way for gluing otherwise disparate blocks of code together, or to make
decisions with "on-the-fly" logic (i.e. logic that wasn't built into
whatever you were building at the time). So the question really is:
what are you going to want to glue together? Message passing is a nice
abstraction for that: you just need to be able to create a message and
pass it into the mill, and to create whatever logic is needed to
handle the message and have that run by the mill. I can see a nice
opportunity for a scripting language there.
rlc
Joe Seigh
> As for a scripting language: I see scripting languages as a convenient
> way for gluing otherwise disparate blocks of code together, or to make
> decisions with "on-the-fly" logic (i.e. logic that wasn't built into
> whatever you were building at the time). So the question really is:
> what are you going to want to glue together? Message passing is a nice
> abstraction for that: you just need to be able to create a message and
> pass it into the mill, and to create whatever logic is needed to
> handle the message and have that run by the mill. I can see a nice
> opportunity for a scripting language there.
>
Message passing is easy to implement. But everything gets turned into
distributed programming then.
blytkerchan
It only becomes distributed programming if the threads become
processes that could eventually end up on different systems and start
talking to each-other by some kind of request broker. If, on the other
hand, the threads really do remain threads, message passing is just an
alternative way of threading - alternative to shared memory, that is.
rlc
Chris Thomasson
> On Sep 29, 5:53 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
>> [...]
>>
>> >> The question remains, though: what is the problem domain?
>>
>> Problem/Question:
>>
>> - How to efficiently solve shared-memory coherency issues in software?
>>
>> Possible Solution:
>>
>> - Virtually Zero-Overhead:
>> Any thoughts?
>
> I like the producer/consumer abstraction a lot, but your vZOOM will
> only work in single-producer single-consumer cases if you don't want
> to use either locks or interlocked instructions - at least I don't
> really see how it could work with multiple producers or multiple
> consumers.
You have to use distributed model. For instance, a
multiple-producer/single-consumer model in vZOOM can consist of per-producer
queue which are registered with a single consumer. This model is 100%
compatible with. You can transform that into a
multiple-producer/multiple-consumer model by hashing a pointer to a producer
thread into an index of consumer threads. The producer uses this index to
know what consumer to register its spsc queue with. All of the described
models can use the ultra-low overhead vZOOM unbounded wait-free queues. This
is ideal for a distributed message passing system.
> For observers, I usually use a generic non-threaded implementation
[...]
I kind of like doing it with a single disributer thread; like the diagram I
linked to shows.
> I have one global queue (multiple producer/
> multiple consumer, lock-free but not wait-free) from which the worker
> threads take their next task if their local queue is empty. If both
> are empty, they sleep on a condvar/event. The per-worker-thread queues
> are multi-producer/single-consumer, lock-free and wait-free.
One global lock-free queue can cause quite a bit of overhead; can have 2
interlocks in the producer _and_ in the consumer. That is basically just
expensive as a traditional uncontended fast-pathed mutex assess; what
algorithm are you using? Also, what algorithm are you using for the
per-worker-thread queues?
http://groups.google.com/group/comp.programming.threads/msg/a359bfb41c68b98b
If so, that works fine; indeed it has wait-free consumers. However, the
vZOOM model can still outperform it by quite a large margin simply because
it does not use interlocking, has wait-free producer and consumer operations
and is highly-distributed/NUMA-friendly.
I want the wait-free observer to be a multi-threaded daemon that can allow
multiple threads to create/register delegates; message-types and allow
consumer threads to register with those delegates and receive their
messages; producer threads create messages with subsequently signal the
delegates that manages those messages to multicast to their registered
consumers.
> As for a Factory, I don't see why a factory would have to know about
> threading unless you want the factory to keep track of whatever it's
> created. Other than that, you just need a thread-safe memory manager..
>
> Or perhaps I don't quite see the problem you're seeing.
I want to implement the wait-free factory as a multi-threaded daemon process
that multiple producers can register the path and name of a shared library,
which concurrent consumer processes can lookup by name; dynamically link
with the resulting library and call a "common" instance function (e.g.,
define common api). I guess you could think of it as a highly concurrent
per-computer COM daemon. The factory consumer threads can use the lock-free
reader pattern, and the producer threads can use a form of mutual exclusion;
including, but not limited, to locks.
> As for a scripting language: I see scripting languages as a convenient
> way for gluing otherwise disparate blocks of code together, or to make
> decisions with "on-the-fly" logic (i.e. logic that wasn't built into
> whatever you were building at the time). So the question really is:
> what are you going to want to glue together? Message passing is a nice
> abstraction for that: you just need to be able to create a message and
> pass it into the mill, and to create whatever logic is needed to
> handle the message and have that run by the mill. I can see a nice
> opportunity for a scripting language there.
Yeah. BTW, are there any scripting langs that have a message passing
interface for their basic method of operation? Simply create a script and
enqueue it onto the message system, and wait/pool on its subsequent
resulting data. Humm...
Chris Thomasson
> On 1 oct, 05:36, Joe Seigh <jseigh...@xemaps.com> wrote:
>> > As for a scripting language: I see scripting languages as a convenient
>> > way for gluing otherwise disparate blocks of code together, or to make
>> > decisions with "on-the-fly" logic (i.e. logic that wasn't built into
>> > whatever you were building at the time). So the question really is:
>> > what are you going to want to glue together? Message passing is a nice
>> > abstraction for that: you just need to be able to create a message and
>> > pass it into the mill, and to create whatever logic is needed to
>> > handle the message and have that run by the mill. I can see a nice
>> > opportunity for a scripting language there.
>>
>> Message passing is easy to implement. But everything gets turned into
>> distributed programming then.
>>
>> --
>> Joe Seigh
>>
>> When you get lemons, you make lemonade.
>> When you get hardware, you make software.
>
> It only becomes distributed programming if the threads become
> processes that could eventually end up on different systems and start
> talking to each-other by some kind of request broker.
Not true. You can implement distributed message passing on a single
computer. Think distributed in the sense of networking the multiple
processors that reside on a _single_ computer...
Chris Thomasson
news:-8SdnVTlM4wvHpza...@comcast.com...
> "blytkerchan" <blytk...@gmail.com> wrote in message
> news:1191204480.2...@o80g2000hse.googlegroups.com...
>> I like the producer/consumer abstraction a lot, but your vZOOM will
>> only work in single-producer single-consumer cases if you don't want
>> to use either locks or interlocked instructions - at least I don't
>> really see how it could work with multiple producers or multiple
>> consumers.
>
> You have to use distributed model. For instance, a
> multiple-producer/single-consumer model in vZOOM can consist of
> per-producer queue which are registered with a single consumer. This model
> is 100% compatible with.
To continue that last sentence:
This model is 100% compatible with vZOOM single-producer/consumer wait-free
queuing.
blytkerchan
> "blytkerchan" <blytkerc...@gmail.com> wrote in message
> news:1191204480.2...@o80g2000hse.googlegroups.com...
> > On Sep 29, 5:53 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
> >> [...]
> >> >> The question remains, though: what is the problem domain?
> >> Problem/Question:
> >> - How to efficiently solve shared-memory coherency issues in software?
> >> Possible Solution:
> >> - Virtually Zero-Overhead:
> [...]
> >> Any thoughts?
>
> > I like the producer/consumer abstraction a lot, but your vZOOM will
> > only work in single-producer single-consumer cases if you don't want
> > to use either locks or interlocked instructions - at least I don't
> > really see how it could work with multiple producers or multiple
> > consumers.
>
> You have to use distributed model. For instance, a
> multiple-producer/single-consumer model in vZOOM can consist of per-producer
> queue which are registered with a single consumer. This model is 100%
> compatible with. You can transform that into a
> multiple-producer/multiple-consumer model by hashing a pointer to a producer
> thread into an index of consumer threads. The producer uses this index to
> know what consumer to register its spsc queue with. All of the described
> models can use the ultra-low overhead vZOOM unbounded wait-free queues. This
> is ideal for a distributed message passing system.
Si you basically use single-producer single-consumer queues in much
the same way as the "input queues" and "output queues" I was talking
about a few days ago. You solve the multi-producer/multi-consumer
problem by hashing your pointer and you can always compensate for a
mis-attribution of a task through work stealing.
It's certainly a scalable approach, and if your virtually-zero
overhead is really virtually zero, the cost of having two queues per
thread is negligeable next to the use of locks.
> > For observers, I usually use a generic non-threaded implementation
>
> [...]
>
> I kind of like doing it with a single disributer thread; like the diagram I
> linked to shows.
That is actually pretty close to what I would do for a dispatcher-
based Mediator implementation: a single multi-producer/single-
consumer queue toward the dispatcher thread and a single-producer/
single-consumer queue between the dispatcher and each consumer of an
observable event. The dispatcher basically works as a switchboard,
delivering its messages to the interested observers according to their
types (required quite a bit of template meta-programming, that
one :) )
> > I have one global queue (multiple producer/
> > multiple consumer, lock-free but not wait-free) from which the worker
> > threads take their next task if their local queue is empty. If both
> > are empty, they sleep on a condvar/event. The per-worker-thread queues
> > are multi-producer/single-consumer, lock-free and wait-free.
>
> One global lock-free queue can cause quite a bit of overhead; can have 2
> interlocks in the producer _and_ in the consumer. That is basically just
> expensive as a traditional uncontended fast-pathed mutex assess; what
> algorithm are you using? Also, what algorithm are you using for the
> per-worker-thread queues?
The basic idea is that an empty queue consists of a single node with a
NULL as its "next"node. Its value is writable by the producer until
that producer has put a new "next" node in place. The consumer
acquires a node it can read from by putting NULL on its "next" and
checking that what was there wasn't NULL already. If it was, the node
is a dummy and should stay where it is. If it wasn't, the node value
is what it wants and whatever was in place is the new head. The
producer keeps track of the tail, the consumer keeps track of the
head. As both the head and the tail can only be mutated by a single
thread, there's no locking required for those.
I.e., the queue looks a bit like this (pseudo-code)
struct Node
{
Node() : next(0) {}
Node * next_;
Any val_;
};
struct Queue
{
Queue() : head_(new Node), tail_(head_) {}
void push(const Any & val)
{
assert(tail_);
std::auto_ptr< Node > new_tail(new Node);
tail_->val_ = val;
Node * old_tail(xchg(tail_, new_tail.release()));
assert(old_tail == 0);
}
Any pop()
{
assert(head_);
Node * new_head(xchg(head_->next_, 0));
if (new_head != 0)
{
Any retval(head_->val_);
delete head_;
head_ = new_head;
return retval;
}
else
throw Exceptions::Empty();
}
Node * head_; // usable only by consumer
Node * tail_; // usable only by producer
};
> http://groups.google.com/group/comp.programming.threads/msg/a359bfb41...
>
> If so, that works fine; indeed it has wait-free consumers. However, the
> vZOOM model can still outperform it by quite a large margin simply because
> it does not use interlocking, has wait-free producer and consumer operations
> and is highly-distributed/NUMA-friendly.
What I gather from vZOOM is that only write operations are interlocked
(or even synchronized) and that you try to reduce write operations to
a strict minimum by consuming in large batches rather than in single
nodes. In my case, that would boil down to iterating to the
(perceived) en of the queue and cutting it off there, which would
reduce the number of XCHGs to one per batch of reads in stead of one
per read (e.g. if there are five writes between two reads, there would
be a total of seven XCHGs in stead of twelve). That is a nice idea..
> I want the wait-free observer to be a multi-threaded daemon that can allow
> multiple threads to create/register delegates; message-types and allow
> consumer threads to register with those delegates and receive their
> messages; producer threads create messages with subsequently signal the
> delegates that manages those messages to multicast to their registered
> consumers.
Which is very, *very* close to my Mediator implementation..
> > As for a Factory, I don't see why a factory would have to know about
> > threading unless you want the factory to keep track of whatever it's
> > created. Other than that, you just need a thread-safe memory manager..
>
> > Or perhaps I don't quite see the problem you're seeing.
>
> I want to implement the wait-free factory as a multi-threaded daemon process
> that multiple producers can register the path and name of a shared library,
> which concurrent consumer processes can lookup by name; dynamically link
> with the resulting library and call a "common" instance function (e.g.,
> define common api). I guess you could think of it as a highly concurrent
> per-computer COM daemon. The factory consumer threads can use the lock-free
> reader pattern, and the producer threads can use a form of mutual exclusion;
> including, but not limited, to locks.
OK, but what does the factory create?
> > As for a scripting language: I see scripting languages as a convenient
> > way for gluing otherwise disparate blocks of code together, or to make
> > decisions with "on-the-fly" logic (i.e. logic that wasn't built into
> > whatever you were building at the time). So the question really is:
> > what are you going to want to glue together? Message passing is a nice
> > abstraction for that: you just need to be able to create a message and
> > pass it into the mill, and to create whatever logic is needed to
> > handle the message and have that run by the mill. I can see a nice
> > opportunity for a scripting language there.
>
> Yeah. BTW, are there any scripting langs that have a message passing
> interface for their basic method of operation? Simply create a script and
> enqueue it onto the message system, and wait/pool on its subsequent
> resulting data. Humm...
not really: DCOM basically allows a (scripting) language to create a
network-transparent object with an underlying messaging protocol much
like CORBA, and I hear Erlang is message-passing-based (but haven't
taken the time to look closely at that) but neither is explicitly
multi-threaded and I don't think the DCOM-based scripting languages
(such as Visual Basic) allow for asynchronous operation - but I don't
know any of those languages, at all. I do know CORBA, however, as I
use it in a distributed multi-platform architecture... but CORBA only
uses "one-way" messages for asynchronous things...
rlc
Chris Thomasson
news:4700bb3f$0$4528$9b4e...@newsspool3.arcor-online.net...
> Sorry, most traffic here is about MT-progtamming; so this group
> isn't dying.
Okay... Well, it seems that the traffic is going to be broken up a bit...
Why post here if your question is about C++ and threading?
> I'm pretty sute you'll call this group dying as long
> as the whole traffic isn't about lock-free programming.
;^)
blytkerchan
> "Elcaro Nosille" <Elcaro.Nosi...@mailinator.com> wrote in message
>
> news:4700bb3f$0$4528$9b4e...@newsspool3.arcor-online.net...
>
> > Sorry, most traffic here is about MT-progtamming; so this group
> > isn't dying.
>
> Okay... Well, it seems that the traffic is going to be broken up a bit...
> Why post here if your question is about C++ and threading?
You'd probably cross-post it to c.l.c++[.mod] and here, but I'd have a
tendency to expect questions on c.l.c++[.mod] to be far more C++-
oriented than threading-oriented, which would mean the signal/noise
ratio for threading will continue to be much better here than on c.l.c+
+[.mod].
rlc
Chris Thomasson
> On Oct 1, 7:37 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
>> "blytkerchan" <blytkerc...@gmail.com> wrote in message
>> news:1191204480.2...@o80g2000hse.googlegroups.com...
>> > On Sep 29, 5:53 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
>> >> [...]
>> >> >> The question remains, though: what is the problem domain?
>> >> Problem/Question:
>> >> - How to efficiently solve shared-memory coherency issues in
>> >> software?
>> >> Possible Solution:
>> >> - Virtually Zero-Overhead:
>> [...]
>> >> Any thoughts?
>>
>> > I like the producer/consumer abstraction a lot, but your vZOOM will
>> > only work in single-producer single-consumer cases if you don't want
>> > to use either locks or interlocked instructions - at least I don't
>> > really see how it could work with multiple producers or multiple
>> > consumers.
>>
>> You have to use distributed model.
>
> Si you basically use single-producer single-consumer queues in much
> the same way as the "input queues" and "output queues" I was talking
> about a few days ago. You solve the multi-producer/multi-consumer
> problem by hashing your pointer and you can always compensate for a
> mis-attribution of a task through work stealing.
Basically, yes.
> It's certainly a scalable approach, and if your virtually-zero
> overhead is really virtually zero,
Well, it actually is... For instance, on x86 the push function is made up of
five (5 mov) instructions. The pop function is (1 push; 5 mov; 1 cmp; 1 xor;
1 pop; ret) for 10 instructions.... The push and pop combined is only 15
instructions. IMHO, that is virtually zero overhead when compared to an
implementation that uses the LOCK prefix or an mfence instruction.
> the cost of having two queues per
> thread is negligeable next to the use of locks.
Yup, that would be a bi-directional communication channel. You can make the
number of per-thread spsc queues dynamic. This could allow you to implement
a fully connected wait-free network of threads. I have this working for
threads; I need to do a process-wide implementation here shortly.
>> > For observers, I usually use a generic non-threaded implementation
>>
>> [...]
>>
>> I kind of like doing it with a single disributer thread; like the diagram
>> I
>> linked to shows.
>
> That is actually pretty close to what I would do for a dispatcher-
> based Mediator implementation: a single multi-producer/single-
> consumer queue toward the dispatcher thread and a single-producer/
> single-consumer queue between the dispatcher and each consumer of an
> observable event. The dispatcher basically works as a switchboard,
> delivering its messages to the interested observers according to their
> types (required quite a bit of template meta-programming, that
> one :) )
That works well. It seems that the only main difference between our setups
is I am using the distributed mp/sc queue scheme instead single mp/sc queue.
>> > I have one global queue
>>
>> One global lock-free queue can cause quite a bit of overhead.
[...]
>
> The basic idea is that an empty queue consists of a single node with a
> NULL as its "next"node. Its value is writable by the producer until
> that producer has put a new "next" node in place.
[...]
>As both the head and the tail can only be mutated by a single
> thread, there's no locking required for those.
[...]
> I.e., the queue looks a bit like this (pseudo-code)
[...]
Okay... That would be a sp/sc queue right? Looks interesting. BTW, the
pseudo-code seems wait-free all the way through; I don't see any looping...
Need to study this some more...
>> http://groups.google.com/group/comp.programming.threads/msg/a359bfb41...
>>
>> If so, that works fine; indeed it has wait-free consumers. However, the
>> vZOOM model can still outperform it by quite a large margin simply
>> because
>> it does not use interlocking, has wait-free producer and consumer
>> operations
>> and is highly-distributed/NUMA-friendly.
>
> What I gather from vZOOM is that only write operations are interlocked
> (or even synchronized) and that you try to reduce write operations to
> a strict minimum by consuming in large batches rather than in single
> nodes.
Yes and no:
- Yes in the sense that vZOOM algorithms use many different amortization
techniques overall; batching is perfect for this.
- No in the sense that vZOOM has algorithms that can perform write
operations that do not use any interlocking; think of the sp/sc queue.
> In my case, that would boil down to iterating to the
> (perceived) en of the queue and cutting it off there, which would
> reduce the number of XCHGs to one per batch of reads in stead of one
> per read (e.g. if there are five writes between two reads, there would
> be a total of seven XCHGs in stead of twelve). That is a nice idea..
The amortization via. batching should allow your applications to experience
marked improvements in scalability, throughput and overall performance...
>> I want the wait-free observer to be a multi-threaded daemon that can
>> allow
>> multiple threads to create/register delegates; message-types and allow
>> consumer threads to register with those delegates and receive their
>> messages; producer threads create messages with subsequently signal the
>> delegates that manages those messages to multicast to their registered
>> consumers.
>
> Which is very, *very* close to my Mediator implementation..
Its a good model. Very straightforward imho, no complicated crap in there...
>> > As for a Factory, I don't see why a factory would have to know about
>> > threading unless you want the factory to keep track of whatever it's
>> > created. Other than that, you just need a thread-safe memory manager..
>>
>> > Or perhaps I don't quite see the problem you're seeing.
>>
>> I want to implement the wait-free factory as a multi-threaded daemon
>> process
>> that multiple producers can register the path and name of a shared
>> library,
>> which concurrent consumer processes can lookup by name; dynamically link
>> with the resulting library and call a "common" instance function (e.g.,
>> define common api). I guess you could think of it as a highly concurrent
>> per-computer COM daemon. The factory consumer threads can use the
>> lock-free
>> reader pattern, and the producer threads can use a form of mutual
>> exclusion;
>> including, but not limited, to locks.
>
> OK, but what does the factory create?
The factory basically maps a name to a shared library which exports a common
interface which includes a constructor. For example:
<extreme pseudo-code>
______________________
foo {
void release();
void do_something();
};
libfoo {
foo* foo_ctor();
};
lib-entry {
path;
desc;
};
factory-entry {
name;
lib-entry lib;
};
factory {
factory-entry *list;
};
void factory-produce(lib-entry const* lib, char const* const name) {
factory-entry* fe = new factory-entry(lib, name);
// enqueue fe factory->list
};
lib-entry const* factory-consume(char const* const name) {
factory-entry* lookup = // search factory->list for name;
return &lookup->lib;
};
application() {
{ // register
lib-entry lib("/bin/libfoo.so", "My Foo Library");
factory-produce(&lib, "myfoo");
}
{ // create
lib-entry* lib = factory-consume("myfoo");
if (lib) {
// get the constructor function
foo* (*foo_ctor) () = dynamic_link(lib->name, "foo_ctor");
foo* _foo = foo_ctor(); // call it...
if (_foo) {
_foo->do_something(); // we created a foo!
_foo->release();
}
}
}
};
______________________
Does that make any sense?
;^)
>> > As for a scripting language:
[...]
>>> Message passing is a nice
>> > abstraction for that: you just need to be able to create a message and
>> > pass it into the mill, and to create whatever logic is needed to
>> > handle the message and have that run by the mill. I can see a nice
>> > opportunity for a scripting language there.
>>
>> Yeah. BTW, are there any scripting langs that have a message passing
>> interface for their basic method of operation?
___
>> Simply create a script and
>> enqueue it onto the message system, and wait/pool on its subsequent
>> resulting data. Humm...
___
>
> not really:
[...]
>
> not really:
Humm... Do you think something like that would be "popular"?
Chris Thomasson
> Chris Thomasson schrieb:
>
>>> Sorry, most traffic here is about MT-progtamming; so this group
>>> isn't dying.
>
>> Okay... Well, it seems that the traffic is going to be broken up
>> a bit... Why post here if your question is about C++ and threading?
>
> people use ready-to-use C++-MT-components (like from boost) and
> don't use yours.
You read into things to much...
> Get a life!
Did you used to get beat up a lot when you were a child?
Chris Thomasson
> Chris Thomasson schrieb:
>
>>> Because you can also write MT-apps in C++. Seems to hurt you
>>> when people use ready-to-use C++-MT-components (like from
>>> boost) and don't use yours.
>
>> You read into things to much...
>
Well, perhaps you should study some more because your conclusions wrt this
matter are wrong.
>>> Get a life!
>
>> Did you used to get beat up a lot when you were a child?
>
> No.