From: Juan Jose Garcia-Ripoll
Subject: Implementing multithreading in Lisp
Date: 
Message-ID: <bpd384$1mtd3v$1@ID-212141.news.uni-berlin.de>
Hi,

I am working on bringing multithreading capabilities into ECL
(http://ecls.sf.net). The easy part is done: having separate state for
different threads, thread-local special variable bindings, etc, and it is
available on CVS (beware of SourceForge's delays for anonymous CVS access).
The implementation is straightforward and inefficient (it is difficult to
have portable thread-local state, and for the special variables I opted to
use an EQ hash table).

However the most complicated seems to me to ensure thread-safety in the
environment. For instance, if one thread tries to add an element to a hash
table, it may happen that the structure has to be resized, and one has to
ensure that this does not happen while another thread tries to access the
same hash table. Same goes for arrays, conses, etc.

My question thus is what should be expected from a multithreaded
implementation of common-lisp? What should be safe, and what should be left
for the user to take care of? Are there any documents about this? Some
inofficial standard that current implementations follow?

Regards,

Juanjo

From: Jon S. Anthony
Subject: Re: Implementing multithreading in Lisp
Date: 
Message-ID: <m3wu9xod7d.fsf@rigel.goldenthreadtech.com>
Juan Jose Garcia-Ripoll <····@arrakis.es> writes:

> My question thus is what should be expected from a multithreaded
> implementation of common-lisp? What should be safe, and what should be left
> for the user to take care of? Are there any documents about this? Some
> inofficial standard that current implementations follow?

Try to "thread the needle" and make the interface look as much like
the existing ones (ACL, LW, CMUCL) as possible.  I suppose everyone
has their favorite, but MP is the one big thing I would next like the
community to converge on and "standardize".  Seems plausible as the
existing implementations do seem "reasonably similar".

/Jon
From: Juan Jose Garcia-Ripoll
Subject: Re: Implementing multithreading in Lisp
Date: 
Message-ID: <bpdhdb$1n7r4o$1@ID-212141.news.uni-berlin.de>
Jon S. Anthony wrote:
> Juan Jose Garcia-Ripoll <····@arrakis.es> writes:
> 
>> My question thus is what should be expected from a multithreaded
>> implementation of common-lisp? [...]
> 
> Try to "thread the needle" and make the interface look as much like
> the existing ones (ACL, LW, CMUCL) as possible.

I have read everywhere that CMUCL can use threads under Linux. However, I
have not seen a documentation of the interface anywhere.

Juanjo
From: Don Geddis
Subject: Re: Implementing multithreading in Lisp
Date: 
Message-ID: <87islh474e.fsf@sidious.geddis.org>
Juan Jose Garcia-Ripoll <····@arrakis.es> writes:
> I have read everywhere that CMUCL can use threads under Linux. However, I
> have not seen a documentation of the interface anywhere.

The source code says
        The interface is based roughly on the CLIM-SYS spec.

I found CLIM-SYS documentation at
        http://www.lispworks.com/reference/lwl42/CLIM-U/html/climguide-330.htm

You might also want to take a look at
        http://alu.cliki.net/com-metacircles-clim-sys-mp
for an attempt to define a cross-implementation MP interface.

For comparison, I found Franz Allegro CL multiprocessing documentation here:
        http://www.franz.com/support/documentation/6.2/doc/multiprocessing.htm

_______________________________________________________________________________
Don Geddis                  http://don.geddis.org/               ···@geddis.org
From: Daniel Barlow
Subject: Re: Implementing multithreading in Lisp
Date: 
Message-ID: <87islhilag.fsf@noetbook.telent.net>
·········@rcn.com (Jon S. Anthony) writes:

> Try to "thread the needle" and make the interface look as much like
> the existing ones (ACL, LW, CMUCL) as possible.  I suppose everyone
> has their favorite, but MP is the one big thing I would next like the
> community to converge on and "standardize".  Seems plausible as the
> existing implementations do seem "reasonably similar".

It seems plausible at least in part because the implementations you
cite are all stack-group based with a Lisp-level scheduler.

When you start looking at OS threads (e.g. OpenMCL 0.14, Corman, SBCL)
which are expected[*] to scale to multi-processor machines, "standard"
functions like process-wait or without-scheduling start looking
distinctly less like a good idea.


-dan

[*] Some day, anyway; at least for SBCL we still have non-trivial
issues like parallelising GC to contend with before there'd be any
point running it on a 32 cpu box.
From: Juan Jose Garcia-Ripoll
Subject: Re: Implementing multithreading in Lisp
Date: 
Message-ID: <bpg0ll$1o929m$1@ID-212141.news.uni-berlin.de>
Daniel Barlow wrote:
> ·········@rcn.com (Jon S. Anthony) writes:
> 
>> Try to "thread the needle" and make the interface look as much like
>> the existing ones (ACL, LW, CMUCL) as possible.  I suppose everyone
>> has their favorite, but MP is the one big thing I would next like the
>> community to converge on and "standardize".  Seems plausible as the
>> existing implementations do seem "reasonably similar".
> 
> It seems plausible at least in part because the implementations you
> cite are all stack-group based with a Lisp-level scheduler.
> When you start looking at OS threads (e.g. OpenMCL 0.14, Corman, SBCL)
> which are expected[*] to scale to multi-processor machines, "standard"
> functions like process-wait or without-scheduling start looking
> distinctly less like a good idea.
>
> [On a different message...]
> Not a lot.  It runs on x86 and all "normal" objects are arranged such
> that slots are naturally aligned for their size, so the fairly strong
> guarantees that x86 itself makes about naturally-aligned quantites
> hold.  If thread A runs (setf *foo* :one) and thread B runs (setf
> *foo* :the-other), you'll definitely get one or the other, not some
> kind of weird mixture.  If instead you run (setf (foo-bar *foo*) 1),
> and (setf foo-bar) is arbitrarily complex, some bets may be off.

How do you handle structural changes of objects in SBCL? They typically
involve updating more than one slot, and atomicity of a single write
operation does not prevent you from trashing everything. Hashes is just
one example of objects that may change in size, but adjustable arrays,
or structures or CLOS instances are some others. To me this seems the biggest
problem which lisp schedulers trivially solve by preventing two threads from
resizing the same object, or one thread resizing it while a different one
reads from it. I have browsed the source code of SBCL and did not find
any protection for this. Is it within your plans?

I am also interested to know whether SBCL will try to imitate the
multiprocessing model of the LispM. Things like process-interrupt,
restart-process or process-wat seem difficult or inefficient to be
implemented with OS threads.

Juanjo
From: Nikodemus Siivola
Subject: Re: Implementing multithreading in Lisp
Date: 
Message-ID: <bpdakb$qct$1@nyytiset.pp.htv.fi>
Juan Jose Garcia-Ripoll <····@arrakis.es> wrote:

> My question thus is what should be expected from a multithreaded
> implementation of common-lisp? What should be safe, and what should be left

I'll pipe in from an end-user perspective. 

 "Everything specified in the standard should be thread-safe."

Cheers,

 -- Nikodemus
From: Frode Vatvedt Fjeld
Subject: Re: Implementing multithreading in Lisp
Date: 
Message-ID: <2hhe1120uc.fsf@vserver.cs.uit.no>
Juan Jose Garcia-Ripoll <····@arrakis.es> wrote:

>> My question thus is what should be expected from a multithreaded
>> implementation of common-lisp? What should be safe, and what should
>> be left

Nikodemus Siivola <······@random-state.net> writes:

> I'll pipe in from an end-user perspective. 
>
>  "Everything specified in the standard should be thread-safe."

What if this implies "everything becomes three times slower"? I'm not
saying it's necessarily so, but I'm guessing it might be.

-- 
Frode Vatvedt Fjeld
From: Nikodemus Siivola
Subject: Re: Implementing multithreading in Lisp
Date: 
Message-ID: <bpdcvb$t08$1@nyytiset.pp.htv.fi>
Frode Vatvedt Fjeld <······@cs.uit.no> wrote:

>>  "Everything specified in the standard should be thread-safe."

> What if this implies "everything becomes three times slower"? I'm not
> saying it's necessarily so, but I'm guessing it might be.

"That hurts, then."

To clarify, 

I'd expect (setf (gethash ...) ...) to be thread-safe from the box,
but not eg.

 (unless (gethash ...)
   (setf (gethash ...) ...))

Also, by thread-safety I don't mean re-entrant. Locks are fine.

Cheers,

 -- Nikodemus
From: Juan Jose Garcia-Ripoll
Subject: Re: Implementing multithreading in Lisp
Date: 
Message-ID: <bpdc2q$1mugmb$1@ID-212141.news.uni-berlin.de>
Frode Vatvedt Fjeld wrote:
> Juan Jose Garcia-Ripoll <····@arrakis.es> wrote:
>>  "Everything specified in the standard should be thread-safe."
> What if this implies "everything becomes three times slower"? I'm not
> saying it's necessarily so, but I'm guessing it might be.

Yes, it might be the case that one has to implement mutexes to avoid the
problems mentioned above. And then one has to choose between having a
per-object, per-type or unique lock. The performance of a single thread
would be penalized in the circumstances I mentioned before (when the size
of a structure, array, hash, etc, changes). This may be rare events for
some applications, but it may hurt some others. For instance, VECTOR-PUSH
would be hurt, and could no longer be implemented as an increment of the
fill pointer plus some size check.

I just posed the question to get a feeling of what people who really use
multithreading in lisp do need, not what should be _theoretically_ correct.

Regards,

Juanjo
From: Matthias
Subject: Re: Implementing multithreading in Lisp
Date: 
Message-ID: <36woev91zdy.fsf@chagall.ti.uni-mannheim.de>
Nikodemus Siivola <······@random-state.net> writes:

> Juan Jose Garcia-Ripoll <····@arrakis.es> wrote:
> 
> > My question thus is what should be expected from a multithreaded
> > implementation of common-lisp? What should be safe, and what should be left
> 
> I'll pipe in from an end-user perspective. 
> 
>  "Everything specified in the standard should be thread-safe."

Please, no!  Make it rather

   "Every data structure specified in the standard should behave as if
   it were plain old data."

I.e., concurrent reads should work, concurrent writes might result in
unspecified behavior.  If I want a thread-save hash-table I'll write
one or load a library which implements it.  I _really_ do not want to
pay synchronization costs (in terms of speed) when I don't have to.
Only the programmer is qualified to decide when synchronization is
needed and how it should be implemented where it is.  Otherwise
performance and/or flexibility might easily get lost.
From: Frank A. Adrian
Subject: Re: Implementing multithreading in Lisp
Date: 
Message-ID: <4Frub.560$436.20290@news.uswest.net>
Matthias wrote:

> Only the programmer is qualified to decide when synchronization is
> needed and how it should be implemented where it is.  Otherwise
> performance and/or flexibility might easily get lost.

Wow!  Substitute memory management for synchronization and you really have a
fun statement!

I won't say as I disagree with your viewpoint that some control of
synchronization is needed, but I believe that one needs to look at
expressing synchronization at a higher level than today's micromanagement
of locks if we are going to gain any improvement in the productivity in
coding and decrease in debugging of multi-tasking applications.

faa
From: Will Hartung
Subject: Re: Implementing multithreading in Lisp
Date: 
Message-ID: <bpdnki$1nov0v$1@ID-197644.news.uni-berlin.de>
"Frank A. Adrian" <·······@ancar.org> wrote in message
························@news.uswest.net...
> Matthias wrote:
>
> > Only the programmer is qualified to decide when synchronization is
> > needed and how it should be implemented where it is.  Otherwise
> > performance and/or flexibility might easily get lost.
>
> Wow!  Substitute memory management for synchronization and you really have
a
> fun statement!
>
> I won't say as I disagree with your viewpoint that some control of
> synchronization is needed, but I believe that one needs to look at
> expressing synchronization at a higher level than today's micromanagement
> of locks if we are going to gain any improvement in the productivity in
> coding and decrease in debugging of multi-tasking applications.

And for heavens sake, don't let any history sway your decision to make
generic operations thread safe.

For example, when Java first appeared, many of its core data structures were
implicitly synchronized. It did not take them very long to toss all of them
aside and push the non-synchronized versions, because even in mutli-threaded
programming, a majority of the work is done on data structures that simply
are not shared across threads and do not need the extra functionality of
synchronization.

They supplmented the standard collections with wrappers that handle
synchronization on top of the standard structures. But this is can be
difficult in CL, specifically with lists as they are worked on typically at
the CONS cell level rather than at the actual overall List level. But you
can wing it for hashtables etc.

Since a VAST majority of CL programs are also not multi-threaded, it would
seem a shame to punish everyone to handle a complicated programming task
that is done rarely. I think that you should provide thread safe data
structures.

Of course, I rather like the "synchronized" paradigm in Java. It makes the
mutex semi-transparent to the programmer.

Regards,

Will Hartung
(·····@msoft.com)
From: William D Clinger
Subject: Re: Implementing multithreading in Lisp
Date: 
Message-ID: <fb74251e.0311181736.aca58e1@posting.google.com>
Will Hartung wrote:
> [Java] supplmented the standard collections with wrappers that handle
> synchronization on top of the standard structures. But this is can be
> difficult in CL, specifically with lists as they are worked on typically at
> the CONS cell level rather than at the actual overall List level. But you
> can wing it for hashtables etc.

Lisp lists are often used as an immutable data type, which eliminates
the need for program-level synchronization.  (The implementor has to
make allocation and garbage collection work, but let's assume that is
done correctly.)  The problem comes with destructive updates, which
are more troublesome because of the tradition Will identified of side
effects to arbitrary cons cells.

I think the best thing to do is to leave the low-level mutators (e.g.
(setf (car x) ...)) exposed to race conditions, and to build Java-like
libraries of mutable collections (e.g. hashtables) that can be locked
as a whole instead of at the level of cons cells.

In short: use traditional lists as unlocked immutable structures, and
use Java-style collections for locked mutable structures.  I think
(but am not sure) that this is what Will Hartung meant when he wrote:

> Since a VAST majority of CL programs are also not multi-threaded, it would
> seem a shame to punish everyone to handle a complicated programming task
> that is done rarely. I think that you should provide thread safe data
> structures.

Will
From: Peter Seibel
Subject: Re: Implementing multithreading in Lisp
Date: 
Message-ID: <m3u151frn2.fsf@javamonkey.com>
"Will Hartung" <·····@msoft.com> writes:

> "Frank A. Adrian" <·······@ancar.org> wrote in message
> ························@news.uswest.net...
> > Matthias wrote:
> >
> > > Only the programmer is qualified to decide when synchronization is
> > > needed and how it should be implemented where it is.  Otherwise
> > > performance and/or flexibility might easily get lost.
> >
> > Wow!  Substitute memory management for synchronization and you really have
> a
> > fun statement!
> >
> > I won't say as I disagree with your viewpoint that some control of
> > synchronization is needed, but I believe that one needs to look at
> > expressing synchronization at a higher level than today's micromanagement
> > of locks if we are going to gain any improvement in the productivity in
> > coding and decrease in debugging of multi-tasking applications.
> 
> And for heavens sake, don't let any history sway your decision to
> make generic operations thread safe.
> 
> For example, when Java first appeared, many of its core data
> structures were implicitly synchronized. It did not take them very
> long to toss all of them aside and push the non-synchronized
> versions, because even in mutli-threaded programming, a majority of
> the work is done on data structures that simply are not shared
> across threads and do not need the extra functionality of
> synchronization.

Agreed. I worked at Weblogic (now part of BEA) in early days and one
of the biggest mistakes we made was following the lead of the JDK and
trying to make most data structures thread safe. Turns out that its
much better to make most data structures single-threaded and then
think very carefully about the places in your overall system that need
to be made thread safe and thread hot. (Mostly because--as is being
discussed in one of the static typing threads--getting concurrency
issues correct is so tricky; you need to really think carefully about
when and where you want threads to interact.)

> They supplmented the standard collections with wrappers that handle
> synchronization on top of the standard structures. But this is can
> be difficult in CL, specifically with lists as they are worked on
> typically at the CONS cell level rather than at the actual overall
> List level. But you can wing it for hashtables etc.

Well, you wouldn't want to do the Java thing for cons cells because
that would imply adding a hidden monitor field to every cons cell.
Which is much too fine grained granularity.

> Since a VAST majority of CL programs are also not multi-threaded, it
> would seem a shame to punish everyone to handle a complicated
> programming task that is done rarely. I think that you should
> provide thread safe data structures.
> 
> Of course, I rather like the "synchronized" paradigm in Java. It
> makes the mutex semi-transparent to the programmer.

I'd agree with that with the addition that given macros and method
combinations, one could build Java-style "synchronized" code out of
lower-level mutex primitives which are also exposed to the programmer.
(In Java the bytecodes contain monitorenter/monitorexit instructions
but they are only exposed to the programmer via block-structured
synchronized constructs.) There are times when it would be nice to
have access to the raw monitorenter/monitorexit calls too, for
instance if you want to crab locks across data structures.

-Peter

-- 
Peter Seibel                                      ·····@javamonkey.com

         Lisp is the red pill. -- John Fraser, comp.lang.lisp
From: Pascal Costanza
Subject: Re: Implementing multithreading in Lisp
Date: 
Message-ID: <bpftk2$107m$1@f1node01.rhrz.uni-bonn.de>
Will Hartung wrote:
> "Frank A. Adrian" <·······@ancar.org> wrote in message
> ························@news.uswest.net...
> 
>>Matthias wrote:
>>
>>
>>>Only the programmer is qualified to decide when synchronization is
>>>needed and how it should be implemented where it is.  Otherwise
>>>performance and/or flexibility might easily get lost.
>>
>>Wow!  Substitute memory management for synchronization and you really have
> 
> a
> 
>>fun statement!
>>
>>I won't say as I disagree with your viewpoint that some control of
>>synchronization is needed, but I believe that one needs to look at
>>expressing synchronization at a higher level than today's micromanagement
>>of locks if we are going to gain any improvement in the productivity in
>>coding and decrease in debugging of multi-tasking applications.
> 
> 
> And for heavens sake, don't let any history sway your decision to make
> generic operations thread safe.
> 
> For example, when Java first appeared, many of its core data structures were
> implicitly synchronized. It did not take them very long to toss all of them
> aside and push the non-synchronized versions, because even in mutli-threaded
> programming, a majority of the work is done on data structures that simply
> are not shared across threads and do not need the extra functionality of
> synchronization.

IIRC, there have been two independent evolutions taken place in the Java 
world: One is indeed to provide two versions of collection classes, one 
thread-safe, other ones not.

However, they have also invested heavily in making thread-safe 
collections cheap by making use of dynamic compilation/optimization both 
in the HotSpot and the IBM Virtual Machines.

These two solutions have been provided in parallel, because the former 
was easier and earlier to achieve.

It's probably worthwhile to take a look at the results of the latter 
efforts.

(However, I am by far not an expert in this area, so I don't any more 
details. Others can probably provide much better comments.)


Pascal

-- 
Pascal Costanza               University of Bonn
···············@web.de        Institute of Computer Science III
http://www.pascalcostanza.de  R�merstr. 164, D-53117 Bonn (Germany)
From: William D Clinger
Subject: Re: Implementing multithreading in Lisp
Date: 
Message-ID: <fb74251e.0311191339.76f3dbd1@posting.google.com>
Pascal Costanza wrote:
> IIRC, there have been two independent evolutions taken place in the Java 
> world: One is indeed to provide two versions of collection classes, one 
> thread-safe, other ones not.

First-generation Java collections were "synchronized" in the sense of
locking and unlocking the collection for every operation.  This was an
unnecessary overhead for the usual case, in which the collection is
accessed by only one thread.  The second generation of Java collection
classes have unsynchronized operations, which assume the client will
enforce any required mutual exclusion; some first-generation collections
remain synchronized for backward compatibility.  All Java collections
are thread-safe if used properly.
:)

> However, they have also invested heavily in making thread-safe 
> collections cheap by making use of dynamic compilation/optimization both 
> in the HotSpot and the IBM Virtual Machines.

Most of the performance improvement comes from just-in-time (JIT)
compilers that translate JVM code (byte code) to native code
instead of interpreting it.  Some additional improvement has
come from dynamic cross-module optimization.  These performance
improvements apply to all Java code, not just the collection
classes.  They have little if anything to do with threads.

On the other hand, the Java community has put a lot of work into
fast locking and unlocking.  That has made a big difference for
applications that use synchronized data structures and operations,
regardless of whether the application would normally be regarded
as multi-threaded.

Will
From: Kent M Pitman
Subject: Re: Implementing multithreading in Lisp
Date: 
Message-ID: <wkwu9xbrje.fsf@nhplace.com>
Matthias <··@spam.pls> writes:

> Nikodemus Siivola <······@random-state.net> writes:
> 
> > Juan Jose Garcia-Ripoll <····@arrakis.es> wrote:
> > 
> > > My question thus is what should be expected from a multithreaded
> > > implementation of common-lisp? What should be safe, and what
> > > should be left
> > 
> > I'll pipe in from an end-user perspective. 
> > 
> >  "Everything specified in the standard should be thread-safe."

The reason it is the standard is that is defined by the text it
contains and not by other text offered elsewhere.  Since it does not
contain this sentence, then it is necessarily the case that an
implementation may conform without this statement being true.  Since,
further, it is possible to implement multithreading without forcing
this situation, it is necessarily true as a consequence that there can
exist implementations that would violate this statement, and it is
useless to pretend otherwise.

Now, you could make a "layered standard" (or just "Juan Possible Lisp"
...  sorry, bad pun, I know, but I couldn't resist) that requires
more.  But you can't exclude the possibility of other layered
standards that go a different way.

At the time we made the standard, they muliprocessed already, and we knew
this was an issue.  We also had in our charter, even in 1986, 2 years before
feature freeze and 8 years before finalizing the spec, see
 http://www.nhplace.com/kent/CL/x3j13-86-020.html
that we wanted to address multiprocessing if possible.  But we decided it
was not possible.  That is, not that multiprocessing wasn't possible, but
that there were too many divergent details and that it wasn't "ripe for
standardization".

> Please, no!  Make it rather
> 
>    "Every data structure specified in the standard should behave as if
>    it were plain old data."

Well, this is the yin to the yang above.  It's the other possible approach.
You either make it synchronized by default, or you don't.  But then, as
they say, there are two kinds of people in the world: people who think there
are two kinds of people in the world, and people who don't... 

> I.e., concurrent reads should work, concurrent writes might result in
> unspecified behavior.

Unspecified by the standard does not require it to be unspecified by the
implementation.

> If I want a thread-save hash-table I'll write
> one or load a library which implements it.

Or use an implementation which promises it rather than one that doesn't.

> I _really_ do not want to
> pay synchronization costs (in terms of speed) when I don't have to.

Whether you are paying a cost for this is, of course, an artifact of the
implementation.  There might be implementations that can provide you 
some synchronization for free (or sufficiently reduced cost as to 
warrant it), while others cannot.

> Only the programmer 

in conjunction with the vendor (and I always try to mean vendor in the
most general sense, that is, any producer of an implementation, even a
free one)

> is qualified to decide when synchronization is needed
> and how it should be implemented where it is.

Some Lisps don't ever multiprocess.  Some always do.  Some optionally
do.  It's really quite tough for a programmer who isn't taking all
three of these into account to really know which he or she wants.  For
example, you may always need this if you are running in a Lisp that is
always multitasking.  At minimum, you need to read the vendor
documentation for such a Lisp to find out what they tell you they
think...  It's hard to universally quantify across all possible
implementations at programming time, and it's even harder to play god
and to say that all implementations should definitely either do or not
do a certain thing in this regard.  I'm not saying impossible.  It's
just something I wouldn't rush to decide without thinking a long time
and making sure I'd covered all the bases.

> Otherwise performance and/or flexibility might easily get lost.

Some performance will almost always get lost if you don't tune your
application per-platform.  I mention this because "port-time" is usually
not the same as "[initial] programming time".

As to flexibility, it's a matter of perspective whether synchronization
enhances flexibility or removes it.
From: Thomas A. Russ
Subject: Re: Implementing multithreading in Lisp
Date: 
Message-ID: <ymid6bpv5qz.fsf@sevak.isi.edu>
Matthias <··@spam.pls> writes:

> Please, no!  Make it rather
> 
>    "Every data structure specified in the standard should behave as if
>    it were plain old data."
> 
> I.e., concurrent reads should work, concurrent writes might result in
> unspecified behavior.  If I want a thread-save hash-table I'll write
> one or load a library which implements it.  I _really_ do not want to
> pay synchronization costs (in terms of speed) when I don't have to.
> Only the programmer is qualified to decide when synchronization is
> needed and how it should be implemented where it is.  Otherwise
> performance and/or flexibility might easily get lost.

Interestingly enough, it seems Java started out with thread-safe hash
tables (in the java.util.Hashtable class) and then on the basis of
experience with that moved to providing non-thread-safe versions
(java.util.Hashmap class) in the new, perferred implementation.

That would seem to be empirical evidence in support of Matthias'
position.

-- 
Thomas A. Russ,  USC/Information Sciences Institute
From: Daniel Barlow
Subject: Re: Implementing multithreading in Lisp
Date: 
Message-ID: <87ptfpimdx.fsf@noetbook.telent.net>
Nikodemus Siivola <······@random-state.net> writes:

>  "Everything specified in the standard should be thread-safe."

That's easy.  The standard doesn't specify threads.

If you use extra-standard facilities to do something else at the same
time as running conforming CL code, clearly you're into
implementation-defined territory.  So, we need do nothing at all :-)


-dan

-- 

   http://web.metacircles.com/cirCLe_CD - Free Software Lisp/Linux distro
From: Peter Seibel
Subject: Re: Implementing multithreading in Lisp
Date: 
Message-ID: <m3ptfpfr3d.fsf@javamonkey.com>
Daniel Barlow <···@telent.net> writes:

> Nikodemus Siivola <······@random-state.net> writes:
> 
> >  "Everything specified in the standard should be thread-safe."
> 
> That's easy.  The standard doesn't specify threads.
>
> If you use extra-standard facilities to do something else at the same
> time as running conforming CL code, clearly you're into
> implementation-defined territory.  So, we need do nothing at all :-)

