Subject: Re: Smug scheme weenies?
From: rpw3@rpw3.org (Rob Warnock)
Date: Tue, 11 Jan 2005 22:17:51 -0600
Newsgroups: comp.lang.lisp
Message-ID: <eIOdnf8W0qxyOXncRVn-hg@speakeasy.net>
Ron Garret  <rNOSPAMon@flownet.com> wrote:
+---------------
| > Each thread maintain a vector containing the addresses of variables
| > which are known to occur "free".  By default, each slot in this vector
| > points to the corresponding global value of its variable.  When
| > variables are dynamically bound, this address is saved and replaced
| > with the address of the dynamic binding.  No runtime decision making
| > occurs because the correct value, dynamic or global, is always
| > accesses through the same location.
+---------------

IIRC hallway conversations at ILC 2003, both Allegro and Corman Lisp
use exactly this technique (or minor variations thereof).

+---------------
| > store the value of Y to the address found at X's offset into this
| > environment structure.  It may update a dynamic value if X has been
| > rebound, otherwise, the global value is updated.
| 
| Well, that's devilishly clever.  It's worth noting that this solution 
| would probably be slower in practice than one which involved run-time 
| decision making (because you always have to touch memory twice)...
+---------------

Yes, but the "extra" memory you touch [one pointer redirection]
is almost always cached if you've touched that variable recently.

And if you're doing accessing the variable multiple times in the
same thread-safe region of cade [e.g., for read-modify-write, say],
you only pay the "extra" accesses once. The generated code can locally
cache the final address for all the accesses.

Note that this makes thread-switching *very* fast, since all you have
to do is change a global pointer to the current-thread global/special-
variable-vector to point to the new thread's vector.

+---------------
| ...and it also suffers from the same problem as that solution,
| namely, that you have to do a global analysis...
+---------------

Not really. Whether a variable is being used as a global or a special
is lexically apparent, so the usual lexical-versus-global compilation
choice [which you have to make any during compilation/evaluation] can
be made in isolation when compiling [or preprocessing for interpretation]
the access. And you can assign global/special-variable vector slots
lazily as find that you need them during compilation/evaluation, caching
the slot number in the symbol's internal data.

The main inefficiency that I see [and it's probably minor in most
applications] is that if a global/special is bound [and notice
that I say "bound", rather than "defined" -- it matters!!] in *any*
thread, then a slot must be allocated for it in *all* threads
[but only allocated, not set].


-Rob

-----
Rob Warnock			<rpw3@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607