利用 JS 函数柯里化，实现高性能虚拟机（1）

[EtherDream]

前言

元旦期间，相信大家都被微信小游戏刷屏了，各种玩法攻略铺天盖地。当得知这是用 JS 开发时，立马想把过去写的 JS 游戏都翻新一遍。于是打开小游戏的官网，查看开发文档。

然而遗憾的是，小游戏虽然是用 JS 写的，但它并非运行在浏览器环境里，因此和 HTML 并不兼容。此外，在官网文档上，还看见一条奇葩的规则：

...
2.与小程序一样，小游戏每次发布需要经过审核。我们在小程序和小游戏中都移除了动态执行代码的能力，包括以下调用方式：
（1）eval 函数
（2）setTimeout、setInterval 函数第一个参数传入代码字符串执行
（3）使用 Function 传入字符串构造函数
（4）使用 GeneratorFunction 传入字符串构造生成器函数
...

咋一看貌似有些道理，要是开放 eval 的话，代码可以从网络上更新，就能绕过官方审核了。

但是，开发者若真想动态执行，那根本就是拦不住的 —— 在代码里藏一个虚拟机不就可以了吗。之前我们探讨《使用 VM 壳混淆 JavaScript 代码》时，就讲解了 JS 虚拟机的概念，让程序根据不同的数据，执行不同的操作。虽然性能不高，但用于简单临时的场合，还是没问题的。

这时冒出个想法：要是能把性能优化得足够好的话，是不是可以让整个小游戏都由虚拟指令实现，这样程序只需发布一次就再也不用审核了呢？

于是开始探索，一个不用 eval、而是由 JS 自我驱动的图灵机，性能最高能达到多少。

[EtherDream]

解释器

传统模式

传统的虚拟机大多是解释执行的。例如，执行一条加法指令：

虚拟字节码      汇编码            备注
00 00 01 02  | ADD r0, r1, r2  | r0 = r1 + r2

解释器先从内存中读取指令，然后跳入相应的 case，接着读取操作数 —— 这才开始真正的计算。最后，还得将结果保存，以及判断是否继续运行，等等。。。

mem = [0,0,1,2, ...]
reg = []
...
do {
  op = mem[pc++]
  ...

  switch (op) {
  case OP_ADD:      // 加法指令
    x = reg[mem[pc++]]
    y = reg[mem[pc++]]
    a = x + y       // 真正的计算！
    reg[mem[pc++]] = a
    ...
  case OP_SUB:      // 减法指令
    ...
    a = x - y
    ...
  }
} while (...)

解释器的原理很简单，但效率却非常低。因为每执行一条指令，都要做大量额外的计算，导致性能降低几十甚至上百倍！

那么是否有办法，能减少运行时的计算量呢？

静态展开

例如上述 r0 = r1 + r2 的计算，我们能否单独设计一条叫 ADD_R0_R1_R2 的指令，这样解释时只需执行：

case OP_ADD_R0_R1_R2:
  reg[0] = reg[1] + reg[2]

于是就能减少 3 次数组访问和递增计算。

这看起来好像不错，但是实现起来就有问题了 —— 假如我们的虚拟机有 8 个寄存器，那么光是加法指令，就得提供 8^3 个 case：

case OP_ADD_R0_R0_R0:
  reg[0] = reg[0] + reg[0]
case OP_ADD_R0_R0_R1:
  reg[0] = reg[0] + reg[1]

// 此处省略几百行 ...

case OP_ADD_R7_R7_R7:
  reg[7] = reg[7] + reg[7]

而这还只是寄存器与寄存器的模式，若再算上立即数、内存等组合，那代码还不炸了！

动态展开

显然，我们不能在代码里静态展开各种 case，而必须采取一种更灵活的方式，动态生成程序逻辑。

先来设想下，如果把寄存器的读写变成函数调用的形式：

function get_r0() { return reg[0] }
function get_r1() { return reg[1] }
...
function set_r0(v) { reg[0] = v }
function set_r1(v) { reg[1] = v }
...

那么 r0 = r1 + r2 就变成这样：

set_r0(get_r1() + get_r2())

当然，这行代码仍是写死的。然而和之前不同的是，现在用的是函数，而函数的行为，是可通过「函数变量」动态改变的！

因此，我们只需提供这样的一个模板：

dst(src1() + src2())

即可实现 任意两个寄存器相加，并将结果保存到任意寄存器！

那么，怎样才能将 set_r0, get_r1, get_r2 这几个函数填充到模板里，然后得到一个「无需参数」的新函数呢？

柯里化

简介

熟悉函数式编程的同学，相信对「柯里化」这个名词不会陌生。它可以把函数的参数事先进行绑定，运行时只需提供更少的参数。

例如，一个加法函数：

function add_xy(x, y) {
  return x + y
}

正常情况下，调用它需要两个参数：

add_xy(arg1, arg2)

假如 arg1 经常用到某个值，我们不妨将其事先绑定，得到一个只接受 arg2 的函数。通过闭包，这很容易实现：

function add_x(x) {
  return function(y) {
    return x + y
  }
}

var add_100 = add_x(100)

这样后期调用时，只需传入 arg2 就可以了：

