From luke at stat.uiowa.edu  Wed Apr  9 13:39:33 2008
From: luke at stat.uiowa.edu (Luke Tierney)
Date: Wed, 9 Apr 2008 06:39:33 -0500 (CDT)
Subject: [Rd] R-uthreads?
In-Reply-To: <20080403143638.GA54892@piskorski.com>
References: <Pine.LNX.4.64.0804021147170.17620@nokomis.stat.uiowa.edu>
	<20080403143638.GA54892@piskorski.com>
Message-ID: <Pine.LNX.4.64.0804090639060.20292@itasca2.wildberry.org>

On Thu, 3 Apr 2008, Andrew Piskorski wrote:

> On Wed, Apr 02, 2008 at 11:58:34AM -0500, Luke Tierney wrote:
>> Subject: Re: [Rd] callCC in 2.7.0
>
>> Some of us worked on something along these lines a while back in a
>> branch called R-uthreads, but the cost of converting to that
>> approach and the overhead of maintaining it seemed too high for the
>> benefit, at least at the time.
>
> Luke, could you say a bit more about R-uthreads, what your ideas,
> goals, and conclusions there were?
>
> I see the old R-uthreads branch in svn (looks like it was based on R
> 1.4 back in Aug. 2001), but I couldn't find any summary discussion,
> and I can't tell much just from looking at "src/main/uthreads.c".
>

The primary objective was to provide user-level threads to help
expressing concurrent computations, including some concurrent
things already happening in R (running finalizers in gc, aspects
of guis).  The infrastructure would also be able to support
one-shot (and maybe more general) continuations, generators,
coroutines, and the like.

The design was based on the same ideas as the stackless python
project at the time, and maybe also the Concurrent Haskell
project -- moving stuff that is currently on the C stack into
data structures allocated on the R heap and arranging for
computations to be done from a single eval call rather than a set
of nested eval calls. That way it is easy to suspend the state of
the current computation so it can be resumed later.  The
uthreads.c file only contains the interface for threading, as I
recall -- the major work is in the other files, like eval.  The
implementation was complete enough to run some very simple
threading examples, though I don't seem to have any code examples
handy.

The effort needed to make this work is fairly high. Some was done
fairly completely (moving contexts into the R heap for example),
but changing functions that use nested eval calls into ones that
do some processing and return a deferred version of the next task
to a top-level eval was only partially done as I recall.  (I also
don't think we dealt with the issue of serializing
continuations.)  Doing this would have been a lot of work, as
would convincing everyone who needed to be convinced that this
was a good idea and needed to be maintained.  In addition, there
are some things, like optim's callbacks for example, that really
are not suitable for this kind of rewriting.  This isn't
necessarily fatal -- in the threading context it would just mean
that no context switches can occur while within such a callback,
but it makes things messy.

The basic approach may still be viable, and it has the benefit of
being fully portable, unlike stack copying tricks. But given
other things that needed to be done at the time, the need for
fairly pervasive changes as well as a change in the way of
thinking about R internals, the benefits of continuing down this
route at the time didn't seem to outweigh the costs.

Best,

luke

-- 
Luke Tierney
Chair, Statistics and Actuarial Science
Ralph E. Wareham Professor of Mathematical Sciences
University of Iowa                  Phone:             319-335-3386
Department of Statistics and        Fax:               319-335-3017
    Actuarial Science
241 Schaeffer Hall                  email:      luke at stat.uiowa.edu
Iowa City, IA 52242                 WWW:  http://www.stat.uiowa.edu



[Rd] R-uthreads?
Luke Tierney