Continuations and threads (was Re: Iterators & generators)

[Christian Tismer]

"Samuel A. Falvo II" wrote:
> 
> In article <evkhGX$e$GA.79 at cpmsnbbsa03>, Tim Peters wrote:
> >The latter are more powerful, but that's not really the attraction.
> >Continuations are both fast and space-efficient compared to threads on most
> >platforms.  Read Christian's paper!  You'll find, e.g., that his simple
> >implementation of generators using continuations ran 3x faster than a simple
> >implementation using threads (& on a platform that does a relatively good

Thanks Tim, yes this is true.

> This is because the operating system  switches threads, not the application.
> At worst case, it does so on an every so often (time-slicing).  At best
> case, it will put a thread to sleep as soon as the OS sees that it can't
> possibly proceed any further without a message or event from another thread.
> 
> Continuations, however, are entirely user-space constructs.  There's no
> user-to-kernel-to-user transitions involved.  So of course they're going to
> be faster when run under such a system.

Until here I agree.

> Now, implement an operating environment that uses continuations natively,
> and you'll find it'll be no faster than using threads.  Why?  Because the
> continuation functions are stuff away in kernel-space (otherwise, they
> wouldn't be "native" to the operating system).

Misconception, sorry. Nobody claimed that they need to be "native" to
the operating system. Instead, they are made native to the environment,
in this case the Python machine.

<snip>

> Because continuations are inherently language specific.  If languages like C
> and its ilk used indirect stack frames (instead of embedded stack frames),
> continuations in C would be more than possible, and threading would be far
> easier.  Billy and I had a discussion on this topic the other day, in fact.

So what? Language specific, or native to operating system?
I'm not sure if we are both talking about the same thing.

...

> Why can't Python's threads package use OS-native threading API, assuming one
> exists?

It does. Threads are good. But for not hardware dependent problems,
mine are smaller and faster.

[Tim]
> >space, while a continuation will usually suck up only a few hundred bytes.
> 
> What is your basis for this conclusion?  An execution context is an
> execution context is an execution context -- the amount of information which
> is required to be stored is going to be roughly equal no matter what.  In
> fact, continuations will consume more space than a pure thread specifically
> because a function's "frame" isn't stored on "the stack."  Thus, something
> somewhere must maintain a reference to it.  Then consider that there can be
> several "continuation objects," where each object stores a branch of the
> frame tree within it.

Well, if you know better... :-)
A continuation in Python is not much more than a frame, below
300 byte, and it can be made smaller.
It does not capture the hardware state, but Python's VM state.
That makes a big difference, since they are always captured in
some defined VM state, in the context of a function call or
between execution of opcodes.
This needs a very small amount of information.
Even a frame is too much in principle, but it was the most
obvious way to implement it.

You may disagree, but while I'm writing this, there is a
Python script in the background, running 1000-2000 continuation
driven small tasks on my notebook. Really :-)

ciao - chris

-- 
Christian Tismer             :^)   <mailto:tismer at appliedbiometrics.com>
Applied Biometrics GmbH      :     Have a break! Take a ride on Python's
Kaunstr. 26                  :    *Starship* http://starship.python.net
12163 Berlin                 :     PGP key -> http://wwwkeys.pgp.net
PGP Fingerprint       E182 71C7 1A9D 66E9 9D15  D3CC D4D7 93E2 1FAE F6DF
     we're tired of banana software - shipped green, ripens at home