Fake threads (was [Python-Dev] ActiveState & fork & Perl)

[Tim Peters]

Just so Guido doesn't feel like the quesion is being ignored <wink>:

> ...
> How does Scheme do this? [continuations]

One more reference here.  Previously sketched Wilson's simple heap
implementation and Dybvig's simple stack one.  They're easy to understand,
but are (heap) slow all the time, or (stack) fast most of the time but
horribly slow in some cases.

For the other extreme end of things, check out:

    Representing Control in the Presence of First-Class Continuations
    Robert Hieb, R. Kent Dybvig, and Carl Bruggeman
    PLDI, June 1990
    http://www.cs.indiana.edu/~dyb/papers/stack.ps

In part:

    In this paper we show how stacks can be used to implement activation
    records in a way that is compatible with continuation operations,
    multiple control threads, and deep recursion. Our approach allows
    a small upper bound to be placed on the cost of continuation operations
    and stack overflow and underflow recovery. ... ordinary procedure calls
    and returns are not adversely affected. ... One important feature of
    our method is that the stack is not copied when a continuation is
    captured. Consequently, capturing a continuation is very efficient,
    and objects that are known to have dynamic extent can be stack­
    allocated and modified since they remain in the locations in which
    they were originally allocated. By copying only a small portion of the
    stack when a continuation is reinstated, reinstatement costs are
    bounded by a small constant.

The basic gimmick is a segmented stack, where large segments are
heap-allocated and each contains multiple contiguous frames (across their
code base, only 1% of frames exceeded 30 machine words).  But this is a
complicated approach, best suited for industrial-strength native-code
compilers (speed at any cost -- the authors go thru hell to save an add
here, a pointer store there, etc).

At least at the time the paper was written, it was the approach implemented
by Dybvig's Chez Scheme (a commercial native-code Scheme compiler noted for
high speed).

Given that Python allocates frames from the heap, I doubt there's a much
faster approach than the one Christian has crafted out of his own sweat and
blood!  It's worth a paper of its own.

or-at-least-two-hugs<wink>-ly y'rs  - tim