Did anybody have any idea how to implement _lightweight process_
efficiently in Common Lisp? Just like the model adopted in Erlang.
IMHO, it cannot be implemented efficiently in CL because:
1) Process switching is very cheap only if it is supported by compiler
because actually it only need to change the pointer of the program
stack and the cpu context.
2) Bacause of no first-class continuations nor compiler support of LWP,
It's impossible to do scheduling for time sharing (it cannot interrupt
the processes). The consequence is we have to write in coroutine style
and make sure every execution doesn't take up too many cpu cycles, just
an implicit way of event programming. ( btw, coroutine is the right
model of cooperative thread)
3) Even with full continuations, the cost is still much more expensive
in context switching because at every time of switching, we need to
capture the continuations, it's a heavy operation.(I think
non-reentrant/on-shot continuations could be implemented efficiently)
So, common lisp would never achieve the performance and convenience of
Erlang-like multiprocessing unless the compiler provides the thread
model.
Am I right? I think lightweight process is handy not only in network
apps but also in simulation where I can create and simulate every
single entity in a very straightforward way.
I'd really appreciate your help for giving me a solution or pointing
out where I was wrong.
I want to add something:
Now almost every Common Lisp implementation emphasis on support of OS
level thread. I really hope they could also provide a Erlang-like
user-level lightweight process model. I don't know if it would
conflict, would it?
Pebblestone wrote:
> Did anybody have any idea how to implement _lightweight process_
> efficiently in Common Lisp? Just like the model adopted in Erlang.
> IMHO, it cannot be implemented efficiently in CL because:
That's a really bizarre way to phrase a question.
> 1) Process switching is very cheap only if it is supported by compiler
> because actually it only need to change the pointer of the program
> stack and the cpu context.
A great part of the cost of a process switch is simply the cache
misses, nowadays.
> 2) Bacause of no first-class continuations nor compiler support of LWP,
> It's impossible to do scheduling for time sharing (it cannot interrupt
> the processes). The consequence is we have to write in coroutine style
> and make sure every execution doesn't take up too many cpu cycles, just
> an implicit way of event programming. ( btw, coroutine is the right
> model of cooperative thread)
It is possible to implement first-class continuations transparently
(except for the capture of untransformed activation records) in
portable CL. Whether it is a good idea is definitely debatable. I have
done so, and I'm really not convinced that the ability to capture any
activation record is a good thing to have to design around. In a
similar vein, I really don't think that we should try to emulate the
preemptiveness of OS processes in micro threads. Preemption means we
have to deal with locks (more so, in any case), atomic sections, etc.
We're only sharing time with our own code anyway, so we can make sure
it's well-behaved.
I'm beginning to think that a system where you basically have a control
flow mini-language that calls out to normal CL functions to do the work
will end up working much better: simpler, easier to analyse, and the
cost is explicitly only borne by the portions of the code that use the
mini-language. Moreover, we can interpret the programmer's use of the
mini-language as a hint that its features will be used and optimise for
the capture of continuations, etc.
> 3) Even with full continuations, the cost is still much more expensive
> in context switching because at every time of switching, we need to
> capture the continuations, it's a heavy operation.(I think
> non-reentrant/on-shot continuations could be implemented efficiently)
The design space for continuations is quite large, and they can be
optimised for frequent capture and/or recapture. I didn't particularly
pay attention to the cost of capture (though I did optimise recapture),
and in fact optimised the system for the case when no continuation is
captured, and it still does 40-45k switches/sec on my P-M 1.6 GHz
(SBCL). Note that this is a "best case" figure, since there was
basically only 1 activation record to (re)capture and reinstate.
However, in the real world, you'd probably want to use smarter
scheduling and be able to actually do some work. The switching rate
then becomes much less important. Also, keep in mind that, if you want
thread migration, you pretty much have to support full continuations,
since serialisation+unserialisation produces a copy of the
continuation.
> So, common lisp would never achieve the performance and convenience of
> Erlang-like multiprocessing unless the compiler provides the thread
> model.
> Am I right?
No, since your premises are wrong.
> I think lightweight process is handy not only in network
> apps but also in simulation where I can create and simulate every
> single entity in a very straightforward way.
That depends on how much and what kind of state you need to keep in
your simulated entity. I'm sure Kenny Tilton can come and plug Cells
here.
Paul Khuong
From: Ken Tilton
Subject: Re: Could CL achieve the performance of Erlang's multiprocessing model?
Date:
Message-ID: <yRsNg.1043$W02.1022@newsfe08.lga>
·······@gmail.com wrote:
> That depends on how much and what kind of state you need to keep in
> your simulated entity. I'm sure Kenny Tilton can come and plug Cells
> here.
Oh, no, forget Cells. I have. Ephemeral Cells, lazy cells, synapses --
turned into real mess. Just didn't scale past certain trivial
applications that are easy enough to handle with good ol' vanilla CL.
kt
--
Cells: http://common-lisp.net/project/cells/
"I'll say I'm losing my grip, and it feels terrific."
-- Smiling husband to scowling wife, New Yorker cartoon
> Oh, no, forget Cells. I have. Ephemeral Cells, lazy cells, synapses --
> turned into real mess. Just didn't scale past certain trivial
> applications that are easy enough to handle with good ol' vanilla CL.
>
> kt
Really? Or is this some type of crazy reverse advertisement?
From: Ken Tilton
Subject: Re: Could CL achieve the performance of Erlang's multiprocessing model?
Date:
Message-ID: <EhqOg.354$%W2.195@newsfe10.lga>
········@gmail.com wrote:
>>Oh, no, forget Cells. I have. Ephemeral Cells, lazy cells, synapses --
>>turned into real mess. Just didn't scale past certain trivial
>>applications that are easy enough to handle with good ol' vanilla CL.
>>
>>kt
>
>
> Really? Or is this some type of crazy reverse advertisement?
>
<g> I do not think there is any need for reverse advertisement based on
the popularity (not!) of the library. PyCells does not seem to be doing
any better.
I knew the game was up when I tried solving a problem with "integrity
bubbles". :)
ken
--
Cells: http://common-lisp.net/project/cells/
"I'll say I'm losing my grip, and it feels terrific."
-- Smiling husband to scowling wife, New Yorker cartoon
From: Wade Humeniuk
Subject: Re: Could CL achieve the performance of Erlang's multiprocessing model?
Date:
Message-ID: <nyqNg.3809$bf5.3534@edtnps90>
Pebblestone wrote:
> Did anybody have any idea how to implement _lightweight process_
> efficiently in Common Lisp? Just like the model adopted in Erlang.
> IMHO, it cannot be implemented efficiently in CL because:
>
What is the performance of Erlang's MP Model?? I am not sure
what that means, you would have to have two large systems implementing
a non-trivial application to compare the two. After all in a real system
most time is spent in actually performing logic, not switching process
contexts.
Anyways... Here is link, write some code to test it out and get back to
us with the results.
http://www.mu.dk/cl-muproc
Wade
Wade Humeniuk wrote:
> Pebblestone wrote:
> > Did anybody have any idea how to implement _lightweight process_
> > efficiently in Common Lisp? Just like the model adopted in Erlang.
> > IMHO, it cannot be implemented efficiently in CL because:
>
> What is the performance of Erlang's MP Model?? I am not sure
> what that means, you would have to have two large systems implementing
> a non-trivial application to compare the two. After all in a real system
> most time is spent in actually performing logic, not switching process
> contexts.
>
> Anyways... Here is link, write some code to test it out and get back to
> us with the results.
>
> http://www.mu.dk/cl-muproc
I recall that in Klaus Harbo's talk in Hamburg that he pointed out that
cl-muproc does not have the performance of Erlang. That is, it does not
have the goal of supporting the large number of processes that you
expect from full blown concurrency-oriented programming, if you look at
the "muproc non-goals" slide:
http://www.mu.dk/cl-muproc/htdocs/eclm2006--cl-muproc--Klaus-Harbo.pdf
Asking a question on (say) the muproc mailing list may garner more
answers than writing some benchmark.
Tayssir
From: John Thingstad
Subject: Re: Could CL achieve the performance of Erlang's multiprocessing model?
Date:
Message-ID: <op.tfr72wo9pqzri1@pandora.upc.no>
On Tue, 12 Sep 2006 04:31:00 +0200, Pebblestone <··········@gmail.com>
wrote:
> Did anybody have any idea how to implement _lightweight process_
> efficiently in Common Lisp? Just like the model adopted in Erlang.
> IMHO, it cannot be implemented efficiently in CL because:
>
> 1) Process switching is very cheap only if it is supported by compiler
> because actually it only need to change the pointer of the program
> stack and the cpu context.
>
> 2) Bacause of no first-class continuations nor compiler support of LWP,
> It's impossible to do scheduling for time sharing (it cannot interrupt
> the processes). The consequence is we have to write in coroutine style
> and make sure every execution doesn't take up too many cpu cycles, just
> an implicit way of event programming. ( btw, coroutine is the right
> model of cooperative thread)
>
> 3) Even with full continuations, the cost is still much more expensive
> in context switching because at every time of switching, we need to
> capture the continuations, it's a heavy operation.(I think
> non-reentrant/on-shot continuations could be implemented efficiently)
>
> So, common lisp would never achieve the performance and convenience of
> Erlang-like multiprocessing unless the compiler provides the thread
> model.
>
> Am I right? I think lightweight process is handy not only in network
> apps but also in simulation where I can create and simulate every
> single entity in a very straightforward way.
>
>
> I'd really appreciate your help for giving me a solution or pointing
> out where I was wrong.
>
Rodger Corman had a lecture on how he implemented
threading in Corman Lisp.
Here is a URL to the powerpoint slides.
www.cormanlisp.com/Multi-threaded%20Lisp.ppt
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
Pebblestone wrote:
> Did anybody have any idea how to implement _lightweight process_
> efficiently in Common Lisp? Just like the model adopted in Erlang.
> IMHO, it cannot be implemented efficiently in CL because:
>
> 1) Process switching is very cheap only if it is supported by compiler
> because actually it only need to change the pointer of the program
> stack and the cpu context.
No - processes are in separate address spaces or at least subject to
different memory access restrictions, independent of language.
Threading (same address space, different flow of control) can be
implemented by changing the PC and register state (which includes
the stack pointer, if any), but that doesn't require compiler help, as
our C/C++ friends have shown.
In particular, threading doesn't require continuation capture or any
of that. Passing continuations from one thread to another doesn't need
much more support than making them multi-use. However, "passing"
may require synch not unlike that often required when using other
shared data structures. I don't know if said synch can be auto
generated, but if it is, the auto-gen is associated with the passing,
or rather, usage, not thread switch, because passing can occur
without thread switch. (Remember, multi-cpu systems may run
multiple threads concurrently.)
User-threads may require compiler help, but OS threads may not.
(Yes, OS threads complicate GC and the compiler can reduce some
of that complication.) Note that OS threads are typically preemptive.
However, if you want Erlang, you're not going to find it in Lisp.
Pebblestone wrote:
> Did anybody have any idea how to implement _lightweight process_
> efficiently in Common Lisp? Just like the model adopted in Erlang.
> IMHO, it cannot be implemented efficiently in CL because:
Oh, I should point out that you may want to take a look at Erlisp,
perhaps speak with the mailing list or whatever avenues of
communication they have...
http://www.dirkgerrits.com/programming/erlisp/
I suspect the project isn't going forward at the moment, but they have
thought about the questions you wish to answer.
Tayssir