[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: let-fluid problem

This page is part of the web mail archives of SRFI 15 from before July 7th, 2015. The new archives for SRFI 15 contain all messages, not just those from before July 7th, 2015.



(Second followup, different subtopic)

Olin writes (in an earlier message, sorry for lengthy quote):

>I would like to argue against any DYNAMIC-WIND + SET! sort of
>"fluid variable" system. The problem is threads. If you have a
>thread model, then any thread switch involves unwinding up the
>stack to the common ancestor continuation, then winding down into
>the activated continuation. This seems unacceptably expensive; thread
>switch should be a low-overhead operation.
>
>Because of this issue, I strongly prefer making fluid variables
>a primitive construct. Scheme48's system is a pretty canonical example
>of this genre. "Fluid variables" are data structures. So you have the
>following primitive procedures:
>   (MAKE-FLUID value) -> fluid
>   (LET-FLUID fluid value thunk)
>   (LET-FLUIDS fluid1 value1 ... fluidn valuen thunk)
>   (FLUID fluid) -> value
>   (SET-FLUID! fluid value)
>There are no primitive syntax forms. This design is not unique to S48;
>I believe it was proposed by someone other than Kelsey & Rees, and
>is used elsewhere (but I can't recall who or where).
>
>Fluid values are cells that have dynamic scope, as provided by LET-FLUID.
>You typically bind them to global vars, e.g.
>    (define $cwd (make-fluid #f))
>    (define (with-cwd dir thunk) (let-fluid $cwd dir thunk))
>Throwing in or out of LET-FLUID scope does the right thing, as you'd want.
>
>Single-threaded implementations can provide fluids using DYNAMIC-WIND,
>*but* multithreaded implementatins can implement fluids using deep
>binding techniques, providing fast thread switch. This is not possible
>with a system that actually effects variables.

Remarkably, it _is_ possible.

The specification only says that valuables are stored in the dynamically
bound variables, but specifies nothing about the mechanism.  All we need
is a mechanism that (a) allows code inside the scope of the FLUID-LET to
get and set the dynamically bound values, (b) allows code outside the
scope of a FLUID-LET to get and set the original value, and (c) gets rid
of the unwind/wind problem.

For the sake of argument, take the case where the dynamically bound
variable is a global.  In Larceny, a global has a single value slot, and
reading a global is implemented using the following code sequence:

get() =
	get constant-vector from procedure
	get global-cell from constant-vector
	get global-cell.value
	if value is #!undefined, then TRAP
	return value

and writing a global is implemented using the following sequence:

store(object) =
	get constant-vector from procedure
	get global-cell from constant-vector
	store object in global-cell.value

This mechanism can be changed as follows.  The idea is to use the
undefined-checking as a fast check for fluidness and handle dynamically
bound variables out-of-line.  

A global cell is given a second value word, whose initial value is #f.
If its value is #f then the global is not dynamically bound by any part
of the program; if its value is #t, then some part of the program has a
FLUID-LET in effect on the variable.

The code for reading the global is modified as follows:

	[get cell as before]
	get global-cell.value1
	if value1 is #!undefined, then			[ fluid or undefined ]
		get global-cell.value2
		if value2 is #f, then 
			TRAP				[ undefined variable ]
		return lookup-fluid(global-cell)	[ fluid ]
	else return value1				[ normal ]

The code for writing the global is modified as follows:

	[get cell as before]
	get global-cell.value1
	if value1 is #!undefined, then			[ maybe fluid? ]
		get global-cell.value2
		if value2 is #f, then			[ undefined ]
			store object in global-cell.value1
		else					[ fluid ]
			store-fluid(global-cell,object)
	else store object in global-cell.value1

The functions lookup-fluid and store-fluid can use whatever storage
mechanism they like to map variables to values (notably thread-local
storage and deep binding).  

One piece remains: FLUID-LET would do something like this on entry:

	if global is already dynamically bound then
		save current value 
		store new value for lookup-fluid to find
	else
		save current value for lookup-fluid to find; this is
			the value outside any FLUID-LET
		set global.value1 to #!undefined
		set global.value2 to #t
		store new value for lookup-fluid to find

and the opposite on exit, except that it takes a little effort to make
sure that the last thread to undo a fluid binding on the global restores
the global to a "normal" value.

The cost to code that reads globals is 0 for globals that are not
dynamically bound, and a call-out of some sort for globals that are
dynamically bound.  The cost in code size is effectively 0 because the
code that checks value2 can be moved into the trap handler.

The cost to code that writes globals is a compare and statically
predictable branch for globals that are not dynamically bound, and in
addition a call-out for globals that are dynamically bound.

The space cost is one _bit_ per global, which in some implementations
will probably need to be rounded up to one or two words.

In addition, the mechanism requires that global-variable checking is
never turned off in programs that use fluid variables implemented
with this technique.

For lexically scoped variables (I find I use fluid-let with these more
than with globals) the problem is a little thornier because they are not
usually checked for definedness; however, if FLUID-LET is known to the
compiler then the compiler can insert the necessary checks on access
to variables that are fluidly bound in the lexical scope.

(For multiprocessors -- well, I don't know.  I didn't say I was
advocating this implementation, only that the SRFI-15 spec does not
necessarily imply the unwind/wind cost on a thread switch.)

--lars