Some Performance Advantages of Lexical Scope
I recently had a discussion with Xah Lee about lexical scope in
Emacs Lisp. The topic was why
lexical-binding exists at a file-level
when there was already
cl-lib), prompted by my
previous article on JIT byte-code compilation. The specific
context is Emacs Lisp, but these concepts apply to language design in
Until Emacs 24.1 (June 2012), Elisp only had dynamically scoped variables — a feature, mostly by accident, common to old lisp dialects. While dynamic scope has some selective uses, it’s widely regarded as a mistake for local variables, and virtually no other languages have adopted it.
Way back in 1993, Dave Gillespie’s deviously clever
macro was committed to the
cl package, providing a rudimentary
form of opt-in lexical scope. The macro walks its body replacing local
variable names with guaranteed-unique gensym names: the exact same
technique used in macros to create “hygienic” bindings that aren’t
visible to the macro body. It essentially “fakes” lexical scope within
Elisp’s dynamic scope by preventing variable name collisions.
For example, here’s one of the consequences of dynamic scope.
(defun inner () (setq v :inner)) (defun outer () (let ((v :outer)) (inner) v)) (outer) ;; => :inner
The “local” variable
outer is visible to its callee,
which can access and manipulate it. The meaning of the free variable
inner depends entirely on the run-time call stack. It might
be a global variable, or it might be a local variable for a caller,
direct or indirect.
lexical-let deconflicts these names, giving the effect of
(defvar v) (defun lexical-outer () (lexical-let ((v :outer)) (inner) v)) (lexical-outer) ;; => :outer
But there’s more to lexical scope than this. Closures only make sense
in the context of lexical scope, and the most useful feature of
lexical-let is that lambda expressions evaluate to closures. The
macro implements this using a technique called closure
conversion. Additional parameters are added to the original
lambda function, one for each lexical variable (and not just each
closed-over variable), and the whole thing is wrapped in another
lambda function that invokes the original lambda function with the
additional parameters filled with the closed-over variables — yes, the
variables (e.g. symbols) themselves, not just their values, (e.g.
pass-by-reference). The last point means different closures can
properly close over the same variables, and they can bind new values.
To roughly illustrate how this works, the first lambda expression
below, which closes over the lexical variables
y, would be
converted into the latter by
#: is Elisp’s syntax
for uninterned variables. So
#:x is a symbol
x, but not the
;; Before conversion: (lambda () (+ x y)) ;; After conversion: (lambda (&rest args) (apply (lambda (x y) (+ (symbol-value x) (symbol-value y))) '#:x '#:y args))
I’ve said on multiple occasions that
lexical-binding: t has
significant advantages, both in performance and static analysis, and
so it should be used for all future Elisp code. The only reason it’s
not the default is because it breaks some old (badly written) code.
lexical-let doesn’t realize any of these advantages! In
fact, it has worse performance than straightforward dynamic scope with
New symbol objects are allocated and initialized (
make-symbol) on each run-time evaluation, one per lexical variable.
Since it’s just faking it,
lexical-letstill uses dynamic bindings, which are more expensive than lexical bindings. It varies depending on the C compiler that built Emacs, but dynamic variable accesses (opcode
varref) take around 30% longer than lexical variable accesses (opcode
stack-ref). Assignment is far worse, where dynamic variable assignment (
varset) takes 650% longer than lexical variable assignment (
stack-set). How I measured all this is a topic for another article.
The “lexical” variables are accessed using
symbol-value, a full function call, so they’re even slower than normal dynamic variables.
Because converted lambda expressions are constructed dynamically at run-time within the body of
lexical-let, the resulting closure is only partially byte-compiled even if the code as a whole has been byte-compiled. In contrast,
lexical-binding: tclosures are fully compiled. How this works is worth its own article.
Converted lambda expressions include the additional internal function invocation, making them slower.
lexical-let is clever, and occasionally useful prior to Emacs
24, it may come at a hefty performance cost if evaluated frequently.
There’s no reason to use it anymore.
Constraints on code generation
Another reason to be weary of dynamic scope is that it puts needless
constraints on the compiler, preventing a number of important
optimization opportunities. For example, consider the following
(defun bar () (let ((x 1) (y 2)) (foo) (+ x y)))
Byte-compile this function under dynamic scope (
nil) and disassemble it to see what it looks like.
(byte-compile #'bar) (disassemble #'bar)
That pops up a buffer with the disassembly listing:
0 constant 1 1 constant 2 2 varbind y 3 varbind x 4 constant foo 5 call 0 6 discard 7 varref x 8 varref y 9 plus 10 unbind 2 11 return
It’s 12 instructions, 5 of which deal with dynamic bindings. The
byte-compiler doesn’t always produce optimal byte-code, but this just
so happens to be nearly optimal byte-code. The
discard (a very
fast instruction) isn’t necessary, but otherwise no more compiler
smarts can improve on this. Since the variables
foo, they must be bound before the call and loaded after
the call. While generally this function will return 3, the
compiler cannot assume so since it ultimately depends on the behavior
foo. Its hands are tied.
Compare this to the lexical scope version (
0 constant 1 1 constant 2 2 constant foo 3 call 0 4 discard 5 stack-ref 1 6 stack-ref 1 7 plus 8 return
It’s only 8 instructions, none of which are expensive dynamic variable instructions. And this isn’t even close to the optimal byte-code. In fact, as of Emacs 25.1 the byte-compiler often doesn’t produce the optimal byte-code for lexical scope code and still needs some work. Despite not firing on all cylinders, lexical scope still manages to beat dynamic scope in performance benchmarks.
Here’s the optimal byte-code, should the byte-compiler become smarter someday:
0 constant foo 1 call 0 2 constant 3 3 return
It’s down to 4 instructions due to computing the math operation at
compile time. Emacs’ byte-compiler only has rudimentary constant
folding, so it doesn’t notice that
y are constants and
misses this optimization. I speculate this is due to its roots
compiling under dynamic scope. Since
y are no longer exposed
foo, the compiler has the opportunity to optimize them out of
existence. I haven’t measured it, but I would expect this to be
significantly faster than the dynamic scope version of this function.
Optional dynamic scope
You might be thinking, “What if I really do want
y to be
dynamically bound for
foo?” This is often useful. Many of Emacs’ own
functions are designed to have certain variables dynamically bound
around them. For example, the print family of functions use the global
standard-output to determine where to send output by
(let ((standard-output (current-buffer))) (princ "value = ") (prin1 value))
Have no fear: With
lexical-binding: t you can have your cake and
eat it too. Variables declared with
defvaralias are marked as “special” with an internal bit flag
declared_special in C). When the compiler detects one of these
special-variable-p), it uses a classical dynamic binding.
y as special restores the original semantics,
bar back to its old byte-code definition (next time it’s
compiled, that is). But it would be poor form to mark
special: You’d de-optimize all code (compiled after the declaration)
anywhere in Emacs that uses these names. As a package author, only do
this with the namespace-prefixed variables that belong to you.
The only way to unmark a special variable is with the undocumented
internal-make-var-non-special. I expected
do this, but as of Emacs 25.1 it does not. This could possibly be
considered a bug.
I’ve said there are are absolutely no advantages to
nil. It’s only the default for the sake of backwards-compatibility.
However, there is one case where
lexical-binding: t introduces a
subtle issue that would otherwise not exist. Take this code for
example (and nevermind
prin1-to-string for a moment):
;; -*- lexical-binding: t; -*- (defun function-as-string () (with-temp-buffer (prin1 (lambda () :example) (current-buffer)) (buffer-string)))
This creates and serializes a closure, which is one of Elisp’s unique
features. It doesn’t close over any variables, so it should be
pretty simple. However, this function will only work correctly under
lexical-binding: t when byte-compiled.
(function-as-string) ;; => "(closure ((temp-buffer . #<buffer *temp*>) t) nil :example)"
The interpreter doesn’t analyze the closure, so just closes over
everything. This includes the hidden variable
temp-buffer created by
with-temp-buffer macro, resulting in an abstraction leak.
Buffers aren’t readable, so this will signal an error if an attempt is
made to read this function back into an s-expression. The
byte-compiler fixes this by noticing
temp-buffer isn’t actually
closed over and so doesn’t include it in the closure, making it work
lexical-binding: nil it works correctly either way:
(function-as-string) ;; -> "(lambda nil :example)"
This may seem contrived — it’s certainly unlikely — but it has come
up in practice. Still, it’s no reason to avoid
Use lexical scope in all new code
As I’ve said again and again, always use
lexical-binding: t. Use
dynamic variables judiciously. And
lexical-let is no replacement. It
has virtually none of the benefits, performs worse, and it only
let, not any of the other places bindings are created: