the evil of continuations
francois Morvillier
whole title but it ends with "how to win big"), the author mentions the
fact that Scheme would be a good basis for a standardisation of LISP if
it weren't for its continuations (call-with-current-continuation ...).
Could someone please elaborate on this?
Also I'd like to know what's the general opinion on continuations - do
people actually understand them, use them, like them?
Cheers.
François.
Joe Marshall
> In a paper I've read on the future of LISP (forgot the author and the
> whole title but it ends with "how to win big"),
Richard Gabriel wrote it. The title is
`Lisp: Good News, Bad News, How to Win Big'
The url is http://www.ai.mit.edu/docs/articles/good-news/good-news.html
> the author mentions the"
> fact that Scheme would be a good basis for a standardisation of LISP if
> it weren't for its continuations (call-with-current-continuation ...).
> Could someone please elaborate on this?
The typical uses of first-class continuations are in
exception-handling, co-routining, and in creating new control-flow
primitives. Common Lisp provides mechanisms for all of these, and the
Common Lisp implementation has much less overhead than first-class
continuations.
First class continuations make compilation harder: when any
computation may be restarted because a continuation might be captured
in a lower layer, the compiler has to be very conservative about
allocating mutable structures.
First class continuations are confusing as well --- apparently much
more so than catch/throw, error-handlers, co-routines, etc.
In Gabriel's opinion, first-class continuations are more trouble than
they are worth.
> Also I'd like to know what's the general opinion on continuations - do
> people actually understand them, use them, like them?
A lot of people understand them, they are not used *that* frequently,
except in Scheme system code. If you have them, they can be pretty
handy, but I don't miss them when I'm hacking Common Lisp.
Barry Margolin
Joe Marshall <jmar...@alum.mit.edu> wrote:
>francois Morvillier <francois....@eurocontrol.fr> writes:
>> Also I'd like to know what's the general opinion on continuations - do
>> people actually understand them, use them, like them?
>
>A lot of people understand them, they are not used *that* frequently,
>except in Scheme system code. If you have them, they can be pretty
>handy, but I don't miss them when I'm hacking Common Lisp.
It should be noted that Scheme was designed mainly for pedagogical
purposes, particularly for research into language design, whereas Common
Lisp was intended to be a practical language for complex application
development. Thus, Scheme provides first-class continuations because
they're a useful substrate upon which just about any control structure can
be implemented. But most programmers aren't doing research about control
structures, so they have little need to use them directly; they're more
likely to use macros that have been implemented using them. For instance,
I expect there are Scheme exception handling macros, and they would
naturally expand into call/cc uses. It's no more necessary for most
programmers to understand continuations than they need to understand how
transistors work (in both cases, understanding them can be helpful, but you
can get by without it).
--
Barry Margolin, bar...@genuity.net
Genuity, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
Thant Tessman
Barry Margolin wrote:
> It should be noted that Scheme was designed mainly for pedagogical
> purposes, particularly for research into language design, whereas Common
> Lisp was intended to be a practical language for complex application
> development. Thus, Scheme provides first-class continuations because
> they're a useful substrate upon which just about any control structure can
> be implemented. [...]
The question remains: What is it about continuations that makes a
language (or its implementation) inappropriate for "real work"? What
about continuations in SML/NJ?
-thant
Joe Marshall
> The question remains: What is it about continuations that makes a
> language (or its implementation) inappropriate for "real work"?
Nothing, per se. It would just be more difficult to implement, and it
would be difficult to justify adding the feature to any language where
adequate alternatives exist (like CL).
> What about continuations in SML/NJ?
Appel argues that heap-allocation of continuation frames is cheap
enough to be considered an alternative, but Jim Miller and Bill Rozas
showed that a stack implemention can outperform a heap.
If your substrate gives you heap-allocated frames, then it makes
sense to create a call-with-current-continuation construct and use it
to implement your various control structures. But I think it would be
wrong to *require* call-with-current-continuation as part of a Common
Lisp substrate because the upper levels don't need it.
Lieven Marchand
Note: I only followed up in comp.lang.lisp. Your question has been
debated/flamed for years between Common Lisp and Scheme fans and I'll
doubt it'll go better this time.
> In a paper I've read on the future of LISP (forgot the author and the
> whole title but it ends with "how to win big"), the author mentions the
> fact that Scheme would be a good basis for a standardisation of LISP if
> it weren't for its continuations (call-with-current-continuation ...).
> Could someone please elaborate on this?
>
Continuations are difficult to implement in traditional
compilers. (It's completely possible to implement them well in
compilers but they strongly influence the entire design of the
compiler - see Apple's book on compiling with continuations for more
info)
Continuations in scheme are used as a basic building block to build
abstractions that are easier to use. (things like exceptions,
unwind-protect etc.) Common Lisp has included these abstractions as
special forms.
The ample experience in teaching scheme seems to indicate that
continuations are the hardest concept to get through to students,
especially escaping continuations and continuations that are entered
multiple times. They are also extremely non-local and non-lexical.
--
Lieven Marchand <m...@bewoner.dma.be>
When C++ is your hammer, everything looks like a thumb. Steven M. Haflich
Thant Tessman
Joe Marshall wrote:
>
> Thant Tessman <th...@acm.org> writes:
>
> > The question remains: What is it about continuations that makes a
> > language (or its implementation) inappropriate for "real work"?
>
> Nothing, per se. It would just be more difficult to implement, and it
> would be difficult to justify adding the feature to any language where
> adequate alternatives exist (like CL).
I'm not familiar with Common Lisp. Is it that CL has its own threading
mechanism? (I'm not arguing that call/cc should be added to CL. I'm way
to ignorant of CL to do anything like that. It's just that call/cc is an
amazingly powerful thing, and I am curious why it's not as celebrated a
language feature as I would think it should be.)
>
> > What about continuations in SML/NJ?
>
> Appel argues that heap-allocation of continuation frames is cheap
> enough to be considered an alternative, but Jim Miller and Bill Rozas
> showed that a stack implemention can outperform a heap.
I thought there were newer techniques that allow stack-based
implementations to still do call/cc efficiently. (Or is that what you're
talking about?)
[...]
-thant
Barry Margolin
>
>
>Barry Margolin wrote:
>
>> It should be noted that Scheme was designed mainly for pedagogical
>> purposes, particularly for research into language design, whereas Common
>> Lisp was intended to be a practical language for complex application
>> development. Thus, Scheme provides first-class continuations because
>> they're a useful substrate upon which just about any control structure can
>> be implemented. [...]
>
>about continuations in SML/NJ?
You've got the implication backwards. It's not 'continuations -> not
real', it's 'not real -> continuations'. In particular, it's the lack of
high-level constructs that makes a language like Scheme more difficult to
use for real work, because you have to find or create them when you need
them.
Basically, I consider Scheme a lower-level member of the Lisp family than
Common Lisp. Continuations are a low-level facility, not a high-level
facility.
Barry Margolin
>I'm not familiar with Common Lisp. Is it that CL has its own threading
>mechanism? (I'm not arguing that call/cc should be added to CL. I'm way
>to ignorant of CL to do anything like that. It's just that call/cc is an
>amazingly powerful thing, and I am curious why it's not as celebrated a
>language feature as I would think it should be.)
CL doesn't have threading in the standard, although most implementations
have it as an extension. The same is true for just about every popular HLL
except for Java and Ada, I think.
But it has exceptions and various types of non-local transfers (both
dynamic and lexical), which are often what continuations are used to
implement. CL doesn't support everything that Scheme continuations allow;
specifically, CL environments capture name bindings, but not control flow,
so you can't re-enter a block that has been exited (this avoids the problem
of spaghetti stacks, but it's also what requires threading to be an
extension).
Joe Marshall
> I'm not familiar with Common Lisp. Is it that CL has its own threading
> mechanism?
Most implementations of Common Lisp provide some multi-threading
capability. There is no `standard' (although most of the
multi-threading implementations seem to be based on `stack groups').
> (I'm not arguing that call/cc should be added to CL. I'm way
> to ignorant of CL to do anything like that. It's just that call/cc is an
> amazingly powerful thing, and I am curious why it's not as celebrated a
> language feature as I would think it should be.)
Some people don't like it. Go figure.
> I thought there were newer techniques that allow stack-based
> implementations to still do call/cc efficiently. (Or is that what you're
> talking about?)
They are still much hairier than implementations that only know how to
unwind the stack. They also preclude allocating mutable structures
and variables on the stack.
vsync
> First class continuations make compilation harder: when any
> computation may be restarted because a continuation might be captured
Hm. That bit made me think of Prolog for a second. I'm a CL fan
myself, and don't have much experience in Scheme, but this intrigues
me a bit. Are continuations more like the backtracking and things
that go on in Prolog, or like exceptions in C++ and Java?
--
vsync
http://quadium.net/ - last updated Fri Jun 16 00:38:12 MDT 2000
Orjner.
at ncal point verio point com x@x.x tom
> The question remains: What is it about continuations that makes a
> language (or its implementation) inappropriate for "real work"? What
> about continuations in SML/NJ?
Well, it's not the presence of continuations as much as the absence of
exceptions and threads (SML/NJ has both). Standardizing exceptions in
particular is important because it means that code that different
people write has a standard way of communicating error conditions. If
everybody does their own exception package, I don't know how to even
detect that something went wrong in your library.
Tom.
Matthias Blume
> Thant Tessman <th...@acm.org> writes:
>
> > The question remains: What is it about continuations that makes a
> > language (or its implementation) inappropriate for "real work"?
>
> Nothing, per se. It would just be more difficult to implement, and it
> would be difficult to justify adding the feature to any language where
> adequate alternatives exist (like CL).
>
> > What about continuations in SML/NJ?
>
> Appel argues that heap-allocation of continuation frames is cheap
> enough to be considered an alternative, but Jim Miller and Bill Rozas
> showed that a stack implemention can outperform a heap.
Notice that the two statements (Appel's claim and Rozas' demonstration
(wasn't it actually Clinger et al.?)) are not necessarily contradictory.
Matthias
--
Matthias Blume <blume@k_u_r_i_m_s.k_y_o_t_o-u.a_c.j_p>
Kyoto University, Research Institute for Mathematical Sciences
(remove those spam-preventing underscores from mail address)
Tim Bradshaw
> Thant Tessman <th...@acm.org> writes:
>> I'm not familiar with Common Lisp. Is it that CL has its own threading
>> mechanism?
> Most implementations of Common Lisp provide some multi-threading
> capability. There is no `standard' (although most of the
> multi-threading implementations seem to be based on `stack groups').
If you use call/cc (+ something else: timer interrupts?) to do
threading could such a system be persuaded to sit naturally on top of,
say, posix threads? By `naturally' I mean `without heroic effort' or
something.
(Not that the current CL thread systems do, I know)
--tim
felix
vsync wrote in message <87d7lhw...@quadium.net>...
>Hm. That bit made me think of Prolog for a second. I'm a CL fan
>myself, and don't have much experience in Scheme, but this intrigues
>me a bit. Are continuations more like the backtracking and things
>that go on in Prolog, or like exceptions in C++ and Java?
They are both. That's the beauty of it.
felix
Pierre R. Mai
OTOH Douglas T. Crosher is still working on an experimental version of
CMUCL multi-threading which sits atop native threading mechanisms on
Linux (and FreeBSD). This project seems to be progressing nicely (see
current snapshots on http://www.cons.org/cmucl/ in the experimental
Category). So it seems that it is imminently doable, which seems to
suggest that most users of the commercial systems don't see native
threading for Lisp stuff as a high priority item...
Regs, Pierre.
--
Pierre Mai <pm...@acm.org> PGP and GPG keys at your nearest Keyserver
"One smaller motivation which, in part, stems from altruism is Microsoft-
bashing." [Microsoft memo, see http://www.opensource.org/halloween1.html]
Pierre R. Mai
> Joe Marshall <jmar...@alum.mit.edu> writes:
>
> > First class continuations make compilation harder: when any
> > computation may be restarted because a continuation might be captured
>
> Hm. That bit made me think of Prolog for a second. I'm a CL fan
> myself, and don't have much experience in Scheme, but this intrigues
> me a bit. Are continuations more like the backtracking and things
> that go on in Prolog, or like exceptions in C++ and Java?
Continuations can be used to implement both of them (and a number of
other things like multi-threading, basic control structures, etc.).
In effect continuations take the control-flow (and local state) of a
program at a certain point-in time, and make them available to the
program itself. In this way you can implement e.g. the cut operator
of Prolog, or catch and throw for exception handling, including
automatic restarts, or e.g. yield for multi-threading, etc.
Note that there are other mechanisms to implement any of the above
mechanims.
Joe Marshall
> Joe Marshall <jmar...@alum.mit.edu> writes:
>
> > Appel argues that heap-allocation of continuation frames is cheap
> > enough to be considered an alternative, but Jim Miller and Bill Rozas
> > showed that a stack implemention can outperform a heap.
>
> Notice that the two statements (Appel's claim and Rozas' demonstration)
> are not necessarily contradictory.
Precisely so. In fact, Miller and Rozas' paper is titled
``Garbage Collection is Fast, but a Stack is Faster''. It is a question
of what is `fast enough'. Miller and Rozas conclude that stack
allocation ``remains an important implementation technique for
procedure calls''.
> (wasn't it actually Clinger et al.?)
James S. Miller and Guillermo J. Rozas
AI memo 1462, March 1994, 37 pages
Rainer Joswig
> OTOH Douglas T. Crosher is still working on an experimental version of
> CMUCL multi-threading which sits atop native threading mechanisms on
> Linux (and FreeBSD). This project seems to be progressing nicely (see
> current snapshots on http://www.cons.org/cmucl/ in the experimental
> Category). So it seems that it is imminently doable, which seems to
> suggest that most users of the commercial systems don't see native
> threading for Lisp stuff as a high priority item...
Maybe not on Unix - but on MacOS and Windows NT. MCL and
LispWorks for Windows both use native threads.
--
Rainer Joswig, BU Partner,
ISION Internet AG, Steinhöft 9, 20459 Hamburg, Germany
Tel: +49 40 3070 2950, Fax: +49 40 3070 2999
Email: mailto:rainer...@ision.net WWW: http://www.ision.net/
Pierre R. Mai
Pierre R. Mai
> * Joe Marshall wrote:
> > Thant Tessman <th...@acm.org> writes:
> >> I'm not familiar with Common Lisp. Is it that CL has its own threading
> >> mechanism?
>
> > Most implementations of Common Lisp provide some multi-threading
> > capability. There is no `standard' (although most of the
> > multi-threading implementations seem to be based on `stack groups').
>
> If you use call/cc (+ something else: timer interrupts?) to do
> threading could such a system be persuaded to sit naturally on top of,
> say, posix threads? By `naturally' I mean `without heroic effort' or
> something.
>
> (Not that the current CL thread systems do, I know)
OTOH Douglas T. Crosher is still working on an experimental version of
CMUCL multi-threading which sits atop native threading mechanisms on
Linux (and FreeBSD). This project seems to be progressing nicely (see
current snapshots on http://www.cons.org/cmucl/ in the experimental
Category). So it seems that it is imminently doable, which seems to
suggest that most users of the commercial systems don't see native
threading for Lisp stuff as a high priority item...
Regs, Pierre.
Will Hartung
Pierre R. Mai wrote in message
<871z1wq...@orion.dent.isdn.cs.tu-berlin.de>...
>
>OTOH Douglas T. Crosher is still working on an experimental version of
>CMUCL multi-threading which sits atop native threading mechanisms on
>Linux (and FreeBSD). This project seems to be progressing nicely (see
>current snapshots on http://www.cons.org/cmucl/ in the experimental
>Category). So it seems that it is imminently doable, which seems to
>suggest that most users of the commercial systems don't see native
>threading for Lisp stuff as a high priority item...
I think part of the problem isn't the threads themselves, it's the
portability of the implementation. I'm that across the major Unices there
are some significant distinctions in how they handles threads. These issues
are non-events for something like NT or even the MacOS.
Of course one can suppose that you'd think it would be practical to release
an implementation as each Unix implementation comes along, but then there
may some interface consistency issues later on.
For myself, the only thing I want out of a threaded Lisp is for it to not
block on FFI calls. The internal MP is fine, but once the hit an FFI the MP
comes to a screeching halt. Normally this isn't important, but when that FFI
is tied to something like "execute really_ugly_stored_procedure" on an
RDBMS, it kind of smashes your concurrency flat. In fact, it effectively
serializes all of your database calls in general. Bother.
Will Hartung
(vft...@home.com)
Boris Schaefer
| Barry Margolin wrote:
|
| > It should be noted that Scheme was designed mainly for pedagogical
| > purposes, particularly for research into language design, whereas Common
| > Lisp was intended to be a practical language for complex application
| > development. Thus, Scheme provides first-class continuations because
| > they're a useful substrate upon which just about any control structure can
| > be implemented. [...]
|
| The question remains: What is it about continuations that makes a
| language (or its implementation) inappropriate for "real work"? What
| about continuations in SML/NJ?
It's the same reason that Java doesn't have "goto" and full MI. It
was thought that it could and would be abused too much. (Personally,
I don't care about "goto", but I think they made a mistake with not
having MI.)
--
Boris Schaefer <bo...@uncommon-sense.net>
If you don't drink it, someone else will.
Tim Bradshaw
> I think part of the problem isn't the threads themselves, it's the
> portability of the implementation. I'm that across the major Unices there
> are some significant distinctions in how they handles threads. These issues
> are non-events for something like NT or even the MacOS.
I think it's a horrible nightmare to be portable across posix threads
implementations.
Quite apart from that there are GC issues.
--tim
Pierre R. Mai
> * Will Hartung wrote:
>
> > I think part of the problem isn't the threads themselves, it's the
> > portability of the implementation. I'm that across the major Unices there
> > are some significant distinctions in how they handles threads. These issues
> > are non-events for something like NT or even the MacOS.
>
> I think it's a horrible nightmare to be portable across posix threads
> implementations.
Indeed, DTC's first efforts seem to have been using POSIX threads,
which he abandoned soon in favour of the native threading mechanisms
of Linux and FreeBSD respectively.
![صورة ملف Michael Sperber [Mr. Preprocessor] الشخصي](http://lh3.googleusercontent.com/a-/ALV-UjW1Ug-7D5rvPAe0Dy8QWlBwdoMp8sHWFACGdNTzwJ9mF7CkTQ=s40-c)
Michael Sperber [Mr. Preprocessor]
>>>>> "Pierre" == Pierre R Mai <pm...@acm.org> writes:
Pierre> Tim Bradshaw <t...@cley.com> writes:
>> * Joe Marshall wrote:
>> > Thant Tessman <th...@acm.org> writes:
>> >> I'm not familiar with Common Lisp. Is it that CL has its own threading
>> >> mechanism?
>>
>> > Most implementations of Common Lisp provide some multi-threading
>> > capability. There is no `standard' (although most of the
>> > multi-threading implementations seem to be based on `stack groups').
>>
>> If you use call/cc (+ something else: timer interrupts?) to do
>> threading could such a system be persuaded to sit naturally on top of,
>> say, posix threads? By `naturally' I mean `without heroic effort' or
>> something.
>>
>> (Not that the current CL thread systems do, I know)
Pierre> OTOH Douglas T. Crosher is still working on an experimental version of
Pierre> CMUCL multi-threading which sits atop native threading mechanisms on
Pierre> Linux (and FreeBSD).
Unfortunately, OS threads are often *way* too heavyweight for the
really interesting applications of threads.
--
Cheers =8-} Mike
Friede, Völkerverständigung und überhaupt blabla
Michael Sperber [Mr. Preprocessor]
Thant> I thought there were newer techniques that allow stack-based
Thant> implementations to still do call/cc efficiently. (Or is that what you're
Thant> talking about?)
They are not really new, but only recently the relevant publication
has become accessible:
William D. Clinger, Anne Hartheimer, Eric Ost: Implementation
Strategies for First-Class Continuations. Higher-Order and Symbolic
Computation 12(1): 7-45 (1999)
Makes for excellent reading!
Martin Cracauer
OS threads != kernel sheduled threads. Most thread interfaces in
current Unix systems shedule N user threads onto M<N kernel
shedulabale threads. Linux and Windows NT are exceptions, they let
every threads be handled by the kernel.
Martin
--
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Martin Cracauer <crac...@bik-gmbh.de> http://www.bik-gmbh.de/~cracauer/
FreeBSD - where you want to go. Today. http://www.freebsd.org/
Michael Sperber [Mr. Preprocessor]
Martin> spe...@informatik.uni-tuebingen.de (Michael Sperber [Mr. Preprocessor]) writes:
>>>>>>> "Pierre" == Pierre R Mai <pm...@acm.org> writes:
Pierre> OTOH Douglas T. Crosher is still working on an experimental version of
Pierre> CMUCL multi-threading which sits atop native threading mechanisms on
Pierre> Linux (and FreeBSD).
>> Unfortunately, OS threads are often *way* too heavyweight for the
>> really interesting applications of threads.
Martin> OS threads != kernel sheduled threads. Most thread interfaces in
Martin> current Unix systems shedule N user threads onto M<N kernel
Martin> shedulabale threads. Linux and Windows NT are exceptions, they let
Martin> every threads be handled by the kernel.
Both are usually too heavyweight.
Jens Kilian
> has become accessible:
>
> William D. Clinger, Anne Hartheimer, Eric Ost: Implementation
> Strategies for First-Class Continuations. Higher-Order and Symbolic
> Computation 12(1): 7-45 (1999)
A Google search turned up the following article:
http://www.acm.org/pubs/citations/proceedings/lfp/62678/p124-clinger/
Is this the same paper?
--
mailto:j...@acm.org phone:+49-7031-464-7698 (HP TELNET 778-7698)
http://www.bawue.de/~jjk/ fax:+49-7031-464-7351
PGP: 06 04 1C 35 7B DC 1F 26 As the air to a bird, or the sea to a fish,
0x555DA8B5 BB A2 F0 66 77 75 E1 08 so is contempt to the contemptible. [Blake]
Tim Bradshaw
> Unfortunately, OS threads are often *way* too heavyweight for the
> really interesting applications of threads.
unfortunately, unless you use the OS-supplied threads you'll never run
on a multiprocessor.
--tim
Matthias Blume
True (probably), but it does not mean that every thread has to be
mapped to an OS thread. For highly concurrent code, threads can and
should be kept as light-weight as possible. OS threads can be
allocated to match the number of physical processors. The threads of
the concurrent program then use those OS threads in a multiplexed way
as "compute-servers" (just like they would use the single thread of a
single-CPU system without OS threads).
Hannah Schroeter
In article <8ipt1q$2umv$1...@counter.bik-gmbh.de>,
Martin Cracauer <crac...@counter.bik-gmbh.de> wrote:
>[...]
>OS threads != kernel sheduled threads. Most thread interfaces in
>current Unix systems shedule N user threads onto M<N kernel
>shedulabale threads. Linux and Windows NT are exceptions, they let
>every threads be handled by the kernel.
However, userland threads also need a completely separate runtime
stack, allocating at least one complete page of memory, perhaps
more. That's a memory overhead that can well be bigger than with a
specialized thread implementation based e.g. on first class continuations
(i.e. CPS transform in the compiler).
Kind regards,
Hannah.
Xenophon Fenderson the Carbon(d)ated
Michael> Both are usually too heavyweight.
What do you mean by "heavyweight"?
--
"I will never submit to your lustful advances", cried Princess Beatrice, as the
wealthy, powerful, muscular and strikingly handsome Count Bertrand slowly
adjusted his mink gloves, "at least for another half-hour!"
--Dr. Zinn, from the novel
Erik Naggum
| Unfortunately, OS threads are often *way* too heavyweight for the
| really interesting applications of threads.
* Tim Bradshaw
| unfortunately, unless you use the OS-supplied threads you'll never run
| on a multiprocessor.
Whatever happened to good old interprocess communication, shared
memory, etc, on multiprocessor systems? Whatever it is people are
doing with threads can be handled without involving any kernel.
There need be no particularly complicated implementation, either.
At issue, however, is whether it makes sense to write languages and
runtime systems that maintain the threads and surrounding support or
hack things by hand in what passes for the "popular" languages.
I'm sorry, but I completely fail to understand why OS threads is the
only way to utilize "modern" multiprocessor systems. Maybe I'm just
too old to be able to pretend we didn't have SMPs in the 1980's.
#:Erik, sighing
--
If this is not what you expected, please alter your expectations.
Kenneth P. Turvey
>
>>>>>> "Pierre" == Pierre R Mai <pm...@acm.org> writes:
>
>
>>> * Joe Marshall wrote:
>>> > Thant Tessman <th...@acm.org> writes:
>>> >> I'm not familiar with Common Lisp. Is it that CL has its own threading
>>> >> mechanism?
>>>
>>> > Most implementations of Common Lisp provide some multi-threading
>>> > capability. There is no `standard' (although most of the
>>> > multi-threading implementations seem to be based on `stack groups').
>>>
>>> If you use call/cc (+ something else: timer interrupts?) to do
>>> threading could such a system be persuaded to sit naturally on top of,
>>> say, posix threads? By `naturally' I mean `without heroic effort' or
>>> something.
>>>
>>> (Not that the current CL thread systems do, I know)
>
>Pierre> CMUCL multi-threading which sits atop native threading mechanisms on
>Pierre> Linux (and FreeBSD).
>
>really interesting applications of threads.
Could you explain this a bit further. I can't really see how OS threads
would carry more overhead.
--
Kenneth P. Turvey <kt-...@SprocketShop.com>
http://www.tranquility.net/~kturvey/resume/resume.html
--------------------------------------------------------
I certainly learned a great deal from 3,000 town hall meetings across
my home state of Tennessee over a 16-year period.
-- Al Gore (That's one every 46.7 hours)
Tim Bradshaw
> I'm sorry, but I completely fail to understand why OS threads is the
> only way to utilize "modern" multiprocessor systems. Maybe I'm just
> too old to be able to pretend we didn't have SMPs in the 1980's.
That's not what I meant -- I worded it badly. What I meant was `a
threading system that isn't based on OS threads is going to have a
very hard time utilizing a multiprocessor'. There are obviously other
ways to use a multiprocessor.
(and the `very hard time' is intentional -- I can imagine a threading
system which didn't use OS facilities which made use of a
multiprocessor, but I think it would be significantly painful to
implement if it was to be general).
--tim
Espen Vestre
> (and the `very hard time' is intentional -- I can imagine a threading
> system which didn't use OS facilities which made use of a
> multiprocessor, but I think it would be significantly painful to
> implement if it was to be general).
but it isn't always 'very hard'. Not if your system consists of several
communicating processes.
--
(espen)
Tim Bradshaw
> but it isn't always 'very hard'. Not if your system consists of several
> communicating processes.
Yes, obviously. The trick is providing a supposedly-general facility,
or arguing convincingly against other people (C/posix vendors) who do.
--tim
Matthias Blume
> >>>>> "Michael" == Michael Sperber [Mr Preprocessor] <spe...@informatik.uni-tuebingen.de> writes:
>
> Michael> Both are usually too heavyweight.
>
> What do you mean by "heavyweight"?
High overhead for creation and context switching. Makes it
impractical to have more than a few. Hundreds would be pushing it,
thousands is pretty much out of the question. Moreover, many systems
place rather arbitrary restrictions on how many threads can be
created.
Espen Vestre
> Yes, obviously. The trick is providing a supposedly-general facility,
> or arguing convincingly against other people (C/posix vendors) who do.
well, if one wants general mechanisms for multiple processors, why not
jump a step further and ask for general mechanisms for programming
over _clusters_... there was an interesting talk on this at ELUGM-99,
I found the paper at one of the authors home page:
http://lki-www.informatik.uni-hamburg.de/~hotz/homepage.html
--
(espen)
Michael Sperber [Mr. Preprocessor]
Jens> spe...@informatik.uni-tuebingen.de (Michael Sperber [Mr. Preprocessor]) writes:
>> They are not really new, but only recently the relevant publication
>> has become accessible:
>>
>> William D. Clinger, Anne Hartheimer, Eric Ost: Implementation
>> Strategies for First-Class Continuations. Higher-Order and Symbolic
>> Computation 12(1): 7-45 (1999)
Jens> A Google search turned up the following article:
Jens> http://www.acm.org/pubs/citations/proceedings/lfp/62678/p124-clinger/
Jens> Is this the same paper?
The HOSC paper is a considerably updated and expanded version of its
LFP predecessor.
Michael Sperber [Mr. Preprocessor]
Tim> * Michael Sperber wrote:
>> Unfortunately, OS threads are often *way* too heavyweight for the
>> really interesting applications of threads.
Tim> unfortunately, unless you use the OS-supplied threads you'll never run
Tim> on a multiprocessor.
You're confusing two different things here:
a) Threads to implement programming paradigms which depend on
concurrency, i.e. GUIs, reactive systems etc.
b) Threads to utilize multiprocessing to increase performance.
OS-supplied threads are sometimes OK for b) but mostly not OK for a).
There's no inherent reason why lightweight threads can't utilize
multiprocessing. However (as Erik Naggum points out later in the
thread), threads are not an ideal mechanism to exploit
multiprocessing.
Tim Bradshaw
> You're confusing two different things here:
> a) Threads to implement programming paradigms which depend on
> concurrency, i.e. GUIs, reactive systems etc.
> b) Threads to utilize multiprocessing to increase performance.
No, I'm not, I just don't care at all about (a), and I do care about
(b).
Tim Bradshaw
> well, if one wants general mechanisms for multiple processors, why not
> jump a step further and ask for general mechanisms for programming
> over _clusters_... there was an interesting talk on this at ELUGM-99,
> I found the paper at one of the authors home page:
It would be very nice if there was such generality, however, as far
as I know no one really knows how to write efficient stuff on a
cache-coherent shared-memory box which is also efficient on a
shared-nothing cluster.
(By `efficient' I mean, at least in part `makes good use of the money
you spent' -- if your program doesn't benefit from all the expensive
stuff that big commercial shared-memory machines have, but would run
just as well on a cluster, then it's not `efficient' by this
definition. I should probably use another word. And not beign
efficient on those machines might just mean they're a wastoe of money
of course).
--tim
Phil Stubblefield
Interesting. Do you mean:
(1) you don't care about (a) for the purposes of this discussion;
(2) you acknowledge the need for (a) but don't often have the time
and/or resources to utilitze it;
(3) think (a) is a load of crap; or
(4) some combination thereof?
Phil Stubblefield
Rockwell Palo Alto Laboratory 206/655-3204
http://www.rpal.rockwell.com/~phil ph...@rpal.rockwell.com
Jost Boekemeier
> > Michael> Both are usually too heavyweight.
> >
> > What do you mean by "heavyweight"?
>
> High overhead for creation and context switching.
Hmm, and I thought that only processes have high overhead. Threads
(created by the Linux clone() call for example) essentially share
their top-level environment and their code.
Why is that more "heavyweight" than continuations?
Jost
Tim Bradshaw
> (1) you don't care about (a) for the purposes of this discussion;
Yes I mean this one: obviously I realize it's important that gui apps
perform well &c. I also kind of misread the question, because
actually I care about concurrency too, just in this context I was
interested a threading system than can make use of multiprocessors.
Sorry for being confusing / confused.
--tim
Erik Naggum
| Interesting. Do you mean:
|
| (1) you don't care about (a) for the purposes of this discussion;
|
| and/or resources to utilitze it;
|
| (3) think (a) is a load of crap; or
|
| (4) some combination thereof?
Or perhaps (5) think some other implementation technique is superior
to using threads, so the performance of threads is irrelevant.
#:Erik
Rob Warnock
+---------------
| ...as I know no one really knows how to write efficient stuff on a
| cache-coherent shared-memory box which is also efficient on a
| shared-nothing cluster.
Well, one data point: The SGI versions of the MPI libraries (I think we
call ours "MPT"?) are tuned to use local shared-memory mailboxes instead
of network calls if the target of the MPI operation is on the same system.
This means, for example, that you get a *lot* better MPI performance by
clustering a few "fat" (many-CPU) nodes, compared to a whole bunch of
small nodes, assuming the same total CPU count.
Ob. c.l.l.: I only wish I could find a "killer" Lisp application that
could make good use of a 256-CPU (or bigger) system. Most of the huge
HPC apps are still Fortran... (*sigh*)
-Rob
-----
Rob Warnock, 41L-955 rp...@sgi.com
Applied Networking http://reality.sgi.com/rpw3/
Silicon Graphics, Inc. Phone: 650-933-1673
1600 Amphitheatre Pkwy. PP-ASEL-IA
Mountain View, CA 94043
George Neuner
>* Erik Naggum wrote:
>
>> I'm sorry, but I completely fail to understand why OS threads is the
>> only way to utilize "modern" multiprocessor systems. Maybe I'm just
>> too old to be able to pretend we didn't have SMPs in the 1980's.
>
>That's not what I meant -- I worded it badly. What I meant was `a
>threading system that isn't based on OS threads is going to have a
>very hard time utilizing a multiprocessor'. There are obviously other
>ways to use a multiprocessor.
>
>(and the `very hard time' is intentional -- I can imagine a threading
>system which didn't use OS facilities which made use of a
>multiprocessor, but I think it would be significantly painful to
>implement if it was to be general).
>
>--tim
I recall seeing a paper from the University of Washington on something
called "scheduler activations" that was concerned with kernel support
for user level thread management.
IIRC - the authors proposed a system in which kernel thread events
were reflected to the user level scheduler. They created a kind of
virtual multiprocessor which allowed for user level threads to be
mapped to a potentially dynamic pool of kernel threads. In effect, it
treated each kernel thread as a separate processor and mapped user
threads to processors as needed.
UW's Spin OS project looks [superficially at least] like it
incorporates a lot of the ideas I recall from that paper.
George
Lyman Taylor
> >multiprocessor, but I think it would be significantly painful to
> >implement if it was to be general).
> IIRC - the authors proposed a system in which kernel thread events
Or from "painful to use".
I haven't scanned that paper but....
If the kernel threads have there own scheduler then there are
two levels of scheduling that occur. Scheduling on the abstract and
physical processors. I suspect that was not a performance benefit.
Lyman
George Neuner
<lyman....@mindspring.com> wrote:
> "Proposed" is not necessarily distinct from "painful to implement". :-)
> Or from "painful to use".
No question.
> I haven't scanned that paper but....
> If the kernel threads have there own scheduler then there are
> two levels of scheduling that occur. Scheduling on the abstract and
> physical processors. I suspect that was not a performance benefit.
User space thread packages have to deal with this now - they have
little control over the kernel thread executing the process. User
threading only affects which part of the application executes when or
if the OS decides to execute it.
Despite that, for certain types of applications, e.g., transaction
systems that create thousands of short lived threads, user threading
is a really big win over kernel threading.
The Spin OS is interesting in that the microkernel can reflect almost
any kernel event into user space for special handling. A process can
only receive events that affect its own virtual space, so there is
isolation from other processes, but the user level event handlers run
with kernel privilege so there is no protection penalty in invoking
them. The handlers are signed in some manner based on what OS
functions they use so the kernel can statically check privileges
before the handler is installed.
George
eric hoffman
as far as I can recall, scheduler activitations are a specialized form
of upcalls used to get around problems with threading caused by the
process/kernel boundary. as such its not as interesting or useful as
a generalized continuation approach.
in case people are interested here is the reference:
T. Anderson, B. Bershad, E. Lazowska and H. Levy. ``Scheduler
Activations: Effective Kernel Support for the User-Level Management of
Parallelism.'' ACM Transactions on Computer Systems 10, 1 (February
1992), pp. 53-79.
Matthew R Wette
> Solaris uses a user-level + kernel-level thread approach. The kernel
> threads are mapped to processors. The user threads are mapped to
> kernel threads. There are hooks to allow the user to specify how many
> processors should be used. There used to be white papers on this
> design but I just looked on sun.com and didn't find them. Maybe
> ftp.uu.net has them still.
There are some details here:
http://www.sun.com/software/white-papers/wp-realtime/index.html
--
Matthew.R.Wette at jpl.nasa.gov -- I speak for myself, not for JPL.
Matthew R Wette
Solaris uses a user-level + kernel-level thread approach. The kernel
threads are mapped to processors. The user threads are mapped to
kernel threads. There are hooks to allow the user to specify how many
processors should be used. There used to be white papers on this
design but I just looked on sun.com and didn't find them. Maybe
ftp.uu.net has them still.
Matt
Rob Warnock
+---------------
| Solaris uses a user-level + kernel-level thread approach. The kernel
| threads are mapped to processors. The user threads are mapped to
| kernel threads. There are hooks to allow the user to specify how many
| processors should be used. There used to be white papers on this
| design but I just looked on sun.com and didn't find them.
SGI does something similar. From <URL:http://techpubs.sgi.com/library/
dynaweb_bin/ebt-bin/0650/nph-infosrch.cgi/infosrchtpl/SGI_Developer/
OrOn2_PfTune/@ebt-link;he=0?target=%25N%15_10657_START_RESTART_N%25;
DwebQuery=threads>, we see that we *used* to do "m-on-n" scheduling
(as above), but now[*] do the multi-CPU dispatching entirely in user mode:
C Source Using POSIX Threads
...
You can write a multithreaded program using the POSIX threads model
and POSIX synchronization primitives (POSIX standards 1003.1b,
threads, and 1003.1c, realtime facilities). The use of these
libraries is documented in Topics in IRIX Programming, listed
in the section "Software Tool Manuals".
Through IRIX 6.4, the implementation of POSIX threads creates a
certain number of IRIX processes and uses them to execute the
pthreads. Typically the library creates fewer processes than the
program creates pthreads (called an "m-on-n" implementation).
You cannot control or predict which process will execute the code
of any pthread at any time. When a pthread blocks, the process
running it looks for another pthread to run.
[*]==> Starting with IRIX 6.5, the pthreads library allocates a varying
number of execution resources (basically, CPUs) and dispatches them
to the runnable threads. These execution resources are allocated
and dispatched entirely in the user process space, and do not
require the creation of UNIX processes. As a result, pthread
dispatching is more efficient.
The "Topics in IRIX Programming" document mentioned can be found at
<URL:http://techpubs.sgi.com/library/dynaweb_bin/ebt-bin/0650/
nph-infosrch.cgi/infosrchtpl/SGI_Developer/T_IRIX_Prog/
@InfoSearch__BookTextView/4>.
Look particularly at "Part Four: Models of Parallel Computation",
"Chapter 13, "Thread-Level Parallelism". Table 13-1 in that section
provides a fairly extensive comparison of POSIX threads, "Lightweight
Processes" [such as Irix's "sproc()"], and traditional Unix processes.