Uh, I thought Nikodemus trying to say that if I have two threads that
are each executing conformant code they should each observe the
semantics described by the standard.

I'm not sure that exactly makes sense, since certainly there's no
provision in the standard for values that a SETF to later be different
than what I set them to (which is, of course, what it will look like
to one thread if another thread manipulates the same place). But if by
"thread-safe" he meant something like if two theads SETF a place,
subsequent reads of that place will see on or another of the values
that was actually stored by one of threads, not an admixture, that
seems like a reasonable proposal. Of course given the number of places
that SETF can modify, I'm not sure I necessarily buy it--I might
rather have complex operations like hash table manipulations be
thread-unsafe and be required to properly serialize access to hash
tables that I know are shared between threads.

Out of curiosity, what guarantees (if any) does SBCL make in the case
of assigning multiple threads assigning to, say, a global variable?

-Peter

-- 
Peter Seibel                                      ·····@javamonkey.com

         Lisp is the red pill. -- John Fraser, comp.lang.lisp
From: Daniel Barlow
Subject: Re: Implementing multithreading in Lisp
Date: 
Message-ID: <87brr9ihch.fsf@noetbook.telent.net>
Peter Seibel <·····@javamonkey.com> writes:

> Uh, I thought Nikodemus trying to say that if I have two threads that
> are each executing conformant code they should each observe the
> semantics described by the standard.

