Re: stackless implementation (was Re: New stackless proposal)

Mark Hahn wrote:

>>>Does your assembly only work on X86 machines?  I may ask to steal your
>>>assembly code.
>>
>>Sure. Here an excerpt of slp_platformselect.h .

...

> Wow!  I'm impressed.  I thought I'd only be stealing your ideas.  It would
> be great if I could steal your code for Prothon.  Will you let it go under a
> Python type license?

Stackless is under Python license, of course.

> This will let me have C extenstions in all types of threads.  If there is
> anything we can do in Prothon to make your code faster or easier let me
> know.

Well, we have to talk about this.
You just discovered Stackless 2.0, which was hardware
switching, only.

I will show you how I do it.
The trick is to intercept C extension callbacks by counting
something like nested interpreter invocations. I have a variable
named "nesting_level" in every tasklet.
Tasklets at nesting_level 0 are "innocent". They have a nonexistant,
or trivial C stack, that is, even if they might have one which is
not empty, the C stack can be discarded. These tasklets are in a shape
that always allows you to restart them from "toplevel".

Then there are those with a non-zero nesting_level. They contain
C state that has to be restored, at some time, under all circumstances.
I have special treatment for these. For instance, I don't allow any
tasklet with such a C state to simply go away. It *must* be finalized
by a TaskletExit exception, to make sure that it had the chance to
und any C state it had changed.

I even do this cross-real-thread. My code can kill any tasklet, in
this or in any other real thread. This took me months, but it works.

> So, does it just copy the C stack into the Object stack space and pop the C
> stack and vice versa?

Yes, it has a concept of an "initial stub" piece of C stack, which
is squirreled away at every entry into an initial interpreter.
This is also the default initial stack for "innocent" tasklets,
which don't really need C state at all.

My implementation is a bit sub-optimal here, and this is where
you might be interested in the Greenlets, again. Armin made this
solution uch more general. I'm not too much after it, because
my major target is soft-switching (not involving asm hacks).
But finally, he has the most general and efficient solution possible,
although it isn't implemented completely, yet.

Armin is btw. using the same set of assembly include files as
Stackless does. He just provides some different supporting
macroes.
The assembly includes appear to be somewhat of a real optimum;
they have typically about five lines of assembly. It is then
the art to use these in the best way. I am happy to help here.

On the "initial stub" idea: The idea is to use a fixed location
in the stack when the stack is touched first by tasklets.
All further ahrd-switching uses this base address.
Armin proved that this is not necessary, and every hard-switched
tasklet can maintain its own subset of C stack that it controls.
I'm going to implement this for Stackless in the near future.
At the moment, I am more concerned with efficient soft-switching,
because this is almost always more efficient.

Well, we have been talking about "C stack hijacking".
This is, from memory size aspects, most efficient, because
you still have only one real stack.
Many platforms suffer from this stack switching, because all
their prediction registers get invalidated.
Interestingly, the X86 seems to be most efficient here,
because its register layout is already as ridiculously dumb
as possible. Therefore, stack switching can be made *very*
efficient on X86 platforms.

In order to combine the benefit of the X86 dumbness with the
typical situation of just some, say, 100 threads (tasklets),
I'm planning to build a stack pool. The stack pool will try to
cover the most frequently used tasklets in a way, that no two
of these live in the same C stack. This doesn't make sense
for huge numbers of tasklets (100.000 and more), here the
soft-switching, and hard-switching with small chunks to
save work the best.
But for high-performance, repeated tasklets, such a stack pool
could outperform typical things like Python generators *by far*:

Right now, a generator frame gets restarted from start every
time it is invoked. This cannot be made better with the past
Stackless features: The best scenario you can get is one frame
on the stack which calls another frame (the generator).
The caller can stay on the stack, but the callee must be re-invoked
all the time. At it's best, Stackless can try to get to this
performance, by the tricks which I tried to explain before.

But a task switch between two C stacks is almost just changing
the EBP and ESP register, plus some crap to change those bad
globals in the thread state, which Prothon hopefully has
avoided. Here you can really get a speed boost of, say, factor
five. This is a special generator mode I'm planning for:
The yield opcode gets a special mode where it doesn't leave the
frame, having to do the complicated re-incarnation stuff,
but where it simply calls a tiny assembly routine which passes
the value over to a different tasklet with a different C stack.

Summarizing: There is a lot what I have implemented, and there
is a lot more that I would like to implement. Prothon has still
the freedom to pick the best of all world. As you have seen,
there is no "one size fits all" solution.
For myriads of tasklets, you will not preserve a 64K segment for
each, but use the stack hijacking idea.
For threads(tasklets) which you need all the time, it is of
course worth spending the extra space.
And even for soft-switched threads, in situations where there are
very many switches, more than the actual computation, it might
make sense to use C stack switching instead of soft-switching,
because the former can be faster, if no data moves are involved.

And this statement is probably not true cross-platform.
There are platforms where changing the C stack is very expensive.
One of them os Spark. I doubt you will change a Spark stack,
unless you really must. :-))

I'd love to have a couple of hours with you in a pub, with paper.

ciao - chris

-- 
Christian Tismer             :^)   <mailto:[email protected]>
Mission Impossible 5oftware  :     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 89 09 53 34  home +49 30 802 86 56  mobile +49 173 24 18 776
PGP 0x57F3BF04       9064 F4E1 D754 C2FF 1619  305B C09C 5A3B 57F3 BF04
      whom do you want to sponsor today?   http://www.stackless.com/