静态作用域的性能优势

Question

最近与 Xah Lee 就 Emacs Lisp 中的静态作用域进行了一番讨论.
主题是既然 cl-lib 已经提供了 lexical-let 那为什么还需要搞出个 lexical-binding 来为整个文件设定静态作用域.
该讨论是由我上篇关于 JIT byte-code compilation 的文章所引发的.
虽说讨论的内容是关于 Emacs Lisp 的,但是对大多数的其他语言也同样适用.

在 Emacs 24.1 (June 2012) 之前, Elisp 只支持动态作用域 — 这一特性是从 lisp 的早期方言中继承下来的.
虽说动态作用域在某些情况下会有些用处,但是仍然普遍被认为不适于用来定义局部变量,而且基本上没有其他语言再支持动态作用域的了.

cl package 于 1993 年将 Dave Gillespie 所写的 lexical-let 宏 纳入其中 , 该宏可以提供对 opt-in 静态作用域的简单模拟.
该宏会遍历它的 body,并用 gensym 来生成一个唯一的名字来代替局部变量的名字: 该技术本身就常用于为宏提供一个不与宏 body 中变量冲突的绑定.
通过保证变量名的唯一性就可以很好的为 Elisp 动态作用域模拟出静态作用域的效果来.

举个例子, 在动态作用域下:

  (defun inner ()
    (setq v :inner))

  (defun outer ()
    (let ((v :outer))
      (inner)
      v))

  (outer)
  ;; => :inner

v 是 outer 的局部变量,但却对它的被调函数 inner 可见, 因此会被 inner 访问和修改.
inner 中自由变量 v 具体指代的是谁完全由当时的运行时调用栈所决定的. 它既可能是一个全局变量,也可能某个直接或非直接调用者中的局部变量.

使用 lexical-let 将这些名称变得各不相同可以达到类似静态作用域的效果.

  (defvar v)

  (defun lexical-outer ()
    (lexical-let ((v :outer))
      (inner)
      v))

  (lexical-outer)
  ;; => :outer

不过静态作用域可不仅仅只是这个作用而已,它还常被用于创建闭包. lexical-let 也常被用于将 lambda 表达式转换成闭包.
为了模拟闭包,该宏使用了一种称之为 closure conversion 的技术. 它会向原 lambda 函数中添加参数,每个静态变量（而不仅仅是那些被捕获的变量(closed-over variable)) 都有一个对应的参数,
然后它再用另一个 lambda 函数来将原 lambda 函数和参数封装起来,并且在内部,它会把这些参数赋值成被捕获的变量本身(symbol) 而不是他们的值（就好像引用传递一样) 哦,然后适用这些参数来调用原 lambda 函数.
The last point means different closures can properly close over the same variables, and they can bind new values.