He was.  I was just pointing out that there are more possible
conclusions you can reach on this topic by appealing to the standard
than the one he arrived at.  Kent's post elsewhere in this thread said
it better than I did anyway, though.

> Out of curiosity, what guarantees (if any) does SBCL make in the case
> of assigning multiple threads assigning to, say, a global variable?

Not a lot.  It runs on x86 and all "normal" objects are arranged such
that slots are naturally aligned for their size, so the fairly strong
guarantees that x86 itself makes about naturally-aligned quantites
hold.  If thread A runs (setf *foo* :one) and thread B runs (setf
*foo* :the-other), you'll definitely get one or the other, not some
kind of weird mixture.  If instead you run (setf (foo-bar *foo*) 1),
and (setf foo-bar) is arbitrarily complex, some bets may be off.

If there's a cpu out there on which doesn't have a type suitable for
use as a lisp pointer that can be cheaply updated atomically, we
probably are going to have fun if/when we port to it.  I'm having
trouble believing that any successful cpu would be that stupid,
though.


-dan
From: Rob Warnock
Subject: Re: Implementing multithreading in Lisp
Date: 
Message-ID: <h7Cdndo6aZZUlyOiXTWc-g@speakeasy.net>
Daniel Barlow  <···@telent.net> wrote:
+---------------
| If there's a cpu out there on which doesn't have a type suitable for
| use as a lisp pointer that can be cheaply updated atomically, we
| probably are going to have fun if/when we port to it.  I'm having
| trouble believing that any successful cpu would be that stupid, though.
+---------------

