[Stackless] micro-threads & co-routines

Christian Tismer tismer at appliedbiometrics.com
Wed Oct 11 16:42:39 CEST 2000


Just van Rossum wrote:
> 
> At 2:05 PM +0300 11-10-2000, Christian Tismer wrote:
> >You're wlecome. It was overdue. I hope it also fixes
> >all of the MAC leaks which I couldn't reproduce.
> 
> Sure does, thanks. I hope it also fixes the leaks that Mike experienced.

I don't think so. It sounds like a completely different
matter. Some extension must break something.

> >> co-routines:
> >> - In the coro list (at egroups) I've proposed a co-routine API
> >>   and have presented an implementation of it. I think it's fairly
> >>   solid (apart from some continuation compatibility issues that
> >>   only Chris understands..). Is it an idea to include it with
> >>   the stackless distro? (It happens to be included in the Mac
> >>   binary, as that's simply my working copy...)
> >
> >I think this API will be the right thing (with tiny changes)
> 
> Like what? (API-wise, of course.)

I think access to frames to be scheduled should go through
tiny access functions (or macroes), since this is a write
access. But give me more time, please.

...
> >In a former message on this list, you mentioned that
> >continuations are way too powerful for coroutines.
> >This is not true (or will loose today's truth, soon:).
> 
> I hope you're right ;-) One thing that will have to change (and that's
> largely a matter for the continuation API) is that cyclic references should
> be easier to avoid. The current continuation API makes this incredibly hard
> due to too much smartness. (But that's a whole nother discussion we've
> mostly already had...)

Hmm no. The smartness was in fact there to avoid cyclic
references as much as possible.
If you want continuations, then you are somehow going to touch
your own running program, and that is always related to creating
cycles. This will be a much smaller problem due to Neil's GC,
but in principle it is there.
The way to avoid this is to avoid pure continuations, but to wrap
them into helper objects which know how to destruct properly.
This will yield simpler objects like coroutines.

In fact, this is a different problem, since I was talking of
simplifying the implementation of the stackless core.

> [ snipped the rest ]
> I worry about the length of your explanation: if it's not easy to explain,
> it might not be such a good idea. I still don't see a compelling reason to
> introduce yet another ownership mechanism: why not use the standard
> refcounting mechanism? In our private discussion I showed you how this
> could work, even in an exception context. I strongly feel that introducing
> another ownership rule causes more trouble than it solves.

I included the current status partially, and I developed the
idea while writing. Maybe it became too long.
Also maybe that the topic is complicated and needs a longer
explanation, whatever you do to it.

Refcounting: Sorry, I couldn't find your reference in that 60 or more
messages long thread, but I'm sure that you didn't convince me.
Version 1.1 solely used reference counting, and that caused
the one or the other trouble.
The current 1.2 system doesn't use the normal reference counting,
but uses its own, via f_referers. That produces less trouble,
especially for tracebacks.

But: I'm not interested to know how many referers there are, just
if it is more than one. But then it is equivalent to just store
the owner. This gives the advantage that we know *who* is the
owner, and we can ask the owner if certain things are allowed.

Advantage: We can use this ownership directly to link tracebacks,
and we don't need any recursion or to turn the chain upside
down. Just traverse it.

Advantage: In interpreter recursions, we don't need to keep
an extra flag to keep track of blocked frames (which wait
for an interpreter to finish). Instead, their f_owner field
points to its dispatcher object, and this object will both
reject to give us write access or to obtain a copy but raise
an exception. All this hair is currently solved in the
continuationmodule, although it doesn't belong there.

Advantage: Assigning ownership doesn't take longer than
the current extra refcounting, but forces me to exactly
define what ownership means, which gives more clarity.

Advantage: Debugging becomes very much easier, since I
don't have to worry about reference counts any longer.
Instead I can track down what the current owner is and
see it in the debugger.

---

Reference counting isn't specific enough. It works, but
not good, as I have convinced myself for many times now.
he working assumption was that if somebody is pointing
to my frame, he will perhaps want to run the frame, and
I must make a copy. This works, but is oversized.
Handling this all via callbacks works, but is ugly.
Instead, ceval will explicitly look if a frame has the
expected owner, and if not, it will explicitly take
the necessary step to continue.

Theoretical considerations are fine to some extent, but
I have been through this, under the pressure to make some
really difficult stuff work. And although I had many ideas
which looked easy to implement, they were not when I actually
tried it. So my only way to find out was to implement it.
If I now have the feeling that explicit ownership is better
than just refcounting, this comes from experience. You can of
course convince me, by implemeting your refcount based idea.
If it does stand the requirement to support first class
continuations under all circumstances *and* does not make
any unnecessary copy *and* is easy to understand, then you
win and I will give you a free meal. :-)

I'm not able to judge in advance what is better, so I will
have to try it. Can be done right now, without implementing
the frame split.

---

Short conclusion of coroutines, ownership and continuations:

a)
If you want a continuation, then you want a frozen program
state. You become the owner, unless the frame is actually
running (owned by the evaluator), then you get a copy.
If the frame is later run by someone else but you, he
will make a copy.

b)
If you want a coroutine or an uthread, then you want a handle
to a program state. You can get this handle. You are not
the owner of coro1 but the ceval instance. But you own coro2.
Transferring from coro1 to coro2 means internally:
Ownerships of coro1 and coro2 are simply swapped.

At the moment we are emulating b) by means of a). That gives
transitional states where it is hard to avoid ownership trouble.

But the distinction between a) and b) simply nails down to
an ownership issue and who does when a copy. In a), we enforce
ownership, and the next owner (ceval when it comes back to that
frame) has to create a copy. We keep the frozen state.
In b), we do not intend to get a copy, and there will not happen
such a thing, unless some other continuation enforces it.

>From a coroutine point of view, this is exactly as efficient
as your plain implementation, but it is also completely
continuation safe.

Maybe this was lengthy again. But this is all about continuations,
full story, solves everything. Under that aspect it is short.

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
14163 Berlin                 :     PGP key -> http://wwwkeys.pgp.net
PGP Fingerprint       E182 71C7 1A9D 66E9 9D15  D3CC D4D7 93E2 1FAE F6DF
     where do you want to jump today?   http://www.stackless.com



More information about the Stackless mailing list