下面简单地展示一下这个过程, 假设第一个 lambda 表达式通过 lexical-let 捕获 x 和 y 变量,则会被转换成后面那种形式.
其中 #: 是 Elisp 用于表达 uninterned variables 的语法. So #:x is a symbol x, but not the symbol x(看不懂这个例子,也不知道这句话怎么翻译~~) (详情请参阅 print-gensym 变量的说明).

  ;; Before conversion:
  (lambda ()
    (+ x y))

  ;; After conversion:
  (lambda (&rest args)
    (apply (lambda (x y)
             (+ (symbol-value x)
                (symbol-value y)))
           '#:x '#:y args))

我曾在多种场合都说过: 将 lexical-binding 设为 t ,在性能和静态分析时带来极大的优势, 因此你在编写新 Elisp 代码时应该总是将选项打开.
该选项之所以没有默认打开,纯粹是因为它会使得那些老旧的代码无法正常工作.
可惜的是, lexical-let 并不具备这些优势! 事实上,它比动态作用域下的 let 性能要更低下.

1. 每次运行时都需要为那些被捕获的变量创建并初始化新的 symbol 对象.
2. lexical-let 依然使用的是动态绑定,而访问动态绑定要比访问静态绑定的性能要低大约 30%,具体低多少有赖于编译 Emacs 的 C 编译器.
   赋值的性能就更糟糕了,对动态绑定赋值要比对静态绑定赋值多出大约 650%的时间.
   至于具体怎么算的,我有在其他文件中说过.
3. 它是使用 symbol-value 来访问这些所谓的 “静态”变量的, 函数调用本身就消耗巨大,因此它甚至比访问普通的动态变量还慢.
4. lexical-let 需要动态地在运行时拼装 lambda 表达式,因此它不能完全地被编译成字节码. 而 lexical-binding: t 闭包能完全地被编译成字节码.
   至于它是怎么被编译到,那又得写另一篇文章来说明了.
5. 转换后的 lambda 表达式在内部又会产生一次函数调用,使得速度更慢了.

虽说 lexical-let 实现的很精妙,对于 Emacs24 之前的版本也蛮有用的,但是若用的太频繁的话会带来繁重的性能消耗. 因此已经没有理由再用它了.

• Constraints on code generation

另一个启用动态作用域的理由是,它给编译器带来了无谓的约束,使得编译器无法很好的优化代码.
举个例子,假设有这么一个 bar 函数:

  (defun bar ()
    (let ((x 1)
          (y 2))
      (foo)
      (+ x y)))

在动态作用域中将之编译成字节码,然后 将它翻译成汇编代码 看看是什么东西:

  (byte-compile #'bar)
  (disassemble #'bar)

这会弹出一个 buffer 有以下内容:

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

一共有 12 条指令,其中 5 条是用来处理动态绑定的. 字节码编译器并不总是会生成最优化的字节码,只不过刚好这次产生的字节码优化程度比较高而已.
其中的 discard 指令 (这是个非常快的指令) 是多余的, 除此之外已经无法再进一步优化了.
由于变量 x,y 对 foo 可见,这两个变量必须在 foo 调用前与它们的值绑定然后再 在函数调用后加载它们的值 .
虽说一般情况下,这个函数的结果应该是 3,但是编译器不能做这样的条件假设,因为最终的结果还有赖于 foo 函数的行为,这种情况下,编译器没法尽情地进行优化.

现在来比较一下静态作用域(lexical-binding: t) 下是怎样的 :

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

只有 8 条指令,而且并没有任何与动态变量相关的指令（这类指令都比较昂贵). 而这还不能算是最优化的字节码.
事实上, Emacs 25.1 的字节码编译器一般都无法为静态作用域变量生成最优化的字节码,这还有待进一步的改进.
即时如此,静态作用域在性能评测上依然比摔动态作用域几条街.

如果某一天编译器足够聪明的话,它应该会产生这样的最优化字节码:

0       constant  foo
1       call      0
2       constant  3
3       return

它会在编译期就计算好了,因此就只需要产生 4 条指令.
Emacs 的字节编译器还不完善,因此它无法发觉 x 和 y 其实是常量,因此无法优化到这个层次.
I speculate this is due to its roots compiling under dynamic scope.
由于 x 和 y 对 foo 不可见, 因此编译器可以尽情地进行优化,就好像 foo 不存在一样.
我没有具体测量过,但是可以遇见,这要比动态作用域下快得多的多.

• Optional dynamic scope

你可能会想, “要是我就是想 x 和 y 处于动态作用域下怎么办?” 有时候动态作用域是有用的. 许多 Emacs 的函数当初设计的时候就是要与某些动态绑定的变量配合使用的.
比如,print 家族里的函数就使用全局变量 standard-output 来决定默认将结果输出到哪里去.

  (let ((standard-output (current-buffer)))
    (princ "value = ")
    (prin1 value))

不要担心: 使用 lexical-binding: t 可以让你做到两全其美.
使用 defvar , defconst , 以及 defvaralias 定义的变量都会标记为"特殊的".
当编译器发现是这些特殊变量时 (special-variable-p), 它会使用经典的动态绑定.

将 x 和 y 声明为特殊变量会使得 bar 在编译时生成之前旧的字节码.
另外,将 x 和 y 这样名字的变量标记为特殊变量可不太好,因为它会影响到其他使用到这些名字的代码.
作为一个 package 的编写者,你应该只将那些属于你独有的变量标记为特殊变量,这些独有变量一般都带有命名空间的前缀.

目前只有一种方法可以将特殊变量变回普通变量,那就是使用函数 internal-make-var-non-special , 但该函数并没有提供文档说明.
我本以为 makunbound 也能起到相同的作用,但是在 Emacs 25.1 中它做不到这一点. 也算是各 bug 吧.

• Accidental closures

我说过的, lexical-binding: nil 根本没有任何优势. 纯粹是为了向后兼容才让它成为默认项的.
不过有一种情况, lexical-binding: t 可能会有点小麻烦. 比如下面这段代码（请暂时忽略 prin1-to-string 的存在):

  ;; -*- lexical-binding: t; -*-

  (defun function-as-string ()
    (with-temp-buffer
      (prin1 (lambda () :example) (current-buffer))
      (buffer-string)))

这会创建并序列化一个闭包, 能够创建并序列化闭包应该算是 Elisp 独一无二的特性了吧.
该闭包并没有捕获任何变量,因此它的序列化结果本应该很简单的. 可是,在 lexical-bingding: t 的情况下,该函数必须被编译成字节码才能够得到正确的结果.

  (function-as-string)
  ;; => "(closure ((temp-buffer . #<buffer  *temp*>) t) nil :example)"

出现问题的原因在于,解释器并不会区分析闭包,它只是单纯第捕获所有的变量.
因此 with-temp-buffer 创建的隐藏变量 temp-buffer 也会被捕获进来,这样一来就出现问题了.
Buffer 本身是不能通过 read 被读取出来的,因此当读取该函数时回引发一个错误.
而编译器会注意到 temp-buffer 并没有被捕获,因此就不会包括到闭包中,也就没有问题了.

当然在 lexical-binding: nil 的环境下,它也没问题:

  (function-as-string)
  ;; -> "(lambda nil :example)"

这个例子看起来很做作 — 这种情况确实不太可能发生 — 但是 它确实是取之于现实的 .
不过虽然如此,依然不是什么不使用 lexical-binding: t 的理由.

• Use lexical scope in all new code

重要的事情说三遍: 总是使用 lexical-binding: t . 谨慎使用动态变量.
要认识到 lexical-let 并不是一个好的替代. 它几乎一无是处,糟糕的性能,还只能用于 let，对于其他像函数参数,dotimes,dolist 和 condition-case 语句中的绑定就无能为力了.