Just to show that it's not unimaginable... Consider a pair of 64-bit CPUs
sharing memory on a 32-bit PCI bus.[1] Let both CPUs be storing a 64-bit
"Lisp value" (pointer) into the same location, when the 32-bit memory
decides it needs to take a breather (for a refresh, or something).
Since PCI *requires* that bus masters accept a "target abort" anywhere
in the middle of a burst and continue the operation from the first word
that didn't transfer, it is quite possible that CPU "A" could store the
first 32 bits of a 64-bit pointer, then the memory "target abort" on
the second 32 bits, then CPU "B" might win the next arbitration and
store all 64 bits of its poitner, then CPU "A" retry the store of its
second 32 bits and succeed this time, leaving the target location garbled.

It *could* happen...


-Rob

[1] A "D32/A64" bus, that is: only 32 data wires, but 64-bit addresses
    provided with dual-cycle address phases (which PCI supports).

-----
Rob Warnock			<····@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607
From: lin8080
Subject: Re: Implementing multithreading in Lisp
Date: 
Message-ID: <3FC28C75.4426B3A1@freenet.de>
Rob Warnock schrieb:

> Just to show that it's not unimaginable... Consider a pair of 64-bit CPUs
> sharing memory on a 32-bit PCI bus.[1] Let both CPUs be storing a 64-bit
> "Lisp value" (pointer) into the same location, when the 32-bit memory
> decides it needs to take a breather (for a refresh, or something).
> Since PCI *requires* that bus masters accept a "target abort" anywhere
> in the middle of a burst and continue the operation from the first word
> that didn't transfer, it is quite possible that CPU "A" could store the
> first 32 bits of a 64-bit pointer, then the memory "target abort" on
> the second 32 bits, then CPU "B" might win the next arbitration and
> store all 64 bits of its poitner, then CPU "A" retry the store of its
> second 32 bits and succeed this time, leaving the target location garbled.
> 
> It *could* happen...

