Hi,
I realize that my recent question about thread-safe caches was pretty
ambiguous. So here is a question narrowed down to something simpler,
which is hopefully more straightforward to answer.
Assume there is a global variable *var*, for example defined like this:
(cl:defvar *var* 42)
Assume there is exactly one thread forever executing the following loop:
(cl:loop
(cl:setf *var* 42)
(cl:setf *var* 84))
Furthermore, assume that other threads either don't touch *var* at all,
or only read from it.
Is it safe to assume that the reading threads will only ever read the
values 42 or 84 from *var*, or should one take into account that every
now and then, *var* may contain garbage (i.e., a bit pattern that
consists partly of the bits of 42, and partly of the bits of 84)?
To generalize, are there datatypes for which it is not safe to assume
that variable assignments are thread-safe in that sense?
What about plain references?
[Since ANSI Common Lisp doesn't say anything about multithreading, this
is by definition implementation-dependent, but nevertheless how
sufficiently safe is it to assume thread-safe variable assignments?]
Thanks for any comments,
Pascal
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
Pascal Costanza <··@p-cos.net> writes:
> Hi,
>
> I realize that my recent question about thread-safe caches was pretty
> ambiguous. So here is a question narrowed down to something simpler,
> which is hopefully more straightforward to answer.
Well, perhaps, but you've been telling us that your caches are
implemented as plists, so this is actually not the same question
simplified, but a different question.
> Assume there is a global variable *var*, for example defined like this:
>
> (cl:defvar *var* 42)
>
> Assume there is exactly one thread forever executing the following loop:
>
> (cl:loop
> (cl:setf *var* 42)
> (cl:setf *var* 84))
>
> Furthermore, assume that other threads either don't touch *var* at
> all, or only read from it.
>
> Is it safe to assume that the reading threads will only ever read the
> values 42 or 84 from *var*, or should one take into account that every
> now and then, *var* may contain garbage (i.e., a bit pattern that
> consists partly of the bits of 42, and partly of the bits of 84)?
I think that for most CLs, the answer is that the store into the word
is atomic. Note that I don't use the word "thread-safe" - that is a
different idea with a different answer (for it, you would have to
introduce the idea that two threads might modify the value if *var*).
> To generalize, are there datatypes for which it is not safe to assume
> that variable assignments are thread-safe in that sense?
Anything that must store or read/store into more than one location at
a time. More precisely, instructions themselves tend to be atomic,
but multiple instructions are not. Since storage of anything with
more than one instruction is thus non-atomic, a second processor could
in theory see a state where part of the structure is modified and part
unmodified.
> What about plain references?
Same situation. If the reference is performed in an instruction, then
it will be
> [Since ANSI Common Lisp doesn't say anything about multithreading,
> this is by definition implementation-dependent, but nevertheless how
> sufficiently safe is it to assume thread-safe variable assignments?]
In Allegro CL, there are two different kinds of references to
globally-special variables. If in the current thread the variable is
not bound at least once in a let or lambda form, then there is a
single global location that the variable is stored equivalent to
(sys:global-symbol-value '*var*). If the variable is bound, however,
e.g. as (let ((*var* nil)) (do-the-test-loop)) then there is not even
an issue of thread-safety; each value for the symbol is kept on a
per-thread basis, and is considered to be thread-local, and so it is
inherently safe.
--
Duane Rettig ·····@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
Hi Pascal,
On Wed, Nov 07, 2007 at 12:57:14PM +0100, Pascal Costanza wrote:
> [Since ANSI Common Lisp doesn't say anything about multithreading, this is by definition
> implementation-dependent, but nevertheless how sufficiently safe is it to assume thread-safe variable
> assignments?]
If it isn't implemented thread-safe, it isn't ;).
When just incrementing an integer you are normally getting three machine instructions:
- Load variable in register
- Increment register's value
- Store register's value in variable
After each instruction your thread's schedule could be exhausted,
leaving the variable in an undefined state.
There are cpu depended atomic (thread-safe) operations for incrementing
and variable assigment.
Or are you asking for something completely different?
Cheers,
Daniel
Daniel Trstenjak wrote:
> Hi Pascal,
>
> On Wed, Nov 07, 2007 at 12:57:14PM +0100, Pascal Costanza wrote:
>> [Since ANSI Common Lisp doesn't say anything about multithreading, this is by definition
>> implementation-dependent, but nevertheless how sufficiently safe is it to assume thread-safe variable
>> assignments?]
>
> If it isn't implemented thread-safe, it isn't ;).
>
> When just incrementing an integer you are normally getting three machine instructions:
> - Load variable in register
> - Increment register's value
> - Store register's value in variable
>
> After each instruction your thread's schedule could be exhausted,
> leaving the variable in an undefined state.
>
> There are cpu depended atomic (thread-safe) operations for incrementing
> and variable assigment.
>
>
> Or are you asking for something completely different?
Only storing values in variables, nothing else. No reading, no
incrementing or other modifications of old values, just plain storing.
Plain storing itself could already be non-atomic, but it would be good
if I could assume that it is atomic in typical CL implementations...
Pascal
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
On Nov 7, 1:14 pm, Daniel Trstenjak <················@online.de>
wrote:
> Hi Pascal,
>
> On Wed, Nov 07, 2007 at 12:57:14PM +0100, Pascal Costanza wrote:
> > [Since ANSI Common Lisp doesn't say anything about multithreading, this is by definition
> > implementation-dependent, but nevertheless how sufficiently safe is it to assume thread-safe variable
> > assignments?]
>
> If it isn't implemented thread-safe, it isn't ;).
>
> When just incrementing an integer you are normally getting three machine instructions:
> - Load variable in register
> - Increment register's value
> - Store register's value in variable
>
> After each instruction your thread's schedule could be exhausted,
> leaving the variable in an undefined state.
>
> There are cpu depended atomic (thread-safe) operations for incrementing
> and variable assigment.
>
> Or are you asking for something completely different?
>
> Cheers,
> Daniel
Since any other thread would reload its own state including registers,
the other threads would be pulling from memory so they would get
whatever was in memory at the time. In this case they would get one
of the two values but never anything else. A memory store from a
register should be atomic for simple values at least.
On Wed, 07 Nov 2007 12:57:14 +0100, Pascal Costanza <··@p-cos.net>
wrote:
>Hi,
>
>I realize that my recent question about thread-safe caches was pretty
>ambiguous. So here is a question narrowed down to something simpler,
>which is hopefully more straightforward to answer.
>
>Assume there is a global variable *var*, for example defined like this:
>
>(cl:defvar *var* 42)
>
>Assume there is exactly one thread forever executing the following loop:
>
>(cl:loop
> (cl:setf *var* 42)
> (cl:setf *var* 84))
>
>Furthermore, assume that other threads either don't touch *var* at all,
>or only read from it.
>
>Is it safe to assume that the reading threads will only ever read the
>values 42 or 84 from *var*, or should one take into account that every
>now and then, *var* may contain garbage (i.e., a bit pattern that
>consists partly of the bits of 42, and partly of the bits of 84)?
>
>To generalize, are there datatypes for which it is not safe to assume
>that variable assignments are thread-safe in that sense?
>
>What about plain references?
>
>[Since ANSI Common Lisp doesn't say anything about multithreading, this
>is by definition implementation-dependent, but nevertheless how
>sufficiently safe is it to assume thread-safe variable assignments?]
>
>
>Thanks for any comments,
>Pascal
You'll never perceive a partially updated single word value - all
single word reads and writes are atomic. The only possibility would
be a delay in propagating the new value on a separate memory
multi-processor - shared memory multi-processors use cache snooping to
keep their view of memory consistent.
Multiple word updates are not safe without synchronization.
Keep in mind though that fixnum updates aren't truly an atomic
operation in Lisp. Tagging the value and writing it to memory takes a
couple of instructions - another thread could potentially sneak in and
read the old value between the time setf is called and the time the
tagged value is actually written to memory. This is unlikely to
matter to you, but I mention it for completeness.
A problem you may encounter is that compiler optimizations might
prevent another thread from seeing the updates even on a single CPU.
Unless the compiler knows the object may be modified by foreign code,
it may cache the value in a register and ignore updates in memory.
The C term for this is a "volatile" variable.
I don't have much multi-thread experience in Lisp - but I would expect
that because many common objects are actually multi-word structures,
that multi-thread implementations either use critical sections
internally or punt synchronization to the programmer. I would say
some quality time with the compiler manual is in order.
George
--
for email reply remove "/" from address
On Thu, 08 Nov 2007 01:09:26 -0500, George Neuner <·········@/comcast.net> wrote:
> I don't have much multi-thread experience in Lisp - but I would
> expect that because many common objects are actually multi-word
> structures, that multi-thread implementations either use critical
> sections internally or punt synchronization to the programmer. I
> would say some quality time with the compiler manual is in order.
The problem is that spending some quality time with the compiler
manual doesn't help, no matter which CL implementation you're
using.[*] As Pascal said, Java is exceptionally well-documented
w.r.t. these issues, but for CL you'll find almost nothing.
Therefore, I'm thankful that Pascal has started this "survey" (parts
of which can also be found on the LispWorks and OpenMCL mailing lists,
for example) which spurred some interesting and educating replies so
far.
I'd be even more thankful if someday we'd find a summary of this
discussion somewhere or, even better, if the Lisp vendors would at
least partly document these issues in their manuals.
Edi.
[*] My apologies if I missed something. If I did, please post the
URLs here.
--
Lisp is not dead, it just smells funny.
Real email: (replace (subseq ·········@agharta.de" 5) "edi")
On Thu, 08 Nov 2007 08:49:57 +0100, Edi Weitz <········@agharta.de>
wrote:
>The problem is that spending some quality time with the compiler
>manual doesn't help, no matter which CL implementation you're
>using.[*]
>[*] My apologies if I missed something. If I did, please post the
> URLs here.
IMO, Corman's user documentation is fairly good with respect to
threads, but it may be an exception. Corman explicitly states that
the kernel is thread safe but most library functions are _not_ yet
fully thread safe and it is up to the programmer to synchronize data
access.
Seeing some of the other responses to Pascal's question, I'm thinking
that "not fully thread safe" may be the dominant model everywhere. I
guess I would just assume the worst and program defensively.
George
--
for email reply remove "/" from address
George Neuner wrote:
> Seeing some of the other responses to Pascal's question, I'm thinking
> that "not fully thread safe" may be the dominant model everywhere. I
> guess I would just assume the worst and program defensively.
>
What does thread safe and not thread safe mean.
As I have stated before I have little Lisp experience
but I have gone through (as a user) single threading to multi threading
transitions of various thing (libs, language compilers) in envs like DOS
to OS/2, from Win3.1 to WIN95/NT and from early Java where everything
was 'thread safe' to current java where 'everything' is 'not thread safe'
I hope people implementing libs and compilers for Lisp have a better
understanding of things and don't go the route of making everything
'thread safe'. Unlike Java, Lisp does not have the luxury of telling
people to start using ArrayList
(http://java.sun.com/j2se/1.4.2/docs/api/java/util/Vector.html)
instead of Vector
(http://java.sun.com/j2se/1.4.2/docs/api/java/util/Vector.html)
(because Vector does not scale)
cause we have existing stuff that just needs a sane mutli-threaded
definition. For example, I do not think car and cdr should be thread
safe in the sense of the java Vector , but of course we can *not* be
having things not thread safe in the sense of strtok
I am writing solely cause I'd like to get some assurance that people in
the libs and compilers business do understand the cost of making
everything 'thread safe' (although I am pretty sure the compilers guys do)
Can somebody please tell me not to worry.
-Antony
On Fri, 09 Nov 2007 18:09:33 -0800, Antony Sequeira
<··················@gmail.com> wrote:
>George Neuner wrote:
>> Seeing some of the other responses to Pascal's question, I'm thinking
>> that "not fully thread safe" may be the dominant model everywhere. I
>> guess I would just assume the worst and program defensively.
>>
>What does thread safe and not thread safe mean.
"Thread safe" means having 2 guarantees:
1) while _any_ thread is accessing an object for reading, other
threads will be prevented from accessing it for writing, and
2) while a thread is accessing an object for writing, _all_ other
threads will be prevented from accessing it.
It does _not_ mean mutual exclusion. It is perfectly safe for
multiple threads to read data simultaneously.
There are various synchronization methods for ensuring that the safety
guarantees hold. The methods differ in whether they give priority to
reading or to writing and in whether threads waiting for access are
blocked.
>I am writing solely cause I'd like to get some assurance that people in
>the libs and compilers business do understand the cost of making
>everything 'thread safe' (although I am pretty sure the compilers guys do)
>Can somebody please tell me not to worry.
I'd love to but I can't. Most people seem to have enormous problems
coping with threads and shared data. Update synchronization failures
are among the most common bugs found in modern programs. Programming
practice is marching inexorably toward providing more safety for the
average programmer at the expense of performance and utility for the
gifted programmer.
If you've been following this thread and the previous one, you know
that some people here are arguing for automatic safety, ie. compiler
directed locking - which is an extremely hard problem. It is
effectively impossible to identify at compile time all the data which
will be shared at run time. In theory a whole program analysis could
do so, but it would be prohibitively time consuming. Shared data can
be accurately identified at run time, but it's actually more efficient
just to unconditionally lock heap objects during access whether they
are shared or not.
The alternative to locking is to use immutable data. Data structures
that are never modified never have to be locked except possibly during
their initial creation. It is always safe to have simultaneous access
to immutable data. This is the route most functional languages are
going (but not Common Lisp or Scheme, both of which are only "sort of"
functional).
George
--
for email reply remove "/" from address
On Sun, Nov 11 2007, George Neuner wrote:
> ...
> Most people seem to have enormous problems coping with threads and
> shared data. Update synchronization failures are among the most
> common bugs found in modern programs.
If most people have a problem with a particular technology then should
we blame it on the people or the technology?
> Programming practice is marching inexorably toward providing more
> safety for the average programmer at the expense of performance and
> utility for the gifted programmer.
Multi-threaded programs based on preemptive threading are inherently
slow. They haven't been introduced because they provide performance,
but because they provide utility. They are harder to write to the
gifted programmer and a bad idea to be assigned to the average
programmer. In other words no matter how gifted a programmer is the
model of using preemptive threading introduces another layer of
complexity.
People tend to associate preemptive threading with low level
programming, but that is a mistake, because generally low level
programming provides high performance on the cost of greater
complexity. With the preemptive threading we gain nothing in this
aspect as on the cost of greater complexity we add low performance!
In contrast the non-preemptive thread model provides both utility for
the user and greatest performance for the programmer on some little
programming cost. I'd also argue that this model is usually
appropriate for the average programmer as libraries could be designed
in a way that they relieve the programmer from the obligation of
yielding control. It is only that the model (AFAIK) is inappropriate
in some cases when the program runs on the currently pervasive
multi-processing systems.
> ...
--
Kamen
On Sun, 11 Nov 2007 15:29:21 +0200, Kamen TOMOV <·····@cybuild.com>
wrote:
>On Sun, Nov 11 2007, George Neuner wrote:
>
>> ...
>> Most people seem to have enormous problems coping with threads and
>> shared data. Update synchronization failures are among the most
>> common bugs found in modern programs.
>
>If most people have a problem with a particular technology then should
>we blame it on the people or the technology?
In this case, I believe the fault lies with the people. I've
maintained for years that the majority of programmers should do the
world a service and explore other employment opportunities.
I've been programming for more than 20 years and I've written a lot of
threaded code - much of it for high availability, real time or high
performance systems, most of it under time pressure to quickly bring a
product to market. I never had much trouble with threads to begin
with, but I also had the benefit of learning good coding practices
from some very skilled programmers.
Most people writing thread code have learned from books or help files
- most have no formal CS schooling and neither training nor more
experienced coders to guide them and so it's little wonder that they
run into trouble. I have a MSCS from a good school and I was aware of
synchronization problems, but virtually all of my knowledge of good
coding practices came from industry experience.
Programmers can be taught to identify potential synchronization
problems in a design and to program defensively to avoid the problems
in the first place. I've experienced it and I've done it.
>Multi-threaded programs based on preemptive threading are inherently
>slow.
Preemption has little to do with it - any form of multiprogramming
sans additional compute resources will run slower than equivalent
serial code - if there is equivalent serial code.
Many threaded programs are slower than necessary because they are
poorly written and/or they running on OSes (or worse VMs) that are
designed for fair CPU access rather than optimal performance.
The scheduling policy makes a huge difference in performance. Get
yourself a preemptive RTOS and see what a difference it makes running
on the same hardware.
Then too, programmers tremendously overuse threads in situations where
they really don't make sense. It seems that once people learn about
threads, they see potential for them everywhere. This goes back to
"code is poorly written"
>They haven't been introduced because they provide performance,
>but because they provide utility. They are harder to write to the
>gifted programmer and a bad idea to be assigned to the average
>programmer. In other words no matter how gifted a programmer is the
>model of using preemptive threading introduces another layer of
>complexity.
Threaded programs are not much harder to write if thought about
properly. Raise your hand if you've read "Communicating Sequential
Processes". Ok, that might be a bad example here in c.l.l., but if
you were to take a poll in the general programmer population, I'd bet
better than 90% have never heard of it, let alone read it.
Conversely, I'd bet more than 90% have heard of and read "Design
Patterns".
Actually, apart from a few hands-on OS textbooks I've seen, most books
that tackle threads suck with regard to teaching synchronization
issues. In many cases the books are no more than a glorified help
file for some language or system. If there is discussion of potential
problems, it is usually theoretical and brief ... if you're really
lucky the philosophers will come to dinner and there may be a few
exercises.
What is almost uniformly missing is presentation of a lot of real
world thread scenarios that are likely to be encountered and thorough
discussion of why the code doesn't work as written and how it might be
fixed.
>People tend to associate preemptive threading with low level
>programming, but that is a mistake, because generally low level
>programming provides high performance on the cost of greater
>complexity. With the preemptive threading we gain nothing in this
>aspect as on the cost of greater complexity we add low performance!
>
>In contrast the non-preemptive thread model provides both utility for
>the user and greatest performance for the programmer on some little
>programming cost. I'd also argue that this model is usually
>appropriate for the average programmer as libraries could be designed
>in a way that they relieve the programmer from the obligation of
>yielding control. It is only that the model (AFAIK) is inappropriate
>in some cases when the program runs on the currently pervasive
>multi-processing systems.
So you're arguing for cooperative multitasking.
Partial updates are unlikely in cooperative code, but there are plenty
of other pitfalls for the unwary - some of them the same as in
preemptive code. Non-reentrant code can be reentered. Use of
asynchronous communication can lead to unintentional data sharing,
missed updates to shared data, etc. Use of synchronous communication
can lead to really lousy performance or even to deadlock in some
systems. The programmer can fail to yield, starve threads by not
yielding enough or (paradoxically) by yielding too often, transfer
control to the wrong thread(s), etc.
It's been my experience that newbies have no more luck writing
cooperative thread code than preemptive. The problems are no easier
to find once noticed and unexperienced programmers are often more
confused when cooperative code breaks because they "couldn't have done
anything wrong".
George
--
for email reply remove "/" from address
On Mon, Nov 12 2007, George Neuner wrote:
> On Sun, 11 Nov 2007 15:29:21 +0200, Kamen TOMOV <·····@cybuild.com>
> wrote:
>
>>On Sun, Nov 11 2007, George Neuner wrote:
>>
>>> ...
>>> Most people seem to have enormous problems coping with threads and
>>> shared data. Update synchronization failures are among the most
>>> common bugs found in modern programs.
>>
>>If most people have a problem with a particular technology then
>>should we blame it on the people or the technology?
>
> In this case, I believe the fault lies with the people. I've
> maintained for years that the majority of programmers should do the
> world a service and explore other employment opportunities.
>
> I've been programming for more than 20 years and I've written a lot
> of threaded code - much of it for high availability, real time or
> high performance systems, most of it under time pressure to quickly
> bring a product to market. I never had much trouble with threads to
> begin with, but I also had the benefit of learning good coding
> practices from some very skilled programmers.
>
> Most people writing thread code have learned from books or help
> files - most have no formal CS schooling and neither training nor
> more experienced coders to guide them and so it's little wonder that
> they run into trouble. I have a MSCS from a good school and I was
> aware of synchronization problems, but virtually all of my knowledge
> of good coding practices came from industry experience.
>
> Programmers can be taught to identify potential synchronization
> problems in a design and to program defensively to avoid the problems
> in the first place. I've experienced it and I've done it.
>
>
>>Multi-threaded programs based on preemptive threading are inherently
>>slow.
>
> Preemption has little to do with it - any form of multiprogramming
> sans additional compute resources will run slower than equivalent
> serial code - if there is equivalent serial code.
>
> Many threaded programs are slower than necessary because they are
> poorly written and/or they running on OSes (or worse VMs) that are
> designed for fair CPU access rather than optimal performance.
>
> The scheduling policy makes a huge difference in performance. Get
> yourself a preemptive RTOS and see what a difference it makes
> running on the same hardware.
>
> Then too, programmers tremendously overuse threads in situations
> where they really don't make sense. It seems that once people learn
> about threads, they see potential for them everywhere. This goes
> back to "code is poorly written"
>
>
>>They haven't been introduced because they provide performance, but
>>because they provide utility. They are harder to write to the
>>gifted programmer and a bad idea to be assigned to the average
>>programmer. In other words no matter how gifted a programmer is the
>>model of using preemptive threading introduces another layer of
>>complexity.
>
> Threaded programs are not much harder to write if thought about
> properly. Raise your hand if you've read "Communicating Sequential
> Processes". Ok, that might be a bad example here in c.l.l., but if
> you were to take a poll in the general programmer population, I'd
> bet better than 90% have never heard of it, let alone read it.
> Conversely, I'd bet more than 90% have heard of and read "Design
> Patterns".
>
> Actually, apart from a few hands-on OS textbooks I've seen, most
> books that tackle threads suck with regard to teaching
> synchronization issues. In many cases the books are no more than a
> glorified help file for some language or system. If there is
> discussion of potential problems, it is usually theoretical and
> brief ... if you're really lucky the philosophers will come to
> dinner and there may be a few exercises.
>
> What is almost uniformly missing is presentation of a lot of real
> world thread scenarios that are likely to be encountered and thorough
> discussion of why the code doesn't work as written and how it might be
> fixed.
>
>
>>People tend to associate preemptive threading with low level
>>programming, but that is a mistake, because generally low level
>>programming provides high performance on the cost of greater
>>complexity. With the preemptive threading we gain nothing in this
>>aspect as on the cost of greater complexity we add low performance!
>>
>>In contrast the non-preemptive thread model provides both utility
>>for the user and greatest performance for the programmer on some
>>little programming cost. I'd also argue that this model is usually
>>appropriate for the average programmer as libraries could be
>>designed in a way that they relieve the programmer from the
>>obligation of yielding control. It is only that the model (AFAIK) is
>>inappropriate in some cases when the program runs on the currently
>>pervasive multi-processing systems.
>
> So you're arguing for cooperative multitasking.
>
> Partial updates are unlikely in cooperative code, but there are
> plenty of other pitfalls for the unwary - some of them the same as
> in preemptive code. Non-reentrant code can be reentered. Use of
> asynchronous communication can lead to unintentional data sharing,
> missed updates to shared data, etc. Use of synchronous
> communication can lead to really lousy performance or even to
> deadlock in some systems. The programmer can fail to yield, starve
> threads by not yielding enough or (paradoxically) by yielding too
> often, transfer control to the wrong thread(s), etc.
>
> It's been my experience that newbies have no more luck writing
> cooperative thread code than preemptive. The problems are no easier
> to find once noticed and unexperienced programmers are often more
> confused when cooperative code breaks because they "couldn't have
> done anything wrong".
IMO it is the technology to blame, not the people. One of the reasons
I don't like preemptive threading is that it's unnatural. Imagine what
would be if humans had preemptive threading implemented in their
brains. What if the moment I see a long-legged, blond walking towards
me the scheduler switches to... the hardships of finding side mirrors
for my car (and I assure you - that's an awful context that would doom
me to failure with the blond). No matter how smart the scheduler is -
he would never outsmart the programmer (God). So He created us
interrupt driven and green threaded.
Another aspect of the issue can be observed in web development. The
fact that PHP outperforms Java in popularity (and grows fast)
testifies that evolution wouldn't put up with threads. [For those of
you who are lucky to be born out of the Matrix - the contemporary Java
prog lang is using preemptive threading and PHP has no built in
support for threading.]
As to the ease of use of the technology - although, your points are
valid, it is *usually* easier to write code that is meant to be run on
non-preemptive machines than code meant to be run in preemptive ones,
but of course I shouldn't overgeneralize so much as there are a few
cases when that's not the case.
--
Kamen
On 2007-11-12 17:39:27 -0500, Kamen TOMOV <·····@cybuild.com> said:
> What if the moment I see a long-legged, blond walking towards
> me the scheduler switches to... the hardships of finding side mirrors
> for my car (and I assure you - that's an awful context that would doom
> me to failure with the blond). No matter how smart the scheduler is -
> he would never outsmart the programmer (God). So He created us
> interrupt driven and green threaded.
You are speaking of conscious attention *only*. Other processing does
not suspend - your heart doesn't stop beating, you continue to process
sound and apprehend words, you continue to be able to speak, swallow,
walk, digest food, etc.
In general your analogy is not the best because your nervous system is
*truly* parallel, with different "threads" of execution (read:
different brain regions) operating simultaneously all the time.
In general the issues you allude to should (imho) be dealt with by
means of thread priorities. Then, in your example, your "brain" would
deal with these "blonde interrupts" by setting the associated task's
"thread" priority to a higher/more real-time policy.
On Tue, Nov 13 2007, Raffael Cavallaro wrote:
> On 2007-11-12 17:39:27 -0500, Kamen TOMOV <·····@cybuild.com> said:
>
>> What if the moment I see a long-legged, blond walking towards me
>> the scheduler switches to... the hardships of finding side mirrors
>> for my car (and I assure you - that's an awful context that would
>> doom me to failure with the blond). No matter how smart the
>> scheduler is - he would never outsmart the programmer (God). So He
>> created us interrupt driven and green threaded.
>
> You are speaking of conscious attention *only*. Other processing
> does not suspend - your heart doesn't stop beating, you continue to
> process sound and apprehend words, you continue to be able to speak,
> swallow, walk, digest food, etc.
Correct, but, the processes you are talking about are either involving
the peripheral nervous system or other processing areas of the
brain. We can look at those areas as different processing units.
> In general your analogy is not the best because your nervous system is
> *truly* parallel, with different "threads" of execution (read:
> different brain regions) operating simultaneously all the time.
We can look at these happenings as processes and not as threads,
because they are not so dependent on each other. The key point is that
they generally does not take advantage of our attention unless some
special occasion happens.
> In general the issues you allude to should (imho) be dealt with by
> means of thread priorities. Then, in your example, your "brain" would
> deal with these "blonde interrupts" by setting the associated task's
> "thread" priority to a higher/more real-time policy.
>
As my argument is that these are not threads but processes the theory
of thread priorities does not apply.
--
Kamen
On 2007-11-13 19:25:24 -0500, Kamen TOMOV <·····@cybuild.com> said:
> As my argument is that these are not threads but processes the theory
> of thread priorities does not apply.
This is a completely arbitrary distinction. There is no reason why
processing in other parts of the cortex is inherently "not threads but
processes."
The reality is that other brain processing does not stop when you see a
blonde, regardless of how long her legs are.
A better example of interrupts would be the various reflexes which
override voluntary motor control - try swallowing with your teeth
apart, for example.
On Thu, Nov 15 2007, Raffael Cavallaro wrote:
> On 2007-11-13 19:25:24 -0500, Kamen TOMOV <·····@cybuild.com> said:
>
>> As my argument is that these are not threads but processes the
>> theory of thread priorities does not apply.
>
> This is a completely arbitrary distinction. There is no reason why
> processing in other parts of the cortex is inherently "not threads
> but processes."
Why cortex in particular?! What I meant was that there were
specialized areas in the human's nervous system (I didn't specify
whether that's the cortex or else as this knowledge is not only fully
available to the science yet, but also mainly because I studied it
long ago and I rarely use it) that are responsible for certain
functionalities - for example - parts responsible for the visual
perception, other parts for hearing, etc. We should not talk about
threads here because these are separate processing units that are
known to be specialized. There's no perception, within the human's
mind science, that a load balancer exists that dispatches processes to
different areas of the brain depending on the computational
intensity. Instead there are *specialized* areas that constantly
evolve with the human's experience. The single place where one should
look for examples of multi-threading activity are these specialized
areas and I don't think there is an evidence for their existence. I
believe that one of these areas is responsible for the human's
"attention".
> The reality is that other brain processing does not stop when you
> see a blonde, regardless of how long her legs are.
If so, you obviously prefer brunettes :-D
Just kidding.. of course they don't stop - there is no need to in my
theory for the brain processing.
> A better example of interrupts would be the various reflexes which
> override voluntary motor control - try swallowing with your teeth
> apart, for example.
>
That proves what?
--
Kamen
On 2007-11-15 04:34:33 -0500, Kamen TOMOV <·····@cybuild.com> said:
> There's no perception, within the human's
> mind science, that a load balancer exists that dispatches processes to
> different areas of the brain depending on the computational
> intensity.
I think you miss the point of preemptive threads - they *simulate* real
parallel processing (i.e. they can only be truly parallel up to the
number of cores). Cooperative threads do *not* simulate parallel
processing well precisely because one thread can suspend all the others
indefinitely. This can't happen in a preemptive model because the
scheduler won't let one thread lock out all others.
>
>> A better example of interrupts would be the various reflexes which
>> override voluntary motor control - try swallowing with your teeth
>> apart, for example.
>>
>
> That proves what?
That there are nervous system processes which *can* preempt others -
reflexes are an example. My whole point here is that conscious focus on
a particular stimulus (here, the leggy blonde) is *not* such a nervous
system process that preempts other brain processing (hearing, motor
control, etc.). These others merely become unconscious - they do not
suspend.
On Thu, Nov 15 2007, Raffael Cavallaro wrote:
> On 2007-11-15 04:34:33 -0500, Kamen TOMOV <·····@cybuild.com> said:
>
>> There's no perception, within the human's mind science, that a load
>> balancer exists that dispatches processes to different areas of the
>> brain depending on the computational intensity.
>
> I think you miss the point of preemptive threads - they *simulate*
> real parallel processing (i.e. they can only be truly parallel up to
> the number of cores). Cooperative threads do *not* simulate parallel
> processing well precisely because one thread can suspend all the
> others indefinitely. This can't happen in a preemptive model because
> the scheduler won't let one thread lock out all others.
I think you are wrong. There is no evidence for parallel processing in
the sense that resembles preemptive multithreading on a single
processing unit (call it a core if you like) in the human brain. What
we observe there is multiple processes running on multiple processing
units.
To understand the brain processes we can try to model one component of
the human brain and one of the components that we think we know more
than the others is the human's attention.
Take myself for example. I am walking in the park and thinking how
will I be paying my morgage and going to exotic islands in the same
time if I'm self employed Lisp programmer so I'm computing
numbers. The next scene is when the blond enters into my sight. The
calculation is immediatelly stopped and all I'm thinking now is how I
walk on the see coast with her, the water is touching our legs and her
hair is tickling my shoulder. Note that there is no background
computing of morgages and compensations going on in this very
moment. Instead, my attention is fully occupied by the gracious moves
of the blonde. For simplicity let's imagine that her boyfriend
suddenly appears and takes her out of the scene. Some time later I'd
pull the numbers out of the stack and continue with the depressive
computation. So what happened there was a "hardware" interrupt. My
visual perception device interrupted a process and other process
started. There wasn't any stupid scheduler on the way.
OK that was easy so lets take more complex situation for example. Some
time later while I am thinking about a mortgage and the islands the
latter would remind me for the blond and my mind would indulge into
dreams of how we'd have good time together. I'd start thinking that I
should go back and beat the hell out of her boyfriend, tell the blond
that I did it because I love her and because I'd like to spend the
rest of my life with her and will tell her my visions of how we could
be walking together on the seaside and so on and on.
Then I'd look back and would realize that neither the blond nor her
stupid boyfriend could be seen anywhere. I'd be looking her up for a
while and eventually I will decide that I should forget her and should
consider pulling one of the waiting processes that would help me do
it. In other words I'd "yield" so that other process could
continue. What's more I'd find a process that is of greatest
importance (priority) to me. Any scheduler in that situation would be
a missconcept. Instead what we appear to have is cooperative
multiprocessing.
The next question would be if we observing the work of thereads or
processes. My last example is far more likely to model the work of
processes and now I wonder if the concept of threads applies to the
human brain at all. Aren't all these processes that communicate
efficiently...
>>> A better example of interrupts would be the various reflexes which
>>> override voluntary motor control - try swallowing with your teeth
>>> apart, for example.
>>>
>>
>> That proves what?
>
> That there are nervous system processes which *can* preempt others -
> reflexes are an example. My whole point here is that conscious focus
> on a particular stimulus (here, the leggy blonde) is *not* such a
> nervous system process that preempts other brain processing (hearing,
> motor control, etc.). These others merely become unconscious - they do
> not suspend.
It proves nothing - it involves a simple and single processing unit
that is exposed to an interrupt.
Your "whole point" does not prove anything either as it involves
multiple processes happening in multiple processing units.
--
Kamen
On Thu, 15 Nov 2007 21:15:23 +0200, Kamen TOMOV <·····@cybuild.com>
wrote:
>On Thu, Nov 15 2007, Raffael Cavallaro wrote:
>
>> On 2007-11-15 04:34:33 -0500, Kamen TOMOV <·····@cybuild.com> said:
>>
>>> There's no perception, within the human's mind science, that a load
>>> balancer exists that dispatches processes to different areas of the
>>> brain depending on the computational intensity.
>>
>> I think you miss the point of preemptive threads - they *simulate*
>> real parallel processing (i.e. they can only be truly parallel up to
>> the number of cores). Cooperative threads do *not* simulate parallel
>> processing well precisely because one thread can suspend all the
>> others indefinitely. This can't happen in a preemptive model because
>> the scheduler won't let one thread lock out all others.
>
>I think you are wrong. There is no evidence for parallel processing in
>the sense that resembles preemptive multithreading on a single
>processing unit (call it a core if you like) in the human brain. What
>we observe there is multiple processes running on multiple processing
>units.
Actually there is quite a bit of evidence that autonomic processes are
time-multiplexed on the same neurons. There is also evidence from
investigations of memory association that individual neurons can
participate in several recall processes simultaneously.
I agree that pre-emptive multi-programming (I reserve the word
"multi-tasking" to mean multi-processors) is not a realistic model of
activity in the brain, neither is cooperative multi-programming.
The interrupt model is somewhat appropriate to describing processing
at all levels of consciousness. But parallel processing based on an
interrupt model would be far more confusing to the average programmer
than the pseudo-simultaneous serial process model we have now.
George
--
for email reply remove "/" from address
On Thu, Nov 15 2007, George Neuner wrote:
> On Thu, 15 Nov 2007 21:15:23 +0200, Kamen TOMOV <·····@cybuild.com>
> wrote:
>
>>On Thu, Nov 15 2007, Raffael Cavallaro wrote:
>>
>>> On 2007-11-15 04:34:33 -0500, Kamen TOMOV <·····@cybuild.com> said:
>>>
>>>> There's no perception, within the human's mind science, that a
>>>> load balancer exists that dispatches processes to different areas
>>>> of the brain depending on the computational intensity.
>>>
>>> I think you miss the point of preemptive threads - they *simulate*
>>> real parallel processing (i.e. they can only be truly parallel up
>>> to the number of cores). Cooperative threads do *not* simulate
>>> parallel processing well precisely because one thread can suspend
>>> all the others indefinitely. This can't happen in a preemptive
>>> model because the scheduler won't let one thread lock out all
>>> others.
>>
>>I think you are wrong. There is no evidence for parallel processing
>>in the sense that resembles preemptive multithreading on a single
>>processing unit (call it a core if you like) in the human
>>brain. What we observe there is multiple processes running on
>>multiple processing units.
>
> Actually there is quite a bit of evidence that autonomic processes are
> time-multiplexed on the same neurons.
Never heard of that. Could you provide references?
> There is also evidence from investigations of memory association
> that individual neurons can participate in several recall processes
> simultaneously.
>
That looks reasonable and does not contradict with my claim.
Nevertheless, it would be more interesting if individual neurons can
participate not only in simultaneous reads, but in simultaneous
reads and writes and especially in deadlocks :-)
> I agree that pre-emptive multi-programming (I reserve the word
> "multi-tasking" to mean multi-processors) is not a realistic model
> of activity in the brain, neither is cooperative multi-programming.
"Multi-programming" sounds ambiguous to me. Within Lisp
multi-processing is used (:mp) but for clarity we can use
multi-processing and multi-threading depending on the context.
> The interrupt model is somewhat appropriate to describing processing
> at all levels of consciousness.
IMO the interrupt model is appropriate in some cases, but not in
others. It is appropriate when there are "devices" involved and not so
much when it comes to "software" interrupts. To me the latter is
better modeled by the concept of "yields" in cooperative
multiprocessing.
> But parallel processing based on an interrupt model would be far
> more confusing to the average programmer than the
> pseudo-simultaneous serial process model we have now.
Hmm.. why do you think so?
--
Kamen
Kamen TOMOV wrote:
> On Thu, Nov 15 2007, George Neuner wrote:
>
>> On Thu, 15 Nov 2007 21:15:23 +0200, Kamen TOMOV <·····@cybuild.com>
>> wrote:
>>
>>> On Thu, Nov 15 2007, Raffael Cavallaro wrote:
>>>
>>>> On 2007-11-15 04:34:33 -0500, Kamen TOMOV <·····@cybuild.com> said:
>>>> ...
I have a pretty different view ... our brain is a massively parallel
machine, each neuron being some kind of an independant state machine.
There lies the parallelism, at the lowest level. Then you have the main
applications, your thoughts about the blond and those about the
depressing numbers. These higher level programs seem to be sequential
only because they operate at such a different level, and because it is
more efficient to perceive these thoughts as sequential, so that we lean
toward a single goal at a time. Each of those thoughts requires the
parallel processing of thousands (millions ?) of neurons.
That's kind of what we need for multi-processor machines, a compiler
that will automatically distribute the computation across processors.
I hope to see such practical applications during my lifetime.
Sacha
On Fri, 16 Nov 2007 01:10:16 +0200, Kamen TOMOV <·····@cybuild.com>
wrote:
>On Thu, Nov 15 2007, George Neuner wrote:
>
>> On Thu, 15 Nov 2007 21:15:23 +0200, Kamen TOMOV <·····@cybuild.com>
>> wrote:
>>>
>>>There is no evidence for parallel processing
>>>in the sense that resembles preemptive multithreading on a single
>>>processing unit (call it a core if you like) in the human
>>>brain. What we observe there is multiple processes running on
>>>multiple processing units.
>>
>> Actually there is quite a bit of evidence that autonomic processes are
>> time-multiplexed on the same neurons.
>
>Never heard of that. Could you provide references?
Sorry. I have a long time interest in both AI and massively parallel
computation - I try to follow brain research but I don't collect
references.
I *think* I saw it in studies on spinal pathway conduction.
>> There is also evidence from investigations of memory association
>> that individual neurons can participate in several recall processes
>> simultaneously.
>>
>That looks reasonable and does not contradict with my claim.
>
>Nevertheless, it would be more interesting if individual neurons can
>participate not only in simultaneous reads, but in simultaneous
>reads and writes ...
They do.
Every time a neuron activates - ie. its combined dendril charge
exceeds the axonal response threshold - its dendrites move slightly
according to their charge and polarization, narrowing or widening the
gap(s) between themselves and their input axion(s), reinforcing the
neuron's response to the last activation pattern while maintaining as
best as possible its responses to other activation patterns.
In essence every activation is both a read and a write/refresh. But
neurons are not discrete memory cells, a neuron is the summation of a
group of fuzzy accumulators.
>... and especially in deadlocks :-)
Analog circuitry cannot deadlock - conflict states produce either
blurred (summed) output or an oscillation depending on the relative
delays in the conflicting circuits.
>> I agree that pre-emptive multi-programming (I reserve the word
>> "multi-tasking" to mean multi-processors) is not a realistic model
>> of activity in the brain, neither is cooperative multi-programming.
>
>"Multi-programming" sounds ambiguous to me. Within Lisp
>multi-processing is used (:mp) but for clarity we can use
>multi-processing and multi-threading depending on the context.
"Multi-programming" is the historically correct term for interleaved
execution of multiple independent programs on a single CPU. It's use
goes back to the first time-sharing monitors (the forerunners of
modern operating systems).
"Multi-processing" historically referred to actual simultaneous
execution of code, ie. on multiple CPUs.
"Multi-tasking", as it pertains to computing, came originally from
embedded programming which historically referred to processing goals
as "tasks" to be accomplished. The current fashion of referring to
any (pseudo)simultaneous processing as "multi-tasking" came from lay
use of the term - it's a historical accident that embedded programming
used it first.
I personally like to preserve the terms and their distinctions even if
it occasionally means I have to explain them.
>> The interrupt model is somewhat appropriate to describing processing
>> at all levels of consciousness.
>
>IMO the interrupt model is appropriate in some cases, but not in
>others. It is appropriate when there are "devices" involved and not so
>much when it comes to "software" interrupts. To me the latter is
>better modeled by the concept of "yields" in cooperative
>multiprocessing.
>
>> But parallel processing based on an interrupt model would be far
>> more confusing to the average programmer than the
>> pseudo-simultaneous serial process model we have now.
>
>Hmm.. why do you think so?
Please note that I'm talking here about theoretical models to think
about simultaneous processing - not about strategies to implement it.
The interrupt model is too low level an abstraction - irrespective of
nesting, the model's strict LIFO suspend/resume semantics do not
easily lend to thinking about simultaneous activities.
The only simultaneous computational model that can be directly evolved
from the interrupt model is the parallel state machine model. And
while the PSM model underlies all the higher level thread/process
models, state machines are also too low level for general consumption.
The majority of programmers make a god-awful mess of formal state
machine design and many have trouble even understanding the operation
of a moderately complex SM implementation.
Interrupts and state machines are useful as tools to implement higher
level abstractions, but it's clear that the idea of cooperating serial
programs is a much more useful abstraction for the average programmer.
George
--
for email reply remove "/" from address
On Fri, Nov 16 2007, George Neuner wrote:
> On Fri, 16 Nov 2007 01:10:16 +0200, Kamen TOMOV <·····@cybuild.com>
> wrote:
>
>>On Thu, Nov 15 2007, George Neuner wrote:
>>
>>> On Thu, 15 Nov 2007 21:15:23 +0200, Kamen TOMOV <·····@cybuild.com>
>>> wrote:
>>>>
>>>>There is no evidence for parallel processing in the sense that
>>>>resembles preemptive multithreading on a single processing unit
>>>>(call it a core if you like) in the human brain. What we observe
>>>>there is multiple processes running on multiple processing units.
>>>
>>> Actually there is quite a bit of evidence that autonomic processes
>>> are time-multiplexed on the same neurons.
>>
>>Never heard of that. Could you provide references?
>
> Sorry. I have a long time interest in both AI and massively
> parallel computation - I try to follow brain research but I don't
> collect references.
>
> I *think* I saw it in studies on spinal pathway conduction.
OK, but how does this theory fit in the theory of specialized
processing units within the brain? For (an arbitrary) example the
visual perception center is not likely to process "hearing" data.
>>> There is also evidence from investigations of memory association
>>> that individual neurons can participate in several recall
>>> processes simultaneously.
>>>
>>That looks reasonable and does not contradict with my claim.
>>
>>Nevertheless, it would be more interesting if individual neurons can
>>participate not only in simultaneous reads, but in simultaneous
>>reads and writes ...
>
> They do.
>
> Every time a neuron activates - ie. its combined dendril charge
> exceeds the axonal response threshold - its dendrites move slightly
> according to their charge and polarization, narrowing or widening
> the gap(s) between themselves and their input axion(s), reinforcing
> the neuron's response to the last activation pattern while
> maintaining as best as possible its responses to other activation
> patterns.
>
> In essence every activation is both a read and a write/refresh. But
> neurons are not discrete memory cells, a neuron is the summation of
> a group of fuzzy accumulators.
>
>
>>... and especially in deadlocks :-)
>
> Analog circuitry cannot deadlock - conflict states produce either
> blurred (summed) output or an oscillation depending on the relative
> delays in the conflicting circuits.
>
>
>>> I agree that pre-emptive multi-programming (I reserve the word
>>> "multi-tasking" to mean multi-processors) is not a realistic model
>>> of activity in the brain, neither is cooperative
>>> multi-programming.
>>
>>"Multi-programming" sounds ambiguous to me. Within Lisp
>>multi-processing is used (:mp) but for clarity we can use
>>multi-processing and multi-threading depending on the context.
>
> "Multi-programming" is the historically correct term for interleaved
> execution of multiple independent programs on a single CPU. It's
> use goes back to the first time-sharing monitors (the forerunners of
> modern operating systems).
>
> "Multi-processing" historically referred to actual simultaneous
> execution of code, ie. on multiple CPUs.
>
> "Multi-tasking", as it pertains to computing, came originally from
> embedded programming which historically referred to processing goals
> as "tasks" to be accomplished. The current fashion of referring to
> any (pseudo)simultaneous processing as "multi-tasking" came from lay
> use of the term - it's a historical accident that embedded programming
> used it first.
>
>
> I personally like to preserve the terms and their distinctions even
> if it occasionally means I have to explain them.
>
>
>>> The interrupt model is somewhat appropriate to describing
>>> processing at all levels of consciousness.
>>
>>IMO the interrupt model is appropriate in some cases, but not in
>>others. It is appropriate when there are "devices" involved and not
>>so much when it comes to "software" interrupts. To me the latter is
>>better modeled by the concept of "yields" in cooperative
>>multiprocessing.
>>
>>> But parallel processing based on an interrupt model would be far
>>> more confusing to the average programmer than the
>>> pseudo-simultaneous serial process model we have now.
>>
>>Hmm.. why do you think so?
>
> Please note that I'm talking here about theoretical models to think
> about simultaneous processing - not about strategies to implement
> it.
>
> The interrupt model is too low level an abstraction - irrespective
> of nesting, the model's strict LIFO suspend/resume semantics do not
> easily lend to thinking about simultaneous activities.
>
> The only simultaneous computational model that can be directly
> evolved from the interrupt model is the parallel state machine
> model. And while the PSM model underlies all the higher level
> thread/process models, state machines are also too low level for
> general consumption. The majority of programmers make a god-awful
> mess of formal state machine design and many have trouble even
> understanding the operation of a moderately complex SM
> implementation.
>
> Interrupts and state machines are useful as tools to implement
> higher level abstractions, but it's clear that the idea of
> cooperating serial programs is a much more useful abstraction for
> the average programmer.
Interesting.
It seems to me that the interrupt model is no more complex to program
than the cooperative serial programs model. It also seems to me that
the former would provide more efficient processing than the latter. Of
course these claims needs to be supported and good abstractions need
to be provided. Perhaps other people delved deeper into that and
someone could refer to their work.
--
Kamen
Not to get on topic or anything, but I have a related question. Can
one assume that accesses to different elements of the same array can
be concurrent? I'm guessing that any access that changes the size or
fill pointer of an array is not thread safe, but what about an
ordinary fixed-sized array? What about different elements of a list,
e.g. via "elt"? Different elements of the same structure or class?
I would guess that all of these things would be thread safe, but it
doesn't seem to be documented anywhere.
George Neuner <·········@/comcast.net> wrote:
+---------------
| Threaded programs are not much harder to write if thought about
| properly. Raise your hand if you've read "Communicating Sequential
| Processes". Ok, that might be a bad example here in c.l.l., but if
| you were to take a poll in the general programmer population, I'd bet
| better than 90% have never heard of it, let alone read it.
+---------------
The orange & white book by C.A.R. (Tony) Hoare that's on that
shelf over there not two meters from my right hand? ;-} ;-}
Great little text!! Loved it!
R.C. Holt's "Concurrent Euclid, The Unix System, & Tunis" is good, too,
as is Cheriton's book on "The Thoth System".
+---------------
| Actually, apart from a few hands-on OS textbooks I've seen, most books
| that tackle threads suck with regard to teaching synchronization issues.
+---------------
Not the above three, nor do Dijkstra'a various articles on the subject,
such as EWD464 "A new elephant built from mosquitos humming in harmony".
See also EWD508 "A synthesis emerging?", which starts out:
... It is exciting because it seems to open the possibility
of writing programs that could be implemented
a) either by normal sequential techniques
b) or by elephant built from mosquitos
c) of by a data-drive machine.
And in the Table of Contents of his collection of "EWD"s, "Selected
Writings On Computing", he links EWD508 with Hoare's "C.S.P." [the
1978 CACM article, that is]. Fun stuff.
-Rob
p.s. Wulf et al's "HYDRA/C.mmp" also had some stuff I found
helpful once upon a time, but it may be a bit too thin in the
parallelism/synchronization area for this thread [pardon the pun].
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
On Tue, 13 Nov 2007 05:30:17 -0600, ····@rpw3.org (Rob Warnock) wrote:
>George Neuner <·········@/comcast.net> wrote:
>+---------------
>| Threaded programs are not much harder to write if thought about
>| properly. Raise your hand if you've read "Communicating Sequential
>| Processes". Ok, that might be a bad example here in c.l.l., but if
>| you were to take a poll in the general programmer population, I'd bet
>| better than 90% have never heard of it, let alone read it.
>+---------------
>
>The orange & white book by C.A.R. (Tony) Hoare that's on that
>shelf over there not two meters from my right hand? ;-} ;-}
>Great little text!! Loved it!
>
>R.C. Holt's "Concurrent Euclid, The Unix System, & Tunis" is good, too,
>as is Cheriton's book on "The Thoth System".
>
>+---------------
>| Actually, apart from a few hands-on OS textbooks I've seen, most books
>| that tackle threads suck with regard to teaching synchronization issues.
>+---------------
>
>Not the above three, nor do Dijkstra'a various articles on the subject,
>such as EWD464 "A new elephant built from mosquitos humming in harmony".
>See also EWD508 "A synthesis emerging?", which starts out:
>
> ... It is exciting because it seems to open the possibility
> of writing programs that could be implemented
> a) either by normal sequential techniques
> b) or by elephant built from mosquitos
> c) of by a data-drive machine.
>
>And in the Table of Contents of his collection of "EWD"s, "Selected
>Writings On Computing", he links EWD508 with Hoare's "C.S.P." [the
>1978 CACM article, that is]. Fun stuff.
>
>
>-Rob
>
>p.s. Wulf et al's "HYDRA/C.mmp" also had some stuff I found
>helpful once upon a time, but it may be a bit too thin in the
>parallelism/synchronization area for this thread [pardon the pun].
Yup, there _are_ some good references out there, but they are few and
programmers are many. And none of the good references appear on the
shelf at the local technical book store.
George
--
for email reply remove "/" from address
On Nov 11, 2:40 am, George Neuner <·········@/comcast.net> wrote:
> On Fri, 09 Nov 2007 18:09:33 -0800, Antony Sequeira
> Most people seem to have enormous problems
> coping with threads and shared data. Update synchronization failures
> are among the most common bugs found in modern programs. Programming
> practice is marching inexorably toward providing more safety for the
> average programmer at the expense of performance and utility for the
> gifted programmer.
>
> If you've been following this thread and the previous one, you know
> that some people here are arguing for automatic safety, ie. compiler
> directed locking - which is an extremely hard problem. It is
> effectively impossible to identify at compile time all the data which
> will be shared at run time. In theory a whole program analysis could
> do so, but it would be prohibitively time consuming. Shared data can
> be accurately identified at run time, but it's actually more efficient
> just to unconditionally lock heap objects during access whether they
> are shared or not.
In my opinion the way to go is Software Transactional Memory. Memory
transactions compose well and don't require static analysis. I'm not a
compiler programmer but would like to know if they have been taken
into account and if not, why?
Here are some very interesting publications I think CL could follow
somehow:
* Composable Memory Transactions: http://research.microsoft.com/~simonpj/papers/stm/stm.pdf
* User Level Transactional Programming In Haskell:
http://portal.acm.org/ft_gateway.cfm?id=1159853&type=pdf&coll=&dl=acm&CFID=15151515&CFTOKEN=6184618
cl-stm (http://common-lisp.net/project/cl-stm/) implements them on
CLOS. Maybe something like that written at the compiler level could be
the solution.
What do you think?
Mariano
On Sun, 11 Nov 2007 17:38:12 -0000, Mariano Montone
<··············@gmail.com> wrote:
>In my opinion the way to go is Software Transactional Memory. Memory
>transactions compose well and don't require static analysis. I'm not a
>compiler programmer but would like to know if they have been taken
>into account and if not, why?
Transactions are easy for programmers to use, and I'm sure some
compiler writers are looking at them. However, transactions involve a
lot of overhead to support journelling, fine grain object locking,
deadlock detection/avoidance, and rollback (for systems that support
it). In the general case, transactions are considerably slower than
programmer directed explicit locking.
Most of the work to improve performance of automatic transaction
systems is in code analysis to determine when it's safe _not_ to use
them. I don't see automatic systems becoming widespread very soon.
Programmer directed transactions, OTOH, might be more quickly adopted
if the performance is adequate. Lisp already has a library
implementation called CL-STM. For most other languages a library
isn't feasible - compiler support would be necessary.
George
--
for email reply remove "/" from address
On Nov 8, 7:09 am, George Neuner <·········@/comcast.net> wrote:
> Keep in mind though that fixnum updates aren't truly an atomic
> operation in Lisp. Tagging the value and writing it to memory takes a
> couple of instructions - another thread could potentially sneak in and
> read the old value between the time setf is called and the time the
> tagged value is actually written to memory. This is unlikely to
> matter to you, but I mention it for completeness.
>
This is very important actually. But I don't think any major CL
implementation will keep untagged data in memory as that would
normally cause problems for the GC. If they do, however, it is a big
concern.
Another concern is bignums. They are usually by default not thread-
safe, and this can cause extremely subtle bugs.
> A problem you may encounter is that compiler optimizations might
> prevent another thread from seeing the updates even on a single CPU.
> Unless the compiler knows the object may be modified by foreign code,
> it may cache the value in a register and ignore updates in memory.
> The C term for this is a "volatile" variable.
Such code will almost always either be a bug in the compiler or in the
user code. This is so, because any variable that is "volatile" should
be protected by a lock. If it is not, then multiple updates are
unsynchronized, and the code is probably buggy. There are very few
exceptions to this rule. The exceptions I can think of are extremely
high-performance caches where you allow updates to be lost, and
profiling counters, also where updates are allowed to be lost.
If the compiler keeps data in registers across a lock operation, then
the compiler is buggy. Any multi-threading library will have to work
with the compiler to avoid this situation.
Alexander
Alexander Kjeldaas <··················@gmail.com> writes:
> Another concern is bignums. They are usually by default not thread-
> safe, and this can cause extremely subtle bugs.
Are you sure about this? I would expect that bignum operators only
read from the (input) operands, while the fresh result is only
referenced by per-thread storage (the stack etc.) until it is fully
computed and safe.
The one issue with this I know of from my own experience with
implementing bignums is that the intermediate result bignum can be in
a GC-unsafe state while it is being constructed, but this issue is not
specific to bignums really.
--
Frode Vatvedt Fjeld
On Fri, 09 Nov 2007 13:48:23 -0000, Alexander Kjeldaas
<··················@gmail.com> wrote:
>On Nov 8, 7:09 am, George Neuner <·········@/comcast.net> wrote:
>
>> A problem you may encounter is that compiler optimizations might
>> prevent another thread from seeing the updates even on a single CPU.
>> Unless the compiler knows the object may be modified by foreign code,
>> it may cache the value in a register and ignore updates in memory.
>> The C term for this is a "volatile" variable.
>
>Such code will almost always either be a bug in the compiler or in the
>user code. This is so, because any variable that is "volatile" should
>be protected by a lock.
Not at all.
The traditional use of "volatile" in C was to support memory mapped
hardware, to tell the compiler the value had to be read from memory
every time it was needed and written back to memory every time it
changed. Without such direction, the optimizer might cache the value
in a register and the code would not work properly.
In a single writer scenario, updates made without locking _may_ be
perfectly safe depending on the size of the object. During any access
the memory bus is locked, so variables up to the size of a register do
not require a separate software lock.
>If it is not, then multiple updates are unsynchronized, and the code
>is probably buggy.
In a multiple writer scenario, locking is needed only if the update
code may be pre-empted before completion. Pre-emptive multi-tasking
is the norm in OS's today, but it isn't used everywhere - in
particular, green thread systems may be cooperatively tasked. So you
can't just assume code without locks is buggy without knowing what
environment it runs under.
I agree with the principle of "when in doubt, lock it", but understand
that it is between very hard and impossible for a compiler to
automatically identify shared data and implementing such an
auto-locking policy generally could cause a severe performance hit.
That's why most Lisp vendors haven't done so already. It's much
easier to punt responsibility for synchronization to the programmer.
>There are very few exceptions to this rule. The
>exceptions I can think of are extremely high-performance caches where
>you allow updates to be lost, and profiling counters, also where
>updates are allowed to be lost.
>If the compiler keeps data in registers across a lock operation, then
>the compiler is buggy. Any multi-threading library will have to work
>with the compiler to avoid this situation.
I can think of lots of things that can be done with single writer and
atomically small buffers. But I used to write small device code so I
have a fair bit of experience finding offbeat solutions to problems.
George
--
for email reply remove "/" from address