[Stackless] What is stackless now?

Christian Tismer tismer at stackless.com
Fri Aug 19 02:16:34 CEST 2005

Grant McDonald wrote:

> Chris,
>  > And that is what just happens, and why I'm in the PyPy
>  > project. Actually, PyPy was my answer to the problems
>  > to make Python Stackless:
> So this is definitely one of the goals of PyPy? To allow
> such a transformation to occur to a python (not CPython)?

Yes, PyPy's goals include the ability to have many different
implementations and paradigms in one source tree.
For instance one example that is hardly possible with CPython:

All our object access has some kind of abstraction, that makes
details like refcounting invisible to the implementation.
Objects are simply accessed as in Python, and it is up to the
backend to decide how to render the code for that.
At the moment, we did refcounting, but really only in the
lowest end of the code generator. A different code generator
could employ garbage collection or even a different scheme.

The same holds for Stackless. The big difference to Stackless
Python is:
In Stackless, I had to obey many rules. I needed to stay
absolutely compatible to the C API, *and* to the C calling
conventions. I also didn't want to change all too much of
the source code, which is still way too much.

That had several effects:
For one, the result is somewhat limited, and I have a
compromize implementation which uses hybrid hardware switching
where I can't do better, and collaborative switching where
All this effort is very visible in the C code, and a PITA
to implement. One of Stackless' efforts is to provide the users
with nice parallel processing while writing in a naive style
of tiny looping engines and to protect him from the hassles
of state engines, thread locks and reactive patterns.
Stackless itself suffers quite much from this and has to
to this all over the place, and some more things, scattered
across the C source.

In PyPy, we can co a completely different (I'd say "the right")
way: We do no direct Stackless specific code at all, only in the
code generator, with a few help functions and creating slightly
different structures.

There is not that much to do to get rid of the stack, if you
are completely in charge. We can play with different strategies
and find what the most efficient solution is.
The rest of the implementation is automatically completely
collaborative, since it doesn't see that at all.
In a sense, our source code is intelligent, not just literal.
The compilation process itself is completely written in Python,
again completely under our control how we want to express what.

And all and every function can be stackless, to whatever level
it makes sense. This will not only be in Python frames, the
major Stackless domain, but also in builtin modules like
marshal. This is a typical example of stuff written in a
recursive manner in C, which suffers from the C stack limit.
I rewrote it in RPython, a Python subset that we currently
can translate into efficient code, and actually the
implementation got nice and readable.
I was tempted to rewrite this in a Stackless manner, but my
examples became quite tedious and lengthy, and I saw myself
getting back into some of the problems which I have in Stackless.
Then I decided to defer this, because we can generate
the necessary non-recursive code for everything, in a much
more general way, and without spoiling the source code.

The general idea is to open the C stack to introspection. Well,
just quite, we can do it even simpler and continue to use
the stack as it is without worring about its memory
layout, but we provide a data structure for every stack
frame, where all variables can be saved to and loaded from.

There are lots of other ideas how to implement this.
One very rough idea is to use no stack at all, but implement
everything via data structures. Then a function when called
just creates such a structure and fills its arguments
and a pointer for the code body procedure in.
Every call to a function does this, and we always return to
a central dispatcher which runs the code for these structures.
A little bit like continuation passing.

This is the simplest possible way, but it also guarantees
the worst performance. Instead of that, I am crafting a proposal
which is much nicer:

We do have recursive functions exactly like now, but in
addition we add the structures from above and allow the system
to unwind the stack into these structures just on demand.
This keeps alloptimization like local variables intact most
of the time, and we only collapse the stack if we get too
deep of we want to switch tasks.

As you might see: I have learned that stacks *do* have some
advantages, because they allow for some locality, and the
hardware has of course good support for it, so why not use it.
But we don't pay for this to always have to depend on this
stack, we just build a feature that forces every stack frame
to save its state and a function pointer and just go away.
Then we have the system in a state where we can easily switch
threads (tasklets) or restore execution state from pickles,
then continuing to run stack frames until some interruption
tells us to unwind.

And the nice thing: Again we don't need to think of this at all
in the interpreter (well, a tiny bit) or the library functions.
It all depends on what kind of code and structures we generate.

The big advantage is:
- we can adopt different, configurable strategies
- we can make Stackless a user option
- we can do this all with no change to most of the implementation

What remains from Stackless is just the functionality, which will
go into an almost regular module, maybe even a pure Python module,
when we at some time can make this fast, too. And there can
be different designs as well. It is easy to play with this,
because we have the completely collaborative system, which we
define by ourselves.

> What is the current state of implementation?

We have a self-contained, stand-alone PyPy which does not need
CPython any longer. It is huge, buggy, slow, but it works.
This is really really fun!

On Sunday, I'm going to the Heidelberg sprint, where we will
be working on a new release that includes this ability
to create a binary.

>  > That's it. Will take a few more years to become perfect.
>  > Until then, I need to finda way to keep Stackless alive.
>  > I'm happy that I seem to get help!
> So how deep is the integration of stackless' ideas into
> PyPy?

The integration is incredibly deep and not in there at the same
time. The idea is to allow to have it, but also to allow to
go without it. Sure, many people will want it, because it
allows several things to implement very efficiently. And things
like generators and friends would in fact become simpler to
implement right now.
But the current idea is to be as independent from any concept
as at all possible.
The idea of PyPy is to get rid of early design decisions.
This makes PyPy so abstract, complicated, and powerful.

> On a slightly unrelated note have you seen PEP-342? It
> looks like they gave into a coroutine implementation
> after all. I'm looking forward to playing around with it :)

It is the finaly say on CPython's stackless-ness. More is not
possible. It is nice to yield data into a generator, which still
keeps it as a limited coroutine. Things are unbalanced. This
may be fine for many application, and I see a major domain
of stackless vanish here: It is very possible to implement
nice asynchronous communication just with yield expressions.
But here the story ends. You cannot do more than this if
the C stack dictates order of execution.
Generators give you freedom by allowing to switch to any
generator. But as soon as they are activated, there is no
way but unwinding the stack if you want to do something else.
Generators calling each other are stack bound as any other
functions. As soon as things go deeper than one stack level,
you are either back at the old save/restore nighmares when
you try to emulate parallelism, or you need Stackless,
which is nothing else as an automation of this nightmare
as your service.

And even this nightmare PyPy is going to make elegant.

Thanks for your questions, I can use this in a book chapter that
I have to finish this weekend. :-)

ciao - chris
Christian Tismer             :^)   <mailto:tismer at stackless.com>
tismerysoft GmbH             :     Have a break! Take a ride on Python's
Johannes-Niemeyer-Weg 9A     :    *Starship* http://starship.python.net/
14109 Berlin                 :     PGP key -> http://wwwkeys.pgp.net/
work +49 30 802 86 56  mobile +49 173 24 18 776  fax +49 30 80 90 57 05
PGP 0x57F3BF04       9064 F4E1 D754 C2FF 1619  305B C09C 5A3B 57F3 BF04
      whom do you want to sponsor today?   http://www.stackless.com/

Stackless mailing list
Stackless at stackless.com

More information about the Stackless mailing list