...something completely different:

what you think about storing data in a magnetic field instead in a
conventional memory?

stefan
From: Joe Marshall
Subject: Re: Implementing multithreading in Lisp
Date: 
Message-ID: <ptfgdi08.fsf@comcast.net>
lin8080 <·······@freenet.de> writes:

>
> ...something completely different:
>
> what you think about storing data in a magnetic field instead in a
> conventional memory?

It's all relativistic.

-- 
~jrm
From: Rob Warnock
Subject: Re: Implementing multithreading in Lisp
Date: 
Message-ID: <wq2dnTojkNs3XVuiXTWc-w@speakeasy.net>
<·······@freenet.de> wrote:
+---------------
| ...something completely different:
| 
| what you think about storing data in a magnetic field instead in a
| conventional memory?
+---------------

Uh... Been there, done that?  It was called "core memory" [after
the doughnut-shaped magnetic ferrite cores used to store each bit],
and was very widely used in the 1970's for the main memories of
systems such as the IBM 360 and the DEC PDP-10, etc. *Much* higher
dynamic power and *much* lower density per bit than today's DRAMs
[though core memory did have the advantage of being nonvolatile when
the power was off].

Or maybe you're thinking of "disk drives"?  I hear that a number of
people are still using those...  ;-}  ;-}


-Rob

-----
Rob Warnock			<····@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607
From: Raymond Toy
Subject: Re: Implementing multithreading in Lisp
Date: 
Message-ID: <4nhe0ke6v4.fsf@edgedsp4.rtp.ericsson.se>
>>>>> "Rob" == Rob Warnock <····@rpw3.org> writes:

    Rob> Uh... Been there, done that?  It was called "core memory" [after
    Rob> the doughnut-shaped magnetic ferrite cores used to store each bit],
    Rob> and was very widely used in the 1970's for the main memories of
    Rob> systems such as the IBM 360 and the DEC PDP-10, etc. *Much* higher
    Rob> dynamic power and *much* lower density per bit than today's DRAMs
    Rob> [though core memory did have the advantage of being nonvolatile when
    Rob> the power was off].

I have some core memory cards sitting right next to me, pulled from an
old Prime (?) computer many years ago.  They're cool to have around to
show people what happens when my programs dump core. :-)

Ray
From: Greg Menke
Subject: Re: Implementing multithreading in Lisp
Date: 
Message-ID: <m3wu9oy44t.fsf@europa.pienet>
····@rpw3.org (Rob Warnock) writes:

> Daniel Barlow  <···@telent.net> wrote:
> +---------------
> | If there's a cpu out there on which doesn't have a type suitable for
> | use as a lisp pointer that can be cheaply updated atomically, we
> | probably are going to have fun if/when we port to it.  I'm having
> | trouble believing that any successful cpu would be that stupid, though.
> +---------------
> 
> Just to show that it's not unimaginable... Consider a pair of 64-bit CPUs
> sharing memory on a 32-bit PCI bus.[1] Let both CPUs be storing a 64-bit
> "Lisp value" (pointer) into the same location, when the 32-bit memory
> decides it needs to take a breather (for a refresh, or something).
> Since PCI *requires* that bus masters accept a "target abort" anywhere
> in the middle of a burst and continue the operation from the first word
> that didn't transfer, it is quite possible that CPU "A" could store the
> first 32 bits of a 64-bit pointer, then the memory "target abort" on
> the second 32 bits, then CPU "B" might win the next arbitration and
> store all 64 bits of its poitner, then CPU "A" retry the store of its
> second 32 bits and succeed this time, leaving the target location garbled.
> 
> It *could* happen...

This isn't a cpu issue though.  It might also be possible to arrange
the bus grants so A can handle the master abort and retry before B can
get the bus.

Gregm
From: Peter Seibel
Subject: Re: Implementing multithreading in Lisp
Date: 
Message-ID: <m3u150dtfu.fsf@javamonkey.com>
Juan Jose Garcia-Ripoll <····@arrakis.es> writes:

> Hi,
> 
> I would like to thank all of you for the valuable feedback. In particular,
> Roger Corman's detailed explanation of the capabilities of Corman Lisp sets
> a nice list of goals, and Daniel Barlow's message induced me to re-read the
> documentation of glibc to happily find that yes (!) POSIX Threads support
> sending signals to specific threads and thus INTERRUPT-PROCESS can be
> implemented. It was also good to discover that somehow there is a common
> naming convention dating back to the Lisp Machines and thus I do not have
> to figure out everything on my own.

One other thing to consider, regarding INTERRUPT-PROCESS is what
happens to locks held by that thread. If INTERRUPT-PROCESS lets you
run an arbitrary function at an arbitrary point in a thread's
execution, it makes it really hard to write thread-safe code. Suppose
thread t1 is in the midst of mutating various objects under the
protection of some lock and thread t2 is waiting for the lock. The
objects are in pieces on the floor with all their invariants
(temporarily) violated. Now t1 is interrupted by with a function that
signals a condition and subsequently unwinds the stack. Either the
lock is automatically released (perhaps by an UNWIND-PROTECT) which
lets in t2 which finds the objects in pieces on the floor. Or the lock
is *not* released and t2 waits forever because t1 is never going to
release it.

I have no idea how the Lisp Machine folks dealt with this problem but
I know it was a big mess in Java[1]. I'm also not sure there is a
*right* answer but it's worth thinking about.

-Peter

-- 
Peter Seibel                                      ·····@javamonkey.com

         Lisp is the red pill. -- John Fraser, comp.lang.lisp
