31

While reading through the source code for the dolist macro, I ran into the following comment.

;; This is not a reliable test, but it does not matter because both semantics are acceptable, tho one is slightly faster with dynamic scoping and the other is slightly faster (and has cleaner semantics) with lexical scoping.

Which referred to this snippet (which I've simplified for clarity).

(if lexical-binding
    (let ((temp list))
      (while temp
        (let ((it (car temp)))
          ;; Body goes here
          (setq temp (cdr temp)))))
  (let ((temp list)
        it)
    (while temp
      (setq it (car temp))
      ;; Body goes here
      (setq temp (cdr temp)))))

It surprised me to see a let form being used inside a loop. I used to think that's slow compared to repeatedly using setq on the same external variable (as is done on the second case above).

I would have dismissed that as nothing, if not for the comment immediately above it explicitly saying that's faster than the alternative (with lexical binding). So... Why is that?

  1. Why does the code above differ in performance on lexical vs dynamic binding?
  2. Why is the let form faster with lexical?
38

Lexical binding versus dynamic binding in general

Consider the following example:

(let ((lexical-binding nil))
  (disassemble
   (byte-compile (lambda ()
                   (let ((foo 10))
                     (message foo))))))

It compiles and immediately disassembles a simple lambda with a local variable. With lexical-binding disabled, as above, the byte code looks as follows:

0       constant  10
1       varbind   foo
2       constant  message
3       varref    foo
4       call      1
5       unbind    1
6       return    

Note the varbind and varref instructions. These instructions bind and lookup respectively variables by their name in a global binding environment on heap memory. All this has an adverse effect on performance: It involves string hashing and comparison, synchronisation for global data access, and repeated heap memory access which plays badly with CPU caching. Also, dynamic variable bindings need to be restored to their previous variable at the end of let, which adds n additional lookups for each let block with n bindings.

If you bind lexical-binding to t in the above example, the byte code looks somewhat different:

0       constant  10
1       constant  message
2       stack-ref 1
3       call      1
4       return    

Note that varbind and varref are entirely gone. The local variable is simply pushed onto the stack, and referred to by a constant offset via the stack-ref instruction. Essentially, the variable is bound and read with constant time, in-stack memory reads and writes, which is entirely local and thus plays well with concurrency and CPU caching, and does not involve any strings at all.

Generally, with lexical binding lookups of local variables (e.g. let, setq, etc.) have much less runtime and memory complexity.

This specific example

With dynamical binding, each let incurs a performance penalty, for above reasons. The more lets, the more dynamic variable bindings.

Notably, with an additional let within the loop body, the bound variable would need to be restored at every iteration of the loop, adding an additional variable lookup to each iteration. Hence, it's faster to keep the let out of the loop body, so that the iteration variable is only reset once, after the whole loop finished. However, this is not particularly elegant, since the iteration variable is bound way before it's actually required.

With lexical binding, lets are cheap. Notably, a let within a loop body is not worse (performance-wise) than a let outside of a loop body. Hence, it's perfectly fine to bind variables as locally as possible, and keep the iteration variable confined to the loop body.

It's also slightly faster, because it compiles to much less instructions. Consider the followed side-by-side disassembly (local let on the right side):

0       varref    list            0       varref    list         
1       constant  nil             1:1     dup                    
2       varbind   it              2       goto-if-nil-else-pop 2 
3       dup                       5       dup                    
4       varbind   temp            6       car                    
5       goto-if-nil-else-pop 2    7       stack-ref 1            
8:1     varref    temp            8       cdr                    
9       car                       9       discardN-preserve-tos 2
10      varset    it              11      goto      1            
11      varref    temp            14:2    return                 
12      cdr       
13      dup       
14      varset    temp
15      goto-if-not-nil 1
18      constant  nil
19:2    unbind    2
20      return    

I have no clue, though, what's causing the difference.

7

In short — dynamic binding is very slow. Lexical binding is extremely fast at runtime. The fundamental reason is that lexical binding can be resolved at compile time, while dynamic binding cannot.

Consider the following code:

(let ((x 42))
    (foo)
    (message "%d" x))

When its compiling the let, the compiler cannot know whether foo will acess the (dynamically bound) variable x, so it must create a binding for x, and must retain the name of the variable. With lexical binding, the compiler just dumps the value of x on the bindings stack, without its name, and accesses the right entry directly.

But wait — there's more. With lexical binding, the compiler is able to verify that this particular binding of x is only used in the code to message; since x is never modified, it is safe to inline x and yield

(progn
  (foo)
  (message "%d" 42))

I don't think that the current bytecode compiler performs this optimisation, but I am confident that it will do so in the future.

So in short:

  • dynamic binding is a heavy-weight operation that allows few oportunities for optimisation;
  • lexical binding is a lightweight operation;
  • lexical binding of a read-only value can often be optimised away.
3

This comment does not suggest that lexical binding is either faster or slower than dynamic binding. Rather, it suggests that those different forms have different performance characteristics under lexical and dynamic binding, eg, one of them is preferable under one binding discipline, and the other preferable in the other.

So is lexical scope faster than dynamic scope? I suspect that in this case that there isn't much difference, but I don't know - you'd really have to measure it.

  • 1
    There is no varbind in code compiled under lexical binding. That's the whole point and purpose. – lunaryorn Oct 14 '14 at 14:55
  • Hmm. I created a file containing the above source, beginning with ;; -*- lexical-binding: t -*-, loaded it, and called (byte-compile 'sum1), assuming that produced a definition compiled under lexical binding. However, it doesn't seem to have. – gsg Oct 14 '14 at 17:51
  • Removed the byte code comments as they were based on that wrong assumption. – gsg Oct 14 '14 at 17:54
  • lunaryon's answer shows that this code clearly is faster under lexical binding (although of course only at the micro level). – shosti Oct 14 '14 at 18:40
  • @gsg This declaration is just a standard file variable, which has no effect on functions invoked from outside of the corresponding file buffer. IOW, it only has an effect if you visit the source file and then invoke byte-compile with the corresponding buffer being current, which is—by the way—exactly what the byte compiler is doing. If you invoke byte-compile separately, you need to explicitly set lexical-binding, as I did in my answer. – lunaryorn Oct 15 '14 at 7:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.