Richard Gabriel writes, in [Performance and Evaluation of Lisp Systems](http://www.dreamsongs.com/Books.html):
> The performance profiles for free/special lookup and binding are > very different depending on whether you have deep or shallow > binding. In shallow-binding implementations, times for function > call and internal binding of free/special variables are inflated > because of the additional work of swapping bindings. On some > deep-binding systems, referencing a dynamically bound variable > (which includes all variable references from the interpreter) can > require a search along the access path to find the value. Other > systems cache pointers to the value cells of freely referenced > free/special variables on top of the stack; caching can take place > upon variable reference/assignment or upon entry to a new lexical > contour, and at each of these points the search can be one > variable at a time or all/some variables in parallel. > Shallow-binding systems look up and store into value cells, the > pointers to which are computed at load time. Deep-binding systems > bind and unbind faster than shallow-binding systems, but > shallow-binding systems look up and store values faster. > Context-switching can be performed much faster in a deep-binding > implementation than in a shallow-binding one. Deep binding > therefore may be the better strategy for a multi-processing Lisp. It occurred to me that there is actually a continuum between these two, using hash tables, as was done in many Forth implementations. Suppose you hash each symbol into one of eight buckets, and have one alist hanging off each bucket. Then saving a context requires saving up to eight cells --- more than one, as in deep binding, but potentially fewer than the total number of variable values being restored, as in shallow binding; and looking up a value requires a linear search along only one eighth of the total number of dynamic variables. Also, the hash table size need not be fixed; it can change over time, or from program to program. When the hash table size is 1 --- that is, there's only one hash bucket --- you have traditional deep binding. When it's large enough that no hash bucket has more than one variable in it, you have traditional shallow binding. If you had about sqrt(number of variables) buckets, then both lookup and swapping of bindings would be O(sqrt(number of variables)). This may seem a bit irrelevant today, since "special variables" (i.e. dynamically-scoped variables) are used very rarely.