From: Daniel Barlow
Subject: Re: Implementing multithreading in Lisp
Date: 
Message-ID: <87ekw4glaf.fsf@noetbook.telent.net>
Peter Seibel <·····@javamonkey.com> writes:

> One other thing to consider, regarding INTERRUPT-PROCESS is what
> happens to locks held by that thread. If INTERRUPT-PROCESS lets you
> run an arbitrary function at an arbitrary point in a thread's
> execution, it makes it really hard to write thread-safe code. Suppose

I think the obvious response is "don't do that then". In SBCL we use
interrupt-process in the implementation of terminate-thread (the
alternative is simply killing the task without running cleanup forms:
probably not what you wanted) or for stopping a task so it can be
debugged, with some form like "(sb-thread:interrupt-thread 12345
#'break)".

I think of these as debugging features (the assumption being that
something is already wrong) and would tend to regard any system that 
depended on them in "normal use" as having something wrong with it.

> I have no idea how the Lisp Machine folks dealt with this problem but
> I know it was a big mess in Java[1]. I'm also not sure there is a
> *right* answer but it's worth thinking about.

UndefinedFootnoteException ...


-dan
From: Peter Seibel
Subject: Re: Implementing multithreading in Lisp
Date: 
Message-ID: <m3ptfodpwx.fsf@javamonkey.com>
Daniel Barlow <···@telent.net> writes:

> Peter Seibel <·····@javamonkey.com> writes:
> 
> > One other thing to consider, regarding INTERRUPT-PROCESS is what
> > happens to locks held by that thread. If INTERRUPT-PROCESS lets you
> > run an arbitrary function at an arbitrary point in a thread's
> > execution, it makes it really hard to write thread-safe code. Suppose
> 
> I think the obvious response is "don't do that then". In SBCL we use
> interrupt-process in the implementation of terminate-thread (the
> alternative is simply killing the task without running cleanup forms:
> probably not what you wanted) or for stopping a task so it can be
> debugged, with some form like "(sb-thread:interrupt-thread 12345
> #'break)".

I think that's probably right. I guess I didn't think enough about the
fact that the caller of INTERRUPT-PROCESS gets to specify any code
they want. So it's up to you to pass in a function that does whatever
cleanup is necessary (probably by writing the code that is potentially
going to be interrupted with appropriate condition handlers and
restarts bound that can make sure that the world is put back in
order.) Does TERMINATE-THREAD terminate the thread by signalling a
condition, thus allowing the possibility to write code that will clean
up properly/differently in the face of asynchronous termination?

> I think of these as debugging features (the assumption being that
> something is already wrong) and would tend to regard any system that 
> depended on them in "normal use" as having something wrong with it.

In general I agree. Though sometimes when writing things such as app
servers which run user-supplied code it may be necessary to be able to
kill or interrupt threads (say that are taking too long).

> > I have no idea how the Lisp Machine folks dealt with this problem
> > but I know it was a big mess in Java[1]. I'm also not sure there
> > is a *right* answer but it's worth thinking about.
> 
> UndefinedFootnoteException ...

Whoops. Actually the footnote, if I had written it would have sort of
made your point. Java has Thread.stop() which kills a thread,
releasing all locks on the way out. Then they deprecated it with all
kinds of horrible warnings. But they'll probably never take it out of
the language because sometimes you really do want to kill a thread and
are willing to live with the consequences. The only real point is that
someone, such as Juan, who is providing a threading API should be
aware of these issues so as to properly guard/document/whatever the
really sharp edges.

-Peter

-- 
Peter Seibel                                      ·····@javamonkey.com

         Lisp is the red pill. -- John Fraser, comp.lang.lisp
From: Daniel Barlow
Subject: Re: Implementing multithreading in Lisp
Date: 
Message-ID: <871xs396yg.fsf@noetbook.telent.net>
Peter Seibel <·····@javamonkey.com> writes:

> order.) Does TERMINATE-THREAD terminate the thread by signalling a
> condition, thus allowing the possibility to write code that will clean
> up properly/differently in the face of asynchronous termination?

TERMINATE-THREAD forces the thread in question to call SB-EXT:QUIT,
which throws to an internal catch tag with a name something like
%END-OF-THE-WORLD.  So, yes.  Although, I confess, if you terminate it
twice in quick succession I haven't thought too hard about what would
happen.

>> I think of these as debugging features (the assumption being that
>> something is already wrong) and would tend to regard any system that 
>> depended on them in "normal use" as having something wrong with it.
>
> In general I agree. Though sometimes when writing things such as app
> servers which run user-supplied code it may be necessary to be able to
> kill or interrupt threads (say that are taking too long).

Right.  I have a timeout on requests in Araneida, for example -
because what else _can_ you do?  If the thread sits there indefinitely
holding locks and the client has already timed out, that really isn't
any more use to anyone than it would be if it dies leaving the locks
held - and if you've written your locking code such that it does
cleanup and unlocks in cleanup forms (WITH-MUTEX will take care of the
unlock, but you'd better fix up whatever broken invariants the lock is
protexting yourself) you might even be /better/ off.

I tend to put that kind of dead or stunned request in the "something
is already wrong" category.


-dan
From: Joe Marshall
Subject: Re: Implementing multithreading in Lisp
Date: 
Message-ID: <1xs353h9.fsf@comcast.net>
Peter Seibel <·····@javamonkey.com> writes:

> One other thing to consider, regarding INTERRUPT-PROCESS is what
> happens to locks held by that thread. If INTERRUPT-PROCESS lets you
> run an arbitrary function at an arbitrary point in a thread's
> execution, it makes it really hard to write thread-safe code. Suppose
> thread t1 is in the midst of mutating various objects under the
> protection of some lock and thread t2 is waiting for the lock. The
> objects are in pieces on the floor with all their invariants
> (temporarily) violated. Now t1 is interrupted by with a function that
> signals a condition and subsequently unwinds the stack. Either the
> lock is automatically released (perhaps by an UNWIND-PROTECT) which
> lets in t2 which finds the objects in pieces on the floor. Or the lock
> is *not* released and t2 waits forever because t1 is never going to
> release it.
>
> I have no idea how the Lisp Machine folks dealt with this problem but
> I know it was a big mess in Java[1]. I'm also not sure there is a
> *right* answer but it's worth thinking about.

You have to defer handling of asynchronous interrupts (external to the
process) during the cleanup of an unwind protect.  

In your example, t1 needs to protect access to the objects not only
with a lock, but also with the appropriate unwind-protects to maintain
the invariants by fixing up whatever isn't finished.

-- 
~jrm
From: Peter Seibel
Subject: Re: Implementing multithreading in Lisp
Date: 
Message-ID: <m3d6bneth2.fsf@javamonkey.com>
Joe Marshall <·············@comcast.net> writes:

> Peter Seibel <·····@javamonkey.com> writes:
> 
> > One other thing to consider, regarding INTERRUPT-PROCESS is what
> > happens to locks held by that thread. If INTERRUPT-PROCESS lets you
> > run an arbitrary function at an arbitrary point in a thread's
> > execution, it makes it really hard to write thread-safe code. Suppose
> > thread t1 is in the midst of mutating various objects under the
> > protection of some lock and thread t2 is waiting for the lock. The
> > objects are in pieces on the floor with all their invariants
> > (temporarily) violated. Now t1 is interrupted by with a function that
> > signals a condition and subsequently unwinds the stack. Either the
> > lock is automatically released (perhaps by an UNWIND-PROTECT) which
> > lets in t2 which finds the objects in pieces on the floor. Or the lock
> > is *not* released and t2 waits forever because t1 is never going to
> > release it.
> >
> > I have no idea how the Lisp Machine folks dealt with this problem
> > but I know it was a big mess in Java[1]. I'm also not sure there
> > is a *right* answer but it's worth thinking about.
> 
> You have to defer handling of asynchronous interrupts (external to
> the process) during the cleanup of an unwind protect.
> 
> In your example, t1 needs to protect access to the objects not only
> with a lock, but also with the appropriate unwind-protects to
> maintain the invariants by fixing up whatever isn't finished.

