Re: Threads and asyncs

[Lynn Winebarger]

On Wednesday 04 September 2002 21:38, Tom Lord wrote:
>       > The problem with this is that it requires really fast garbage 
> collection.
> Again -- I'll point at the substantial (from vague recollection: 20%?)
> speedup SCM got from generationally collecting environments.  The 
> common case pattern of how environments are used makes this a really
> excellent choice.
     I believe the ML community has the most history of needing
fast GC to deal with heap-allocated frames.  Appel has several
papers on SML/NJ's GC and dealing with this design decision.
     I haven't read them, of course, but they seem like the
canonical starting place.

> There's also Stallman's ancient spaghetti-stack approach -- which is
> kinda close to what SCM is doing.

      I'm not familiar with this spaghetti stack.  

>        > Now that I think about it [...]
> 
> you lost me with the rest of that, in case you want to clarify.

       Ok.  Stack based function calling is a particular allocation
strategy for activation records.  It's simple and reasonably quick.
In C,  you don't have grabbable continuations (at least not 
supported by the language), so when the function returns,
the only valid reference to the activation record is dropped,
and that activation record's memory is reclaimed by popping
the stack.  
    In Scheme, you can grab continuations, of course,
so as long as there's an external reference to an activation 
record/continuation, the stack cannot be popped.  However,
the only way such a reference can be (legally) created is
by call/cc.  Unless that is called, we know we are safe
"collecting" that activation record by popping the stack.  On
the other hand if we know there is a possible reference to
a continuation that's higher on the stack, we haven't collected
those frames, so we must freshly allocate new space for
activation records.  Now, you may occasionally create
stacks unnecessarily (e.g. the continuation was used only
for escaping, and there's no other way to get into the
lambda of the (call/cc (lambda (k) ...))); however, we will
never invalidly collect it either.  Instead, the garbage collector
will have the responsibility of seeing when that frame isn't
reachable.  
     In the straightforward, always allocate from the heap
model, the GC is always responsible for collecting activation
records.  In this model, we explicitly handle a very common
case, so the GC doesn't have to.  Otherwise, the GC handles
it, as it would have anyway.  Thus we have strictly improved
the speed (because popping the stack is about the
fastest deallocation anybody will ever have, other than exiting,
of course).
      Better?

>        > Is all the thread hair in SCM as well?
> 
> Grr.  We need a wiki to sort that out.  No, I don't (recall that) it's
> in SCM -- but then I also think Guile is dead-ending in this regard.

    I don't think anybody's found the grail yet.  
   
> Am I misunderstanding the referent of "the two"?   amdhal's law talks
> about the impact of optimizing components on the performance of a
> system that incorporates those components.   Clean APIs can enable
> swappable components.

       Sorry, the last time I heard a reference to Amdhal's law was
in a hardware course three years ago.  I looked it up on FOLDOC
and it gave a definition referring to the maximum speedup 
of parallelization (which is why I didn't see the connection).  I just 
went back to Hennessy and Patterson and they give the right definition.

Lynn