Dynamic bindings and lightweight processes
Simon Katz
bindings, and was surprised to learn that the dynamic binding of a symbol is
the same as its symbol-value slot. I had a different (and wrong) model along
the following lines:
WRONG
- The top-level special binding of a symbol is the same as its symbol-value
slot.
- Other special bindings are stored on the stack.
- To find the value of a special variable, the most recent binding on the
stack is used.
(I had also assumed that good compilers did something clever to make the
lookup efficient.)
END WRONG
My wrong model simply explains the following behaviour with multiple
(lightweight) processes in LispWorks, which I now find hard to explain!
====
I have two Listener windows, A and B.
In Listener A, I do:
(defvar *x* 8)
In both A and B, *x* now evaluates to 8.
Next, in Listener A, I do:
(let ((*x* 9))
(break))
Within the break in Listener A, *x* now evaluates to 9.
In Listener B, *x* evaluates to 8, as before.
====
My wrong model explains this simply (two stacks), but with my new knowledge
I have to account for the fact that somehow I seem to have two distinct
symbol-value slots for *x*.
What's really going on here? How do other Lisps that support lightweight
processes compare?
Simon.
Tim Bradshaw
> My wrong model explains this simply (two stacks), but with my new knowledge
> I have to account for the fact that somehow I seem to have two distinct
> symbol-value slots for *x*.
I think the wrongness is to assume that SYMBOL-VALUE gets at the `slot
in the symbol', which is something I used to think. In fact it gets
at the current dynamic binding -- there is no portable way to get at
the slot in the symbol -- and indeed there may *be* no distinct symbol
slot, but just a top-level binding.
So I think your model is right, apart from thinking SYMBOL-VALUE does
something other than it does.
--tim
Erik Naggum
| What's really going on here?
the special bindings of a process are re-bound during the context switch.
(however, if you don't _bind_ special variables in such a multiprocessing
environment, only set it, this mechanism is defeated.)
| How do other Lisps that support lightweight processes compare?
they seem to do the same thing all over the place.
#:Erik
Erik Naggum
| I think the wrongness is to assume that SYMBOL-VALUE gets at the `slot in
| the symbol', which is something I used to think. In fact it gets at the
| current dynamic binding -- there is no portable way to get at the slot in
| the symbol -- and indeed there may *be* no distinct symbol slot, but just
| a top-level binding.
if the current dynamic value of a special variable and symbol-value of
the symbol _differ_ (modify one, don't see the difference in the other),
you have a seriously non-conforming implementation, so _the_ portable way
to get at the slot in the symbol cannot be any different than the current
dynamic value. please don't confuse this issue beyond necessity.
there are two ways to do this dynamic binding thing: shallow and deep
binding. shallow binding stuffs the old value away, typically on the
same stack that unwind-protect uses, and stores the new value in the
symbol-value slot. deep binding basically pushes symbols on an alist (or
something very similar) and traverses it to get the current value. in a
multiprocessing setting, there are multiple stacks, and at least one of
them is used to store the process-local value of symbol-value slots of
process-bound special variables.
this is actuall fairly well documented in each of the Common Lisp systems
that support multiprocessing.
#:Erik
Joe Marshall
> I've been following some of the recent discussion here on variables and
> bindings, and was surprised to learn that the dynamic binding of a symbol is
> the same as its symbol-value slot. I had a different (and wrong) model along
> the following lines:
>
> WRONG
> - The top-level special binding of a symbol is the same as its symbol-value
> slot.
> - Other special bindings are stored on the stack.
> - To find the value of a special variable, the most recent binding on the
> stack is used.
> (I had also assumed that good compilers did something clever to make the
> lookup efficient.)
> END WRONG
This is almost the `deep binding' model. The only bug with your model
is that symbol-value would have to scan the stack to find the current
value of a dynamically bound symbol. You *could* implement dynamic
binding this way, but most systems don't.
> What's really going on here? How do other Lisps that support lightweight
> processes compare?
In a multi-threaded `shallow bound' lisp, there is a stack of `old
values' associated with each thread. When you exit a stack, you
squirrel away the current dynamic values and restore the top level
values. When you enter a stack, you save the top level values and
restore the latest dynamic values. So the cost of a thread switch
is proportional to the number of dynamically bound variables.
There is a tradeoff between shallow and deep binding. Shallow binding
makes dynamically bound variables faster at the expense of making
stack switching slower, deep binding makes stack switching faster, but
slows down lookup of dynamic variables.
(History note: On the Lisp machine, the dynamic bindings were kept in
the `special-pdl' (pronounced `special piddle', pdl was short for
`push-down list'. It was a stack that was cdr-coded to appear as a
list.) On a `sequence break' (thread switch), you would `unwind the
special-pdl' of the current thread and `rewind the special-pdl' of the
new thread.)
~jrm
Tim Bradshaw
What I was trying to get at (incoherently) is that there are several
possible implementations, and not all of them involve there actually
being any kind of `slot in the symbol' at all -- there might be just a
top-level alist for instance. It may be that this is confusing the
issue. But this kind of gory detail does matter in multiporocessing
lisps -- for instance shallow binding is a pretty hideous nightmare on
anything that wants to run on a multiprocessor as far as I can see
(because there is no context switch that lets you swap the bindings
around).
--tim
Barry Margolin
>What I was trying to get at (incoherently) is that there are several
>possible implementations, and not all of them involve there actually
>being any kind of `slot in the symbol' at all -- there might be just a
>top-level alist for instance. It may be that this is confusing the
>issue. But this kind of gory detail does matter in multiporocessing
>lisps -- for instance shallow binding is a pretty hideous nightmare on
>anything that wants to run on a multiprocessor as far as I can see
>(because there is no context switch that lets you swap the bindings
>around).
It's important to remember that "slots" are just conceptual notions. How a
slot is implemented is completely unspecified by the language. This is
true for all data types, not just symbols; the slots in a DEFSTRUCT or CLOS
instance don't have to be consecutive locations in memory. For all you
know, they're implemented like OO objects in Perl, as hash tables that key
off the slot name.
Most implementations *don't* do things like this because there are more
efficient ways that are well known. In the case of variable bindings, just
about everyone either using shallow binding (the current dynamic value
lives in a real slot in the symbol object, saved values live on the stack)
or deep binding (dynamic bindings are all in an alist, with new bindings
being pushed onto the front -- a similar technique can be used for lexical
bindings). Shallow binding makes variable access very efficient, but
context switching slow; deep binding makes context switching efficient, but
adds overhead to variable access.
Lisp machines used shallow binding, but I think they also had some hardware
assist for special indirect pointers that reduced the overhead of context
switching.
--
Barry Margolin, bar...@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
Roger Corman
wrote:
>In a multi-threaded `shallow bound' lisp, there is a stack of `old
>values' associated with each thread. When you exit a stack, you
>squirrel away the current dynamic values and restore the top level
>values. When you enter a stack, you save the top level values and
>restore the latest dynamic values. So the cost of a thread switch
>is proportional to the number of dynamically bound variables.
>
>There is a tradeoff between shallow and deep binding. Shallow binding
>makes dynamically bound variables faster at the expense of making
>stack switching slower, deep binding makes stack switching faster, but
>slows down lookup of dynamic variables.
In my view, a proper implementation of threads, or lightweight
processes, doesn't require stack-switching (or thread-switching).
There is no "switch" because all threads and all stacks are active
simultaneously. Of course, we know this is a virtual construct,
depending on the number of processors, but it certainly could be true
(given enough processors) and the language should not give the user
any implication about process switching underneath. When programmers
start thinking about what should happen when a process-switch occurs,
they are already thinking the wrong way. In that way madness lies! ;-)
I realize that lisp systems traditionally ran on only one processor,
and that the evolution has been to give the users control over a
virtual "process machine". However, I think this is an antiquated
model that should be updated.
In Corman Lisp, multiple threads can run on separate processors, so no
task switch need occur. In any case, the dynamic bindings are
per-stack, and I think would be "shallow" by your definition. All
threads share the outermost binding (which they get if they don't
rebind). However, there is not stack switch overhead, even on a single
processor (other than the normal OS overhead) and no penalty for using
lots of dynamic bindings. And, by the way, there is a fixed cost (I
think two instructions) to fetch any dynamic binding, which makes it
very fast. Nearly as fast as a lexical variable,
Indeed, I have found the ease of declaring, binding and using dynamic
variables in Corman Lisp to be extremely useful, and makes it an
easier language to write thread-safe code in than any version of Java
or C++ I have used. In C++ it is very clumsy (and non-portable) to
have per-stack global variables, and in Java I don't know of any way
other than maybe to derive from the Thread class and add some instance
variables to that, which a thread can use to lookup its
thread-specific bindings (not elegant).
Roger Corman
Tim Bradshaw
> It's important to remember that "slots" are just conceptual notions. How a
> slot is implemented is completely unspecified by the language. This is
> true for all data types, not just symbols; the slots in a DEFSTRUCT or CLOS
> instance don't have to be consecutive locations in memory. For all you
> know, they're implemented like OO objects in Perl, as hash tables that key
> off the slot name.
> [And then about shallow and deep binding]
I'd be interested to know how any lisps that had intentions to run on
multiprocessors do/did special variables.
It's always seemed to me that you'd have to deep bind because you have
no context switch in which to do the binding-diddling (and also if you
expect to have lots of processes you are stuck with an awful lot of
binding-diddling to do. But deep binding means things take
non-uniform time to access which might be bad.
Last night I realised that you could do something cleverer (well, I
thought so) -- you could have a system which shallow-bound *per
process* -- so each process would have something like a hashtable
(perhaps only created on demand the first time it bound a special),
which it would use to do special bindings shallowly.
From something Roger Corman wrote in another branch of this thread it
looks like Corman Lisp might work like that?
--tim
Roger Corman
>* Barry Margolin wrote:
>Last night I realised that you could do something cleverer (well, I
>thought so) -- you could have a system which shallow-bound *per
>process* -- so each process would have something like a hashtable
>(perhaps only created on demand the first time it bound a special),
>which it would use to do special bindings shallowly.
>
>From something Roger Corman wrote in another branch of this thread it
>looks like Corman Lisp might work like that?
In Corman Lisp, a vector of dynamic bindings is maintained as the
system runs. As code is loaded/compiled, this vector is extended each
time a new symbol is encountered and bound to (symbols which never get
dynamically bound to are never added to this vector). All dynamic
bindings are kept in this vector.
There is a master vector, of global bindings, and each process
(thread) has its own copy, which, along with other data like code jump
addresses, are indexed off a committed register (which points to the
thread's particular copy). The compiler knows exactly where the
binding is at any time (a fixed offset off a register) so reading and
setting that binding is very quick.
Roger Corman
Douglas T. Crosher
...
> I'd be interested to know how any lisps that had intentions to run on
> multiprocessors do/did special variables.
> Last night I realised that you could do something cleverer (well, I
> thought so) -- you could have a system which shallow-bound *per
> process* -- so each process would have something like a hashtable
> (perhaps only created on demand the first time it bound a special),
> which it would use to do special bindings shallowly.
The thread branch of CMUCL splits the symbol value into a global
slot and a per thread dynamic value slot. The dynamic value is
shallow bound giving fast access to the current value. A general
symbol value access must first check for a dynamic value and then
if unbound the global value. The symbol may be declared as a
global or dynamic special to speed the access, and in some cases
the compiler can determine that an access is to be dynamic.
On the x86 port the symbol dynamic value is acessed at an offset
within a thread local segment; the offset for each symbol is
allocated when the code is loaded.
Regards
Douglas Crosher
Reini Urban
>> Last night I realised that you could do something cleverer (well, I
>> thought so) -- you could have a system which shallow-bound *per
>> process* -- so each process would have something like a hashtable
>> (perhaps only created on demand the first time it bound a special),
>> which it would use to do special bindings shallowly.
Just wanted to say that this thread is one of the most informative ones
in the last years. Much better than any hairy Queinnec or elsewhere
explanation. (If the gory internals of efficient lexical bindings would
have discussed as well. But these are much easier.)
I would even vote it "My favorite comp.lang.lisp thread at all".
Thanks Simon and others.
--
Reini