Right. I think the problem in Java land was that a lot of the threads
one might want to Thread.stop() were threads running user-supplied
code (such as a servlet in an app server or an applet in a browser)
that may or may not have been written with appropriate care. It's hard
enough to get invariants right when things are single-threaded. Having
to defend against asynchronous interruption is just that much harder.

For instance, while there might be a try/finally (Java's
UNWIND-PROTECT) around a particular bit of code, particularly if it
throws other exceptions, if threads can be asynchronously stopped
there needs to be a try/finally around every bit of code that perturbs
an invariant. For instance suppose x and y are fields on some object.
Lots of folks would write code like this:

    synchronized (this) {
      int tmp = y;
      y = x;
      x = tmp;
    }

and think they're safe. But if the thread running that code can get
stopped and the stack unwound at any point they need to write
something like this:

    synchronized (this) {
      boolean done = false;
      int xvalue = x
      int yvalue = y;
      try {
        y = xvalue;
        x = yvalue;
        done = true;

      } finally {
        if (!done) {
          x = xvalue;
          y = yvalue;
        }
      }
    }

And even that's not enough if the same thread can get interrupted
again while it's in the finally block. (Of course if we can count on
that, we could just go ahead and finish the swap in the finally
block.)

Presumably similar care would need to be taken in multithreaded Lisp
if you want your code to be robust in the face of asynchronous
interrupts. (Though I guess stuff like this example is what
WITHOUT-INTERRUPTS constructs are for. Which I guess is how they
should Java should have fixed the Thread.stop() problem.)

-Peter

-- 
Peter Seibel                                      ·····@javamonkey.com

         Lisp is the red pill. -- John Fraser, comp.lang.lisp
From: Paolo Amoroso
Subject: Re: Implementing multithreading in Lisp
Date: 
Message-ID: <874qx084x6.fsf@plato.moon.paoloamoroso.it>
Juan Jose Garcia-Ripoll writes:

> implemented. It was also good to discover that somehow there is a common
> naming convention dating back to the Lisp Machines and thus I do not have
> to figure out everything on my own.

By the way, if you are interested in more detailed information on
LispM multiprocessing, there is some online documentation at the
Minicomputer Orphanage (don't have the URL handy, but a Google search
returns it among the first few hits). Check in particular the relevant
sections of the MIT CADR Lisp reference and TI Explorer's programming
concepts manual.


Paolo
-- 
Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film
From: Mario S. Mommer
Subject: Re: Implementing multithreading in Lisp
Date: 
Message-ID: <fzislgvvvb.fsf@cupid.igpm.rwth-aachen.de>
In the midst of our friendly debate with the nice folks from c.l.f (I
mean this), which you guys have all probably killfiled by now, someone
mentioned that Erlang solved this problem by nont allowing threads to
share data directly. Might something like this be a feasable approach?
From: Matthias
Subject: Re: Implementing multithreading in Lisp
Date: 
Message-ID: <36wislf1ghs.fsf@chagall.ti.uni-mannheim.de>
Mario S. Mommer <········@yahoo.com> writes:

> In the midst of our friendly debate with the nice folks from c.l.f (I
> mean this), which you guys have all probably killfiled by now, someone
> mentioned that Erlang solved this problem by nont allowing threads to
> share data directly. Might something like this be a feasable approach?

For a lot of applications it might.  For some it won't. I'm thinking
about scientific large-scale applications where large amounts of data
are shared between threads and you do not want to copy and/or lock too
large pieces of it at a time.  (However, one may argue that
large-scale scientific programming is rarely done in CL, so this might
not be a typical application scenario.)  Also, the copy-everything
approach might more easily integrate in a mostly functional
programming style than in a procedural style where state information
is modified all the time.

Maybe one could come up with a set of design patterns for concurrent
programming, nicely packaged into some macros.  These would then
simplify working in certain application domains.  For that one would
need portable access to the underlying synchronization primitives.
From: Alan Shutko
Subject: Re: Implementing multithreading in Lisp
Date: 
Message-ID: <87fzgjm4c3.fsf@wesley.springies.com>
Matthias <··@spam.pls> writes:

> For a lot of applications it might.  For some it won't. I'm thinking
> about scientific large-scale applications where large amounts of data
> are shared between threads and you do not want to copy and/or lock too
> large pieces of it at a time. 

The large-scale scientific applications I've worked on tried very
hard not to share anything between threads of execution that didn't
need to be shared, because most supercomputers don't have fast shared
memory.  The fastest one I had access to was the IBM SP2 at Cornell,
which had 512 CPUs and was essentially a cluster of RS6000s on a fast
network.  Since then, I believe the cluster setup has gotten even
more popular.

You can only have shared memory up to a pretty small number of CPUs,
16 or so.  Even then, to minimize contention you really want to
partition your data as much as possible between threads.  So a
share-nothing approach isn't as unlikely as it might seem.

-- 
Alan Shutko <···@acm.org> - I am the rocks.
"Curve: the loveliest distance between two points." - Mae West
From: Tim Bradshaw
Subject: Re: Implementing multithreading in Lisp
Date: 
Message-ID: <ey3llqa6kxk.fsf@cley.com>
* Alan Shutko wrote:

> You can only have shared memory up to a pretty small number of CPUs,
> 16 or so.  Even then, to minimize contention you really want to
> partition your data as much as possible between threads.  So a
> share-nothing approach isn't as unlikely as it might seem.

Bullshit.  Large commercial machines are essentially all
cache-coherent shared memory systems, and large systems are 70-100
CPUs.  Yes, of course, they're doing a lot of clever HW and SW tricks
to do this, and they may or may not actually share one large memory
system (SGIs don't I think, E10ks did, Sunfires probably don't, don't
know about the big HP and IBM boxes), but they look like shared memory
to applications.