add_100(10)     // 110
add_100(20)     // 120

更进一步，假如 arg1、arg2 都经常用到某个值，我们甚至可继续降阶：

function add(x, y) {
  return function() {
    return x + y
  }
}

var f1 = add(100, 10)
f1()    // 110

这样，运行时无需传入任何参数了。

应用

事实上，预先绑定的参数并没有类型限制，无论数字、字符还是对象都可以。既然如此，函数型也可以。

于是，前面我们提到的加法模板，就可以这样实现：

function add(dst, src1, src2) {
  return function() {
    dst(src1() + src2())
  }
}

当解释器预处理 ADD r0, r1, r2 指令时，为其生成一个闭包函数：

f = add(set_r0, get_r1, get_r2)

未来运行时，只需 f() 即可实现 reg[0] = reg[1] + reg[2] 这一连串的逻辑，而无需解码指令、分析操作数等额外步骤！

性能

也许你会说，这么做只是将细节隐藏起来，交给 JS 引擎了而已，复杂度并没有真正降低。而且连寄存器读写这么频繁的操作，都要变成函数调用，性能恐怕会更糟吧。

看起来好像确实如此。然而如今的 JS 引擎，都有较强的优化能力 —— 尤其对于简短的函数，完全可被内联优化。

例如上述那条加法指令，我们测试下柯里化后的性能。首先，观察等价的「硬编码」有多快：

const reg = [11, 22, 33, 44]
console.time('t1')

for (let i = 0; i < 100000000; i++) {
  reg[0] = reg[1] + reg[2]
}
console.timeEnd('t1')

在我的电脑上，硬编码花费 140ms 左右。接着尝试柯里化的方案：

const reg_get = [
  function() { return reg[0] },
  function() { return reg[1] },
  function() { return reg[2] },
]
const reg_set = [
  function(v) { reg[0] = v },
  function(v) { reg[1] = v },
  function(v) { reg[2] = v },
]

function add(dst, src1, src2) {
  return function() {
    dst(src1() + src2())
  }
}

// 动态数据
let [c1, c2, c3] = JSON.parse('[0,1,2]')
let fnOP = add
let args = [ reg_set[c1], reg_get[c2], reg_get[c3] ]

// 动态生成 r0 = r1 + r2 的逻辑
const f = fnOP.apply(null, args)

const reg = [11, 22, 33, 44]
console.time('t2')

for (let i = 0; i < 100000000; i++) {
  f()
}
console.timeEnd('t2')

结果：耗时仍在 140ms 上下 —— 两者相差无几，有时甚至后者还更快一些！

在线测试：https://jsfiddle.net/vassd787/2/

尽管柯里化的方案看起来更冗余，但那些都是易优化的，因此经过 JS 引擎内联后，两者性能几乎相同！

更多指令

运算符

前面我们实现了加法模板，现在来补充更多的运算，例如数学运算、位运算、JS 操作等等。

不过，要给每种运算都写一个函数套函数，也是挺累赘的。事实上我们可以进一步精简，将运算符也柯里化：

function mod(x, y) { return x % y }
function xor(x, y) { return x ^ y }
function get(x, y) { return x[y] }
function has(x, y) { return x in y }
// ...

function OP2(op, dst, src1, src2) {
  return function() {
    dst(op(src1(), src2()))
  }
}

// mod r3, r5, r7
f1 = OP2(mod, set_r3, get_r5, get_r7)

// xor r0, r0, r1
f2 = OP2(xor, set_r0, get_r0, get_r1)

这样，任意二元运算指令，都可以套用这个模板了！

类似的，一元、三元都可使用这种方式。

立即数

当然，指令的操作数未必都是寄存器，也可能是立即数：

SUB r0, r1, 100     # r0 = r1 - 100

对于这个常量 100，又该如何实现呢？

事实上，同样可用闭包解决！我们设计一个函数，专门用于立即数的包装：

function imm(v) {
  return function() {
    return v
  }
}

这样，只需调用 imm(x)，即可得到一个「能返回 x」的函数：

var imm_100 = imm(100)
imm_100()       // 100

现在我们将 imm_100 作为参数传给 OP2：

f = OP2(sub, set_r0, get_r1, imm_100)

因为 OP2 里统一使用 src() 获得源数据，并不关心取自寄存器、还是立即数，所以就能实现 r0 = r1 + 100 的逻辑！

寄存器

类似的，寄存器的传递、赋值，也可通过闭包实现：

function mov(dst, src)  {
  return function() {
    dst(src())
  }
}

f1 = mov(set_r0, get_r1)
f2 = mov(set_r2, imm_100)

f1()    // reg[0] = reg[1]
f2()    // reg[2] = 100

流程

事实上，所有的存储指令、运算指令，都可在「运行前」生成相应的闭包函数，最终得到一个函数列表：

 字节码   (0x00, 0x02, ...)
   ↓
 预处理
   ↓
函数列表  (fn, fn, fn, ...)

那么，如何将这些函数有序地驱动起来？其中判断、循环又该如何实现？请看下一篇。

[EtherDream]

下一篇：#4

[legend80s]

一篇一篇慢慢来，刷新业务前端的知识疆域