The `large shared memory system is impossible' mantra is a bit like
the `Moore's law will run out next year' mantra that people have being
repeating for the last 20 years or so.  It's something that computer
`scientists' repeat because it's obviously going to be true
*eventually* and it gets them research grants in the mean
time. Hardware engineers know it will be true eventually too but,
being much smarter than CS people, they also know just how far they
can push things.  So we have 3+GHz processors and 100+CPU shared
memory systems.  My guess is that shared memory systems might top out
at, maybe, 1000 CPUs.

--tim
From: Rob Warnock
Subject: Re: Implementing multithreading in Lisp
Date: 
Message-ID: <LrCdnbiu045skiOiXTWc-g@speakeasy.net>
Tim Bradshaw  <···@cley.com> wrote:
+---------------
| * Alan Shutko wrote:
| > You can only have shared memory up to a pretty small number of CPUs,
| > 16 or so. 
| 
| Bullshit.  Large commercial machines are essentially all
| cache-coherent shared memory systems, and large systems are 70-100
| CPUs.  Yes, of course, they're doing a lot of clever HW and SW tricks
| to do this, and they may or may not actually share one large memory
| system (SGIs don't I think, E10ks did, Sunfires probably don't, don't
| know about the big HP and IBM boxes), but they look like shared memory
| to applications.
+---------------

SGI Origin systems *do* cache-coherently share one large memory address
space, even though that "single system image" (SSI) is actually made up
of smaller memories scattered throughput the nodes of the ccNUMA system.
That single image obeys the same "sequential consistency"[1] cache-coherency
model which user programs see on classic snoopy-cache bus SMP systems.
Standard Origin systems can have up to 512 CPUs per SSI (though up to
1024 have been shipped in to a few special customers), with up to 1 TB
of cache-coherent main memory.


-Rob

[1] Some versions of the hardware were capable of being run with the
    looser "release consistency" model, but the improvement in performance
    on the small number of applications for which it would theoretically
    make a significant difference was never felt to be worth the trouble
    of fixing the operating system and all of the standard utilities to
    handle it, so Origin (MIPS/Irix) has always shipped with "sequential
    consistency".

-----
Rob Warnock			<····@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607
From: Tim Bradshaw
Subject: Re: Implementing multithreading in Lisp
Date: 
Message-ID: <ey3ekw17re9.fsf@cley.com>
* Rob Warnock wrote:

> SGI Origin systems *do* cache-coherently share one large memory address
> space, even though that "single system image" (SSI) is actually made up
> of smaller memories scattered throughput the nodes of the ccNUMA system.
> That single image obeys the same "sequential consistency"[1] cache-coherency
> model which user programs see on classic snoopy-cache bus SMP
> systems.

I wasn't meaning to imply they didn't, sorry!  What I meant was that
there may or may not actually be one huge memory subsystem there, or
it may be distributed somehow (ccNUMA pretty much), but what it
*looks* like on these systems is cache-coherent shared address space.
I imagine that the single-huge-memory-system machines are probably
dying out, but cc shared address space isn't).  There must be proper
terminology for all this, but I never can get it right.

> Standard Origin systems can have up to 512 CPUs per SSI (though up to
> 1024 have been shipped in to a few special customers), with up to 1 TB
> of cache-coherent main memory.

Well, I should revise my shared address space system maximum size up,
since Origin systems are already hitting my previous estimate. I'd
guess therefore that commercial 10,000 to 100,000 CPU cc shared
address space systems will be made.

--tim
From: Alan Shutko
Subject: Re: Implementing multithreading in Lisp
Date: 
Message-ID: <87vfpdg2fa.fsf@wesley.springies.com>
Tim Bradshaw <···@cley.com> writes:

> Bullshit.  Large commercial machines are essentially all
> cache-coherent shared memory systems, and large systems are 70-100
> CPUs. 

Does it _feel_ like local shared memory?  No additional latency to
access something on another node?  Even on a 2-cpu SMP box you often
want to lock threads to CPUs so you don't thrash the cache, and I
find it hard to believe that this has been suddenly solved for big
iron.  

As long as memory access is nonuniform, performance-sensitive
applications will want to manage what happens where, so most of my
statement stands.  Although it's nice to know that we now have shared
memory up to many more CPUs, so naive apps can potentially scale
without much effort.

-- 
Alan Shutko <···@acm.org> - I am the rocks.
From: Raymond Wiker
Subject: Re: Implementing multithreading in Lisp
Date: 
Message-ID: <867k1vjnmm.fsf@raw.grenland.fast.no>
Matthias <··@spam.pls> writes:

> Mario S. Mommer <········@yahoo.com> writes:
>
>> In the midst of our friendly debate with the nice folks from c.l.f (I
>> mean this), which you guys have all probably killfiled by now, someone
>> mentioned that Erlang solved this problem by nont allowing threads to
>> share data directly. Might something like this be a feasable approach?
>
> For a lot of applications it might.  For some it won't. I'm thinking
> about scientific large-scale applications where large amounts of data
> are shared between threads and you do not want to copy and/or lock too
> large pieces of it at a time. 

        This may not be much of an issue... for large data sets, it is
often possible to partition the set, and let threads have exclusive
access to subsets.

> (However, one may argue that
> large-scale scientific programming is rarely done in CL, so this might
> not be a typical application scenario.)  Also, the copy-everything
> approach might more easily integrate in a mostly functional
> programming style than in a procedural style where state information
> is modified all the time.
>
> Maybe one could come up with a set of design patterns for concurrent
> programming, nicely packaged into some macros.  These would then
> simplify working in certain application domains.  For that one would
> need portable access to the underlying synchronization primitives.

-- 
Raymond Wiker                        Mail:  ·············@fast.no
Senior Software Engineer             Web:   http://www.fast.no/
Fast Search & Transfer ASA           Phone: +47 23 01 11 60
P.O. Box 1677 Vika                   Fax:   +47 35 54 87 99
NO-0120 Oslo, NORWAY                 Mob:   +47 48 01 11 60

Try FAST Search: http://alltheweb.com/
From: james anderson
Subject: Re: Implementing multithreading in Lisp
Date: 
Message-ID: <3FBBEC88.F81CAA78@setf.de>
Roger Corman wrote:
> 
> On Tue, 18 Nov 2003 13:27:48 +0100, Juan Jose Garcia-Ripoll <····@arrakis.es>
> wrote:
> 
> >
> >However the most complicated seems to me to ensure thread-safety in the
> >environment. For instance, if one thread tries to add an element to a hash
> >table, it may happen that the structure has to be resized, and one has to
> >ensure that this does not happen while another thread tries to access the
> >same hash table. Same goes for arrays, conses, etc.
> >
> >My question thus is what should be expected from a multithreaded
> >implementation of common-lisp? What should be safe, and what should be left
> >for the user to take care of? Are there any documents about this? Some
> >inofficial standard that current implementations follow?
> 
> I have been dealing with this same issue in Corman Lisp. I will summarize what
> Corman Lisp currently does. It uses OS preemptive threads, BTW.
> 
> ...
> 
> Hashtables can by optionally synchronized. I have added a system-specific
> keyword extension to MAKE-HASH-TABLE.
> 
> You specify
> :synchronized t
> if you want the synchronization wrappers to be generated for the hash table
> methods. I think it is better for the implementation to provide this than to
> require the user to deal with it, since hash-tables have some unique issues with
> regard to threading and garbage collection.

what would be the argument against providing "shadow" classes and operators
with names drawn from a package which mirrored :common-lisp rather than
changing the standard iterfaces. if an application needs pervasive thread-safe
operators and data then it uses those aspects of the, eg,
:common-lisp-thread-safe package which it needs and shadows the respective
:common-lisp components. is there a real use case for specifying thread-safety
in a given control path through an application on a per-call basis as opposed
to statically?

> 
> ...
> 
> I would like to see CLOS extended with a similar :synchronized option on
> MAKE-INSTANCE which would add a synchronization object to the instance. Then
> methods could use this sync object as necessary. An easy way to specify that a
> method should use the sync object would be helpful as well (usually only methods
> that modify the object need to use this). We don't currently do any of this, but
> we do provide macros that help a bit in defining synchronized methods.
> 

similar to the issue above, what is the use case which argues for per-instance
specification rather than per-class or -metaclass?

i would also wonder whether one would also need to synchronize on the method
or generic function for those occasions when multi-object invariants are
violated, which would argue for providing synchronizing method-combinations in addition.

...


...